[The World of Linkers—Theory 01] The Long Road from Names to Addresses

A square-root routine can be mathematically correct and still fail when someone reuses it. Put its instructions after a different program, and every address written into those instructions may point to the wrong place.

This is the problem that gives linking its shape: what code means must survive a change in where code lives. The history of linkers is a succession of increasingly demanding versions of that problem. Separate compilation introduces names whose definitions are elsewhere. Shared libraries postpone some addresses until execution. Exceptions, debuggers, and security mechanisms introduce other consumers of the final layout.

We will follow those dependencies, then reduce them to a ten-word program small enough to link on paper.

Reusable code needs movable addresses

In 1949, EDSAC programmers began collecting useful routines on paper tape. A routine appended to one program would begin at a different memory location from the same routine appended to another. Absolute addresses made that library difficult to reuse.

David Wheeler's Initial Orders 2 solved this with an extraordinarily small assembly-and-loading program: 41 instructions. A routine could express an address relative to its own beginning; the loader added the location at which that routine was actually placed. The EDSAC material at Clemson documents this early arrangement.

That adjustment is relocation. The representation preserves enough information to compute an address after placement. Modern relocation records are more expressive, but they answer the same question.

Counting offsets by hand soon becomes another obstacle. Assembly languages give locations names. Instead of counting the bytes before a loop, the programmer writes a label and refers to it. A basic assembler can make one pass to determine locations and build a symbol table, then another to encode references. Real assemblers may revisit layout because instruction lengths, alignment, and branch ranges interact; two passes are the useful starting model, not a universal implementation rule.

An assembly file also contains instructions to the assembler:

1
    .section .text.add,"ax",@progbits   # select .text.add: allocated and executable
2
    .globl add                          # export the name add
3
add:
4
    leal (%rdi,%rsi), %eax              # x86-64 integer arguments in rdi/rsi; result in eax
5
    retq
6
    .section .rodata                    # select read-only data
7
msg:
8
    .asciz "hello"                      # emit hello followed by a zero byte

The CPU executes leal and retq. It never executes .section, .globl, or .asciz. Those directives organize bytes and describe names. Theory 02 examines that distinction in detail.

Separate compilation leaves promises in the object file

Putting everything in one assembly file makes every edit expensive and collaboration awkward. Once routines can be translated separately—as in FORTRAN II's subroutine model—the assembler must handle a new situation: a call names a function whose implementation is in another file.

The answer is an intermediate product: an object file. It contains machine code, a symbol table recording definitions and unresolved names, and relocation records describing fields that cannot yet receive their final values. Their placeholder bytes need not all be zero.

A linker collects those files, matches references with definitions, lays out the surviving content, and evaluates the relocations. IBM called the tool a linkage editor in the 1966 OS/360 manual. Early Unix manuals variously described ld¹ as a link editor or loader. Historical terminology overlaps; in this series, linking constructs the output file, while loading establishes its runtime image.

Here is a small modern example:

1
// main.c
2
int add(int a, int b);   // declaration; the definition is in add.c
3
int counter = 1;
4
int main(void) { return add(counter, 2); }

Compile on native x86-64 Linux with Clang², then inspect it with GNU³ objdump⁴. The following is an excerpt; formatting varies between tool versions.

1
$ clang -O1 -c main.c
2
$ objdump -t main.o
3
0000000000000000 g     F .text   0000000000000010 main
4
0000000000000000 g     O .data   0000000000000004 counter
5
0000000000000000         *UND*   0000000000000000 add
6

7
$ objdump -d main.o
8
   0: 8b 3d 00 00 00 00     movl  (%rip), %edi
9
   6: be 02 00 00 00        movl  $0x2, %esi
10
   b: e9 00 00 00 00        jmp   0x10
11

12
$ objdump -r main.o
13
OFFSET           TYPE              VALUE
14
0000000000000002 R_X86_64_PC32     counter-0x4
15
000000000000000c R_X86_64_PLT32    add-0x4

The symbol table says that main is a global function, counter a global data object, and add undefined in this object. At -O1, the final call becomes a tail jump. Two four-byte fields await relocation: one for the load of counter, one for the transfer to add.

