race condition in multi-job dependency checking

[Chris Frey]

Hi,

I've attached a test case Makefile, in an attempt to illustrate the
following behaviour.

For example:

both: lib1-build lib2-build

If both lib1-build and lib2-build take a substantial amount of time,
then there is the possibility that lib2-build's dependencies will
be satisfied on the first pass, while lib1-build's are satisfied
in conjunction with lib2-build's own job, and lib2-build's run will
continue, and make will miss an opportunity to run lib1-build in parallel.

To test this with the attached Makefile, run the following in a
clean directory:

        mkdir Nothing
        make -j16 -d

In my test case (the attached Log file) you'll notice that 'sleep 15s'
happens first (the lib2-build case), while 'sleep 5s' happens later
(the lib1-build case) and 'sleep 5s' waits until sleep 15s is finished,
even though this is not required.

Here's the abbreviated log to show what's happening:

Considering target file `all'.
 File `all' does not exist.
 Looking for an implicit rule for `all'.
 Trying pattern rule with stem `all'.
 Considering target file `both'.
  File `both' does not exist.
  Considering target file `lib1-build'.
   File `lib1-build' does not exist.
   Considering target file `lib2-dir'.
    File `lib2-dir' does not exist.
    Finished prerequisites of target file `lib2-dir'.
   Must remake target `lib2-dir'.
   Successfully remade target file `lib2-dir'.
   Considering target file `lib1-dir'.
    File `lib1-dir' does not exist.
    Finished prerequisites of target file `lib1-dir'.
   Must remake target `lib1-dir'.
Need a job token; we don't have children
mkdir lib1-dir
Putting child 0x0807e930 (lib1-dir) PID 12258 on the chain.
   Commands of `lib1-dir' are being run.
   Considering target file `Nothing'.
    Finished prerequisites of target file `Nothing'.
   No need to remake target `Nothing'.
   Finished prerequisites of target file `lib1-build'.
  The prerequisites of `lib1-build' are being made.
  Considering target file `lib2-build'.
   File `lib2-build' does not exist.
   Pruning file `lib2-dir'.
   Finished prerequisites of target file `lib2-build'.
  Must remake target `lib2-build'.
Live child 0x0807e930 (lib1-dir) PID 12258 
Reaping winning child 0x0807e930 PID 12258 
Removing child 0x0807e930 PID 12258 from chain.
Need a job token; we don't have children
sleep 15s
Putting child 0x0807e930 (lib2-build) PID 12259 on the chain.
  Commands of `lib2-build' are being run.
  Finished prerequisites of target file `both'.
 The prerequisites of `both' are being made.
 Finished prerequisites of target file `all'.
The prerequisites of `all' are being made.


At this point all dependencies for lib1-build and lib2-build are
complete, but they are not running in parallel.  A new pass would
discover this, but make waits for the lib2-build dependency to finish first.


Live child 0x0807e930 (lib2-build) PID 12259 
Reaping winning child 0x0807e930 PID 12259 
touch lib2-build
Live child 0x0807e930 (lib2-build) PID 12260 
Reaping winning child 0x0807e930 PID 12260 
Removing child 0x0807e930 PID 12260 from chain.
Considering target file `all'.
 File `all' does not exist.
 Considering target file `both'.
  File `both' does not exist.
  Considering target file `lib1-build'.
   File `lib1-build' does not exist.
   Considering target file `lib2-dir'.
   File `lib2-dir' was considered already.
   Considering target file `lib1-dir'.
   File `lib1-dir' was considered already.
   Considering target file `Nothing'.
   File `Nothing' was considered already.
   Finished prerequisites of target file `lib1-build'.
  Must remake target `lib1-build'.
Need a job token; we don't have children
sleep 5s
Putting child 0x0807eb20 (lib1-build) PID 12261 on the chain.
  Commands of `lib1-build' are being run.
  Considering target file `a'.


I had to really work to get this small test case to behave this way, and
without the -d option, make is fast enough to behave differently.
In my work makefile, this happens easily, since the file is so big.

I suspect the problem is that make doesn't perform a new pass after every
finished job.  It looks like the first job finished at the same time the
second job started (sleep 15s) and this first job was not seen as a trigger
to start a new pass.

For long-running jobs, this can be a significant bottleneck.

Thanks,
- Chris

Log.bz2
Description: BZip2 compressed data

Makefile
Description: Text document