Symbol resolution — order matters — Coding notes

WHAT is symbol resolution?

Two ingredients per object file's symbol table:

Defined symbols (this .o provides them) — the function/global lives here.
Undefined symbols (this .o needs them) — must be supplied by someone else.

The linker's job: make the set of undefined symbols empty by the end.

WHY does order matter? (The algorithm, derived)

The linker maintains three sets as it scans inputs left → right:

$E$ — the set of object files that will end up in the executable.
$U$ — the set of currently undefined symbols.
$D$ — the set of symbols already defined by files in $E$ .

The crucial clause: an archive is searched only against the $U$ that exists when the linker arrives at it. Symbols that become undefined later (because of an object further right) were not in $U$ yet, so the archive — already passed — is never revisited.

Consequence (the rule you memorise):

Put objects first, then libraries; and put a library after every object that uses it. If library A uses library B, write ... A B (the user, then its dependency).

Figure — Symbol resolution — order matters

HOW it plays out — worked examples

Worked example Example 1 — the classic failure

$ gcc main.o -lm        # main.o calls sqrt(); -lm = libm.a

Trace:

Read main.o → $E=\{main\}$ , defines main, references sqrt → $U=\{sqrt\}$ .
Read libm.a → member sqrt.o defines sqrt ∈ $U$ → pull it in. $U=\varnothing$ . ✅

Why this step? sqrt was undefined before we reached libm, so libm got searched for it. Now flip the order:

$ gcc -lm main.o        # WRONG

Read libm.a first → $U=\varnothing$ , so no member is pulled in.
Read main.o → now $U=\{sqrt\}$ — but libm is already behind us. ❌ undefined reference to 'sqrt'.

Worked example Example 2 — circular dependency between two static libs

libfoo.a calls into libbar.a, and libbar.a calls back into libfoo.a.

$ gcc main.o -lfoo -lbar          # may fail

Suppose -lbar pulls in a member that needs a new symbol from libfoo. But libfoo was already scanned → that symbol stays undefined. Fix: repeat libraries or group them:

$ gcc main.o -lfoo -lbar -lfoo               # repeat
$ gcc main.o -Wl,--start-group -lfoo -lbar -Wl,--end-group   # better

Why this step? --start-group/--end-group tells ld to re-scan the enclosed archives repeatedly until no new member is pulled — defeating the one-pass rule on purpose.

Worked example Example 3 — why a needed object got dropped

$ ar rcs libutil.a a.o b.o      # b.o defines log_init()
$ gcc main.o -lutil             # main never references log_init

If main.o never references any symbol in b.o, b.o is not linked in (archives pull in only members that satisfy a current undefined). A __attribute__((constructor)) inside b.o silently won't run! Fix: link b.o directly, or force inclusion: -Wl,--whole-archive -lutil -Wl,--no-whole-archive. Why this step? --whole-archive overrides the "only on demand" rule and includes every member.

Steel-manning the common mistakes

Recall Feynman: explain it to a 12-year-old

Imagine you're packing a school bag by walking down a hallway of lockers once, never turning back. Every time you find a note saying "I need a red pen," you grab a red pen from the next locker that has one. But if you reach a locker full of pens before anyone asked for a pen, you walk right past it — you only grab what someone has already asked for. So if the kid who needs the pen is further down the hallway than the pen locker, he never gets his pen. Lesson: put the askers before the givers.

Flashcards

What direction does the traditional Unix linker scan its command line, and how many times?

Left to right, a single pass (objects/archives processed once; only --start-group or repeating forces re-scan).

What three sets does the linker maintain during resolution?

E

(objects going into the executable),

U

(currently undefined symbols),

D

(symbols already defined).

When is a member of a static archive .a pulled into the link?

Only if, at the moment the linker reaches the archive, that member defines a symbol currently in

U

(undefined).

Why does gcc -lm main.o fail while gcc main.o -lm works?

At -lm first,

U

is empty so sqrt.o isn't pulled; main.o later makes sqrt undefined but libm is already passed. Objects must come before the libraries they use.

General rule for placing libraries on the link line?

Objects first, then libraries; each library after every object/library that depends on it (user before provider).

How do you resolve a circular dependency between two static libraries?

Repeat one library (-lfoo -lbar -lfoo) or wrap them in -Wl,--start-group ... -Wl,--end-group to force repeated scanning.

What does --whole-archive do and why need it?

Forces every member of an archive to be linked, even ones not referenced — needed when a member has side effects (e.g. a constructor) but no referenced symbol.

Strong vs weak symbol rule for multiple definitions?

One strong + several weak → the strong definition is chosen silently; two strong → multiple-definition error. (-fno-common makes tentative globals errors.)

Connections

Static vs Shared Libraries
The Linker (ld) and Linking Phases
Object File Format (ELF) and Symbol Tables
Name Mangling in C++
Build Systems & Toolchain
Library Constructors and __attribute__((constructor))

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab tum gcc se program banate ho, last mein linker chalta hai jo saare symbols (functions, global variables) ko unki definition se jodta hai. Yahan ek important baat hai: purana Unix linker command line ko left se right, sirf ek baar scan karta hai. Woh ek list rakhta hai "abhi tak kaunse symbols undefined hain" — isko hum $U$ bolte hain. Jab bhi koi static library (.a) aati hai, linker uske andar sirf woh members uthata hai jo $U$ ke kisi undefined symbol ko satisfy karte hain. Jo symbol baad mein undefined hoga, uske liye library dobara nahi dekhi jaati.

Isi wajah se order matters. Agar tum gcc -lm main.o likhoge to fail hoga, kyunki jab -lm scan hua tab tak main.o padha hi nahi gaya tha, to sqrt undefined hi nahi tha, library khaali chali gayi. Sahi tareeka hai gcc main.o -lm — pehle object, phir library. Golden rule yaad rakho: user pehle, provider baad mein. Agar libA libB ko use karti hai to -lA -lB likho.

Do special situations: agar do libraries ek dusre ko call karti hain (circular), to --start-group ... --end-group use karo, jo linker ko baar-baar scan karne deta hai. Aur agar kisi library member mein constructor jaisa side-effect hai par koi usko reference nahi karta, to woh silently chhoot jaayega — wahan --whole-archive lagao. Yeh chhoti baat exam aur real debugging dono mein "undefined reference" errors ka 80% reason hoti hai, isliye is rule ko pakka yaad rakho.

Symbol resolution — order matters

WHAT is symbol resolution?

WHY does order matter? (The algorithm, derived)

HOW it plays out — worked examples

Steel-manning the common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Build Systems & Toolchain

Connections