Down to the Metal

Part III · Chapter 10

Virtual Memory and Paging

Every address you've seen so far pointed straight at a real place in memory. In this chapter we break that rule. With virtual memory, every program lives in its own private, imaginary address space, and the processor quietly translates every single address it uses. It's how a computer runs hundreds of programs at once without them trampling on each other.

Imagine your computer right now: a web browser, a music player, a few background services and the operating system itself, all sharing the same RAM. That raises some hard questions:

One idea answers all three: virtual memory.

Life without it

The IBM PC had no virtual memory. Every program saw the real, physical addresses of Chapter 8's memory map, and nothing stopped it from writing anywhere at all. A single wrong address in a program could overwrite DOS itself, and the whole machine would freeze. Saving your work often was simply good sense. Running two programs at once safely was out of the question.

The fix is to put a translator between the program and the memory. The program uses virtual addresses, which are just numbers in its own private world. A piece of hardware inside the processor, the memory management unit (MMU), translates each one into a physical address on its way to memory, on every single load, store and instruction fetch.

Pages and page tables

Translating each byte individually would need an impossibly big table. Instead, memory is divided into fixed-size blocks called pages, usually 4 KB each on both x86-64 and RISC-V. Physical memory is divided into blocks of the same size, called frames. The operating system can put any page into any frame, and it records where each page lives in a page table, one per program.

A virtual address then splits into two parts, just like a cache address in Chapter 9:

So translating an address just means swapping its page number for a frame number. In the demo below, addresses have 4 hex digits, so the first digit is the page number and the other three are the offset.

