Debugging broken builds with SparkBuild Insight: Implicit Dependency Mistakes

In the previous articles: Debugging broken builds with SparkBuild Insight: Malformed Makefiles and Debugging broken builds with SparkBuild Insight: Simple Problems we covered some basic broken-build scenarios: source code errors and broken makefiles. This installment will look at another common cause of failed builds - implicit dependencies - and how to identify (and fix) this type of problem with SparkBuild Insight.

What do we mean by an implicit dependency? To understand that, you'll need to know another term - an explicit dependency is when the makefile identifies a prerequisite for a target, like this:
foo.exe : foo.o

These dependencies are what make make work. Ideally, a makefile should contain an explicit dependency like this for every file used by a rule. So, if foo.exe depends on foo.o and util.lib, there ought to be something like:
foo.exe: foo.o util.lib

in the makefile.

In contrast, an implicit dependency is anything which a rule body reads but is not listed as a prerequisite. Here's an example:

foo.exe:        gcc -o foo.exe foo.o

Implicit dependencies are tricky since there's no way to specify them (otherwise they'd be explicit dependencies!) However, if ordering could be predicted and controlled, an explicit dependency could be ommitted in favor of a dependency on that implied ordering - effectively getting correct behavior without specifying it. One way to satisfy actual dependencies through an implied ordering is to exploit the the way make evaluates prerequisites (strictly left-to-right). If the makefile indicates
all: foo.o util.lib foo.exe

then make all will provide the following build order:

foo.o
util.lib
foo.exe
all

Since we can predict that make will evaluate the targets in this order, we can rely on this ordering to satisfy the implicit dependency between foo.exe and foo.o. Another way to produce this effect is to use a list and iterator structure to explicitly call submakes from within a rule body; in fact, any mechanism which invokes submakes - and therefore controls rule execution order - can do this.

There are some good reasons to avoid implicit dependencies - they'll break your incremental builds and make parallelization difficult - but they are also extremely common, due to the effort required to discover and maintain complete file-level dependencies, and the way that make will suddenly 'just work' when the ordering is accidentally right. Builds which break because an implicit dependency was not respected are just as common, and can be really hard to diagnose.

