Part One

The Physical
World

Before software, there is sand. Before logic, there is voltage. Before any program runs, a billion tiny switches must already agree on what "true" and "false" mean, and one program, the kernel, must already be standing watch. This is where the story has to begin: in the place most books skip.

CHAPTER 01
The Machine Beneath Everything
Transistors, von Neumann's insight, the CPU, and why the kernel had to be invented.
CHAPTER 02
The Algebra of Switches
Boolean logic, binary numbers, how arithmetic emerges from electricity, and IEEE 754.
CHAPTER 03
The Language the CPU Speaks
Assembly, registers, the stack, calling conventions, and how buffer overflows actually work.
BRIDGE
The Boundary
The hardware face of the kernel. Privilege rings, the trap mechanism, the MMU, the timer, MMIO, and DMA: what the silicon must provide before a kernel can keep programs apart and share the CPU among them.
Chapter 01

The Machine
Beneath
Everything

In 1936 a mathematician described, on paper, a machine that could follow any rules written down for it. Within ten years such machines were being built. This is the story of computer architecture, told in the order civilization needed it.

TopicsCPU · Memory · Kernel · OS
Era covered1936 → present
Chapter 01 hero · The Machine Beneath Everything ALU Arithmetic Logic Unit CU Control Unit REGISTERSvalues in use now CACHErecent memory CPU CORE bus bus bus RAM Main Memory I/O Devices DISK Storage KERNEL OS Core bus: shared wires; data moves both ways
01 · Context

Why does any of this exist?

For most of human history, calculation was something people did by hand. The word computer once meant a person employed to do arithmetic, and from the late nineteenth century that person was often a woman. The machine you are reading this on replaced an entire profession.

Replacing the human computer took a particular insight: that thinking itself could be mechanised. It applies to one kind of thinking only: following fixed rules step by step, so that the same input always gives the same output. That was exactly the work human computers did.

The 1936 paper that changed everything

In 1936, a 24-year-old Cambridge mathematician named Alan Turing published a paper titled On Computable Numbers, with an Application to the Entscheidungsproblem. The title's last word is German for "decision problem" and names a question David Hilbert had posed in 1928: is there a mechanical procedure that, given any mathematical statement, will decide whether the statement is true or false?

Turing's answer was no. To prove it, he first pinned down what "mechanical procedure" meant by imagining a device: an endless tape of cells, a head that reads and writes one cell at a time as it moves, and a finite set of rules saying what to do for each symbol under the head and each state the machine can be in. A machine's rules, its program, can be written as symbols on a tape for another machine to read. The modern form of his proof narrows Hilbert's question to one case: can a machine read any program and decide whether it will ever stop? A program is only symbols and rules, so "this program stops" is a mathematical statement, and a procedure that decides every statement would settle it. Suppose such a decider exists. Build a program that runs the decider's rules on a copy of itself, asking "will this very program stop?", and then does the opposite: told it will stop, it loops forever; told it will never stop, it stops. The decider is wrong about this program either way, so it cannot exist, and neither can Hilbert's procedure.

He called his imagined device an a-machine, for automatic machine; we now call it a Turing machine. He also showed that one machine, with the right rules, can read any other machine's rules from its tape and do whatever that machine would do. He called such a machine universal. It is the first formal description of what we now call a computer.

Fig 1.1 · A Turing machine · three marks become four
Fig 1.1 · A Turing machine · three marks become four A tape holds three tally marks. A head reads one cell at a time and follows two rules: on a mark, move one cell right; on an empty cell, write a mark and stop. It walks past the three marks, writes a fourth in the first empty cell and stops: 3 plus one is 4. head move right write, stop 3 + 1 = 4

The head reads one cell at a time and does what the matching rule says: on a mark it moves right, on an empty cell it writes a mark and stops. Following just these two rules, it has added one.

How it works
  1. Turing's model. In 1936 Turing analysed what a person does when computing by rules with pencil and paper: looks at a few squares, keeps a state of mind, writes, moves on. His machine is that person reduced to parts: tape for the paper, head for the eye and pencil, rules for the rulebook.
  2. Tape. An endless row of cells, one symbol in each; the head sees one cell at a time.
  3. Rule. For the current state and the symbol under the head, a rule says what to write, where to move and which state comes next.
  4. This program. The marks count like tallies, one mark for each unit: walking right to the first empty cell and writing a mark there adds one.
  5. Universal. A machine whose rules read another machine's rules from its tape can run any of them: the universal machine of the text.

"We can only see a short distance ahead, but we can see plenty there that needs to be done."

Alan Turing, 1950

The war that built the first computers

Theory met urgency in 1939. Britain needed to read German messages scrambled by the Enigma machine (Fig 1.2), whose settings changed every day and could be chosen in more than 158 quintillion ways, far too many to try by hand. At Bletchley Park, Turing designed the Bombe, an electromechanical machine built to find the day's setting. Codebreakers could often guess a few words of a message, such as a weather report, and Enigma had a flaw that narrowed the search: it never turned a letter into itself, so the guessed words could only sit where none of their letters matched the scrambled letter beneath. The Bombe did not try every setting. It raced through the positions of Enigma's turning wheels, the rotors, and threw out each one that could not have turned the guessed words into the scrambled text, leaving a handful for people to check. Later, his colleague Tommy Flowers built Colossus, the first programmable electronic digital computer, set up with switches and plugs for different tests against the Lorenz cipher of Hitler's high command. Each machine served one purpose only, so neither was universal in Turing's sense, but together they proved that mechanical computation worked at scale.

Fig 1.2 · Enigma · one key, a different lamp every press
Fig 1.2 · Enigma · one key, a different lamp every press The key A is pressed three times. Each press steps the fast rotor one position before the current flows, so the current takes a different path out through three rotors, turns in the reflector, and returns on another wire: the lamps F, then E, then C light. The reflector never sends a letter back to itself. KEY · LAMP ROTORS REFLECTOR B C D A A steps each press A B C D E F F E C PRESS A THREE TIMES A → F A → E A → C out back 6 of 26 contacts

The same key, pressed three times, lights three different lamps: each press steps the fast rotor, so the current takes a new path out and, after the reflector, a different one back. The reflector also guarantees that no letter is ever enciphered as itself, the flaw the Bombe exploited.

How it works
  1. Press. The fast rotor steps one position first, so its wiring meets the contacts differently every time.
  2. Out. The current runs through the three rotors, each a fixed scramble of 26 wires.
  3. Turn. The reflector pairs contacts and sends the current back through the rotors on another wire.
  4. Lamp. It arrives at a different letter, and never at the one pressed.
  5. The settings. Rotor order, start positions and plugboard pairs gave more than 158 × 1018 possible settings, changed daily.

Some historians estimate that the codebreaking at Bletchley Park shortened the war in Europe by two years or more. The question after the war became how to build a machine that isn't purpose-built for a single problem: a universal machine, Turing's theoretical idea, in actual hardware.

Historical note. Turing was prosecuted for homosexuality in 1952 and given probation on condition of chemical castration. He died of cyanide poisoning in 1954; the inquest ruled it suicide. Britain issued a formal apology in 2009, and he now appears on the £50 note.

02 · The Transistor

Everything is sand

The first general-purpose electronic computer, ENIAC (1945), was built from vacuum tubes: glass bulbs that controlled electrical current using a heated filament inside a vacuum. ENIAC had 17,468 of them. It had thirty metres of cabinets lining the walls of a room, weighed thirty tons, consumed 150 kilowatts, and broke down on average every two days because a tube would burn out.

To make computers smaller, faster, more reliable, and affordable, the vacuum tube had to go. Its replacement was invented in 1947 at Bell Labs in New Jersey by John Bardeen and Walter Brattain, physicists in William Shockley's group. Bell Labs named it the transistor, a contraction of transfer resistor.

Fig 1.3 · The replacement · the same switch, without the fire
Fig 1.3 · The replacement · the same switch, without the fire One small control signal drives both devices. When it turns on, electrons flow and both lamps light. In the vacuum tube a filament, kept glowing hot, boils off electrons that the plate catches only when the grid, the switch, lets them through. In the transistor the control goes to the base of a small piece of crystal and current flows through it. VACUUM TUBE 1906 TRANSISTOR 1947 lamp plate catches electrons grid the switch filament, always hot crystal base SMALL CONTROL SIGNAL off on

A vacuum tube and a transistor do the same job: a small control signal decides whether a much larger current flows. The transistor does it in a sliver of crystal, with no glass, no glowing filament and nothing to burn out.

How it works
  1. Tube. A filament, kept hot, boils electrons off; the plate draws them across the vacuum; the grid between them, set by the control signal, lets them through or holds them back.
  2. Transistor. The control signal goes to the base, and current flows through the crystal between the other two terminals (the next figures open it).
  3. Why it won. A tube is hot, fragile and wears out: one of ENIAC's 17,468 tubes failed about every two days. A transistor has nothing to burn out, and it shrinks.

What a transistor actually is

A transistor is a switch with no moving parts, flipped by electricity instead of a finger. A small voltage on its base (the control terminal) lets a much larger current flow between the other two, the collector (one end of the path) and the emitter (the other end); with no voltage there, nothing flows.

Off and on can stand for 0 and 1. Two switches in a row let current through only when both are on, a rule called AND. Circuits that apply such rules, wired together, can add numbers, hold them and carry out a program like a Turing machine's (Chapter 2 builds these circuits, called logic gates, up to one that adds).

Fig 1.4 · Transistor as a switch · base off, base on
Fig 1.4 · Transistor as a switch · base off, base on Two identical transistors, each wired from + through a lamp to −. On the left the base is at 0 volts: no current flows between collector and emitter and the lamp is dark. On the right the base is at 0.7 volts: electrons flow through and the lamp lights. + − 0 V collector base emitter no current + − 0.7 V current flows

Left, 0 V on the base and the lamp stays dark; right, 0.7 V and it lights. This is the older kind of transistor; modern chips are built from the field-effect kind, opened in Fig 1.5.

How it works
  1. Three terminals. Collector and emitter carry the current; the base controls it.
  2. The threshold. In this kind of transistor about 0.7 V on the base opens the path; below it, almost nothing flows. In the field-effect transistors of modern chips the control terminal is called the gate (Fig 1.5).
  3. The dots. Electrons, drifting from emitter to collector for as long as the base signal is there.

Why semiconductors

A switch with no moving parts cannot open a gap in a wire, so the material itself must stop and start conducting when told. A semiconductor, a material whose conductivity sits between a conductor (like copper) and an insulator (like glass), can be made to. In pure silicon the atoms bond by sharing their outer electrons, so almost none move freely. What changes that is doping: salting the silicon with a trace of another element. An added atom with one more outer electron than silicon has no bond for the extra one, which wanders free (n-type silicon); one with one fewer leaves a gap in a bond, a "hole" (p-type).

A field-effect transistor puts p-type silicon between two n-type regions, the source and the drain. Where the kinds meet, free electrons drop into the nearby holes and leave a thin barrier with nothing free to move, so no current flows. Over the p-type silicon, on a thin insulating oxide, sits the third terminal, the gate, which does the base's job: a voltage on it draws free electrons out of the source and drain and in under the gate, where they form a bridge (Fig 1.5). Silicon and oxide both come from sand, which is mostly silicon dioxide: the silicon is refined from it, and the oxide is the same compound.

Fig 1.5 · Inside the switch · a field-effect transistor in cross-section
Fig 1.5 · Inside the switch · a field-effect transistor in cross-section A slab of p-type silicon with two n-type regions, the source and the drain, and between them a gate resting on a thin insulating oxide. With the gate at 0 V there is no path. With the gate off, the free electrons (blue dots) sit in the source and drain. A positive gate voltage acts through the oxide as a field and draws them in from both sides into a thin channel under it, and they flow along it from source to drain. source drain no voltage + voltage p-type silicon n-type n-type gate oxide electron field no path · no current channel · current flows

A positive voltage on the gate draws electrons in from the source and drain until they form a thin channel under the oxide, and current flows. The gate never touches them: its charge pulls through the insulator, as a rubbed balloon lifts hair, and that influence across a gap, an electric field, names the field-effect transistor.

How it works
  1. The silicon. The body is p-type silicon, doped with electron-accepting atoms; the source and drain are n-type, rich in free electrons. With the gate off, nothing joins them.
  2. The field. The gate's voltage acts across the oxide as an electric field. No charge crosses the insulator.
  3. The channel. The field gathers electrons, drawn in from the source and drain, under the oxide until that thin layer inverts, from p-type to n-type, and conducts.
  4. The name. MOSFET: metal-oxide-semiconductor field-effect transistor. A modern CPU holds billions of them, each a few tens of nanometres across.

In 1958, Jack Kilby at Texas Instruments made the first integrated circuit: a transistor and the other parts of a small circuit, formed in one piece of germanium (another semiconductor), though still joined by hand with fine wires. Within months, Robert Noyce at Fairchild Semiconductor conceived the same on silicon with the wiring laid on the chip itself, and his more manufacturable process became the basis of the entire industry. From then on, more parts on a chip meant smaller parts, not more wiring.

In 1965, Gordon Moore, Noyce's colleague at Fairchild and later a co-founder of Intel, observed that the number of transistors that fit on one integrated circuit was doubling about every year, and predicted it would continue; he later revised this to every two years. This pattern, Moore's Law, held for about fifty years, until around 2015, and drove the semiconductor industry's roadmap. It is why your phone, with perhaps fifteen billion transistors, exists at all.

Fig 1.6 · Moore's Law · transistors per chip, 1971 to 2024
Fig 1.6 · Moore's Law · transistors per chip, 1971 to 2024 Transistors per chip on a logarithmic scale, from the Intel 4004 in 1971 with 2,300 to the Apple M4 in 2024 with 28 billion, twelve million times more. A dashed line doubles every two years from the 4004; the chips follow it closely for more than forty years, then fall below it. 100 10 K 1 M 100 M 10 B 1971 2000 2024 ×2 every 2 years 4004 · 1971 8086 · 1978 386 · 1985 Pentium · 1993 Pentium 4 · 2000 Core i7 · 2008 Epyc · 2017 · four chips in one package M4 · 2024 4004 · 2,300 M4 · 28 B ×12 million in 53 years transistors per chip, log scale

On a log scale, where each gridline is ten times the one below (every second one is labelled), steady doubling draws a straight line. The chips follow the dashed two-year line for more than forty years, then fall below it: 2,300 transistors in 1971, 28 billion in 2024.

How it works
  1. The scale. Each gridline is ten times the one below, so growth at a steady rate of doubling is a straight line.
  2. The chips. 4004 (1971, 2,300) · 8086 (1978, 29 K) · 386 (1985, 275 K) · Pentium (1993, 3.1 M) · Pentium 4 (2000, 42 M) · Core i7 (2008, 731 M) · Epyc (2017, 19.2 B across four chips in one package) · M4 (2024, 28 B).
  3. The line. Doubling every two years from the 4004. Across the whole span the chips doubled about every two and a quarter years.
1947
The transistor invented at Bell Labs

Bardeen and Brattain show the first working transistor on December 23, 1947; with Shockley, they share the 1956 Nobel Prize.

1958
First integrated circuit

Silicon wins over germanium because it grows a better insulating oxide on its own surface.

1965
Moore's Law stated

Moore's article, "Cramming More Components onto Integrated Circuits", appears in the magazine Electronics in April 1965.

1971
Intel 4004: first commercial microprocessor

The 4004 put a whole processor, the part that carries out a program's instructions, on one chip: 2,300 transistors, paced by a clock ticking 740,000 times a second. Intel built it for a Japanese calculator maker.

2024
Apple M4 chip

Apple's M4 holds 28 billion transistors on a 3-nanometre process, each smaller than the width of a flu virus. The doubling has slowed since about 2015, as physical limits near.

Fig 1.7 · ENIAC and the Apple M4 · the same job, 79 years apart
Fig 1.7 · ENIAC and the Apple M4 · the same job, 79 years apart ENIAC, 1945: a U of cabinets, thirty metres of them in all, lining the walls of a room, a person drawn for scale, 17,468 vacuum tubes, 30 tons, 150 kilowatts; now and then a tube burns out. The Apple M4, 2024: a chip under a fingertip with 28 billion transistors, about 1.6 million times as many switches. ENIAC · 1945 a person 10 m 17,468 vacuum tubes 30 tons · 150 kW ×1.6 million switches 79 years later APPLE M4 · 2024 a fingertip 28 billion transistors

ENIAC's thirty metres of cabinets held 17,468 vacuum tubes; the M4 fits under a fingertip and holds 28 billion transistors, about 1.6 million times as many switches. Each is drawn at its own scale: in life ENIAC's row of cabinets is some two thousand times longer than the chip.