For R_X86_64_PC32, the essential calculation is $S+A-P$: symbol address, plus addend, minus the address of the relocation field. The processor, however, interprets the displacement relative to the next instruction. In these particular instructions the field occupies the last four bytes, so an addend of −4 reconciles the two reference points. It is not a rule that every PC-relative instruction always needs −4; bytes following the field can change the correction. The PLT32 record shown here uses the corresponding relative calculation for a call target. We will return to PLT⁵ routing when shared libraries enter the picture.

Moving both ends of a PC-relative reference equally preserves their distance. That observation explains why some references need no load-time patch. It does not prove that an entire program is position independent.

A reusable library can now be an archive of object files. Normally the linker extracts members needed to resolve outstanding references, rather than copying the entire archive. Options that request whole-archive inclusion change that policy. The archive mechanism turns symbol resolution into a discovery process: a newly extracted member may introduce more unresolved names.

One file, two views

Early Unix a.out files had a compact, relatively fixed layout. The Unix V6 header consisted of eight 16-bit words describing text, initialized data, zero-initialized storage, and related information. As toolchains acquired read-only constants, richer debugging information, and additional metadata, a few fixed regions became restrictive.

COFF⁶ made named sections a more general organizing unit. ELF⁷, developed for System V Release 4 and standardized through the 1990s, carried that extensibility forward while distinguishing two readers:

The section header table serves the first view. The program header table serves the second, grouping content into loadable segments and describing other runtime requirements. A relocatable object normally has the former. A conventional executable normally has both, but the operating system does not need an offline section inventory merely to execute its loadable image.

The distinction will matter throughout the series: a section is not a segment with a different spelling. ELF also inherited historical naming variations—Extensible Linking Format and Executable and Linking Format appear in older material; Executable and Linkable Format is the familiar modern expansion. The generic ABI is the reference for the actual structures.

Shared code moves some binding into the running process

If every executable incorporates its own library implementation, many processes carry copies of almost the same code. Sharing those bytes requires separating reusable instructions from addresses that vary by process.

Multics tackled this before Unix shared libraries. Its segmented addressing hardware gave each process an address space in which a shared procedure could receive a different segment number. The procedure therefore used a private linkage section for external addresses. Another process could share the procedure's instructions while owning a different linkage section.

An unresolved linkage entry encoded a special pointer and the target name. On first use, hardware trapped to the dynamic linker. It found the target, replaced the unresolved entry with a usable pointer, and resumed execution. Later uses followed the resolved pointer. Multics segments were hardware addressing units, not ELF program-header segments.

J. H. Saltzer's Naming and Binding of Objects explains both this mechanism and the naming context around it. The reference-name table recorded procedures already available in an address space; search rules could then consider directories associated with the caller, the current directory, and libraries. Because resolution occurred on use, an unexecuted path could refer to a routine that was never present. See the MIT-hosted edition's printed pages 94 and 100–103 for the linkage mechanism.

Saltzer also provides a useful interpretation of traditional static linking: it constructs a context mapping names to objects. Library extraction extends that context when a name cannot yet be resolved. Two conflicting definitions compete in that context. Modern partial linking with ld -r adds a capability absent from the simple historical model: the output can remain relocatable and participate in another link.

Unix needed a solution without Multics' special unresolved-pointer trap. Gingell and colleagues' 1987 SunOS shared-library paper, followed by SunOS 4.0, describes the family of mechanisms familiar on ELF systems:

• PIC⁸ avoids baking process-specific absolute addresses into shared instructions.
• The GOT⁹ holds address-dependent data separately, so each process can receive its own resolved values.
• PLT stubs transfer external function calls through a binding mechanism. With lazy binding, the first call reaches the dynamic linker; subsequent calls use the resolved destination.

A PLT stub uses ordinary instructions where Multics used a hardware trap. The private GOT plays a role analogous to private linkage data. The analogy explains the design, but the formats and exact rules are different.

Earlier fixed-address Unix shared libraries imposed another constraint: libraries had to agree in advance on nonconflicting load locations. Position-independent code and runtime binding remove much of that constraint. ELF records the libraries to load, symbols to resolve, and relocations to apply; ld.so consumes that information. A process can also request a library later with dlopen.

The static linker's output is now partly a program and partly a set of instructions for another linker running at startup or later.

A debugger asks questions the CPU never asks

An instruction address does not identify a source line by itself. Nor does a register value announce the source variable it currently represents. The compiler must supply that relationship explicitly.

