The compiler's job ends with an object file — machine code for one source file, riddled with holes. It cannot possibly be finished code: when your main.o calls printf, the compiler has no idea what address printf will live at, because printf is in a different file it never saw. So it leaves a blank where the address goes and writes a note to itself: "fill this in later, once you know where printf ended up." Linking is the phase that reads all those notes across every object file and library, decides the final memory layout, and relocates — patches every blank with a real address — to produce a running executable.

It is the same trick as backpatching, promoted from within one function to across an entire program: emit now, record the hole, fill it when the address is known. Understanding it explains a dozen everyday mysteries — "undefined reference" errors, why a static binary is huge and a dynamic one tiny, what a .so or DLL actually is, and why the same shared library can sit at a different address in every process.

What's in an object file

An object file (ELF on Linux, Mach-O on macOS, COFF/PE on Windows) is more than raw bytes. It carries three things the linker needs:

The linker's two jobs fall straight out of this. Symbol resolution: match every undefined reference to a definition somewhere in the other object files and libraries (fail, and you get the dreaded "undefined reference to printf"). Relocation: now that every symbol has a final address, walk the relocation entries and write those addresses into the holes.

From object files to an executable

Watch the pipeline. Two object files each define some symbols and reference others; the linker lays their sections end to end (assigning real addresses), resolves the cross-references, and patches the holes.

Once main.o's .text is placed at, say, address 0x400000 and util.o's at 0x400080, the linker knows helper lives at 0x400080 and can finally fill the blank in main's call helper. Every hole becomes a number; the result is an executable with no undefined symbols left.

Absolute vs relative relocations

Not all holes are patched the same way, and the difference is the crux of modern code. An absolute relocation writes the symbol's actual address into the hole: \textit{value} = S (plus an addend). Simple — but it bakes a fixed address into the code, so the code only works if loaded at exactly the address the linker assumed.

A relative (PC-relative) relocation instead writes the distance from the patch site to the target: \textit{value} = S + A - P, where S is the symbol's address, A an addend, and P the address of the hole itself. This is the magic ingredient of position-independent code (PIC): if the whole block moves, the site P and the target S move together, so the difference is unchanged and the same bytes work at any load address. That is why a shared library can be mapped wherever the loader likes.

Static vs dynamic linking

The final fork. Static linking copies the machine code of every library function you use into the executable at link time and relocates it there. The binary is self-contained and needs nothing at run time — but it is large, and every program that uses printf carries its own private copy, wasting disk and RAM.

Dynamic linking leaves the library out and records only that the program needs, say, libc.so. The loader maps the shared library into the process at run time and fixes up the references then. One copy of libc in memory is shared by every process — smaller binaries, and a security fix in the library helps everyone at once. The cost is a little start-up work and a layer of indirection, which has two famous names:

The indirection works through two tables. The GOT (Global Offset Table) is an array of pointers, filled in with real addresses at load time; code reaches a global or function through its GOT slot rather than by a baked-in address, so only the small GOT needs fixing up, not the code. The PLT (Procedure Linkage Table) adds lazy binding: the first call to a dynamic function jumps through a PLT stub that asks the loader to resolve the symbol and cache its address in the GOT; every later call flies straight through the now-filled GOT slot. Cheap start-up, one-time cost per function actually used.

Applying relocations, in code

Here is a miniature linker's relocation pass. We place two object files' sections at chosen base addresses, build a symbol table of final addresses, then walk each relocation entry and compute the patch value — absolute or PC-relative.

The helper call gets a small PC-relative displacement (target minus the site minus 4), exactly the encoding an x86-64 call rel32 wants; the logmsg reference gets the full absolute address 0x4000b0. Change a section base and the relative patch adjusts itself while staying correct — the whole point of position independence.