Linking and Loading

15 · Linking and Loading¶

The question¶

How does a file on disk become an address space?

ch12 left the linker as the stage that “fills in the holes” and moved on. This chapter opens the file it produced. By the end you should be able to say what is in an executable, which parts of it will exist at run time and which will not, and what exec has to do to turn one into a running program — and you should have written enough of a reader to believe it.

The material¶

Write the reader¶

A reader who has only ever used readelf — the standard tool for printing what an ELF file contains — believes an ELF file is a thing a tool understands. The fastest cure is to write a tool.

/* Field offsets, straight out of the specification. Named rather than written inline so that a
 * reader with the document open can check each one. */
#define EH_TYPE 16
#define EH_MACHINE 18
#define EH_ENTRY 24
#define EH_PHOFF 32
#define EH_SHOFF 40
#define EH_PHENTSIZE 54
#define EH_PHNUM 56
#define EH_SHENTSIZE 58
#define EH_SHNUM 60
#define EH_SHSTRNDX 62

Build it and point it at something:

./run elfdump xv6/stage/user/_sameanswer

That is most of what an ELF file is: a header with a magic number — a few fixed bytes that say this is ELF — a handful of sizes, and the offsets of two arrays. Everything else is found by following one of those offsets. There is no #include <elf.h> anywhere in sysfs/tools/elfdump.c, deliberately — the structures are declared from the specification The Santa Cruz Operation (n.d.), so that they read as a documented layout of bytes rather than as something only a library may know.

Two arrays, two audiences¶

The two arrays describe the same bytes to different readers, and confusing them is the single most common muddle about executables.

Sections are the linker’s view. They are named, they are numerous, and most of them exist to be combined with the corresponding sections of other objects: put all the .text — the instructions — together, all the .rodata — the read-only data — together, resolve what refers to what. After linking, most of them have no further purpose — the debug sections in particular are enormous and are never loaded.

Segments are the loader’s view, and there are far fewer:

A segment says: take this many bytes from this offset in the file, put them at this address, give them these permissions. That is nearly the whole interface between a file and an address space.

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · cc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · the reader is built for this machine; the subjects are built by xv6 · 2026-09-17 · Source: bench/results/elf-xv6.json, code hash 85308ce82a349d62.

Eighteen sections, two segments. The collapse is by permission: everything that needs to be readable and executable goes in one, everything writable in the other. Permissions are a property of a page, not of a symbol, which is why the grouping is by what the hardware can enforce rather than by what the programmer named.

The segment that is partly not in the file¶

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · cc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · the reader is built for this machine; the subjects are built by xv6 · 2026-09-17 · Source: bench/results/elf-xv6.json, code hash 85308ce82a349d62.

Look at the writable rows. Those segments occupy bytes in memory and none at all in the file.

That is .bss: variables that start as zero. Storing them would mean putting a run of zeroes in every binary, so the format does not. It records how much space to provide and the loader provides it, already zeroed. A global array of a million integers costs a number in a header.

Two consequences worth carrying forward. A binary’s size on disk tells you little about its size in memory — ch12’s comparison of glibc against xv6’s library was about code, and this is the other direction. And “zero-initialised” is not a favour the language does you at some cost; it is the cheapest initial state, because it is the one the loader was going to produce anyway.

What exec actually does¶

The interface above is small enough that you can now read the kernel side of it. xv6’s exec opens the file, checks the magic number, walks the program headers — the segment array — and for each loadable one allocates pages and copies bytes in Cox et al. (n.d.). Then it builds a stack, puts the arguments on it, and switches the process to the new address space.

Everything it does is a consequence of what the file said. It has no idea what the program does, what language it was written in, or what its functions are called — the symbol table is not consulted. An ELF executable is a set of instructions to a loader, and the code is incidental.

The permissions matter here in a way they do not in a file. The code segment is mapped executable-and-not-writable and the data segment writable-and-not-executable, and those two prohibitions are enforced by the page table rather than by convention. ch17 is where that enforcement becomes a mechanism you can see and ch18 is where breaking it becomes a fault you can catch.

