Virtual memory and paging

Every address a program uses is a lie. When the previous chapters showed two processes reading different values at the same address, or main landing somewhere new on every run, the addresses involved were virtual addresses: numbers that mean something only inside one process. Between the CPU and the memory chips, a piece of hardware translates each of them, on every load, store and instruction fetch, into a physical address, the actual location in RAM. That translation, set up by the operating system and carried out by the hardware, is virtual memory.

It started in the 1950s: programmers split programs into overlays by hand and loaded them one after another into a tiny memory. In 1961 a group in Manchester proposed doing it automatically, and by the early 1970s most computers had it. The motivation has shifted since (machines now have plenty of RAM), but virtual memory stayed, because it gives every process a private, protected address space, lets the OS share and copy memory cheaply, and lets memory be allocated only when it's actually used.

Pages, frames and the MMU

The mapping isn't kept byte by byte. The virtual address space is cut into fixed-size pages, physical memory into page frames of the same size, and a page table says, for each virtual page, which frame holds it, or that none does. The hardware that consults it is the MMU (memory management unit), part of every core.

Because the page size is a power of two, an address splits cleanly in two: the high bits are the virtual page number, the low bits the offset within the page. Only the page number is translated; the offset passes through unchanged. With 4 KiB pages, the offset is the low 12 bits, the last three hex digits:

It prints 40401c page 404 offset 1c for the global, 406010 page 406 offset 10 for the heap block and 7fffffc4 page 7ffff offset fc4 for the local variable. The simulator doesn't translate addresses (its address space is the physical one), but real machines split them exactly this way. The same program on the Mac this chapter was written on, where pages are 16 KiB, keeps 14 bits of offset instead: its stack variable at 0x16b11e794 is at offset 0x2794 of page 0x5ac47.

Page tables with levels

A single flat table doesn't work for 64-bit address spaces. x86-64 and ARM64 use 48-bit virtual addresses; with 4 KiB pages that's 2³⁶ pages, and an 8-byte entry for each would take 512 GiB per process. Most of an address space is empty, so the table is made a tree: the page number is cut into several indexes, each selecting an entry in one level, which points to the table of the next level. Only the parts of the tree that cover used memory exist.

On x86-64, and on ARM64 with 4 KiB pages, each table is one 4 KiB page of 512 eight-byte entries, so each level consumes 9 bits of the address: 9 + 9 + 9 + 9 + 12 = 48. Take the stack address 0xffffec4f579c from a 64-bit ARM Linux process:

bits 47–39  → level 0 index 511
bits 38–30  → level 1 index 511
bits 29–21  → level 2 index 354
bits 20–12  → level 3 index 245   → frame number
bits 11–0   → offset 0x79c        (copied unchanged)

Four memory reads to translate one address: this is the page walk, done by the MMU in hardware on x86, ARM and RISC-V. Each process has its own tree, and switching processes means pointing the MMU at a different root: the CR3 register on x86, TTBR0_EL1 on ARM64.

48 bits give 256 TiB of virtual addresses, which Linux splits in half on x86-64: 128 TiB for the user, 128 TiB for the kernel. Intel added a fifth level, starting with its Ice Lake processors, for servers with huge memories: 5-level paging extends addresses to 57 bits, 128 PiB, and Linux supports it.

ARM64 lets the OS choose the page size, called the translation granule, and the tree's shape follows:

Apple chose 16 KiB pages for its ARM Macs and iPhones: sysctl hw.pagesize answers 16384 on this M2. The Linux virtual machine running on the same chip uses 4 KiB (getconf PAGESIZE says 4096), because that's how its kernel was built. The page size isn't a property of the CPU but a choice of the OS within what the CPU allows, and a slow-moving one, since software quietly assumes it: Android only began supporting 16 KiB pages with Android 15, and since November 2025 Google Play has required new apps and updates targeting it to work with them.

Older 32-bit designs used two levels: x86 in 32-bit mode split an address 10 + 10 + 12 bits with 4 KiB pages, and 32-bit ARM offered 4 KiB to 16 MiB pages. The principle is identical; 64-bit machines simply need two or three more levels. And page sizes, once anywhere from 512 bytes to 64 KB, are now 4, 16 or 64 KiB, with huge pages on top.

What a page table entry holds

An x86-64 page table entry (PTE) is 64 bits: the physical frame number, and flags the MMU checks on every access:

