bugmake - Bugs: bug #13529, Incorrect circular dependancy

 
 

bug #13529: Incorrect circular dependancy

Submitter:  None
Submitted:  Thu 23 Jun 2005 06:12:14 PM UTC
Votes: 20
 
Severity:  3 - Normal Item Group:  Bug
Status:  Fixed Privacy:  Public
Assigned to:  psmith Open/Closed:  Closed
Component Version:  3.81 Operating System:  Any
Fixed Release:  3.82 Triage Status:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Sun 14 Jun 2009 05:58:39 AM UTC, comment #5: 

Fixed using Reid's solution: the investigation is good stuff!  Thanks.

Paul D. Smith <psmith>
Group administrator
Mon 22 May 2006 03:27:34 PM UTC, comment #4: 

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

Reid Madsen <srmadsen>
Tue 21 Feb 2006 01:29:03 PM UTC, comment #3: 

OK, I tracked down my problem and reduced it to a small testcase:

The Makefile looks like this:
vpath %.te test/
.SECONDARY:
default: test/a test/b
test/a: fail.te
test/b : fail.te
test/fail.te:

test/ exists but is empty. When I run make with this makefile it complains: "make: Circular test/b <- fail.te dependency dropped."
This seems like a bad interaction between vpath and .SECONDARY, if I remove one of the two lines the problem goes away.

I don't know if this is fixable, but at least a nicer error message would be very helpful.

Thomas Bleher <thomasbleher>
Tue 21 Feb 2006 02:45:29 AM UTC, comment #2: 

I'm having a similar problem (make from CVS 2006-02-21, Ubuntu Dapper):

Testcase: http://www.cip.ifi.lmu.de/~bleher/refpolicy-segfault.tar.gz (same as in bug #15818).

When make is called on this tree with "make -C build-tree/refpolicy NAME=refpolicy-strict TYPE=strict-mcs DISTRO=debian DIRECT_INITRC=y MONOLITHIC=n clean all"
it complains:
"make: Circular tmp/all_te_files.conf <- corenetwork.te dependency dropped."
(sixth line of the output). The compilation continues but produces incorrect results.
The Makefile works with earlier versions of make (unfortunately I can't say which version exactly at the moment)

Thomas Bleher <thomasbleher>
Sun 22 Jan 2006 06:35:49 AM UTC, comment #1: 

More info:

  The dependency is redundant (%.3 already depends on dep.x indirectly through %.2).  Could gmake be confused by that?

  The *.3 files are ".INTERMEDIATE".  When they are created (temporarily), we see that false error message.  When those files already exist, we don't see that message.

"funny=1" gives those files as explicit prerequisites; then, they aren't seen as ".INTERMEDIATE".

Anonymous
Thu 23 Jun 2005 06:12:14 PM UTC, original submission:  

I am having a problem with a makefile which appears to be a bug with make. Unfortunately, I can't compile make from CVS because of problems with automake on Fedora Core 4. I have tried this with the 3.81beta2 release though.

I have attached the makefile in question. To run the test, first make setup. This will create a list of source files and a dependency in a subdirectory. Next make the level4 target. Make complain about circular dependencies on dep.x. I don't see how this dependency is circular. On make 3.80, if you define funny to be 1 (make -f foo.mk level4 funny=1) the problem goes away. Not so with 3.81beta2. Also, if you change the target for %.3 or %.4 to depend on depdir/dep.x rather than picking it up from the vpath then everything works.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #10030:  remake.c added by srmadsen (47KiB - application/octet-stream)
file #3117:  foo.mk added by None (346B - application/octet-stream - Makefile demonstrating the bug)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by psmith (Posted a comment)
  •  

    There are 20 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2010-07-28 psmith Fixed Release4.0 3.82
    2009-06-14 psmith StatusNone Fixed
        Assigned toNone psmith
        Open/ClosedOpen Closed
        Component Version4.0 3.81
        Fixed ReleaseNone 4.0
    2006-05-22 srmadsen Carbon-Copy- Added srmadsen
    2006-05-22 srmadsen Attached File- Added remake.c, #10030
    2005-06-23 None Attached File- Added foo.mk, #2625

    Back to the top

    Powered by Savane 3.13-ee12.
    Corresponding source code