[The World of Linkers—Theory 16] From a Working Linker to One You Can Trust

This chapter places familiar algorithms inside a complete tool. It builds on symbol selection from Theory 03, relocation from Theory 04, and layout from Theory 05. Engineering does not replace linking rules: parallelism, caching, and reduced copying must preserve their results and diagnostic boundaries.

Follow the stages by asking which information is stable and who consumes it next, then examine parallelism and determinism. The testing discussion separates evidence about formats, algorithms, output structure, and runtime behavior. Performance measurements and specific implementations illustrate tradeoffs; incremental linking and default-toolchain integration can follow once correctness boundaries are clear.

A small linker can be described in three nouns: sections, symbols, and relocations. Give it tens of thousands of object files, ask it to use every CPU core, require identical output on repeated builds, and hand that output to several generations of kernels and runtimes. The question changes. How do individually correct algorithms become a complete tool that people can trust?

Even the boundary of the implementation is a choice. ELF¹, Mach-O, and PE/COFF all organize code and repair references, but their rules for symbols, layout, and loading differ. A common abstraction can make the straightforward operation in each format harder to express. LLD² deliberately keeps its format-specific linkers largely separate; GNU³ ld retains BFD's general framework for many binary formats. Sharing code has a cost as well as a benefit. The useful question is what a particular pass actually needs to do with its data. LLD design

For an ELF link, a simplified pipeline looks like this:

1. Read object files, archives, shared libraries, and any linker scripts.
2. Resolve symbols, extracting archive members when needed.
3. Mark sections reachable from the entry point and other roots, then discard the rest.
4. Organize input sections into output sections and merge eligible strings. Scan retained relocations to collect GOT⁴, TLS⁵, and PLT⁶ requirements, and determine synthetic-section sizes.
5. Assign output addresses and file offsets.
6. Copy contents into their assigned ranges, apply relocations such as S + A − P, and fill address-dependent fields in synthetic sections such as .dynamic and .eh_frame_hdr.
7. Calculate the build ID and finish the output file.

These pass boundaries describe when information becomes stable and which work may proceed in parallel. They do not promise a single trip through the pipeline. RISC-V⁷ relaxation changes section sizes; branch thunks add content; LTO⁸ produces new object files. A real implementation must revisit affected decisions.

A synthetic section contains output generated by the linker rather than a complete copy of one input section. It occupies file or memory space and must participate in layout. Establishing its size and filling its bytes are separate steps. The number of GOT entries determines how many address slots to reserve; final symbol addresses determine what goes in those slots. The number of .eh_frame_hdr index entries determines the table's extent; final function and FDE addresses determine the entry values. Stable addresses depend on known sizes.

Suppose an ELF64 output places two eight-byte GOT slots at [0x402000, 0x402010), immediately followed by read-only constants at 0x402010. Adding a third slot after assigning addresses changes both ranges:

This example omits additional alignment for the constants to isolate the propagation of a size change. Actual layout must recheck alignment, range limits, and segment boundaries as well. A later pass may request another layout iteration; it cannot continue treating the old addresses as final.

Consider main.o calling add defined in add.o. Resolution selects the definition without yet assigning its final address. Layout supplies both that address S and the call field's address P, allowing S + A − P to be written. A relocation that requires another GOT entry can affect section size and layout; the linker must gather that demand before treating addresses as final.

Parallelism distributes independent work within these boundaries. Two workers may read different input sections at once. Writing them concurrently also requires known, disjoint output ranges. Atomic flags address shared state, fixed output ordering addresses determinism, and pass boundaries address dependencies; these are related but different problems.

The scale of the input encourages fewer traversals and copies. The contracts with loaders and runtimes demand a reason for every shortcut. Correct local formulas, invariants between passes, and the rules used by consumers together determine whether the complete tool is reliable.

Correctness can fail far from the link

The kernel, dynamic loader, unwinder, and debugger all interpret bytes written by the linker. Completing the linker's own algorithm is only part of correctness. Its consumers must receive structures that support the promised behavior.

Chapter 1 introduced the glibc⁹ 2.41 change that prevented some existing Steam games and Discord components from loading; Chapter 7 followed the mechanism in ld.so. Years earlier, a linker had emitted an executable PT_GNU_STACK, sometimes because an input lacked .note.GNU-stack. Linking succeeded and the program ran at the time. A later loader policy exposed the old declaration.

An unwinding failure fixed in mold 2.42.1 had a different trigger. Optimization left a zero-length FDE¹⁰ at the same start address as a real function's unwind record. Searching .eh_frame_hdr could find the empty record and miss the exception handler. An exception that should have been caught terminated the program. Release notes, fix

Both failures have the same shape: the link succeeds, ordinary execution works, and a rarely exercised path fails in a component far removed from the linker. A test that merely links and runs Hello World leaves that entire class of errors largely untouched.

Compatibility includes historical mistakes

No single document completely specifies a production linker. The gABI¹¹ and psABI¹² define file structures and relocation rules; many other behaviors are established by implementations and the software built around them.

Executable-stack defaults illustrate the difference. Historical x86 versions of GNU ld could interpret a missing .note.GNU-stack as a request for an executable stack. AArch64, RISC-V, and LoongArch did not all adopt that default. Defaults also change between releases. The backend's elf_backend_default_execstack setting is implementation policy, not an eternal ELF rule. GNU ld provides --error-execstack to turn relevant diagnostics into failures. AArch64 backend

A safer default still raises a compatibility question: does existing software depend on the old behavior? Rust's announcement of its default-linker change explicitly acknowledges that LLD and GNU ld are not bug-for-bug compatible. LLD's archive extraction rules are one deliberate difference. Earlier, gold encountered Linux kernel builds that depended on undocumented script behavior. Rust announcement, Taylor's LFCS 2010 slides

Here is the mixed-input case. Clang supplies .note.GNU-stack for lib.c; the handwritten assembly supplies no stack declaration:

