Linking and relocation

Deep dive

How it works

Parts:

• Object file — sections, symbol table, relocation records.
• Symbol table — global name to definition (strong, weak, COMDAT).
• Layout — input sections merged into output sections and segments.
• Relocation record — r_offset, r_info (symbol, type), r_addend.
• GOT/PLT — loader-filled address table and call stubs for dynamic symbols.

1. Read inputs. Each object has sections (.text, .data, .rodata, .bss, ...), a symbol table and relocation sections. See ELF/PE formats.
2. Resolve symbols. One global table: defined strong wins over weak; two strong definitions fail; an undefined weak resolves to 0. COMDAT (ELF section groups) lets many objects carry the same inline function or template instance; the first group with a signature is kept, the others are discarded. Archives: GNU-style linkers scan an archive in command-line order and extract a member only when it defines a currently undefined symbol, so order matters (or --start-group); an extracted member can introduce new undefined symbols, so extraction repeats until stable.
3. Garbage-collect. With -ffunction-sections --gc-sections, sections unreachable from the entry (and other roots) through relocations are dropped; ICF merges identical ones.
4. Lay out. Merge input sections of equal name and flags into output sections, align them, then group by permission into segments (PT_LOAD: R-X text, R-- rodata, RW- data) at page boundaries. Section = linker view, segment = loader view.
5. Relocate. ELF x86-64/AArch64 use Rela records: r_offset (where, a section offset in objects), r_info (symbol index in the high 32 bits, type in the low 32), r_addend (A). Values: S symbol address, P address of the patched place, A addend.
   • R_X86_64_64: S+A, 8 bytes absolute.
   • R_X86_64_PC32, R_X86_64_PLT32: S+A-P, signed 32 bits. For a call rel32 the addend is -4, since rip is 4 bytes past the field. PLT32 means "through a PLT if S is not local"; compilers emit it for calls, so the linker can bind it directly.
   • R_X86_64_GOTPCRELX/REX_GOTPCRELX: GOT slot address -P; if the symbol is local the linker may relax the load to lea.
   • R_AARCH64_CALL26: (S+A-P)>>2 into imm26 of bl, range +-128 MiB; farther calls go through a linker-made thunk.
   • R_AARCH64_ADR_PREL_PG_HI21 + ADD_ABS_LO12_NC: adrp gets Page(S+A)-Page(P) (4 KiB pages, imm21), the add/ldr gets the low 12 bits.
6. Dynamic linking. Shared objects are not copied in; the output records DT_NEEDED and dynamic relocations. Code reaches external data via the GOT (R_*_GLOB_DAT); external calls via PLT stubs jumping through .got.plt. Lazy binding: the slot first points back into the stub, the first call enters the resolver (R_*_JUMP_SLOT) which patches the slot. -z now (BIND_NOW) resolves everything at load; with full RELRO the GOT is made read-only afterwards, so it cannot be overwritten.
7. PIC/PIE. Position-independent code uses PC-relative addressing and the GOT, so one copy maps anywhere; a PIE executable is loaded at a random base (ASLR). Absolute pointers in data (vtables, function-pointer tables) get R_*_RELATIVE (base + A) fixups at load; -z pack-relative-relocs (RELR) stores them compactly.
8. LTO. The compiler leaves IR in the object; the linker plugin hands all IR to the optimizer so inlining and dead code removal cross file boundaries, then final machine code is linked normally.

a.o  b.o  libx.a ─► resolve ─► GC/ICF ─► layout ─► relocate ─► a.out
 sections+syms      (names)    (drop)   (addresses) (patch S+A-P)
                                  PIE/shared: GOT, PLT, RELATIVE fixups ─► loader

Code

A toy linker over byte buffers: lays out code then data, resolves strong/weak symbols, applies absolute and PC-relative relocations.

use std::collections::HashMap;

