Linking is usually described as “matching up symbols”, which is true and completely useless, because it does not tell you what happens when the match is not unique, not found, or not needed. Here is a link that fails for a reason no amount of symbol-matching intuition predicts:
$ cat mu.c
extern int a_fn(void);
int main(void) { return a_fn(); }
$ cat ma.c
extern int b_data;
int a_fn(void) { return 1 + b_data; }
$ cat da.c
int a_data = 10;
$ cat mb.c
extern int a_data;
int b_fn(void) { return 2 + a_data; }
$ cat db.c
int b_data = 20;
$ ar rcs libMA.a ma.o da.o
$ ar rcs libMB.a mb.o db.o
$ clang -o prog mu.o libMA.a libMB.a
$ ./prog ; echo $?
21 <-- fine
$ clang -o prog mu.o libMB.a libMA.a
ma.c:(.text+0x7): undefined reference to `b_data'
The same four object files, in a different order, and one order links while the other does not. Every symbol involved is defined exactly once. There is no duplicate, no missing definition, no ambiguity. The failure is purely about sequence, and the message names b_data — a symbol that is defined, in db.o, inside an archive that was on the command line.
Understanding why is the entire content of this module.
GNU ld’s static link is a single left-to-right pass with one piece of state: the set of currently-undefined symbols. It starts with everything undefined, and shrinks.
THE PASS
undefined = {} # nothing wanted yet
for each input file F, left to right:
if F is an OBJECT (.o):
add every symbol F defines to `defined`
remove every symbol F references from `undefined`
if F is an ARCHIVE (.a):
repeat:
pulled = false
for each MEMBER M of F, in archive order:
if M defines something still in `undefined`:
take M: add its definitions to `defined`
remove its references from `undefined`
pulled = true
until nothing more can be pulled
if F is a SHARED OBJECT (.so):
record it as a source of definitions, but resolve nothing yet
at the end: anything left in `undefined` is an error
Three consequences fall straight out of that pseudocode, and each one is a thing people get wrong.
One: an object file is unconditional, an archive is conditional. Everything in a .o is always taken, whether it is needed or not. A member of an .a is taken only if it answers a name that is undefined at that moment. This is the entire reason archives exist: they let you ship a thousand-object library and link only the eight objects your program needs.
Two: the scan is one pass, not repeated. The inner repeat loop is within a single archive, and it is what makes an archive self-contained. It is not a retry of earlier archives. Once the linker has moved past libMB.a, it does not come back.
Three: therefore order is a semantic input. Not a performance hint, not a style preference — part of the meaning of the link. libMA.a libMB.a and libMB.a libMA.a are different links, and in general only one of them resolves.
Step through the failing order by hand. Start: mu.o wants a_fn.
ORDER: mu.o libMB.a libMA.a
mu.o defines: main
wants: a_fn undefined = { a_fn }
libMB.a scan members for anything defining a_fn:
mb.o defines b_fn, a_data no
db.o defines b_data no
nothing pulled undefined = { a_fn }
libMA.a scan members:
ma.o defines a_fn YES -> take it
wants b_data undefined = { b_data }
(repeat within this archive)
da.o defines a_data b_data is not a_data. no.
undefined = { b_data } <-- never satisfiable now
END b_data was defined, in db.o, 30 lines of output ago.
The linker is not allowed to look back. ERROR.
And the working order, for contrast:
ORDER: mu.o libMA.a libMB.a
mu.o wants a_fn undefined = { a_fn }
libMA.a ma.o defines a_fn -> take; wants b_data
undefined = { b_data }
da.o defines a_data not b_data. stop.
libMB.a mb.o defines b_fn not b_data. no.
db.o defines b_data YES -> take
undefined = { } done
Notice what the second trace does that the first cannot: the demand for b_data is created insidelibMA.a, and libMB.a has not been passed yet. That is the entire mechanism. A demand can only be satisfied by something to its right.
Now the question the map file answers, which is more interesting than whether the link succeeded — which member was actually read?
$ clang -o prog mu.o -Wl,--start-group libMB.a libMA.a -Wl,--end-group \
-Wl,-Map=prog.map
$ grep -E '^libM[AB]\.a\(' prog.map
libMA.a(ma.o) mu.o (a_fn)
libMB.a(db.o) libMA.a(ma.o) (b_data)
Two members, not three. libMB.a(mb.o) is absent from the map entirely — it defines b_fn, which nothing ever wanted, so it was never read off the archive. da.o is there because it came along inside the same archive as the member that was pulled; archive granularity is per-file, not per-symbol.
This is worth stating as a performance fact, not just a curiosity: an unused archive member costs nothing, not even a read. The index at the front of the archive is what makes that possible, and it is the structure the object-files course measured in .a files. The linker consults a table of names to offsets, decides that mb.o is not in it, and moves on.
The mutual-dependency case is not a toy, because it is what happens when two independently-maintained libraries each grow a dependency on the other. And --start-group exists precisely for it:
$ clang -o prog mu.o -Wl,--start-group libMB.a libMA.a -Wl,--end-group $ ./prog ; echo $? 21 <-- links, in EITHER order
--start-group / --end-group turns the archives inside into a fixed-point region: keep cycling through the group, pulling whatever answers a pending demand, until a whole pass pulls nothing. That is the whole feature, and the next concept is about it properly.
There is a cost, and it is worth knowing when to reach for the flag versus when to fix the build. The group is rescanned until it stabilises, so a group of n archives with heavy interdependency can take several passes, and each pass re-reads the archive indexes. The reflex fix — wrap everything in --start-group — is usually wrong, because it also removes the signal that your libraries have a dependency cycle you should probably break. Build systems that do it by default tend to get slower over time for no visible benefit.
The other real-world case is --as-needed, which is the same algorithm pointed the other way. By default a .so on the command line is recorded as a dependency whether or not it answered anything. --as-needed drops it if it did not, which is why a library can stop appearing in ldd output after you add a flag that has nothing to do with linking libraries. Same demand-driven idea, different question: not “which members do I need” but “which whole libraries did I actually use”.
$ cd courses/sym/assets/samples $ ./build_samples.sh 2>&1 | sed -n '/Finding 6/,/Finding 7/p' $ python3 crosscheck.py 2>&1 | sed -n '/\[4\]/,/^$/p'
Then build the trace yourself. Put the archives in the order that fails, and answer from the algorithm rather than by experiment:
1. libMA.a = (ma.o, da.o), libMB.a = (mb.o, db.o)
ma.o defines a_fn, wants b_data
mb.o defines b_fn, wants a_data
da.o defines a_data
db.o defines b_data
Without running anything: which members are pulled, and in
what order, for each of the four orderings below?
mu.o libMA.a libMB.a
mu.o libMB.a libMA.a
mu.o libMA.a libMB.a libMA.a (listed twice)
mu.o libMB.a libMA.a libMB.a (listed twice)
2. Question 1's third and fourth lines have a duplicate. Why
is the SECOND mention of libMA.a enough to pull da.o in
case 3, when in case 1 it was not pulled at all?
Question 2 is the one that teaches the algorithm. In case 1, by the time the pass reaches the end, nothing is undefined, so a second visit to libMA.a would find no demand. In case 3, the second libMA.a comes afterlibMB.a, and by then da.o may be wanted. The fixpoint is not “try harder” — it is that position in the sequence is what carries meaning.
Order, Archives and the Map File is this concept applied: same algorithm, but the consequences pulled apart — the map file as an observation tool, --start-group as the sanctioned escape, and the cost of reaching for it. Read them in that order and the two lessons are one argument split for length.
Back to the identity module, the algorithm is what gives binding and visibility their teeth. Binding, and the Two Tables established that a LOCAL name is invisible outside its file and a WEAK definition may lose; this concept is where “may lose” becomes the rule that equal candidates are decided by position. Visibility Is Not Binding contributed the candidate set — a LOCAL symbol is not a candidate at all, and a PROTECTED one is a candidate that cannot be beaten later.
Forward, and this is the connection that makes the module matter: every line of this pseudocode is about the static case, and not one of them applies to a shared object. A .so resolves nothing at link time, because the set of libraries that will be loaded is not known until run time. The whole runtime module exists because of that gap. Two Hash Tables, One Job is the data structure the loader uses to answer the same question against the same kind of table; The PLT and the GOT is the mechanism by which it defers the question; Lazy, Eager, and the Flag That Does Nothing is about exactly when the answer is demanded; and Who Owns the Storage is the case where the linker’s answer and the loader’s answer have to be reconciled, and cannot always be.
Finally, the connection to the object files course is mechanical and worth stating because it closes a loop. The Archive measured the .a format — the index, the members, the header — and noted that GNU ld’s resolution is a fixed-point iteration rather than a backwards scan. This concept is that other half: the index is what makes the demand-driven scan cheap, and the fixed point is why the scan can defeat itself when the order is wrong.