Foundations — Symbol resolution — order matters

This page assumes nothing. Before you can understand why link order matters, you need to know what a symbol is, what "defined" vs "undefined" means, what an object file and an archive are, when two providers clash (weak vs strong), what to do about circular libraries, and what the three sets $E$, $U$, $D$ stand for. We build each one from the ground up, in the order they depend on each other.

1. What is a symbol?

When you write C or C++, you give names to functions and global variables:

int count;              // a global variable named "count"
int square(int x) { ... }   // a function named "square"

The compiler cannot leave these as human words in the final machine code — the CPU only understands numeric addresses. So the compiler keeps a little notebook that maps each name to a location. Each entry in that notebook is a symbol.

Look at the figure: the source code on the left is turned by the compiler into a file on the right (we'll formally call it an object file in §3), and inside that file is a small table with one row per name. We'll formally name that table (the symbol table) in §3 too — for now just picture a two-column list: name and have-it / need-it. That list is the only thing the linker reads; it never re-reads your C code.

2. Defined vs undefined — the two states of a symbol

Every symbol in a file's list is in one of two states:

In the figure, main.o defines main (blue, "I have this") and lists sqrt as undefined (pink, "I need this — someone please provide"). The linker's success condition is simple:

Two failure modes fall straight out of this goal:

• Zero providers for a needed name → undefined reference error.
• Two conflicting providers for the same name → multiple definition error (but §4b explains why sometimes it doesn't error).

3. What is an object file (.o)?

Now we can formally name the file and the table from §1.

The internal layout of a .o (which sections hold code, which hold the symbol table) is the ELF format — see Object File Format (ELF) and Symbol Tables if you want to peek inside. For this topic you only need: an object file always goes into the final program, and it advertises exactly what it has and what it needs.

4. What is an archive / static library (.a)?

Now the piece that makes ordering subtle.

The crucial difference from a plain .o, shown in the figure:

• A plain object is always copied into your program.
• An archive is searched on demand: the linker opens the bag and pulls out only the members that provide a name it is currently missing. Members nobody asked for are left in the bag.

The difference between these .a archives and the .so shared libraries that resolve at load time is covered in Static vs Shared Libraries — the ordering rule bites hardest for the static case.

4a. When two archives need each other — circular dependencies

Because each archive is searched once, on demand, two archives that call into each other can trip the one-pass rule.

Picture libfoo.a and libbar.a: a member of libfoo calls a function in libbar, and a member of libbar calls back into libfoo.

Trace ... -lfoo -lbar:

• Reach libfoo → pull in the member you need. That member adds a new need pointing into libbar.
• Reach libbar → satisfy that need, but the pulled libbar member adds a new need pointing back into libfoo — which the linker has already passed. That name stays unfilled → undefined reference.

Two standard fixes — both tell the linker to stop obeying "once":

4b. When two providers clash — strong vs weak symbols

Section 2 said "two providers → multiple definition." That's only half true. The linker actually classifies each defined symbol by strength and visibility, and those decide whether you get an error, a silent pick, or nothing at all.

Note the subtle tie to ordering: because the first strong wins among strong-vs-weak, which provider is reached first can change which definition you get — so scan order affects not only whether a symbol resolves but sometimes which body you run.

5. The three sets: $E$, $U$, $D$

The parent note tracks the linker's progress with three collections. A "set" here just means "a list of items, no duplicates." Read each symbol out loud with its meaning:

The figure shows these as three boxes. As the linker reads each input left to right:

• reading an object adds it to $E$, moves the names it provides into $D$, and drops any new "needs" into $U$;
• reading an archive pulls out only members that satisfy something currently in $U$.

The symbol $\varnothing$ (an "O" with a slash) means the empty set — "nothing left." The linker succeeds when $U=\varnothing$ at the end, and fails if $U$ still has anything in it.

6. The one command-line idea that ties it together

The linker reads the inputs in the order you type them, once. So main.o -lm and -lm main.o are different programs to the linker, even though the same files are named. That single fact — order is meaning — is the whole topic. Everything in the parent note is a consequence of the building blocks above.

Here -lm is shorthand: -l followed by m tells the tool "find and add the archive named libm.a." The mechanics of how ld expands and searches these are in The Linker (ld) and Linking Phases. And when an archive member must be included even though nobody references it — e.g. it holds a constructor with a side effect — you force it in with --whole-archive.

Prerequisite map

Read this map top to bottom: each arrow means "you must understand the box it leaves before the box it points to." The two middle boxes (object vs archive) both feed the sets $E$, $U$, $D$, which in turn power the single-pass scan — and only then does the parent topic (bottom) make sense. If any box above feels shaky, re-read its section before moving down.

Equipment checklist

Below, each line is a self-test: cover the part after the arrow, answer from memory, then reveal. (In this vault, ::: renders as a hide/reveal flip-card — question on the left, answer on the right.)