1
// lib.c
2
int fast_add(int, int);
3
int api(int x) { return fast_add(x, 1); }

1
# fast_add.s
2
    .text
3
    .globl fast_add
4
    .type fast_add, @function
5
fast_add:
6
    leal (%rdi,%rsi), %eax
7
    ret
8
    .size fast_add, .-fast_add

1
$ clang -c fast_add.s -o fast_add.o
2
$ clang -O2 -fPIC -c lib.c -o lib.o

Link lib.o and fast_add.o into a shared library with each linker and inspect readelf -lW. In the recorded environment, GNU ld 2.46 and LLD 21 both produced GNU_STACK ... RW; GNU ld used alignment 0x10, and LLD used zero. Giving GNU ld only fast_add.o, with no input stack note at all, produced no GNU_STACK program header. Older GNU ld versions could emit RWE and a deprecation warning for the mixed case. Their already-published binaries remain subject to later loader checks: changing a new linker's defaults does not rewrite old files.

A comparison therefore needs the tool version and the complete input set. It also needs three distinct kinds of evidence: what the specification requires, what the reference implementation does, and what existing software relies on. Those answers can conflict. “The other linker does it” identifies a compatibility target; it does not explain whether the result is correct.

Where the time goes

Compilation is naturally local. A source file can be compiled independently, in parallel, or retrieved from a cache. Linking must make global decisions about references, reachability, and layout. Even a one-line edit can trigger another full link. As compilation gets faster or more cacheable, linking becomes a larger fraction of the build.

LLD's design document gives a useful historical Chrome workload: roughly 17,000 input files, 1.8 million sections, 6.3 million symbols, 13 million relocations, and a 2 GB debug output, linked in about 15 seconds. Symbol-name strings alone occupied 450 MB; inserting them into a hash table took 1.5 seconds. Mold's 2020 design notes describe another Chrome configuration with about 62 million relocations. These are measurements of specific workloads, not universal performance promises. LLD design, mold design

Most relocations perform little arithmetic: obtain a symbol address, apply a formula, and store four or eight bytes. Symbol resolution is dominated by lookup. Against that volume of data, an extra lookup or a larger record matters. Memory layout, copying, and available parallelism often dominate. Algorithmic complexity still matters too: repeated archive scans, suffix merging, ICF¹³, and relaxation can become expensive when a pass revisits too much work.

Four linkers, four sets of tradeoffs

GNU ld inherits BFD's ability to represent many binary formats. Taylor's 2010 comparison counted 13 symbol-table traversals for a typical GNU ld link versus three for gold, and a 156-byte x86-64 symbol record versus gold's 68 bytes. Removing those costs would have meant changing the architecture, not polishing an inner loop. LFCS 2010

Gold specialized in ELF, using C++ templates for word size and endianness. Google's 2008 announcement reported approximately a fivefold improvement over GNU ld. Its optional threading was a further optimization; --threads was disabled by default in the cited implementation. Announcement, gold options

LLD emphasizes avoiding work. It delays reading contents until needed, retains handles after expensive lookups, and updates the resolution of a name through a canonical Symbol object. It also remembers archive symbols it has encountered, allowing a later input to extract a member from an earlier archive. That deliberate difference from traditional left-to-right scanning is why --warn-backrefs matters: it identifies dependencies that might fail with a different linker. LLD design

Mold began with a different hardware opportunity: a machine with 64 cores and 128 hardware threads that existing linkers could not fully use. Its 2020 design aims to establish layout early and approach file-copy speed. The broad structure remains simple: sequential passes, parallel loops within each pass, and atomic flags where threads must record shared facts such as “this symbol needs a GOT entry.” Mold design

Move less data

Memory mapping lets later passes refer directly to input bytes. Symbol names, section contents, and relocation records need not each acquire a private copy. The kernel supplies pages as they are accessed, from storage or the page cache.

Combined with lazy processing, this can avoid copying or inspecting the contents of unextracted archive members and discarded sections. It does not guarantee that none of their pages is physically read: metadata, adjacent data, readahead, or other analysis may touch the same pages. The benefit is avoiding unnecessary processing, not a promise about every storage request.

There are two useful units of parallel work. Files work well for parsing headers, symbols, and relocation tables. Threads can resolve definitions into a concurrent symbol table and atomically record required GOT or PLT entries. Sections provide a finer unit when file sizes are uneven: a single giant object should not monopolize one worker while the others finish. Copying and relocation application can be assigned by section; GC¹⁴ can traverse from multiple roots; ICF can hash sections and refine separate equivalence classes concurrently.

String merging is more than deduplication

Both files below contain the same literal:

1
// a.c
2
int puts(const char*);
3
void a(void){puts("connection reset");puts("ok");}
4
// b.c
5
int puts(const char*);
6
void b(void){puts("connection reset");puts("retry");}

Compile both files before inspecting their sections and relocations. In addition to the a.c command below, run clang -O2 -c b.c -o b.o to create the second object:

1
$ clang -O2 -c a.c -o a.o
2
$ objdump -s -j .rodata.str1.1 a.o
3
Contents of section .rodata.str1.1:
4
 0000 636f6e6e 65637469 6f6e2072 65736574  connection reset
5
 0010 006f6b00                             .ok.
6
$ objdump -s -j .rodata.str1.1 b.o
7
Contents of section .rodata.str1.1:
8
 0000 636f6e6e 65637469 6f6e2072 65736574  connection reset
9
 0010 00726574 727900                      .retry.
10
$ objdump -r a.o        # Excerpt; .eh_frame relocations omitted
11
RELOCATION RECORDS FOR [.text]:
12
OFFSET           TYPE                     VALUE
13
0000000000000004 R_X86_64_PC32            .L.str-0x4
14
0000000000000009 R_X86_64_PLT32           puts-0x4
15
0000000000000010 R_X86_64_PC32            .L.str.1-0x4
16
0000000000000016 R_X86_64_PLT32           puts-0x4