• P (present): the mapping is valid. If it's clear, any access raises a page fault, and the other 63 bits are free for the OS to record, for example, where on disk the page went.
• R/W: writes allowed.
• U/S: user mode may access the page. Kernel pages have it clear. That's the hardware behind the isolation of the system calls chapter.
• NX (no-execute, bit 63): the page's bytes can't be run as instructions. Together with R/W, it gives the W^X permissions seen in /proc/self/maps: code r-x, data rw-.
• A (accessed) and D (dirty): set by the hardware when the page is read and when it's written. The OS uses them to decide what to evict, and whether an evicted page must be written back: "clean" and "dirty" pages.

ARM64 entries carry the same information under other names (access permissions, UXN/PXN for execute-never, an access flag, a dirty-bit mechanism). Every protection the OS offers a process (read-only code, a non-executable stack, a guard page below the stack, a NULL page that crashes) is one of these bits.

The TLB: caching translations

Four extra memory reads per access would make every program several times slower. So each core keeps recent translations in a small, fast cache, the TLB (translation lookaside buffer): virtual page number in, frame number and permissions out, in the same cycle as the cache lookup. Only on a TLB miss does the MMU walk the tree, and even then the upper levels of the tree are usually in the ordinary data caches.

The TLB is what makes access patterns matter at the page level, not just at the cache-line level. This experiment follows a chain of pointers through 4,096 cache lines in random order: 512 KiB of data either way. In one layout the lines are packed together; in the other, each sits alone in its own page, so the chain touches 4,096 different pages:

Same data, same cache behavior, three to five times slower: the difference is TLB misses and page walks. With 1,024 lines, which fit in the L1 cache, the packed chain takes 0.9 ns per load and the page-per-line chain 3 to 8 ns. The 16 KiB pages of macOS cover four times more memory per TLB entry than 4 KiB pages, and 2 MiB huge pages 512 times more, enough to bring the scattered case almost back to the packed one. (The Linux numbers include a virtualization cost: inside a virtual machine, a TLB miss walks the guest's page tables and the hypervisor's, as the chapter on hardware virtualization explains.)

A context switch changes the page tables, which would make every TLB entry wrong. Old x86 processors flushed the whole TLB on each switch. Current ones tag entries with an address-space number (PCID on x86, ASID on ARM), so entries from several processes coexist and survive the switch.

Page faults and demand paging

When the MMU finds no valid mapping, it raises a page fault, the restartable exception of the traps chapter. The kernel looks up what should be at that address. If the access is illegal, the process gets SIGSEGV. If it's legal but the page isn't there yet, the kernel finds a frame, fills it, writes the PTE, and returns to the faulting instruction, which runs again and succeeds. The program never notices.

That makes demand paging possible: nothing is loaded until it's touched. malloc(1 GiB) or mmap only records a region; no frame is allocated. The first write to each page faults, the kernel hands over a zero-filled frame, and only then does the page count in the process's memory. Measured by reserving 1 GiB, writing one byte per page, then doing it again:

Every page of the first pass took a fault, and each fault cost 500–900 ns, mostly zeroing the new frame, plus the trap. The second pass took no fault at all. With huge pages, one fault maps 2 MiB at once, and the fault count drops by a factor of 512. Afterwards, Linux's /proc/self/status showed VmRSS: 1049836 kB (the gigabyte, now resident) and VmPTE: 2100 kB: the page tables themselves, 262,144 entries of 8 bytes plus the upper levels.

These are minor faults: no disk involved. A major fault needs to read the page from disk: from the executable file for code, from swap for data that was evicted. The same mechanism implements copy-on-write: after fork, parent and child share frames marked read-only, and the first write faults, copies the page, and retries. And it lets Linux overcommit: it hands out more virtual memory than it has RAM plus swap, betting that most of it will never be touched.

When memory runs out

When a frame is needed and none is free, the kernel must evict a page: drop it if it's clean and backed by a file, write it to swap first if it's dirty. Which page? The ideal is the one that won't be needed for the longest time, which nobody knows. LRU (least recently used) approximates it, but tracking the exact order of every access is too expensive. Real kernels approximate LRU with the hardware's accessed bit: the clock algorithm sweeps the frames, clearing accessed bits, and evicts a page whose bit is still clear on the next pass. Linux keeps active and inactive lists, and since version 6.1 (2022) offers a multi-generation LRU; macOS and Windows use their own variants of the same idea.

