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

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)

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.