Updating to GCC 3.4/4? Want to use 2006.1 profile? READ THIS

[ck42]

One request....

my / partition is fairly small (512M) and the log file that is created and kept in /root is getting VERY close to filling that partition. Not sure what happens at the point that the partition is full, but I'd rather not find out. I have another ~300 packages left and only about 90Megs left.

Can you provide an option in the script to prompt for the log file location?

[Guenther Brunthaler]

Can you provide an option in the script to prompt for the log file location?

A good point. Having a small root partition is actually a preferable system layout, especially when some logical volume manager is used for the other partitions.

I will add a command line option for this in the next version, allowing to freely specify the base directory where log files will be created.

I'm also considering to change the default base directory to somewhere below /var/tmp, as there is typically plenty of space there in Gentoo installations.

Or perhaps just using the system logger? What are services like syslog-ng and cron/logrotate good for, if not for such tasks? But that's just an idea yet.

In the meantime, please manually edit the generated script and change the $HOME part of the line

Code: Select all

LOG_FILE="$HOME/${BASENAME}_$(date '+%Y-%m-%dT%T').log"

to a directory of your choice.

[ck42]

Thanks.
Looks like ~60 packages left....and about 60Megs left. I think I'll make it this time. For other systems I'll go in edit $HOME though...until the option is made available.

[steveL]

I think now it must have something to do with you bash's settings.

You know, the operation of bash is influenced by several environment variables like SHELLOPTS and POSIXLY_CORRECT as well as by builtins such as shopt and set.

I therefore suggest that you check those settings.

For instance, if your bash runs in POSIX mode, it will disable most extensions, including process substitution. Read section 6.11 of the bash info manual for more details on POSIX mode.

I don't think it's in POSIX mode; POSIXLY_CORRECT is not set.
echo $SHELLOPTS gives:
braceexpand:emacs:hashall:histexpand:history:interactive-comments:monitor
(no posix)
shopt gives:
cdable_vars off
cdspell off
checkhash off
checkwinsize on
cmdhist on
dotglob off
execfail off
expand_aliases on
extdebug off
extglob off
extquote on
failglob off
force_fignore on
gnu_errfmt off
histappend on
histreedit off
histverify off
hostcomplete on
huponexit off
interactive_comments on
lithist off
login_shell off
mailwarn off
no_empty_cmd_completion off
nocaseglob off
nocasematch off
nullglob off
progcomp on
promptvars on
restricted_shell off
shift_verbose off
sourcepath on
xpg_echo off

Could it be one of those?

[Guenther Brunthaler]

echo $SHELLOPTS gives:
braceexpand:emacs:hashall:histexpand:history:interactive-comments:monitor

Looks good.

shopt gives:

I diff'ed your settings and mine:

Code: Select all

$ diff -bu yours mine
--- yours       2006-10-01 06:30:01.000000000 +0200
+++ mine        2006-10-01 06:30:12.000000000 +0200
@@ -7,15 +7,15 @@
 execfail off
 expand_aliases on
 extdebug off
-extglob off
+extglob                on
 extquote on
 failglob off
 force_fignore on
 gnu_errfmt off
 histappend on
-histreedit off
-histverify off
-hostcomplete on
+histreedit             on
+histverify             on
+hostcomplete           off
 huponexit off
 interactive_comments on
 lithist off

The only flag that seems interesting here is the extglob flag.

But unfortunately, setting extglob to off did not change anything on my box.

Which means there must be some other reason for your shell to not support process substitution.

Perhaps it's not a shell issue, but rather a system issue?

Bash supports process substitution if it is available - but what if it's not avaiable for some reason?

Do you perhaps use a special/customized version of the Kernel oder glibc? Or is there anything else unusual / especially tailored in your system that you are aware about?

Perhaps you are running your Gentoo installation on a special hardware platform (PDA or something)?

Obviously there must be some presumably small but essential difference in our basic system configurations; we only have to find it.

I have an up-to-date system using the default-linux/x86/2006.1/desktop profile; standard PC-platform. Nothing special regarding bash or the typical Gentoo execution environment.

[steveL]

Firstly, can I just say thanks for trying to help me with this.

The only flag that seems interesting here is the extglob flag.

But unfortunately, setting extglob to off did not change anything on my box.

Which means there must be some other reason for your shell to not support process substitution.

Agreed. according to man bash:
extglob If set, the extended pattern matching features described above under Pathname Expansion are enabled.

Perhaps it's not a shell issue, but rather a system issue?

Bash supports process substitution if it is available - but what if it's not avaiable for some reason?

Do you perhaps use a special/customized version of the Kernel oder glibc? Or is there anything else unusual / especially tailored in your system that you are aware about?

Perhaps you are running your Gentoo installation on a special hardware platform (PDA or something)?

Obviously there must be some presumably small but essential difference in our basic system configurations; we only have to find it.

I have an up-to-date system using the default-linux/x86/2006.1/desktop profile; standard PC-platform. Nothing special regarding bash or the typical Gentoo execution environment.

I'm running gentoo on a desktop, same profile as you. The only possible difference I can think of is that I originally had -mfpmath=sse (it's an Athlon-XP) in my make.conf, and then I read that it actually works slower under current gcc, due to problems in glibc.
I installed my system (from stage 3) with gcc 4.1.1 (first thing i emerged from 2006.0 disk) and have never actually had any problems (apart from this one, of course!) I've reemerged glibc recently. I certainly haven't put any special options for bash or anything else I can think of. Are there kernel options I might have set? (Kernel is self-compiled.) It couldn't be anything to do with having linux-headers-2.11 originally when the kernel is 2.6.17-r7?
Although I'm sure bash has been updated since the kernel headers were..
I guess I could try recompiling the kernel for the newer version that came out recently (2.6.17-r8,) although that feels like a cop out.
I was going to try using your script to generate the list of packages and then [topic=497125]this script[/topic] to compile (there are instructions in that topic to do exactly that.) I'd still, however, like to solve this problem, tho hopefully it'd go away after a complete recompile.