DWARF¹⁰ describes source locations, types, variables, and machine-level locations. Its name is a deliberate companion to ELF; the DWARF FAQ describes its origins in Brian Russell's work for the System V debugger. DWARF 2 appeared in 1993, and DWARF 5 in 2017.

One particularly consequential addition was Call Frame Information, or CFI¹¹. A debugger needs to reconstruct callers. A frame-pointer chain can help, but optimized code often omits the dedicated frame pointer, and architectures differ in how they initially save a return address. CFI describes how to recover the caller's state at different instruction positions: the stack reference point, return address, and saved registers.

The rules are compact instructions describing an unwind procedure. They need not resemble the program's own instruction set. The distinction is between executing the function forward and reconstructing enough state to walk backward through its calls.

Exceptions make those tables part of the runtime

C++ exceptions require a stack walk during execution. The runtime must recover caller state, run applicable cleanups, and locate a matching handler.

A registration approach can save state when entering protected regions. A table-driven approach instead records how to unwind each code range and consults the tables when an exception occurs. The latter is often called zero-cost exceptions: it avoids routine exception-registration work on the normal path. The tables occupy space, and code layout and optimization can still be affected. “Zero cost” is a statement about a particular execution-path cost, not a claim that exceptions have no cost anywhere.

GCC¹² adopted DWARF-based exception support in the 1990s. The runtime representation, .eh_frame, adapts call-frame information for loading into memory. Relative encodings help it remain useful when a shared image changes address. Common rules can be shared, while records describe individual code ranges; a function need not correspond to exactly one record.

The Itanium C++ ABI's exception specification separates two responsibilities. The unwinder recovers successive frames. A language-specific personality routine decides whether a frame has a handler or cleanup. C++ commonly uses __gxx_personality_v0; Rust uses rust_eh_personality. Language-specific action data is commonly stored in .gcc_except_table.

This explains why even a C function can have .eh_frame. Exceptions may need to cross it, and debuggers and profilers may need to unwind it. Source-language syntax alone does not determine whether frame recovery is useful. The x86-64 toolchain convention supplies unwind information for that broader purpose.

Searching all frame records on every unwind step would be costly. .eh_frame_hdr adds an address-sorted lookup table; Ian Lance Taylor's account describes the GNU implementation's history. Producing and maintaining these structures gives the linker a task beyond concatenating bytes: it must understand record relationships, rewrite references, and discard records when their code is discarded.

Repeated definitions become a normal input

C++ templates and inline functions may generate equivalent definitions in many translation units. Here, inline concerns the language's multiple-definition rules; it does not promise that every call becomes inlined instructions.

Rejecting all repeated definitions would make ordinary header-based C++ impossible. GNU's .gnu.linkonce convention provided an early selection mechanism. ELF COMDAT¹³ groups subsequently made the relationship explicit: select one group with a given signature and keep its associated content together. A function's code, constants, and metadata cannot always be selected independently.

Section GC¹⁴ handles a different question: which content is reachable at all? Starting from roots, the linker follows references and retains reachable sections. With -ffunction-sections and -fdata-sections, the compiler provides a fine enough section granularity to remove individual functions or data objects. This is build-time reachability, not heap collection during execution.

Selection, reachability, and relocation now interact. A reference to a discarded duplicate needs the surviving definition. An unwind record for removed code must not remain a valid-looking runtime entry.

Permissions become another output of the link

Executable-stack declarations illustrate how a small piece of metadata can have a long afterlife. An input .note.GNU-stack communicates stack requirements; the output PT_GNU_STACK summarizes them for the runtime. The note commonly has no contents. Its presence and flags carry the meaning.

Some older toolchains conservatively treated missing declarations as a possible executable-stack requirement. That is not an immutable ELF rule. In this chapter's native Linux measurements, GNU ld 2.46 and LLD¹⁵ 21.1.8 both produced an RW stack for the same assembly file with no note. Handwritten assembly should state its requirement explicitly instead of depending on a version-specific default.

RELRO¹⁶ addresses a related transition: some data must be writable while relocations are applied but should become read-only afterward. PT_GNU_RELRO describes the range. Eager binding with -z now allows the relevant function-binding entries to be resolved before protection is applied. The linker arranges and describes the range; the startup path enforces the protection.

These contracts remain consequential years later. For example, glibc¹⁷ 2.41 tightened the interaction between loading a library with executable-stack requirements and an already-running process. A library's declaration can therefore affect whether it loads, even when its authors did not intend to execute stack code. Inspect the actual output metadata; neither a filename nor an old default is an adequate explanation.

