Linkingtarget

What a Linker Does

Object files and libraries in, one runnable image out. Four jobs: combine sections, resolve symbols, lay out an address space, and patch every reference that could not be resolved until the layout existed.

The question

What happens between my .o files and an executable I can actually run?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A set of relocatable object files: machine code and data, cut into named sections, with a symbol table naming what each file defines and what it still needs, and a relocation list saying which bytes must be patched once addresses are known. That representation exists because the compiler compiles one translation unit at a time and therefore cannot know where anything will end up — so it emits placeholders plus instructions for fixing them.

What this phase may assume or do

The linker may place sections at any addresses that satisfy their alignment requirements, the target's address-space constraints and any explicit layout script, and it may discard a section only if nothing reachable references it. It may resolve an undefined symbol to any definition permitted by the resolution rules — one strong definition, or a weak one if no strong one exists — and it must fail rather than guess when a reference has no definition or several strong ones. What it may never do is change the semantics of the code it is patching: a relocation specifies exactly which bytes are overwritten and by what function of the target address, and the linker computes that function, nothing more.

Key points

  • The linker does four things: combine sections, resolve symbols, lay out the address space, apply relocations — and the order is forced by dependencies between them.
  • Layout is the first moment in the entire pipeline at which any address is known; everything before it is relative offsets.
  • The compiler leaves relocation records precisely because it compiles one translation unit and cannot know where anything else will be.
  • The output is organised into segments with permissions, not sections, because that is what the loader maps.
  • The entry point is not main: it is the C runtime's _start, which calls main after setup.
  • Linking is serial and whole-program, which is why it is the bottleneck at the end of an otherwise parallel build.

Four jobs

A linker is often described as "combining object files", which is the least interesting of the things it does. The work divides into four distinct jobs, and each of them exists because of something the compiler could not do.

It combines sections: every input contributes some .text, some .data, some .rodata, and the linker concatenates all the .text from all the inputs into one output .text, and so on. It resolves symbols: every undefined reference in every input must be matched to exactly one definition, drawn from the other inputs or from libraries. It lays out the address space: it assigns a final address to every section, which is the first moment in the entire pipeline that any address is known. And it applies relocations: now that addresses exist, it walks the relocation lists and patches the placeholder bytes.

The ordering is forced. You cannot patch addresses before layout, you cannot lay out before you know which sections are included, and you cannot know that before symbol resolution has decided which archive members to pull in. That dependency chain is why a linker is a distinct program with distinct phases, and it is why link time is a serial bottleneck at the end of a build that was otherwise embarrassingly parallel.

A link, as a sequence of representationstypical
  1. Object filesbuild time
    Per-translation-unit sections, symbol tables and relocation lists. All addresses are placeholders relative to section starts.
    Nothing yet — this is the input.
  2. Resolved symbol tablebuild time
    One global map from symbol name to the input section and offset that defines it.
    A decision about which definition each reference means, and which archive members are needed at all.
    Nothing yet, but this is where an unresolved reference becomes a hard error.
  3. Laid-out imagebuild time
    Output sections grouped into segments, each assigned a final virtual address.
    Addresses. This is the first point in the entire pipeline where any address exists.
    The identity of the input files — from here it is one address space.
  4. Relocated imagebuild time
    The same bytes with every placeholder patched to a real address or offset.
    Working references between translation units.
    The relocation records themselves, in a fully static link; a dynamic executable keeps the ones the loader must still apply.
  5. Executable or shared objectbuild time
    A file with a program header telling the OS what to map where, plus an entry point.
    Everything the loader needs and nothing it does not.
  6. Process imageload time
    Mapped memory with libraries bound and the entry point about to run.
    Real addresses in a real address space, and the resolution of anything left dynamic.

Read it asThe third row is the pivot. Everything before it is bookkeeping over relative offsets; everything after it is about real addresses. That is also why [[relocations]] exist at all — they are the record the compiler leaves behind saying "I could not do this, do it when you get to row three".