The symbol table, which is not loaded¶

The symbol table is not loaded and is not needed to run the program. It survives in the file for the benefit of debuggers and of anybody reading it, which is why stripping a binary makes it smaller without making it slower, and why a stripped binary produces a backtrace full of addresses and no names.

It cuts both ways: the names in a backtrace are a convenience the file happens to carry, and a production binary that has been stripped has thrown them away permanently — which is why ch30 spends time on keeping symbols around for the profiler.

What we measured¶

Sections, segments and symbol counts for two xv6 programs, read by sysfs/tools/elfdump.c rather than by readelf. Facts about files, stamped as artefacts, regenerated by CI.

xv6’s binaries were chosen over Linux ones because a Linux executable’s answer to “where does this get loaded” is complicated by a dynamic loader and a position-independent layout, both of which deserve their own explanation and neither of which is the mechanism underneath. xv6 links a program to a fixed address and puts it there. That is the simple version of what the complicated version is doing.

What this cannot tell you¶

How dynamic linking works. Every binary here is statically linked to a fixed address. Shared libraries, relocation at load time, the procedure linkage table and the global offset table are all absent, and they are the majority of what happens when you run a program on Linux. ch29 touches the cost of the machinery; this chapter does not describe it.

What a linker script decides. xv6 has one, it fixes the addresses in the table above, and this chapter shows the result of it rather than the language it is written in. Linker scripts are a small, strange, badly documented language, so this chapter does no more than say the addresses came from somewhere and point at the file.

Anything about time. Loading a program costs something — pages have to be allocated and bytes copied — and this chapter has no way to measure it. ch29 measures what a process costs to start on a machine with a clock.

Whether the symbol table is “wasted space”. It is not loaded, so it costs no memory at run time; it costs file size and it buys every debugging session you will ever have. That is a trade-off rather than a defect, and which side of it you want depends on things this chapter has no opinion about.

Problems¶

Three, and the first is the one that makes the format stop being magic.

15.1 — Finish the reader. Two functions sysfs/tools/elfdump.c does not contain: how much memory a program occupies once loaded, and which section covers a given address. The second one requires the indirection this chapter describes — a section header does not hold its own name.

The expected answers are not stored. The test runs the book’s finished reader on the same binary and compares, so the target moves with the file rather than going stale the next time xv6 is rebuilt.

python3 -m pytest tests/linking_and_loading/test_problem_1_reader.py

15.2 — Which of these links? Five pairs of C files. Predict whether each produces a program. The test actually links them.

One of the five links successfully and produces a program that is wrong, which is not a trick: it is the reason the C language has a reputation. Say whether it links; the chapter has already said what to make of the fact that it does.

python3 -m pytest tests/linking_and_loading/test_problem_2_resolve.py

15.3 — Read the error, name the cause. Four link failures, with the messages a linker really produced during the test run. Name the cause of each.

Linker errors are terse, they name symbols rather than files, and they come from a program that knows nothing about your intentions. Reading one is a skill, and it is the difference between twenty minutes and ten seconds.

python3 -m pytest tests/linking_and_loading/test_problem_3_diagnose.py

Where to go next¶

The ELF specification The Santa Cruz Operation (n.d.) is the document sysfs/tools/elfdump.c was written from, and it is unusually pleasant for a format specification: the structures are small, the field names are the ones every tool uses, and you can check the reader against it line by line.

The RISC-V psABI RISC-V International (n.d.) supplies the architecture-specific half — which relocation types exist and what each computes — and is where to look when a relocation name appears in an error message.

xv6’s kernel/exec.c Cox et al. (n.d.) is short, and it is now readable end to end. It is the shortest complete answer to “what happens when you run a program” that exists anywhere, and having written a reader for the format it consumes, you will find it contains no surprises at all. That feeling is what Part III was for.

ch16 begins Part IV by asking what happens when that program asks the kernel for something.