.rodata.str1.1 has the SHF_MERGE and SHF_STRINGS flags. Here the conventional suffix denotes one-byte elements with one-byte alignment. The linker splits the section into zero-terminated pieces and keeps one copy of each equal string.

It must also translate references. An instruction in a.o refers to a position in an input section. After merging, that position has a new output offset; b.o must reach the same retained string. Each input piece therefore needs an output mapping. The same problem applies to .debug_str, potentially at a scale of hundreds of megabytes.

Parallel insertion into a hash table introduces another issue: arrival order depends on scheduling. If arrival order determines placement, the output changes between links. LLD's MergeNoTailSection::finalizeContents partitions strings into a fixed set of hash shards. Each shard processes its assigned strings in input order; the final output concatenates shards in a fixed order. Equal strings reach the same shard. Worker assignment can vary without changing the result. Implementation

Establish sizes before writing bytes

A relocation needs final addresses. Those addresses depend on preceding section sizes, and some sizes depend on global information: the number of required GOT entries, for example, or the surviving FDEs in .eh_frame_hdr.

Separating size computation from final output makes those dependencies explicit. It is a division of responsibilities, not a guarantee of exactly two scans. Relaxation and branch thunks may require repeated layout computation before writing can begin.

Mold's design considered starting ordinary fixed-size sections early and placing variable-size synthetic sections at the end. It rejected the approach: calculating the variable parts cost less than 100 milliseconds in the studied workload, while copying first and relocating later would revisit section contents. With final layout already known, a thread can copy a section and immediately patch its relocations while the data is hot in cache.

Known offsets also give threads disjoint output ranges. With an output mapping, each worker writes directly to its assigned bytes without a lock around every write.

Operating-system costs then become visible. Mold's historical notes report saving roughly 300 milliseconds for a 2 GiB output by overwriting an existing cached file rather than allocating a new one. They also describe using a worker child process so the parent can return after output completion while the kernel finishes costly mapping cleanup. These are workload- and implementation-specific observations, not general reasons to overwrite arbitrary files. Mold design

A parallel fingerprint

Chapter 11 introduced .note.gnu.build-id as the identifier used to pair a binary with separate debugging information. For a content-derived mode, the linker hashes selected output content under a defined policy. The LLD version examined there uses BLAKE3 behind the option names md5 and sha1; uuid instead requests a fresh random value.

A conventional serial hash interface consumes a stream in order. A tree construction can hash independent chunks concurrently and combine their results deterministically. The build-ID field itself also needs a defined treatment; a not-yet-known digest cannot recursively include its final value.

The implementations discussed here divide the output into 1 MiB chunks, hash them in parallel, and hash the ordered collection of chunk digests. That is a two-level Merkle-tree construction.¹⁵ Mold's design reports roughly 60–70 milliseconds for a 2 GiB output on 16 cores. The value differs from a conventional hash of the entire file. Content-derived modes aim for stable identification with a low collision probability; random or explicitly supplied build IDs have different properties. None is, merely by being a GNU build ID, a tamper-proof authenticity claim. Mold design

Parallel computation, deterministic decisions

A reproducible build produces identical bytes from the same source, build environment, and instructions. This makes independent verification of distributed binaries possible. Definition

A serial linker must already control input iteration order, hash randomization, timestamps, environment dependencies, and any ordering derived from addresses. Parallel execution adds more opportunities: string placement, .dynsym order, GOT numbering, and symbol winners can all accidentally depend on which thread arrives first. A content-derived build ID propagates covered differences into the identifier as well.

Weak definitions make the semantic risk concrete. If the rule selects the first weak log_level in input order, selecting the first thread to insert it is wrong. Mold ranks candidate definitions instead:

1
auto get_sym_rank = [&] {
2
  if (esym.is_common()) { ... return is_in_archive ? 6 : 5; }
3
  if (file->is_dso || is_in_archive)
4
    return (esym.st_bind == STB_WEAK) ? 4 : 3;
5
  if (esym.st_bind == STB_WEAK)
6
    return 2;
7
  return 1;
8
};
9
return (get_sym_rank() << 24) + file->priority;

The high bits encode the definition category; the low bits encode file priority. Within the symbol's lock, a lower rank wins. For candidates with defined priorities, scheduling no longer chooses the result. Ties and duplicate strong definitions still require their own checks, and this rank implements mold's chosen semantics—it does not prove equivalence to every other linker's archive behavior. Mold symbol resolution

A basic regression check changes the thread count while keeping everything else fixed:

1
$ ld.lld -shared --threads=1 --build-id=sha1 a.o b.o -o t1.so
2
$ ld.lld -shared --threads=8 --build-id=sha1 a.o b.o -o t8.so
3
$ shasum t1.so t8.so
4
d1b2d47f3d60b104fbaec863e41216d47c99e74a  t1.so
5
d1b2d47f3d60b104fbaec863e41216d47c99e74a  t8.so

A tiny example does not establish determinism for a large project. Repeat this kind of check across demanding inputs and schedules.

The string shards and symbol ranks embody the same principle: parallelize the computation, but derive decisions from stable input properties. Chunk hashing uses a related pattern: parallel reduction followed by ordered combination. Determinism also makes failures debuggable. A failure that appears in only one of ten otherwise identical links is much harder to isolate.

How to test a result with no unique byte representation

Two correct linkers can place main at different addresses, order sections differently, and choose different GOT indices. A golden output file therefore cannot be the sole oracle. A useful test suite has several layers, each answering a different question.

Follow one defect across the evidence layers

Consider an x86-64 call rel32 starting at 0x401000. Its four-byte displacement field begins at P = 0x401001, and the selected function answer is at S = 0x401020. With relocation addend A = −4, the correct calculation is:

