How Linkers Resolve Symbols and Relocations
A linker combines compiled object files, matches names such as functions and global variables to their definitions, and fixes machine-code references so the final program can run. A relocation is the record that tells the linker or loader how to patch one of those references when its final address becomes known.
The problem: addresses are not known yet
A compiler translates each source file separately. While compiling app.c, it may know that the program calls parse_request, but it usually does not know which object file will define that function, where the function will live in the final executable, or where the operating system will load the executable in memory.
Without a linker, every compiler invocation would need the entire program and a fixed memory layout. Adding a source file or library could change addresses throughout the program, requiring every file to be recompiled. Separate compilation would be impractical.
Instead, the compiler emits an object file: machine code and data packaged with metadata. An object file contains sections such as code, read-only data, writable data, a symbol table listing names and their locations, and relocation records for references that are not yet complete.
For example:
extern int request_count;
int current_count(void) {
return request_count;
}
The compiler can generate the instructions for current_count, but it cannot put the final address of request_count into those instructions. It emits a placeholder and a relocation saying, in effect, “at this location, insert the address or offset of the symbol request_count using the appropriate machine-code format.”
Resolving symbols
A symbol is a named entity that can be referenced across compilation units: commonly a function or global variable. A definition gives a symbol a location; a declaration says that a definition exists elsewhere. In the example, request_count is undefined in this object file but may be defined in another one.
The linker reads all input object files and libraries, then builds one combined view of their symbols. It performs tasks such as:
- Matching each undefined reference with a definition.
- Rejecting missing definitions, often with an “undefined reference” error.
- Rejecting conflicting strong definitions, such as two ordinary definitions of the same function.
- Choosing which members of a static library are needed to satisfy unresolved references.
- Assigning final locations to code and data sections.
A static library is an archive of object files copied into the executable at link time. A shared library is a separately loadable binary whose code and data can be used by multiple processes; it is usually connected to the program partly at run time.
Once the linker knows that request_count is, for example, 128 bytes into the executable's data area, it can resolve the name. It still must apply the relocation: write the right value into the right bytes in the generated machine code or data.
Applying a relocation
A relocation record normally identifies three things:
- Where to patch, such as an offset inside a code section.
- Which symbol supplies the value.
- What calculation to perform, because instruction encodings differ.
A relocation might request the symbol's absolute address, its address relative to the instruction pointer, or a value adjusted by an addend. An addend is a constant included in the relocation calculation, such as a field offset or the displacement encoded by an instruction.
For an absolute reference, the conceptual calculation is:
value written at patch location = address(symbol) + addend
For a position-relative branch, it is more like:
value written = address(symbol) + addend - address(next instruction)
The exact relocation names and encoding rules are architecture- and object-format-specific. ELF on Linux, for example, has relocation types for x86-64 and for other processors, and each type specifies how bits in an instruction are interpreted.
The linker also lays out sections and may rewrite or relax instructions when the target is close enough for a shorter encoding. The important boundary is that the compiler produced a reference with missing address information; the linker fills that information using the machine architecture's rules.
Why position-independent code changes the job
Traditional code can contain absolute addresses: “load from address 0x....” That works if the executable is always loaded at the address assumed during linking. It does not work when the operating system chooses a different address, as it commonly does for ASLR (address-space layout randomization), a security feature that varies memory locations between runs.
Position-independent code (PIC) is machine code designed to work at different load addresses without rewriting every absolute reference. It favors values that are relative to the current instruction or uses indirection through tables whose locations can be adjusted once.
For example, on x86-64, a compiler can address nearby data relative to the instruction pointer. If both instruction and data move together, their difference remains valid. A shared library can therefore be mapped at an arbitrary base address without changing all of its code.
PIC cannot make every reference purely relative. A library may need to access a global symbol supplied by the main program or another library. It commonly uses a global offset table (GOT): a table of addresses, with code loading the address from the table rather than embedding it directly. The dynamic linker fills the relevant GOT entries after loading.
External function calls often use a procedure linkage table (PLT) as well. The PLT is a set of small call stubs. A first call can pass through a stub that asks the dynamic linker to find the function and record its address in the GOT; later calls can jump through the now-filled entry. This is called lazy binding. Systems can also resolve such functions at load time instead.
Shared libraries and the dynamic linker
A normal static link can finish all symbol resolution and relocations before the program starts. Shared libraries require another stage because their final addresses, and sometimes their symbol providers, are unknown until load time.
The executable and each shared library carry dynamic symbol and relocation information. When the program starts, the dynamic linker (also called the runtime loader) maps the required libraries into memory, chooses their load addresses, resolves dynamic symbols according to the platform's lookup rules, and applies the remaining relocations. It may patch GOT entries, adjust library data containing addresses, and connect PLT calls.
This is why a shared library must be built with compatible relocation handling. A relocation that writes an absolute address into a library's code would have to be redone whenever the library is loaded at a new address, making the code page writable and increasing startup work. Such text relocations are undesirable because code pages are normally shared and read-only. PIC keeps most relocations in writable data, especially the GOT, while leaving the code itself shareable.
Errors such as “undefined symbol,” “relocation truncated,” “cannot allocate memory in static TLS block,” or loader messages about text relocations are therefore clues about different stages: symbol matching, instruction-size limits, thread-local storage, or run-time relocation policy. The same basic mechanism explains them all: a name must be found, and a machine-level reference must be encoded for where the referenced object will actually live.