NetHack 4 homepage | NetHack 4 blog | ATOM feed
Tags: aimake internals c | Wed Nov 5 11:10:26 UTC 2014 | Written by Alex Smith
C is a compiled language, and as such, C programs need to be converted to executables in order to use them. Typically, programmers do this with some sort of build system, rather than running the necessary commands manually, because the compilation process for a large project tends to be quite complex.
NetHack's build system is one of the parts of the code that is more
frequently replaced in variants. The problem is that the build system
in NetHack 3.4.3 requires manual intervention from the end user in
order to work correctly, which nowadays (in 2014) is almost unheard
of. However, the normal methods of modifing the build system
(e.g. using autoconf as in UnNetHack or AceHack, or cmake as in
NitroHack) basically just add extra layers of abstraction; and in a
world as poorly standardised as that of building C, what typically
happens is that each of these layers is trying to work around
incompatibilities and nonstandard behaviour in the layers below it,
meaning that you have a complex stack built mostly out of workarounds.
Another issue is that there are many more steps in building a C program than most people realise. Some of these are handled by the build system, but others are typically left to the programmer or end user to do manually. This wastes everyone's time, really; the vast majority of the build process can be automated, and thus should be, because the time of a computer is so much less valuable than the time of a human (and computers are faster at it, anyway).
For NetHack 4, I aimed to flatten these levels of abstraction as much
as possible; instead of writing yet another wrapper around yet another
set of poorly standardised existing tools, I'm using aimake, a
build system I wrote originally for NetHack 4 (but is not specific to
it). It's still somewhat unfinished – there are known bugs, missing
features, and interface issues – but it works quite effectively for
building NetHack 4, and hopefully will become more widely used some
day, when it's ready for release.
There are two main differences between aimake and other existing
build tools. One is that aimake aims to avoid relying on
lower-level build tools; most build systems work by producing output
that serves as input to other build systems, and this can go down
multiple layers before reaching anything that actually builds the code
(e.g. with GNU Autotools, Makefile.am is the source for
Makefile.in which is the source for Makefile, which contains
instructions for actually building the code). The other is that
aimake automates many more of these steps than most build systems
do, handling steps which are often left to humans to deal with.
One problem with this method, though, is that it can lead to gaps in
understanding; most people who work on build systems are merely trying
to adapt to existing tools, rather than actually handling the build
themselves. This can make aimake quite hard to understand, as it
works at a relatively unfamiliar level of abstraction. Therefore, I'm
writing this blog post to explain what actually goes on when you build
a C program. A disclaimer: this post focuses on how things typically
work on modern consumer operating systems (especially Linux and
Windows), rather than trying to cover all possible obscure systems. C
doesn't have to work like this. It just normally does in practice.
Normally, I'd start with the first step of the build and move forwards from there. However, that order of presenting things is actually quite confusing when it comes to building C; many of the steps are only needed to prepare for future steps, and it's hard to explain something without first explaining why it's needed. Thus, I'll start in the middle and work backwards and forwards from there. However, I'll first list the steps in order, before explaining them out of order (this order is not set in stone, but is a sensible and logical one to use):
Most build systems handle steps 3, 5 to 7, 9 and 10 in this list
(leaving the others to be done manually, before or after the build).
aimake currently handles 1 to 11 and has made a start on 12. Step
13 is almost always handled by the operating system.
And now, the main body of this post, a description of the build itself.
As an example throughout this blog post, I'm going to use the following Hello World program in C.
#include <stdio.h>
int main(void)
{
fputs("Hello, world!\n", stdout);
return 0;
}
Right now, I want to focus on the #include <stdio.h> line. A common
misconception among people new to C is that it has something to do
with libraries, typically that it causes the definition of fputs to
be "linked in" to the program somehow. Actually, its effect is quite
different: it serves to tell the compiler what types fputs and
stdout have. The above program is, on Linux, 100% equivalent to
this one:
struct foo;
typedef struct foo FILE;
extern int fputs(const char *, FILE *);
extern FILE *stdout;
int main(void)
{
fputs("Hello, world!\n", stdout);
return 0;
}
We no longer have any mention of stdio.h anywhere, and yet the
program still works. So clearly, it's nothing to do with linking.
What's actually going on here is that stdio.h is just a list of
declarations of types, functions, and variables, together with some
macro definitions. The C standard places no restrictions on how a
compiler chooses to implement these definitions, but in practice,
headers like stdio.h are nearly always implemented in a slightly
extended dialect of C (that uses compiler-specific extensions to do
things that could not be expressed in C directly, such as adding
buffer overflow check code based on the lengths of arrays in the
source program).
In this case, we're defining FILE as an incomplete type (the
compiler doesn't need to know the definition of FILE to run the
program, just that it's some sort of struct, because all sane
compilers treat pointers to all struct identically); fputs as a
function from a const char * and FILE * to an int; and stdout
as a variable of type FILE. The extern means that this is just a
declaration, and this file does not necessarily contain a definition
of the function and variable in question. (We'll see where the
definition actually is later on, when the linker gets involved.)
On Linux, stdout is actually a variable. On Windows using mingw,
however, an accessor function is needed to find the value of the
standard filehandles stdin, stdout and stderr, so the
preprocessor expands the program to something like this (I've omitted
some details, and thousands of irrelevant lines):
struct foo;
typedef struct foo FILE;
extern int fputs(const char *, FILE *);
extern FILE *__iob_func();
int main(void)
{
fputs("Hello, world!\n", &__iob_func()[1]);
return 0;
}
We can now see what the purpose of standard header files like
stdio.h is: it's to paper over system-specific differences in the
implementation details of the standard library. What the preprocessor
is doing, then, is evaluating "preprocessor directives" like
#include (to use definitions in a header file) or #define (to do
symbol substitution on a source file, such as replacing stdout with
&__iob_func()[1]). The result is a C source file that you could
just have written directly, but is a little more system-specific than
would be appropriate for the source files of your project.
In addition to standard header files like stdio.h, projects can also
have their own header files (e.g. NetHack's hack.h). From the point
of view of the preprocessor, these work exactly the same way as
standard header files, and they contain similar content (although,
obviously, tend to be less system-specific). These are distinguished
by using double quotes rather than angle brackets, i.e. you would
write #include "hack.h" but #include <stdio.h>.
The preprocessor is also traditionally responsible for removing comments from the source. It still does by default, for backwards compatibility, but modern compilers have no issue with comments, and the build process will work just fine even if you tell the preprocessor to leave the comments in.
Nowadays, the preprocessor is nearly always built into the compiler,
because they work so closely together. However, the preprocessor can
also be run individually. The standard name for a command that does
preprocessing is cpp (standing for, I believe, "C
Preprocessor"); this is normally implemented as a wrapper for
the C compiler, providing the -E command-line option to tell it to
do preprocessing only (and in fact, aimake currently uses the -E
method when it needs to access the preprocessor individually in order
to prevent mismatches between which preprocessor and compiler it
uses). The standard filename for preprocessed output is .i.
In the early of C programming, the preprocessor worked on a very low
level, pretty much just textually manipulating the source. Although
preprocessors can still do that – in case someone decides to use them
for something other than C, which is not unheard of – this rapidly
runs into scaling problems in practice. The problem is that the
standard headers have to be designed to handle all possible programs
that might want to include them; our Hello World program just used
fputs and stdout, but stdio.h has many other features, any or
all of which a program might use. The result is that our preprocessed
Hello World program is 1192 lines long; most of them are blank, and
most of the rest are unused, but the compiler has no way to know this
until after preprocessing.
A traditional build process would preprocess each source file individually, meaning that each header file would have to be read by the preprocessor once for each source file. This has two problems. One of these is that it takes a long time (especially when using C++, whose build process is pretty similar to that of C). Modern computers are fast enough that the time taken is of the order of tens of seconds, rather than days, but even having to wait an extra minute in your build can significantly slow down your development process (because it reduces the rate at which you can use your compiler to catch errors, and means you can't get useful feedback from an IDE). The other problem is that if there is, say, a mistake in a declaration in a header file, this will cause an error compiling every single file that includes that header, whether it cares about the declaration or not.
Given that modern compilers work so closely with their preprocessor
counterparts, there is a solution to these problems: the preprocessor
and compiler can cooperate to compile as much of a header file as
possible ahead of time, without needing to know which source files
will eventually use it. Although not every part of a header file can
be precompiled (e.g. the effect of the textual substitution that
#define performs is impossible to precalculate because it might end
up being stringified), much of a header file is declarations, which
can be. This means that the header file only needs to be parsed once
(rather than once per file that uses it), and that errors in it may be
caught before it's used. (It also helps in the common case where the
source files are changed without changing any headers; the same
precompiled header can be used as last time.)
Although relatively old (I remember using them back in the 1990s),
precompiled headers are nonetheless a newer innovation than most other
parts of the C toolchain, and thus are relatively nonstandardised.
gcc and clang use the extension .h.gch extension for precompiled
headers; Visual Studio seems to use .ipch.
aimake currently always precompiles headers. I'm not 100% convinced
this actually saves time – although it speeds up the compiler in most
cases, it slows down aimake because it has to keep track of them –
but the improved error messages are worth it.
In order to be able to include header files, you have to be able to
find them on the filesystem. The algorithm used by the vast majority
of preprocessors is very simple: the preprocessor has a hardcoded list
of directories, which the user can add to, and the preprocessor will
scan them in sequence until it finds the file it's looking for. In
the case of include "file.h", it will also scan the directory
containing the source file.
Although sufficient for small projects, in large projects, this
approach is highly inadequate. Unlike in a small project, large
projects will typically be formed out of several, mostly unrelated,
parts (e.g. NetHack 4's source ships with libuncursed, which was
originally written for NetHack 4 but is conceptually separate, and
with libjansson, which was written entirely independently of NetHack
and chosen as a dependency by the NitroHack developer). And with
disparate sources comes naming clashes. So far, NetHack 4 has managed
to avoid naming clashes among header files we ship (although there are
currently six names which are used for multiple source files:
dump.c, log.c, messages.c, options.c, topten.c,
windows.c), but this increasingly becomes unlikely as projects get
larger.
There is another problem, which has a simple solution, but is worth
mentioning because it catches some people out: not all C compilers are
configured correctly for the system they run on, and may miss a few
system headers as a result. I've most commonly seen this happen with
the directory /usr/local/include on Linux systems, which is intended
for system-wide header files that were installed manually, rather than
by the operating system's package manager. The fix is just to add the
directory as an include directory for every compile using command-line
options.
Anyway, as a result of the potential for name clashes, the set of header files to include for each individual source file needs to be determined for that file individually. The normal solution in build systems is to do this manually; the user will specify a list of directories to scan for header files, typically a project-wide list with options to override it for particular source files. Although these specifications tend to be quite simple to specify with some sort of loop, and are not hard to write, the fact that they need to be written at all increases the chance of human error (and this sort of error has definitely caused problems in practice). Their existence also encourages the tendency to use multiple nested build systems with different configurations that is frequently seen in large projects, and which is nearly always a bad idea. (There is a relatively famous paper about this called Recursive Make Considered Harmful [PDF].)
In aimake, I use the approach of scanning the entire source tree for
header files with appropriate names, then working out which header is
intended via comparing paths (we take the closest matching header file
in terms of directory structure). Different parts of a project have
to be placed in different directories anyway when using a hierarchical
build, and doing so is sensible anyway, so this is not a particularly
odious requirement.
It's also necessary to scan the system include directories for header
files, because they aren't always at a consistent location on every
system. For instance, on my Ubuntu laptop, the Postgresql header that
NetHack 4's server daemon needs is stored at
/usr/include/postgresql/libpq-fe.h. On some other people's systems,
it's just /usr/include/libpq-fe.h. The solution to this problem
I've most commonly seen used in practice is to require the user to
specify the location as a configuration variable, then use conditional
compilation to select between #include <postgresql/libpq-fe.h> and
#include <libpq-fe.h> respectively. Getting the build system to
just search for the header file in question on the file system is
simpler, and requires less human intervention, and thus is preferable.
aimake does this, in addition to scanning the source tree.
There is one other subtlety here: because the preprocessor works at
the level of directories rather than files, it's impossible to exclude
a file from the header file search if another file in the same
directory is included. This might seem minor, as there's no reason to
arrange header files like that during the actual build. What it does
do, however, is make it much more difficult to reliably discover
dependency loops; a build system wants to avoid using files that
aren't meant to have been built yet (and are left over from a previous
compile), but the directory-level granularity of a preprocessor's
header file search makes this impossible to avoid without using a
separate directory for each generated header file (in case some are
meant to have been generated at that point in the build, but not
others). As a workaround for this problem, and for numerous other
reasons, aimake now copies each header file in the source tree to a
directory of its own in the build tree before building (with a #line
directive so that errors are still reported against the original
source file); I haven't had to resort to this for system headers,
because they can't be confused with user headers due to the different
syntax and system toolchain maintainers work to avoid clashes, but it
would be a possibility if necessary.
It should be noted that the original reason I wrote aimake was that
I'd accidentally introduced a dependency loop into a beta of my
"attempt to merge AceHack with NitroHack" in late March 2012, a couple
of days before it got the name NetHack 4, and couldn't figure out what
was going wrong with the build (back then, I was using the cmake
build system inherited from NitroHack, which didn't realise that
anything was amiss and was hopeless at giving appropriate feedback for
this kind of mistake). Because I was under time pressure (wanting to
get the program ready for April 1), I quickly knocked a script
together as a replacement build system to get the build working, and
after a couple of rewrites and numerous smaller changes, that script
eventually became aimake.
When working on a large project, you want to avoid recompiling it
every time there are changes made to any file; rather, you want to
compile just the bits that actually changed. This is probably the
motivating factor behind the earliest build process automation tools;
this sort of optimization is hard to express in a shellscript or batch
file, leading to the creation of tools like make, which compare
timestamps to determine what needs to be done in any given build.
I'd argue that nowadays, trying to generate input for make is
probably the #1 biggest mistake you can make in a build system (even
though it's very common practice; the problems being that dependency
resolution is a relatively small part of a build, and working around
differences in different make implementations (some of which are
very primitive) is quite complex, and thus it's normally simpler to
just resolve the dependencies yourself rather than trying to get
make to do it. make is also quite limited in what it can do; for
example, it has no obvious support for rebuilding a file when the
build rules for that file in the Makefile change (as opposed to
rebuilding nothing, or the entire project). Most build systems work
as wrappers around make (or the equivalent for IDEs like Visual
Studio); aimake just skips this level of abstraction and handles the
dependencies itself. (I'm not the first person to come to this
conclusion; for instance, the standard toolchain for Perl used to use
ExtUtils::MakeMaker, which generated Makefiles, but is now moving
in the direction of Module::Build, which does the dependencies
itself.)
Anyway, regardless of whether you use make, aimake, or some
completely different tool to process dependency calculation, you need
to know what those dependencies actually are. This was originally
left to the person writing the code to specify, and often still is in
simple projects. However, as a task that can reasonably be automated
(and that is somewhat time-consuming to do by hand for large
projects), automating it makes a lot of sense.
Something many people don't realise about dependency calculation is that correct dependency information is actually needed for two different purposes:
The most common method of dependency automation nowadays is to get the preprocessor to report on every header file it includes, during the build (and preprocessors have pretty advanced support for this; most can generate Makefile fragments directly). However, this leads to a chicken-and-egg problem (you can't calculate dependencies until you compile, but can't compile without knowing the dependencies). The standard solution to this (e.g. as used by GNU autotools) is to start the first build with no dependencies. This satisfies goal 1 (because on the first build, everything has to be rebuilt anyway, thus it doesn't matter that you don't know its dependencies), but fails goal 2, which tends to be dealt with using ugly workarounds. (Just look at this mess.)
An alternative tradeoff (and one that aimake uses, although other
choices are reasonable depending on what your goals are) is to run the
source files through the preprocessor in a separate stage, without
compiling them, to get hold of the dependencies. Thus, in aimake,
this is step 3 of the build (whereas with many other build systems, it
would be step 6).
Although this seems simpler than producing dependencies as a
side-effect of a compile would be, modern preprocessors actually make
it much harder than you would think. The first problem is that they
include header files transitively; this is what you want for a build
(because you're actually building), but not what you want for
dependency calculations (it's much faster, in the sense of "linear
rather than quadratic", to look at what headers are needed without
actually compiling them). The next problem is that the headers in
question might not exist yet (e.g. they're generated files), and (in
the order aimake does things) won't have been located yet. At least
gcc and clang can be told to report on but ignore nonexistent
files, which would seem to solve this problem.
My first attempt at implementing dependency automation was to ignore
the first problem (as it only affected performance) and use the
obvious solution to the second, but it lead to unexpected compile
failures in NetHack, due to a reasonably subtle problem. What
happened was that one of the files in NetHack is called magic.h;
although it's part of the source tree, it hadn't been located yet (and
in general, because a good build system would handle arbitrary files
being generated during the compile without prior warning, there's no
point in locating header files early because that won't help with
generated files). This is fine if there's no file magic.h anywhere,
because then gcc and clang will treat it as empty and just report
on the dependency, which is exactly what we want. However, some
operating systems have a system header magic.h (which I believe is
related to detecting file formats), leading the preprocessor to report
a dependency on the system magic.h (and all its transitive
dependencies) rather than the one in the source tree!
Clearly, the behaviour I actually needed was to treat all header files
as empty, rather than actually including them. Sadly, though,
typically preprocessors don't have an option to do this. I actually
seriously considered writing my own preprocessor to deal with the
problem, but it would have been a mess and probably too large
(aimake is implemented as a single file that you can ship with your
project, much like configure, so I want to keep the size down if
possible; it's already a little over ten thousand lines long). I
eventually found a simpler solution, even if it is a bit sad: aimake
reads the header files itself, looking for #include statements, then
creates an empty file named after each header it finds, and tells the
preprocessor to look there for include files.
Note that one limitation of this method of dependency handling is that a file can't determine which header files to include dynamically based on constants included in a different header file. There are plausible useful reasons to do this, and it's permitted by the C standard. However, looking at what actually happened in practice in NetHack 4, it turned out that almost every location where it happened was a mistake that caused header file inclusion order to be relevant when it shouldn't have been (and the other cases were reasonably fixable). So again, this seems like a reasonable tradeoff to make.
In order to be able to do any sort of processing of the system headers
and libraries, you first have to know where they are. With header
files, you need to know the location of the system headers to be able
to scan the subdirectories of that location for header files like
libpq-fe.h, which I discussed earlier. Libraries intended for
public use are rarely stored in subdirectories; however, aimake needs
to be able to look inside them in order to determine which library
holds a particular symbol, so it needs to find the set of standard
libraries, too.
It's actually a surprisingly hard problem to determine where the system headers and libraries are stored with no hardcoded knowledge of the system you're on, and this may be part of the reason why header file location and object file dependency calculation are normally left to humans by most build systems, rather than being automated. The headers and libraries could be just about anywhere on a system (e.g. on my Windows system, I installed the compiler to a subdirectory of my Documents directory, which could have had an entirely arbitrary name); assuming that all we know the location of is the executables of the C toolchain, can we find the rest?
I tried several techniques, and eventually settled upon two that seem
reasonably portable (by which I mean that they work on Linux with
gcc/clang and GNU ld/gold, on Windows with mingw, and
apparently on Mac OS X too, although that's mostly been tested by
other people because I don't have a Mac handy):
For header files, the preprocessor must know where the header
files are in order to be able to include them; and although
there's no standard option for asking where they are, there is a
standard option (-M) for reporting dependencies. Thus, all we
need is to produce a file with one dependency in each of the
possible standard header file directories.
Currently, aimake uses five header files as dependencies.
There's a full explanation in its source, but here's a quick
summary of the possible directories that header files can be
sorted into on systems I've seen, and which header file aimake
uses as a test:
Header files that ship with the compiler (<iso646.h>,
because there is literally no reason not to ship it with a
compiler, especially as many C libraries don't ship it);
Header files that were patched by the compiler (<limits.h>,
the only file that gcc patches unconditionally);
Architecture-dependent header files (<sys/types.h>; none of
the standard C headers are stored here on most systems which
have it, so I used the most architecture-dependent POSIX
header);
Header files that ship with the C library (<setjmp.h> is the
only header I've found that's in this category on every system
I tested, probably because it's too weird for the compiler to
mess with it);
Nonstandard (i.e. non-C/POSIX) header files that shipped with
libraries (<zlib.h>, because zlib is one of the world's most
widely-used libraries).
For libraries, again there's no standard way to find out where the
linker is looking, even though it must know; I attempted to use
gcc --print-search-dirs even though it's gcc-specific, but it
appears to only find library directories that gcc needs for its
own internal use, rather than all the library directories on the
system. The most portable method I've found is to ask the linker
to link in each of the libraries we care about to a small test
file (one at a time so that the failure to find a library won't
affect the search for the others), and get it to produce a debug
trace as it does so.
There are several problems with this method (even though I use it
anyway). The first is that although the option to ask linkers for
a trace is standard (-t), the format of the output is not, and
can vary wildly even on a single linker depending on the reason
that the library is being linked in. Here's a current regex
aimake might use for parsing the output (with the part aimake
uses to avoid matching the source file removed, and with file
extensions set appropriately for Linux; the file extensions need
to change on other systems):
/^(?:(?:-l|lib)[^ ]+ )?\(?(.*?\/.*?(?:\.a|\.o|\.so)(?:\.[0-9]+)?)(?:\)|\([^\/]*\)|\z)/
The next problem is that, looking at the files matched by this,
sometimes some of them will be text files! This problem is due to
the fact that library developers sometimes have to do weird things
for backwards compatibility. Here's what libncurses.so looks
like on my Ubuntu system, in full:
INPUT(libncurses.so.5 -ltinfo)
I don't know for certain, but my guess as to what happened here is
that libncurses got split into two libraries sometime in the
past (libncurses and libtinfo), and thus libncurses.so
became a wrapper linker script that pulls in both libraries.
Obviously, this script is useless for things like determining
which symbols exist in which libraries. However, the linker trace
will also contain both of the libraries it pulls in, so all that's
necessary with such wrappers is that we ignore them. aimake
scans the first kilobyte or so of the library looking for
non-ASCII characters; if it fails to find any, it assumes that the
"library" is actually just a linker script.
Another issue is that, if we don't use at least one symbol from a
library, the linker may optimize it out; and in some circumstances
(e.g. if it's a static library), it then won't show on the linker
trace output. aimake currently only searches for libraries that
the user mentions might be required in the configuration file (for
performance reasons; searching every library on the entire system
for symbols takes about an hour on my laptop), so I solved this by
asking the user to mention the name of a symbol that they expect
to be in that library, and aimake then forces the linker to link
that symbol using the standard -u option. An added benefit of
this approach is that it ensures that we find the library we
expected, rather than a different library with the same name.
A bad side-effect of this is with respect to the standard
libraries of the system, the ones that are linked in by default.
(In addition to needing to analyse these in order to do dependency
calculations correctly, as any dependencies on them won't need to
be explicitly satisfied, we also need to not pass them to the
linker, because Mac OS X's linker complains and refuses to build
if you try to explicitly link a standard library.) We can't know
how those are divided up between files, so specifying a symbol is
of no use. Thus, I ended up having to settle on the rather
drastic method of asking the linker to link in every symbol in
the standard libraries (--whole-archive, plus
--allow-multiple-definition to reduce the amount of error spam
you get as a result). This normally doesn't produce a usable
output file (nor could it really be expected to), but aimake
doesn't care about this, just about the trace output.
Incidentally, it causes mingw's linker to crash, but only after
it's already printed the trace output aimake needs. (This is
why building NetHack 4 on Windows shows an error dialogue box
about ld.exe crashing.)
All this annoys me, as something this apparently basic really shouldn't be this difficult. I guess the problem is that nobody really expects someone to try to determine inherently system-specific information (where the headers and libraries are installed) in a system-agnostic way.
Traditionally, the first thing done in any build is to fix values for
the parts of the build that vary from build to build. This includes
everything that needs to be specified by a human before the build
starts; thus, configuration is quite lengthy and time-consuming with
NetHack 3.4.3, as you have to answer questions like "what terminal
codes library does your system use?". aimake cuts down considerably
on this sort of question, because it can determine so much by itself,
but there are always going to be questions that only a human can
answer, such as "are you interested in building the tiles ports", or
"do you want me to install this to your home directory or
system-wide?". (At least aimake mostly manages to condense all
these choices down to a couple of command-line options. It does have
one major problem in terms of user-friendliness right now, though,
which is that there's no simple way to specify unusual options you
want to pass to the compiler, or similar special build rules; you can
do it but the syntax is horrendous. This is something I need to work
on before aimake is really ready for production use.)
However, there are also lots of questions whose answers can be
determined experimentally, and which a computer can answer as easily
(in fact, more easily) than a human. This is normally performed by a
program named configure (typically, but not always, generated by a
GNU autoconf), with a separate configure program written for each
project and shipped with the distribution tarball. configure's job
is to paper over nonportabilities between systems by determining what
needs to be done on each one.
Just as happened with curses, though (as I wrote in
my blog post on portable terminal control codes), configure is
increasingly solving the wrong problem. I have written systems based
on GNU Autotools that aimed to do everthing by the book as much as
possible, but it was mostly as a joke / thought exercise; modern
programs don't need to worry about, say, stdlib.h not existing (and
don't really have an obvious workaround for if it doesn't). At least
autoconf's documentation mentions that that particular check is
obsolete nowadays, and recommends leaving it out.
There are several checks that are more useful, but so far, I've only
actually needed two checks of this nature in NetHack 4 (and aimake
has support for doing them), a very small portion of the build system
as a whole (and not something that warrants being one third of the
"standard" build sequence, which for autotools, is configure,
make, make install). One is about how to set the compiler to C11
mode (--std=c11, -std=c11, or nothing and let the compiler fall
back to non-standards-compliance mode, which contains all the C11 and
C99 features we use in the case of gcc and clang). The other is
how to indicate that a function never returns: is it _Noreturn (the
version recently standardised in C11), __declspec(noreturn) (used by
Microsoft compilers), or __attribute__((noreturn)) (used by gcc
and clang before the standard syntax was invented)? I originally
tried to detect this using compiler predefined macros, but this caused
problems on some specific old versions of clang (which are still
used nowadays on some Mac OS X systems). Neither of these checks
exists in my current version of autoconf, so it wouldn't have helped
much here.
It should be noted that this is the most user-visible step (because it
requires the most manual intervention), and also the one that varies
the most between build systems. Thus, it needs the best interface,
and it's a particular pity that aimake falls down here.
We've now seen pretty much everything that happens at the C level, from the source files up to the preprocessor. As a recap from earlier, the preprocessor's output is typically a slightly extended C, which contains declarations for all the relevant parts of the standard library (and typically for irrelevant parts, too, but those get optimized out). The next part of the build process is the compilation and assembly, which takes the preprocessor's output and transforms it into an "object file".
Just as the preprocessor's output is slightly extended C, the object
file (which is the linker's input) is slightly extended machine code.
The difference from the machine code that a processor actually runs is
that it's full of instructions to the linker, as well as instructions
to the processor; typical linker instructions are along the lines of
"this string is read-only data, place it with the other strings for me
and tell the MMU to mark it read-only", or "I know I said to call the
all-zeroes address as a subroutine, but can you replace that with the
address of strcmp when you figure out where it is?". In short, an
object file contains as much of the machine code as can be calculated
by looking at one file in isolation; the rest is made out of linker
instructions to patch up the file later on in the build.
There are two basic approaches that can be used for this C to machine
code transformation. One is to do it directly; the other is to go via
assembly code (which is almost as low-level as machine code, but which
is much more human-readable, and which can express various linker
instructions that machine code can't. When assembly code exists as an
intermediate step (or sometimes even when it doesn't – some compilers
can produce it on demand), compilers typically support the -S option
to let you take a look at it. Our Hello World program expands to just
30 lines of assembly. It's also possible to "disassemble" the object
file, to determine what its machine code would look like as assembly,
to make it more human readable. Here's the Hello World program as C
(as a reminder):
#include <stdio.h>
int main(void)
{
fputs("Hello, world!\n", stdout);
return 0;
}
And here's how it looks as assembly produced by the compiler, and how the object file looks after disassembly (rearranged so that common lines are next to each other; my disassembler also printed the machine code as hexadecimal, but I've removed that to save space, even though it leads to the newline and NUL at the end of "Hello, world!" displaying ambiguously as periods):
.file "t.c"
.section .rodata Contents of section .rodata:
.LC0:
.string "Hello, world!\n" Hello, world!..
.text Disassembly of section .text:
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
pushq %rbp push %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp mov %rsp,%rbp
.cfi_def_cfa_register 6
movq stdout(%rip), %rax mov 0x0(%rip),%rax
movq %rax, %rcx mov %rax,%rcx
movl $14, %edx mov $0xe,%edx
movl $1, %esi mov $0x1,%esi
movl $.LC0, %edi mov $0x0,%edi
call fwrite callq 22 <main+0x22>
movl $0, %eax mov $0x0,%eax
popq %rbp pop %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE0:
.size main, .-main
.ident "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
.section .note.GNU-stack,"",@progbits
On the left is the assembly output for the Hello World program; we can
see that it contains many notes for the linker (the lines starting
with .), and various constructs that don't exist in machine code
(e.g. it can say call fwrite, and mention stdout, even without
knowing where fwrite and stdout are in memory). Comparing this to
the machine code produced by disassembling the object file, we can see
that many of the lines are basically the same, but some have bits
replaced by zeroes; movq stdout(%rip), %rax cannot sensibly be
interpreted as mov 0x0(%rip),%rax, for instance. Likewise, the call
to fwrite has been replaced by a call to the current instruction
pointer location (which also translates as zeroes in machine code).
It's worth noting that, even though this program was compiled without
optimization, the compiler has done a small optimization anyway; the
original Hello World program called fputs, but the compiler has
compiled it into a call to fwrite. Both these functions need to use
a buffer to store their output, according to the C standard; fputs
has to do a series of strncpy or equivalent to fill the buffer
(strncpy instead of strcpy because it has to allow for the
potential that the string might be very long and so overflow the
buffer, causing it to be output in sections), whereas fwrite knows
the length before it even starts, and (for short strings like this)
can memcpy it into the buffer directly. memcpy is faster than
strncpy because it can copy more than one character at a time
(strncpy has to take care not to read past the end of the string,
and doesn't know where that will be in advance), so fwrite should be
faster than fputs. (We can see the "14" in the assembly code, that
isn't in the original program, containing the length of the string
"Hello, world!\n" that appears in our program, not counting the
terminating NUL because that isn't output.)
The object file places its output into various sections, which tells
the linker (and eventually the OS kernel) about the purpose of the
data stored there. Our main function goes into a section that is,
rather confusingly, named .text; this contains the actual code that
makes up our program. (This is on Linux; on other operating systems;
the name of the section varies, but is nearly always some variation on
"text" for historical reasons, even though executable code is about as
binary on the binary/text distinction as you can get.) The string
"Hello, world!\n" itself is in a separate section, .rodata, which
stores read-only data.
The .cfi_ lines tell the assembler to generate stack unwind
information, which is mostly irrelevant here (it's used by exception
handling in C++ to figure out which catch blocks might be relevant
for the current code location, and by debuggers to produce stack
backtraces); they also compile into a section (.eh_frame) in the
object file.
In addition to the sections, our object file also contains headers,
which contain instructions to the linker; the information about names
like main and stdout hasn't just disappeared, but as it can't be
expressed in machine code, it needs to be expressed some other way.
On Linux, we can see these headers using objdump -x. This is more
than a screenful of text, but here are some interesting excerpts:
SYMBOL TABLE:
[...]
0000000000000000 g F .text 0000000000000029 main
0000000000000000 *UND* 0000000000000000 stdout
0000000000000000 *UND* 0000000000000000 fwrite
RELOCATION RECORDS FOR [.text]:
OFFSET TYPE VALUE
0000000000000007 R_X86_64_PC32 stdout-0x0000000000000004
0000000000000019 R_X86_64_32 .rodata
000000000000001e R_X86_64_PC32 fwrite-0x0000000000000004
The "symbol table" tells the linker about any identifiers in the
source code that need to be given a consistent meaning between files.
In this case, main is 0x29 bytes from the start of the .text
section, and the compiler doesn't know where stdout and fwrite
are. Meanwhile, the "relocations" tell the linker which parts of the
machine code will need patching up; it's asking the linker to
substitute in appropriate values for just before stdout, just before
fwrite, and for the start of this file's part of the .rodata
section (which is where the "Hello, world!\n" string is stored).
The compiler cannot figure out where any of these will be; it can't
know where the .rodata section is relative to the .text section
because it doesn't know how large those sections will be, and stdout
and fwrite are in the standard library, not in the Hello World
program itself. The hexadecimal numbers in the left column tell the
linker where in the .text section the new values will need to be
substituted (and the central column explains what format the linker
should use for the substitutions).
The traditional name for a compiler is cc, and for an assembler is
as. However, the compiler also traditionally runs the linker once
it's done; although appropriate for very small programs, this is not
what you normally want for a large project (where you're going to want
to recompile just the source files that changed, but relink all the
executables that depend on any file that changed). Thus, it's typical
to tell the compiler to do just the compile (and assemble, if
necessary) using the -c command line option, which is standard.
Object files have the extension .o with most toolchains, although
some Windows toolchains use .obj.
Once we have our object files, the next step is to work out how to fit
them together to form executables. There are two sources of object
files; one is the C source files we just built, and the other is the
system libraries. (System libraries can ship object files directly;
more commonly, though, they're bundled together into libraries of
object files, with extensions like .lib or .a, which are simply
archives containing multiple object files, typically with some extra
metadata to allow the linker to figure out which of the contained
object files are relevant more quickly. On Linux or UNIX-based
systems like Mac OS X you can use the command ar x to unpack a
library and look at the object files inside it directly.)
In order to produce an executable, we need a list of object files and
libraries that together have no unmet dependencies; any undefined
symbols in any of the object files (such as stdout in our Hello
World object file) need to be defined by one of the other object
files. We also need an "entry point" to the program, so that it has
somewhere to start running. (The way this is typically implemented is
for the entry point to be somewhere in a standard library, normally in
an object file whose sole purpose is to provide an entry point; and
that object file calls main, which it leaves undefined, performing
initialization before the call and cleanup afterwards.)
Thus, one thing we need to do as part of the build is to produce such a list. This is a job that's normally left to the programmer, and in my opinion, making the programmer do it is a terrible idea. As usual with jobs that are left to humans, it's error-prone; unlike some of the other things that are normally left to humans, it's also somewhat time-consuming, as whenever you add a new file to your project, you'll need to add it as a source for one or more of your executables (or libraries, if you build libraries as part of your build).
This is thus an excellent candidate for automation, and the concept
here is pretty simple: we have one executable for each main
function, and we find the files required to produce it by recursively
looking for object files or libraries that define symbols that are
undefined in the object files that are already part of the build. In
the case of our Hello World program, aimake would start by checking
the symbol table for our main program, finding it needed definitions
of stdout and fwrite, then finding those in the standard library,
and it'd be done.
One potential problem here is if symbols with the same name are
defined in multiple files, but aimake uses heuristics to figure out
which file to link that work excellently in practice for correct
programs. However, there's another problem: when the input programs
contain subtle errors (such as linking against implementation details
of a library defined elsewhere in the project, rather than using the
public API of that library), aimake can normally find a solution
that works anyway (for this example, linking against the relevant
object files in that library directly), even though we wouldn't want
it to. At the moment, I check to ensure this hasn't happened by
inspecting the symbol tables manually once every few months, but this
is unsatsifactory. Ideally, there should be some way to tell aimake
(or some way to have it automatically deduce) that certain files
should be kept separate; a crude way to do this at the moment is to
define symbols with the same name in each to force a link error, but
this isn't really satisfactory.
In order to actually discover which symbols are defined (or referenced
but undefined) in the various object files, we need to look at their
symbol table headers. We could use a program like objdump for this,
but it's rather system-specific; there's a more generally usable
program, nm, that deals with symbol tables specifically. Again, we
have to deal with variations in the output format, and come across a
particularly weird problem: POSIX defines a standard output format for
nm, but the way you get at that format varies from nm
implementation to nm implementation, making it not particularly
useful as a standard. Meanwhile, the default output format of nm is
consistent enough that just matching it directly seems to cause no
problems.
Once we know which object files we need to combine to make an executable, the next step is to use the linker to actually make our executable.
The first job of the linker is to work out how to lay everything out
in memory; it will generally combine sections with the same name into
contiguous blocks. On modern systems, the sections keep their
identity all the way into the executable, and so combining them means
that the executable's headers will be simpler and shorter. There are
multiple reasons that the executable needs to know about the sections.
One is to correctly configure permissions on memory while the
executable is running; the kernel will tell the computer's memory
management unit (MMU) which parts of memory are supposed to be
readable, writable, and/or executable, and violating these rules will
cause a crash. For our the sections used by our Hello World program,
.rodata is readable but not writable or executable (which is useful
for diagnosing errors in which you try to write to a string literal,
or to deallocate one); .text is executable and readable but not
writable (for security reasons, toolchains try to avoid memory that's
both writable and executable as far as possible). Another reason is
that some of the sections can be optimized out of the output entirely;
the .bss section is for read-write data that's initialized entirely
with zeroes, which is a common enough special case that it makes sense
to not have to pad the executable with that many bytes of zeroes. The
kernel knows about this rule, but needs the .bss section identified
so it can allocate memory for it at runtime.
The linker has a lot of control over the memory addresses used by the program; object files typically have no opinion on where something should be placed in memory, but it's in the linker's power to fix all the addresses within the resulting file, and this is what it does in typical usage. (There's no need to worry about clashes between executables; the MMU will place each executable in its own separate address space, so each executable has perfect control over how it wants to lay out memory.)
Once the linker's decided all the addresses that the program should
use, it creates an output file that's basically a memory image of each
section, and substitutes in addresses according to the relocations
requested by the compiler. This list of sections, plus appropriate
headers, is the executable file (i.e. .exe on Windows) that's
actually produced on disk. In order to run such a file, the operating
system basically just has to memory-map all the sections in the
executable at the virtual addresses that the linker indicates, then
starts the program running at the start address indicated. (Modern
operating systems can thus optimize memory storage for executables the
same way they would for memory-mapped files.)
It's worth noting that some operating systems have rather simpler
executable formats than this. A DOS .com file is a memory image of
a single section (starting at a virtual address of 0x0100), with an
entry point at the start of the section, that's readable, writable and
executable. The advantage of this format is that it doesn't need a
header at all, as all the information that it would specify is fixed;
the disadvantage is that because the 8086's memory management was so
primitive, it means that the entire program is limited to 65280 bytes
of program, static data, and stack.
Although the main job of the linker is to fix memory addresses and patch up the relocations accordingly, it also has a few other jobs. One is handling code that define a variable in multiple source files. There are three ways to specify variables that the linker might potentially have to process, in C:
extern int foo;int foo;int foo = 0;The first and third cases are well-defined and have the same meaning
everywhere; the first uses extern to explicitly state it isn't a
definition, and the third initializes the variable (and thus must be a
definition). The second case is more ambiguous; the standard states
that it's always a definition, but not all C programmers seem to have
got the message, and sometimes it's incorrectly used as just a
declaration instead. Worse, sometimes all your object files just say
int foo;, and none of them initialize it; now (in pre-standard C)
one of them is a definition, the others are declarations.
Many linkers thus have special logic to handle this case, converting
one all but one plain int foo;-style definition into a declaration
if it's required for the program to link correctly (by allocating all
the definitions at the same memory address). Some don't, perhaps for
technical issues (e.g. building shared libraries on Mac OS X).
Because well-written programs shouldn't be doing this sort of thing
anyway, and because it would confuse aimake's heuristics, aimake
tells the compiler to tell the linker that all definitions are
definitely definitions (rather than possibly declarations), and thus
can help catch this sort of error. (NetHack 4 was unintentionally
doing this for a long time; two different variables windowprocs were
getting merged together, when they shouldn't have been. It didn't
affect the operation of the program, as it happens, so I'd never have
caught it without aimake telling me something was wrong. It didn't
manage to articulate the problem very clearly, though, and I had an
incorrect fix in place for months, until I finally figured out what
was wrong when working on the Mac OS X port of NetHack 4.)
The linker can also catch certain problems with an executable that the
compiler can't; for instance, it can notice that a function isn't
defined anywhere (leading to an undefined symbol error). However, the
linker can't check as much as you'd like; if you declare a variable as
an int in one file and a float in another, then it's very unlikely
that the linker will be able to discover the type mismatch (it might
know about the expected size of the two resulting symbols, on some
operating systems, but both types are usually 4 bytes long; in order
to know about the type, the only source of information the linker
could rely on is the debug information, which linkers typically don't
parse and which the compiler doesn't always generate).
Although you might think that the build is done once the executables are produced, there's still several steps left in a full build process. One problem at this point in the build is, although we have a working executable, it would be very hard to ship. One possible build layout is for the executables and object files and source files to all be mixed together in the source tree (something I personally hate because it makes it impossible to have multiple builds from the same source, and makes reversing a build hard, but which is nonetheless very common), which is too disorganized to ship easily. The alternative, having files generated during the build in a separate directory, means that the executables are separate from any data they might need (which is still sitting in the source tree). Either way, some files are going to need to be copied and/or reorganized before they're really usable.
The simplest possible form of installation is simply taking the files
we just built, together with relevant data files from the source, and
copying them to the location the user asked us to install them in
(back during configuration, at the start of the build). There's
nothing conceptually too difficult about this; however, it's nearly
always a separate step from the actual build due to the potential need
for elevated permissions (it's common to want to install into system
directories that aren't writable by ordinary users, like /usr/bin on
Linux or a subdirectory of CSIDL_PROGRAM_FILES (which is typically
C:\Program Files on the filesystem) on Windows).
There are also some subtle details that build systems take care of during this step. For instance, the build system needs to create directories before installing in them. Another example is that it's common to "strip" executables while installing them; this discards all information in the executable (symbol tables, debug information, etc.) that isn't absolutely necessary for it to run, and so reduces disk usage at the expence of debuggability. (A more recent innovation is to split out the debug symbols into a separate file, typically stored on a network and downloaded when debugging information is needed.)
Another job of the install process is to set the permissions on the
files it installs. This is surprisingly easy to get wrong, especially
when they need to be different from the defaults. For example, on
Linux and UNIX-based systems, NetHack in general and NetHack 4 in
particular set permissions so that players can't write the high score
table, or write bones files, without going through the nethack
executable or using administrator privileges. Some distributions
(which modified this step of the install process, despite warnings in
the documentation that their new configuration was a bad idea) managed
to screw this up to the extent of introducing a security bug that
could allow anyone with local access to take over the whole system.
It's also worth noting the "DESTDIR convention", which will become
relevant later. The idea is that you compile as if you were
installing into one location (telling your program to look for its
data files in /usr/share, for instance), then actually place the
compiled files in a different location (typically somewhere in your
home directory). It's easy to add this feature to an installer, and
forgetting will make some of the later steps of the build process
almost impossible to complete. (The way you specify this using GNU
automake, and with most hand-written makefiles, is to set a make
variable DESTDIR; aimake uses a command-line option --destdir.)
In addition to its use in generating packages, this is also handy when
installing into a chroot; I use this feature when updating the server
on nethack4.org.
Still, this is one of the simpler steps. The main problem from the
point of view of a build system designer is that because it needs
enhanced privileges, the UI will inevitably be more complex than for
the other steps. aimake supports three different models for
handling the install step:
If you don't actually need permissions for your install, you can
just use -i (i.e. "install as well as building") directly, and
things work fine.
You can tell aimake how to elevate permissions with the -S
option, e.g. -S sudo, and it'll use that method (sudo on Linux
is very similar to UAC on Windows; it can only be used on an
administrative account, and prompts for your password, elevating
one process if i's entered correctly).
You can run aimake without -i to do the build; then elevate
permissions, and run with -i --install-only. (This is how -S
is implemented internally.)
The second method is the most convenient, and minimizes the risk of
permissions-related errors (a build directory full of files you don't
own is always frustrating to deal with). The third method is the one
that most other build systems use, so it's included to make it easier
to write a wrapper that makes aimake look like, say, GNU autotools.
We're now past the point where most build systems consider their work to be done. This is a pity, as resource linking is something that typically has to be done at the same time as the installation; the normal workaround (that's been repeated so many times across so many projects that many people don't realise it is a workaround) is to manually write build rules to perform the relevant steps. On Windows, the situation is less bad, because Visual Studio does a resource link just after linking (and thus it happens immediately before installation).
The term "resource link" comes from Windows, but the general principle
is the same across operating systems: a plain executable by itself is
not particularly usable, because all it has is a filename, and (if
you're lucky) documentation. Documentation might be useful to a
human, but what can a computer do with a name like nethack4.exe but
place it in a list of thousands of other executables that nobody will
ever scroll through? (This is not just a hypothetical; it's Firefox's
actual UI on Linux for selecting a program to open a file, when it
doesn't know of an appropriate option already, because it just opens
up an "Open File" dialog box that you even have to navigate to
/usr/bin by hand. This really sucks when all you wanted was to open
a text file in a text editor.)
Clearly, what is needed is some sort of metadata: a longer description
than the filename, an icon, perhaps a version number, things like
that. On Windows, this is compiled into the executable. On Linux,
it's typically done by means of .desktop files in a known directory
(/usr/share/applications); many desktop environments maintain an
index of these files so that they can grab the metadata for a given
executable on demand. (I'm not sure how this works on Mac OS X,
although would be interested for someone to tell me.)
It's impossible for a build system to know what all the metadata
should be without being told. However, aimake can certainly
translate it to an appropriate format for the OS by itself, and the
amount of information it needs to make a decent shot at it is actually
very small. (The only pieces of information that it can't at least
make a reasonable guess at or a plausible placeholder for are the
version number and icon; and if not specified, it'll just tell the OS
to use its default placeholder icon.)
It would be reasonable to do this step before the install, rather than
after; that's where Visual Studio does it, and I originally tried to
put it there. However, doing it just after the install (while
aimake still has elevated permissions, so that it can write to
system directories like /usr/share/applications) turned out to be
much simpler in terms of aimake code (which in turn made NetHack 4's
aimake.rules simpler as it didn't have to try to deal with the
pre-resource-link and post-resource-link versions of executables
separately). Besides, on Windows, you want to make a Start menu
shortcut as well, and because shell links on Windows have a curious
mix of overengineering and underengineering (some of which is to
compensate for bad design decisions made elsewhere), it's impossible
to create a robustly behaving shortcut unless its target exists at the
time. (aimake currently does not make these shortcuts during the
install process for this reason, also because most of the existing
wrappers use the wrong APIs and when I wrote a new wrapper, it was 153
lines of C++ before even writing the code to communicate with aimake
itself.)
As a fun fact, the two main NetHack 4 executables, nethack4 and
nethack4-sdl, differ only in filename and metadata (nethack4-sdl
is a symlink on Linux, because the metadata is in external files).
The filename difference determines the default interface plugin to use
(an ending of -sdl loads the graphical interface by default); as
well as explaining the interface difference, the metadata is used to
request a terminal window for nethack4, while not opening one for
nethack4-sdl because it doesn't need one and so it would look ugly.
So far, we've been focusing on the build and install process as it looks to a developer. However, distributing a source tarball and telling users to build it is considered a very user-unfriendly method of distribution nowadays. On Linux, nontechnical users want a package that they can point their distribution's package manager to. On Windows, most users will want an installer that they can double-click on. (Additionally, nothing about the previous steps has any particular support for an uninstaller, something which any software package should have; the sort of end-user installation framework discussed in this section typically comes with an uninstaller as well.)
This step is going to be inherently somewhat system-specific; Windows
Installer has many differences from dpkg (the Debian equivalent),
for instance. However, some things are the same. The most notable is
that the input into these install tools is a folder hierarchy
containing the files that would be installed; the DESTDIR convention
is very useful here. (The package generation tools also need to be
told about the permissions on the files, but ideally, administrator
permissions wouldn't be needed for a DESTDIR install; on Linux, the
workaround for this problem is a program called fakeroot which
intercepts attempts to set permissions and remembers which permissions
the files "should" have, and on Windows, aimake will make a list of
all the files it's installing and the permissions they need and pass
that to the package generation tool separately.)
Currently, aimake's support for generating an installer on Windows
is almost complete; it can get as far as generating an input file for
WiX, which can then take the build process the rest of the way.
The only thing it doesn't do is actually run WiX; that's currently
left to the user, even though it should be easier to automate than do
manually. (One problem is that Windows Installer has a few design
issues that need working around, and some of the recommended
workarounds are ridiculous; eventually, I stopped trying to use them,
and instead came up with my own workarounds which both practically and
theoretically seem to work better, but now the build process spams
warnings and errors because I'm not using the recommended workarounds.
(Interestingly, the errors and many of the warnings are false
positives caused by the same design issues that lead to the
workarounds being necessary in the first place. It's a good thing
that "errors" from Windows Installer's consistency checkers are really
just warnings, and thus can be turned off.)
The situation on Linux is a little more complex. So far I've been
focusing on Debian (who have the most widely used package format).
Debian's policy is written assuming that either the package was
developed for Debian in particular, or that it was developed without
knowledge of Debian and was packaged separately by one of their
developers. The case of "a package that exists on its own but knows
how to deploy itself on Debian" makes it quite hard to work out an
appropriate source package (a binary package is much easier).
Currently, aimake itself has all the appropriate options to handle
being run by dpkg-buildpackage, which requires a short wrapper
script (31 lines in NetHack 4, probably about 20 for most packages) to
tell dpkg-buildpackage how aimake wants to be run. Much of the
Debian metadata should be the same for all aimake-using programs,
though (just as happened with WiX), so I'm hopeful that eventually,
aimake will have an option to just automate all the steps in
generating a Debian package. This would lead to a weird situation in
which aimake is running dpkg-buildpackage to run itself, but this
method maximises the chance that the build is reproducible.
As something that happens at runtime, this is a little irrelevant to
the design of a build system, but I'm mentioning it for completeness.
So far, we've been implicitly assuming that the build is a so-called
static build, in which all the code that runs at runtime is part of
the executable. In practice, though, this isn't normally the case; an
executable will depend on shared libraries (.so files on Linux,
.dll on Windows, .dylib on Mac OS X), which contain code that's
shared between multiple executables.
Conceptually, dynamic linking is pretty similar to regular, static
linking; the dynamic linker picks an address for the shared library
and maps it into the address space of the executable, which then makes
calls into it. This means that the executable needs to contain
some sort of relocations, just the same way that the object file did.
Here are the five relocations that end up in our Hello World
executable on my 64-bit Linux system (as printed by readelf -r):
Relocation section '.rela.dyn' at offset 0x3a8 contains 2 entries:
Offset Info Type Sym. Value Sym. Name + Addend
000000600ff8 000200000006 R_X86_64_GLOB_DAT 0000000000000000 __gmon_start__ + 0
000000601040 000400000005 R_X86_64_COPY 0000000000601040 stdout + 0
Relocation section '.rela.plt' at offset 0x3d8 contains 3 entries:
Offset Info Type Sym. Value Sym. Name + Addend
000000601018 000100000007 R_X86_64_JUMP_SLO 0000000000000000 __libc_start_main + 0
000000601020 000200000007 R_X86_64_JUMP_SLO 0000000000000000 __gmon_start__ + 0
000000601028 000300000007 R_X86_64_JUMP_SLO 0000000000000000 fwrite + 0
We can see our old friends stdout and fwrite here, still waiting
to be linked against libc. However, we can see that the offsets for
the relocations are much higher than existed in the object file;
that's because the linker has already determined addresses for
everything in the executable itself, and so knows where the
relocations need to be at runtime. Dynamic linking is harder than
static linking because the OS really wants the shared library to be
bitwise identical between all the processes that run it (so that it
can maintain just one copy of it in physical memory); on 64-bit Linux,
the solution to this is to place the relocations in various tables
that the dynamic linker updates, rather than in the code directly, and
making calls indirectly via the table. (This won't work for stdout,
which is a variable rather than a function; the linker resolved the
problem by putting it in a separate table.) This also means that the
shared library needs to be written in such a way that it can be moved
around in memory and still run correctly, but on x86_64, the
processor makes this pretty easy by allowing memory references to be
relative to the program counter. (Meanwhile, on 32-bit x86, it's a
complete nightmare; the compiler can handle it, but it has to jump
through such hoops that you can instead tell the compiler to not
bother, in which case the dynamic linker has to make a copy of the
shared library in memory and patch up all the relocations the same way
that the regular linker does. Linux's dynamic linker is actually
willing to do this; on x86_64, though, it refuses, explaining that it
really should be the compiler's job to make the library
position-independent on a system where it's so easy.)
I won't go into all the details of dynamic linking here, partly
because they aren't relevant to understanding build systems and partly
because I don't know what they are. However, there is one issue that
needs to be addressed: what does it mean to link against a shared
library, given that its code doesn't actually end up in the
executable? The answer lies in the concept of an import library,
which is a file that looks like a static library to the linker, but
actually just puts relocations into the output executable, rather than
code. On Linux, each shared library can also act an import library
for itself, which makes shared library deployment pretty easy, but
writing build systems confusing (especially when you consider the case
of two shared libraries that need symbols from each other at runtime;
this is not technically a circular dependency, but you need to somehow
come up with a working import library by other means, such as by first
linking the libraries without the dependency on each other). On
Windows, import libraries tend to be separate files that are generated
by a program dlltool from a description of which symbols go into the
shared library; aimake gives it the object files from which the
shared libraries are built as a handy method of describing the shared
library without actually needing a copy of it (and thus breaking up
the circular dependency that way).
There's also a point that's important for programmers, too. On Windows, imports from a shared library will need special code generated for them, so they have to be marked in the source file. Likewise, exports need to be marked as such inside the shared library on Windows. On Linux, exports don't need to be marked, but they should be; this makes it possible for a build system to hide all the non-exported symbols from the API of the shared library by means of command-line options, thus reducing namespace pollution.
Handling appropriate marking is normally done by the preprocessor. You typically have a header file declaring the API of your shared library, which looks something like this:
#ifdef IN_SHARED_LIBRARY_INTERNALS
# define IMPORT_EXPORT(x) AIMAKE_EXPORT(x)
#else
# define IMPORT_EXPORT(x) AIMAKE_IMPORT(x)
#endif
int IMPORT_EXPORT(function1) (void);
int IMPORT_EXPORT(function2) (int, int);
Then, users of the shared library just include the header; the shared
library itself does #define IN_SHARED_LIBRARY_INTERNALS and then
includes the header, and thus gets the "export" definitions rather
than the "import" definitions. The AIMAKE_EXPORT and
AIMAKE_IMPORT macros are defined by aimake to expand into whatever
system-specific annotation is needed to import or export from a shared
library. (The exact syntax is subject to change, because gcc
doesn't like the way the current syntax interacts with functions that
return pointers; I'm currently working around that with typedef, but
really need a better solution.)
As far as I can tell, this sort of marking is necessary to create
shared libraries, as the API of the shared library has to be specified
somehow. However, aimake will spot these annotations and
automatically generate shared libraries rather than executables when
it sees them, so no extra work is needed beyond the bare minimum.
(Some improvements to this are needed, though; it currently doesn't
work on Mac OS X because I don't know enough about shared libraries on
that system, and there really should be some way to override the whole
mechanism and generate static libraries instead.)
Hopefully, this post should give C programmers something of a better understanding of the toolchain that goes into actually building their programs; perhaps it'll even inspire someone to go into toolchain development. I hope I've also made the point that a lot more of a build toolchain can and should be automated than typically is; there's a lot of programmer time being wasted right now dealing with things that should really be done by a computer. Most of the attempts I've seen to fix this are dealing with the wrong problem; people look at existing build systems, and think "we need a better tool for writing Makefiles" or "we need a better tool for generating configuration", when these are really relatively small parts of a build.
I hope aimake acts as a proof of concept that almost the entire
build process can and should be automated, and perhaps one day grows
into a tool that can be widely used for this purpose (even if today,
it suffers from UI problems, the occasional bug, missing features, and
incomplete platform support). At the very least, maybe the world's
build system designers will be inspired to deal with every part of the
build, not just the small corners they previously worked on, and I'll
be able to use something standard rather than being forced to work on
aimake.