Glossary

The chapter in parentheses is where the term is explained; most terms are used again in every chapter after that one.

A20 line: The twenty-first address line of the PC, gated off at power-up so that addresses wrap at 1 MiB as they did on the 8086. The bootloader opens the gate through bit 1 of port 0x92 before the kernel can use memory above 1 MiB (chapter 9).
Abort: The class of exceptions that report a state too broken to restart the program, such as the double fault and the machine check. Unlike a fault, the saved EIP cannot be trusted (chapter 11).
ACPI: The firmware interface that, among much else, specifies the INT 15h, E820h memory map and the tables the firmware leaves in memory for the operating system (chapter 12).
Address space: The set of addresses a program can name. A PC has a memory address space, 4 GiB wide on a 32-bit processor, and a separate 64 KiB I/O address space reached by in and out; with paging, each process gets a memory address space of its own (chapter 12).
APIC: The Advanced Programmable Interrupt Controller: a per-processor local APIC and an I/O APIC that replace the 8259A PIC on every machine built since the late 1990s, and the mechanism through which processors wake each other up (chapter 17).
ATA: The command set of IDE and SATA disks: a drive is selected, a sector number and a count are written to its registers, a command byte is issued, and the data is transferred through the data register. The kernel’s disk driver uses IDENTIFY DEVICE and READ SECTORS (chapter 14).
BIOS: The firmware of the PC. It initializes the hardware, loads the first sector of the boot device at 0x7C00 and offers 16-bit services through INT instructions: INT 13h for the disk, INT 10h for the screen, INT 15h for the memory map (chapter 7).
Bitmap allocator: An allocator that keeps one bit per unit of a resource, 1 for used and 0 for free. The kernel’s physical memory manager keeps one bit per 4 KiB frame and hands out the lowest free one (chapter 12).
Block bitmap, inode bitmap: In ext2, the two bitmaps of a block group that say which blocks and which inodes of the group are in use (chapter 14).
Block group: The unit into which ext2 divides a disk: 8192 blocks, each group with a copy of the superblock, the group descriptor table, its own bitmaps, an inode table and data blocks (chapter 14).
BOOKFLAGS: The compiler options the hosted examples of the book are compiled with: -m32 -no-pie -fno-pie -fno-asynchronous-unwind-tables -fcf-protection=none -O0. The container defines the variable; define it yourself if you installed the tools natively (chapter 0).
Boot information block: The area at physical address 0x500, just above the real-mode interrupt vector table and the BIOS data area, where the bootloader leaves the E820 memory map for the kernel: the entry count at 0x500, the 24-byte entries from 0x508 (chapter 12).
Boot sector: The first 512-byte sector of a disk, ending with the signature 0x55 0xAA, which the BIOS loads at 0x7C00 and jumps to (chapter 7).
Bootloader: The program in the boot sector. The book’s bootloader reads the kernel from disk with the BIOS, collects the memory map, opens the A20 gate, switches to protected mode and jumps to the kernel’s ELF entry point (chapter 7, rewritten in chapter 9).
.bss: The section of an ELF file that holds uninitialized global variables. It has a size but no bytes in the file (NOBITS); a loader must zero it, and on bare metal the kernel’s entry code does (chapter 5).
Calling convention: The agreement between caller and callee on where arguments and the return value go and which registers survive a call. On 32-bit x86 arguments are pushed on the stack and EAX, ECX and EDX may be clobbered, which is why interrupt handlers need an assembly stub (chapter 4).
CMOS, RTC: The battery-backed clock and configuration memory of the PC. The real-time clock keeps wall-clock time and raises IRQ 8; the kernel uses the PIT for intervals instead (chapter 11).
Compatibility mode: The sub-mode of IA-32e mode in which a 64-bit kernel runs 32-bit code with 64-bit page tables (chapter 17).
Context switch: Saving the registers of the running task and loading those of another, so that the second continues where it stopped. The kernel does it by swapping kernel stacks in context_switch (chapter 13).
Control registers (CR0 to CR4): Registers that configure the processor itself. CR0 holds PE (protected mode), PG (paging) and WP; CR2 receives the faulting address of a page fault; CR3 holds the physical address of the page directory; CR4 selects paging extensions such as PAE (chapters 9 and 12).
Copy-on-write: Sharing a page between two address spaces as read-only and copying it at the first write. It is what makes fork cheap (chapter 15).
CPL, DPL, RPL: The three privilege numbers of x86 segmentation: the current privilege level in the low bits of CS, the descriptor privilege level in a segment descriptor, and the requested privilege level in the low bits of a selector. The processor compares them on every segment load (chapter 9).
CPUID: The instruction that reports which features a processor implements; the Intel instruction reference lists, for each instruction, the CPUID flag that announces it; the kernel reads the vendor string and the feature bits in cpuid.c (chapters 4 and 10).
Critical section: A sequence of operations on shared data that must not be interleaved with another. On a single processor the kernel protects one by disabling interrupts around it with irq_save and irq_restore (chapter 13).
Demand paging: Mapping a page only when it is first touched: the access faults, the handler maps a frame and returns, and the instruction runs again. It relies on page faults being faults, not traps (described in chapter 12, implemented for the .bss and the stack in chapter 15, “Pages on demand”).
Descriptor: An 8-byte entry of the GDT, LDT or IDT. Segment descriptors describe memory (base, limit, type, privilege); system descriptors describe a TSS or an LDT; gate descriptors describe a controlled entry point into code (chapter 9).
Directory entry: In ext2, a variable-length record in a directory’s data blocks: inode number, rec_len, name length, file type and the name. rec_len links the entries into a list (chapter 14).
Disk Address Packet: The structure through which the BIOS extended read service, INT 13h, AH=42h, is told what to read: a sector count, a destination and a 64-bit LBA (chapter 9).
Double fault: Exception 8, raised when the processor cannot deliver an exception because the handler’s descriptor or stack is itself broken. A fault while delivering the double fault is a triple fault (chapter 11).
DWARF: The debugging information format that gcc -g writes into ELF files and that gdb reads: which source line each address comes from, where each variable lives, how to unwind the stack (chapter 6).
E820: The BIOS service INT 15h, EAX=E820h, which returns the physical memory map one entry at a time: base, length and type (usable, reserved, ACPI) of each range (chapter 12).
EFLAGS: The 32-bit flags register: arithmetic flags (CF, ZF, SF, OF), the direction flag and the interrupt flag IF, which sti sets, cli clears and an interrupt gate clears on entry (chapter 3).
ELF: The Executable and Linkable Format, the file format of objects, executables and libraries on Linux. A header, a section table for the linker, a program header table for the loader (chapter 5).
End of interrupt (EOI): The command a handler sends to the 8259A to say that an interrupt line has been serviced; until it arrives the controller does not raise that line again (chapter 11).
Entry point: The address where execution starts, e_entry in the ELF header. The bootloader reads it from the kernel’s header and jumps to it (chapter 5).
Error code: The doubleword some exceptions push after EFLAGS, CS and EIP. For #GP, #NP, #TS and #SS it names the descriptor at fault: bit 1 set means an IDT gate, bits 15:3 are the index. For #PF it describes the access: present or not, write or read, user or kernel mode. Hardware interrupts never push one, so the stubs of the vectors without one push a 0 in its place and every handler sees the same frame (chapter 11).
Exception: An interrupt raised by the processor itself when an instruction cannot complete normally: division by zero, an invalid opcode, a protection violation, a page fault. Vectors 0 to 31 are reserved for them (chapter 11).
exec: Replacing the program of a process by one loaded from a file, keeping the process itself (chapter 15).
ext2: The second extended file system of Linux, chosen for the book because its on-disk format fits in one document: a superblock, block groups, inodes and linked-list directories (chapter 14).
Fault: An exception reported before the instruction completes, with the saved EIP pointing at the instruction, so that a handler that fixes the cause can let it run again. Page faults and general protection faults are faults (chapter 11).
First fit: The allocation policy of the kernel heap: walk the free list from the start and take the first block that is large enough (chapter 12).
Flat model: The use of segmentation in which one code and one data segment both start at 0 and cover all 4 GiB, so that a logical address equals its offset and C pointers are linear addresses (chapter 9).
fork: Creating a new process as a copy of the calling one; the two share nothing but start from the same state (chapter 15).
Gate: A descriptor that names a code entry point rather than a memory region. Interrupt gates and trap gates in the IDT lead to handlers; the only difference between them is whether IF is cleared on entry (chapter 11).
GDT: The Global Descriptor Table, the array of segment descriptors every protected-mode system has; its first entry is the null descriptor. Its address and size live in the GDTR, loaded with lgdt (chapter 9).
Group descriptor: In ext2, the 32-byte record that locates the block bitmap, the inode bitmap and the inode table of one block group and keeps its free counts. The group descriptor table is the block after the superblock, s_first_data_block + 1 (chapter 14).
Guard page: A page kept deliberately unmapped next to a region that grows, such as the bottom of a stack, so that running past the region faults at once instead of silently overwriting whatever lies beyond it (chapter 15, exercise 15.7).
Hardware Abstraction Layer: The set of interfaces, usually tables of function pointers, through which an operating system talks to device drivers without knowing the device (chapter 9).
Heap, kmalloc: The kernel’s allocator for objects of arbitrary size, built on page frames: a virtual range mapped page by page, managed as a free list with splitting and coalescing (chapter 12).
Higher-half kernel: A kernel linked to run at a high virtual address, typically 0xC0000000 and up, leaving the low addresses to user programs. The book’s kernel is identity-mapped instead (chapter 12).
IA-32e mode: Intel’s name for the 64-bit mode of x86 (AMD’s name is long mode), entered from protected mode by enabling paging with 64-bit page tables and the LME bit of the IA32_EFER MSR (chapter 17).
Identity mapping: Mapping every virtual page to the physical frame of the same address, so that turning paging on changes nothing visible. The kernel identity-maps all the RAM it manages (chapter 12).
Idle task: Task 0, kmain itself on the original stack at 0x90000: it runs when no other task is ready, halts the processor until the next interrupt, and reaps the tasks that have exited (chapter 13).
IDT: The Interrupt Descriptor Table, 256 gate descriptors indexed by vector, whose address and size are loaded into the IDTR with lidt (chapter 11).
Indirect block: A block that holds block numbers rather than file data. An ext2 inode names its first twelve blocks directly; i_block[12] points to a singly indirect block of 256 numbers with 1 KiB blocks, i_block[13] to a doubly indirect one and i_block[14] to a triply indirect one (chapter 14).
Inode: The on-disk record of one ext2 file: type and permissions, size, timestamps and the block pointers, 12 direct and 3 indirect. Names are not in it; directories map names to inode numbers (chapter 14).
Interrupt: An event that makes the processor suspend the current code, push EFLAGS, CS and EIP, and jump to the handler named by a vector in the IDT; iret resumes the suspended code. Hardware interrupts come from devices, exceptions from the processor, software interrupts from int n (chapter 11).
Interrupt vector: The number, 0 to 255, that identifies an interrupt and indexes the IDT. Vectors 0 to 31 are the exceptions, 32 to 47 the IRQs once the PIC is reprogrammed, 0x80 the book’s system call (chapter 11).
IRQ: An interrupt request line of the PIC, 0 to 15 on the PC: IRQ 0 is the timer, IRQ 1 the keyboard, IRQ 14 the primary disk. The kernel maps them to vectors 32 to 47 (chapter 11).
Kernel space, user space: The two worlds of a protected system: the kernel runs in ring 0 with access to everything; user programs run in ring 3 and reach the kernel only through system calls (chapter 9).
Kernel stack: The stack on which a task runs kernel code: its interrupt and system call handlers, and context_switch. Every task has one, KERNEL_STACK_SIZE bytes from kmalloc, and the scheduler writes its top into ESP0 of the TSS so that an interrupt from ring 3 lands on it; the idle task keeps the original stack at 0x90000 set up by entry.asm (chapter 13).
Kernel thread: A task that runs kernel code in ring 0 on its own kernel stack and shares the kernel’s address space (chapter 13).
LBA: Logical Block Addressing: naming a disk sector by its number from the start of the disk, as opposed to cylinder, head and sector (chapter 9).
LDT: The Local Descriptor Table, a per-task descriptor table selected by bit 2 of a selector. No modern system uses it; everything in the book goes in the GDT (chapter 9).
Lazy allocation: Postponing the allocation of a frame until the page is first touched: exec records the range of pages a program is entitled to, leaves their page-table entries not present, and the page-fault handler allocates each one on its first access. Demand paging is lazy allocation driven by the page fault (chapter 15).
Linker script: The text file that tells ld where to place each section, which symbols to define and which program headers to emit. The kernel’s script places .text at 0x10100 and defines the .bss bounds (chapter 8).
Little-endian: The byte order of x86: the least significant byte of a value is at the lowest address, so 0x0000ffff appears in memory as ff ff 00 00 (chapter 4).
Long mode: AMD’s name for the 64-bit mode of x86; see IA-32e mode (chapter 17).
Memory-mapped I/O: Device registers that appear at memory addresses and are reached with ordinary loads and stores, such as the VGA text buffer at 0xB8000, as opposed to port I/O (chapter 10).
MSR: A model-specific register, read and written with rdmsr and wrmsr; IA32_EFER, which enables long mode, is one (chapter 17).
Null descriptor: Entry 0 of the GDT, never used by the processor. A selector of 0 may be loaded into a data segment register but any access through it faults (chapter 9).
objdump: The binutils tool that disassembles sections of an object or executable; objdump -d -M intel is used throughout the book (chapter 5).
os01 image: The Docker image built from tools/Dockerfile that holds the exact toolchain the book’s listings were produced with: gcc, binutils, nasm, gdb, QEMU and e2fsprogs at pinned versions (chapter 0).
Page directory, page table: The two levels of 32-bit paging. The directory, named by CR3, has 1024 entries each naming a page table; a page table has 1024 entries each naming a 4 KiB frame. An entry carries the physical address in bits 31:12 and flags, P, R/W and U/S among them, in the low bits (chapter 12).
Page fault: Exception 14, raised when a translation fails: a non-present entry, a write to a read-only page, a user access to a supervisor page. The error code says which, and CR2 holds the address (chapter 12).
Page frame: A 4 KiB unit of physical memory, aligned on a 4 KiB boundary. Pages are the virtual side, frames the physical side; a page table entry maps one to the other (chapter 12).
Paging: The translation of linear addresses to physical addresses through page tables, enabled by CR0.PG. It gives each process its own address space and is the protection mechanism of every modern kernel (chapter 12).
Panic: The kernel’s reaction to a state it cannot recover from: print a message and the registers, then halt with interrupts disabled (chapter 10).
PIC (8259A): The Programmable Interrupt Controller: two cascaded chips with eight inputs each that turn device interrupt lines into vectors on the processor’s INTR pin. The BIOS programs them to vectors 8 to 15; the kernel moves them to 32 to 47 (chapter 11).
PIE: A position-independent executable, which the operating system can load at any address; the default of most distributions’ gcc. The book’s examples are built with -no-pie -fno-pie so that addresses are fixed and readable (chapter 0).
PIO: Programmed I/O: transferring data between a device and memory with in and out instructions, one word at a time, as the disk driver does with insw (chapter 14).
PIT (8253/8254): The Programmable Interval Timer, three counters driven at 1.193182 MHz; channel 0 raises IRQ 0 at the rate the kernel programs, 100 Hz in the book (chapter 11).
Polling: Asking a device repeatedly whether it has something to report, as the serial driver does before writing a byte. Interrupts are the alternative (chapter 10).
Port I/O: The separate 64 KiB I/O address space of x86, reached only by in and out; the serial port, the PIC, the PIT, the keyboard controller and the ATA registers all live there (chapter 10).
Preemption: Taking the processor away from a task that did not give it up, on a timer interrupt, so that no task can monopolize the machine (chapter 13).
Privilege level, ring: The four levels, 0 to 3, at which x86 code can run. The kernel runs at level 0, user programs at level 3; the processor refuses transfers and accesses from a less privileged level to a more privileged segment or page (chapter 9).
Process: A running program together with the state the kernel keeps for it: identifier, saved registers, page directory, kernel stack and, later, open files. The book’s struct task is its implementation (chapter 13).
Program header, segment (ELF): An entry of the ELF program header table, describing a piece of the file that the loader copies into memory: file offset, address, sizes in file and in memory, permissions (chapter 5).
Protected mode: The 32-bit mode of x86 in which segment registers hold selectors, every access is checked against a descriptor and paging is available. Entered by setting CR0.PE (chapter 9).
QEMU monitor: QEMU’s own command console, reached from gdb with the monitor prefix. info registers shows the system registers gdb does not know, GDTR, IDTR, TR and the control registers; info mem and info tlb the current page mappings; info pic the interrupt controllers; xp/ and i /b read physical memory and I/O ports from outside the guest (chapters 9, 12 and 16).
Race condition: A bug in which the result depends on the timing of two activities that touch shared data, for example a list walked by the scheduler while an interrupted function was modifying it (chapter 13).
readelf: The binutils tool that prints the headers, sections, segments and symbols of an ELF file (chapter 5).
Real mode: The 16-bit mode in which every x86 processor starts, with 1 MiB of memory addressed as segment * 16 + offset, no protection and the BIOS services available (chapter 7).
Reference count: The number of page-table entries that point to a frame, kept by the frame allocator as one byte per frame from chapter 15 on. A frame shared copy-on-write is copied at a write only while its count is above one, and freed only when the count reaches zero (chapter 15).
Relocation: A record left by the assembler or compiler saying “patch this address once the final layout is known”; the linker resolves them, and a loader of position-independent code resolves the rest at run time (chapter 8).
Run queue: The circular list of tasks from which the scheduler picks the next one to run (chapter 13).
Scancode: The byte a PS/2 keyboard sends for a key press (make code) or release (break code, the make code with bit 7 set); the kernel translates it to a character (chapter 11).
Scheduler: The kernel code that chooses which ready task runs next. The book’s scheduler is round-robin, driven by the timer interrupt and by yield (chapter 13).
Section: A named, contiguous part of an object file with one kind of content: .text for code, .data for initialized variables, .bss for uninitialized ones, .rodata for constants (chapter 5).
Sector: The 512-byte unit of a disk transfer; a disk image is a sequence of sectors numbered from 0 (chapter 7).
Segment (x86): A region of memory described by a segment descriptor: base, limit, type and privilege level. In protected mode every memory access goes through one; in the flat model the segments are invisible (chapter 9).
Segment selector: The 16-bit value in a segment register: an index into the GDT or LDT, the table indicator bit and the requested privilege level. 0x08 and 0x10 are the kernel’s code and data selectors (chapter 9).
Serial port, UART: The 16550 universal asynchronous receiver/transmitter behind COM1 at port 0x3F8, the kernel’s debugging channel: bytes written to it appear on the host’s terminal or in a file (chapter 10).
Spinlock: A lock that is acquired by repeating an atomic test-and-set until it succeeds; the building block of critical sections on a multiprocessor, where disabling interrupts is not enough (chapters 13 and 17).
Spurious interrupt: An interrupt the 8259A reports on IRQ 7 or 15 when a request disappears before the processor acknowledges it; the handler must check the In-Service Register before sending an EOI (chapter 11).
Superblock: The ext2 structure at byte 1024 of the file system that describes it: block size, number of blocks and inodes, blocks per group, inode size, magic number 0xEF53 (chapter 14).
Symbol: A name with an address, in the symbol table of an object or executable: functions, variables and linker-defined markers such as __bss_start (chapter 5).
System call: The way a user program asks the kernel for a service: a software interrupt (int 0x80 in the book) through a gate with DPL = 3, with the call number and arguments in registers (chapter 13).
Task: The kernel’s unit of scheduling: an execution context with its own kernel stack, saved stack pointer, state and page directory. Kernel threads and user processes are both tasks (chapter 13).
TLB: The Translation Lookaside Buffer, the processor’s cache of recent address translations. It is not updated when a page table is written, so the kernel invalidates entries with invlpg or by reloading CR3 (chapter 12).
Trap: An exception reported after the instruction completes, with the saved EIP pointing at the next instruction, so that returning continues the program. int 3, the breakpoint, is a trap (chapter 11).
Trap gate: An IDT gate that does not clear IF on entry, so the handler runs with interrupts enabled; the book’s gates are all interrupt gates (chapter 11).
Triple fault: A fault raised while the processor was trying to deliver a double fault. It is not an exception but a reset of the processor, and the usual symptom of a broken IDT or page table (chapter 11).
TSS: The Task-State Segment, a system segment the hardware task switch was designed around. The book uses one, only for its ESP0 and SS0 fields, which tell the processor which stack to use when an interrupt arrives in ring 3 (chapter 13).
UEFI: The firmware interface that has replaced the BIOS on new PCs: it starts the processor in 64-bit mode and loads a PE executable from a FAT partition instead of a boot sector (chapter 17).
User stack: The one page mapped just below USER_STACK_TOP, 0x80000000, in a user program’s address space, writable from ring 3. ESP points into it when the program starts, and the processor leaves it for the task’s kernel stack on every interrupt and system call (chapter 13).
VGA text mode: The 80 by 25 character display the BIOS leaves the screen in: two bytes per cell, character and attribute, at physical address 0xB8000, with a hardware cursor driven through the CRT controller ports (chapter 10).
Virtual memory: The illusion, built with paging, that each program has a contiguous memory of its own, independent of where the physical frames are and of what other programs do (chapter 12).
volatile: The C qualifier that tells the compiler a variable can change for reasons it cannot see, an interrupt handler or a device, so that every access must really be performed (chapters 10 and 11).
Watchpoint: A gdb breakpoint on data rather than code: watch variable stops when the variable changes and names the old value, the new one and the line that wrote it. On a running processor it uses the debug registers, of which there are four, which bounds the number of watchpoints on real hardware (chapter 16).
Zero page: A single frame of zeros that a kernel maps read-only and copy-on-write wherever a program reads an untouched page of its .bss, so that a page which is only ever read never costs a frame of its own; Linux does this, the kernel of chapter 15 allocates a zeroed frame on first touch instead (chapter 15).
Zombie: A task that has exited but whose resources have not yet been reclaimed, because a task cannot free the stack it is standing on; the idle task reaps it later (chapter 13).