Recursive make Reloaded

It’s been eight years since recursive make was called" harmful," but developers still use it. Here’s how to break the habit.
In 1997, Peter Miller wrote a now famous paper entitled “Recursive make Considered Harmful” (available online at (http://www.pcug.org.au/~millerp/rmch/recu-make-cons-harm.html), which details why recursive use of make is slow, problematic, and unnecessary. But eight years later, it’s still common to see recursive make used in projects. Even GNU make itself has a recursive Makefile!
Yet recursive make is easy to avoid and undo. Let’s look at a short, working example that eliminates recursive make. As you’ll see, you can use the very same model to write new Makefile s that are effective, easy to maintain, and fast. Your improved Makefile s can also leverage parallel compilation for maximum speed.
Recursive make is fundamentally wrong because it breaks the one thing that make is really good at: tracking the dependencies between files. Each call to make generates a separate graph of dependencies between objects and source code. At best, the separate graphs may actually be unrelated, but in many situations may contain the same files.
For make to work best it needs to know all of the dependencies in a build. When some dependencies are missing or perhaps even erroneous, make may work unreliably, or be forced to do more work than necessary, say, updating the same file more than once. Moreover, recursive make is forced to enter subdirectories and create processes even when no work to be done; this effect is particularly bad in an incremental build where you’ve made a small change: make may be forced to slowly traverse a hierarchy of directories calling itself recursively just to discover the one compile that’s necessary.
These problems lead to inaccurate builds, maintenance problems, and long, slow builds. Worse, recursive make cannot take advantage of parallelism offered by distcc or GNU make ‘s –j feature. (For more about parallel compilation, see April 2005’s “Tech Support” column, available online at http://www.linux-mag.com/2005-04/tech_01.html.)

Making a Simple Yet Costly Mistake

Imagine a project that consists of two libraries, lib1 and lib2, and a program called prog. The program consists of a number of C files compiled that are linked with the two static libraries. Such a project might be laid out like this:
Here, the sources for lib1, lib2, and prog are in the subdirectory of the same name and each subdirectory has its own Makefile with the rules to build that component. A top-level Makefile in the src/ directory does the familiar recursive descent:
01 MODULES = lib1 lib2 prog
02 all:
03 for dir in $(MODULES); do \
04 ($(MAKE) –C $$dir); \
05 done
When you type make in the top-level directory, the single all rule runs and calls make in each directory in turn: first lib1, then lib2, and finally prog:
make[1]: Entering directory `lib1’

make[1]: Leaving directory `lib1’
make[1]: Entering directory `lib2’

make[1]: Leaving directory `lib2’
make[1]: Entering directory `prog’

make[1]: Leaving directory `prog’
While the Makefile (seemingly) works, it actually contains a litany of problems:
1.The correct order is clearly lib1, then lib2, and finally prog (or at least make the two libraries before prog). If a third library is added, a user might be tempted just to tack it onto MODULES, as in MODULE=lib1 lib2 prog lib3. But this fails to produce the correct program if lib3 changes, forcing you to run make twice to get the right result. The problem occurs because the dependency between prog and lib1 and lib2 has been expressed implicitly in the MODULES variable; it would be better to use make ‘s dependency mechanism.
2.If a sub- make fails, the overall make process doesn’t halt. For instance, if the make in lib1 exits with an error code, the error is hidden by the for loop, and although make reports an error when it’s finished every directory, it may be very hard to determine where the error actually occurred. It would be better to have one command per target so that make can stop when an error is detected.
3.This Makefile may not be able to take advantage of full parallelism. Since the for loop executes the sub- make s serially, each sub- make has the chance to run as many jobs as the –j option has specified. On multi-processor systems this may result in a slower build than is actually possible because a sub- make may not use all the available job slots and there is no way for make to pass those slots to a subsequent make. This happens every time a sub- make links, as there is typically a single job running doing the link, yet a subsequent make could have already started compiling.
4.Each sub- make requires a process invocation. If there are a large number of sub- make s and little actual work to do (for example, in the case of a small incremental change), most of the build time can be spent starting make. This is an absolute waste of time: GNU make ‘s Makefile parser is very fast, and the best use of make is with a single invocation to minimize overhead.
5.If you try to fix the first problem by unwinding the for loop (as suggested in the GNU make manual section 4.5) you get the following Makefile:
01 MODULES=lib1 lib2 prog
04 all: $(MODULES)
06 $(MODULES): ; @$(MAKE) –C $@
08 prog: lib1 lib2
Here, although line 8 now specifies the explicit dependency between prog and lib1 and lib2, it’s still at a too high a level. This dependency says, “before building any of prog, all of lib1 and lib2 must be built.”
The real dependency is between the program that prog generates and the libraries created by lib1 and lib2. But because there is no way to express that dependency using recursive make and although this Makefile can make better use of parallelism and will stop if any sub- make fails, it cannot exploit –j to the fullest and requires a costly traversal of every subdirectory to determine what work must be done.

Transformation Station

The most robust and fastest solution is a single make job with complete dependency information. Many Makefile authors shy away from this solution because of the belief that it’s too complex. But it is not.
Listing One shows a transformed Makefile.
LISTING ONE: A much-improved Makefile that is fast and dependable
01.PHONY: all
04_OUTTOP ?= .
05_OUTTOP := $(_OUTTOP)/output
07ifdef DEBUG
08 _OUTTOP := $(_OUTTOP)/debug
010 _OUTTOP := $(_OUTTOP)/nondebug
013.PHONY: clean
014clean:: ; @rm –rf $(_OUTTOP)
017MODULES=lib1 lib2 prog
019include $(addsuffix /Makefile,$(MODULES))
021$(prog_BINARY) : $(lib1_BINARY) $(lib2_BINARY)
Listing One might look like a lot of complex code, but it’s doing a number of things that improve the build process in addition to removing recursion:
1.The output (the objects and executable binary files) are all placed in the directory defined by _OUTTOP (which defaults to the current directory, as set in line 4). There’s an option to specify debug or non-debug code by setting DEBUG on the make command-line (lines 7 to 11).
2.When making non-debug code, all the output is placed in ./output/nondebug; when making debug code, the output is placed under ./output/debug. This eliminates a common make problem: since make doesn’t track changes in the flags used to build files, it’s possible when building debug and non-debug code which use the same object files to end up with a mixture of some debug and some non-debug code. In fact, it’s common when changing between modes to have to do a complete, clean build just to be sure. By separating the output, make is able to use its normal file dependency tracking based on timestamps to determine what needs to be rebuilt regardless of whether you are making debug or non-debug.
3.This technique of encoding options in the output path name can be extended further by adding other parts to _OUTTOP. For example, you could distinguish between versions that have profiling enabled or disabled, or even versions for different target platforms.
4.Because all the output resides under _OUTTOP, it’s possible to define a simple clean target that cleans up all of the object files: all clean has to do is rm –rf the directory named by _OUTTOP (see line 14). And since _OUTTOP changes depending on the debug or non-debug mode of the build, clean only cleans up the relevant object files; a make clean DEBUG=yes only cleans up the debug objects, leaving the non-debug objects intact.
5.The all target, which previously used a shell for loop to do the recursion, has been replaced by a single include statement (line 19). The include includes the file Makefile from each of the modules (which is still specified in MODULES). The all rule itself has been specified as a double-colon rule (::), which allows included Makefile s to redefine it later. That technique allows each included Makefile to set up the rules necessary to build its portion of the program.
6.Finally, the new Makefile can specify a very fine-grained dependency that states that the binary file for prog depends upon the binary files for lib1 and lib2 (see line 21). That is, make can’t link prog until it’s made the libraries. This fine-grained dependency allows make to build all the .o files in all the modules simultaneously if running a parallel make. The parallelism only needs to be limited right at the end to ensure that the libraries are linked together before the final executable.

Uniformity is Good

Additionally, each Makefile in a module subdirectory has a simple, regular form. Here’s the Makefile for the lib1 directory, which specifies that the module creates a library called lib1prog.a from sources lib1foo.c and lib1bar.c:
01 include _header.mak
03 SRCS = lib1foo.c lib1bar.c
04 BINARY = lib1prog.a
06 include _footer.mak
All of the work is done by the included Makefile s _header.mak and _footer.mak. These two Makefile s define the rules for building the object files for each module. Listing Two shows _header.mak.
LISTING TWO: The Makefile header
01_MAKEFILES := $(filter-out _header.mak _footer.mak,$(MAKEFILE_LIST))
02_MODULE := $(patsubst %/,%,$(dir $(word $(words $(_MAKEFILES)),$(_MAKEFILES))))
05$($(_MODULE)_OUTPUT)/.f: ; @if !([ –e $@ ]); then ( mkdir –p $(patsubst %/.f,%,$@) ; touch $@ ); fi
The variable _MAKEFILES is the list of all Makefile s included in the build up to this point after filtering out _header.mak and _footer.mak. The last element is the Makefile that included _header.mak, that is, the file Makefile in a module subdirectory. In the file lib1/Makefile, the last element of _MAKEFILES is lib1/Makefile.
_MODULE is the name of the module being processed and is obtained by finding the last element of _MAKEFILES (for example, lib1/Makefile) and then stripping the /Makefile part to be left with lib1. _MODULE is used throughout the rest of processing the module as the name of the module being handled.
For example, the variable $(_MODULE)_OUTPUT is defined to be the location under _OUTTOP to place the objects created for the module. The name $(_MODULE)_OUTPUT is a computed name, since its name changes depending on the module being processed. While processing the lib1 module the variable name is lib1_OUTPUT and will have the value ./output/lib1. So, all of lib1’ s objects go in ./output/lib1.
Finally, _header.mak defines a rule that ensures that $(_MODULE)_OUTPUT exists by performing a mkdir with the –p option to make the complete path specified by $(_MODULE)_OUTPUT (see line 8). This rule is used in _footer.mak to ensure that the output directory exists before doing any compiles or links.
_footer.mak is more complex and is where all the real work is done. It’s shown in Listing Three.
LISTING THREE: The Makefile footer
01$(_MODULE)_OBJS := $(addsuffix .o,$(addprefix $($(_MODULE)_OUTPUT)/,$(basename $(SRCS))))
04$($(_MODULE)_OUTPUT)/%.o: $(_MODULE)/%.c $($(_MODULE)_OUTPUT)/.f @$(COMPILE.c) –o $@ $<
05$($(_MODULE)_OUTPUT)/%.a: $($(_MODULE)_OBJS)
06 $($(_MODULE)_OUTPUT)/.f
07 @$(AR) r $@ $(filter %.o,$^)
08 @ranlib $@
09$($(_MODULE)_OUTPUT)/%: $($(_MODULE)_OBJS) $($(_MODULE)_OUTPUT)/.f
010 @$(LINK.cpp) $(filter %.a %.o,$^) –o$@
012all:: $($(_MODULE)_BINARY)
Line 13 of _footer.mak augments the all rule, saying that to build all, make must build the binary for this module, which is called $(_MODULE)_BINARY.
The binary filename is stored in the variable $(_MODULE)_BINARY on line 3 and consists of the output directory for this module (from $(_MODULE)_OUTPUT)) followed by the name of the binary stored in BINARY. BINARY is defined by the Makefile specific to each module: in lib1, BINARY is lib1prog.a (see line 4 of the lib1 Makefile above).
The rest of _footer.mak consists of rules that build .o,.a, and executable files in the appropriate output directory. Each depends on the $(_MODULE)_OUTPUT directory, which is created by the rule defined in _header.mak, if it doesn’t exist.
The rules for .a (line 7) and executables (line 10) also depend on the variable $(_MODULE)_OBJS. $(_MODULE)_OBJS is a list consisting of all the object files for the module and is created on line 1 by transforming the list of source files (stored in variable SRCS at line 3 of the Makefile for lib1) into object files. It works by stripping off the extension (in this case, .c) and adding .o, and then adding the output directory from $(_MODULE)_OUTPUT. For example, in lib1, the object file for lib1foo.c is ./output/nondebug/lib1/lib1foo.o for a non-debug build.

Non-Recursive make in Action

To try out this new structure, run GNU make with the –n option, which prints out the commands that it would run, but does no other work. Listing Four shows the output for a clean build with no preexisting objects.
LISTING FOUR: The processing performed by the non-recursive make
01if !([ –e output/nondebug/lib1/.f ]); then ( mkdir –p output/nondebug/lib1 ; touch output/nondebug/lib1/.f ); fi
02cc –c –o output/nondebug/lib1/lib1foo.o lib1/lib1foo.c
03cc –c –o output/nondebug/lib1/lib1bar.o lib1/lib1bar.c
04ar r output/nondebug/lib1/lib1prog.a output/nondebug/lib1/lib1foo.o output/nondebug/lib1/lib1bar.o output/nondebug/lib1
05ranlib output/nondebug/lib1/lib1prog.a
06if !([ –e output/nondebug/lib2/.f ]); then ( mkdir –p output/nondebug/lib2 ; tou ch output/nondebug/lib2/.f ); fi
07cc –c –o output/nondebug/lib2/lib2foo.o lib2/lib2foo.c
08cc –c –o output/nondebug/lib2/lib2bar.o lib2/lib2bar.c
09ar r output/nondebug/lib2/lib2prog.a output/nondebug/lib2/lib2foo.o output/nondebug/lib2/lib2bar.o output/nondebug/lib2
010ranlib output/nondebug/lib2/lib2prog.a
011if !([ –e output/nondebug/prog/.f ]); then ( mkdir –p output/nondebug/prog ; touch output/nondebug/prog/.f ); fi
012cc –c –o output/nondebug/prog/prog.o prog/prog.c
013cc –c –o output/nondebug/prog/progstuff.o prog/progstuff.c
014g++ output/nondebug/prog/prog.o output/nondebug/prog/progstuff.o output/nondebug/prog output/nondebug/lib1/lib1prog.a output/nondebug/lib2/lib2prog.a –o’output/nondebug/prog/prog’
Lines 1 through 5 are the creation of lib1prog.a after creating the necessary .o files; lines 6 through 10 are the similar creation of lib2prog.a. Lines 11 through 14 are the creation of the .o files for prog followed by the final link step. Lines 1, 6, and 11 create the relevant output directories.
Listing Five shows what happens if just the lib1/lib1foo.c file is updated. Because the make is no longer recursive and has full knowledge of all the dependencies, it only has to rebuild lib1foo.o, recreate the library lib1prog.a, and relink prog. This starts instantly because make no longer has to recurse into directories where no work is necessary.
LISTING FIVE: The non-recursive Makefile does minimal recompilation
01cc –c –o output/nondebug/lib1/lib1foo.o lib1/lib1foo.c
02ar r output/nondebug/lib1/lib1prog.a output/nondebug/lib1/lib1foo.o output/nondebug/lib1/lib1bar.o
03ranlib output/nondebug/lib1/lib1prog.a
04g++ output/nondebug/prog/prog.o output/nondebug/prog/progstuff.o output/nondebug/lib1/lib1prog.a output/nondebug/lib2/lib2prog.a –o output/nondebug/prog/prog

Have No Fear!

Don’t be afraid of non-recursive make anymore and take back your Makefile! The skeleton Makefiles provided in this article are a good starting point for a large build system.
If this article has peaked your interest in some hard-core Makefile creation, check out O’Reilly’s new Managing Projects with GNU Make, which has good sections on recursive and non-recursive make, and many other GNU Make topics.

John Graham-Cumming is founder and Chief Scientist at Electric Cloud, Inc. (http://www.electric-cloud.com), a Silicon Valley start-up that is reducing software build times for its customers. He is also the creator of POPFile (http://getpopfile.org/).

Comments are closed.