How it works
  1. The same job. Both machines flip switches according to instructions; what changed is the size of the switch, from a glass tube to a speck of silicon.
  2. The red flashes. As the figure plays, a tube burns out. ENIAC lost one about every two days; a chip's transistors run for years.
  3. The numbers. 28,000,000,000 ÷ 17,468 ≈ 1.6 million. (From the 4004 of 1971 to the M4 the factor is twelve million: Fig 1.6.)
03 · The Architecture

Von Neumann's insight: instructions are data

Early computers were hardwired. To set up a new calculation on ENIAC, its operators (almost all women, called "the ENIAC girls") unplugged and replugged cables for days. To change what the machine did, you changed the machine.

In 1945 the mathematician John von Neumann wrote the First Draft of a Report on the EDVAC, the machine ENIAC's builders planned as its successor. It described a different architecture, one that nearly every computer built since has followed.

The report's central idea: store the program itself in memory, alongside the data it operates on. Turing's universal machine had done this on paper; the report turned it into a design for real hardware, with one fast memory holding both. Instructions and data are both patterns of bits (ones and zeros), and the processor (the CPU) reads both the same way, so a program can read, change or create another program: a compiler, which turns code in a language such as C into the CPU's own instructions, is a program that writes programs.

A stored-program computer is never rewired: to change what it does, you load a different program into its memory. Each instruction is a number in bits: a code for an operation plus the number of the memory cell or the value it works on. The CPU's program counter names the next cell to run; that cell is read as an instruction, and any cell the instruction names, as data. In Fig 1.8, load A copies the 5 in cell 3 (A is the program's name for that cell) into a register (a slot in the CPU holding one value); add B adds the 3 in cell 4, and store C writes the 8 into cell 5.

Fig 1.8 · Von Neumann architecture · one memory, one bus
Fig 1.8 · Von Neumann architecture · one memory, one bus One memory holds a three-instruction program (load A, add B, store C) and its data (A = 5, B = 3, C = 0). The CPU fetches each instruction over the single bus, then the data it needs over the same bus; the ALU adds 5 and 3; the result 8 travels back up the bus into C. MEMORY · ONE STORE FOR BOTH 0 load A 1 add B 2 store C 3 A = 5 4 B = 3 5 C = 0 C = 8 bus I/O CPU control load A add B store C register 5 8 ALU 5 + 3 = 8 code data

One memory holds the program and its data; one bus, shared wires that the input and output devices (I/O) also use, carries both to the CPU one transfer at a time. There the control unit reads each instruction and the ALU (arithmetic and logic unit) computes.

How it works
  1. Fetch. The program counter names the next cell; its instruction travels over the bus to the control unit.
  2. Execute. The instruction asks for data, which travels over the same bus; the ALU does the arithmetic: 5 + 3.
  3. Store. The result goes back up the bus into memory, and the counter moves on.
  4. One bus. Code and data share it, so they take turns: the bottleneck the next sections return to.

The von Neumann bottleneck

Because instructions and data share one memory, they share one bus, and it carries one transfer at a time: even fetching the next instruction is one. While CPUs got faster over the decades (their clocks went from hundreds of thousands of ticks a second to billions), main memory became faster much more slowly. A modern CPU performs a basic operation in under a nanosecond (a billionth of a second); a round trip to main memory takes about sixty nanoseconds. Without help, the CPU would spend most of its time waiting.

The main remedy is a hierarchy of caches: small, fast memory built into the CPU that holds copies of recently used data, so most reads never make the trip to main memory. Much of CPU design since the 1980s is an effort to work around this bottleneck.

04 · The CPU

Fetch. Decode. Execute. Repeat.

Every CPU ever built does the same four things in a loop, today billions of times per second.

This loop is the instruction cycle. The program counter holds the address of the next instruction. In Fig 1.8 each cell held a whole instruction; a real memory numbers every byte (eight bits), and an instruction may take one byte or several. Fetch: the CPU reads the instruction's bytes out of memory. Decode: the control unit works out which operation those bits ask for and which registers or values it acts on. Execute: the unit that does the work (usually the ALU) carries it out, adding, comparing, or computing an address. Writeback: the result is stored back into a register or memory, and the program counter moves to the next instruction. Then the cycle starts over, on every core (a complete copy of this machinery). Fig 1.9 writes addresses in hexadecimal (0x), base sixteen, because each of its digits, 0–9 or A–F, stands for exactly four bits.

Fig 1.9 · The instruction cycle · fetch, decode, execute, writeback
Fig 1.9 · The instruction cycle · fetch, decode, execute, writeback Four stages on a ring: fetch, decode, execute, writeback. One instruction goes round per cycle. In the middle the program counter and the instruction: mov eax, 5 at 0x00, add eax, 3 at 0x05, jmp 0x00 at 0x08, a jump that sends the counter back to 0x00. Fetch from memory Decode what to do Execute do it Writeback store, move on program counter 0x00 mov eax, 5 0x05 add eax, 3 0x08 jump back to 0x00 jmp 0x00 THE PROGRAM 0x00 mov eax, 5 0x05 add eax, 3 0x08 jmp 0x00

Follow the program counter: 0x00, then 0x05, then 0x08 (addresses written in hexadecimal, here the same as 0, 5 and 8), because the first instruction takes five bytes and the second three; at 0x08 the jump sets it back to 0x00, so the program loops.

How it works
  1. Fetch. Read the bytes at the address in the program counter.
  2. Decode. Work out the operation and its operands from the bit pattern (Fig 1.10 takes one apart).
  3. Execute. The ALU or another unit does the work: an addition, a comparison, an address.
  4. Writeback. Store the result and move the counter on by the instruction's length; a jump sets the counter instead.

What an instruction actually is

To the hardware, an instruction is a pattern of bits, and the control unit is a circuit that turns each pattern into a particular sequence of internal signals. The mapping from bit patterns to operations is called the instruction set architecture, or ISA. Intel and AMD CPUs use the x86 ISA; Apple Silicon Macs, your phone and the Raspberry Pi use ARM. The two are incompatible: code compiled for one will not run on the other unless translated.

Assembly language gives each pattern a human-readable name, and a program called an assembler translates the names into bits, one for one: mov eax, 5 becomes 10111000 00000101 00000000 00000000 00000000 on x86. We will spend all of Chapter 3 on this.

x86 assembly 
; A simple addition program
; The steps behind an addition like C's "a + b", with a = 5 and b = 3 held in registers

mov  eax, 5        ; load the value 5 into register EAX
mov  ebx, 3        ; load the value 3 into register EBX
add  eax, ebx      ; EAX = EAX + EBX, result is now 8

; In memory, "add eax, ebx" is just two bytes: 01 D8
; The CPU's decoder maps this pattern to "ALU add" with
; source EBX and destination EAX. Then the ALU performs it.
Fig 1.10 · From assembly to binary · one instruction decoded
Fig 1.10 · From assembly to binary · one instruction decoded mov eax, 5 assembles to five bytes, B8 05 00 00 00. The first byte, B8, is 10111 000 in binary: the top five bits mean move a 32-bit value into a register, the bottom three name the register, 000 for EAX. The next four bytes are the value 5, stored lowest byte first; read in reverse they are 00 00 00 05. Result: EAX holds 5. YOU WRITE mov eax, 5 assembler IN MEMORY · 5 BYTES B8 05 00 00 00 B8, BIT BY BIT 1 0 1 1 1 0 0 0 MOV a value into a register EAX register 000 THE VALUE · LOW BYTE FIRST 05 00 00 00 00 00 00 05 = 5 EAX ← 5

One instruction as the CPU sees it: the first byte says what to do and to which register, the next four hold the value, lowest byte first.

How it works
  1. Opcode. B8 is 10111 000. The top five bits mean “move a 32-bit value into a register”; the bottom three name the register, and 000 is EAX.
  2. Value. x86 is little-endian: it stores the lowest byte first, so 5 sits in memory as 05 00 00 00.
  3. Decode. The decoder is a circuit that recognises these bit patterns and routes them to the right units; nothing is looked up by name.

Pipelining and parallelism inside one core

Instead of finishing one instruction before starting the next, modern CPUs use pipelining: they cut the four steps into stages and overlap the stages of different instructions, like an assembly line. While instruction 3 is being executed, instruction 4 is being decoded, and instruction 5 is being fetched. Fig 1.11 adds a fifth stage, MEM, for reading or writing data in memory; a modern pipeline may have 14 to 20. Each stage takes one clock tick, or cycle.

Fig 1.11 · Pipelined execution · five instructions, five stages
Fig 1.11 · Pipelined execution · five instructions, five stages A grid of cycles 1 to 9 across and instructions 1 to 5 down. Each instruction passes through fetch, decode, execute, memory and writeback, starting one cycle after the one before, so the stages form a diagonal and all five finish by cycle 9. Run one at a time, they would need 25 cycles. A key under the grid spells out the stage labels: IF fetch, ID decode, EX execute, MEM memory, WB writeback. 1 2 3 4 5 6 7 8 9 cycle i1 IF ID EX MEM WB i2 IF ID EX MEM WB i3 IF ID EX MEM WB i4 IF ID EX MEM WB i5 IF ID EX MEM WB IF fetch · ID decode · EX execute MEM memory · WB writeback one at a time 25 cycles pipelined 9 cycles

Five instructions of five stages each, overlapped like an assembly line, finish in 9 cycles instead of 25. Each still takes five cycles; the gain is that once the pipeline is full, one instruction completes every cycle.

How it works
  1. The stages. IF fetch · ID decode · EX execute · MEM memory access · WB writeback.
  2. The diagonal. Each instruction starts one cycle after the one before, so the instructions in a column are always in different stages; in cycle 5 all five stages are busy at once.
  3. Beyond this. Modern CPUs also duplicate stages and finish several instructions in one cycle.

Modern CPUs also use out-of-order execution. If instruction 5 doesn't depend on instruction 4's result, the CPU may execute 5 first while 4 waits for memory. Speculative execution goes further. At a branch, a jump taken only if some condition holds (an if in a program), the pipeline must keep fetching before the condition is known, so the CPU guesses which way it will go and runs ahead on that path. A right guess keeps the work and saves the wait; a wrong one throws it away.

Fig 1.12 · Speculative execution · the CPU guesses, then checks
Fig 1.12 · Speculative execution · the CPU guesses, then checks A branch, jne loop_start (jump if not equal), whose condition is not known yet. The CPU guesses and runs the guessed path ahead: add, load from memory, compare; the load brings its data into the cache. When the guess is right the work is kept. When it is wrong the guessed path is thrown away and the other path runs (mov, then jump to exit), but the loaded data is still in the cache. jne loop_start ; jump if not equal ? ✓ ✗ guessed path other path add eax, 1 load from memory compare ebx, 0 mov eax, 0 jump to exit CACHE loaded data, still there right · ~95% keep the work wrong · ~5% throw it away

The guessed path runs before the branch is decided. If the guess is wrong its work is thrown away, but the data it loaded stays in the cache, a trace that the attacks described below, Spectre and Meltdown, read.

How it works
  1. Why guess. Waiting for the condition would leave the pipeline idle for many cycles.
  2. The guess. Made from the branch's history; modern CPUs are right about 95% of the time.
  3. The catch. Throwing work away rolls back the registers, not the cache. A load that should never have run leaves its data behind, and an attacker can time the cache to find it.

Spectre and Meltdown (2018). Spectre affects nearly every fast processor made since the mid-1990s, Meltdown mainly Intel's; both let a program read memory it may not see, such as another program's passwords. Both exploit speculative execution. The CPU runs ahead (in Meltdown, past a permission check that will fail; in Spectre, down a wrongly guessed branch) into work that reads a secret byte. That work then loads one of 256 memory locations, the one numbered by the byte's value (a byte has 256 possible values). The work is thrown away, but the loaded location stays cached, so the attacker times a read of each of the 256: the one that answers fast gives away the byte. Chapter 16 returns to them.

05 · The Kernel

Why the kernel had to be invented

In the 1950s, running a program meant booking the entire computer for yourself: you handed in your stack of punched cards, the machine ran it alone, and you came back later for the printout.

Fig 1.13 · Running a program in 1955 · one job, one user, one machine
Fig 1.13 · Running a program in 1955 · one job, one user, one machine An illustrative hour. You hand in your deck of punched cards at 9:00 and wait. The machine runs one job at a time: four jobs, yours from 9:30 to 9:40, with idle gaps between them while the operator loads the next deck. At 10:00 you collect your printout. 9:00 9:30 10:00 you waiting CPU yours yours running a job idle: the next deck loading an illustrative hour

An illustrative hour: your job runs for ten minutes of it, and between jobs, while the operator loaded the next deck, the most expensive machine in the building sat idle.

How it works
  1. A job. A deck of punched cards, roughly one line of program per card, carried to the machine room.
  2. The queue. The operator loaded decks one after another; each job had the whole computer while it ran.
  3. The cost. A bug meant new cards and another hour's wait, and the machine stood idle in the gaps.

As computers got faster, the CPU sat idle most of the time even while a job ran, waiting for slow input/output (I/O) devices such as card readers and tape drives. Universities started asking: can one program run while another waits for I/O? Can different users be logged in at once?

The answer was time-sharing: programs taking turns on one CPU, so quickly that each user seems to have the machine alone. Running the turns takes something between the programs and the hardware: the operating system kernel, the one program that stays loaded. A program that needs something slow (a disk, a keypress, a network reply) must ask the kernel, and asking makes the CPU jump into the kernel's code. While the program waits, the kernel saves where it stopped (its program counter and registers) and gives the CPU to another program with work ready; when the data arrives, it reloads that program's counter and registers and the program carries on. A program that never asks is interrupted anyway: a hardware timer hands the CPU to the kernel every few milliseconds. Programs sharing a machine must not trample each other, so the kernel owns the hardware and every other program must ask its permission to touch it (Fig 1.14).

Fig 1.14 · Protection rings · user programs, the kernel, the hardware
Fig 1.14 · Protection rings · user programs, the kernel, the hardware Three layers: user programs in Ring 3, the kernel in Ring 0, the hardware below. A program that reaches straight for the disk is stopped at the boundary by the CPU. The same request made as a system call traps into the kernel, which drives the disk and returns the result to the program. USER PROGRAMS · RING 3 KERNEL · RING 0 HARDWARE your program browser editor driver scheduler disk network RAM blocked system call

The CPU runs each program at a privilege level, or ring: Ring 3 for programs, Ring 0 for the kernel. The red path, a program reaching straight for the disk, is blocked; the gold one, a request to the kernel called a system call, is let through.

How it works
  1. The rings. x86 has four privilege levels; operating systems use two: Ring 0 for the kernel, Ring 3 for everything else.
  2. Enforced in silicon. In Ring 3 the CPU itself refuses privileged instructions and the kernel's memory; no software stands in the way to be fooled.
  3. Driver, scheduler. Two parts of the kernel: a driver gives a device its orders; the scheduler decides which program gets the CPU next (the turns of the text).

The system call: crossing the boundary

When your program opens a file, it cannot touch the disk itself: in Ring 3 it may not give the disk orders. Instead it asks the kernel through a system call, the one instruction whose whole job is to cross the boundary: it switches the CPU to Ring 0 and jumps to an entry point, an address the kernel chose at boot, so a program can ask but never pick where it lands. The kernel checks permission and does the work, and your program gets back a small number (a file descriptor) that names the file in every later read or write. The Bridge, the short chapter that closes Part I after Chapter 3, shows how the CPU makes that crossing safe; Chapter 4 shows what the kernel does with the request.

That boundary, enforced by the CPU itself, is the foundation of operating system security: without it, every program could read every other program's memory, every file and every network packet.

UNIX and the kernels we still use

In 1969, at Bell Labs, Ken Thompson and Dennis Ritchie designed an operating system called UNIX around a four-word creed: everything is a file. A file on disk, the keyboard and, in later versions, a network connection or even a running program are all read and written through file descriptors, so once a program holds one, the same read and write calls work on any of them. The kernel calls each running program a process: on Linux, reading the file /proc/1234/status returns process 1234's name and memory use as text. UNIX became the model for most operating systems in use today (Linux, macOS, iOS, Android), and the ideas it spread (processes, file descriptors, the system call interface) define what an operating system is. Chapter 5 tells the story of C, the language it is written in.

Why this matters for security. In a privilege escalation attack, a malicious program running in Ring 3 gains Ring 0 power, for instance through a bug in the kernel code that handles its requests. If it succeeds, it controls the whole machine: it can read any file and watch any keypress. Every major operating system has had such bugs, which makes the kernel the most security-critical code on any computer. Part II's kernel chapter and Part IV's security chapter return to it.

