Static Archives and Link Order: Why a Library Must Come After Its User

A static library is not a linked object. It is a container of unlinked object files, and the linker chooses among them at link time. That choice is the reason -lfoo must usually appear after the object that uses foo: the linker processes inputs in command-line order, and an archive only offers up members for symbols that are already known to be needed when the archive is reached.

The rule is stated often and understood rarely. It is not an arbitrary convention but a direct consequence of a single-pass algorithm chosen for speed and simplicity. Understanding the pass explains every symptom it produces, including the ones that look like a linker bug.

An archive is a concatenation with an index

The ar format predates ELF and was designed for magnetic tape. A file begins with the eight bytes !<arch>\n, followed by a sequence of members. Each member has a 60-byte header: a 16-byte name, a 12-byte modification time, a 6-byte owner and a 6-byte group, an 8-byte mode, a 10-byte decimal size, and the two bytes `\n. Member data follows the header and is padded to an even offset with a newline if the size is odd.

The 16-byte name field is the reason for the truncated-name problem in old archives and the #1/<len> and GNU long-name conventions that work around it. A modern archive built by GNU ar typically stores the long-name table as a member whose name is //, with each real long name referred to by a /-prefixed decimal offset in a member’s name field. None of this matters to the linker beyond needing to parse it.

What matters is the symbol index. A normal archive contains a special member named /, whose contents map symbol names to the member offset at which their definition lives. The index is a flat table: a 32-bit big-endian count of entries, that many 32-bit offsets, then that many NUL-terminated names. The fields are stored big-endian so that the table has one defined interpretation on disk, independent of the byte order of the machine reading it; an index written in the producer’s native order would force every reader to establish the writer’s machine before it could parse the table.

The index is what makes linking fast. Without it, resolving one symbol against an archive with a thousand members would require reading each member’s symbol table. With it, the linker loads a hash map of names to member offsets and answers each undefined symbol with one lookup. Building the index is the job of ranlib or of ar with the appropriate flag; an archive without one is still linkable, but the linker must scan every member, and many linkers refuse to use such an archive at all.

An important subtlety: the index records only global symbols that are defined by members. Local symbols and undefined references are not indexed, because the index exists to answer “who defines this name”, not “who needs it”. This asymmetry is the root of the ordering rule.

The pass that defines the rule

The traditional Unix linker algorithm is a single left-to-right sweep over the input list. It maintains two sets: a set of defined symbols accumulated so far, and a set of unresolved references.

When the input is a relocatable object, the linker adds all its definitions to the defined set, adds all its undefined symbols to the unresolved set, and — this is the key step — immediately removes from the unresolved set any symbol the object itself defines. It then copies the object’s sections into the output and records its relocations for later patching.

When the input is an archive, the linker does something different: it looks up every currently unresolved symbol in the archive’s index, and for each hit it pulls that member into the link exactly as if it had appeared on the command line at that point. Pulling a member can introduce new undefined symbols, which are then looked up in the same archive again. The process repeats until a pass over the archive produces no new members. Only then does the linker move to the next input.

The consequence is immediate. Suppose main.o calls parse, which lives in libparser.a, and parse calls tokenize, which lives in liblex.a. The command line must be main.o libparser.a liblex.a. When the linker reaches libparser.a, parse is unresolved, so the member defining it is pulled in; that member’s undefined tokenize is added to the unresolved set; the rescan of libparser.a finds nothing more; the linker proceeds to liblex.a, where tokenize resolves. Reverse the two libraries and the linker reaches liblex.a while nothing needs tokenize yet, so it pulls no member, then reaches libparser.a, pulls the member, discovers the tokenize reference, and has no input left to satisfy it. The result is an undefined reference to tokenize, from a program whose libraries both exist and are correct.

Nothing about the code is wrong. The order encodes a dependency, and the linker reads the order as the dependency graph.

Why not iterate until a fixed point

The obvious fix is to repeat the whole input list until no new symbols resolve. Some linkers do exactly this internally for archives, and the cost is bounded but real: each iteration re-reads the index and re-checks unresolved symbols, so a chain of n libraries in the wrong order costs O(n²) index probes. The single pass costs O(n), and the designers of the original toolchain considered the ordering requirement a reasonable price for that.

There is also a semantic argument. A repeated pass makes the link order-insensitive in a way that hides genuine circular dependencies between libraries, which are usually a sign that the code should be reorganised. The single pass surfaces the cycle at link time instead of silently satisfying it.

The practical tools for the cases where ordering cannot be expressed are explicit. Wrapping a library in --start-group and --end-group tells the linker to iterate over the enclosed archives until no progress is made, which is the standard remedy for mutually dependent static libraries. Wrapping a single library in --whole-archive pulls in every member regardless of whether it is needed, which is required when a library registers itself through constructors and nothing references its symbols by name. Repeating a library name later on the command line is the crudest way to satisfy a back-reference: the archive is searched again at the point where it reappears, by which time the reference it has to satisfy is known.

# Fails: liblex is searched before anything needs tokenize.
cc -o prog main.o liblex.a libparser.a

# Succeeds: each archive is searched when its symbols are already needed.
cc -o prog main.o libparser.a liblex.a

# For cyclic dependencies, iterate over the group until stable.
cc -o prog main.o -Wl,--start-group libparser.a liblex.a -Wl,--end-group

# Pull every member, needed or not, so constructor registration runs.
cc -o prog main.o -Wl,--whole-archive libregistry.a -Wl,--no-whole-archive

--whole-archive has a cost beyond size. If two archives both contain a member defining the same global symbol, pulling both in produces a duplicate-definition error that would not occur with selective extraction. The flag also defeats the archive’s main size advantage: a large library included wholly contributes all its code to the binary even if one function is called.

The other ordering rule: objects before libraries

A related rule concerns where individual object files sit. Definitions from an object on the command line are available to every archive that follows, because the object is processed when it is encountered. An object that appears after all libraries cannot contribute definitions to them; its references can still be satisfied by symbols already pulled in, but its own definitions are added too late to trigger extraction.

This produces the familiar failure of a command line where the main program object is placed last, which some build systems generate when they append objects to a link line built from library flags. The symptom is a set of undefined references to symbols that are demonstrably defined in the objects listed. Moving the objects to the front resolves it.

Shared objects behave differently, and the difference is instructive. A shared object is not searched member by member; it is either used or not, and its whole symbol table is available for resolution at the point where the linker processes it. On most systems the dynamic linker resolves lazily or at load time against the full set of loaded objects, so link order among shared libraries rarely produces undefined-reference failures. The ordering rule is a property of the archive extraction algorithm, not of linking in general — a distinction taken up again in Symbol Versioning and SONAME.

Failure modes beyond ordering

Weak symbols interact badly with archive extraction in a way that surprises people. If an archive member defines a weak symbol and another object defines a strong one, the strong definition wins and the member need not be pulled in. But if the member is pulled in for an unrelated symbol, its weak definition joins the link and may then be overridden or may override, depending on the linker’s rules for weak versus strong at that point. A weak definition in an archive is therefore not a reliable way to provide a fallback: whether it participates depends on whether some other symbol caused the member to be extracted.

The index itself can be stale. If a member is replaced or added without rebuilding the index, the linker’s lookup misses a definition that is physically present, producing an undefined reference that manual inspection contradicts. ar warns about this when it can detect it, and the fix is to rebuild the index. Archives copied between systems with tools that do not preserve the special members lose the index entirely.

Duplicate definitions across archives are silent in one direction and fatal in the other. If two archives define the same symbol, the first one searched wins and the second member is never extracted, so no error is reported; the program links against whichever definition happened to come first. If the same symbol is defined in two ordinary objects, the linker reports a multiple-definition error. The asymmetry means that a symbol collision between libraries can be invisible until a change in link order or an added reference alters which member is extracted.

Finally, the SHN_COMMON legacy interacts with archives: a common symbol in an object can be satisfied by a definition pulled from an archive, and the linker must decide which size wins. Modern toolchains avoid this by defaulting to non-common definitions, as described in Sections, Symbols, and Relocations in an ELF Object File, which converts the ambiguity into a duplicate-symbol diagnostic.

What the format cannot express

The archive format has no notion of a dependency between members. There is no field saying that the member defining parse requires the member defining tokenize, and no field naming another archive. All dependency information lives outside the file, in the order the user writes on the command line or in a build system’s declared edges. A linker cannot recover it, because the information was never recorded.

That is the design constraint the format accepted: the archive is a bag of object files with a lookup table, minimal and cheap to build, and the dependency graph is the caller’s problem. Build systems that model dependencies explicitly — resolving a topological order over libraries before emitting the link line — are compensating for this, and the compensation is where most of the complexity in static linking actually lives. The link editor itself remains a single pass, which is what makes it fast enough to be unremarkable.