Lesson 0.6 — The toolchain around the compiler: preprocessor, assembler, linker, loader, runtime¶

Techniques: the preprocessor, assemblers and object files, static linking, loading and dynamic linking, the C runtime (crt files, libc) · Pebble uses: pebblec emits an object file with LLVM's integrated assembler and links it with the system linker against libpebble_runtime.a and libc (docs/runtime-abi.md) · Lab: first.ll calls printf from libc through lli (labs/ch00-first-ir) · Prerequisites: Lesson 0.1 · Time: 3–5 hours

The phases printed by clang -ccc-print-phases at the start of Lesson 0.1 begin with a preprocessor and end with an assembler and a linker; after that, the operating system's loader and the C runtime run before main. This lesson treats each at overview depth — enough to read an object file, understand a link error, and know what happens between exec and main. The running example is two files:

/* sum.c */                                   /* main.c */
int sum(int n) {                               int sum(int n);
  int s = 0;                                   int printf(const char *, ...);
  for (int i = 0; i < n; i++)                  int main(void) {
    s += i;                                      printf("%d\n", sum(10));
  return s;                                      return 0;
}                                              }

1. Problem and motivation¶

The problem. Turn the compiler's output for separately compiled translation units into a running process: expand the source text the compiler actually sees, encode instructions into bytes, combine units and libraries while resolving the names they share, place everything in memory, and set up the environment main expects.

The preprocessor¶

C and C++ source is first rewritten by the preprocessor: #include pastes files, #define macros are expanded, #if selects text. The C preprocessor dates from 1972–73 and was standardized with C in 1989; its expansion rules (with "hide sets" that stop recursion) were formalized by Dave Prosser for the ANSI C committee in 1986 and are specified in §6.10 of the C standard [C-Std]. Only the preprocessed translation unit reaches the lexer (Ch 1). Pebble, Rust and Go have no textual preprocessor.

Assemblers and object files¶

An assembler turns assembly text into machine-code bytes in a relocatable object file: code and data in sections, a symbol table, and relocations — notes that say "patch these bytes when the address of that symbol is known". Object formats: ELF on Linux and most Unix systems [ELF], Mach-O on macOS, COFF/PE on Windows. LLVM integrates its assembler (the MC layer) into the compiler, so clang -c never writes assembly text unless asked.

Static linking¶

A linker combines object files and archive libraries into an executable (or a shared library): it resolves each undefined symbol to a definition, lays out sections at final addresses, and applies relocations. Linkers date from the 1950s; Levine's book is the standard reference [Lev00]. lld (LLVM), GNU ld and gold, mold and Apple's ld64 are production linkers.

Loading and dynamic linking¶