[Guenther Brunthaler]

I'm running gentoo on a desktop, same profile as you. The only possible difference I can think of is that I originally had -mfpmath=sse

I doubt this problem has something to do with FP math or special compiler options. This would render your whole system unstable, and not just that one specific bash feature.

Most likely it's the fault of some non-standard option in some configuration or initialization file related to bash operation.

If you haven't especially customized the bash initialization files in /etc, it might be easiest to re-emerge bash

Code: Select all

emerge --oneshot bash

and then run etc-update or dispatch-conf and let those tools replace your old copies of the initialization files by up-to-date copies.

I was going to try using your script to generate the list of packages and then [topic=497125]this script[/topic] to compile

That should no longer be necessary, as the current version of my script has already incorporated count_zero's extensions.

Also note that the process substitution feature is not necessary for the primary operation of the script. It's only used for the newly added logfile feature.

Just delete the following lines

Code: Select all

    exec > >(
         echo "Note: Logging to file '$LOG_FILE'."
         tee "$LOG_FILE"
         echo
         echo "Note: A log has been written to '$LOG_FILE'."
      )

from the generated script. The script will then run without generating a log file.

But you can do this yourself by running

Code: Select all

./recompile-remaining-packages 2>&1 | tee mylogfile

Of course this will not solve your process substitution problem, but at least you can use my script to recompile your system.

If re-emerging bash does not help in re-activating the process substitution feature, then I'm afraid I have no more clues what to do next.

But I'll remember the issue and will tell you if any better ideas should happen to come to my mind.

[steveL]

I doubt this problem has something to do with FP math or special compiler options. This would render your whole system unstable, and not just that one specific bash feature.