Speed becomes an architectural requirement

Debug information can dominate linker input. A tiny C++ function involving standard-library templates may carry orders of magnitude more type and source metadata than machine code. The linker must process and write that information even though the loader normally does not map it into the executing program.

GNU ld is built around BFD's support for many object formats and extensive linker-script behavior. That breadth is valuable, particularly for kernels and firmware with strict placement requirements. It also made a different design attractive for large ELF applications.

Gold, begun by Ian Lance Taylor in 2006 and integrated into Binutils in 2008, focused on ELF rather than BFD's cross-format abstraction. LLVM¹⁸'s rewritten LLD applied direct data structures and simpler processing; its ELF design is described in the 2016 EuroLLVM presentation. Mold, begun in 2020 and released as 1.0 in 2021, made broad parallelism a central design constraint.

The effect is visible to application developers. The Rust project's announcement for Rust 1.90 reports a ripgrep development-build case in which LLD reduced linking time by roughly a factor of seven and overall incremental build time by about 40%. Those are measurements for that workload, not a universal speed ratio. Faster linking still has to coexist with script compatibility, platform conventions, and maintenance.

Formats continue to evolve too. Compact relocation encodings such as CREL target object-file size. SFrame supplies a compact representation for stack tracing; it does not provide the language-specific exception semantics of the C++ unwinding machinery. A smaller format is useful only when it still expresses the consumer's required contract.

Across these changes, the oldest dependency survives: placement must be known before an address-dependent field can receive its final value. With fixed module sizes, that gives a simple two-pass model. First determine bases and definitions; then evaluate references. Optimizations can make real layout iterative, but the small model is enough to start building a linker.

Exercises

Use the native x86-64 Linux environment from Theory 00. Compile ordinary C/C++ with gcc and g++; use musl-gcc¹⁹ for the static musl²⁰ example. Inspect files with ar²¹, nm²², readelf²³, objdump, and size. The example contains the complete file-inspection experiments and creates a fresh output directory for each run.

Begin with a program that returns 42. Ask the linker to trace its actual inputs and write a map:

1
printf 'int main(void) { return 42; }\n' > hello42.c
2
musl-gcc -static hello42.c -o hello42 -Wl,-t,-Map=hello42.map > link-inputs.txt
3
cat link-inputs.txt

Find the musl libc.a that actually participated in the link and copy it into the working directory. A driver's file query is distinct from the final link inputs: the musl wrapper can select musl through additional configuration while -print-file-name=libc.a follows other GCC search settings. The -Wl,-t trace names files the linker actually opened, making it suitable for this archive-extraction exercise. The archive path can be taken directly from that trace.

1. Inspect file libc.a and ar t libc.a | head. Is the archive itself ELF? Find the member defining printf, extract it with ar x, and inspect that member. Is it a relocatable ELF file?
2. Count archive members with ar t libc.a | wc -l. How many were extracted for hello42? Read the map's opening “Archive member included” section and trace the dependencies that caused extraction.
3. Inspect readelf -h hello42. Decode the first four magic bytes, the OS/ABI and ABI Version fields, and the machine name. Why can a Linux executable say “System V” and “AMD”?

For the next three exercises, use a machine with 500 decimal words. Each word has an opcode in the thousands digit and a three-digit operand. A module lists definitions as module-relative offsets and an indexed list of external names. Mode I leaves the word unchanged; R adds the module base to the operand; E replaces the operand's use-list index with the referenced symbol's absolute address. Modules are packed in input order starting at zero.

1
module boot
2
  use main
3
  text
4
    R 1002
5
    E 2000
6
    I 42
7
end
8
module main
9
  def main 1
10
  use put msg
11
  text
12
    I 5000
13
    E 3000
14
    E 4001
15
    R 6000
16
end
17
module lib
18
  def put 0
19
  def msg 2
20
  use main
21
  text
22
    R 7002
23
    E 8000
24
    I 104
25
end

4. Compute each module's base and length, then the symbol table.

5. Compute the ten output words. Why can the reference in the second word of boot not be resolved from that module alone?

6. Move lib before the other modules. Which word values change, and which merely move?

7. Compile main.c and the following C++ input twice, with -O1 -c and -O1 -g -c. Compare total file sizes, size output, and section inventories. Does equal code size prove equal machine-code bytes?