Why the compiler could not have done it

targetThe relocation type names and the encoding are x86-64 ELF. AArch64 ELF uses R_AARCH64_CALL26 for the same job with a 26-bit encoded offset and a correspondingly smaller reach; Mach-O uses its own relocation records with a different structure; PE/COFF uses yet another. The concept — a record naming a location, a symbol and an arithmetic form — is universal, and no specific name or encoding is.

The compiler processes one translation unit. When it compiles a call to printf, it knows nothing about where printf will be: not its address, not whether it comes from an archive or a shared library, not even whether it exists. So it emits a call instruction with a zero displacement and a relocation record saying "the four bytes at offset 0x1a are a PC-relative reference to the symbol printf; fix them when you know".

This is not a limitation to be engineered away — it is the whole point of [[separate-compilation]]. If the compiler needed to know every final address, changing one line would require recompiling the program, and the build would be proportional to the codebase rather than to the change. The cost of that property is that somebody has to do the address arithmetic later, and the linker is that somebody.

It also explains the linker's peculiar position in the toolchain: it is the first component to see the whole program, and the last to see it at a level where the source is entirely gone. That combination is what makes [[link-time-optimization]] both possible and awkward — possible because the whole program is finally visible, awkward because by then it is machine code, which is why LTO works by keeping IR in the object files rather than by optimizing the machine code.

One call, before and after linking (x86-64 ELF)
1# In main.o:  objdump -dr main.o
2  10:  e8 00 00 00 00     call  15 <main+0x15>
3                          11: R_X86_64_PLT32   printf-0x4
4        ^^^^^^^^^^^ placeholder: four zero bytes plus a relocation record
5 
6# In the linked executable:  objdump -d app
7  1139: e8 f2 fe ff ff     call  1030 <printf@plt>
8        ^^^^^^^^^^^ patched: the displacement from here to the PLT entry

The R_X86_64_PLT32 line is not disassembly — it is the relocation record objdump -r prints alongside. Read it as an instruction to the linker: take the address of printf, subtract the address of this field, subtract four to account for the instruction length, and store the result as a 32-bit signed displacement. The linker is executing a small, fixed arithmetic program per record.

What comes out, and what is thrown away

A linker also deletes. Sections that nothing references can be discarded if the inputs were compiled to allow it — -ffunction-sections -fdata-sections puts every function and object in its own section, and --gc-sections then removes the unreferenced ones. Identical code folding merges functions with byte-identical bodies. Debug sections can be stripped, split into a separate file, or kept.

The output is not simply "the inputs concatenated". It is an image with a program header describing segments — regions the OS should map, with permissions — rather than sections, because the loader thinks in mappable, permission-bearing regions and the linker thinks in named collections of similar content. Grouping many sections into few segments is what allows .text and .rodata to share a read-only mapping and .data and .bss to share a writable one.

And it emits an entry point, which is not main. On a typical Unix system the entry is _start, supplied by the C runtime startup object, and main is called from there after the runtime has set up the stack, the environment and the static initializers. That is [[the-loader]]'s subject, and it is the reason a program can misbehave before any line you wrote has executed.

  • Combine: concatenate like-named sections from every input into one output section each.
  • Resolve: match every undefined symbol to exactly one definition, pulling archive members in as needed.
  • Lay out: assign final addresses to sections and group them into loadable segments with permissions.
  • Relocate: patch every recorded location using the now-known addresses.
  • Prune: discard unreferenced sections, fold identical functions, strip or split debug information.
  • Emit: write the program header, the entry point, and — for a dynamic executable — the tables the loader will need.

How it works