Try the preset addresses, first as Program A, then switch to Program B. Then try Write on address 0x0123 (the program's own code), and visit 0x3000 and 0x5000.

Every program gets its own world

Notice what happened when you switched programs. Address 0x1F00 means "my data" to both of them, but it leads to completely different frames. Neither program can even name the other's memory: there's simply no virtual address in A's page table that leads to B's frames. That's isolation, and it's why one crashing app no longer takes the whole computer down with it.

It also means every program can be built as if it had the whole address space to itself, starting at the same addresses. And when two programs want to share something, the operating system just points both page tables at the same frame. That's what happened at 0x2010: both programs use the same shared library code, stored only once in physical memory. Your computer probably has dozens of programs sharing the same copy of the standard C library right now.

Protection

Each page-table entry also carries permission bits, checked by the MMU on every access:

If an access breaks the rules, the MMU doesn't complete it. Instead it raises a page fault: the processor stops the program mid-instruction and jumps into the operating system to decide what to do. If the program really was misbehaving, the operating system ends it. On Linux and macOS you'll see the famous message "Segmentation fault".

Page faults that aren't errors

Not every page fault is a mistake. Sometimes the page is perfectly valid, but the operating system has decided to keep it on disk instead of in RAM. That was the case at 0x3000: present bit 0, but a legal page. The operating system loads it from disk into a free frame, updates the page table, and restarts the instruction as if nothing had happened.

This lets a computer pretend to have more memory than it really does. Programs often reserve far more memory than they actually touch, and many pages sit unused for long stretches. So the operating system loads pages only when they're first touched (demand paging), and when RAM fills up, it writes rarely-used pages out to disk (swapping) to make room. It's the cache idea from Chapter 9 again, one level down: RAM acts as a cache for the disk.

This program's memory has room for just 4 pages. Run each pattern and compare the number of page faults. Each one costs about 80 µs (loading from an SSD), 800 times longer than an access that finds its page already in RAM.

The last pattern shows the danger. A program that loops over just one page more than will fit faults on every access: each page is thrown out right before it's needed again. When a whole computer gets into this state, it spends nearly all its time moving pages to and from disk, and slows to a crawl. That's called thrashing, and it's the sound of a hard disk grinding away on an overloaded computer.

Page tables in a real CPU

Real address spaces are enormous. x86-64 programs use 48-bit virtual addresses, which means 236 pages of 4 KB. A simple flat page table with one 8-byte entry per page would need 512 GB, per program! But most of that space is empty, so the page table is built as a tree instead: tables of tables, where any part of the tree that would be empty is simply left out.

x86-64 uses a four-level tree. The 48-bit address splits into four 9-bit indices and a 12-bit offset. Each index picks one of 512 entries in a table, and each entry points to the next table down. A special register, CR3, holds the physical address of the top table.

Try the preset addresses. The colored groups of bits are the four indices and the offset; the steps below show the walk from CR3 down to the physical frame.

Each table has 512 entries of 8 bytes, so every table is exactly one 4 KB page: tidy. RISC-V offers the same design in sizes: Sv39 (three levels, 39-bit addresses), Sv48 (four levels) and Sv57 (five). Newer x86 chips can use five levels too, for 57-bit addresses.

The TLB: a cache for translations

There's an obvious problem. Every memory access now needs a translation, and a four-level walk means four extra memory reads before the real one. That would make everything several times slower. The solution, once again, is a cache.

The translation lookaside buffer (TLB) is a small, very fast cache of recent translations: "page so-and-so lives in frame such-and-such". A typical first-level TLB holds about 64 entries, backed by a second level of a couple of thousand. Thanks to locality, the TLB answers the great majority of lookups, and the full page walk is needed only occasionally. Even then, the page-table entries themselves are usually sitting in the data caches.

Programs that use huge amounts of memory can also ask for huge pages of 2 MB or even 1 GB on x86-64. One TLB entry then covers far more memory, so fewer page walks are needed.

Meanwhile, inside a real CPU

Normal programs never see any of this: they just use their virtual addresses. Only the operating system manages page tables. Switching from one program to another largely means pointing the MMU at a different page table, and telling the TLB to forget old translations when needed:

; x86-64 (operating system only)
mov     cr3, rax        ; switch to another program's page tables
invlpg  [rdi]           ; forget the TLB's translation for one page
# RISC-V (operating system only)
csrw    satp, a0        # switch to another program's page tables
sfence.vma              # make the TLB forget stale translations

On Linux you can look at any program's virtual memory map. Here's part of the map of the cat command, taken on the computer this book was written on:

$ cat /proc/self/maps
6315aa9c8000-6315aa9cd000 r-xp  /usr/bin/cat          ← cat's code: read + execute
6315aa9d0000-6315aa9d1000 rw-p  /usr/bin/cat          ← its data: read + write
6315ad65e000-6315ad67f000 rw-p  [heap]
7d8b14828000-7d8b149b1000 r-xp  /usr/lib/x86_64-linux-gnu/libc.so.6   ← shared C library
7ffda6952000-7ffda6974000 rw-p  [stack]

Every line is a range of virtual pages with its permissions: r read, w write, x execute. Notice that no range is both writable and executable. Notice also the addresses: huge numbers near the top of the 48-bit space, with vast unused gaps between them. Only the pages actually used have frames behind them.

Try it yourself

  1. With 4 KB pages, a program uses virtual address 0x3A7C, and its page table maps page 3 to frame 5. What's the physical address?
    Show answerPage number 3, offset A7C. Swap the page number for the frame number: 0x5A7C.
  2. How many 4 KB pages are there in 4 GB?
    Show answer4 GB = 232 bytes, and 4 KB = 212 bytes, so 232 / 212 = 220 = 1,048,576 pages.
  3. Use the page-walk demo on 0x7FFD4A2C1E40. Which entry is used at each of the four levels?
    Show answerEntry 255 of the level 4 table, 501 of level 3, 81 of level 2 and 193 of level 1, with offset 0xE40 inside the final page.
  4. In the translation demo, both programs use address 0x2010. Do they read the same byte?
    Show answerYes. Both page tables map page 2 to frame 3, the shared library. It's stored once in physical memory but appears in both programs' worlds, marked read-only so neither can change it for the other.
  5. In the page-fault demo, why does looping over pages 0–4 fault on every single access?
    Show answerOnly 4 pages fit. Each time a fifth page is needed, the least recently used page is thrown out, and that's always exactly the page the loop will need next. It's thrashing in miniature: one frame more (or one page fewer) and almost every access would be a hit.

What we learned

That completes Part III: memory, from a single address wire all the way to virtual address spaces. So far our computer has been a brain in a jar: it computes and remembers, but it can't see or touch the outside world. In Part IV we connect it to keyboards, screens and disks, starting with I/O ports and memory-mapped I/O: the ways a processor talks to devices.