06 · Memory

The hierarchy of forgetting

A computer's memory is a hierarchy of storage, managed at different levels by the CPU and the kernel, that grows larger, slower and cheaper the further it sits from the CPU. Each level holds a copy of part of the level below it.

Section 03's gap, on one scale: arithmetic takes about 0.3 nanoseconds, a round trip to main memory (RAM) 60 nanoseconds, two hundred times longer, and a read from a fast SSD (solid-state drive) 50,000 nanoseconds, about 167,000 times longer than the arithmetic. Hiding the gap to RAM is the job of the caches: three levels of them, L1 to L3, sit between the CPU and RAM.

LevelLocationTypical sizeAccess timeManaged by
RegistersInside the CPU core~1 KB1 cycle (~0.3 ns)Compiler, CPU
L1 CacheOn the CPU die32–64 KB4 cycles (~1.2 ns)CPU hardware
L2 CacheOn the CPU die1–3 MB12 cycles (~3.6 ns)CPU hardware
L3 CacheOn the CPU die, shared by cores8–64 MB40 cycles (~12 ns)CPU hardware
RAM (DRAM)On the motherboard8–128 GB~200 cycles (~60 ns)OS kernel
SSD (NVMe)On the PCIe bus256 GB – 4 TB~50,000 nsOS + filesystem
HDD (spinning disk)SATA bus1–20 TB~5,000,000 nsOS + filesystem
Fig 1.15 · The hierarchy of forgetting · bigger and slower at every step
Fig 1.15 · The hierarchy of forgetting · bigger and slower at every step Seven levels from registers to hard disk, each bar longer (more capacity, log scale) and slower. If a register access took one second, L1 would take 4 seconds, L2 12, L3 40, RAM 3 minutes, an SSD 2 days and a hard disk 6 months. A first read misses every cache and fetches from RAM, leaving copies in L3, L2 and L1; a second read of the same data stops at L1. SIZE → 0.3 ns = 1 s REGISTERS 1 s L1 CACHE 4 s L2 CACHE 12 s L3 CACHE 40 s RAM 3 min SSD 2 days HDD 6 months bar length: size, log scale miss miss miss found found 1st read RAM · 3 min 2nd read L1 · 4 s

Each level down is bigger and far slower: at a scale where a register answers in one second, a hard disk takes six months. A cache keeps a copy of what was just read, so reading it again costs seconds, not minutes.

How it works
  1. The scale. One register access, about 0.3 ns, becomes one second; every other time keeps its ratio to it. Bar length is size on a log scale.
  2. A miss. The first read looks in L1, L2 and L3, finds nothing, and waits for RAM: about 60 ns.
  3. A copy. On the way back each cache keeps a copy of the data and its neighbours.
  4. A hit. The next read of the same data, or of data next to it, stops at L1: about 1.2 ns.
Why caches multiply speed

The hierarchy works because programs do not use memory evenly. They keep returning to the same places and the places next to them: a loop that adds up a list of numbers runs the same few instructions again and again, and reads numbers stored side by side. This is called locality of reference, and it is why a small fast cache can speed up a much larger slow memory. In numbers, the average time per access is:

Tavg = h · tcache + (1 − h) · tRAM

If the hit rate h, the share of accesses found in the cache, is 95% for L1 (tcache = 1 ns) and the other 5% miss into RAM (tRAM = 60 ns), the average access time is 0.95 × 1 + 0.05 × 60 = 3.95 ns. Without the cache, every access would cost 60 ns. The cache makes the average access roughly fifteen times faster, and the hit rate only has to be high, not perfect. The same calculation justifies every layer of the hierarchy.

Peter Denning's working set model (1968) made the idea rigorous for virtual memory (just below): a program needs in fast memory only the pages it has used recently. Processor caches rest on the same principle. It returns wherever a small fast store sits in front of a large slow one: recently used file data kept in RAM (Part II), recent web-address lookups remembered (Part III), a database's busiest data held in memory (Part IV).

Virtual memory: the lie the kernel tells

When your program asks for memory, the kernel does not give it a real physical address. It gives a virtual address, a fiction: every program sees its own private range of addresses, starting at zero and seemingly gigabytes long, as if it had the machine to itself. So two programs can both use address 1,000 and reach different places in the real memory.

Between the CPU and the RAM sits the Memory Management Unit (MMU), a piece of hardware that translates every virtual address to a physical one at the moment of access. Memory is handled in fixed-size blocks called pages, typically 4 KB (4,096 bytes), and for each program the kernel keeps page tables that say which physical page holds each of its virtual pages. Take address 1,000: it is byte 1,000 of virtual page 0. If one program's table maps its page 0 to physical page 37, the MMU reads byte 1,000 of page 37; the other program's table sends its page 0 elsewhere. The Bridge shows the hardware at work, and Chapter 4 the kernel's side.

Page tables give three things. Isolation: no program can read another's memory, because different programs' page tables point to different physical pages. Flexibility: the kernel can move pages around in RAM, send little-used ones out to disk, or read a program's file in from disk only as its pages are first used. Protection: the page tables also encode permissions for read, write and execute, and the MMU enforces them. When a program touches a page that is not in RAM, the MMU stops it with a page fault and calls the kernel, which reads the page in, updates the table and lets the program carry on, none the wiser.

Buffer overflow attacks pass the MMU's write checks, because they write only into the program's own writable memory. Each call to a function (a reusable piece of the program) keeps its buffers, fixed-size blocks for incoming data, in its own slot on the stack (the memory that function calls work in), beside its return address: the address the CPU jumps back to when the function ends. If a program writes more data than a buffer can hold, the extra bytes spill over that return address, so an attacker who controls the input can fill the buffer with instructions and aim the return address at them. Those instructions can run only if the stack's pages allow execution, so marking them no-execute (the defence called DEP) lets the MMU's execute check stop them. Chapter 3 shows the defences, among them the stack canary, ASLR and DEP, at the assembly level.

What you now understand