The steps, in the order the compiler takes them.

  • Read every input object and archive, building a table of the symbols each defines and each requires.
  • Resolve: for each undefined symbol, find a definition among the objects already included, or pull in an archive member that provides it — which may itself introduce new undefined symbols, so this iterates.
  • Decide the final set of input sections, discarding unreferenced ones if garbage collection is enabled.
  • Merge input sections into output sections by name and attributes, and group output sections into loadable segments by required permissions.
  • Assign a virtual address to every segment and hence to every section and every symbol within it.
  • Walk each relocation record, compute the value its type specifies from the now-known addresses, and patch the target bytes.
  • Write the program headers, the entry point, and — for dynamically linked output — the dynamic symbol table, the relocation entries the loader must still apply, and the list of needed libraries.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A build fails with undefined reference to 'foo' naming a function that is visibly defined in a file you compiled — because that object was not on the command line, or an archive containing it came before the object that needed it.
  • A build fails with multiple definition of 'x' after a variable was defined rather than declared in a header, and every translation unit that includes it contributed a definition.
  • The link succeeds and the binary is enormous, because debug sections were kept and nothing was garbage-collected — a routine surprise for anyone comparing a debug build's size to a release build's.
  • A link that used to take seconds takes minutes after LTO is enabled, because code generation for the whole program has moved into the link step and it is single-threaded by default.
  • The program links and immediately faults before main, because a static initializer ran and the runtime was not in the state it expected.
  • A symbol resolves to the wrong definition — a stale object file from a previous build, or a library shadowing a local implementation — and the program runs the wrong code with no diagnostic at all.

When it helps

  • Reading link errors as a mechanism rather than a mystery: knowing that resolution is a search with an order explains most of them immediately.
  • Reducing binary size, where knowing that the linker can garbage-collect sections and fold identical functions turns "the binary is too big" into three specific flags.
  • Debugging "why is this code even in my binary": the linker included it because something referenced it, and --print-gc-sections or a map file will say what.

When it hurts

  • Treating the linker as a place to fix design problems. Symbol interposition and link order can make a wrong program work, and both are fragile ways to express something a build dependency should have expressed.
  • Assuming the link is cheap. Whole-program work — LTO, identical code folding, large debug sections — concentrates at exactly the point where nothing else can proceed in parallel.

What it costs

Every one of these is paid by something.

  • Separate compilation plus a linker buys rebuilds proportional to the change rather than to the codebase, and costs a whole-program serial step at the end plus the loss of cross-unit optimization unless LTO is bought back at further link-time cost.
  • Section garbage collection buys smaller binaries and costs compile-time granularity — every function in its own section makes object files larger and gives the linker more work — plus surprising removals when a symbol is referenced only from assembly or a linker script.
  • Identical code folding buys size and costs the property that two distinct functions have distinct addresses, which breaks code that compares function pointers for identity.
  • Keeping debug information buys the ability to diagnose the shipped binary and costs binary size and link time; splitting it into separate files buys both back and costs an artifact that must be archived and retrieved to be useful — see [[symbolication]].

What else you could do

What a different compiler or language does instead, and when that is better.

  • No separate linker: a whole-program compiler that reads all sources at once and emits a finished binary. Simpler, and it makes every build a full build, which is why it survives only in small languages and single-file toolchains.
  • Dynamic linking, which defers most of this work to load time so libraries can be shared and updated independently — the same four jobs, done later and partly by the loader. See [[dynamic-linking]].
  • A modern parallel linker — LLD, Mold — which keeps the same model and attacks the serial bottleneck with parallelism and better data structures, often by an order of magnitude over traditional BFD ld.
  • Runtime linking by a virtual machine: the JVM and .NET resolve references lazily by name at first use, with no separate link step at all, buying flexibility and paying with per-reference resolution machinery in the runtime.

See it for yourself