LRU fails badly when a loop cycles through one page more than fits: every access evicts exactly the page needed next. More generally, each program has a working set, Denning's term for the pages it's actively using. If the working sets of the running programs fit in RAM, faults are rare. If they don't, the system thrashes: it spends its time moving pages in and out. A container limited to 256 MiB of RAM, with swap allowed, touching every page of a buffer four times in a row:

Three to five thousand times slower, for a buffer only twice as big. Each pass evicts the pages the next pass needs first. That's the LRU pathology, for real. Each of the 25,600 major faults read four pages from swap at once; the pass time divided by the number of major faults comes to about 100 µs per fault on this virtual disk. A hard-disk access takes about 10 ms of seek and rotation; SSDs cut that by two orders of magnitude, but a page from swap still costs about ten thousand times more than a page already in RAM.

Modern systems try to avoid disk swap altogether by compressing memory. macOS has done it since 2013: pages that would be swapped are compressed in RAM first. On this Mac, vm_stat reported 2,462,121 pages stored in the compressor, 37.6 GiB of data, occupying 587,094 pages, 9.0 GiB: a ratio of about 4 to 1. Windows 10 added a similar compression store; Linux offers zswap and zram.

Choosing a page size

The trade-off still holds. Small pages waste less memory: on average half of a region's last page is unused, which is internal fragmentation. Large pages need fewer page table entries, fewer faults and fewer TLB entries, as measured above. The trend has gone toward large: 4 KiB pages were the norm for decades, 16 KiB is Apple's choice, and on top of the base size, x86-64 offers 2 MiB and 1 GiB pages, ARM64 2 MiB, 32 MiB, 512 MiB or 1 GiB blocks depending on the granule.

Linux uses huge pages two ways. Transparent huge pages (THP) let the kernel back suitable anonymous memory with 2 MiB pages automatically; the Linux VM here has THP set to always, which is why the experiments above had to opt out with madvise(MADV_NOHUGEPAGE) to see 4 KiB behavior. And hugetlbfs reserves huge pages explicitly, for databases and virtual machines that want guarantees.

Segmentation: a historical detour

Older systems used segmentation: instead of one linear address space, a program gets several segments (code, stack, symbol table), each starting at 0 and able to grow independently. 32-bit x86 had the full machinery: selectors in CS, DS and SS, descriptors in the GDT and LDT with a base and a limit, and paging applied on top, all modeled on MULTICS; and four protection rings with call gates between them.

That describes 32-bit x86. In 64-bit mode, which every current x86 operating system uses, segmentation is essentially gone: the bases of CS, DS, ES and SS are treated as 0 and their limits aren't checked. Only FS and GS keep a base, and it's used for a single purpose: pointing at per-thread data (Linux puts thread-local storage behind FS, Windows its thread information block behind GS). Rings 1 and 2 go unused, and system calls use syscall rather than call gates. ARM64 and RISC-V never had segments. Paging alone won: every address space is one flat range, and the regions of /proc/self/maps play the role segments were meant to play, without a second kind of address.

Virtual memory and caches

One observation is worth keeping: virtual memory and caching are the same idea at two levels of the hierarchy. A cache keeps some of memory's lines in fast SRAM, and a miss is handled by hardware in nanoseconds; virtual memory keeps some of the address space's pages in RAM, and a miss is handled by the OS in microseconds, or milliseconds from disk. Both rely on locality. Both evict with approximations of LRU. And the TLB is a cache for the page table itself, sitting on the path of every memory access.

Takeaways

• Programs use virtual addresses; the MMU translates them to physical addresses on every access, page by page. The offset within a page passes through unchanged.
• Page tables are trees: 4 levels of 9 bits on x86-64 and on ARM64 with 4 KiB pages (48-bit addresses), 5 levels for 57 bits. ARM64 also allows 16 KiB and 64 KiB granules; Apple uses 16 KiB.
• A page table entry holds the frame number and the protection bits (present, writable, user, no-execute), plus the accessed and dirty bits the OS uses for eviction.
• The TLB caches translations. Touching many pages costs real time: 6 ns per load packed, 30 ns with one line per 4 KiB page, 8 ns with 2 MiB huge pages, measured here.
• Demand paging allocates frames on first touch: about 500–900 ns per page fault here. The same fault mechanism gives copy-on-write and overcommit.
• When RAM runs out, the OS evicts pages chosen by LRU approximations like clock. If the working set doesn't fit, the system thrashes: thousands of times slower in the container experiment. Memory compression (4:1 on this Mac) delays the trip to disk.
• Segmentation is history on 64-bit x86: only FS and GS survive, for thread-local data.