Appendix E · Glossary¶
An appendix in this book is a reference, not a chapter: no argument, no narrative, and everything
in it either cites a primary source or comes from a stamped result under bench/results/.
Assembled from the chapters after they were written, which is the only order that works: a glossary drafted first defines the words the prose did not end up using. Every entry names the chapter that establishes it, and the definition here is deliberately shorter than the chapter’s — this page is for recognising a term, not for learning it.
The book’s own vocabulary¶
These four are used throughout and mean something specific here.
| Term | What it means in this book |
|---|---|
| target | One of three places code runs: bare (a RISC-V machine under QEMU with nothing on it), xv6 (the teaching kernel under QEMU) or host (Linux on real hardware, natively). Every result declares one. ch00 |
| stamped result | A JSON file under bench/results/ carrying what was measured, on which machine, with which toolchain, and a hash of the code that produced it. Nothing reaches a chapter any other way. ch00 |
| pending figure | A measurement the book owes but has not taken. It renders as a warning containing no numbers — never a placeholder and never an estimate. Preface |
| listing | Disassembly captured from a compiler and stamped, so a chapter can show machine code without pasting it. Re-captured by CI on every push. ch02 |
Part I — C, and what the machine does with it¶
| Term | Definition | Where |
|---|---|---|
| disassembly | A compiled function printed back as instructions. What the compiler produced, not what you wrote. | ch02 |
| mnemonic | The name of an instruction, as distinct from the bytes that encode it. | ch02 |
| operand | What an instruction acts on. In both of this book’s syntaxes the destination comes first. | ch02 |
| address | A number naming a byte. Memory is one array and an address is an index into it. | ch03 |
| pointer | A variable holding an address, with a type saying what to assume is there. | ch03 |
| freestanding | The standard’s word for C with no library underneath it. ch04 deliberately does not use it, on the grounds that what matters is which specific things are missing. | ch04 |
| free list | An allocator that keeps its bookkeeping inside the memory it is not currently handing out. | ch04 |
| storage duration | How long an object lives: automatic, static, or allocated. The distinction a garbage-collected language does not make you make. | ch05 |
| function pointer | An address of code rather than of data, and how a kernel gets a virtual call without a class. | ch05 |
Part II — the machine with nothing on it¶
| Term | Definition | Where |
|---|---|---|
| trap vector | The address the hardware jumps to when a trap happens, which software puts there before any trap can be handled. | ch06, Appendix A |
| trap handler | The code at that address. On a bare machine it is a function you wrote; in a kernel it is the start of everything. | ch06, ch16 |
| privilege level | Which of the machine’s modes is executing, and therefore what the instruction being attempted is allowed to do. | ch07 |
| hart | A RISC-V hardware thread: one instruction stream with its own registers, sharing memory with the others. | ch08 |
| identity mapping | A page table in which a virtual address translates to the same physical address, so translation can be switched on without anything moving. | ch08 |
| dispatch | Turning a number a caller supplied into the function that serves it, which is all a system-call table is. | ch09 |
| file descriptor | A small integer that means a device, because a table in the process turns it into one. | ch10 |
| process table | The kernel’s fixed array of processes, and the reason running out of them is a number rather than a shortage of memory. | ch11 |
Part III — the machine underneath a program¶
| Term | Definition | Where |
|---|---|---|
| translation unit | One source file plus everything it included, which is what the compiler actually sees. | ch12 |
| preprocessing | The first stage: includes pasted in, macros expanded, conditionals resolved. Its output is C. | ch12 |
| relocation | A note in an object file saying “this address is not known yet”, resolved at link time. | ch12, ch15 |
| object file | Compiled code with unresolved references, not yet a program. | ch12 |
| padding | Bytes a compiler inserts inside a struct so each member lands on an address it can be accessed at. | ch13 |
| alignment | The requirement that an object’s address be a multiple of its size, or of its widest member. | ch13 |
| undefined behaviour | A program the standard makes no promises about, which a compiler may therefore assume never happens. | ch13, ch05 |
volatile | A promise not to cache a value in a register and not to reorder accesses to it relative to each other. Not a threading tool. | ch05 |
| calling convention | The agreement about which registers carry arguments, which are preserved, and who cleans up. A contract between compiled code, not a hardware rule. | ch14 |
| caller-saved / callee-saved | Whether the code making a call or the code being called is responsible for preserving a register across it. | ch14 |
| stack frame | The region a function owns on the stack. At -O2 many functions have none. | ch14 |
| prologue / epilogue | The instructions at a function’s start and end that establish and dismantle its frame. | ch14 |
| leaf function | One that calls nothing, and therefore usually needs no frame and no saved return address. | ch14 |
| section | A named region of an object file — what the linker deals in. | ch15 |
| segment | A named region of a program image — what the loader deals in. Sections are mapped into segments. | ch15 |
| symbol table | The list of names an object file defines and requires. | ch15 |
Part IV — the kernel, as structure¶
| Term | Definition | Where |
|---|---|---|
| trap | Any transfer to the kernel: a system call, a fault, or an interrupt. The hardware’s mechanism is the same for all three. | ch16 |
| exception | A trap caused by the instruction being executed — it could not complete. | ch16, ch19 |
| interrupt | A trap caused by something outside the program asking for attention. | ch19 |
| trampoline | A page mapped at the same address in every address space, so the trap path survives the page table changing under it. | ch16, ch17 |
| trap frame | Where the interrupted program’s registers are put, since it agreed to no convention about which to preserve. | ch16 |
| virtual address | An address a program uses, which means nothing without a page table. | ch17 |
| page table | The tree the hardware walks to turn a virtual address into a physical one. | ch17 |
| Sv39 | RISC-V’s three-level paging scheme: three nine-bit indices and a twelve-bit offset. | ch17, Appendix A |
| page-table entry (PTE) | One sixty-four-bit word: permission flags and a physical page number, or a pointer to the next level. | ch17 |
| TLB | The cache of recent translations. Changing a page table means telling it. | ch17, ch29 |
| page fault | A trap raised when translation fails. Not an error — a hook, and most of what a modern kernel does with memory is built on it. | ch18 |
| lazy allocation | Handing out address space and only finding physical pages when they are touched. | ch18 |
| copy-on-write | Sharing a page until somebody writes to it, using the fault as the trigger. | ch18 |
| device driver | The code that knows a device’s registers. In xv6, small enough to read in full. | ch19 |
| interrupt controller | The hardware that decides which device may interrupt which core. | ch19 |
| spinlock | A lock that waits by running. Correct when the wait is shorter than a context switch. | ch20 |
| sleeplock | A lock that waits by yielding. Correct when it is not. | ch20, ch21 |
| memory ordering | Which of one core’s writes another core may observe, and in what order. Weaker than the program order on both of this book’s architectures. | ch20, ch28 |
| barrier / fence | An instruction, or a property of one, constraining that order. | ch20, ch28 |
| acquire / release | The two halves of the ordering a lock needs: nothing moves out of the critical section past either end. | ch20 |
| context switch | Saving one thread’s registers and restoring another’s. Structurally small; what surrounds it is not. | ch21 |
| scheduler | The code that decides which thread runs next. | ch21 |
| buffer cache | The kernel’s copy of recently used disk blocks, and the reason a read can cost nothing. | ch22 |
| write-ahead log | Writing what you are about to do before doing it, so a crash leaves a recoverable state. | ch22 |
| write amplification | How many blocks actually move for each block a program asked to write. | ch22 |
| inode | The on-disk record of a file, distinct from any name it has. | ch22 |
Part V — where the cycles go¶
| Term | Definition | Where |
|---|---|---|
| monotonic clock | One that cannot go backwards and is not adjusted to keep wall-clock time honest. The only kind to measure with. | ch24 |
| minor fault | A page fault the kernel satisfies without touching storage. | ch18, ch29 |
| major fault | One that has to wait for storage. Orders of magnitude more expensive, and identical from the trap’s point of view. | ch29 |
| clock cost | What reading the clock costs. The number that decides whether a measurement means anything. | ch24, ch29 |
| distribution | What to report instead of a number: minimum, median, tail. A single duration is an anecdote. | ch24 |
| warm-up | Discarding the start of a run, only when the discarded part is genuinely slower and you can say why. | ch24 |
| cache line | The unit everything happens in. Not the variable, not the byte. | ch25, ch28 |
| working set | How much memory a piece of code touches in the window that matters. | ch25, ch30 |
| prefetch | The hardware fetching ahead of a predictable access pattern, and the reason a sequential walk is not a sequence of misses. | ch25 |
| pointer chase | A walk whose next address is not known until the current load returns, which defeats prefetching. | ch23, ch25 |
| strength reduction | Replacing an expensive operation with a cheaper one that computes the same thing. Usually the compiler’s job. | ch26 |
| pipeline | The core overlapping the stages of consecutive instructions. | ch27 |
| instruction-level parallelism (ILP) | How many independent instructions are available to overlap. | ch27 |
| IPC | Instructions retired per cycle. Above one on a core that can finish several at once, and a diagnostic rather than a goal. | ch27, ch29 |
| dependence chain | A sequence where each instruction needs the previous one’s result. Its length is a floor no width removes. | ch27, ch31 |
| branch predictor | The hardware guessing which way a branch goes, so the pipeline need not wait. | ch27 |
| misprediction | A wrong guess, paid for by discarding the work done since. | ch27 |
| branchless | Computing both sides and selecting, so there is nothing to mispredict. Worth it exactly when the branch is unpredictable. | ch27 |
| coherence | The guarantee that cores agree about the contents of a cache line, and the traffic that provides it. | ch28 |
| false sharing | Two cores fighting over a line neither shares data on. The sharing is real; what is false is that anyone meant to share. | ch28 |
| Amdahl’s law | The ceiling a scaling curve cannot pass, computed from the program before the machine is involved. | ch28 |
| system call | A request to the kernel. Compiled into your program as a branch, with the trap somewhere you cannot see. | ch16, ch29 |
| vDSO | Kernel code mapped into every process so a few requests need no privilege change at all. The reason the clock is cheap. | ch29 |
| sampling profiler | One that arranges to be interrupted and writes down where the program was. Everything it can and cannot tell you follows from that. | ch30 |
| exclusive / inclusive time | Samples in a function itself, against samples in it and everything it called. The flat list blames the leaf. | ch30 |
| skid | The gap between the instruction that stalled and the one the sample was attributed to. Read the neighbourhood, never the line. | ch30 |
| aliasing (sampling) | A fixed sampling period over a fixed loop visiting only some positions, producing a stable and confidently wrong profile. | ch30 |
| vectorisation | One instruction doing several elements. Not on by default at the level most people build at. | ch31 |
| lane | One element’s worth of a vector register. | ch31 |
| tail | The elements left over when the trip count is not a multiple of the width, handled one at a time. | ch31 |
| reassociation | Adding the same numbers in a different order. Free for integers, not free for floats, and the reason one reduction widens and the other does not. | ch31 |
| arithmetic bound | The most a change could possibly buy, computed before measuring. A speedup is reported against it or not reported. | ch28, ch31 |
What this cannot tell you¶
Enough to use any of these. A one-line definition is for recognising a term you have met. The chapter named beside it is where it is established, and none of these entries is a substitute for the measurement that made the chapter worth writing.
The standard meaning. Where a term is used here more narrowly than in general practice — and several are — this page gives the book’s sense. Where the book’s sense differs from the common one deliberately, the chapter says so.