The flag, dump or tool that shows you this directly.

  • See the inputs: objdump -h file.o lists sections with sizes and alignments; objdump -dr file.o disassembles with relocation records interleaved, which is the single most instructive view in this module.
  • See the decisions: pass -Wl,-Map=app.map to get a link map naming every input section, its final address, and why each archive member was pulled in.
  • See what was discarded: -Wl,--print-gc-sections reports every section garbage collection removed.
  • See the output structure: readelf -lW app prints the program headers — the segments the loader will map and with what permissions.
  • See how long it takes: -Wl,--stats on LLD, or simply time the link separately, which is usually enough to show that it is the serial tail of the build.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "The linker just concatenates object files." It resolves a global name-matching problem, assigns every address in the program, and rewrites bytes throughout every input. Concatenation is the easy quarter of it.
  • "If it links, it works." Linking checks that every name has exactly one definition. It checks nothing about types, layouts or conventions — see [[abi]].
  • "The entry point is main." The entry point is _start from the C runtime, and a good deal runs before main is called.
  • "Link errors mean a missing library." They mean no definition was found for a name, which can equally be a missing definition, a hidden symbol, a mangling mismatch or a bad link order.

Misconceptions

The claim, and what is actually true.

The compiler produces the executable and the linker just packages it.
The compiler cannot produce an executable, because it never knows an address. Every inter-unit reference in every object file is a placeholder until the linker patches it.
Linking is fast because it is just I/O.
It is a whole-program symbol resolution plus a full rewrite of every relocated byte, and with LTO it also includes code generation for the entire program.
The linker understands the program.
It understands names, sections and relocation arithmetic. It has no notion of types, calling conventions or object layouts, which is why ABI mismatches pass through it silently.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Each source file is compiled on its own, so it cannot know where anything in the other files will end up. The linker takes all those pieces, decides on one address for everything, matches every reference to exactly one definition, and then goes back through and fills in all the blanks the compiler left. What comes out is a file the operating system knows how to load.

practical

Ask a link map for anything you do not understand: -Wl,-Map=app.map tells you what was included, from where, at what address and why. For undefined references, check in order — is the object on the command line, is the archive after the object that needs it, is the symbol exported, and does the name shape match what the caller expected. For size, --gc-sections with -ffunction-sections plus stripping debug info is usually most of the win.

advanced

The interesting structural property is that the linker is the only whole-program component in a pipeline designed around not having one. Every design pressure on modern toolchains pushes against that: LTO puts IR in object files so the middle-end can run at link time, incremental linking tries to avoid redoing the whole image, and parallel linkers attack the serial tail directly. Mold's central insight is that most of a link is embarrassingly parallel once the symbol resolution is done, and that traditional linkers were structured around a memory-constrained, single-threaded era. The residual serial dependency — you cannot patch until you have laid out, and you cannot lay out until you have resolved — is genuinely irreducible, and it is why link time has a floor that build parallelism cannot lower.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

targetSection names, relocation types and the segment model described here are ELF, as used on Linux and most Unix-likes. Mach-O on Apple platforms uses segments containing sections with different names (__TEXT,__text), and PE/COFF on Windows uses yet another structure with an import table rather than ELF-style dynamic relocations. The four jobs are the same everywhere; every identifier here is not.
typicalThat the entry point is _start and that it calls main after runtime setup is typical of C and C++ toolchains on Unix-likes. Freestanding and embedded builds often define their own entry with -nostartfiles, Go supplies its own runtime entry, and a shared library has an initialization mechanism rather than an entry point at all.
implementationSection garbage collection, identical code folding and parallel linking are features of specific linkers: GNU ld, gold, LLD and Mold differ in which they support, how they default and how fast they are. A statement about "the linker" is a statement about the one your driver invokes, which -fuse-ld= selects.

If you were asked this in an interview

  • Name the four things a linker does and say why they must happen in that order.
  • Why can the compiler not resolve a call to a function in another translation unit?
  • You get undefined reference to 'foo' and foo is definitely defined in a file you compiled. Name three reasons.

Connections

Computer Architectureaddressing-modesassembly-fundamentals
OS & Networkingprogram-vs-processprocess-memory-layoutfiles-and-paths
Domains that do not exist yet
  • DevOps / Production Engineering — Build graphs and where the serial tail of a build actually is
    Compilation parallelises across translation units and linking does not, so link time sets a floor on incremental build latency that adding machines cannot lower. Deciding how to structure a build around that is owned there.