1
S + A − P = 0x401020 − 4 − 0x401001 = 0x1b
2
Instruction bytes: e8 1b 00 00 00
3
Next instruction address: 0x401005
4
Decoded call target: 0x401005 + 0x1b = 0x401020

Mistaking the next instruction address for P produces 0x17 instead. The CPU then calls 0x40101c, four bytes before the function. No ELF header, program header, or segment size needs to change: the defect fits inside one field of an otherwise valid code segment.

The example puts _start and answer in separate objects; answer returns 42. It fills the gap before the function with 0xcc (int3), then perturbs the correct output's call field to make the wrong version. The wrong call therefore traps rather than accidentally traversing padding and reaching the function anyway. This checks whether the observations distinguish these two outputs; it is not a claim that all linker defects have been tested.

From the repository root on native x86-64 Linux, the commands above rebuilds and checks both outputs. It distinguishes normal exit from signal termination through subprocess status rather than treating any nonzero exit as a crash.

Each observation has a separate responsibility. Structural checks protect file and mapping boundaries; field checks establish reference semantics; execution tests the path taken by a consumer; determinism checks repeated builds. A differential test that gives a reference implementation the candidate's wrong target address can even produce agreement. An independent expectation is still needed: here it is the selected definition of answer, rather than the target asserted by the candidate output.

Structural invariants

First separate format requirements from implementation choices. For PT_LOAD with p_align > 1, p_offset and p_vaddr must be congruent modulo that alignment. p_filesz cannot exceed p_memsz, and the described file range must be valid. Do not use p_align == 0 or 1 as though all cases required a modulo operation.

An implementation that selects _start, separates permissions onto distinct pages, or provides __stop_x can assert those declared choices. They verify its layout contract, not universal ELF axioms. ELF permits another explicit entry point; a section can be described by both PT_LOAD and PT_TLS; and NOBITS occupying no file bytes does not require its numeric sh_offset to fall outside every file-backed range.

An assertion needs a stated scope and a reason. Valid sizes and alignments still cannot prove that a call displacement is correct.

Execute the difficult paths

Execution checks the effect of the final bytes, but only along the paths actually taken. Deliberately exercise exceptions caught several frames away, TLS accessed by multiple threads, and functions reached through dlopen.

The environment is part of the test. Changing the code segment from R+X to R caused a native x86-64 Linux execution to receive SIGSEGV; the shell reported status 139. A tool being able to parse the file does not make its permissions executable. Check both readelf -lW and the actual outcome.

A user-mode emulator has its own loader behavior, which varies with implementation and version. This series therefore runs its main ELF experiments through the Linux kernel. Chapter 15's static Mach-O and PE inspection provides evidence about file structure, not about a foreign operating system's loading or signature policy.

Compare semantics against a reference

Differential testing feeds the same inputs to the implementation under test and a reference linker. Compare meaningful properties: relocation targets and addends, dynamic symbols and tags, segment permissions, and unwind coverage. Raw addresses may legitimately differ.

String merging provides a small example:

1
$ ld.lld -shared a.o b.o -o ab.so
2
$ readelf -p .rodata ab.so
3
  [     0]  connection reset
4
  [    11]  retry
5
  [    17]  ok
6
$ ld.bfd -shared a.o b.o -o ab_bfd.so
7
$ readelf -p .rodata ab_bfd.so
8
  [     0]  connection reset
9
  [    11]  ok
10
  [    14]  retry

Both outputs contain one copy of connection reset. The positions of ok and retry differ because of the layout strategy. The right question is whether each reference reaches the intended string.

The source of comparison addresses matters. One approach reads the tested linker's layout and makes the reference linker use it. Matching S and P isolate relocation arithmetic, but a wrong layout shared by both can escape detection. Entry offsets and local-symbol values also need independent structural assertions and execution cases.

A different approach lets the reference linker choose its own layout and compares program headers, symbols, and section contents through semantic relationships. This adds an independent choice, but the reference layout is not the only valid answer. Document intentional differences and test that each still satisfies the required constraints.

Errors are observable behavior

Build scripts parse diagnostics too. The NYU teaching-linker specification describes 11 error and warning rules: a syntax error stops processing; the others define both the diagnostic and recovery behavior, such as retaining the first duplicate definition or assigning zero to an unresolved name. Its grader compares output with diff -b -B -E. RUC's LinkLab specifies expected exit status and stderr patterns in TOML; a strong-symbol conflict must return 1 and match the required diagnostic. NYU assignment, LinkLab

Diagnostics are observable output. Tests can specify expected status and stderr exactly, including silence on valid input; an unexpected warning may be a regression even when linking succeeds.

Test the tests

Passing tests establishes agreement with the written expectations. It does not show what those expectations missed. Michigan's EECS 370 linker assignment makes that visible by assessing student tests against deliberately faulty linker implementations. This is mutation testing.¹⁶ Assignment

A distinguishing input must make the correct and faulty rules produce different results. More assertions cannot distinguish implementations that happen to agree on every existing input. Derive small cases from representative defects:

The relocation case tests arithmetic and encoding without requiring an actual high-address load. The padding case derives from f + d ≡ v (mod page): the smallest nonnegative correction is d = (v − f) mod page. An implementation using a power-of-two mask must express the subtraction safely under its arithmetic model. Other segment and section alignment requirements still apply.

These cases observe input-order invariance, field width, congruence, and execution semantics. Introduce one meaningful source defect at a time so a failure can be attributed to it; a mutation that merely prevents compilation has not tested linking correctness. Detection is conventionally called killing a mutant. A survivor may be equivalent to the original implementation, so survival requires analysis rather than automatically proving a coverage gap. The conclusion remains bounded by the chosen defect models, however many are detected.

Production test suites

