[bug #13529] Incorrect circular dependancy

[Reid Madsen]

Follow-up Comment #4, bug #13529 (project make):

I'm experiencing similar problems with V3.81.  The symptoms are these: 

1. make clean 
2. make -- make rebuilds everything, with no warnings about circular
dependencies. 
3. make -- nothing to do, but I get hundreds of false warnings about circular
dependencies. 

I decided to debug the issue.  There is a bug in the following two functions
of remake.c: 

+ update_file_1 
+ check_deps 

At the top of remake.c, there are three macros: 

+ start_updating(file) 
+ end_updating(file) 
+ is_updating(file) 

These macros set, clear, and test the 'updating' flag in the 'struct file*'
object passed.  

The functions recursively traverse the dependency tree for a given target. 
These functions set the 'updating' flag on the 'struct file*' argument
shortly after entry, and clear the 'updating' flag before exiting.  A
circular dependency is detected when 'is_updating(file)' is true on entry to
either of these functions. In a true circular dependency the traversal would
loop back onto itself -- eventually -- and the 'updating' flag would be set.

The assumption in the above functions is that they are setting and clearing
the 'updating' flag on the same 'struct file*' object.  Unfortunately that
assumption is false.  In the presence of 'vpath' definitions, they often set
the 'updating' flag on one 'struct file*' object, but clear it on a different
one.  These leaves 'struct file*' objects floating around with an 'updating'
flag that is set, but never cleared.  Later when these functions are
traversing the dependencies of the next target, they run across a 'struct
file*' object with the 'updating' flag set, and incorrectly report a circular
dependency error.

To validate this I modified the above macros to dump information about which
object they were working with.  This resulted in the following:

01 ....BEG update: (1) ual.a (0x905a1c8) 
02 .....BEG update: (1) ual.a (0x905a1c8) 
03 ......BEG update: (1) ual.a(File.o) (0x9059728) 
04 .......BEG update: (1) ual.a(File.o) (0x9059728) 
05 ........BEG update: (1) File.o (0x9056c40) 
06 .........BEG update: (1) File.cpp (0x905a308) 
07 ..........BEG update: (1) File.cpp (0x905a308) 
08 ..........END update: (0) File.cpp (0x905a308) 
09 .........END update: (0) ../File.cpp (0x905a308) 
10 .........BEG update: (1) .dfiles/.mkdir (0x905b040) 
11 ..........BEG update: (1) .dfiles/.mkdir (0x905b040) 
12 ..........END update: (0) .dfiles/.mkdir (0x905b040) 
13 .........END update: (0) .dfiles/.mkdir (0x905b040) 
14 .........BEG update: (1) ../File.cpp (0x905a308) 
15 .........END update: (0) ../File.cpp (0x905a308) 
16 .........BEG update: (1) ual/File.h (0x9049448) 
17 ..........BEG update: (1) ual/File.h (0x9049448) 
18 ...........BEG update: (1) File.h (0x905b120) 
19 ............BEG update: (1) File.h (0x905b120) 
20 ............END update: (0) File.h (0x905b120) 
21 ...........END update: (0) ../File.h (0x905b120) 
22 ...........BEG update: (1) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
23 ............BEG update: (1) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
24 ............END update: (0) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
25 ...........END update: (0) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
26 ..........END update: (0) ../../x86-linux-fedora-4/include/ual/File.h
(0x9058ef0) 
27 .........END update: (0) ../../x86-linux-fedora-4/include/ual/File.h
(0x9058ef0) 
28 .........BEG update: (1) ual/FileNotFoundException.h (0x905f3f0) 
29 ..........BEG update: (1) ual/FileNotFoundException.h (0x905f3f0) 
30 ...........BEG update: (1) FileNotFoundException.h (0x905b280) 
31 ............BEG update: (1) FileNotFoundException.h (0x905b280) 
32 ............END update: (0) FileNotFoundException.h (0x905b280) 
33 ...........END update: (0) ../FileNotFoundException.h (0x905b280) 
34 ...........BEG update: (1) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
35 ...........END update: (0) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
36 ..........END update: (0)
../../x86-linux-fedora-4/include/ual/FileNotFoundException.h (0x9058f98) 
37 .........END update: (0)
../../x86-linux-fedora-4/include/ual/FileNotFoundException.h (0x9058f98) 
38 ........END update: (0) File.o (0x9056c40) 
39 .......END update: (0) ual.a(File.o) (0x9059728) 
40 ......END update: (0) ual.a(File.o) (0x9059728) 
41 ......BEG update: (1) ual.a(FileNotFoundException.o) (0x9059780) 
42 .......BEG update: (1) ual.a(FileNotFoundException.o) (0x9059780) 
43 ........BEG update: (1) FileNotFoundException.o (0x9056da0) 
44 .........BEG update: (1) FileNotFoundException.cpp (0x905ec00) 
45 ..........BEG update: (1) FileNotFoundException.cpp (0x905ec00) 
46 ..........END update: (0) FileNotFoundException.cpp (0x905ec00) 
47 .........END update: (0) ../FileNotFoundException.cpp (0x905ec00) 
48 .........BEG update: (1) .dfiles/.mkdir (0x905b040) 
49 .........END update: (0) .dfiles/.mkdir (0x905b040) 
50 .........BEG update: (1) ../FileNotFoundException.cpp (0x905ec00) 
51 .........END update: (0) ../FileNotFoundException.cpp (0x905ec00) 
52 make[2]: Circular FileNotFoundException.o <- ual/File.h dependency
dropped. 
53 make[2]: Circular FileNotFoundException.o <- ual/FileNotFoundException.h
dependency dropped. 
54 ........END update: (0) FileNotFoundException.o (0x9056da0) 
55 .......END update: (0) ual.a(FileNotFoundException.o) (0x9059780) 
56 ......END update: (0) ual.a(FileNotFoundException.o) (0x9059780) 

In the above, I'm building a library (ual.a), using the archive member rules.
 Of particular interest in the above are the following lines:

16 .........BEG update: (1) ual/File.h (0x9049448) 
17 ..........BEG update: (1) ual/File.h (0x9049448) 
18 ...........BEG update: (1) File.h (0x905b120) 
19 ............BEG update: (1) File.h (0x905b120) 
20 ............END update: (0) File.h (0x905b120) 
21 ...........END update: (0) ../File.h (0x905b120) 
22 ...........BEG update: (1) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
23 ............BEG update: (1) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
24 ............END update: (0) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
25 ...........END update: (0) ../../x86-linux-fedora-4/include/ual/.mkdir
(0x9049748) 
26 ..........END update: (0) ../../x86-linux-fedora-4/include/ual/File.h
(0x9058ef0) 
27 .........END update: (0) ../../x86-linux-fedora-4/include/ual/File.h
(0x9058ef0) 

The above is produced by the 'start_updating' and 'finish_updating' macros. 
The level, file name, and object address are printed.  The 'updating' flag
value is also printed.  Each matching BEG/END represents the enter/exit from
one of the above functions.

Note that at line 16 make is setting the 'updating' flag on 'ual/File.h'. 
Then note that at line 27 make is clearing the 'updating' flag on a different
object '../../x86-linux-fedora-4/include/ual/File.h'.  This file was found via
a 'vpath %.h ../../x86-linux-fedora-4/include' statement in the makefile.  The
key point here is that the 'updating' flag was set on one object, but cleared
on a different object -- which leaves one object floating around with the
'updating' flag still set.

Then later at lines 41-56, we find the following: 

41 ......BEG update: (1) ual.a(FileNotFoundException.o) (0x9059780) 
42 .......BEG update: (1) ual.a(FileNotFoundException.o) (0x9059780) 
43 ........BEG update: (1) FileNotFoundException.o (0x9056da0) 
44 .........BEG update: (1) FileNotFoundException.cpp (0x905ec00) 
45 ..........BEG update: (1) FileNotFoundException.cpp (0x905ec00) 
46 ..........END update: (0) FileNotFoundException.cpp (0x905ec00) 
47 .........END update: (0) ../FileNotFoundException.cpp (0x905ec00) 
48 .........BEG update: (1) .dfiles/.mkdir (0x905b040) 
49 .........END update: (0) .dfiles/.mkdir (0x905b040) 
50 .........BEG update: (1) ../FileNotFoundException.cpp (0x905ec00) 
51 .........END update: (0) ../FileNotFoundException.cpp (0x905ec00) 
52 make[2]: Circular FileNotFoundException.o <- ual/File.h dependency
dropped. 
53 make[2]: Circular FileNotFoundException.o <- ual/FileNotFoundException.h
dependency dropped. 
54 ........END update: (0) FileNotFoundException.o (0x9056da0) 
55 .......END update: (0) ual.a(FileNotFoundException.o) (0x9059780) 
56 ......END update: (0) ual.a(FileNotFoundException.o) (0x9059780) 

In this case a different target is being updated.  It also depends on
'ual/File.h'.  Once the traversal hits u'al/File.h', a false circular
dependency is reported because the 'updating' flag on 'ual/File.h' was never
cleared.  Ditto for 'ual/FileNotFoundException.h' (See lines 28-47).  Both of
these are false warnings -- there is no circular dependency.

It appears (though it is completely non-obvious) that the 'struct file*'
argument is replaced by a new 'struct file*' argument for the vpath-resolved
object.  The 'updating' flag is propagated to the new 'struct file*' object
from the original.  Thus at the end of both of the above functions the
'updating' flag needs to be cleared on both the original and the new
'vpath-resolved' object.  Failure to do both results in false circular
dependency warnings.

The fix for this bug is to save the original 'struct file* file' argument
into a variable named 'struct file* orig_file' and then invoke the
'finish_updating(file)' macro on both the 'orig_file' and 'file' objects. 
 
I have attached a copy of remake.c that contains the fix for this bug.  Just
look for the TEKTRONIX_CIRCULAR_FIX conditionals.  This was based on the
V3.81 version of remake.c.  Just set the above conditional and compile.  This
file also contains a fix for #14927, which is activated by setting the
TEKTRONIX_AR_FIX to 1.  These fixes are mutually exclusive.

I'd like to know if this fix resolves the problems others have reported. 
Post your results as follow-ups to this bug.

Thanks,
Reid Madsen
Tektronix Inc.
Richardson, Texas

    _______________________________________________________

Additional Item Attachment:

File name: remake.c                       Size:46 KB

<http://savannah.gnu.org/bugs/download.php?file_id=10030>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?func=detailitem&item_id=13529>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/