Nah, didn't think it would be the problem. One thing that gets me with this whole thing is the issue of binary compatibility- after all gcc should be compiling to the same ABI (unless one has changed eg -malign-double) so personally I can't see the need for all this. (And yes I have read all the explanations as to why it's necessary; I just don't buy 'em.) I'm doing this more because I changed my NLS USE flag (to turn it on.)

Most likely it's the fault of some non-standard option in some configuration or initialization file related to bash operation.

If you haven't especially customized the bash initialization files in /etc, it might be easiest to re-emerge bash

Code: Select all

emerge --oneshot bash

and then run etc-update or dispatch-conf and let those tools replace your old copies of the initialization files by up-to-date copies.

I was going to try using your script to generate the list of packages and then [topic=497125]this script[/topic] to compile

That should no longer be necessary, as the current version of my script has already incorporated count_zero's extensions.

Does your script delete dependencies of failed packages from the list as his does? (Only I can't find that in the recompile script.)

Also note that the process substitution feature is not necessary for the primary operation of the script. It's only used for the newly added logfile feature.

Just delete the following lines

Code: Select all

    exec > >(
         echo "Note: Logging to file '$LOG_FILE'."
         tee "$LOG_FILE"
         echo
         echo "Note: A log has been written to '$LOG_FILE'."
      )

from the generated script. The script will then run without generating a log file.

But you can do this yourself by running

Code: Select all

./recompile-remaining-packages 2>&1 | tee mylogfile

Thanks that's excellent.

Of course this will not solve your process substitution problem, but at least you can use my script to recompile your system.

If re-emerging bash does not help in re-activating the process substitution feature, then I'm afraid I have no more clues what to do next.

But I'll remember the issue and will tell you if any better ideas should happen to come to my mind.

Thank you for your excellent support.

[Guenther Brunthaler]

Does your script delete dependencies of failed packages from the list as his does? (Only I can't find that in the recompile script.)

No, but that should not be too bad: The script tries to recompile the failing packages again at the end of the recompilation anway. And if the dependencies of the failing packages are already compiled at that time, they need not be compiled then.

This means the dependendies will be compiled sooner than necessary in this case, but they will not be compiled unnecessarily.

Thank you for your excellent support.

I'm glad if I can help.

[steveL]

No, but that should not be too bad: The script tries to recompile the failing packages again at the end of the recompilation anway. And if the dependencies of the failing packages are already compiled at that time, they need not be compiled then.

This means the dependendies will be compiled sooner than necessary in this case, but they will not be compiled unnecessarily.

(Just being pedantic) can I suggest you incorporate that in your next update? I'm thinking of a situation where a library changes a header.

Again, vielen dank.

[Guenther Brunthaler]

can I suggest you incorporate that in your next update? I'm thinking of a situation where a library changes a header.

Incorporate what?

If you meant the recompilation feature: This is already part of the current script!

Again, vielen dank.

Gerne geschehen!

[steveL]

I don't mean recompilation, I mean deferring dependencies until after the failed package.

So if a lib changed its header files, and the lib failed to emerge, then its dependencies would also be marked failed and consequently compiled after it.

Just trying to avoid dependency hell/ gentoo borks in the longer term.

[Guenther Brunthaler]

I don't mean recompilation, I mean deferring dependencies until after the failed package.

Oh, I see.

So if a lib changed its header files, and the lib failed to emerge, then its dependencies would also be marked failed and consequently compiled after it.

This sounds great, indeed.

But I'm afraid I have no idea how to implement this: My script uses the combined output of emerge -ep system and emerge -ep world as input for its operation.

This is a long list of packages to be compiled. But there is no indication which of the packages in the list are dependencies.

So my script simply can't tell which of those packages are dependencies of what other packages ... it all compiles them in order, skipping failing packages (and retrying them again at the end).

Certainly the dependency information is dug somewhere inside Portage, but like most of us I have only very limited knowledge about the internals of Portage: I'm not a Gentoo dev guru.

So I'm afraid I cannot implement that feature with my current level of knowledge.

Perhaps I'll retry some time later after I have gained more Gentoo experience.

[steveL]

Well count_zero's script uses:

Code: Select all

       failedpkgdeps=`echo $failedpkg | sed 's/-[0-9].*//'` 
       deps=`equery depends $failedpkgdeps | sed '/^\[/d' | sed 's/-[0-9].*//'` 
       for each in `echo $deps` 
       do 
          if [[ -n `cat $emergelist | grep "$each"` ]] 
             then 
             if [[ -n `emerge -p $each | grep "$failedpkg"` ]] 
                then 
                each2=`cat $emergelist | grep $each | sed 's/\=//'` 
                echo "$each2 (depends on $failedpkg)" >> $failedlist 
                eachsed=`echo $each | sed 's|\/|\\\/|'` 
                cat $emergelist | sed "/$eachsed/d" > $emergetemp 
                mv $emergetemp $emergelist 
                echo "*** $each depends on $failedpkg, skipping." 
                else : 
             fi 
             else : 
          fi 
       done 
       echo "*** Continuing with emerge world"

That should give you a start?

I'm off now, but I'll check on this later.
PS: Why doesn't (or how does) what this topic work? This is the 2nd topic I've tried to watch, but I never get any indication that something's been added. (And I'm a bit tired of seeing `egosearch' )

[Guenther Brunthaler]

That should give you a start?

I'll check it out.

Anyway, one has to be very cautious when dropping dependencies: What if a dependent package is also a direct or an indirect dependency of some other package?

If it skipped a package in such a situation, the other packages which depend on the skipped dependencies would fail building as well, potentially leading to an unwanted avalance-effect.

In order to track dependencies, my script also needed to run "equery depends" for each and every package, and record the results somewhere. This would require a major rewrite of my script.

Also, skipping dependencies is a rather futile effort anyway:

• By definition, dependencies must be compiled before the package which uses them.
• If a package using the dependencies fails to compile, it will be too late: The dependencies have already been compiled.

Of course, it makes sense to skip packages which depend on dependencies which are known to not have been built successfully.

Which brings us back to the problem of how to get, store and retrieve that list from within a simple shell script (I'm not using Perl or something in the generated script for stability reasons: Perl & friends depend on too many components which could result in problems when those programming envrironments are recompiled themselves during the system rebuild.)

And there is also the "statistical" argument: If the emerge -uDN world was performed successfully before running my script, chances for packages failing the subsequent system rebuild are rather small.

Which means, only a very small number of packages will be affected by those problems at all.

PS: Why doesn't (or how does) what this topic work?

Via e-mail. Each time a followup-article is posted, an e-mail containing a link to the new entry will be sent to you.

As far as I can remember, it's all part of the forum user profile. At least I didn't change anything since I registered with the forum, and it has worked fine so far.

Perhaps there is a simple typing error in your registered e-mail-address? Be sure to check it.

[steveL]

Anyway, one has to be very cautious when dropping dependencies: What if a dependent package is also a direct or an indirect dependency of some other package?

If it skipped a package in such a situation, the other packages which depend on the skipped dependencies would fail building as well, potentially leading to an unwanted avalance-effect.

I think we're using the same word to opposite effect; I'm using dependency to mean a package which need this one. So a lot of things are dependencies of glibc for instance. But agreed dependencies of the dependencies (eg if glibc failed, and a lib using it which is then used by another package) do also need to be failed.

In order to track dependencies, my script also needed to run "equery depends" for each and every package, and record the results somewhere. This would require a major rewrite of my script.

No, you just need to check when a package fails as count_zero's does. (That bit would go in the main loop of recompile_remaining_packages.) Granted for every dependency that you moved to the fail list, you'd also have to check packages that require it, but that's still a lot less than `each and every package.' And as you said, you get to the fail list at the end. If a package fails again, you can just mark it (and it's dependencies) as permanently failed.

Also, skipping dependencies is a rather futile effort anyway:

• By definition, dependencies must be compiled before the package which uses them.
• If a package using the dependencies fails to compile, it will be too late: The dependencies have already been compiled.

Of course, it makes sense to skip packages which depend on dependencies which are known to not have been built successfully.

This is where we're getting our words mixed up as outlined above. Sorry if I'm using dependency in an invert to the normal usage.

Which brings us back to the problem of how to get, store and retrieve that list from within a simple shell script (I'm not using Perl or something in the generated script for stability reasons: Perl & friends depend on too many components which could result in problems when those programming envrironments are recompiled themselves during the system rebuild.)

Well I reckon we can easily slot that bit into your bash script. I'll have a look in a little while.

And there is also the "statistical" argument: If the emerge -uDN world was performed successfully before running my script, chances for packages failing the subsequent system rebuild are rather small.

Which means, only a very small number of packages will be affected by those problems at all.

Yes, but it' be even better if we could only run an emerge --sync and then your script.

Via e-mail. Each time a followup-article is posted, an e-mail containing a link to the new entry will be sent to you.

As far as I can remember, it's all part of the forum user profile. At least I didn't change anything since I registered with the forum, and it has worked fine so far.

Thanks, I've finally been notified of a couple of updates. (Dunno why it wasn't doing them over the last few days, but wtf.)

[count_zero]

I think that you would run into problems trying to implement this dependency feature--you may as well just do it the old way, and allow the emerge world to die if a package fails.

Suppose a package fails. For example, I just picked out a random package from xorg, x11-misc/xbitmaps. The following packages on (my) system "depend" on xbitmaps:
x11-base/xorg-server-1.1.1
x11-apps/xsetroot-1.0.1
x11-libs/openmotif-2.2.3-r9

Now these packages have to be considered "failed" packages as well, and here are the packages that depend on them:
x11-drivers/xf86-input-keyboard-1.1.0
x11-drivers/xf86-video-nv-1.2.0
x11-drivers/xf86-video-fbdev-0.3.0
x11-drivers/xf86-video-vesa-1.2.1
x11-drivers/xf86-input-mouse-1.1.1
x11-drivers/synaptics-0.14.5-r1
x11-drivers/nvidia-drivers-1.0.8774
gnome-base/libbonoboui-2.14.0
gnome-base/libgnomecanvas-2.14.0
x11-base/xorg-x11-7.1
x11-libs/gtk+-2.8.20-r1
media-video/kaffeine-0.8.1-r1
virtual/x11-7.0-r2
kde-base/kdebase-startkde-3.5.4

This is as far as I went, but you would have to do the same for *each* of these packages as well--you would delay building any packages that depend on them, and those that depend on them, et cetera--as Guenther put it, an "avalanche" effect. Is it really best to delay building all of these packages for xbitmaps? Do I care if kaffeine is built upon an xorg-server that is built with the latest xbitmaps? Maybe, but probably not. I already have an older version of xbitmaps that will allow xorg to compile. Skipping xbitmaps and allowing the rest of the system to continue building is probably good enough.

Just my 2 cents.

[steveL]

This is as far as I went, but you would have to do the same for *each* of these packages as well--you would delay building any packages that depend on them, and those that depend on them, et cetera--as Guenther put it, an "avalanche" effect. Is it really best to delay building all of these packages for xbitmaps? Do I care if kaffeine is built upon an xorg-server that is built with the latest xbitmaps? Maybe, but probably not. I already have an older version of xbitmaps that will allow xorg to compile. Skipping xbitmaps and allowing the rest of the system to continue building is probably good enough.

Just my 2 cents.

Blimey that's a lot. Fair enough. So what does your script do (one layer of depends?)

[count_zero]

My script looks for packages that require the failed package to be built before proceeding. For instance, continuing with my example above:

if xbitmaps were to fail, the script would perform "equery depends x11-misc/xbitmaps", producing these packages as dependents:
x11-base/xorg-server-1.1.1
x11-apps/xsetroot-1.0.1
x11-libs/openmotif-2.2.3-r9

These aren't automatically removed from the emerge queue. Rather, the output of emerge -p is performed on each of them. If xbitmaps were really needed to proceed, portage would include xbitmaps in the output of emerge -p. However, since I already have an old version of xbitmaps, portage doesn't require that the new version be installed before proceeding with these emerges. Thus, the script only removes packages which must be built before proceeding.

I hope I explained this okay.

[gerard27]

Hi Günther,
Man this is some script you wrote!
My box is churning away now.
I am having a problem with php not wanting to compile for all kinds of reasons.
When I did an emerge -uD world it would stop and I'd have to issue emerge --resume --skipfirst to
continue.Now I can go to bed and it will simply wait till all the rest is compiled.
My box runs alright without it even though some programs depend on it.
I don't do any php coding.
Thanks a lot man.
Gerard

[Guenther Brunthaler]

I think we're using the same word to opposite effect

I see; you are right. Then it's also clear to me now what you actually wanted to suggest in the first place.

No, you just need to check when a package fails as count_zero's does.

Initially, I was not sure whether this could be dangerous: My script uses static version numbers; that is it uses the version numbers (and dependencies) at the time when the script was generated.

I thus had concerns whether an equery depends, run at some later time, would actually return the same dependency version numbers, or different ones (after another emerge --sync).

But as I see it now, there are two possibilities in this case:

• The version numbers of the dependencies are still the same. In this case it would not be a problem to move the matching packages to the list of failing packages.
• The version numbers are different. In this case the match will not be detected and the dependent packages will still be emerged, resulting in a potential failure. But this is actually the same as it happens now for each package, and thus not worse than it is now.

However, there is still another problem with the suggested approach: Circular dependencies.

Unfortunately, some ebuilds contain circular dependencies.

That is, package A depends on package B, and package B depends on package A.

Although such a relationship is clearly illegal from a logical point of view, it nevertheless is a fact that the Portage tree contains such dependencies.

When emerge --emptytree world is run, it selects an arbitrary package order (such as by lexicographical order of the package name), and uses that order in the package list it generates.

So, let's say the real dependency were: First package B, then package A. But emerge --emptytree shows the opposite order.

In this case, the current version of my script will first compile package A, which will fail (because package B is not available), and put package A into the list of failing packages.

Then it will try to compile package B (because it was not aware of the fact that package B seems to be dependent on package A), which will succeed (because package B is not really dependent on package A).

Finally, after all the other packages have been recompiled, my script will recompile package A again. And this time it will succeed, because package A is already there.

Which means, my script will not be severely affected by incorrect dependency entries in Portage: Due to its incremental nature, any package order will eventually work.

The script would even succeed if no package dependency information was available at all and if the packages are displayed by emerge --emptytree in arbitrary random order.

In other words: The script takes a safe approach which allows to succeed even in case of conflicting or even completely wrong dependency ordering as reported by equery depend.

If it would honor dependency information, it could be sped up by skipping dependent packages, but it would lose its capability to reliably resolve circular dependencies.

If a package fails again, you can just mark it (and it's dependencies) as permanently failed.

As outline above, this could be dangerous in the case of circular dependencies, especially in cases where indirect dependency cycles are used: Package A depends on B depends on C depends on A.

The current approach allows to resolve all such dependencies correctly (if they can be resolved at all), being tolerant to incorrect dependency information.

The simple algorithm used also guarantees that the process will terminate eventually, never resulting in an infinite loop.

[hielvc]

When emerge --emptytree world is run, it selects an arbitrary package order (such as by lexicographical order of the package name), and uses that order in the package list it generates.

Wrong. If you check out "man 5 ebuild " You have DEPEND, RDEPEND, and PDEPEND. Portage goes thourgh the ebuilds checking the depends such that kde isnt built before X11. The major problem for scripts like ours is we are getting list from "'emerge blah -p > file" but portage doesnt run the ebuilds in --pretend and will miss some of the DEPEND's. Heck it miss's some ocassionally when running for real. In the last week 1 or 2 patchs have been rreleashed improving this.

In emwrap.sh one of the options is to build "world -e" minus "system -e" where for a small gain in speed I sort the system and world outputs "comm" them to remove the system files and then useing the orignal world sort the "world - minus system" files back into the same order for building.

As for what to do with failed builds I stick them into file called 'faild' list them at the end and the next time emwrap.sh is run offer to build them. In the case of "emwrap.sh world -uDN it isnt really important just re-run emwrap.sh -wuDn and anything needing updateing show up again. In the case of a system/world --emptytree it can but rarely does cause problems. Its only when your useing it to rebuild a stage3 or stage1 form scratch that you could end up wtih a really long failed list

[Guenther Brunthaler]

When emerge --emptytree world is run, it selects an arbitrary package order (such as by lexicographical order of the package name), and uses that order in the package list it generates.

Wrong. If you check out "man 5 ebuild " You have DEPEND, RDEPEND

Sorry for being not specific enough. I meant the above in the context of circular dependencies only, where there seems not to be any "right order" to do things.

In this context only I assumed Portage will select an arbitrary order, such as lexicographical ordering (because I have no idea how it actually determines the package order in such cases).

[Guenther Brunthaler]

Hi all,

Due to multiple misunderstandings how my script resolves "circular" (i. e. incorrectly reported) dependencies, I have written a simulation in order to demonstrate by example how the algorithm works.

Here is the output of the simulation run:

Code: Select all

"recompile-entire-system" Algorithm Simulation

Number of simulated packages: 200
Number of simulated dependencies: 600
Packages in simulated "emerge --emtpytree" order: DC, E, ES, GL, BF, EH, GG, 
    FJ, FM, AA, CH, CB, GQ, P, BE, BR, BU, GS, GA, AF, FC, EQ, CJ, R, F, K, GO,
    AW, BP, FY, EE, CS, CW, BK, DQ, CL, Y, DK, EJ, CV, GF, DL, FR, EW, DM, CC, 
    DW, CY, AJ, DT, DJ, GM, ET, EM, AO, DP, C, CU, I, AD, FZ, DE, BH, GE, CA, 
    CI, B, EV, BW, AY, ED, FD, EA, Z, FS, G, EU, BV, GR, AM, L, CX, GP, AP, FU,
    CF, AB, FG, GI, BN, BY, FV, FL, W, FH, FP, EK, DZ, CK, J, CM, BC, T, DH, 
    BD, GK, FE, AN, BQ, X, AX, EX, DN, EL, V, EY, FN, EN, AU, H, CN, DY, CR, 
    DX, DO, BI, GH, AE, EG, FX, M, AV, EP, GB, CE, DU, D, BB, BX, EI, AT, AS, 
    EF, O, GC, DV, BM, BT, AK, BL, BZ, DA, DF, AC, GD, AZ, DB, DI, S, AR, AQ, 
    FF, ER, DS, EO, BG, FB, EB, CQ, BJ, U, FI, FA, FO, FQ, GN, N, DR, BS, GJ, 
    BA, AI, FK, CZ, FW, EC, EZ, DD, BO, CP, CO, CG, AG, AH, FT, AL, CD, DG, Q, 
    CT.
Dependencies (Format: "package(dependencies)"): AA(EI), AB(BL, BR, D), AC(Z), 
    AD(J), AE(BO, CO), AG(AB), AH(AI, AJ, Z), AK(DY, Z), AL(CV, DL, R), AM(AJ, 
    AR, BL, M, Z), AN(AJ, AR, BY, CY, F, FE, FQ), AO(DF), AP(AJ, FE, J, Z), 
    AQ(AF, AI, FE), AR(AF, FJ), AS(AI, CZ, EJ, FJ, FR), AT(AO, CR, DT, DY, GQ),
    AU(AF, CV, FE), AV(BT, ED, F, GH), AW(AJ, CM), AX(CM, CV, DT), AY(DF, DT, 
    FQ, J, X), AZ(BD, CB, DF, DS, EA), B(AC, BD, BM, BS, CP, EF, GG, GK), 
    BA(AJ, BS, CM, D, FM), BB(BL, Z), BC(AF, AH, AK, CO, EG, X), BD(BL, BT), 
    BE(AM, F, X), BF(EK, FG, GQ), BG(BS, CH, G, GQ, J, X), BH(AJ, BS, D, FJ, 
    GR), BI(EW), BJ(BL, F, FG, J, R, T), BK(BD, CX, FJ, X), BM(FE), BN(BL, CY, 
    EW), BO(EK, FD), BP(BS, CO, ES), BQ(AR, DC, EW, FE), BR(CV, ED), BS(DF), 
    BT(Z), BU(BI, CO, DF, F, GL), BV(BL, FT), BW(AR, BM), BX(AB, DT, GK, J), 
    BY(AF), BZ(BY), C(AF, AJ), CA(EP, FG, GK), CB(AQ, BL, DS, EX), CC(AR, BZ, 
    DH, ET), CD(CO, DV, EA, FG), CE(EQ), CF(BY, D, EQ, J), CG(FJ, GM, GO, X), 
    CH(AV, ER), CI(BF, BS, DT, EW, F), CJ(DF, DH, Q), CK(AI, EP, FG, GM, J), 
    CL(AQ, D), CM(FJ), CN(AC, AO, BM, CO, CZ, R), CO(ED), CP(CV, DF, DL, FJ, 
    FT), CQ(AI, BZ, CM), CR(CV, D, DF, DL, J), CS(BL, BS, GP), CT(CM, DL, F, 
    Z), CU(BN), CV(DF), CW(AJ, BT, CZ, D, DV, F), CX(BR, DI), CY(BL, CM, EW), 
    D(AR, BL, CO, T), DA(CV, DF, GB), DB(BS, CZ, EI), DC(FQ, GQ), DD(AJ, GM), 
    DE(AB, BI, FE, GK), DG(C, CO, GF), DH(BD), DI(EW, FO, GK), DJ(AU, CV, DL, 
    EW), DK(ER), DM(CO, FR), DN(AF, BM, DV, EC), DO(AI, AR, BV, DT, EK, EW), 
    DP(AD, BT, FG, FJ), DQ(CQ, T), DR(CM, CV, ED, FT), DS(BI, EM), DU(AF, DR, 
    DT, FT), DV(FG), DW(DV, EI, GG), DX(AR, DS, FE, FG, GQ), DY(AI, DL, EW), 
    DZ(AH, CM), E(AC, AJ, CH, FE, FG, S), EA(AF, DL), EB(AC, BD, BI, BQ), 
    EC(AR, DL, FO, GK), EE(AF, X, Z), EF(DF, EW, FE), EG(DF, EW, FJ, GF), 
    EH(CO, FG, GK, GQ, X), EI(AF, D, GQ, J), EJ(ED, FG, FT, Y), EK(AR, F), 
    EL(EK, EX, FE, FG), EM(G), EN(AF, AU, FK), EO(AQ, BY, CU), EP(CV, F, GK, 
    J), EQ(CP, DF), ER(AR, BY, EF, GK), ES(AK, CM), ET(BL, BV, FU), EU(AI, BF, 
    CM, CO, CR, DL), EV(BI, BM), EW(F, GK), EX(BT, DR), EY(BT, FE, FT, GK, T), 
    EZ(BT, CN, E, EP, FG), FA(CO, FJ, FU), FB(C, EW, F, FG, GJ), FC(AR, BD, DD,
    DV), FD(BB, FG, GK), FE(ED), FF(AS, CZ, EA, EF), FH(BM, DT, FY), FI(AR, F, 
    FE, GP), FJ(AJ), FK(AI, DN, DT, FO), FL(AC, CZ, EA, FJ, J), FM(AO, CM, FJ, 
    J), FN(AF, AH, AI, CO, FE, GA, J), FO(CV, FE, FG, FT, J, T), FP(AK, T), 
    FQ(CY, DV), FR(DV), FS(AI, AO, FM), FU(J, O), FV(AQ, CV, EI), FW(GK, Z), 
    FX(BR, GB), FY(AJ, BN, CV, EK, FE), FZ(CV, EE, FT, T), G(BM, CO), GA(AI, 
    DT, FE), GB(BW, DF, DL, FJ), GC(AI, BN, FJ), GD(CY, FJ), GE(FA, GK, X), 
    GF(BL, DF, FO), GG(AC, DV, ED, FE, GK), GH(CV, DF, DT), GI(BQ, CV, DL), 
    GJ(DL, GF), GL(BW, DV, ED, F, FJ, FT, X), GM(AR, BM, EP, FM, Z), GN(CV, DU,
    GJ), GO(AD, DV), GP(AO, BQ, DI, DY, FE, GK), GQ(BS), GR(DF, DX, GK, GQ), 
    GS(CO, DT, F, T), H(DF, DZ, EW), I(CZ, DM), J(BM, F), K(AH, AM, CV, DY, FT,
    GF), L(BL, BT, CO, DF, G, GK), M(AI, AR, BT), N(DF), O(EA, GQ), P(AC, BD, 
    BM, J), Q(EI), R(DS, FS), S(EA, J), T(BM), U(BD, CZ, FT, M), V(BY, FJ), 
    W(AF, BL, DM, DS, FJ), X(AJ, DV), Y(BC, DF, ED, ER, FG, GG, GK), Z(DF).

Phase 1:
Packages left to be recompiled in order: DC, E, ES, GL, BF, EH, GG, FJ, FM, AA,
    CH, CB, GQ, P, BE, BR, BU, GS, GA, AF, FC, EQ, CJ, R, F, K, GO, AW, BP, FY,
    EE, CS, CW, BK, DQ, CL, Y, DK, EJ, CV, GF, DL, FR, EW, DM, CC, DW, CY, AJ, 
    DT, DJ, GM, ET, EM, AO, DP, C, CU, I, AD, FZ, DE, BH, GE, CA, CI, B, EV, 
    BW, AY, ED, FD, EA, Z, FS, G, EU, BV, GR, AM, L, CX, GP, AP, FU, CF, AB, 
    FG, GI, BN, BY, FV, FL, W, FH, FP, EK, DZ, CK, J, CM, BC, T, DH, BD, GK, 
    FE, AN, BQ, X, AX, EX, DN, EL, V, EY, FN, EN, AU, H, CN, DY, CR, DX, DO, 
    BI, GH, AE, EG, FX, M, AV, EP, GB, CE, DU, D, BB, BX, EI, AT, AS, EF, O, 
    GC, DV, BM, BT, AK, BL, BZ, DA, DF, AC, GD, AZ, DB, DI, S, AR, AQ, FF, ER, 
    DS, EO, BG, FB, EB, CQ, BJ, U, FI, FA, FO, FQ, GN, N, DR, BS, GJ, BA, AI, 
    FK, CZ, FW, EC, EZ, DD, BO, CP, CO, CG, AG, AH, FT, AL, CD, DG, Q, CT.
Packages successfully compiled: AF, F, DL, AJ, DT, C, ED, EA, FG, BY, GK, FE, 
    DV, BM, BL, BZ, DF, N, BS, AI, CZ, CO, FT, CD.
Failed packages: DC, E, ES, GL, BF, EH, GG, FJ, FM, AA, CH, CB, GQ, P, BE, BR, 
    BU, GS, GA, FC, EQ, CJ, R, K, GO, AW, BP, FY, EE, CS, CW, BK, DQ, CL, Y, 
    DK, EJ, CV, GF, FR, EW, DM, CC, DW, CY, DJ, GM, ET, EM, AO, DP, CU, I, AD, 
    FZ, DE, BH, GE, CA, CI, B, EV, BW, AY, FD, Z, FS, G, EU, BV, GR, AM, L, CX,
    GP, AP, FU, CF, AB, GI, BN, FV, FL, W, FH, FP, EK, DZ, CK, J, CM, BC, T, 
    DH, BD, AN, BQ, X, AX, EX, DN, EL, V, EY, FN, EN, AU, H, CN, DY, CR, DX, 
    DO, BI, GH, AE, EG, FX, M, AV, EP, GB, CE, DU, D, BB, BX, EI, AT, AS, EF, 
    O, GC, BT, AK, DA, AC, GD, AZ, DB, DI, S, AR, AQ, FF, ER, DS, EO, BG, FB, 
    EB, CQ, BJ, U, FI, FA, FO, FQ, GN, DR, GJ, BA, FK, FW, EC, EZ, DD, BO, CP, 
    CG, AG, AH, AL, DG, Q, CT.

Phase 2:
Packages left to be recompiled in order: DC, E, ES, GL, BF, EH, GG, FJ, FM, AA,
    CH, CB, GQ, P, BE, BR, BU, GS, GA, FC, EQ, CJ, R, K, GO, AW, BP, FY, EE, 
    CS, CW, BK, DQ, CL, Y, DK, EJ, CV, GF, FR, EW, DM, CC, DW, CY, DJ, GM, ET, 
    EM, AO, DP, CU, I, AD, FZ, DE, BH, GE, CA, CI, B, EV, BW, AY, FD, Z, FS, G,
    EU, BV, GR, AM, L, CX, GP, AP, FU, CF, AB, GI, BN, FV, FL, W, FH, FP, EK, 
    DZ, CK, J, CM, BC, T, DH, BD, AN, BQ, X, AX, EX, DN, EL, V, EY, FN, EN, AU,
    H, CN, DY, CR, DX, DO, BI, GH, AE, EG, FX, M, AV, EP, GB, CE, DU, D, BB, 
    BX, EI, AT, AS, EF, O, GC, BT, AK, DA, AC, GD, AZ, DB, DI, S, AR, AQ, FF, 
    ER, DS, EO, BG, FB, EB, CQ, BJ, U, FI, FA, FO, FQ, GN, DR, GJ, BA, FK, FW, 
    EC, EZ, DD, BO, CP, CG, AG, AH, AL, DG, Q, CT.
Packages successfully compiled: FJ, GQ, GA, CV, FR, EW, DM, AO, I, Z, G, BV, J,
    CM, T, X, AX, V, AU, DY, BI, GH, EP, BB, EF, O, BT, AK, AC, S, AR, AQ, ER, 
    CQ, FO, DR, FW, EC, CP, AH, CT.
Failed packages: DC, E, ES, GL, BF, EH, GG, FM, AA, CH, CB, P, BE, BR, BU, GS, 
    FC, EQ, CJ, R, K, GO, AW, BP, FY, EE, CS, CW, BK, DQ, CL, Y, DK, EJ, GF, 
    CC, DW, CY, DJ, GM, ET, EM, DP, CU, AD, FZ, DE, BH, GE, CA, CI, B, EV, BW, 
    AY, FD, FS, EU, GR, AM, L, CX, GP, AP, FU, CF, AB, GI, BN, FV, FL, W, FH, 
    FP, EK, DZ, CK, BC, DH, BD, AN, BQ, EX, DN, EL, EY, FN, EN, H, CN, CR, DX, 
    DO, AE, EG, FX, M, AV, GB, CE, DU, D, BX, EI, AT, AS, GC, DA, GD, AZ, DB, 
    DI, FF, DS, EO, BG, FB, EB, BJ, U, FI, FA, FQ, GN, GJ, BA, FK, EZ, DD, BO, 
    CG, AG, AL, DG, Q.

Phase 3:
Packages left to be recompiled in order: DC, E, ES, GL, BF, EH, GG, FM, AA, CH,
    CB, P, BE, BR, BU, GS, FC, EQ, CJ, R, K, GO, AW, BP, FY, EE, CS, CW, BK, 
    DQ, CL, Y, DK, EJ, GF, CC, DW, CY, DJ, GM, ET, EM, DP, CU, AD, FZ, DE, BH, 
    GE, CA, CI, B, EV, BW, AY, FD, FS, EU, GR, AM, L, CX, GP, AP, FU, CF, AB, 
    GI, BN, FV, FL, W, FH, FP, EK, DZ, CK, BC, DH, BD, AN, BQ, EX, DN, EL, EY, 
    FN, EN, H, CN, CR, DX, DO, AE, EG, FX, M, AV, GB, CE, DU, D, BX, EI, AT, 
    AS, GC, DA, GD, AZ, DB, DI, FF, DS, EO, BG, FB, EB, BJ, U, FI, FA, FQ, GN, 
    GJ, BA, FK, EZ, DD, BO, CG, AG, AL, DG, Q.
Packages successfully compiled: ES, EH, GG, FM, BR, GS, EQ, AW, BP, EE, DQ, DK,
    GF, CY, DJ, GM, EM, AD, FZ, CA, EV, BW, FD, FS, L, AP, FU, BN, FL, FP, EK, 
    DZ, CK, BD, EX, DN, EL, EY, FN, H, DO, EG, M, AV, GB, CE, DU, D, EI, GC, 
    DA, GD, DB, DI, DS, U, FA, FQ, GJ, BA, FK, DD, BO, DG, Q.
Failed packages: DC, E, GL, BF, AA, CH, CB, P, BE, BU, FC, CJ, R, K, GO, FY, 
    CS, CW, BK, CL, Y, EJ, CC, DW, ET, DP, CU, DE, BH, GE, CI, B, AY, EU, GR, 
    AM, CX, GP, CF, AB, GI, FV, W, FH, BC, DH, AN, BQ, EN, CN, CR, DX, AE, FX, 
    BX, AT, AS, AZ, FF, EO, BG, FB, EB, BJ, FI, GN, EZ, CG, AG, AL.

Phase 4:
Packages left to be recompiled in order: DC, E, GL, BF, AA, CH, CB, P, BE, BU, 
    FC, CJ, R, K, GO, FY, CS, CW, BK, CL, Y, EJ, CC, DW, ET, DP, CU, DE, BH, 
    GE, CI, B, AY, EU, GR, AM, CX, GP, CF, AB, GI, FV, W, FH, BC, DH, AN, BQ, 
    EN, CN, CR, DX, AE, FX, BX, AT, AS, AZ, FF, EO, BG, FB, EB, BJ, FI, GN, EZ,
    CG, AG, AL.
Packages successfully compiled: DC, GL, BF, AA, CH, CB, P, BU, FC, R, GO, FY, 
    CW, CL, DW, ET, DP, CU, GE, CI, B, AY, AM, CX, CF, AB, FV, W, FH, BC, DH, 
    AN, BQ, EN, CN, CR, DX, AE, FX, BX, AT, AZ, EO, BG, FB, EB, BJ, GN, CG, AG,
    AL.
Failed packages: E, BE, CJ, K, CS, BK, Y, EJ, CC, DE, BH, EU, GR, GP, GI, AS, 
    FF, FI, EZ.

Phase 5:
Packages left to be recompiled in order: E, BE, CJ, K, CS, BK, Y, EJ, CC, DE, 
    BH, EU, GR, GP, GI, AS, FF, FI, EZ.
Packages successfully compiled: E, BE, CJ, K, BK, Y, EJ, CC, DE, EU, GR, GP, 
    GI, AS, FF, FI, EZ.
Failed packages: CS, BH.

Phase 6:
Packages left to be recompiled in order: CS, BH.
Packages successfully compiled: CS, BH.
Failed packages: <none>.

Success - all packages have been recompiled!

In the above example, the algorithm required 6 phases (passes) in order to reach its ultimate goal "no more packages left to be recompiled".

The simulator assumes a package will compile successfully if all its dependencies are already compiled at the time the package is due to be compiled.

The order in which compilations are attempted is the order as shown in the lists.

Note that the example uses random ordering of the packages, which is equivalent to having no dependency information available at all to the algorithm.

The real script uses the dependency information from Portage, which means multiple passes will only result from incorrectly reported dependencies (or from other temporary factors, such as an ebuild failing because the machine ran out of memory during the compilation when other processes ate up to much memory at that time).

[Guenther Brunthaler]

For those who like to toy around with the simulation, here is the simulator script:

Code: Select all

#! /usr/bin/perl -w

use strict;
srand 42;
my $NUM_PACKAGES= 200;
my $MAX_NUM_DEPS= 600;
my $MAX_TRIES= 1e5;
#
my($n, $i, $i2, @f, @s, %h, $k, $a, $t, @p);
# List of packages.
$k= 'A';
for ($n= $NUM_PACKAGES; $n--; ) {
   push @p, ++$k;
}
# Reorder as displayed by simulated "emerge -ep world".
for ($i= @p; $i--;) {
   $i2= int rand @p;
   @p[$i, $i2]= @p[$i2, $i];
}
# Generate random dependencies.
my %d;
sub dep {
   my($p, $on)= @_;
   return 1 if $d{$p} && $d{$p}->{$on};
   foreach (keys %{$d{$p} || {}}) {
      return 1 if &dep($p, $_);
   }
   return undef;
}
$t= 0;
for ($n= $MAX_NUM_DEPS; $n--; ) {
   ($i, $i2)= @p[int(rand @p), int rand @p];
   if ($i eq $i2 || exists $d{$i} && exists $d{$i}->{$i2} || dep $i2, $i) {
      last if ++$t > $MAX_TRIES;
      redo;
   }
   $d{$i}= {} unless exists $d{$i};
   $d{$i}->{$i2}= 1;
   $t= 0;
}
sub pwrap {
   our $c= 0; our $width= 79, our $oi; our $indent= " " x 4;
   my @a= map {
      $_ ne "\n" && /^\s+$/ ? " " : $_;
   } split /
      (?<= \n) | (?= \n)
      | (?<= \s) (?= \S)
      | (?<= \S) (?= \s)
   /xs, join '', @_;
   my $ol;
   for (my $i= 0; $i < @a; ) {
      if ($a[$i] eq "\n") {
         if ($c) {print "\n"; $c= 0}
         undef $oi;
         while ($i + 1 < @a && $a[$i + 1] eq "\n") {
            print "\n"; ++$i;
         }
      } else {
         $ol= length $a[$i];
         if ($c + $ol > $width) {
            print "\n"; $c= 0; $oi= 1;
            while ($i < @a && $a[$i] eq " ") {
               ++$i;
            }
            next;
         }
         if ($oi) {
            print $indent;
            $oi= 0; $c= length $indent;
         }
         print $a[$i]; $c+= $ol;
      }
      ++$i;
   }
}
sub sum {
   my $s= 0;
   for (my $i= @_; $i--; ) {
      $s+= $_[$i];
   }
   return $s;
}
pwrap
   "\"recompile-entire-system\" Algorithm Simulation\n\n"
   , "Number of simulated packages: ", scalar(@p), "\n"
   , "Number of simulated dependencies: "
   , sum(map scalar keys %{$d{$_}}, keys %d), "\n"
   , "Packages in simulated \"emerge --emtpytree\" order: "
   , join(", ", @p), ".\n"
   , "Dependencies (Format: \"package(dependencies)\"): "
   , join(
      ", ", map "$_(" . join(", ", sort keys %{$d{$_}}) . ")", sort keys %d
   ), ".\n\n"
;
for (my $p= 1; @p; ++$p) {
   pwrap
      "Phase $p:\nPackages left to be recompiled in order: "
      , join(", ", @p), ".\n"
   ;
   undef $a;
   PKG: foreach $k (@p) {
      foreach (keys %{$d{$k} || {}}) {
         if (!exists $h{$_}) {
            push @f, $k;
            next PKG;
         }
      }
      $a= $h{$k}= 1;
      push @s, $k;
   }
   pwrap
      "Packages successfully compiled: "
      , join(", ", @s, @s ? () : "<none>"), ".\n"
      , "Failed packages: ", join(", ", @f, @f ? () : "<none>"), ".\n\n"
   ;
   last unless $a;
   @p= @f; @s= (); @f=();
}
pwrap
   $a
   ? "Success - all packages have been recompiled!\n"
   : "Giving up - the remaining packages cannot be recompiled!\n"
;

Remove the

Code: Select all

srand 42;

line if you want different results for each repeated run.

Change the assigned values for $NUM_PACKAGES, $MAX_NUM_DEPS and $MAX_TRIES to any values you like.

$NUM_PACKAGES is the total number of simulated packages.

$MAX_NUM_DEPS is the maximum number of dependencies to be generated. The script will try to create that number of dependencies, but will give up creating dependencies if it is unable to find a possible new dependency within $MAX_TRIES tries of random selection.