LLD commonly uses LLVM¹⁷ lit and FileCheck.¹⁸ A test's RUN: lines assemble input with llvm-mc, invoke ld.lld, and send an inspection tool's output to checks embedded in comments. Many such tests never execute the product. Mold uses shell tests that compile inputs, check structures with tools such as readelf, and also run programs, with a $QEMU wrapper where configured. GNU ld uses DejaGnu: many .d tests declare inputs, link options, a dump tool, and regular expressions consumed by run_dump_test. LLD example, FileCheck, mold example, GNU ld example, dump-test driver

The framework is secondary. What matters is the contract represented by each expectation, whether expressed as a binary structure, a textual dump, an exit status, or program output.

Inputs nobody thought to write

Input mutation and source mutation are different experiments. Source mutation deliberately changes the implementation to evaluate test sensitivity. Input mutation keeps the implementation and changes bytes or combinations to examine robustness. Each needs replay, but records a different object.

A malformed-input check has at least three outcomes: accepted, normally rejected, or implementation failure. Returning a specified error is a successful robustness path. Panics, signals, timeouts, and resource-budget exhaustion require separate records. Collapsing every unsuccessful result into one category loses the distinction; suppressing an error is not a repair.

Mutation does not guarantee invalidity. It may touch padding, change a value to another valid value, or write back the original bytes. A robustness survey must not demand rejection of every mutation. Separate normal termination and memory safety from the semantic validity of accepted output. Outcome counts examine the first question; decoded records, structural invariants, and execution oracles for runnable cases examine the second.

Counts should also reconcile. If each of N calls returns or produces a caught failure, accepted + rejected + caught failures = N. This catches missed accounting, duplicate calls, and panics misclassified as rejections; it does not prove accepted output correct. Requiring at least one rejection shows an error path was reached, but rejecting every input also meets that condition. Validate supported, unmodified samples before drawing conclusions from the survey.

For deterministic replay, preserve the initial seed, corpus order, generator and mutation-rule versions, failing iteration, and selected input. Different mutation operations may consume different numbers of random draws. Reseeding and mutating only the failing sample may therefore produce different bytes. Replay the preceding draws or save the failing files directly. Saved inputs also support reduction: remove irrelevant material while preserving the same failure to obtain a smaller counterexample.

Rust’s catch_unwind catches unwinding panics, not panic=abort, process signals, infinite loops, or allocation exhaustion. Investigating those failures requires subprocess isolation, time and resource budgets, and recorded exit information. The panic hook is process-global: a harness that temporarily replaces it must restore it and avoid concurrent hook changes. The catch_unwind documentation explicitly distinguishes unwinding from aborting.

Fuzzing explores malformed inputs beyond hand-written cases. Start by truncating a valid object at every shorter length, then mutate multiple samples with a fixed seed and exercise parsing, symbol selection, and linking. Record acceptance, rejection, and reached stages: rejecting everything at the magic check provides little evidence about later code.

Csmith provides a complementary model: generate C programs that avoid UB¹⁹, compile them with different compilers, and compare executions. Its PLDI 2011 paper reported more than 325 previously unknown compiler bugs. For a linker, generate groups of mutually referencing objects, link them in different ways, and compare behavior. That combines generated inputs with a differential oracle. Paper, Csmith

Diagnose the decision behind the symptom

The linker author asks whether the implementation is correct. The user often starts with a harder observation: linking succeeded, but the program behaves incorrectly. The following table gives a first inspection step, not an exhaustive diagnosis.

The distance between symptom and cause is the recurring difficulty. Often the linker applied its rules correctly to surprising inputs. Find the decision that produced the result, then identify the input that caused that decision.

A practical investigation sequence

First separate link-time decisions from runtime ones. Ask the linker where contents went with -Map, why a member entered with --why-extract, which inputs referenced or defined a name with -y name, and why a symbol remained live with LLD's --why-live.

For runtime decisions, glibc's LD_DEBUG=libs, bindings, and versions trace library search, symbol binding, and version selection. Musl²³ does not provide this glibc tracing interface. Reproduce under glibc when that comparison is meaningful, or inspect the relevant GOT entries and loader state in GDB; changing runtimes is itself a change to the experiment.

Then inspect the bytes. Use readelf -r for the requested relocations and objdump -d for their actual effect. Calculate a suspicious relocation manually. In GDB, info symbol address identifies the containing symbol and x/i decodes the instruction.

Finally, reduce the problem. Compare GNU ld, LLD, and mold; a changed result can identify a compatibility boundary, though it does not by itself identify the guilty implementation. Disable one optimization at a time—LTO, section GC, ICF. Chapter 12's assembly-only reference to helper2 is a useful example of a failure isolated by removing LTO. Bisect inputs or compilation choices. Before doing so, LLD's --reproduce can capture the original link inputs and invocation in a tar archive.

Why is this function still here?

main calls only the first entry in a table:

1
// main.c: uses only handlers[0]
2
typedef void (*handler)(void);
3
extern handler handlers[];
4
int main(void) { handlers[0](); return 0; }

1
// handlers.c: the second table entry is the debug function
2
void on_read(void) {}
3
void debug_dump(void) {}
4
void (*handlers[])(void) = { on_read, debug_dump };

1
$ clang -O2 -ffunction-sections -fdata-sections -c main.c handlers.c
2
$ ld.lld -e main --gc-sections --why-live='debug_*' main.o handlers.o -o live
3
live symbol: handlers.o:(debug_dump)
4
>>> referenced by: handlers.o:(handlers)
5
>>> referenced by: main.o:(main) (entry point)

The diagnostic chain reads from the bottom upward: entry main references handlers, whose section contains a relocation to debug_dump. GC follows sections and relocation edges, not the runtime index used to access a table. As long as the whole table remains live, both addresses remain references.

--print-gc-sections tells you what was removed. --why-live answers the opposite question. To eliminate the debugging function, separate the table data or include that entry only in debug builds. This example uses main as a diagnostic root; the directly linked live file has no ordinary C startup path and is not a demonstration of a runnable C executable.