1
// words.cpp
2
#include <map>
3
#include <string>
4
#include <vector>
5

6
int count_words(const std::vector<std::string> &ws) {
7
    std::map<std::string, int> freq;
8
    for (const auto &w : ws) freq[w]++;
9
    return static_cast<int>(freq.size());
10
}

8. Assemble this input without a stack note and link it with the C caller. Compare GNU ld and -fuse-ld=lld, then add an explicit non-executable-stack note and repeat.

1
# answer.s
2
    .text
3
    .globl answer
4
answer:
5
    movl $42, %eax
6
    ret

1
// use.c
2
int answer(void);
3
int main(void) { return answer(); }

9. For the hand-calculated model in exercises 4–6, list the state that must survive the first pass. Choose a diagnostic rule for an external reference with no definition. How will the report make the failure visible? This is a model-design question, not a repository implementation task.

Answers and evidence

The recorded file experiments ran natively on x86-64 Ubuntu 26.04 with GCC 15.2, GNU ld 2.46, and Clang/LLD 21.1.8. Counts, sizes, and defaults below describe that environment. They are not constants of the formats.

1–3: Archives and ELF headers

The archive begins with the eight-byte ar signature, !<arch> followed by a newline. Its extracted member begins with the ELF magic and is relocatable:

1
$ file libc.a
2
libc.a: current ar archive
3
$ head -c 8 libc.a | od -c | head -1
4
0000000    !   <   a   r   c   h   >  \n
5
$ ar t libc.a | head -5
6
aio.lo
7
aio_suspend.lo
8
lio_listio.lo
9
__cexp.lo
10
__cexpf.lo
11
$ ar x libc.a printf.lo && file printf.lo
12
printf.lo: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

There were 1,347 archive members; the link selected ten:

1
$ ar t libc.a | wc -l
2
    1347
3
$ musl-gcc -static hello42.c -o hello42 -Wl,-Map=hello42.map
4
$ sed -n '/^Archive member included/,/^Merging/p' hello42.map
5
Archive member included to satisfy reference by file (symbol)
6

7
libc.a(__libc_start_main.lo)
8
                              Scrt1.o (__libc_start_main)
9
libc.a(exit.lo)
10
                              libc.a(__libc_start_main.lo) (exit)
11
libc.a(defsysinfo.lo)
12
                              libc.a(__libc_start_main.lo) (__sysinfo)
13
libc.a(libc.lo)
14
                              libc.a(__libc_start_main.lo) (__progname_full)
15
libc.a(__environ.lo)
16
                              libc.a(__libc_start_main.lo) (__environ)
17
libc.a(__init_tls.lo)
18
                              libc.a(__libc_start_main.lo) (__init_tls)
19
libc.a(_Exit.lo)
20
                              libc.a(exit.lo) (_Exit)
21
libc.a(memcpy.lo)
22
                              libc.a(__init_tls.lo) (memcpy)
23
libc.a(default_attr.lo)
24
                              libc.a(__init_tls.lo) (__default_stacksize)
25
libc.a(__set_thread_area.lo)
26
                              libc.a(__init_tls.lo) (__set_thread_area)
27

28
Merging object attributes

Although main calls no library function, Scrt1.o requires __libc_start_main. That member introduces dependencies including initialization and exit handling. Further members satisfy those references. This is the recursive library search described by the historical naming-context model. printf.lo does not appear because nothing in this program requires it. nm -A libc.a can associate the exported printf symbol with its member.

1
$ readelf -h hello42
2
ELF Header:
3
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
4
  Class:                             ELF64
5
  Data:                              2's complement, little endian
6
  Version:                           1 (current)
7
  OS/ABI:                            UNIX - System V
8
  ABI Version:                       0
9
  Type:                              EXEC (Executable file)
10
  Machine:                           Advanced Micro Devices X86-64
11
  ...

The first four bytes are 0x7f, E, L, F. The following identifiers specify 64-bit class, little-endian data, and the ELF version. OS/ABI zero means no specific extensions or an unspecified ABI identity in the generic format; tools traditionally display it as System V. It does not claim the machine is running the historical System V operating system. ABI Version is interpreted with that identity. The AMD machine name reflects the origin of the x86-64 architecture.

An object that uses GNU extensions can advertise a different identity:

