Relocations and Symbol Resolution

Two jobs hiding inside one word: "linking"

From the last guide you know an object file is not a runnable program. It is a half-finished thing: machine code with holes in it, plus a symbol table that lists which names this file provides and which names it still needs. The job of the linker is to take a pile of these half-finished files, snap them together, fill the holes, and hand back something whole. That single job actually splits cleanly into two phases, and keeping them separate in your head is the key to everything that follows.

The first phase is symbol resolution: for every name a file uses but does not define, find the file that does define it, and pair them up. The second phase is relocation: now that every function and variable has been assigned a final address, go back through the code and patch in those addresses everywhere they were referenced. Resolution answers "which printf do you mean?" Relocation answers "and where did printf end up, so I can write that number into the call instruction?" One is about identity; the other is about location.

Symbol resolution: matching every name to exactly one home

Recall the defined-versus-undefined split from guide 1. Inside each object file, the symbol table marks every symbol as either defined here (this file contains the code or data for it) or undefined (this file uses the name but expects someone else to supply it). When you write a call to printf() in main.c but never write printf yourself, your main.o ends up with an undefined symbol named printf — a labelled hole that says "fill me in with whatever printf turns out to be."

Resolution is the linker scanning every input file, building one giant table of all defined symbols, and then walking each undefined reference until it finds the matching definition. The hard cases are not the matches but the conflicts. What if two files both define a global named init? The linker would not know which one you meant, so by default it refuses — that is the "multiple definition" error, the mirror image of "undefined reference." The rule is meant to be strict: exactly one definition per name, no more and no fewer.

But there is a deliberate escape hatch, and it is genuinely useful: the weak symbol. A normal definition is strong; a weak definition says "use me only if nobody stronger shows up." When the linker sees one strong and one weak definition of the same name, it silently takes the strong one and discards the weak — no error. When it sees several weak definitions and no strong one, it just picks one. This is how a library can ship a default implementation of, say, a malloc() hook that your program is free to override simply by defining a strong version. It is powerful, but be honest about the risk: two strong C definitions of the same name is a real bug, while two weak ones quietly picking one can hide a real bug, so do not lean on weakness to paper over a naming collision you did not intend.

Why relocation has to exist at all

Now the second phase. To see why it is unavoidable, put yourself in the compiler's shoes when it turns main.c into main.o. It is compiling main.c alone, with no idea what other files exist or where any of them will sit in the final program. When it hits a call to a function in another file, it genuinely cannot write the target address — that address does not exist yet, because nothing has been laid out. So the compiler does the only honest thing: it leaves the address field blank (often literally zeros) and attaches a note saying "once you know where this symbol lives, come back and fill in this exact spot."

That note is a relocation entry. Each one is a small record that names three things: where the hole is (an offset into a section), which symbol's address should go there, and how to compute the value to write — because not every reference wants the same number. A relocation entry is, in effect, a to-do item the compiler hands forward to the linker: "patch is pending; here are the instructions." An object file carries a whole list of them, one per unresolved address baked into its code or data.

The "how to compute" part is the subtle one, and it is worth one concrete example. Some references want the symbol's absolute address — the full final number where it lives. Others want a relative one: the call instruction on x86-64 does not store the target's absolute address, it stores the signed distance from the next instruction to the target. So the relocation for a call computes (address of symbol) minus (address right after the patched field), and writes that difference. Same symbol, same hole almost, but a completely different number depending on the relocation type. This is exactly why the entry must carry a type, not just a target.

Walking one relocation by hand

Let us patch one hole step by step, so the mechanism stops being abstract. Imagine main.o contains a call to a function foo defined in foo.o. In main.o the call instruction has a blank 4-byte field where the relative offset belongs, and a relocation entry pointing at it. Here is the whole dance, from "address unknown" to a finished, runnable instruction.

1. Resolve first: the linker matches main.o's undefined symbol foo to the defined foo in foo.o. Now they are paired; foo has one home.
2. Lay out the program: the linker assigns final addresses. Say foo lands at 0x401130, and the 4-byte hole inside main's call instruction lands at 0x401152 (so the byte right after the hole is at 0x401156).
3. Read the relocation type: this entry is a PC-relative call, so the value to write is (target) minus (address just past the field): 0x401130 minus 0x401156.
4. Compute the offset: 0x401130 - 0x401156 = -0x26, i.e. the signed 32-bit value 0xffffffda. The call jumps backward 0x26 bytes from where it would otherwise continue.
5. Patch and discard: the linker writes 0xffffffda into the 4 bytes at 0x401152, then drops the relocation entry — the to-do item is done. The instruction now jumps to exactly foo, no matter where foo ended up.

main.o BEFORE linking          relocation entry
-----------------------        ---------------------------------
... e8 00 00 00 00 ...          offset = 0x.. (the 4-byte field)
      ^^^^^^^^^^^                symbol = foo
      blank: "fill me"           type   = R_X86_64_PC32  (PC-relative)

linker lays things out:        foo -> 0x401130
                               field -> 0x401152, next byte -> 0x401156

value = 0x401130 - 0x401156 = -0x26 = 0xffffffda

main  AFTER linking
-----------------------
... e8 da ff ff ff ...          // call foo, encoded as a backward jump

When relocation can't finish at link time

Everything so far assumed the linker knows the final address — and for a classic statically linked executable, it does. But two real situations break that assumption, and they are exactly what the next two guides are about. First, with a shared library, the code is loaded at an address chosen at run time, possibly different on every launch, so the loader must finish some relocations the static linker could not. Second, position-independent code is deliberately written so that most references need no run-time patching at all — it reaches data and functions through indirection instead of baked-in absolute addresses.

So relocation is not a single moment; it is a spectrum of when. Some relocations are resolved entirely at link time and burned permanently into the executable. Others are deferred and carried as relocation entries inside the final file, to be applied by the dynamic loader the instant the program starts. Still others are routed through small tables so the address only has to be written once in one place rather than patched at every call site. The same core idea — a hole, a target, and a rule for filling it — stretches across all of them; only the who and the when change.