Why did this definition win?

The application supplies a weak default of 1. An archive member supplies a strong value of 3:

1
// app.c: a weak default for log_level
2
#include <stdio.h>
3
int log_level __attribute__((weak)) = 1;
4
void net_init(void);
5
int main(void) {
6
    net_init();
7
    printf("log_level = %d\n", log_level);
8
    return 0;
9
}

1
// net.c: an archive member with a strong definition
2
int log_level = 3;
3
void net_init(void) {}

1
$ musl-gcc -O2 -c app.c net.c
2
$ ar rcs libnet.a net.o
3
$ nm -A app.o net.o | grep log_level
4
app.o:0000000000000000 V log_level
5
net.o:0000000000000000 D log_level
6
$ musl-gcc -static -fuse-ld=lld -Wl,--no-dynamic-linker app.o -L. -lnet -o app \
7
    -Wl,-y,log_level -Wl,--why-extract=why.txt
8
app.o: definition of log_level
9
./libnet.a(net.o): definition of log_level
10
$ grep -v libc.a why.txt
11
reference	extracted	symbol
12
app.o	./libnet.a(net.o)	net_init
13
$ ./app
14
log_level = 3

This example requires a static program that starts without a dynamic interpreter. It explicitly passes --no-dynamic-linker and checks that readelf -lW app shows no PT_INTERP. Driver options and the output contract provide different evidence: a wrapper can pass both static-link options and an interpreter path, and linkers can handle that combination differently. musl-gcc -### exposes the actual arguments; program headers describe the startup path the kernel will use. The musl project has discussed this wrapper/linker interaction. Diagnose the output and its startup obligations rather than inferring every runtime condition from the word -static.

The excerpt filters the many libc archive rows from why.txt. nm marks the application's log_level as V, a weak object, and the archive definition as D. Symbol tracing reports both definitions. Extraction tracing supplies the missing cause: app.o needed net_init, so the entire net.o member entered the link. Its strong log_level then replaced the weak definition.

Remove the call to net_init and the member no longer enters; the program prints 1. A change unrelated to the setting's declaration changes its value. The trace makes that indirect dependency visible.

A growing set of responsibilities

The link step sees multiple modules at once, so it becomes a natural place to coordinate new cross-module decisions. Every added responsibility expands the proof required of the implementation.

Driving the optimizer

With LTO, some .o inputs contain LLVM bitcode or GCC intermediate representation. Through an embedded compiler or plugin interface, the linker obtains their symbols, resolves them alongside native objects, communicates which definitions must survive, and resumes linking when the compiler produces machine code.

A failure exclusive to LTO can therefore arise in symbol resolution, in the preservation decisions communicated to the optimizer, or in optimization itself. The assembly-only helper2 call from Chapter 12 crosses exactly that boundary. ICF introduces another obligation: respect observable function identity while keeping unwind and debug metadata consistent.

Hardware properties must survive the whole input set

AArch64 BTI and x86 IBT constrain checked indirect branch targets. On x86 the landing instruction is endbr64; AArch64 has compatible landing instructions, including relevant PAC instructions in some cases, rather than only the literal bti mnemonic. Shadow stacks preserve an additional return-address history; x86 SHSTK and IBT are components of CET. AArch64 has GCS, while PAC authenticates pointers such as return addresses.²⁴

Compiler options influence both generated instructions and property declarations. Runtime enforcement additionally depends on the CPU, kernel, and loader. The declarations examined here use an AND-style merge: the linker conservatively combines the participating inputs' stated compatibility.

1
// p.c
2
int f(void){return 1;}

1
$ clang -O2 -fcf-protection=full -c p.c -o p_cet.o
2
$ objdump -s -j .note.gnu.property p_cet.o
3
Contents of section .note.gnu.property:
4
 0000 04000000 10000000 05000000 474e5500  ............GNU.
5
 0010 020000c0 04000000 03000000 00000000  ................
6
$ objdump -d p_cet.o
7
0000000000000000 <f>:
8
       0: f3 0f 1e fa                  	endbr64
9
       ...
10
$ clang --target=aarch64-unknown-linux-gnu -O2 -mbranch-protection=standard -c p.c -o p_bti.o
11
$ objdump -s -j .note.gnu.property p_bti.o
12
Contents of section .note.gnu.property:
13
 0000 04000000 10000000 05000000 474e5500  ............GNU.
14
 0010 000000c0 04000000 07000000 00000000  ................

The AArch64 command generates a comparison object for static inspection on the Linux host; it is not an AArch64 execution test.

Decode the note as little-endian fields: name size 4, descriptor size 0x10, type 5 (NT_GNU_PROPERTY_TYPE_0), and name GNU\0. The x86 descriptor has type 0xc0000002, GNU_PROPERTY_X86_FEATURE_1_AND, four data bytes, and value 3: IBT in bit 0 plus SHSTK in bit 1. The AArch64 descriptor uses 0xc0000000, GNU_PROPERTY_AARCH64_FEATURE_1_AND, with value 7 for BTI, PAC, and GCS. LLVM ELF constants

For this property class, a missing input bit removes the corresponding compatibility claim from the default merge. Runtime activation remains a separate platform decision. Link the marked object with the unmarked assembly:

1
$ ld.lld -shared p_cet.o -o cet_ok.so
2
$ readelf -nW cet_ok.so | grep Properties
3
  GNU                  0x00000010	NT_GNU_PROPERTY_TYPE_0	      Properties: x86 feature: IBT, SHSTK
4
$ ld.lld -shared p_cet.o fast_add.o -o cet_mix.so
5
$ readelf -nW cet_mix.so | grep Properties
6
$ ld.lld -shared -z cet-report=warning p_cet.o fast_add.o -o cet_mix.so
7
ld.lld: warning: fast_add.o: -z cet-report: file does not have GNU_PROPERTY_X86_FEATURE_1_IBT property
8
ld.lld: warning: fast_add.o: -z cet-report: file does not have GNU_PROPERTY_X86_FEATURE_1_SHSTK property