1
$ cat ifunc.c
2
static int impl(void) { return 7; }
3
static int (*resolve(void))(void) { return impl; }
4
int pick(void) __attribute__((ifunc("resolve")));
5
$ clang -c ifunc.c -o ifunc.o
6
$ readelf -h ifunc.o | grep OS/ABI
7
  OS/ABI:                            UNIX - GNU
8
$ file ifunc.o
9
ifunc.o: ELF 64-bit LSB relocatable, x86-64, version 1 (GNU/Linux), not stripped

This example checks the object produced by native Clang. Actually executing an IFUNC-based program also depends on runtime-library support; inspecting the header does not test that support.

4–6: Link the ten words

The initial bases are boot = 0, main = 3, lib = 7. Definitions become main = 4, put = 7, and msg = 9.

The second word of boot names a definition in a later module. The target's offset within that module is insufficient without the module's eventual base. The following report organizes the hand calculation; it is not command output:

1
Modules
2
  1  boot       base 000  size 3
3
  2  main       base 003  size 4
4
  3  lib        base 007  size 3
5
Symbols
6
  main       004  main
7
  msg        009  lib
8
  put        007  lib
9
Memory
10
  000: 1002
11
  001: 2004
12
  002: 0042
13
  003: 5000
14
  004: 3007
15
  005: 4009
16
  006: 6003
17
  007: 7009
18
  008: 8004
19
  009: 0104

After reordering, the bases are lib = 0, boot = 3, main = 6, and the definitions are put = 0, msg = 2, main = 7:

1
Memory
2
  000: 7002
3
  001: 8007
4
  002: 0104
5
  003: 1005
6
  004: 2007
7
  005: 0042
8
  006: 5000
9
  007: 3000
10
  008: 4002
11
  009: 6006

Every R and E value changes in this particular example. The I values survive unchanged but occupy different output addresses. Relative references depend on their owning module's base; external references depend on the target definition's module. Recomputing both preserves the original relationships.

7–8: Metadata is not machine code

1
$ wc -c main.o main-g.o words.o words-g.o
2
  1416 main.o
3
  3312 main-g.o
4
  9200 words.o
5
288912 words-g.o
6
$ size main.o main-g.o words.o words-g.o
7
   text data bss  dec hex filename
8
    109    4   0  113  71 main.o
9
    109    4   0  113  71 main-g.o
10
   2481    8   0 2489 9b9 words.o
11
   2481    8   0 2489 9b9 words-g.o

Here -g leaves the reported code/data sizes unchanged while increasing the C++ object's file size from about 9 KB to 289 KB. Added content includes type descriptions, source positions, line tables, location lists, and relocations for debug information. Equal sizes alone do not establish byte-for-byte code identity; extract and compare the relevant code sections to make that stronger claim. Compression settings can also change file sizes.

Both tested linkers emitted a non-executable stack even when the assembly note was missing:

1
$ gcc -c answer.s use.c
2
$ musl-gcc -static use.o answer.o -o bad
3
$ readelf -lW bad | grep GNU_STACK
4
  GNU_STACK 0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW 0x10
5
$ musl-gcc -static -fuse-ld=lld -Wl,--no-dynamic-linker use.o answer.o -o bad-lld
6
$ readelf -lW bad-lld | grep GNU_STACK
7
  GNU_STACK 0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW 0

Make the intended requirement explicit at the end of answer.s:

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

After reassembly and static linking, GNU_STACK is RW and the program exits with status 42. An actual executable-stack requirement is a separate contract; omission is an unreliable way to express it.

9: State and recovery

The first pass must retain module bases and lengths, definitions, use lists, and each word's mode and value—or an input representation that can be reread. The second pass needs the owning module's base for R, and both its use list and the global symbol table for E.

The hand-calculated model may adopt the NYU teaching assignment's recovery policy: report an undefined name, substitute address zero, and continue listing a diagnostic memory image. This does not make the erroneous program safe to run.

References and terminology

The exercises draw on the two-pass linker assignments associated with Allan Gottlieb and Hubertus Franke's NYU operating-systems courses. Historical context and specifications are available in the EDSAC collection, Multics history, Saltzer's naming study, SunOS shared-library paper, DWARF standard, ELF gABI, and x86-64 psABI. John R. Levine's Linkers and Loaders and Ian Lance Taylor's linker series provide longer accounts.