#[derive(Clone, Copy)]
enum Kind { Abs64, Pc32 } // R_X86_64_64, R_X86_64_PC32

struct Sym { name: &'static str, sect: Option<usize>, value: u64, weak: bool }
struct Reloc { sect: usize, offset: usize, sym: usize, kind: Kind, addend: i64 }
struct Obj { sects: Vec<(Vec<u8>, bool)>, syms: Vec<Sym>, relocs: Vec<Reloc> } // bool: writable

fn link(objs: &[Obj], base: u64) -> Result<(Vec<u8>, HashMap<&'static str, u64>), String> {
    // 1. layout: code first (16-aligned), then data on a new 4 KiB page
    let mut addr: Vec<Vec<u64>> = objs.iter().map(|o| vec![0; o.sects.len()]).collect();
    let mut cur = base;
    for pass_data in [false, true] {
        if pass_data { cur = (cur + 0xfff) & !0xfff; }
        for (i, o) in objs.iter().enumerate() {
            for (j, s) in o.sects.iter().enumerate() {
                if s.1 != pass_data { continue; }
                cur = (cur + 15) & !15;
                addr[i][j] = cur;
                cur += s.0.len() as u64;
            }
        }
    }
    // 2. resolution: strong beats weak, two strongs clash, first weak wins
    let mut global: HashMap<&str, (u64, bool)> = HashMap::new();
    for (i, o) in objs.iter().enumerate() {
        for s in &o.syms {
            let Some(sec) = s.sect else { continue };
            let a = addr[i][sec] + s.value;
            match global.get(s.name) {
                Some(&(_, false)) if !s.weak => return Err(format!("duplicate symbol {}", s.name)),
                Some(&(_, false)) => {}
                Some(&(_, true)) if s.weak => {}
                _ => { global.insert(s.name, (a, s.weak)); }
            }
        }
    }
    // 3. image, then relocation: S + A (absolute) or S + A - P (PC-relative)
    let mut image = vec![0u8; (cur - base) as usize];
    for (i, o) in objs.iter().enumerate() {
        for (j, s) in o.sects.iter().enumerate() {
            let off = (addr[i][j] - base) as usize;
            image[off..off + s.0.len()].copy_from_slice(&s.0);
        }
    }
    for (i, o) in objs.iter().enumerate() {
        for r in &o.relocs {
            let name = o.syms[r.sym].name;
            let s = global.get(name).ok_or(format!("undefined symbol {name}"))?.0 as i64;
            let p = (addr[i][r.sect] + r.offset as u64) as i64;
            let at = (p as u64 - base) as usize;
            match r.kind {
                Kind::Abs64 => image[at..at + 8].copy_from_slice(&((s + r.addend) as u64).to_le_bytes()),
                Kind::Pc32 => {
                    let v = i32::try_from(s + r.addend - p).map_err(|_| format!("{name}: PC32 out of range"))?;
                    image[at..at + 4].copy_from_slice(&v.to_le_bytes());
                }
            }
        }
    }
    Ok((image, global.into_iter().map(|(k, v)| (k, v.0)).collect()))
}

Test (compiled and run): a.o has main = e8 00000000 c3, a weak foo, a data pointer to foo; b.o has a strong foo.

let base = 0x40_0000;
let (img, syms) = link(&[a, b], base).unwrap();
let foo = syms["foo"];
assert_eq!(foo, base + 16);                       // strong foo from b.o wins, 16-aligned
assert_eq!(&img[1..5], &11i32.to_le_bytes());     // foo - (main+1) - 4 = 16 - 5
let d = (syms["foo_ptr"] - base) as usize;
assert_eq!(&img[d..d + 8], &foo.to_le_bytes());   // R_X86_64_64

Complexity and constants

Linear in input bytes, symbols and relocations; no step is superlinear except sorting (symbol tables, .eh_frame, sections for ICF). Cost drivers: bytes read (debug info is often most of the input), bytes written (the output file), one hash lookup per symbol reference (cache miss), string comparisons of long C++ names, and the relocation pass, which touches memory randomly (S lookup, P write).

Efficiency

• Cost: a link is dominated by reading inputs, hashing symbol names, resolving and patching relocations, and writing the output. Sourced figures (mold README, August 2026 benchmark, AMD Threadripper 7980X 64 cores, release builds of linkers, median of three runs): Chromium 145 debug build, 4.51 GiB output, lld 16.64 s vs mold 1.65 s; TensorFlow 2.21 debug, 9.55 GiB output, lld 50.73 s vs mold 3.15 s.
• Levers:
  • Parallel symbol resolution and relocation — mold paper: 2.4-16.1x faster than lld, up to 112x faster than GNU ld on large programs (mold paper abstract) — many cores, big inputs.
  • Decouple archive handling from symbol resolution (no order-dependent serial scan) — removes the main serial bottleneck (mold paper abstract) — archive-heavy builds.
  • mmap inputs and write the output in place — no copy of input bytes, page cache does the I/O (design notes of mold/lld; mechanism, not benchmarked here) — always.
  • Intern symbol names (string interning) and use a concurrent hash table — one pointer compare instead of string compares — C++ with long mangled names.
  • Split debug info (-gsplit-dwarf) — much less input to move, no figure here — debug-edit-rebuild loops.
  • --gc-sections/ICF — smaller output, so less to write and load — release builds, at extra link time.
• Naive → standard → state of the art: serial linker re-scanning archives and copying all bytes · GNU ld, seconds to minutes on multi-GiB outputs → lld: parallel passes, mmap, hash-based resolution · several times faster than GNU ld → mold/Apple ld-prime/wild: parallelism through every pass · another 2-16x over lld on the machine above.

Implementation notes

• Process relocations per output section in parallel; each patch touches only its own place, so no locks.
• Check ranges: PC32 overflow (+-2 GiB) and CALL26 (+-128 MiB) are real errors or need thunks/veneers; place thunks within range of their callers.
• Keep symbol names as interned ids and sort once; avoid per-symbol heap allocation.
• Emit .eh_frame_hdr so the unwinder works.

Pitfalls

• Archive order: a library listed before the object that needs it is silently skipped, giving "undefined reference".
• ODR/COMDAT: same name, different bodies in different objects: the linker keeps one at random-looking order, no error.
• Symbol interposition: -fPIC libraries call their own exported functions via PLT unless -Bsymbolic or hidden visibility is used.
• Text relocations (DT_TEXTREL) make pages unshareable; hardened systems reject them.

Variants and alternatives

In production

• Toolchains: GNU ld/gold (binutils), LLVM lld (Chrome, Android, FreeBSD), mold, Apple's ld-prime in Xcode, MSVC link.exe; Rust's rustc calls the system linker, with lld or mold selectable.
• JITs: LLVM's JITLink links in-memory objects for the ORC JIT, with the same relocation work as a static linker (docs).
• GPU runtimes: NVIDIA's nvJitLink links device code at runtime from host objects, libraries and other inputs (docs).
• WebAssembly: wasm-ld and other linkers follow the relocation and symbol conventions in the tool-conventions Linking document (spec).
• Databases and embedded: PostgreSQL loads C-language functions from dynamically loaded object files (docs); firmware images are laid out with GNU ld linker scripts and MEMORY regions (docs).

Implementations

Sources

• System V ABI, ELF specification (gABI). pdf
• System V x86-64 psABI (relocation types). repo
• Arm, ELF for the Arm 64-bit Architecture (AArch64). spec
• R. Ueyama, mold: A Massively Parallel Linker, ASPLOS 2027. arXiv · code
• I. L. Taylor, Linkers (blog series, part 1). post
• F. Wu (MaskRay), All about procedure linkage table. post · All about global offset table. post
• LLVM, JITLink and ORC. docs