The second link silently loses both properties. A tiny assembly input changes the declaration for the entire output, much as a missing stack note affected the earlier example.

Linker-generated code must comply too. An IBT-compatible PLT needs suitable landing instructions. LLD's -z force-ibt and -z force-bti can force the output property and appropriate PLT construction despite missing input declarations, issuing warnings. -z cet-report=warning|error identifies x86 inputs missing the expected properties. None of these options inspects and repairs every arbitrary assembly function. LLD options

New sections bring new edge cases

SFrame and CREL add more than parsing work. The linker must decide how new contents participate in GC, merging, script placement, and empty-section handling. Mold 2.42.1 fixed rejection of empty .sframe sections emitted for Ubuntu 25.10 glibc startup files. A producer's valid edge case had crossed an implementation assumption. Release notes

What Rust can—and cannot—change

Mold's 2.42.1 announcement described a Rust rewrite planned for 3.0, arguing that a tool expected to last decades was still young enough to justify the change. It also stressed preserving existing users' trust. That is an announced direction, not a claim that a replacement had already shipped. Announcement

The input boundary makes memory safety particularly relevant. GNU binutils²⁵ has traditionally assumed trusted inputs, an assumption that is uncomfortable when build systems consume third-party binary libraries. A concrete example is CVE-2026-15003: processing a crafted 32-bit XCOFF object could use an unvalidated field as an array index, causing an out-of-bounds read. Binutils security policy, Ubuntu's input-safety note, Red Hat advisory

The pass structure also suits ownership-based design: much data becomes immutable after an earlier stage, then can be shared across workers. Safe Rust helps enforce the absence of data races. Mapping a file still commonly involves an unsafe contract because outside processes can modify the backing bytes; the caller must establish the required conditions.

Memory safety does not establish linker correctness. A locked hash table that lets the first arriving weak definition win is legal safe Rust and can still be nondeterministic. Writing the wrong relocation value or retaining an empty unwind record is a semantic error regardless of the implementation language. The testing obligations above remain.

The threshold for becoming the default

Speed alone does not make a linker a system default. Gold's early gains did not remove the need to build kernels and glibc correctly, including undocumented script behavior. After binutils 2.44 deprecated gold, Fedora, Swift, and Apache Arrow discussed moving away from it. Taylor's slides, Fedora, Swift, Arrow

Successful default changes include FreeBSD 12.0's adoption of LLD as /usr/bin/ld and Android NDK r22's adoption of LLD, alongside the Apple and Rust changes discussed in Chapter 1. These ecosystems have an organization able to coordinate toolchain changes and repair affected builds. Rust's default change applies to its officially distributed toolchains and the relevant target configuration, not every independently built Rust installation. FreeBSD toolchain update, NDK r22, Rust change

A Linux distribution integrates thousands of independently maintained projects. Replacing /usr/bin/ld means taking responsibility for that combined set of build assumptions. Linker scripts make the problem tangible: on typical GNU/Linux development systems, a path such as /usr/lib/x86_64-linux-gnu/libc.so can name a text script rather than an ELF shared object. Even a userspace-focused linker needs some script support. Kernels and firmware need much more. Mold design

The mold 3.x plan explicitly makes missing script features and distribution compatibility work prerequisites for broader adoption as /usr/bin/ld. That work is a different engineering investment from shortening a hot loop. Release roadmap

Incremental linking adds history to the problem

When a full link approaches the cost of copying its output, another possible improvement is to reuse the previous result and process only changes.

MSVC's /INCREMENTAL, normally enabled with /DEBUG, reserves padding and uses jump thunks when code moves; it stores state in an .ilk file. Options such as /OPT:REF and /OPT:ICF, or changes to the object-file set, can require a full link instead. Microsoft documentation

Gold explored --incremental in the early 2010s. Coutant's 2012 presentation describes reserving 10% patch space per section, foregoing SHF_MERGE deduplication, and consequently much larger debug strings—about ten times the size in the discussed case. Its design also conflicted with section GC and the LTO plugin. LFCS 2012

The difficult dependency is not always local. Suppose a program defines malloc, overriding the library implementation. Removing that definition can cause an archive member to enter, which introduces more references and extracts more members. A small source edit creates a global binary change. This was one reason mold's original design prioritized fast full links. Its later roadmap leaves room for incremental linking if a sufficiently simple, reliable design emerges. Original design, later roadmap

Reusing old work requires evidence that all affected dependencies have been reconsidered. Reserved space and thunks make incremental output differ from a fresh full link, so byte equality is usually the wrong requirement. The useful promise is functional equivalence under a stated model.

That adds a new test dimension: sequences of edits. Compare each incremental result with a full link of the same current inputs, normalize permitted layout differences, and exercise the behavior. Testing one static input set cannot establish that every path from an old state to a new one updates the right information.

Reading a real linker after building a small one

A linker engineer needs several habits together: read specifications and recognize where they stop; decode binary structures with readelf and objdump²⁶; calculate relocation values, CIE²⁷ pointers, and property bits by hand; trace distant runtime failures back to the bytes that caused them; and design tests that challenge every optimization's assumptions.

The series began with cc main.c add.c. A declaration described how to call a function, an object retained an unresolved reference, and the linker connected it to a definition. The later int x versus extern double x example exposed the limit: matching symbol names do not establish matching C types. LTO can improve diagnostics, but it cannot turn UB into a valid program.

That same distinction runs through everything since. Layout must satisfy the loader, unwind records must support real exception paths, TLS addressing must agree with runtime allocation, and parallel execution must preserve specified symbol selection. Each new capability needs matching evidence: structural assertions, execution, explained differences, error specifications, mutation tests, and fuzzing that reaches beyond the parser.