You have followed the chain from sand to software. Transistors, silicon switches controlled by voltage, combine into logic gates, then into integrated circuits, then into CPUs. The CPU runs an endless loop: fetch, decode, execute, writeback. It executes instructions encoded as binary patterns drawn from an instruction set architecture like x86 or ARM. Programs and data live together in the same memory, a design choice (von Neumann's) that defines what a modern computer is. The kernel mediates between programs and hardware, enforcing isolation and security through privilege rings, virtual memory and a hardware timer.

This is the substrate. Every chapter that follows builds on it. Chapter 2 goes deeper into a single layer of this stack: the layer where mathematics and electricity meet. We will look at why a computer must be binary, how George Boole invented the logic that runs on those binary signals, and how arithmetic emerges from a few simple gates. By the end of Chapter 2, you will understand why 0.1 + 0.2 does not equal 0.3 in almost any programming language.

Chapter 02

The Algebra
of Switches

In 1847, a self-taught English schoolteacher published a book reducing logic to algebra. He died in 1864, long before electricity did any computing. In 1937, ninety years after his book, a student showed that circuits of relays (switches worked by an electromagnet) obey his rules exactly, and a reshaped form of those rules became the logic every digital circuit is built from.

TopicsBoolean logic · Binary · Gates · Floats
Era covered1847 → present
Chapter 02 hero · The Algebra of Switches A · ¬B + ¬A · B · is AND, + is OR, ¬ is NOT A = 1 B = 0 NOT ¬B AND A · ¬B A = 1 NOT ¬A B = 0 AND ¬A · B OR 1 1 0 1 1 0 0 1 0 two states, the easiest to tell apart
01 · Why binary

Why a computer can only count to two

You count to ten because you have ten fingers. The Babylonians counted to sixty, perhaps from the twelve joints of one hand's four fingers times the five fingers of the other. The Mayans counted in twenties, perhaps on fingers and toes. Computers count to two because they are made of switches, each used in only two states: on and off.

The reason for two is physical: electricity reliably represents two states, but not many more. A wire either has a voltage above some threshold (call it 1) or it doesn't (call it 0), and the CPU can tell the two apart with very high reliability, even when noise and manufacturing variation nudge the voltage.

Could a computer use three voltage levels (low, medium, high) for three digits? The transistor allows it: part-way on, it lets only some of the current through and holds a wire at a middle voltage. Ternary computers have been built: the Soviet Setun of 1958 counted in balanced ternary (digits −1, 0, +1), though it stored its digits magnetically, not as voltages. But a wire works within a fixed span of voltage. Binary splits it with one threshold, leaving each level a wide margin before it is misread. Ternary must fit three levels into the same span, with two thresholds and much narrower bands, so a drift that binary would shrug off can push a level across a threshold into its neighbour. Parts age and temperatures swing, so small drifts happen all the time, which is why computers drive each transistor fully on or fully off: those two extremes are the easiest to tell apart.

Fig 2.1 · Why binary survives noise · one threshold against two
Fig 2.1 · Why binary survives noise · one threshold against two Two wires with the same voltage span and the same noise. The binary wire has one threshold and wide bands; its five bits 0 1 1 0 1 are all read correctly. The ternary wire squeezes three levels into the same span with two thresholds; a small drift on its fourth digit crosses a threshold and the 0 is read as +1. BINARY · ONE THRESHOLD 1 0 threshold 0 1 1 0 1 TERNARY · TWO THRESHOLDS +1 0 −1 0 +1 −1 +1 +1 sent 0, read +1

Two wires, the same span and the same noise: binary reads all five of its bits right, ternary misreads its fourth digit.

How it works
  1. A threshold. The reader decides a digit by which side of a threshold the voltage is on.
  2. The margin. Binary's single threshold sits halfway: a level must drift half the span to flip. Ternary's two thresholds put a level a quarter of the span from the nearest threshold, half binary's margin.
  3. The noise. Ageing parts and temperature swings make small drifts constant, so the wider margin won.

A wire that is either on or off holds one bit, short for binary digit. One wire expresses two values; two wires, four (00, 01, 10, 11); n wires, 2n. Read as numbers, binary places are worth 1, 2, 4, 8 from the right, where decimal places are worth 1, 10, 100, so 0101 is 4 + 1, or 5. Eight bits make a byte, enough to represent 256 distinct values. A CPU handles a fixed number of bits at once, its word: 64 in today's laptops and phones.

A note on counting

In any base b, an n-digit number can represent bn distinct values: three decimal digits run from 000 to 999, 10³ = 1,000 values, and three binary digits from 000 to 111, 2³ = 8. Memory works the same way: an address is a binary number, one bit per wire, so n wires name 2n memory cells, and each added wire doubles the memory a computer can reach.

02 · Boole

The Victorian schoolteacher who reduced logic to algebra

George Boole, a shoemaker's son, was born in Lincoln, England, in 1815. Taught Latin by a local bookseller, he taught himself Greek, French and German, opened his own school at nineteen with no university degree, and by twenty-five was publishing original mathematics.

In 1847 he published a short book, The Mathematical Analysis of Logic, and seven years later expanded it into An Investigation of the Laws of Thought. Their thesis was that logic, the discipline of valid reasoning, was a branch of algebra.

Boolean algebra works on statements that are either true or false, such as "it is raining". Its variables stand for truth values: true, written 1, or false, written 0. AND, written like multiplication (A · B), is true only when both statements are true: "raining and cold" is true only on a day that is both. OR, written like addition (A + B), is true when at least one is true. NOT turns true into false and false into true. Because AND and OR ask only whether something is true, the algebra has laws that would be errors in school algebra, A + A = A and A · A = A: "true or true" and "true and true" are each still just true.

"The design of the following treatise is to investigate the fundamental laws of those operations of the mind by which reasoning is performed; to give expression to them in the symbolical language of a Calculus…"

George Boole, An Investigation of the Laws of Thought, 1854

Boole died of pneumonia in 1864, aged 49, after lecturing in clothes soaked by a three-mile walk through heavy rain. He never saw electricity used in computing: he died thirty-three years before the electron was discovered. For seventy years his algebra stayed with the logicians, who reshaped it into the Boolean algebra used today.

Shannon's master's thesis: Boole's algebra in the wiring

Then, in 1937, a 21-year-old MIT graduate student named Claude Shannon wrote his master's thesis. He was working with relays: switches that an electromagnet opens or closes, so that a current in one circuit controls another. He noticed that relay circuits could be described exactly by Boolean algebra. Call an open relay 0 and a closed one 1. Wire two relays in series, one behind the other, and current can reach the far end only if both are closed: that is AND. Wire them in parallel, side by side, and current gets through if either one is closed: OR. And a relay built to spring open when its control signal arrives passes current only when the signal is absent, which is NOT.

Shannon showed that any expression in Boolean algebra could be built as a circuit of relays that physically computed it, and that a circuit could be simplified by simplifying its expression. A switch circuit computing one of the three operations is now called a gate (not the transistor's gate terminal). The computer pioneer Herman Goldstine called the thesis one of the most important master's theses ever written.

Fig 2.2 · Boole's algebra · Shannon's switches · the same AND
Fig 2.2 · Boole's algebra · Shannon's switches · the same AND Above, Boole (1847): two overlapping circles, A and B; A · B is their overlap, true only where both hold. Below, Shannon (1937): a battery, two switches in series and a lamp; current reaches the lamp only when both switches are closed. A and B step through all four cases; the overlap and the lamp light together, only for A = 1 and B = 1. BOOLE · 1847 A B A · B is the overlap SHANNON · 1937 A B two switches in series 0 0 → 0 1 0 → 0 0 1 → 0 1 1 → 1

Boole's A · B, true only where both statements hold, is the overlap of two circles; Shannon saw that two switches in series pass current only when both are closed. Ninety years apart it is the same AND, today the AND gate in every CPU.

How it works
  1. Boole, 1847. Boole worked in symbols alone; the circles are John Venn's later picture of the idea (1880). A · B, "A and B", is the set of cases where both hold, the overlap.
  2. Shannon, 1937. His master's thesis showed relay circuits obey Boole's algebra exactly. This book labels closed 1 and open 0; Shannon himself counted the other way.
  3. Series and parallel. Switches in series are AND; side by side they would be OR (Fig 2.3).

The deeper claim. Any rule that turns a fixed number of input bits into output bits can be built from gates. Take XOR, "exactly one of A and B is 1": it gives 1 when A = 0, B = 1 and when A = 1, B = 0. Give each case an AND, with a NOT on each input that is 0 there: (NOT A AND B) is 1 in the first case alone, (A AND NOT B) in the second. An OR of the two is 1 in exactly those two cases: XOR. Because each AND picks out one case, the recipe builds any rule, of three inputs or thirty. Add memory to hold bits between steps, and gates build the CPU, Chapter 1's universal machine.

03 · Logic gates

The atoms of computation

A logic gate is a small circuit of a few transistors that takes one or two input bits and produces one output bit according to a Boolean rule. There are only a handful of fundamental gates.

The three foundational gates

AND: true only if both inputs are true

ABA · B
000
010
100
111

OR: true if at least one input is true

ABA + B
000
011
101
111

NOT: flips the input (written ¬A)

A¬A
01
10

Transistors are switches worked by a voltage (Chapter 1), so gates are wired like Shannon's relays: two in series conduct only when both inputs are 1, two in parallel when either is. For NOT, two transistors take turns: a 1 at the input switches on one that connects the output to 0 volts and switches off the other, which joins the output to the supply; a 0 does the reverse, and the supply holds the output at 1.

Fig 2.3 · The three fundamental gates · AND, OR, NOT
Fig 2.3 · The three fundamental gates · AND, OR, NOT AND outputs 1 only when both inputs are 1. OR outputs 1 when at least one input is 1. NOT outputs the opposite of its one input. Each gate is drawn with its standard symbol, inputs A and B on the left, its output on the right labelled in words (A and B, A or B, not A), and its truth table with columns A, B and out; the inputs step through every case. AND A B A and B 0 1 0 1 0 1 AB out 00 0 01 0 10 0 11 1 OR A B A or B 0 1 0 1 0 1 AB out 00 0 01 1 10 1 11 1 NOT A not A 0 1 0 1 A out 0 1 1 0

AND, OR and NOT, the three gates any circuit can be built from, in their standard symbols (unchanged since the 1960s), each beside its truth table as the inputs step through every case.

How it works
  1. Reading a gate. Inputs A and B enter on the left, the output leaves on the right named in words (A and B, A or B, not A); the table beside it lists every case.
  2. The shapes. AND has a flat back, OR a curved one, NOT is a triangle with a bubble, and the bubble alone means "invert".
  3. In silicon. Each gate is a few transistors (Fig 1.5), switching in well under a nanosecond.

Universal gates: NAND alone is enough

A result that goes back to Henry Sheffer in 1913: a single gate type, NAND (NOT-AND), can imitate all three. A NAND is an AND with its output inverted; it emits 0 only when both inputs are 1. Tie its two inputs together so the same signal A feeds both: it computes NOT(A · A), and since A · A is just A, the result is NOT A: an inverter, from one NAND. Run a NAND's output into a second NAND wired as that inverter and the two inversions cancel, leaving a plain AND. For OR, invert A and B with two such NANDs and feed the results to a third. It gives 0 only when NOT A and NOT B are both 1, that is, when A and B are both 0, the one case where OR gives 0; so it is an OR (the box below gives the rule). NAND is therefore called a universal gate.

Since AND, OR and NOT can build any circuit, so can NAND alone, repeated billions of times. Real CPUs also use NOR (an OR with its output inverted), XOR and larger compound gates, each doing in one gate a job that would take several NANDs: an XOR takes four.

Fig 2.4 · Everything from NAND · NOT, AND and OR built from one gate
Fig 2.4 · Everything from NAND · NOT, AND and OR built from one gate Three circuits built only of NAND gates. One NAND with its inputs tied together is NOT. A NAND followed by that NOT is AND. Inverting both inputs and then taking their NAND is OR, by De Morgan's law. The inputs step through every case and each output matches the ordinary gate. NOT one NAND, inputs tied 0 1 0 1 AND NAND, then NOT 0 1 0 1 0 1 OR NOT both, then NAND 0 1 0 1 0 1 every gate drawn here is a NAND

NOT, AND and OR, each wired from NAND gates alone; the inputs step through every case.

How it works
  1. NAND. AND with its output inverted: 0 only when both inputs are 1. The bubble on the symbol is the inversion.
  2. NOT. With both inputs on A, NAND gives ¬(A · A), which is ¬A.
  3. AND. Invert a NAND once more: ¬(¬(A · B)) = A · B.
  4. OR. De Morgan's law: A + B = ¬(¬A · ¬B), a NAND of the two inverted inputs.
De Morgan's laws

Two identities of Boolean algebra, both due to Augustus De Morgan, a contemporary of Boole:

¬(A · B) = ¬A + ¬B

¬(A + B) = ¬A · ¬B

These laws say that a NOT can move through an AND or an OR by flipping it into the other: "not (raining and cold)" means "not raining, or not cold". They are how you simplify Boolean expressions and how chip designers turn one kind of gate circuit into another. The NAND-built OR above is the first law at work: it computes ¬(¬A · ¬B), which the law turns into ¬¬A + ¬¬B, and two NOTs cancel, leaving A + B.

04 · Arithmetic from logic

How a circuit learns to add

A computer is a machine for arithmetic, yet at the level of voltages and gates it has no idea of "five" or "twelve": it knows only ones and zeros and Boolean operations on them. It works out 5 + 3 the way you add on paper, one column at a time, carrying as it goes.

The half adder

Adding two single bits has four cases. With no digit 2, 1 + 1 is written 10, a 1 in the twos place: write 0, carry 1, just as 5 + 5 in decimal gives 0, carry 1.

Adding two single bits

ABSumCarry
0000
0110
1010
1101

The Sum column is 1 when exactly one input is 1: that is XOR (exclusive OR), the rule built in Section 02. The Carry column is exactly an AND. So a single-bit adder, called a half adder, is just an XOR and an AND sharing the same two inputs.

The full adder, and adding wider numbers

Wider numbers pass a carry from each bit position to the next, which needs a full adder: a circuit that takes three input bits (A, B and a carry-in) and gives a sum bit and a carry-out. It is two half adders and an OR gate: the first adds A and B, the second adds that sum to the carry-in, and the OR merges their carry-outs. Nothing is lost, because the first carries only on 1 + 1, leaving its sum 0, so the second cannot carry too.

To add two 8-bit numbers, you chain eight full adders, the carry-out of each becoming the carry-in of the next; 64-bit numbers take 64. This design is called a ripple-carry adder, and modern CPUs use faster variants (carry-lookahead adders) built from the same simple gates.

The ALU in the CPU of Fig 1.8 is built from gates the same way: an adder that also subtracts (next section), and circuits for multiplication and for bitwise operations, which apply one gate to each pair of matching bits (0101 AND 0011 is 0001).

Fig 2.5 · Adding 5 + 3 in binary · a ripple-carry adder
Fig 2.5 · Adding 5 + 3 in binary · a ripple-carry adder Four full adders side by side, the least significant bit on the right. A is 0101 (5), B is 0011 (3). Bit 0: 1 + 1 gives 0, carry 1. Bit 1: 0 + 1 + carry gives 0, carry 1. Bit 2: 1 + 0 + carry gives 0, carry 1. Bit 3: 0 + 0 + carry gives 1. The sum is 1000, which is 8. A 5 B 3 0 0 + ? 1 1 0 + ? 0 1 0 1 + ? 0 1 1 1 + ? 0 1 SUM 8 carries ripple right to left

Adding 5 + 3: four full adders, one per bit, the least significant on the right. Each must wait for the carry from its neighbour, so the carry ripples left and the answer, 1000, settles one bit at a time.

How it works
  1. A full adder. Adds two bits and a carry-in, and gives one sum bit and a carry-out (Fig 2.6 opens one).
  2. The ripple. Bit 0: 1 + 1 = 0, carry 1. Bits 1 and 2: the carry makes 0 again, carry 1. Bit 3: the carry alone gives 1.
  3. Wider numbers. A 64-bit add is 64 of these in a row. Real CPUs use carry-lookahead designs so they need not wait for the ripple.
Fig 2.6 · Inside a full adder · two half adders and an OR
Fig 2.6 · Inside a full adder · two half adders and an OR A full adder built from gates. A and B meet in an XOR and an AND: the first half adder. The XOR's output meets the carry-in in a second XOR and AND: the second half adder; its XOR gives the sum bit. Either AND's carry, through an OR, gives the carry-out. The inputs step through all eight cases. XOR AND XOR AND OR 0 1 A 0 1 B 0 1 carry in 0 1 sum 0 1 carry out 0 + 0 + 0 = 00 0 + 0 + 1 = 01 0 + 1 + 0 = 01 0 + 1 + 1 = 10 1 + 0 + 0 = 01 1 + 0 + 1 = 10 1 + 1 + 0 = 10 1 + 1 + 1 = 11 carry out, then sum

One full adder of Fig 2.5, opened: two half adders, each an XOR and an AND, joined by an OR, as the inputs step through all eight cases.

How it works
  1. Half adder. XOR gives the sum of two bits, AND their carry: 1 + 1 is 0, carry 1.
  2. Adding the carry. The second half adder adds the incoming carry to the first sum.
  3. One carry out. The two half adders can never both carry, so an OR is enough. Chain four of these and you have Fig 2.5.
05 · Negative numbers

Two's complement, or how to subtract by adding

A computer has no transistor that means "minus", so a negative number such as −5 has to be written in bits like any other.

The naive approach, sometimes called signed magnitude, is to reserve one bit (usually the leftmost) as a sign indicator. 0 means positive, 1 means negative; the remaining bits represent the magnitude. So in 8 bits, 00000101 is +5 and 10000101 is −5. It is simple, and almost never used for whole numbers.

It has two flaws. First, there are two zeros, 00000000 and 10000000 ("positive zero" and "negative zero"), which makes equality testing awkward. Second, and far worse, the ordinary adder gives the wrong answer: +5 (00000101) plus −5 (10000101) comes out as 10001010, which reads back as −10, not 0, because the adder adds the sign bit in like any other. Subtracting correctly would take a separate, more complex circuit that inspects the sign bits first, costing transistors, area, heat and money.

The trick: complement

The solution, used by every modern computer, is called two's complement, and with it subtraction is just addition. To represent a negative number in n bits:

Step 1Take the binary representation of the positive number.
Step 2Flip every bit (0→1, 1→0). This is "one's complement".
Step 3Add 1 to the result. This is "two's complement".

So in 8 bits, +5 is 00000101. Flip the bits to get 11111010, add 1, and 11111011 is −5. Read as a plain number, the same bits are 251, which is 256 − 5: 5 plus its flipped self is all ones, 255, and the added 1 makes 256. The pattern has two readings, 251 or −5, and the program decides which it means.

For 7 − 5, the CPU adds 7 and 11111011 on its ordinary adder, which knows nothing of signs and simply adds 251: 7 + 256 − 5, or 256 + 2. Writing 256 takes a ninth place; the register has eight, so that 1 falls off the end and leaves exactly 2. When the answer is negative, nothing falls off: 5 − 7 becomes 5 + (256 − 7) = 254, and 254, 11111110, is how two's complement writes −2. The adder itself never changes: for a subtract instruction, NOT gates flip the second number's bits on the way in, and a carry-in of 1 into the rightmost full adder adds the 1. Any width works the same way, with 2n in place of 256.

Fig 2.7 · Computing 7 − 5 = 2 with two's complement
Fig 2.7 · Computing 7 − 5 = 2 with two's complement Inside an 8-bit register, 00000111 (7) plus 11111011 (−5 in two's complement), added column by column from the right. Every column carries 1, and the final carry is a ninth bit the register cannot hold. It falls off and is dropped; what remains, 00000010, is 2. 8-BIT REGISTER 1 1 1 0 0 0 0 0 7 1 1 0 1 1 1 1 1 −5 + 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 2 1 ninth bit: no room, dropped the same adder as every addition

7 − 5 on the ordinary adder: 7 plus 11111011, with the ninth bit dropped.

How it works
  1. Making −5. Flip every bit of 5 (00000101 → 11111010) and add 1: 11111011.
  2. Why it works. 11111011 is 251, which is 256 − 5. Adding it adds 256 and takes away 5.
  3. The lost 256. 256 is the ninth bit. An 8-bit register has no place for it, so it is dropped and the answer is 2. There is no separate subtractor in any modern CPU.

An n-bit two's complement number ranges from −2n−1 to 2n−1 − 1. The patterns whose top bit is 1, half of them, are the negatives; the other half hold 0 and the positives, so 8 bits run from −128 to +127. For 32-bit signed integers, that's roughly −2.1 billion to +2.1 billion. There is one more negative number than positive because 0 takes up one of the "positive" slots.

Fig 2.8 · The two's-complement wheel · where addition wraps
Fig 2.8 · The two's-complement wheel · where addition wraps The 256 values of a signed 8-bit number around a dial: 0 at the top, positives clockwise down the right to +127, negatives up the left from −128 to −1, so +127 and −128 meet at the bottom. Adding 1 turns the pointer one notch clockwise: from +127 it lands on −128, a silent overflow; from −1 it lands on 0, the dropped carry that makes subtraction by addition work. 0 −1 +64 −64 +127 −128 +12501111101 +12601111110 +12701111111 −12810000000 −12710000001 −211111110 −111111111 000000000 +100000001 +127 + 1 = −128overflow: a silent wrap −1 + 1 = 0the carry is dropped: correct SIGNED 8-BIT · +1 TURNS ONE NOTCH

The 256 values of a signed byte sit on a wheel, not a line: adding 1 turns the pointer one notch. At the bottom +127 + 1 silently becomes −128; at the top −1 + 1 becomes 0, the same wrap that makes subtraction free in Fig 2.7.

How it works
  1. The slots. 0 at the top, positives clockwise to +127, negatives counter-clockwise from −1 to −128.
  2. The seam. 01111111 + 1 = 10000000: the top bit flips, and a top bit of 1 means negative. Nothing in the hardware complains.
  3. Every width. 32- and 64-bit integers have the same wheel, with about 4 billion and 18 quintillion slots.

Overflow and sign bugs. Adding two large positive numbers can produce a negative result: a carry runs into the top bit, which is 1 in every negative number, rather than off the end (the bottom of Fig 2.8). In 1996, an Ariane 5 rocket exploded 37 seconds after launch because a velocity value was converted to a 16-bit signed integer too small to hold it. A misread sign is a second danger. A program that copies data into a buffer first checks that the length it was handed, perhaps by an attacker, is not more than the buffer holds; −1 passes. The copying code then reads the length as unsigned: a plain number with no sign. −1 is all ones, the largest unsigned number its bits can hold, so the copy runs far past the buffer (Fig 2.9): a classic buffer overflow.

Fig 2.9 · How a signed length becomes a buffer overflow
Fig 2.9 · How a signed length becomes a buffer overflow A copy function checks that n is not more than 256, then calls memcpy with n. Called with n = −1, the check passes because −1 is less than 256. memcpy takes its length as an unsigned size_t, and on a 64-bit machine the 32 one-bits of −1 become 64 one-bits: 18,446,744,073,709,551,615. The copy runs out of the 256-byte buffer and over everything after it. copy(to, from, n), n an int: if n > 256: stop memcpy(to, from, n) called with n = −1 1 the check: −1 > 256? no, so on 2 n read as unsigned (size_t) as int (signed): 32 ones = −1 as size_t (unsigned): 64 ones = 18,446,744,073,709,551,615 3 the copy buffer next next … 256 bytes and on, over everything

The bug in three steps: the check that lets −1 through, memcpy (C's copy function) reading n as unsigned, and the copy running far past the 256-byte buffer.

How it works
  1. The check. n is a signed int, so −1 > 256 is false and the early return is skipped.
  2. Read as unsigned. memcpy's length is a size_t: unsigned, and 64 bits on a 64-bit machine. Widening the 32-bit −1 keeps it −1, which is all ones at any width (Fig 2.8), and 64 ones read as unsigned are 264 − 1.
  3. The write. The copy overruns the buffer and smashes whatever lies after it, the start of the memory-corruption attacks of Chapter 3.
  4. The fix. Use an unsigned type for sizes, or check n < 0 as well as n > 256.
06 · Floating point

Why 0.1 + 0.2 ≠ 0.3

Type 0.1 + 0.2 into almost any programming language and the answer is not 0.3 but 0.30000000000000004, in Python, JavaScript, Java and Rust alike. The languages agree because all of them store fractions the way the processor does, in binary.

Decimal already has fractions that never end: 1/3 is 0.333..., because decimal digits after the point are tenths, hundredths and thousandths, and no power of ten divides evenly by 3. Binary digits after the point are halves, quarters and eighths, so only a fraction that can be written over a power of two comes out exact: 0.5 is 1/2 and 0.25 is 1/4. But 0.1 is 1/10, and 10 = 2 × 5 has a factor of 5 that no power of two contains, so 0.1 in binary runs 0.0001100110011001100..., the pattern 0011 repeating forever. Memory is finite, so the endless expansion has to be rounded to fit, and the difference becomes a tiny error.

IEEE 754: the universal floating-point standard

In 1985 the Institute of Electrical and Electronics Engineers (IEEE) published standard 754, which defines how all modern processors represent fractional numbers. Before it, each computer maker had its own format.

The format works like scientific notation, which writes 6,500 as 6.5 × 10³: the digits, 6.5, called the mantissa, and an exponent, 3, that says where the point goes. Because the point moves, the number is called floating point, or a float. The usual 64-bit kind, double precision or a double, holds a sign bit, an 11-bit exponent and a 52-bit mantissa. The point is placed after the first non-zero digit, and in binary that digit is always 1, so it is never stored: the 52 bits of the stored mantissa are only the digits after the point, and Fig 2.10 writes the whole value as 1.mantissa.

Fig 2.10 · IEEE 754 double precision · sign, exponent, mantissa
Fig 2.10 · IEEE 754 double precision · sign, exponent, mantissa A 64-bit double is a sign bit, an 11-bit exponent and a 52-bit mantissa, read as ±1.mantissa × 2 to the power (exponent − 1023), the sign bit choosing + or −. 6.5 has sign 0, exponent 10000000001 (1025, so 2 to the 2 = 4) and mantissa 101 then zeros (1.101 in binary = 1.625): 1.625 × 4 = 6.5. −0.75 has sign 1, exponent 01111111110 (1022, so one half) and mantissa 1 then zeros (1.5): −1.5 × ½ = −0.75. ±1.mantissa × 2exponent − 1023 ± exponent · 11 bits mantissa · 52 bits 6.5010000000001101000000000… 40 more bits, all 0 sign 0+ exponent 1025 − 1023 = 2× 4 1.mantissa = 1.101 (binary)= 1.625 +1.625 × 4 = 6.5 −0.75101111111110100000000000… 40 more bits, all 0 sign 1− exponent 1022 − 1023 = −1× ½ 1.mantissa = 1.1 (binary)= 1.5 −1.5 × ½ = −0.75

6.5 and −0.75 as doubles, each read straight off its sign, exponent and mantissa bits.

How it works
  1. Sign. 0 is positive, 1 negative.
  2. Exponent. Eleven bits give a range of about 10⁻³⁰⁸ to 10³⁰⁸.
  3. Mantissa. Fifty-two bits give 15 to 17 decimal digits.
  4. Single precision. The 32-bit float is the same with 1, 8 and 23 bits.

The exponent is stored 1023 too high, so that negative powers need no sign of their own: stored 1025 means 22, 1022 means 2−1. A double rounds an endless expansion to the nearest binary fraction it can hold: 0.1 and 0.2 round up, 0.3 rounds down.

The stored 0.1 and 0.2, both slightly high, add up to a true sum exactly halfway between the stored 0.3 and the next double up. For such a tie, IEEE 754 picks the neighbour whose last binary digit is 0: here the upper one, which prints as 0.30000000000000004.

Python (or any language) 
>>> 0.1 + 0.2
0.30000000000000004

>>> 0.1 + 0.2 == 0.3
False

# The double stored for 0.1, to 20 decimal places:
>>> format(0.1, '.20f')
'0.10000000000000000555'

# The 555... is the rounding error: the endless binary
# fraction was rounded to the nearest double, a hair above 0.1.
Fig 2.11 · 0.1 + 0.2 in binary · where the famous error lives
Fig 2.11 · 0.1 + 0.2 in binary · where the famous error lives 0.1 in binary is 0.0 0011 0011 0011 and so on forever, so a double keeps its leading 1 and the next 52 bits and rounds the rest. Near 0.3 the doubles are spaced about 5.6 × 10⁻¹⁷ apart. The exact value 0.3 lies a fifth of a step above the double that 0.3 is stored as. The exact sum of the rounded 0.1 and 0.2 falls exactly halfway between two doubles, and the tie rounds up to the next double, which prints as 0.30000000000000004. 0.1 IN BINARY 0.0 0011 0011 0011 0011 0011 … repeats forever, so a double rounds it THE DOUBLES NEAR 0.3 5.6 × 10⁻¹⁷ exact 0.3 0.3 as stored true sum: a tie, rounds up 0.1 + 0.2one double up 0.1 + 0.2 prints 0.30000000000000004

The doubles near 0.3, drawn to scale: where 0.3 is stored, where the true sum of the stored 0.1 and 0.2 falls, and the double it rounds to.

How it works
  1. Why it repeats. 0.1 is 1/10, and 10 has a factor of 5 that no power of two can supply, just as 1/3 never ends in decimal.
  2. The grid. Doubles are not continuous. Near 0.3 neighbours are 2⁻⁵⁴, about 5.6 × 10⁻¹⁷, apart; the true 0.3 falls between two of them.
  3. The result. "0.3" is stored as the double just below it; the rounded 0.1 and 0.2 add up to the one just above. So in most languages 0.1 + 0.2 == 0.3 is false.
  4. Living with it. Compare floats within a tolerance, and count money in whole cents.

Special values: ±∞ and NaN

IEEE 754 reserves some bit patterns for special values, so that a calculation gone wrong keeps flowing instead of halting the machine. When the exponent is all ones and the mantissa is zero, the value is infinity, what you get when a number grows past the largest double, roughly 10308, or when a non-zero number is divided by zero (1.0 / 0.0), since dividing by ever smaller numbers gives ever larger results. The sign bit says which direction. When the exponent is all ones and the mantissa is non-zero, the value is NaN (Not a Number), the result of an operation with no meaningful answer, like the square root of −1 or 0.0 / 0.0 (every number times 0 gives 0, so no one number is the answer). A NaN spreads: any arithmetic that touches it yields another NaN, so the bad result reaches the end of the computation, where it can be spotted, instead of crashing the program where it arose.

NaN is not equal to anything, including itself: NaN == NaN, "does NaN equal NaN?", gives false wherever IEEE 754 is followed. That looks perverse until you remember what NaN means: no value at all, and two failed computations are not "the same number", because neither is a number. Since a NaN is the one value not equal to itself, x != x, "is x unequal to x?", is true only for a NaN, a classic way to catch one.

Real-world consequences. Financial software counts money in integer cents or special decimal types, because floating-point rounding errors compound across millions of transactions. The 1991 Patriot missile failure during the Gulf War, in which a Scud killed 28 American soldiers, came from the same endless 0.1. The system counted time in tenths of a second and held 0.1 in fixed point (a set number of binary places, with no exponent), so it chopped off the digits that did not fit. Every tick was a hair short, and over 100 hours the shortfall grew until the radar looked for an incoming Scud in the wrong place.

Fig 2.12 · The Patriot missile · a clock that lost a third of a second
Fig 2.12 · The Patriot missile · a clock that lost a third of a second A Patriot battery counted time in tenths of a second, but 0.1 rounded in binary made each tick about 0.000000095 seconds short. Over 100 hours, 3.6 million ticks, the clock fell 0.34 seconds behind. At a Scud's 1,676 metres per second that is about 570 metres: the radar looked for the missile where the clock said it should be, found nothing there, and the battery did not fire. CLOCK ERROR · 100 HOURS POWERED ON 0 h 50 h 100 h 0 s 0.34 s 3.6 million ticks, each 0.000000095 s short WHERE THE RADAR LOOKED window: empty the Scud≈ 570 m 0.34 s × 1,676 m/s ≈ 570 m

After 100 hours of tenth-of-a-second ticks the clock was 0.34 s behind, about 570 m at a Scud's speed, so the radar looked in the wrong place and the battery never fired.

How it works
  1. The tick. 0.1 repeats forever in binary (Fig 2.11). The system held it in a 24-bit fixed-point register, chopped, so each tick counted about 0.000000095 s too little.
  2. The sum. 100 hours is 3.6 million ticks; 3.6 million × 0.000000095 s ≈ 0.34 s.
  3. The window. The radar predicts where a target will be and looks only there. With the clock 0.34 s behind, the window was some 570 m (at Mach 5) from the Scud, on 25 February 1991.
  4. The fix. Corrected software reached Dhahran the next day. Rebooting the battery would have reset the drift.

What you now understand

You have followed the layered chain from electricity to mathematics. A wire that can be on or off gives you a bit. Combinations of bits give you binary numbers. Boolean algebra, invented in 1847 by Boole and applied to circuits in 1937 by Shannon, describes operations on those bits. Logic gates are physical implementations of Boolean operations: AND, OR, NOT, XOR. Combinations of gates implement arithmetic: half adders, full adders, ALUs. Two's complement makes subtraction free. IEEE 754 extends the system to fractional numbers, with the unavoidable cost of finite precision.

Every higher-level abstraction in computing, from a Python list to a TLS handshake to a neural network, is built on top of these primitives. Chapter 3 takes us up one level: from the gate-and-wire view to the instruction view. We will look at how the CPU executes a program, how function calls work at the metal, what a "stack" is, and how attackers exploit the gap between what programmers intend and what their compiled code does.

Chapter 03

The Language
the CPU
Speaks

Below every program, whatever language it is written in, lies a sequence of instructions in the only language a processor understands. This chapter follows your code down to them.

TopicsAssembly · Stack · ABI · Exploits
Era covered1972 → present
Chapter 03 hero · The Language the CPU Speaks THE STACK main program where to go back to add, called by main a=5 · b=3 helper, called by add newest call high address low address each callgoes below machine codemoves valuesboth ways REGISTERS the CPU's few fast slots the sum8 next stepline 7 stack tophelper inputs5 and 3
01 · ISA

An instruction is a contract

In 1978, Intel released the 8086, a 16-bit chip whose instruction set its descendants have extended but never replaced: every x86-64 processor sold today still recognises the core binary patterns Intel encoded that year. Whatever language a program is written in, the processor runs it as a sequence of binary patterns drawn from a fixed menu, the instruction set architecture (ISA) of Chapter 1. The ISA is the contract between hardware and software: hardware promises to execute every pattern in the menu correctly; software promises to use only patterns from the menu. Everything else, from compilers to applications, sits on top of this contract.

Three ISAs dominate the world. x86-64, the direct descendant of that 1978 Intel line, runs most PCs and most servers. It is complex, with thousands of instructions accumulated over four decades of backward compatibility. ARM, designed by Acorn in the 1980s and licensed to chip designers such as Apple and Qualcomm, is the modern alternative: cleaner, more efficient, and the architecture of every iPhone, every Apple Silicon Mac, and nearly every Android phone. RISC-V, from Berkeley in 2010, is an open standard: anyone can build a RISC-V chip without paying licensing fees, and it is gaining ground in academia, embedded systems, and increasingly in industry.

Fig 3.1 · Same operation · three ISAs · three encodings
Fig 3.1 · Same operation · three ISAs · three encodings "Add 5 to a register" in three instruction sets, as the 32 bits each one uses. x86-64 add rax, 5 is the bytes 48 83 C0 05: a 64-bit prefix, the opcode, a byte naming the register rax, and 5. ARM64 add x0, x0, 5 is 0x91001400: the opcode first, then 5, then the two register numbers. RISC-V addi a0, a0, 5 (addi: add a number) is 0x00550513: 5 first and the opcode last. Grey fields hold other bits. Each pattern is also written in hex. The same three ingredients sit in different places, so the other chips read each pattern differently. x86-64 add rax, 5 0 1 0 0 1 0 0 0 64-bit prefix 1 0 0 0 0 0 1 1 opcode 1 1 0 0 0 0 0 0 rax 0 0 0 0 0 1 0 1 5 in hex: 48 83 C0 05 ARM64 add x0, x0, 5 1 0 0 1 0 0 0 1 0 opcode 0 other 0 0 0 0 0 0 0 0 0 1 0 1 5 0 0 0 0 0 x0 0 0 0 0 0 x0 in hex: 0x91001400 RISC-V addi a0, a0, 5 0 0 0 0 0 0 0 0 0 1 0 1 5 0 1 0 1 0 a0 0 0 0 other 0 1 0 1 0 a0 0 0 1 0 0 1 1 opcode in hex: 0x00550513 addi: add a number opcode register name the 5 other chips read these bits differently

"Add 5 to a register" in the three instruction sets that run the world: the same three ingredients, an opcode, a register and the number 5, packed into 32 bits in three different orders.

How it works
  1. x86-64. Variable length, 1 to 15 bytes. Here a prefix (64-bit), the opcode, a byte naming rax, and the 5 itself, an immediate (a number written into the instruction), in one byte. A number too big for one byte takes four; rax has a shorter form of its own with no register byte, so this add then grows to 6 bytes.
  2. ARM64. Every instruction is exactly 32 bits; this one is opcode, a shift bit, the 12-bit immediate, then source and destination registers.
  3. RISC-V. Also 32 bits, in another order: immediate first, opcode last. The base ISA has only six formats.
  4. The order of the bits. x86 is shown byte by byte as stored; ARM64 and RISC-V as 32-bit words, high bit on the left.

Because the encodings differ, an x86 binary will not run on an ARM CPU and vice versa, so the shift from Intel x86 to Apple's ARM-based M1 in 2020 required Apple to ship Rosetta 2, a translation layer that rewrites x86 binaries as ARM ones before they run.

Fig 3.2 · Rosetta 2 · an Intel app, translated once for an ARM chip
Fig 3.2 · Rosetta 2 · an Intel app, translated once for an ARM chip Three x86-64 instructions from an Intel app: store 5 in memory, add 3 to it in place, load it into eax. Rosetta 2 translates them once, on first launch, into six ARM64 instructions that do the same work: ARM cannot add to memory directly, so the middle step becomes load, add, store. The translation is cached and runs as ARM code. A plain note beside each line says what it does; a key below says square brackets mean memory, names the registers, and repeats that ARM cannot add in memory. x86-64 · AN INTEL APP mov dword [rbp-4], 5 store 5 in memory add dword [rbp-4], 3 add 3 in memory mov eax, [rbp-4] load it into eax Rosetta 2 translates once, on first launch ARM64 · CACHED, RUNS AS ARM CODE mov w8, #5put 5 in register w8 stur w8, [x29, #-4]store w8 in memory ldur w8, [x29, #-4]load it into w8 add w8, w8, #3add 3 to w8 stur w8, [x29, #-4]store w8 in memory ldur w0, [x29, #-4]load it into w0 3 instructions in, 6 out [ ] = memory ARM can't add in memory: load, add, store rbp, x29: an address · w8, w0: registers dword: 4 bytes · #: a number

Three lines of an Intel app and the six ARM lines Rosetta 2 turns them into: storing 5 takes two (mov, stur) and adding 3 takes three (ldur, add, stur), because ARM cannot add in memory.

How it works
  1. Ahead of time. Rosetta reads the whole executable on first launch, writes an ARM version, and caches it; later launches skip the translation. Translated code runs at roughly 80% of native speed.
  2. One for many. Any x86 sequence has some ARM sequence with the same observable result; the translator's job is to find it. The ARM shown here is a faithful translation, not Rosetta's literal output.
  3. The hard part. x86 and ARM differ in the order in which one core's memory writes become visible to the others (Chapter 16). Apple's chips can enforce x86's order while translated code runs, so programs running on several cores at once behave as they did on Intel.

RISC vs CISC, and why the war ended in a draw

In the 1980s there was a vigorous debate. CISC (Complex Instruction Set Computers, like x86) had hundreds of specialised instructions, including multi-step operations like "load from memory, add, and store back" in a single instruction. RISC (Reduced Instruction Set Computers, like ARM, MIPS, SPARC) had a small set of simple, uniform instructions. They computed only in registers and reached memory only through separate loads and stores, which is why Fig 3.2's three x86 lines became six. RISC machines could clock faster, and the reason is decoding. A variable-length instruction hides its own length. Fig 3.1's x86 add spent four bytes, but other encodings of the same operation run anywhere from two bytes to a dozen, so the decoder cannot even find where the next instruction begins until it has finished parsing this one. Fixed-width instructions, always four bytes on ARM64, sit at known boundaries, so the CPU can locate and decode a whole run of them at once, and each decode step stays simple enough to fit inside a shorter clock tick.

By the 2000s the debate was over, and both sides had quietly converged. Modern x86 CPUs internally translate complex CISC instructions into simpler RISC-like micro-operations (μops) and execute those. They pay the hard variable-length parse once, then serve the code that runs most often from a small cache of already-decoded μops. Modern ARM chips have grown more complex, with specialised instructions for cryptography, vector math, and machine learning.

02 · Registers

The CPU's tiny notebook

Registers are the smallest, fastest level of the memory hierarchy from Chapter 1: a few dozen tiny storage cells inside the CPU core. Memory is too slow to compute on directly, so the CPU does its arithmetic in registers. To add two numbers from memory, it loads them into registers, adds, and stores the result back; even x86's one-instruction add to memory (Fig 3.2) takes these three steps inside the chip.

x86-64 has 16 general-purpose registers, each 64 bits wide. A few roles in the table below are built into instructions (RSP always marks the top of the stack); the rest belong to the calling convention (Section 04), the rules compilers share so that one function can call another, including which registers a called function may overwrite (the volatile or caller-saved ones) and which it must hand back unchanged. Six of them matter most here: RAX holds a function's result, RDI and RSI its first two arguments (the values handed to it when it is called), RSP and RBP its place on the stack (next section), and RIP the next instruction.

Fig 3.3 · The x86-64 register file · one register, five names
Fig 3.3 · The x86-64 register file · one register, five names RAX holds eight bytes. Its lower four bytes are also called EAX (1985), the lower two AX (1978), and those two bytes AH and AL. Starting from 11 22 33 44 55 66 77 88, mov al, 0xFF changes only the lowest byte (only AL changes). mov eax, 1 writes the lower half and clears the upper half too: 00 00 00 00 00 00 00 01. Below, the sixteen general-purpose registers: eight 8086 names, now 64-bit, and eight new in x86-64 in 2003. RAX · 64 BITS · 2003 1122334455667788 11223344556677FFmov al, 0xFFonly AL changes 0000000000000001mov eax, 1upper half cleared too RAX EAX · 1985 AX · 1978 AH AL write: THE SIXTEEN RAX RBX RCX RDX RSI RDI RBP RSP R8 R9 R10 R11 R12 R13 R14 R15 8086 names, now 64-bit new in x86-64

One register, five names: RAX (2003) contains EAX (1985), which contains AX (1978), split into AH and AL. Writing AL changes only that byte; writing EAX also clears the upper half, a rule of x86-64.

How it works
  1. The names. The 8086 had 16-bit AX, BX, CX, DX; 32-bit chips added an E for extended; AMD64, the 64-bit x86 that AMD shipped in 2003, replaced it with R and added R8 to R15.
  2. The quirk. 8- and 16-bit writes leave the rest of the register alone; 32-bit writes zero the top 32 bits.
  3. Two more. RIP, the instruction pointer, and RFLAGS, the condition codes set by most arithmetic operations, are not general-purpose.
RegisterConventional purposeWhy
RAXAccumulator: holds return values from function callsHistorical: x86's earliest predecessor used "A" for arithmetic accumulator
RBXBase: historically held the address of data in memoryNow mostly general-purpose; preserved across function calls
RCXCounter: used for loop counts and shift amountsThe rep prefix and the loop instruction take their count from RCX
RDXData: second half of multiplication results"mul" stores 128-bit results split between RAX and RDX
RSPStack Pointer: points to the top of the call stackMoves as values go on and come off the stack (next section)
RBPBase Pointer (the frame pointer): points to the current function's stack frameLets a function find its own values at fixed distances
RDI, RSI, RDX, RCX, R8, R9First six function arguments (Linux/Mac)System V ABI: the calling convention
RIPInstruction Pointer: address of next instructionCannot be written directly; changed by jumps, calls, returns and interrupts

RIP, the instruction pointer, is x86's name for Chapter 1's program counter, and it is itself a register, so changing it changes what the CPU does next. That is the entire mechanism behind a function call, a loop, an if/else branch, an interrupt, and (as we'll see) a memory corruption exploit.

Fig 3.4 · System V calling convention · which register holds which argument
Fig 3.4 · System V calling convention · which register holds which argument A call work(a, b, c, d, e, f, g) with seven arguments. Under the System V AMD64 convention the first six go into the registers RDI, RSI, RDX, RCX, R8 and R9 in that order; the seventh is passed on the stack. The function's result comes back in RAX and lands in r. THE CALL int r = work( a , b , c , d , e , f , g ); RDI 1 RSI 2 RDX 3 RCX 4 R8 5 R9 6 STACK · ARGUMENTS 7 ONWARD a b c d e f g RAX resultr

Under the System V convention (Linux, macOS, BSD) the first six integer or pointer arguments travel in RDI, RSI, RDX, RCX, R8 and R9, the seventh and beyond on the stack, and the result comes back in RAX. That agreement lets code from any compiler call any other.

How it works
  1. Registers first. Registers are the fastest place to put a value, so the common case, six arguments or fewer, never touches memory.
  2. Other kinds. Floating-point arguments use XMM0 to XMM7; structures larger than 16 bytes are copied onto the stack.
  3. Who saves what. The caller saves any volatile registers it still needs; the callee must preserve RBX, RBP and R12 to R15.
03 · The stack

Memory that grows down

When a program starts, the operating system gives it a chunk of memory laid out in a specific pattern: its virtual address space. Among other regions, the OS reserves an area called the stack: a last-in-first-out region that grows as functions are called and shrinks as they return. The operating system places the stack at a high address, and on x86-64 it grows downward, toward lower addresses, as items are pushed.

Fig 3.5 · A process's virtual address space
Fig 3.5 · A process's virtual address space A column of addresses, highest at the top. The kernel's half is off limits. Below it the stack, which grows downward: frames for main, f and g are pushed as the calls happen (main calls f, f calls g) and popped as they return. Far below, the heap grows upward as memory is allocated. Below the heap, the data region of global variables, and at the bottom the program's machine code, read-only. high addresses kernel off limits to the program stack grows main's frame f's framemain calls f g's framef calls g unused heap grows malloc block malloc block data global variables text · machine code low addresses

Every process sees the same layout: machine code (text) and global variables (data) at the bottom; the heap, memory taken with malloc while the program runs and kept until freed, growing up from them; the stack growing down from just under the kernel, one frame of local values per call, gone when the call returns.

How it works
  1. Virtual. These are virtual addresses: each process gets the whole picture to itself (the MMU from Chapter 1, opened up in the Bridge, maps it to real RAM).
  2. Kernel. On x86-64 Linux the top half of the address space belongs to the kernel and is off limits in Ring 3.
  3. Text. The machine code is read-only and executable; data and the heap are writable but not executable.
  4. Toward each other. Stack and heap grow into the unused gap between them.

The CPU manages the stack with two instructions: push decrements RSP by 8 (one 8-byte value on a 64-bit machine), then writes the value to the address RSP now points to. pop reads the value at RSP and increments RSP back. Because push, pop, call and ret all move RSP, the stack is built into the silicon rather than offered by a library.

Each function call creates a stack frame: a contiguous region of the stack holding that function's local variables (values only it uses), its return address, and copies of the caller's register values it must restore, since caller and callee share the same sixteen registers. A caller waits for the function it called, so the newest frame always leaves first. When a function returns, moving RSP back up discards its frame. Data that must outlive the call goes on the heap instead (Fig 3.5).

04 · Function calls

What "calling a function" actually means

Take the C line int result = add(5, 3);: call add with 5 and 3 and keep the whole number (int) it returns. The compiler must follow the calling convention, the contract between caller and callee about who puts arguments where, who saves which registers, and how return values are delivered. On Linux and macOS x86-64, that is the System V AMD64 ABI (application binary interface) drawn in Fig 3.4; on Windows, the Microsoft x64 calling convention. They use different argument registers, so calling from one to the other needs a wrapper that moves each argument over.

Under System V, add(5, 3) therefore receives its 32-bit int arguments in EDI and ESI, the lower halves of RDI and RSI, and returns its result in EAX. Windows would pass them in ECX and EDX.

C source 
int add(int a, int b) {
    return a + b;
}

int main() {
    int result = add(5, 3);
    return result;
}
x86-64 assembly (System V) 
; ---- function: add(int a, int b) ----
add:
    push   rbp             ; save caller's frame pointer onto stack
    mov    rbp, rsp        ; new frame pointer = current stack top
    mov    eax, edi        ; eax ← first arg (a, was in edi)
    add    eax, esi        ; eax += second arg (b, was in esi)
    pop    rbp             ; restore caller's frame pointer
    ret                    ; pop return address from stack, jump there

; ---- function: main() ----
main:
    push   rbp
    mov    rbp, rsp
    mov    esi, 3          ; second arg goes in esi
    mov    edi, 5          ; first arg goes in edi
    call   add                ; push return addr, jump to "add"
    ; --- after add returns, result is in eax ---
    pop    rbp
    ret

Two instructions carry the call: call and ret. call add does two things in one step: it pushes the address of the next instruction (the address of pop rbp in main) onto the stack, then sets RIP to the address of add. When add reaches ret, the inverse happens: ret pops the saved return address off the stack into RIP, and execution resumes in main at exactly the next instruction. Three nested calls leave three return addresses on the stack, taken off newest first.

Fig 3.6 · The stack during a function call
Fig 3.6 · The stack during a function call main's frame (the saved rbp of main's caller, then main's variables) sits on the stack. call add, in main, pushes the return address (the next line of main) and jumps into add. add pushes main's frame pointer and begins its own frame. On the way out, pop rbp removes it, and ret pops the return address into RIP, the register that holds the next instruction to run, so execution continues in main at the next instruction. RSP, the stack pointer, follows the top of the stack. THE STACK · GROWS DOWN caller's rbp, saved main's variables return: main, next main's rbp, saved main add RSP RIP next to run main: call add add: push rbp add: … add: ret main, next line main, next

The stack and RIP through one call of add, from call to ret.

How it works
  1. RSP. The stack pointer always marks the top of the stack; on x86-64 that is the lowest address in use.
  2. call. Pushes the address of the next instruction in main (its pop rbp), then jumps to add.
  3. The chain. Each saved rbp points at the frame before it, so the frames form a list back through every call: what a debugger walks to print a stack trace.
  4. ret. Pops whatever is at the top of the stack into RIP.

Why this matters. The return address is just a number stored in memory, and a plain ret does not check it. If anything at all overwrites it between the call and the ret, the CPU will obediently jump wherever the new value points (Section 06 shows the hardware that later learned to check).

05 · Buffer overflow

The bug that defined three decades of security

In November 1988, a 23-year-old Cornell graduate student named Robert Tappan Morris released a small program onto the early internet. It was meant to count machines. Within hours it had brought down roughly ten percent of the computers then connected to the network (about six thousand machines). One vulnerability it exploited was a buffer overflow in fingerd, a UNIX background program that answered queries about a machine's users. Morris became the first person convicted under the Computer Fraud and Abuse Act. The attack class he made famous is still, decades later, among the most exploited bugs in computing. To see why, trace what happens when a tiny C function's input doesn't fit.

C (vulnerable function) 
// A function that greets the user. Looks innocuous.
void greet(char *name) {
    char buffer[16];        // 16 bytes on the stack
    strcpy(buffer, name);   // copies until it hits a null byte
    printf("Hello, %s\n", buffer);
}

strcpy is the culprit. It copies bytes from name into buffer one at a time, stopping only at a null byte (a zero), and never checks whether buffer has room. If name is 17 characters long, the 17th byte lands one byte past the end of buffer. The stack grows downward, so the values pushed before buffer sit at higher addresses, but the copy fills buffer from its lowest address up and runs on into them: the saved RBP, and just past it, the return address. Fig 3.7 lists memory with the lowest address at the top, the reverse of Fig 3.6, so there the copy runs down the page.

Fig 3.7 · Stack frame of greet(): normal vs overflow
Fig 3.7 · Stack frame of greet(): normal vs overflow NORMAL: name = "Tiger" "Tiger\0" + 11 unused bytes buffer[16] saved rbp return address → caller function returns normally ATTACK: name = 16 'A's + 8 bytes + addr "AAAAAAAAAAAAAAAA" buffer[16]: full "BBBBBBBB" overwrote rbp 0x4011e7 → attacker's code on ret, CPU jumps wherever attacker said ANATOMY OF THE OVERWRITE strcpy writes: A A A A A A A A A A A A A A A A B B B B B B B B 0x4011e7 ↑ 16-byte buffer ↑ saved rbp ↑ return address No bounds check. strcpy keeps writing. The return address is just bytes, and bytes can be replaced.

On the left, normal use: the buffer holds the input, the saved RBP and return address are intact, and the function returns to its caller. On the right, an oversized input keeps writing past the buffer, eventually overwriting the saved RBP and the return address. When ret executes, RIP gets loaded with whatever the attacker placed there.

From overwrite to code execution

Overwriting the return address is half the attack; the other half is choosing what to write there. The classic technique, perfected in the 1990s, is called shellcode injection: place machine code for a small payload (traditionally one that spawns a shell, a program that runs whatever commands are typed into it, hence "shellcode") into the buffer being overflowed, and overwrite the return address with the address of that shellcode. (In Fig 3.7 the A's stand where that code would go.) When the function returns, the CPU jumps into the buffer and runs the attacker's instructions. It worked because the stack could then hold running code; the NX bit (Defence two, below) took that away.

A 1996 essay in the underground hacking magazine Phrack popularised the technique, turning it from rare expert knowledge into a cookbook.

"The objective of this paper is to show how to write buffer overflow exploits, using as an example a vulnerability in a real program. … The reader is expected to be familiar with C and assembly under x86 systems."

Aleph One, "Smashing the Stack for Fun and Profit," Phrack 49, 1996

Why C lets this happen

C, which gets its own chapter later, was designed in 1972 as a portable assembler. It exposes raw memory and raw pointers, and by default it does not check that array accesses stay within bounds (an array, a row of same-sized values in memory like the 16-byte buffer above). strcpy, gets, scanf("%s"), and many other standard-library functions assume the programmer has guaranteed the buffer is large enough. When they're wrong, the corruption is silent: bytes get overwritten, the program keeps running, and the consequence may not appear until a function returns into junk.

This is the price of memory unsafety. C and C++ are memory-unsafe by design, trading safety for performance and control. Modern languages like Rust, Java, Python, and Go are memory-safe: their compilers, or their runtime (the support code that runs the program, such as the Java virtual machine or the Python interpreter), check every array access against the array's real length, and they check before the write lands. An out-of-bounds access becomes a controlled failure (an exception, a Rust panic): the program stops loudly at the bad access instead of sailing on with a trampled return address, and a crash is not code execution. For Rust this guarantee was the whole reason the language exists; for Java, Python, and Go it came bundled with runtimes adopted for other reasons. Either way, outside the escape hatches each language keeps (such as unsafe Rust), the classical buffer overflow cannot occur.

Famous buffer overflow incidents. The Code Red worm (2001, IIS, infected 359,000 hosts in 14 hours). The SQL Slammer worm (2003, infected 75,000 servers in 10 minutes). Heartbleed (2014, OpenSSL), technically a buffer over-read rather than an overflow. The server trusted an attacker-supplied length field and copied back that many bytes from its own memory, so each reply spilled whatever happened to sit next to the buffer, which could include the server's private key. Microsoft, Google, and others have published data showing that around 70% of severe security bugs (CVEs, Common Vulnerabilities and Exposures) in their large C/C++ codebases trace back to memory unsafety. This is why Rust adoption is growing inside operating system kernels, Linux itself included as of 2022.

06 · Defences

The arms race the OS fought back

Beginning in the late 1990s, operating systems, compilers and CPUs added defences in layers. Each one closed a class of attack, was in turn worked around by attackers, and was followed by a more sophisticated defence.

Defence one: stack canaries

In 1998, Crispin Cowan introduced StackGuard, a compiler modification that placed a random value between local variables and the saved return address. The value was called a "canary," after the birds carried into coal mines to detect poison gas. Before each function returns, compiler-inserted code checks that the canary still holds its original value. If it has changed, because a buffer overflow trampled it on the way to the return address, the program aborts immediately.

This works only while the attacker cannot guess the canary, and the program picks a fresh random one each time it starts. An attacker who can read process memory through a separate information leak, however, can sometimes recover it.

Fig 3.8 · The stack canary · a tripwire between buffer and return address
Fig 3.8 · The stack canary · a tripwire between buffer and return address SAME OVERFLOW · CANARY DETECTS IT BEFORE RIP IS HIJACKED NORMAL · CANARY INTACT saved RIP (return addr) 0x0040 1234 (caller) saved RBP previous frame ptr CANARY · 0x47A1F392B5... random, set at process start char buf[64] "hello\0" fits in buffer no overflow → canary unchanged prologue stored canary == stack canary? → yes · ret to caller normally ✓ STACK GROWS DOWN OVERFLOW · CANARY CLOBBERED saved RIP (return addr) 0x4141 4141 ← attacker-controlled saved RBP 0x4141 4141 4141 4141 CANARY · 0x41414141... overwritten: does not match char buf[64] "AAAA…AAAA": 200 bytes, oversize overflow walks upward through the canary prologue stored canary == stack canary? → no · __stack_chk_fail() → abort ✗ OVERFLOW WRITES UPWARD The canary is between the buffer and the saved RIP: the overflow must trample it on the way

A stack canary is a randomly-chosen value placed by the compiler between local variables and the saved return address. The function's prologue writes the value; the function's epilogue, just before ret, checks that it has not changed. A buffer overflow that wants to overwrite the saved RIP must walk upward through memory, which means it must overwrite the canary first. When the epilogue's check fails, the program calls __stack_chk_fail and aborts before ret can transfer control. The defence assumes that the attacker cannot leak the canary value through some other channel, and it is one of several reasons modern programs make information disclosure a serious vulnerability class on its own.

Defence two: non-executable memory (DEP / NX bit)

Shellcode injection depends on the CPU executing bytes that sit in a buffer on the stack. The defence is to mark stack pages as non-executable. The CPU's MMU refuses to execute instructions from a page marked NX, raising a hardware exception instead. Software patches for Linux made the stack non-executable from 1997; AMD put it into x86 hardware in 2003 as the "NX bit" (No-eXecute), and Intel followed; Windows calls it DEP (Data Execution Prevention), Linux keeps the name NX bit. Stack-injected shellcode immediately stopped working on systems with DEP enabled.

Defence three: ASLR

Even without injecting shellcode, attackers could redirect execution by overwriting the return address with the address of an existing function, such as system() from the C library (libc, the ready-made code every C program loads), called with "/bin/sh", which starts a shell. This is called a return-to-libc attack. The countermeasure is ASLR, Address Space Layout Randomization. At each program launch, the operating system loads code, libraries, the heap, and the stack at random addresses, so the attacker no longer knows where to point the return address. Like the canary, ASLR holds only while the addresses stay secret: a library loads as one block, so one leaked address locates all of it. ASLR debuted in PaX (a Linux patch) in 2001, two years before the NX bit reached x86 hardware, and became default on most operating systems by the late 2000s.

Fig 3.9 · ASLR · the same binary, three random load layouts
Fig 3.9 · ASLR · the same binary, three random load layouts SAME PROGRAM · THREE LAUNCHES · THREE DIFFERENT MAPS RUN 1 · 09:14:22 stack 0x7FFE 9A23 ____ …unmapped… libc.so.6 0x7F4C 3D11 ____ heap 0x55A8 0040 ____ .text · 0x562B 4400 ____ RUN 2 · 09:15:48 stack 0x7FFD C812 ____ …unmapped… libc.so.6 0x7F2D 6E55 ____ heap 0x55C4 0020 ____ .text · 0x55F1 8800 ____ RUN 3 · 09:18:11 stack 0x7FFE F005 ____ …unmapped… libc.so.6 0x7F89 2B40 ____ heap 0x55B9 8000 ____ .text · 0x5577 C200 ____ low high Each region's base is shifted by ~16 bits of randomness on every launch

Three launches of the same executable, on the same machine, within seconds of each other. The .text segment, the heap, the libraries, and the stack each load at a different random address every time. An attacker who has overwritten a return address must guess where to redirect it. On 64-bit Linux the entropy is high enough (typically 28–30 bits for libraries, 24–28 bits for the heap, 30–32 bits for the stack) that brute-force guessing crashes the program long before a successful guess. ASLR is not perfect. Small entropy pockets, leaks of address fragments and partial overwrites can sometimes be exploited. Still, it raises the cost of every memory-corruption attack. It is, in a real sense, the reason modern software is roughly survivable.

Return-Oriented Programming, and defence four

Return-to-libc can reuse only whole functions, one at a time, and on x86-64 it cannot even hand system() its argument, which must sit in RDI (Fig 3.4), not on the stack. In 2007 Hovav Shacham showed that tiny fragments of existing code are enough, and introduced Return-Oriented Programming (ROP). Instead of injecting new code, the attacker chains fragments that end in a ret instruction. Each fragment, called a "gadget," does some tiny operation (load a register, increment a counter, write a byte). By stacking up the right sequence of return addresses on the stack, the attacker can build arbitrary computation out of the program's own code without executing anything new, which defeats DEP. Given large enough libraries, useful gadgets always exist somewhere.

The leaks above undid the canary and ASLR, and ROP undid DEP, which forced another layer. A ret is an indirect jump: its destination is read from memory as the program runs. In Control Flow Integrity (CFI), the compiler records where indirect jumps may legally land and the runtime refuses any transfer to an address off that list. Two further defences guard the return address itself. A shadow stack keeps a second copy of each return address out of reach of ordinary writes, and ret halts the program if the copies differ; recent Intel CPUs build it in as CET (Control-flow Enforcement Technology). ARM Pointer Authentication (PAC), in Apple Silicon, tags each return address with a code computed from it and a key the program cannot read, checked before ret.

Fig 3.10 · Return-Oriented Programming · arbitrary computation from existing code
Fig 3.10 · Return-Oriented Programming · arbitrary computation from existing code NO NEW CODE INJECTED · ONLY TINY FRAGMENTS OF LIBC, WIRED TOGETHER SMASHED STACK attacker-controlled return addresses ret → addr of G1 [smashed RIP] value: 0x68 [arg for G1's pop] addr of G2 [next gadget] value: "/bin/sh" [arg for system] addr of G3 [next gadget] addr of system() [final target] …rest of payload… RIP READS DOWN GADGETS · IN libc.so.6 existing code, ending in ret G1: 0x7F4C…2A0 pop rdi ; ret // load arg G2: 0x7F4C…59C pop rsi ; ret // load 2nd arg G3: 0x7F4C…814 xor rdx, rdx ; ret // zero env system() · existing libc function execve("/bin/sh", …) → shell Every gadget ends with ret · ret pops the next address from the stack · the stack is the program

Return-Oriented Programming, demonstrated by Hovav Shacham in 2007. The attacker still smashes the stack, but instead of injecting new code (DEP would forbid it), the new "program" is a sequence of return addresses, each pointing to a tiny gadget: a one-or-two-instruction snippet ending in ret, somewhere in the existing libraries. The first ret after the overflow pops the first gadget address into RIP. That gadget executes its tiny op, then its own ret pops the next gadget address from the stack, and so on. With a sufficiently large library, gadgets for any required operation can be found. Every program links libc, which has hundreds of thousands of bytes of code. ROP turned an entire field of defence (mark code non-executable) into a starting point. Modern hardware mitigations (CFI, shadow stacks, ARM PAC, Intel CET) are the response.

Fig 3.11 · The arms race, in one diagram
Fig 3.11 · The arms race, in one diagram 1988 today ATTACKMorris Worm1988 · stack overflow DEFENCEStackGuard1998 · canaries DEFENCEDEP / NX bit2003 · non-exec stack DEFENCEASLR2001+ · randomisation ATTACKReturn-Oriented Prog.2007 · gadget chains DEFENCECFI · PAC · CET2017+ · hardware-signed

Each red dot is an attack technique that broke the previous defence. Each green dot is a hardware or compiler change that responded. The arms race continues, and at each step the cost of exploitation rises while the cost of a single mistake by a programmer in C or C++ falls more slowly.

The deeper lesson

Buffer overflows follow from a particular language model, one in which memory is raw, addresses are plain numbers any stray write can change, and the programmer is responsible for every check. The defences above only make a missed check harder to exploit; the cure is to use a memory-safe language wherever possible. That so much critical infrastructure (operating system kernels, web browsers, database engines, network stacks) is still written in C and C++ reflects those languages' performance, and it remains a permanent source of risk.

What you now understand

You have followed the chain from gates to assembly to exploits. The CPU executes a fixed menu of binary instructions defined by its ISA, whether x86, ARM or RISC-V, and everything else is a translation onto that menu. Registers are the CPU's tiny, fast notebook; the stack is a region of memory that grows downward and stores the bookkeeping of every function call. Calling conventions are the contract between caller and callee. Function calls work by pushing a return address onto the stack and jumping; they return by popping it back. And because the return address is just a number that lives in writable memory, an unchecked write (a buffer overflow) can replace it with anything, handing control of the machine to whoever supplied the input. The defences against this have evolved in lockstep with the attacks for thirty years: canaries, DEP, ASLR, CFI, pointer authentication.

Chapter 1 named what stops a program from reading another program's memory, writing to a disk it does not own, or holding the CPU until the user gives up: the rings, virtual memory and the timer. The Bridge that closes Part I asks why those walls hold: which hardware features the silicon must already provide, and how together they let one program, the kernel, control the machine and keep every other program in check. We do not yet open the kernel and look inside it; that waits for Part II.

Bridge: The Boundary

What the Silicon
Must Provide

Five small pieces of hardware let one program, the kernel, own a computer and share it safely among all the others: a privilege bit, a trap, a memory-management unit, a timer, and a way to reach devices. Take any one away and a service every program relies on goes with it.

TopicsPrivilege · Traps · MMU · Timer · MMIO/DMA
Era covered1965 → present
Bridge hero · What the Silicon Must Provide RING 0 · KERNELring 0 is trusted; ring 3 is not all instructions · all memory · all devices trap THE BOUNDARY PROCESS A browser PROCESS B editor PROCESS C music RING 3 · USER MODE limited instructions · own memory only · no devices FIVE PIECES OF SILICON privilege bit · which ring runs traps · the only way up memory unit · own memory only timer · takes the CPU back device access · ring 0 only
01 · User vs Kernel

One bit, two worlds

Of all the millions of bits inside a modern CPU, one decides what the running code may do: set one way, the CPU runs every instruction; set the other way, it refuses the few that control the whole machine. No user program can flip it: it changes only when a trap carries the CPU into the kernel, or when the kernel hands the CPU back. This bit is the seam at which all of operating-system security begins.

On x86 this setting is stored in two bits, the bottom two of a register called CS; together they hold the Current Privilege Level, or CPL, from 0 (most privileged) to 3 (least). Operating systems use only two of those four levels: Ring 0 (kernel mode) for the kernel and Ring 3 (user mode) for everything else. So in effect it is one bit: kernel or not.

The hardware enforces, not the operating system

When a program in Ring 3 tries a privileged instruction, the CPU itself checks the CPL, with no kernel code involved, so there is nothing to fool. The instruction does not execute. Instead the CPU raises a general-protection fault (#GP in the figure below): it takes control from the program and jumps, in Ring 0, to a handler the kernel set up at boot, which may end the program.

On x86-64 a short list of instructions is reserved for Ring 0: those that control the machine as a whole. MOV CR3 chooses which page tables the MMU uses, so a program allowed to run it could map in any memory on the machine. IN and OUT talk to devices directly, past the kernel's permission checks, and HLT halts the processor. User mode is defined by exclusion: it can do everything except these.

Fig BR.1 · The privilege bit · two worlds, one chip
Fig BR.1 · The privilege bit · two worlds, one chip The low two bits of the CS register hold the current privilege level: 00 in Ring 0, the kernel, and 11 in Ring 3, user programs. Both run the same three instructions. add runs in both. mov cr3, which changes the page tables, and hlt, which halts the processor, run in Ring 0; in Ring 3 the CPU stops each before it takes effect with a general-protection fault, #GP, and jumps to a handler the kernel registered in advance. RING 0 · KERNEL CS bits 1–0 0 0 add rax, rbx ✓ mov cr3, rax ✓ hlt ✓ RING 3 · USER CS bits 1–0 1 1 add rax, rbx ✓ mov cr3, rax #GP hlt #GP kernel handler, registered at boot

The same three instructions in each ring: add runs in both, while in Ring 3 the two privileged ones stop at #GP and the CPU jumps to the handler the kernel registered.

How it works
  1. CPL. The current privilege level, held in the low two bits of CS: 00 for the kernel, 11 for user programs.
  2. Privileged. Instructions that would let a program step past the operating system: loading the page tables (mov cr3), the interrupt table (lidt), model-specific registers, I/O ports, halting the CPU.
  3. #GP. A general-protection fault. The instruction does not run and the program gets no result; the CPU jumps to the handler the kernel set up, and the kernel decides what happens to the program.

The CPU powers on in its most privileged mode, since there is no operating system yet to grant privileges, so the kernel starts in Ring 0 and must step down by itself. First it prepares what user programs will depend on: page tables that map their memory, the table telling the CPU where to jump on each trap, and the timer of Section 04. All of it must be ready in advance, because once the CPU is in Ring 3 the kernel runs again only when a trap, the subject of the next section, brings it back. Then one instruction (IRET or SYSRET on x86-64, ERET on ARM) switches the CPU to Ring 3 and jumps to the start of the first user program.

The CPL also guards memory. Each page-table entry carries a flag, U or S (user or supervisor), and on every access the MMU compares it with the CPL: a page marked S is open only to the kernel, in Ring 0. A user program that reaches for the kernel's data, even by accident, gets a page fault instead. Section 03 shows the MMU at work.

Why this is the seam. Every protection the operating system enforces (keeping processes apart, file permissions, sandboxes) rests on this bit, because what they are built from (the page tables, the trap table, the timer) can be changed only from Ring 0. No program can switch the CPU into Ring 0 itself: only a trap does, and always at an entry point the kernel chose and keeps in registers and S pages that Ring 3 cannot change. And SYSRET, the way back to Ring 3, faults outside Ring 0: only the kernel moves the bit, in either direction.

02 · The Trap

The only way into the kernel

A user program often needs things only the kernel can do: reading a file, opening a network connection, printing to the screen. The ISA has no READ_FILE opcode, and a program in Ring 3 cannot reach the devices itself, so it asks the kernel to do the work: it makes a system call, Chapter 1's request across the boundary, by executing one special instruction. The request crosses by a trap, the only way from Ring 3 into Ring 0.

A function call jumps to an address the caller chose; a trap jumps to an address the kernel registered in advance, which user code cannot change. The program chooses the request, never the destination: it puts the number of the service it wants in a register (on x86-64 Linux, 1 in RAX asks for write, as in Fig BR.2) and executes its chip's system-call instruction (SYSCALL on x86-64, SVC on ARM, ECALL on RISC-V). The CPU then makes the crossing in one step: it saves the address of the program's next instruction, switches CPL to 0 and jumps to the kernel's entry point. The kernel does the work, and SYSRET returns to Ring 3 at the saved address with the result in RAX. To the program, the system call looks like any other instruction that took unusually long.

The path of one syscall

Fig BR.2 · The trap mechanism · one round trip across the boundary
Fig BR.2 · The trap mechanism · one round trip across the boundary A write system call, step by step, time flowing down. In user mode the program puts 1, the number of write, in RAX and executes SYSCALL. The CPU saves RIP, the return address, in RCX and RFLAGS, its status bits, in R11 (a spare register), switches to Ring 0 and jumps to the entry point the kernel stored in MSR_LSTAR. The kernel looks up entry 1 in its syscall table, runs write, puts the result, 6 bytes written, in RAX, and executes SYSRET, which restores user mode at the next instruction. USER · RING 3 KERNEL · RING 0 mov rax, 1 syscall entry · MSR_LSTAR table[1] → write write; rax = 6 sysret next instruction REGISTERS R11: a spare register RAX 1 · write 6 · bytes written RCX saved RIP (return address) R11 saved RFLAGS (status bits)

One write system call, time running down: the program in Ring 3 on the left, the kernel in Ring 0 on the right, and below them the registers that carry the request and the way back. The round trip typically takes under a microsecond.

How it works
  1. The number. RAX names the call (1 is write on x86-64 Linux); the arguments sit in RDI, RSI, RDX, R10, R8 and R9: Fig 3.4's order, with R10 in place of RCX, which SYSCALL overwrites.
  2. SYSCALL. In one instruction the CPU saves RIP in RCX and RFLAGS in R11, sets CPL to 0, masks interrupts, and loads RIP from MSR_LSTAR, a register only the kernel can set.
  3. Dispatch. The entry stub indexes the syscall table with RAX and runs that handler; the result comes back in RAX.
  4. SYSRET. Restores RIP and RFLAGS from RCX and R11 and drops back to Ring 3. No scheduling is involved.

System calls, exceptions, interrupts: three kinds of trap

System calls are not the only traps. An exception is a trap raised by the running instruction when it cannot complete: division by zero, a page fault, Section 01's #GP. An interrupt is a trap raised by a device (a disk finishing a read, the timer firing), and it can arrive between any two instructions. On x86 each kind of exception and interrupt has a number, its vector, and the kernel keeps one table, the interrupt descriptor table (IDT), with a handler address for each vector (Fig BR.3). A system call made with SYSCALL skips that table and jumps to its own entry point (Fig BR.2); older Linux programs made theirs through the table, as vector 128.

Fig BR.3 · The interrupt descriptor table · 256 doors into the kernel
Fig BR.3 · The interrupt descriptor table · 256 doors into the kernel IDT · 256 ENTRIES, EACH A KERNEL-REGISTERED HANDLER ADDRESS CPU · IDTR base + limit INTERRUPT DESCRIPTOR TABLE VECTOR CAUSE HANDLER 0 divide-by-zero do_divide_error 6 invalid opcode do_invalid_op 13 general protection do_general_protection 14 page fault do_page_fault … 32 timer (LAPIC) apic_timer_interrupt 33 keyboard (IRQ 1) do_IRQ → driver … 128 int 0x80 (legacy) entry_INT80 SOURCE EXCEPTIONS vectors 0–31 CPU itself INTERRUPTS vectors 32–255 timer · NIC · disk SYSCALLS SYSCALL or int 0x80 user request Each entry holds: handler offset · target segment · DPL · gate type, all set up by the kernel at boot.

When any trap fires, the CPU reads the IDT base address from its IDTR register, indexes by vector number, and jumps to the handler the kernel registered for that vector. The same table dispatches CPU exceptions (vectors 0–31), hardware interrupts from devices (vectors 32 and up), and on legacy x86 the int 0x80 system call. Exactly the same machinery underlies every involuntary entry into the kernel.

The instruction int n lets a program raise any vector n itself, as if that event had happened; this is how those older system calls reached vector 128. So each IDT entry also carries a DPL (Descriptor Privilege Level): 3 lets user code raise that vector this way, 0 only the kernel. Without it, a program could run int 14, and the kernel's page-fault handler would go to work on a fault that never happened, acting on the address of some earlier fault, because a real page fault records the address that failed and int 14 records nothing. The kernel gives DPL 3 only to the few vectors user code is meant to raise, such as 128, so int 14 from Ring 3 becomes a real general-protection fault.

Where the kernel's authority comes from. On a trap the CPU jumps only where the kernel told it to at boot: the kernel wrote the IDT into memory and pointed IDTR at it, and stored the system-call entry point in MSR_LSTAR. Only Ring 0 can load those registers, and the table sits in pages marked S (Section 01), so no user program can redirect a trap.

03 · The MMU

The hardware that draws the walls between processes

Memory isolation cannot be a software policy. A memory read is an ordinary instruction that the CPU runs on its own, without the kernel. If process A could aim one at address 0x4000 in process B's memory, no kernel code would run in time to stop it. The check has to happen inside every access, before it completes. It does, because every memory access the CPU makes flows through the MMU of Chapter 1, the small piece of silicon between the CPU and the RAM.

The MMU is the hardware half of the virtual memory of Chapter 1, the illusion that each process owns the entire address space. It translates whole pages, blocks of 4 KiB on x86-64: the last twelve bits of an address (212 = 4,096) give the offset inside the page and pass through unchanged, and only the page number above them is translated, using page tables the kernel keeps in RAM. Addresses on x86-64 are 48 bits, so a process could address 236 pages, and one flat table with an 8-byte entry for each would take 512 GiB. So x86-64 splits it into four levels of small tables, each a single page of 512 entries, and the kernel builds only the tables for parts of the address space in use. Nine bits of the page number pick an entry in the top table, which points to a table on the next level; three more steps reach the physical page. Following that chain is the page-table walk.

The page-table walker as a hardware unit

Fig BR.4 · The MMU · silicon between the CPU and the RAM
Fig BR.4 · The MMU · silicon between the CPU and the RAM Two memory accesses through the MMU. A load from virtual address 0x7fff_fa3c_4010 misses the TLB, so the walker reads the four page-table levels, level 4 down to level 1, starting from CR3; the permission bits allow the load, and the physical address 0x4a20_0010 goes to RAM, keeping the same offset within the page. Then a store to the next page up, 0x7fff_fa3c_5010: it misses the TLB too, the walk succeeds, but that page is read-only, so the store never reaches RAM: the MMU raises a page fault and the kernel decides what happens next. CPU load 0x7fff_fa3c_4010 store 0x7fff_fa3c_5010 MMU · a circuit, no code TLB: recent translations miss miss page-table walk from CR3: level 4 level 3 level 2 level 1 check: present, user, writable? load allowed store to a read-only page: no RAM 0x4a20_0010 not reached page fault kernel decides offset 0x010 unchanged: only the page moves

Every load, store and instruction fetch goes through the MMU, which first looks in its TLB, a cache of recent translations, and on a miss walks the page tables the kernel wrote; then it checks the permission bits. If the check fails, nothing reaches RAM: the MMU raises a page fault and the kernel takes over.

How it works
  1. The walk. On x86-64, CR3 holds the top table; nine bits of the address pick an entry at each of four levels, and the last twelve are the offset inside the 4 KiB page.
  2. The bits. Each entry carries present, user/supervisor, writable and no-execute flags; a failed check raises a page fault (vector 14).
  3. The shortcut. The TLB keeps recent answers, so a second access to the same page skips the walk (Fig BR.5).

The kernel never runs the walk itself. It writes the page tables, points the register CR3 at the top one, and leaves the walk to a circuit inside the MMU, the page-table walker; translation happens billions of times per second, and the machine could not run if the kernel took part in each. To switch between processes, the kernel changes that one register; from that nanosecond on, the same virtual addresses lead through different tables to different physical pages. That is what process isolation is. Every process's tables also map the kernel, or at least its entry code, in pages marked S (Section 01), so a trap lands in kernel code whichever process was running, and the program still cannot touch it.

The TLB: a cache for translations

A four-level walk costs four memory accesses on top of the one the program asked for, a 5× tax on every load and store that no machine could afford. So the MMU includes a cache called the translation lookaside buffer, the TLB, which remembers recent virtual-to-physical translations. It is small, but locality of reference means a hit rate above 99% is normal, and the walker runs only on misses. A switch of CR3 drops the old process's translations so the next process cannot use them, unless each is tagged with its address space.

Fig BR.5 · The TLB · why the walk usually doesn't happen
Fig BR.5 · The TLB · why the walk usually doesn't happen Twelve memory accesses from a program working through a few pages, run through a four-entry TLB. Most name a page the TLB already holds and are translated at once. Two name a page it does not hold: each of those runs the page-table walk, four extra memory reads, and loads the translation into the TLB, replacing the entry used longest ago. The count ends at ten hits and two misses; real programs usually hit well over 99% of the time. virtual pages the program touches 4 4 5 4 5 6 4 6 7 7 4 5 page a3c? (last digit shown) TLB · four entries a3c4 → a200 a3c5 → b731 b210 → 51e0 a3c6 → 0907 b211 → 51e1 a3c7 → c152 page-table walk 4 extra memory reads hits 1misses 0 hits 2misses 0 hits 3misses 0 hits 4misses 0 hits 5misses 0 hits 5misses 1 hits 6misses 1 hits 7misses 1 hits 7misses 2 hits 8misses 2 hits 9misses 2 hits 10misses 2 real programs: well over 99% hits

Programs touch the same few pages again and again, so the TLB can answer most accesses at once. Only a miss pays for the four-read walk, and its translation then replaces the entry used longest ago.

How it works
  1. Sizes. From 64 entries to a few thousand per core, in one or two levels; one entry can also cover a 2 MiB or 1 GiB huge page.
  2. Tags. On x86 the address-space tag is the PCID, so a switch of CR3 need not empty the TLB.

When the kernel changes a page-table entry (because a page was swapped out to disk, say, or a permission was taken away), the TLB must be told, or it will keep serving the old translation. The privileged instruction INVLPG drops one entry, so the next access to that page misses and the walker reads the updated tables. Each core has its own TLB, so the kernel must also have every other core that might hold the old entry drop it.

04 · The Timer

The piece of silicon that makes multitasking possible

Imagine a CPU exactly like the modern ones (privilege bit, traps, MMU, all of it) but with no timer, no circuit that interrupts the CPU on a schedule. A cooperative kernel could still share the CPU: each program would yield, handing the CPU back through a system call, and the kernel would run the next. One program that never yields, stuck in an endless loop or written that way, then freezes the machine, because the kernel never runs again to take the CPU back.

Devices interrupt only when they have news and programs yield only when they choose, so neither guarantees the kernel a turn. One circuit does, the hardware timer: a counter in each core's interrupt controller (the circuit that delivers interrupts to the core). The kernel loads it with a count that runs out after, say, a millisecond, and at zero it raises an interrupt (a timer tick) and starts again. At each tick the kernel saves the interrupted program's registers, picks what runs next, restores that program's registers, points CR3 at its page tables and returns into it, exactly where it stopped. No program can stop the ticks, because reprogramming the timer and switching interrupts off are privileged. Without the timer, preemptive multitasking, in which the kernel takes the CPU back instead of waiting for a yield, is impossible.

Fig BR.6 · The timer interrupt loop · how the kernel takes the CPU back
Fig BR.6 · The timer interrupt loop · how the kernel takes the CPU back Four milliseconds of one CPU core with the timer set to a thousand ticks a second. Process A runs until the timer's countdown reaches zero; the timer interrupts, the kernel runs for a moment and its scheduler picks process B; at the next tick, process C; at the next, A again. Process C is stuck in an endless loop and never gives up the CPU, but the tick takes it back exactly as it does from the others. one core, timer at 1,000 ticks a second A B C while (1) A 0 ms 1 ms 2 ms 3 ms 4 ms kernel: tick, scheduler picks next timer countdown C never yielded; the tick took the CPU back

Four milliseconds of one core at 1,000 ticks a second: at each tick the kernel's scheduler picks the next process, and C, stuck in an endless loop, loses the CPU like the others.

How it works
  1. The rate. Linux's tick is a build option, commonly 100, 250, 300 or 1,000 per second; the kernel programs the timer in each core's interrupt controller (the local APIC on x86; on ARM, the generic timer) at boot.
  2. Not to scale. The kernel slices are drawn wide enough to see; a real tick takes microseconds, and the scheduler often lets one process run for several ticks.

Ticks cost power and pause useful work. So most Linux systems stop them on an idle core, where there is nothing to take back, and Linux can be configured to stop nearly all of them on a core with a single task, for real-time and high-performance computing. With one task there is nothing to share; as soon as a second task is ready, the tick returns, because only the tick lets the kernel share a core.

Why the timer is irreducible. Privilege rings, traps, and the MMU all give the kernel authority over what user code can do. The timer gives the kernel a chance to exercise that authority, even when user code never calls into the kernel. Preemptive multitasking, fair turns for every program, even the ability to kill a misbehaving program: all rest on this one circuit firing on a schedule the user cannot disable.

05 · Talking to the World

How the CPU reaches beyond itself

The CPU on its own can only compute. To take in a keystroke, light a pixel or fetch a file, it has to reach devices. The path to them is hardware too, and as with everything else in the Bridge, only the kernel gets to use it.

Two channels carry most of the conversation between CPU and device. The first is memory-mapped I/O (MMIO): a device's registers, small cells in its own circuit, sit at fixed addresses in the physical address space, so writing one gives the device a command and reading one reports its status. The second is direct memory access (DMA): the device reads and writes RAM by itself, without the CPU handling each byte and without passing through the CPU's MMU. x86 also has a third: the IN and OUT instructions of Section 01. Whichever channel carries the work, a device reports that it has finished by raising an interrupt request (IRQ), which reaches the CPU through the trap machinery of Section 02.

Memory-mapped I/O: devices live at memory addresses

Fig BR.7 · The physical address space · devices among the RAM
Fig BR.7 · The physical address space · devices among the RAM The lowest 4 GiB of a typical PC's physical address map, top to bottom: the read-only boot code (firmware) just below 4 GiB, the local APIC at 0xFEE0_0000, the interrupt router (IO-APIC) that passes device interrupts to the cores at 0xFEC0_0000, a network card's registers and the GPU's frame buffer in a PCIe window, and RAM from address zero. The CPU runs the same store instruction four times with four addresses: into RAM, where the value is simply stored; into the frame buffer, where a pixel changes; into the network card's registers, which sends a packet; and into the local APIC, which sets the timer's rate. The box each store reaches stays outlined until the next store. CPU: store x at 0x0040_1000 store x at 0xC000_0400 store x at 0xD000_0018 store x at 0xFEE0_0380 boot code (firmware) from 0xFF00_0000 local APIC from 0xFEE0_0000 interrupt router from 0xFEC0_0000 network card from 0xD000_0000 GPU frame buffer from 0xC000_0000 RAM from 0x0000_0000 low addresses at the bottom, not to scale stored, nothing else a pixel changes a packet is sent timer rate set

To the CPU, the physical address space is one flat range, and only part of it is RAM: other ranges belong to devices, such as the GPU's frame buffer (the screen's pixels) and the local APIC (each core's interrupt controller and timer). The same store saves a value, changes a pixel or sets the timer, depending only on the address.

How it works
  1. Who routes it. The CPU's address decoding sends each access to RAM, to a unit inside the CPU (the local APIC), or out to the device that claimed that range at boot; the addresses shown are typical, and every machine's map differs.
  2. Who may touch it. These are physical addresses, after the MMU's translation (Fig BR.4); only the kernel maps device ranges into an address space, so a user program cannot reach a device's registers directly.
  3. Not cached. Device registers are marked uncacheable, so every store really reaches the device; a frame buffer is write-combining, which batches stores but still sends them all.

DMA: when the device copies on its own

Take a modern solid-state drive (an NVMe SSD) reading a file. The kernel writes a small command into a queue in RAM, a list of commands waiting for the drive: read this part of the drive into the buffer at this address. Then it makes one MMIO write, to a register called the doorbell, which tells the drive a command is waiting. The drive fetches the command from RAM itself and copies the data straight into the buffer: that is direct memory access. The CPU could copy the data with MMIO loads instead, but far too slowly: at eight bytes a load, each taking about a microsecond, it would move about 8 MB a second, while the drive delivers several gigabytes a second. With DMA the CPU runs other work until the drive's completion interrupt.

Fig BR.8 · Direct memory access · the device writes RAM by itself
Fig BR.8 · Direct memory access · the device writes RAM by itself A disk read by direct memory access. Process A asks for data; the kernel puts a small command in a queue in RAM (read these blocks into the buffer at 0x4a20_0000) and rings the SSD's doorbell register. The SSD then streams the data straight into RAM, filling the buffer block by block, while the CPU runs process B. When the transfer is finished the SSD raises an interrupt, the kernel completes the request and wakes process A. The CPU never copies the data during the transfer. CPU process A asks kernel: doorbell runs process B IRQ: kernel done A woken NVMe SSD reading blocks done RAM: buffer at 0x4a20_0000 command queue 1 command queued, doorbell rung1 command queued, doorbell rung 2 the SSD fills RAM on its own2 the SSD fills RAM on its own 3 an interrupt says done3 an interrupt says done

One SSD read in the three steps drawn: the kernel queues a command and rings the doorbell, the drive fills the buffer while process B runs, and an interrupt wakes process A.

How it works
  1. Scattered buffers. The buffer need not be one block of RAM: the command can list many separate pages (PRP or SGL entries), and the drive fills each in turn.

DMA has a security cost. A device that can write any address in RAM is dangerous: a malicious or buggy network card could overwrite kernel code. Modern systems address this with another piece of silicon, the IOMMU: a second MMU that translates and checks the addresses devices use, as the regular MMU does for the CPU. The kernel can then allow a network card to write only into its own buffers; an attempt to reach kernel memory raises a fault.

06 · Synthesis

What the kernel must therefore be

Part I has been building toward one question since Chapter 1, and we can now answer it without reading a single line of kernel source. Given the five hardware features of the Bridge (the privilege bit, traps, the MMU, the timer, and MMIO with DMA), what is the smallest program that turns them into the services all other software relies on: protection, system calls, separate processes, multitasking, files and networking?

These services are abstractions: programs use them as if the machine offered them, but the kernel builds each one from the hardware. Each rests, almost one to one, on one of the five features, and no feature is of use until the kernel sets it up at boot.

Fig BR.9 · Hardware features → kernel → abstractions
Fig BR.9 · Hardware features → kernel → abstractions Five hardware features on the left, the abstractions programs rely on at the right, and the kernel joining each pair: the privilege bit gives a protected kernel apart from user programs, traps give system calls, the MMU and TLB give separate processes, the timer gives multitasking, and MMIO and DMA give files and networking. Each feature is then taken away in turn and its abstraction goes with it: without privilege any program can do anything, without traps there is no safe way into the kernel, without the MMU every program can read every other, without the timer a stuck loop keeps the CPU, and without MMIO and DMA there is no disk and no network. silicon kernel what you get privilege bit kernel vs user traps system calls MMU · TLB processes timer multitasking MMIO · DMA files, network no privilege: any program can do anything no traps: no safe way into the kernel no MMU: every program reads every other no timer: a stuck loop keeps the CPU no MMIO or DMA: no disk, no network take a feature away, its abstraction goes

Each hardware feature on the left becomes, through the kernel, the abstraction on the right. Take the feature away and the abstraction goes with it: without the MMU there are no separate processes, and without the timer nothing can take the CPU from a program that never yields.

How it works
  1. Why the kernel. Only code running with full privilege can program these features, so one program does it and every other program asks it through system calls.
  2. Not strictly one to one. A process needs the MMU, traps and the timer together; each row shows the feature its abstraction cannot do without.

The kernel as the smallest program that arranges the silicon

The answer is a short list. Set up the page tables, register the trap handlers, program the timer and the devices, and drop the CPU into Ring 3; from then on, run only when a trap brings the CPU back. That is the least the silicon demands of a kernel, not the size of a real one. Linux is more than thirty million lines of code, most of it drivers, filesystems, network stacks and other services built on top of that minimum.

Everything else is engineering, and it is the subject of Chapter 4, which opens Part II by reading the kernel as a real program: how it schedules processes, organises virtual memory in software on top of the hardware tables, finds a file's data on disk, lets processes talk to each other, and what goes wrong when it has bugs.

Each of those subjects rests on what the Bridge has shown: under every time-slice switch from one process to another, a timer tick that took the CPU back; under the read() system call, a SYSCALL instruction and an entry point the kernel registered at boot; under every memory access, the TLB or, on a miss, the four-level page-table walk.

The kernel is software. The reason the kernel can exist at all is hardware.

the lesson Part I has been building to
End of Part I

The substrate is built.

From sand to gates, from gates to instructions. Part II opens the program that owns this hardware, the kernel, and then turns to the languages people write in.

Continue to Part II: The Software Layer