The loader (the kernel's exec plus, for dynamically linked programs, the dynamic linker ld.so) maps the executable's segments into memory, loads the shared libraries it needs, applies the remaining relocations and binds imported functions — possibly lazily, on first call, through the PLT and GOT [Dre11, Lev00].

The C runtime (crt, libc)¶

main is not the first code that runs. The linker adds crt ("C runtime") object files — crt1.o/Scrt1.o with _start, crti.o/crtn.o, crtbegin.o/crtend.o — which set up the stack and arguments, call __libc_start_main, run constructors, call main, and pass its result to exit. libc supplies printf, malloc and the system-call wrappers. Pebble's own runtime (pebble_print_int, pebble_trap) sits on top of libc.

2. Definitions and algorithms¶

The preprocessor¶

Definition 0.6.1 (Tokens with hide sets; object-like and function-like macros)

A preprocessing token $t$ carries a hide set $\mathrm{HS}(t)$, a set of macro names (initially $\emptyset$). A macro definition maps a name $M$ to a replacement token list $\rho_M$, with parameters for a function-like macro. Expanding an occurrence $t$ of $M$ with $M \notin \mathrm{HS}(t)$ replaces it (and, for a function-like macro, its argument list) by $\rho_M$ with arguments substituted, and adds $M$ (and $\mathrm{HS}(t)$) to the hide set of every token of the result. A token whose name is in its own hide set is never expanded again ("painted blue").

Algorithm 0.6.2 (Macro expansion with hide sets, after Prosser)

Input: a token sequence $\tau$; a macro table.
Output: the expanded token sequence.
Precondition: every function-like macro invocation has a complete argument list.
Postcondition: no token $t$ in the output names a macro $M \notin \mathrm{HS}(t)$ that could still be expanded.
Invariant: every token produced by expanding $M$ has $M$ in its hide set.

function Expand(τ):
    out ← []
    while τ ≠ []:
        t ← pop front of τ
        if t names a macro M and M ∉ HS(t):
            if M is function-like:
                if next token is not '(': append t to out; continue
                args ← read balanced arguments from τ (each fully Expanded first)
                r ← Substitute(ρ_M, args)
            else:
                r ← ρ_M
            for u in r: HS(u) ← HS(u) ∪ HS(t) ∪ {M}
            push r to the front of τ                # rescan the result
        else:
            append t to out
    return out

The preprocessor at work

Reproduce (clang 23.1.2):

printf '#define SQ(x) ((x) * (x))\n#define N N + 1\n#define A B\n#define B A\nint f(int y) { return SQ(SQ(y)) + N + A; }\n' > mac.c
clang-23 -E -P mac.c
printf '#define SQ(x) ((x) * (x))\nint sq(int y) { return SQ(y); }\n' > sq.c
clang-23 -fsyntax-only -Xclang -dump-tokens sq.c 2>&1 | sed -n '9,11p'

Output (complete):

int f(int y) { return ((((y) * (y))) * (((y) * (y)))) + N + 1 + A; }
l_paren          '('                             Loc=<sq.c:2:24 <Spelling=sq.c:1:15>> [LeadingSpace]
l_paren          '('                             Loc=<sq.c:2:24 <Spelling=sq.c:1:16>>
identifier       'y'                             Loc=<sq.c:2:24 <Spelling=sq.c:2:27>>

What to notice: SQ(SQ(y)) expands both levels (arguments are expanded before substitution); N expands once to N + 1 — the inner N has N in its hide set; A expands to B, which expands back to A and stops (Definition 0.6.1). In the token dump each token of the expansion is located at the use (sq.c:2:24) but spelled at the definition (Spelling=sq.c:1:15): clang tracks both so diagnostics can point into macros.

Assemblers and object files¶

Definition 0.6.3 (Relocatable object file)

A relocatable object is a tuple $(\Sigma, \mathrm{Sym}, \mathrm{Rel})$: sections $\Sigma$ (named byte arrays with flags, e.g. .text executable, .rodata read-only, .data writable); a symbol table $\mathrm{Sym}$ whose entries are defined (a section and an offset) or undefined, with a binding — local, global (strong) or weak; and relocations $\mathrm{Rel}$, each $(s, o, \mathit{type}, \mathit{sym}, A)$: "in section $s$ at offset $o$, write the value computed by $\mathit{type}$ from the final address $S$ of $\mathit{sym}$, the addend $A$ and the final address $P$ of the patched location".

Definition 0.6.4 (PC-relative relocation on x86-64)

For R_X86_64_PC32 and (when no PLT is needed) R_X86_64_PLT32, the linker writes the 32-bit value $S + A - P$ at $P$ [SysV-ABI]. A call or RIP-relative operand whose 4-byte displacement field is at $P$ is followed by the next instruction at $P + 4$ and addresses $(P + 4) + \mathrm{disp}$; the assembler therefore emits $A = -4$.

Algorithm 0.6.5 (Two-pass assembler)

Input: assembly text: labels, instructions, directives.
Output: a relocatable object (Definition 0.6.3).
Precondition: each instruction's encoding length can be determined in pass 1 (or is fixed by relaxation, below).
Postcondition: every reference to a label in the same section is encoded with its final offset; every other reference has a relocation.
Invariant (pass 2): the offset counter equals the offset pass 1 assigned to the current line.

function Assemble(lines):
    # pass 1: addresses
    off[s] ← 0 for every section s
    for line in lines:
        if line is a label L in section s: define L at (s, off[s])
        else: off[s] ← off[s] + EncodedLength(line)
    # pass 2: bytes and relocations
    for line in lines (instructions only), in section s:
        for each operand referring to symbol x:
            if x is defined in section s and the reference is PC-relative:
                field ← address(x) − (address of next instruction)   # resolved now
            else:
                field ← 0; add relocation (s, offset of field, type, x, addend)
        append Encode(line, fields) to s
    emit sections, symbol table (labels, plus UNDEF entries for unknown x), relocations

An ELF object: sections, symbols, relocations

Reproduce (clang 23.1.2, llvm-readelf and llvm-objdump 23.1.2; sum.c and main.c as above):

clang-23 --target=x86_64-linux-gnu -O2 -c sum.c main.c
llvm-readelf -h main.o | grep -E 'Class|Type|Machine'
llvm-readelf -s main.o
llvm-readelf -r main.o
llvm-objdump -d -r --no-show-raw-insn main.o

Output (complete):

  Class:                             ELF64
  Type:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64

Symbol table '.symtab' contains 7 entries:
   Num:    Value          Size Type    Bind   Vis       Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT   UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT   ABS main.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT     2 .text
     3: 0000000000000000     4 OBJECT  LOCAL  DEFAULT     4 .L.str
     4: 0000000000000000    31 FUNC    GLOBAL DEFAULT     2 main
     5: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT   UND sum
     6: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT   UND printf

Relocation section '.rela.text' at offset 0x1b0 contains 3 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000000007  0000000500000004 R_X86_64_PLT32         0000000000000000 sum - 4
000000000000000e  0000000300000002 R_X86_64_PC32          0000000000000000 .L.str - 4
0000000000000017  0000000600000004 R_X86_64_PLT32         0000000000000000 printf - 4

Relocation section '.rela.eh_frame' at offset 0x1f8 contains 1 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000000020  0000000200000002 R_X86_64_PC32          0000000000000000 .text + 0

main.o: file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <main>:
       0:       pushq   %rax
       1:       movl    $0xa, %edi
       6:       callq   0xb <main+0xb>
        0000000000000007:  R_X86_64_PLT32   sum-0x4
       b:       leaq    (%rip), %rdi            # 0x12 <main+0x12>
        000000000000000e:  R_X86_64_PC32    .L.str-0x4
      12:       movl    %eax, %esi
      14:       xorl    %eax, %eax
      16:       callq   0x1b <main+0x1b>
        0000000000000017:  R_X86_64_PLT32   printf-0x4
      1b:       xorl    %eax, %eax
      1d:       popq    %rcx
      1e:       retq

What to notice: sum and printf are UND (undefined) global symbols; each call's 4-byte displacement (at offsets 7 and 0x17) is 0 in the file and has a relocation with addend $-4$ (Definition 0.6.4). The disassembler shows callq 0xb — a call to the next instruction — because the displacement is still 0. Even the reference to the local string .L.str needs a relocation: its section's final address is unknown too.

Static linking¶

Algorithm 0.6.6 (Static linking)

Input: relocatable objects $O_1, \dots, O_k$ and archives (libraries) in command-line order; an entry symbol (_start).
Output: an executable, or an error (undefined or duplicate symbol).
Precondition: all objects are for the same target and ABI.
Postcondition: every relocation has been applied with the final $S$ and $P$; every referenced global symbol has exactly one chosen definition (Theorem 0.6.13).
Invariant: the global symbol table maps each name to at most one strong definition.

function Link(inputs):
    G ← empty map name → definition; U ← set of undefined names
    for input in inputs, in order:
        if input is an object: Add(input)
        if input is an archive:
            repeat: add every member that defines a name in U (via its index)
            until no member was added                     # archives are searched, not added
    if U ≠ ∅: error "undefined reference to" each name in U
    Layout: concatenate same-named sections of the chosen objects; assign addresses
    for each object o, relocation (s, off, type, x, A) of o:
        S ← address of G[x] (or of o's local x); P ← address of s in o + off
        write Compute(type, S, A, P) at P                 # S + A − P for PC32/PLT32
    return executable with program headers (segments) and entry = address of _start

function Add(o):
    for each global symbol x of o:
        if x is defined (strong):
            if G[x] is strong: error "multiple definition of x"
            G[x] ← o's definition; remove x from U
        elif x is weak and x ∉ G: G[x] ← o's definition; remove x from U
        elif x is undefined and x ∉ G: add x to U

After linking: the relocation applied

Reproduce (clang 23.1.2 driver, GNU ld 2.42, glibc 2.39 on Ubuntu 24.04; addresses depend on the linker and libc):

clang-23 main.o sum.o -o prog && ./prog
llvm-objdump -d --disassemble-symbols=main prog | sed -n '6,9p'
clang-23 main.o -o bad

Output (complete):

45
0000000000001140 <main>:
    1140: 50                            pushq   %rax
    1141: bf 0a 00 00 00                movl    $0xa, %edi
    1146: e8 15 00 00 00                callq   0x1160 <sum>
/usr/bin/ld: main.o: in function `main':
main.c:(.text+0x7): undefined reference to `sum'
clang-23: error: linker command failed with exit code 1 (use -v to see invocation)

What to notice: the displacement bytes 15 00 00 00 are $S + A - P$ with $S$ = 0x1160 (sum), $A = -4$, $P$ = 0x1147 (§3 computes it). Without sum.o the same relocation has no definition to resolve to, and the linker — not the compiler, which accepted main.c — reports it, naming the object, the section offset .text+0x7 and the symbol, i.e. exactly the relocation of the previous box.

Loading and dynamic linking¶

Definition 0.6.7 (Segments, dynamic section, PLT and GOT)

An executable's program headers describe segments: byte ranges to map at virtual addresses with permissions (R, R E, RW). INTERP names the dynamic linker; the DYNAMIC segment lists the shared libraries it NEEDED and the dynamic relocations. A call to an imported function goes through a PLT (procedure linkage table) stub, which jumps through a GOT (global offset table) slot; with lazy binding the slot initially points back into the PLT, whose code calls the resolver to find the function, stores its address in the slot and jumps there.

Algorithm 0.6.8 (Loading a dynamically linked program)

Input: an ELF executable $E$ and the file system.
Output: a process about to execute $E$'s entry point, or a load error.
Precondition: every NEEDED library can be found in the search path (DT_RUNPATH, LD_LIBRARY_PATH, the system cache).
Postcondition: every eager relocation is applied; every lazily bound GOT slot resolves to the right function on first call (Proposition 0.6.14).
Invariant: libraries are loaded at most once each, in breadth-first order of NEEDED entries.

function Exec(E):                                   # kernel
    map every PT_LOAD segment of E with its permissions
    if E has PT_INTERP: map the dynamic linker D; jump to D's entry with E's auxv
    else: jump to E's entry

function DynamicLinker(E):                           # ld.so
    queue ← NEEDED(E); loaded ← [E]
    while queue ≠ []:
        lib ← pop(queue); if lib ∈ loaded: continue
        path ← Search(lib) or error "cannot open shared object file"
        map path's segments; append to loaded; queue ← queue + NEEDED(path)
    for obj in loaded: apply its eager relocations (RELATIVE, GLOB_DAT), looking symbols
                       up in loaded order
    for obj in loaded: point each JUMP_SLOT GOT entry at its PLT resolver stub (lazy)
    run init functions of libraries, then jump to E's entry (_start)

function Resolve(slot):                              # first call through the PLT
    f ← look up the slot's symbol in loaded order
    GOT[slot] ← address of f; jump to f

The loader: program headers, NEEDED, a missing library, lazy binding

Reproduce (clang 23.1.2, GNU ld 2.42, glibc 2.39; Ubuntu 24.04):

llvm-readelf -l prog | grep -E 'INTERP|interpreter|LOAD'
clang-23 -shared -fPIC sum.c -o libsum.so
clang-23 main.c -L. -lsum -o prog2
llvm-readelf -d prog2 | grep NEEDED
./prog2; echo "exit status $?"
LD_LIBRARY_PATH=. LD_DEBUG=bindings ./prog2 2>&1 | grep -E "normal symbol .(sum|printf)" | sed -E 's/^ *[0-9]+://'

Output (complete; the LD_DEBUG process-id prefix is removed by sed):

  INTERP         0x000318 0x0000000000000318 0x0000000000000318 0x00001c 0x00001c R   0x1
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
  LOAD           0x000000 0x0000000000000000 0x0000000000000000 0x0005f0 0x0005f0 R   0x1000
  LOAD           0x001000 0x0000000000001000 0x0000000000001000 0x000189 0x000189 R E 0x1000
  LOAD           0x002000 0x0000000000002000 0x0000000000002000 0x0000e0 0x0000e0 R   0x1000
  LOAD           0x002dd0 0x0000000000003dd0 0x0000000000003dd0 0x000248 0x000250 RW  0x1000
  0x0000000000000001 (NEEDED)       Shared library: [libsum.so]
  0x0000000000000001 (NEEDED)       Shared library: [libc.so.6]
./prog2: error while loading shared libraries: libsum.so: cannot open shared object file: No such file or directory
exit status 127
    binding file ./prog2 [0] to ./libsum.so [0]: normal symbol `sum'
    binding file ./prog2 [0] to /lib/x86_64-linux-gnu/libc.so.6 [0]: normal symbol `printf' [GLIBC_2.2.5]

What to notice: the executable asks for /lib64/ld-linux-x86-64.so.2 as its interpreter and has four LOAD segments with different permissions (only one is executable, R E). prog2 needs libsum.so; it linked fine, but at load time the dynamic linker cannot find it (not on the search path) and the program never starts. With LD_LIBRARY_PATH=. it runs, and LD_DEBUG=bindings shows the dynamic linker binding sum and printf in the running process (Algorithm 0.6.8's Resolve).

The C runtime (crt, libc)¶

Definition 0.6.9 (Startup objects and the startup sequence)

The entry point _start (in crt1.o, or Scrt1.o for position-independent executables) is the first user-space code of a process. It calls __libc_start_main(main, argc, argv, …) in libc, which initializes libc, runs the functions in .init_array (constructors, collected by the linker with help from crti.o/crtbegin*.o/crtend*.o/crtn.o), calls main, and calls exit with its result, which runs .fini_array and atexit handlers.

Algorithm 0.6.10 (Program startup and shutdown)

Input: a process image after Algorithm 0.6.8; argc, argv, envp on the stack.
Output: the process exit status.
Precondition: the linker placed crt1/Scrt1 first, crti/crtbegin before and crtend/crtn after the user objects, and libc last.
Postcondition: every constructor ran before main and every destructor after it (Proposition 0.6.15); the exit status is main's return value.
Invariant: the stack is aligned as the ABI requires at every call.

function _start():                           # Scrt1.o, hand-written assembly
    clear the frame pointer; align the stack
    argc, argv ← from the initial stack
    __libc_start_main(main, argc, argv, …)   # never returns

function __libc_start_main(main, argc, argv, …):   # libc
    initialize libc (TLS, stdio, security features)
    for f in .init_array (in order): f(argc, argv, envp)
    exit(main(argc, argv, envp))

function exit(status):
    for h in atexit handlers (reverse registration order): h()
    for f in .fini_array (reverse order): f()
    flush stdio; _exit(status)               # system call

The crt files on clang's link line

Reproduce (clang 23.1.2 driver on Ubuntu 24.04 with GCC 14's crt files; paths differ per system):

clang-23 -### main.o sum.o -o prog 2>&1 | tail -1 | tr ' ' '\n' | grep -E 'crt|^"-l|ld"$|main.o|sum.o'
llvm-nm prog | grep -E ' (_start|main|sum|__libc_start_main.*)$'

Output (complete):

"/usr/bin/ld"
"/lib/x86_64-linux-gnu/Scrt1.o"
"/lib/x86_64-linux-gnu/crti.o"
"/usr/lib/gcc/x86_64-linux-gnu/14/crtbeginS.o"
"main.o"
"sum.o"
"-lgcc"
"-lgcc_s"
"-lc"
"-lgcc"
"-lgcc_s"
"/usr/lib/gcc/x86_64-linux-gnu/14/crtendS.o"
"/lib/x86_64-linux-gnu/crtn.o"
                 U __libc_start_main@GLIBC_2.34
0000000000001050 T _start
0000000000001140 T main
0000000000001160 T sum

What to notice: the driver brackets your objects with the startup files in exactly the order Algorithm 0.6.10's precondition requires, and adds -lc (libc) and -lgcc (compiler support routines). The executable's entry _start (at 0x1050, the entry point readelf -h reports) comes from Scrt1.o; __libc_start_main is imported from glibc and bound by the dynamic linker.

3. Worked examples¶

Running example. sum.c and main.c, compiled, linked and run.

The preprocessor¶

Algorithm 0.6.2 on N + A with #define N N + 1, #define A B, #define B A (hide sets in braces):

step	output so far	remaining input	action
0	—	`N`{} `+`{} `A`{}	—
1	—	`N` `+` `1` `+`{} `A`{}	expand `N` (N ∉ {})
2	`N`	`+` `1` `+` `A`{}	`N` ∈ HS: copy (painted blue)
3	`N + 1 +`	`A`{}	copy three tokens
4	`N + 1 +`	`B`	expand `A`
5	`N + 1 +`	`A`	expand `B` (B ∉ {A})
6	`N + 1 + A`	—	`A` ∈ {A, B}: copy

Result N + 1 + A, as clang printed.

Assemblers and object files¶

Algorithm 0.6.5 on main's code (pass 1 lengths from the disassembly: pushq 1 byte, movl $imm 5, callq 5, leaq 7, …):

line	offset (pass 1)	pass 2: operand	resolved or relocation
`pushq %rax`	0	—	—
`movl $10, %edi`	1	immediate	—
`callq sum`	6	`sum` undefined	relocation at 6 + 1 = 7: `R_X86_64_PLT32 sum − 4`
`leaq .L.str(%rip), %rdi`	0xb	`.L.str` in `.rodata.str1.1`, another section	relocation at 0xb + 3 = 0xe: `R_X86_64_PC32 .L.str − 4`
`callq printf`	0x16	`printf` undefined	relocation at 0x17

The three relocations are exactly those of llvm-readelf -r main.o.

Static linking¶

Algorithm 0.6.6 for clang main.o sum.o (after layout: main at 0x1140, sum at 0x1160, the string at 0x2004):

relocation	$S$	$A$	$P$	$S + A - P$	bytes written	check: next instruction + disp
`sum`, PLT32 at `main+7`	`0x1160`	−4	`0x1147`	`0x15`	`15 00 00 00`	`0x114b + 0x15 = 0x1160` ✓
`.L.str`, PC32 at `main+0xe`	`0x2004`	−4	`0x114e`	`0xeb2`	`b2 0e 00 00`	`0x1152 + 0xeb2 = 0x2004` ✓

printf is not defined by any object: libc.so.6 defines it, so the linker leaves a R_X86_64_JUMP_SLOT dynamic relocation for the loader and directs the call to a PLT stub (callq 0x1030 <printf@plt> in the linked program).

Loading and dynamic linking¶

Algorithm 0.6.8 for prog2 with LD_LIBRARY_PATH=.:

step	action	state
1	kernel maps `prog2`'s LOAD segments, sees `INTERP`	ld.so mapped
2	queue ← NEEDED(prog2) = [libsum.so, libc.so.6]	loaded = [prog2]
3	load `./libsum.so` (found via `LD_LIBRARY_PATH`)	loaded = [prog2, libsum.so]; its NEEDED libc queued
4	load `libc.so.6`	loaded = [prog2, libsum.so, libc.so.6]
5	skip libc.so.6 (already loaded)	—
6	eager relocations; JUMP_SLOT entries lazy	GOT[sum], GOT[printf] → resolver
7	first call to `sum`: Resolve	GOT[sum] ← address in libsum.so ("binding … `sum'")
8	first call to `printf`: Resolve	GOT[printf] ← address in libc

Without LD_LIBRARY_PATH, step 3's Search fails: exit status 127.

The C runtime (crt, libc)¶

Algorithm 0.6.10 for prog: _start (0x1050) → __libc_start_main → .init_array (one entry, frame_dummy, from crtbeginS.o) → main (0x1140) → sum → printf prints 45 → main returns 0 → exit(0) runs .fini_array (__do_global_dtors_aux) → _exit(0).

4. Invariants and correctness¶

The preprocessor¶

Theorem 0.6.11 (Macro expansion terminates)

For a finite macro table with $k$ macros, Algorithm 0.6.2 terminates on every finite input.

Proof

Assign each token $t$ in the remaining input the value $v(t) = k - \lvert \mathrm{HS}(t) \rvert \in \{0, \dots, k\}$ (hide sets contain macro names only, so $\lvert \mathrm{HS}(t) \rvert \le k$), and consider the multiset $V$ of these values. Copying a token to the output removes one element of $V$. Expanding $t$ (naming $M \notin \mathrm{HS}(t)$) removes $t$ and inserts finitely many tokens, each with hide set $\supseteq \mathrm{HS}(t) \cup \{M\}$ (the invariant), hence value at most $v(t) - 1$. Both steps make $V$ strictly smaller in the multiset ordering over $\mathbb{N}$, which is well founded (Dershowitz–Manna), so the loop runs finitely often. Argument pre-expansion is a recursive call on a sub-sequence, which terminates by the same argument.

Assemblers and object files¶

Lemma 0.6.12 (Pass 1 addresses are the pass 2 addresses)

If EncodedLength in pass 1 equals the length of Encode in pass 2 for every line, then every label's address assigned in pass 1 is the offset at which the labelled line is emitted in pass 2, and every resolved PC-relative field is correct.

Proof

Induction over the lines of a section: both passes start at offset 0 and advance by the same length per line. Hence a label defined before line $j$ has the offset at which line $j$ is emitted. A resolved field computes target − (next instruction), both final offsets in the same section, which is what the CPU adds to its program counter. When it breaks: x86 jumps have 2-byte and 5-byte forms; if pass 1 guesses the short form and the target turns out to be far, lengths disagree. Assemblers relax: start with short forms and iterate pass 1 until no jump needs to grow (LLVM's MCAssembler relaxation loop).

Static linking¶

Theorem 0.6.13 (Relocation and resolution correctness)

(a) If the linker writes $S + A - P$ for a PC32/PLT32 relocation with $A = -4$, the patched call or RIP-relative operand refers to address $S$. (b) Algorithm 0.6.6 succeeds iff every name that remains undefined after processing all inputs is defined in no input, and no name has two strong definitions; then every reference is bound to the unique strong definition if one exists, else to the first weak one.

Proof

(a) The instruction after the 4-byte field starts at $P + 4$, and the CPU computes $(P + 4) + (S + A - P) = S + A + 4 = S$. (b) Add fails exactly on a second strong definition (the invariant keeps at most one). A strong definition replaces a weak one and is never replaced, so the final binding is the strong definition when there is one; otherwise the first weak definition added stays. Archive members are added only when they define a currently undefined name, repeatedly, so a name is left in $U$ only if no processed object and no archive member defines it. When it breaks: archive order matters — an archive is searched only when it appears, so cc -lm main.o can fail to find sqrt that main.o needs, while cc main.o -lm works.

Loading and dynamic linking¶

Proposition 0.6.14 (Lazy binding is transparent)

If symbol lookup at Resolve time returns the same definition as an eager lookup would, then a call through the PLT behaves as a direct call to the resolved function: on the first call via Resolve, afterwards via the patched GOT slot.

Proof

The PLT stub jumps through GOT[slot]. Before the first call, the slot points to code that calls Resolve, which computes $f$, stores it, and jumps to $f$ with the original arguments (the stub preserves the argument registers), so the first call reaches $f$. Afterwards GOT[slot] $= f$ and the stub jumps straight there. Lookup order is fixed (loaded order), so eager and lazy lookups agree unless libraries are loaded or unloaded in between (dlopen), which is where the hypothesis matters. LD_BIND_NOW=1 or -z now makes binding eager (and lets the GOT be made read-only: GNU_RELRO).

The C runtime (crt, libc)¶

Proposition 0.6.15 (Constructors before main, destructors after)

Under Algorithm 0.6.10's precondition, every function in .init_array runs before main, and every function in .fini_array runs after main returns (or exit is called), in reverse order.

Proof

The linker concatenates the .init_array sections of all inputs into one array delimited by symbols the crt objects provide (__init_array_start/__init_array_end); __libc_start_main iterates over it before calling main, and exit iterates over .fini_array backwards before _exit. main's return value is passed to exit, so the ordering holds on both exit paths. Calling _exit directly (or crashing) skips the destructors — the one way around the proposition.

5. Complexity¶

Variables: $n$ = input size in tokens or bytes, $r$ = number of relocations, $y$ = number of symbols, $\ell$ = number of shared libraries, $k$ = number of macros.

Technique	Time (worst)	Time (typical)	Space	Variables
The preprocessor	exponential output in the worst case (nested macros can double the size per level)	linear in the (large) expanded text: C++ headers expand to $10^5$–$10^6$ lines	expanded translation unit	$n, k$
Assemblers and object files	$O(n)$ per pass; relaxation iterates, $O(n)$ passes in the worst case	two passes + a few relaxation rounds	object size $O(n)$	$n$
Static linking	$O(n + y + r)$ with hash tables	seconds for huge C++ programs; parallel linkers (lld, mold)	output + symbol table	$n, y, r$
Loading and dynamic linking	$O(\ell + r_{\text{eager}})$ at startup + one lookup per lazily bound function	milliseconds; lazy binding moves cost to first calls	mapped segments (shared between processes)	$\ell, r$
The C runtime (crt, libc)	$O(\text{constructors})$ before `main`	negligible for C, significant for C++ static initializers	—	—

Proposition 0.6.16 (Linear-time linking)

With hash tables for $G$ and $U$, Algorithm 0.6.6 runs in expected $O(n + y + r)$ time, plus the archive rescans.

Proof

Each symbol of each added object is inserted or looked up once (expected $O(1)$); layout visits each section once; each relocation is computed and written once in $O(1)$. Archive rescans add a factor bounded by the number of archive members added, since each rescan adds at least one member or ends.

Pathological inputs. (1) Preprocessor: #define A0 x and #define A{i+1} A{i} A{i} for $i < 30$ makes A30 expand to $2^{30}$ tokens. (2) Assembler: a chain of jumps whose short/long forms depend on each other can force many relaxation rounds. (3) Linker: circular dependencies between archives need the archive listed twice (or --start-group), because Algorithm 0.6.6 searches each archive only where it appears. (4) Loader: thousands of shared libraries with eager binding make startup slow — the reason lazy binding exists, and a reason for prelinking.

At scale. lld and mold link programs with hundreds of millions of relocations in seconds by parallelizing layout and relocation application; Chromium's debug build links thousands of objects per binary.

The preprocessor¶

Modules (C++20 modules, Clang modules) [CLANG-Modules] — replace textual #include with compiled interfaces, removing repeated preprocessing and parsing of headers; trade-off: build-system complexity.
Precompiled headers [CLANG-PCH] — cache the parsed state after a common prefix of includes; trade-off: the prefix must be identical across files.

Assemblers and object files¶

Integrated assemblers — LLVM's MC layer encodes instructions directly from machine IR, skipping the assembly text (clang -c); trade-off: none for users, one encoder per target for LLVM.
Mach-O and COFF — the same concepts with different containers: Mach-O's LC_SEGMENT_64 load commands and relocation types, COFF's sections and IMAGE_REL_* relocations.

Static linking¶

LTO — objects contain IR; the linker calls back into the compiler to optimize across units (Lesson 0.1 §6).
Section garbage collection (-ffunction-sections -Wl,--gc-sections) and identical code folding — remove unreferenced and duplicate functions (lld: elf::markLive, elf::doIcf) [LLD-GC]; trade-off: link time.

Loading and dynamic linking¶

Position-independent executables (PIE) and ASLR — load at a random base; the R_X86_64_RELATIVE relocations in .rela.dyn adjust absolute pointers; trade-off: a few relocations at startup.
Eager binding + RELRO (-z now) — resolve everything at startup and make the GOT read-only; trade-off: startup time for security.

The C runtime (crt, libc)¶

Static linking against libc (musl, -static) — no dynamic linker; the startup sequence and libc are in the executable; trade-off: size and no shared security updates.
Freestanding programs (-ffreestanding -nostdlib) — provide _start yourself (kernels, embedded, the Pebble runtime tests); trade-off: no libc.

7. In real compilers¶

The preprocessor¶

LLVM

clang/lib/Lex/PPDirectives.cpp handles #include/#define/#if; clang/lib/Lex/LiteralSupport.cpp — NumericLiteralParser::NumericLiteralParser reports err_invalid_suffix_constant (the 0x; example of the phases drill) (LLVM 23.1.2) [CLANG-Lex].

GCC libcpp/ — the C preprocessor library used by GCC's C-family front ends.

Assemblers and object files¶

LLVM MC llvm/lib/MC/ELFObjectWriter.cpp writes ELF objects; llvm/lib/MC/MCParser/AsmParser.cpp parses assembly, including inline asm strings, and hands operands to the target's parser: llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp — X86AsmParser::ParseRegister reports the invalid register name example of the phases drill (LLVM 23.1.2) [LLVM-MC].
GNU as (binutils) — the assembler GCC invokes by default.

Find where LLVM does it. Open llvm/lib/MC/ELFObjectWriter.cpp at llvmorg-23.1.2. Question: which type in that file (it is declared with struct) writes the ELF section headers and computes the symbol table? (quiz llvm-where-elf-writer)

Static linking¶

lld lld/ELF/Symbols.cpp — the Symbol::resolve overloads implement Algorithm 0.6.6's Add (strong/weak/lazy/shared), elf::reportDuplicate the "duplicate symbol" error; lld/ELF/InputSection.cpp — InputSectionBase::getRelocTargetVA computes $S + A - P$ for R_PC; lld/ELF/Arch/X86_64.cpp — X86_64::relocate writes the bytes (LLVM 23.1.2) [LLD-ELF].
GNU ld (binutils 2.42) — the linker used in the boxes (/usr/bin/ld).

Loading and dynamic linking¶

glibc elf/rtld.c (the dynamic linker ld.so), elf/dl-runtime.c (_dl_fixup, the lazy Resolve) (glibc-2.39) — see Drepper's paper for the design [Dre11].
Linux fs/binfmt_elf.c (v6.8) — the kernel side of Exec (maps PT_LOAD, honors PT_INTERP).

The C runtime (crt, libc)¶

clang driver clang/lib/Driver/ToolChains/Gnu.cpp — chooses Scrt1.o/crt1.o, crti.o, crtbeginS.o and the libraries on the link line (the box above) (LLVM 23.1.2) [CLANG-Driver].
compiler-rt compiler-rt/lib/builtins/crtbegin.c — LLVM's own crtbegin implementation (LLVM 23.1.2).
Pebble pebble/runtime/ — pebble_print_int, pebble_trap on top of libc (docs/runtime-abi.md).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
The preprocessor	textual: can generate any token sequence, knows no types	linear in expanded size, which can be huge · C++ headers dominate compile time	notoriously poor (errors appear in expanded code; clang tracks macro locations to help)	moderate (hide sets, stringizing, pasting)	C, C++, assembly with macros
Assemblers and object files	exact encoding; no optimization	two passes + relaxation · negligible time	precise (line, invalid register or operand)	one encoder per ISA (LLVM: TableGen-generated)	every native toolchain; integrated in LLVM
Static linking	whole-program symbol resolution and layout	$O(n + y + r)$ · seconds even for huge programs with lld/mold	clear for undefined/duplicate symbols; object and offset named	high (formats, relocation types, archives)	every native build
Loading and dynamic linking	late binding: libraries shared and updated independently	$O(\ell + r)$ at startup + lazy lookups · milliseconds	errors only at run time (missing library, symbol version)	high (in libc and kernel)	every dynamically linked program
The C runtime (crt, libc)	defines what runs before and after `main`	negligible for C	failures look like crashes before `main`	small (crt), huge (libc)	every hosted C program; Pebble's runtime

Choose these by what your language needs, not by preference: a C-family language needs the preprocessor; every native compiler needs an assembler (integrated, if it uses LLVM) and a linker; dynamic linking is the default on desktop systems and static linking is preferred for self-contained deployments (containers, embedded, Go's default); a freestanding runtime replaces crt and libc when there is no operating system.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch00.yaml`)	Drill	Flashcard tag	Exercises
The preprocessor	`macro-hideset`, `phase-attribution`	`./course drill phases`	`preprocessor`	E1
Assemblers and object files	`reloc-value`, `llvm-where-elf-writer`	`./course drill phases`	`assembler`	E1
Static linking	`reloc-value`, `link-errors`	`./course drill phases`	`linker`	E1
Loading and dynamic linking	`loader-exit-127`, `phase-attribution`	`./course drill phases --difficulty hard`	`loader`	—
The C runtime (crt, libc)	`crt-order`, `startup-sequence`	— (a fixed sequence, not a randomizable problem; the quiz orders it)	`crt`	—

Pitfall

"Undefined reference" is not a compiler error. main.c compiled because a declaration (int sum(int n);) is enough for the compiler; only the linker, which sees all objects, can discover that no object defines sum. The fix is on the link line, not in the code.

References¶

See the chapter references.

Lesson 0.6 — The toolchain around the compiler: preprocessor, assembler, linker, loader, runtime¶

1. Problem and motivation¶

The preprocessor¶

Assemblers and object files¶

Static linking¶

Loading and dynamic linking¶

The C runtime (crt, libc)¶

2. Definitions and algorithms¶

The preprocessor¶

Assemblers and object files¶

Static linking¶

Loading and dynamic linking¶

The C runtime (crt, libc)¶

3. Worked examples¶

The preprocessor¶

Assemblers and object files¶

Static linking¶

Loading and dynamic linking¶

The C runtime (crt, libc)¶

4. Invariants and correctness¶

The preprocessor¶

Assemblers and object files¶

Static linking¶

Loading and dynamic linking¶

The C runtime (crt, libc)¶

5. Complexity¶

6. Variants and refinements¶

The preprocessor¶

Assemblers and object files¶

Static linking¶

Loading and dynamic linking¶

The C runtime (crt, libc)¶

7. In real compilers¶

The preprocessor¶

Assemblers and object files¶

Static linking¶

Loading and dynamic linking¶

The C runtime (crt, libc)¶

8. Comparison¶

9. Assessment¶

References¶