Case Study: Breaking Implicit Dependencies
(Grab this annotation file if you'd like to look at this example in your own SparkBuild Insight: error3.anno.xml.tar.gz)

For this case study, we'll look at another MySQL build. Here's the tail of our build log:

g++ -DMYSQL_SERVER -DDEFAULT_MYSQL_HOME="\"/usr/local\"" -DDATADIR="\"/usr/local
/var\"" -DSHAREDIR="\"/usr/local/share/mysql\"" -DHAVE_CONFIG_H -I. -I. -I.. -I.
./zlib -I../innobase/include -I../include -I../include -I../regex -I. -O3 -D
DBUG_OFF -fno-implicit-templates -fno-exceptions -fno-rtti -c -I../zlib -I../
innobase/include -I../include -I../include -I../regex -I. -DTZINFO2SQL mysql_tz
info_to_sql.cc
make[4]: *** No rule to make target `../myisam/libmyisam.a', needed by `mysql_tz
info_to_sql.exe'. Stop.
make[4]: Leaving directory `c:/example/mysql-4.1.22/sql'
make[3]: *** [all-recursive] Error 1
make[3]: Leaving directory `c:/example/mysql-4.1.22/sql'
make[2]: *** [all] Error 2
make[2]: Leaving directory `c:/example/mysql-4.1.22/sql'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `c:/example/mysql-4.1.22'
make: *** [all] Error 2


What a mess! No rule to make target can be a frustrating error, because there are generally no references in a build log to that file, and (of course) there won't be an obvious rule for it in the makefile. Let's open the log in SparkBuild Insight, and take a look at the failed job list:

If you've read the previous two articles in this series, this structure should look pretty familiar. We've got a failed target at the bottom of the list, and a succession of all and all-recursive jobs. Double-clicking on mysql_tzinfo_to_sql.exe will bring up the complaining job:

These 'No rule to make' errors occur before any rule commands are executed, because they indicate an inability to satisfy a prerequisite. (The error text being displayed isn't coming from a tool or command, it comes directly from emake.)

Looking at the job path for this rule identifies this build as a recursive one:

The recursive structure of this build has a makefile for each component directory, and the rules for building each object in the component are in that makefile.

Take a look at the 'Working dir' field:

We're in the sql component directory, and the file we're missing (and don't know how to make) is in the myisam directory. This tells us to look for the rule to make ../myisam/libmyisam.a should be in myisam/Makefile:

(download the myisam component Makefile here)

Clearly there's a rule to make this file, so why are we experiencing a failure? gnu make is a narrow-minded piece of software. It can only work with the rules it has been given, and it doesn't know about rules other make instances have read - so the makefile in the myisam directory has a rule to build ../myisam/libmyisam.a - but that makefile isn't loaded by the submake in the sql directory, and the sql submake is the one complaining about 'No rule to make'.

(Incidentally, this is one of the problems which SparkBuild's subbuild feature solves - the subbuild database gives emake a map to follow when looking for the rule to make a target. In this instance, a build invoked from the sql directory with subbuilds turned on would be able to build ../myisam/libmyisam.a automatically.)

Since the sql submake isn't capable of building libmyisam.a, we need to figure out whether the myisam component was built. This can be done in SparkBuild Insight, starting in the Job Path pane of the mysql_tzinfo_to_sql.exe job. We're looking for a job which is run from the top-level source directory, and which invokes submakes in the individual component directories (like the sql submake.) By looking at the 'Working dir' field for each make instance, we can identify likely jobs pretty easily.

The all-recursive target appears to be what we're looking for (it's the rule job directly after the relevant make job):

Clicking on the 'Submakes' tab of the all-recursive job exposes a valuable piece of the puzzle:

The list of submakes which are invoked by this target are a smoking gun (or the lack of one). The include, Docs, zlib, and sql submakes are executed, but nowhere does the myisam component show up. This explains why make couldn't get ../myisam/libmyisam.a to build mysql_tzinfo_to_sql.exe. So, why wasn't myisam built?

To dig further, we're going to need the makefile which contains the all-recursive target.

(Download this Makefile here.)

Here is the relevant part of the rule that definies the all-recursive behavior:

This snippet iterates over a list of directories, and executes a submake in each one. Does this technique make you suspicious? It should - this is one of the ways of managing implicit dependencies, as described earlier.

The right fix for problems with implicit dependencies is to express the dependency explicitly. In this top-level makefile the rule information about how to produce mysql_tzinfo_to_sql.exe and libmyisam.a isn't available - so we'll have to generalize:
sql : myisam

This explicit dependency will force the entire myisam target to be built before the sql target - which is fine for serial make, but will slow down a parallel one. But, when we make this change to the makefile, the build still fails!

Here's a great example of why mechanisms for enforcing an explicit ordering can be dangerous: by using an iterator within a rule to invoke all the component submakes, we've robbed make of its ability to correctly order the targets. So our sql : myisam rule has no effect - the all-recursive target doesn't list any prerequisites, and at this make level there's no rule for myisam anyways.

To make sure that myisam/libmyisam.a is available for mysql_tzinfo_to_sql.exe it's therefore necessary to make sure that the list of directories for the iterator is properly ordered. Since our build failed because targets produced for myisam weren't available at the time sql was built, we now need to check the directory list ordering.

Since the list we're iterating through is the $(SUBDIRS) macro, we can seek through the makefile to find it:

SUBDIRS = . include Docs zlib sql libmysql\               cmd-line-utils sql-common \               pstack \               strings [...] myisam myisammrg [...]

Here's the source of our problem. The sql target occurs earlier than the myisam in the list of directories which will be recursed through. But wait! Don't just move myisam earlier in the SUBDIRS definition - the sql target may have other dependencies. Going back to the makefile in the sql directory will help us make an informed fix:
mysql_tzinfo_to_sql$(EXEEXT): $(mysql_tzinfo_to_sql_OBJECTS) $(mysql_tzinfo_to_sql_DEPENDENCIES)

(download the sql Makefile here).

A little investigation into the makefile should let us know where we can move the sql component - it will contain an explicit list of the files required for mysql_tzinfo_to_sql.exe - and the paths to those files should indicate components which should be built first.

For brevity's sake, we'll leave out all the intermediate macros: mysql_tzinfo_to_sql.exe's prerequisite list is defined by the am__DEPENDENCIES_1 macro:

The repaired SUBDIRS declaration looks like this:

SUBDIRS = . include Docs zlib \               cmd-line-utils sql-common \               pstack \               strings [...] myisam myisammrg [...] sql [...]

Fixing broken builds which fail due to unsatisfied implicit dependencies is a tricky business, since virtually everything relevant to the problem is missing: the violated dependency (which isn't written down), logs of the production of the missing file (which was never built), a specific compiler error or tool fault (which never occur, since the maligned rule is never run). SparkBuild Insight can get you pretty far along the path - making it easy to triage what type of problem you're troubleshooting, and providing the essential clues about what is broken.

In an ideal build system, implicit dependencies would never occur. For those of us who have real-world systems to contend with, SparkBuild Insight makes identifying problems with implicit dependencies considerably easier.