You can now read a production pipeline with concrete questions in mind. In LLD, LinkerDriver::link calls passes such as markLive, doIcf, and writeResult. In mold, mold_main leads through resolve_symbols, gc_sections, scan_relocations, compute_section_sizes, and copy_chunks. The architecture is recognizable from the seven steps at the beginning. LLD Driver.cpp, mold main.cc

Start with one operation you have calculated yourself: PC32, perhaps, or an .eh_frame_hdr entry. Find the implementation, then follow its history to a bug report that changed it. At that point the most useful question is precise: which test layer would have caught the earlier implementation before somebody's program failed?

Exercises

1. Observe. Link the diagnostic main.c and handlers.c with --why-live=on_read. Identify the chain retaining on_read. Add -Map=- and locate its output address. Does the map explain why it survived?
2. Predict. Remove the net_init() call from app.c, leaving everything else unchanged. Recompile, rebuild the archive, and relink. Predict the printed value and whether --why-extract will still report net.o, then verify.
3. Break and repair. Link p_cet.o with fast_add.o using -z cet-report=error. After observing failure, add a handwritten .note.gnu.property to the assembly so the same command succeeds and reports IBT and SHSTK. Is adding the declaration sufficient without changing instructions?

Further reading

• John R. Levine, Linkers and Loaders (1999). Some implementation details have aged, but the conceptual framework remains useful. The author's site includes draft chapters.
• Ian Lance Taylor's 20-part linker series, beginning in August 2007, follows the mechanisms from basic linking through relocations, shared libraries, symbol versions, and TLS. Part 1
• MaskRay's articles examine ELF, relocation, unwinding, TLS, CREL, SFrame, and differences between implementations.
• The specifications: System V gABI, x86-64 psABI, Arm ABI documents, DWARF 5, and Itanium C++ exception handling ABI.
• Mold's design notes, written in 2020 with an explicit warning that parts have aged, and the LLD design document.
• Coutant's incremental-linking presentation, read alongside mold's original reasons for prioritizing full links.
• Yang et al., Finding and Understanding Bugs in C Compilers, on UB-free generated tests and reducing failures.

Answers

1
$ clang -O2 -ffunction-sections -fdata-sections -c main.c handlers.c
2
$ ld.lld -e main --gc-sections --why-live=on_read main.o handlers.o -o live
3
live symbol: handlers.o:(on_read)
4
>>> referenced by: handlers.o:(handlers)
5
>>> referenced by: main.o:(main) (entry point)
6
$ ld.lld -e main --gc-sections -Map=- main.o handlers.o -o live | grep -E 'on_read|handlers|main'
7
          2001c8           2001c8       30     1         main.o:(.eh_frame+0x0)
8
          2001f8           2001f8       28     1         handlers.o:(.eh_frame+0x18)
9
          201230           201230        e    16         main.o:(.text.main)
10
          201230           201230        e     1                 main
11
          201240           201240        1    16         handlers.o:(.text.on_read)
12
          201240           201240        1     1                 on_read
13
          201250           201250        1    16         handlers.o:(.text.debug_dump)
14
          203260           203260       10    16         handlers.o:(.data.handlers)
15
          203260           203260       10     1                 handlers

1
$ musl-gcc -static -fuse-ld=lld -Wl,--no-dynamic-linker app.o -L. -lnet -o app2 \
2
    -Wl,-y,log_level -Wl,--why-extract=why.txt
3
app.o: definition of log_level
4
$ grep -v libc.a why.txt
5
reference	extracted	symbol
6
$ ./app2
7
log_level = 1

1
$ ld.lld -shared -z cet-report=error p_cet.o fast_add.o -o mix.so
2
ld.lld: error: fast_add.o: -z cet-report: file does not have GNU_PROPERTY_X86_FEATURE_1_IBT property
3
ld.lld: error: fast_add.o: -z cet-report: file does not have GNU_PROPERTY_X86_FEATURE_1_SHSTK property

1
fast_add:
2
    endbr64
3
    leal (%rdi,%rsi), %eax
4
    ret
5
    .size fast_add, .-fast_add
6

7
    .section .note.gnu.property,"a",@note
8
    .p2align 3
9
    .long 4                 # n_namesz: "GNU\0" occupies 4 bytes
10
    .long 16                # n_descsz: one property, padded to 16 bytes
11
    .long 5                 # n_type: NT_GNU_PROPERTY_TYPE_0
12
    .asciz "GNU"
13
    .long 0xc0000002        # GNU_PROPERTY_X86_FEATURE_1_AND
14
    .long 4                 # pr_datasz
15
    .long 3                 # IBT | SHSTK
16
    .p2align 3              # Pad pr_data to an 8-byte boundary
17

18
    .section .note.GNU-stack,"",@progbits

1
$ clang -c fast_add_cet.s -o fast_add_cet.o
2
$ objdump -s -j .note.gnu.property fast_add_cet.o | tail -2
3
 0000 04000000 10000000 05000000 474e5500  ............GNU.
4
 0010 020000c0 04000000 03000000 00000000  ................
5
$ ld.lld -shared -z cet-report=error p_cet.o fast_add_cet.o -o fixed.so
6
$ readelf -nW fixed.so | grep Properties
7
  GNU                  0x00000010	NT_GNU_PROPERTY_TYPE_0	      Properties: x86 feature: IBT, SHSTK

1
$ ld.lld -shared -z force-ibt p_cet.o fast_add.o -o force.so
2
ld.lld: warning: fast_add.o: -z force-ibt: file does not have GNU_PROPERTY_X86_FEATURE_1_IBT property
3
$ readelf -nW force.so | grep Properties
4
  GNU                  0x00000010	NT_GNU_PROPERTY_TYPE_0	      Properties: x86 feature: IBT

Notes on the exercises

The exercise design combines CS