Why virtual memory

This page uses a small 32-bit machine with a two-level page table so every step fits on the canvas, and spends most of its time on page faults, page replacement, swap and copy-on-write. For the x86-64 four-level walk, PCID, the zero page and huge pages, see Linux Virtual Memory.

Every process sees its own flat address space, from 0 up to 4 GiB (on 32-bit) or 128 TiB (on x86-64), and every address it uses is virtual. On each memory access the CPU's memory management unit (MMU) translates the virtual address into a physical one, using page tables that the kernel builds for that process. This one level of indirection buys a lot:

  • Isolation. A process can only reach the frames its page tables point at. A stray pointer faults instead of scribbling over another program or the kernel.
  • A private, tidy address space. Every copy of ./prog finds its code at the same address, no matter where in RAM its pages really are.
  • More memory than RAM. Pages that are not in use can live on disk (the file they came from, or swap) and come back on demand.
  • Sharing. Two page tables can point at the same frame: shared libraries, the page cache of a file, and every page of a process right after fork.

The animation follows one memory access, mov eax, [0x0804A123], the whole way, and then shows what the kernel does when that access cannot be translated.

Reading the canvas

  • Top line: the running process, the instruction, and its virtual address split into three coloured groups of bits. The red and green groups are the two table indexes; the yellow offset goes straight into the physical address (PA) below.
  • TLB and CR3: the 4 cached translations (page number → PFN, permissions, dirty) and the register that points at the current page directory.
  • Page tables: for A (blue) on the left and, after fork, for B (orange). Only the entries this program can use are drawn: P 101 rw- A D is present, frame PFN 0x101, read-write, accessed, dirty; COW marks a read-only page in a writable mapping; swap S0 is a page that was written to swap slot 0; - was never used.
  • RAM: the data frames, each with its owner(s) (A:H0, A+B:H0 for a shared frame in lilac, cache prog:C for a page-cache page), its R (referenced) and D (dirty) bits, its refcount, and the value it holds. With the clock policy the red hand points at the next frame to look at; LRU shows each frame's last use, FIFO its load time.
  • Swap, disk, counters: swap slots with the value they hold and how many PTEs refer to them, the file prog, and running counts of TLB hits, memory references, faults, swapping and copy-on-write. The green line checks that every read returned the value that process last wrote.

A virtual address is three numbers

Memory is managed in pages of 4 KiB, so the low 12 bits of an address (the offset) say where in the page the byte is, and are never translated. The rest is the virtual page number, which the page tables map to a physical frame number (PFN). One flat table for 220 pages would need 4 MiB per process, almost all of it empty, so the page number is itself split and the table becomes a tree:

32-bit x86 (no PAE), 2 levels              x86-64, 4 levels (48-bit addresses)
 31        22 21        12 11          0    47   39 38   30 29   21 20   12 11      0
[ dir: 10  ][ table: 10  ][ offset: 12 ]    [PML4:9][PDPT:9][ PD:9 ][ PT:9 ][ off:12 ]

0x0804A123 = dir 0x020 | table 0x04A | offset 0x123
PA         = PFN 0x100 << 12 | 0x123 = 0x00100123   (Demo 1)

CR3 holds the physical address of the top table. Each level is one 4 KiB page of entries (1024 of 4 bytes, or 512 of 8 bytes on x86-64), and each entry holds the PFN of the next level plus flag bits: P present, R/W writable, U/S user-accessible, A accessed and D dirty (set by the hardware), and on x86-64 NX no-execute. Recent CPUs add a fifth level (57-bit addresses). A huge page ends the walk early: a PD entry can map 2 MiB directly, a PDPT entry 1 GiB.

Page tables are sparse: the program in the animation uses 32 KiB near 0x08048000 and 4 KiB of stack just below 0xC0000000, and needs one directory and two tables, not 1024 tables. Tables are created by the fault handler the first time a 4 MiB region is touched.

The TLB

A walk costs one memory read per level, before the access itself. The translation lookaside buffer caches recent translations so that most accesses skip the walk. With hit rate h, and counting memory references:

EAT = h · 1 + (1 − h) · (levels + 1)           (in units of one memory access)
    = 0.99 · 1 + 0.01 · 5  =  1.04             (99 % hits, 4-level walk)

Demo 1 shows the difference: the first read of D misses and walks (after a page fault), the second one hits and costs one reference, and so does 0x0804A456, a different address in the same page.

  • Loading CR3 on a process switch flushes the TLB (see the context switch page): the new process starts cold. PCID (x86) and ASID (ARM) tag entries with an address-space ID so they can survive the switch.
  • When the kernel changes a PTE that other CPUs may have cached, it must send them an interrupt to invalidate it: a TLB shootdown, one of the hidden costs of munmap, page migration and reclaim.
  • A TLB has a few thousand entries at most. With 4 KiB pages that covers a few MiB; with 2 MiB huge pages it covers GiBs. That is why databases and JVMs with large heaps use huge pages (-XX:+UseLargePages, PostgreSQL's huge_pages, transparent huge pages).

Page faults are not errors

When the walk finds a PTE that is not present, or present without the needed permission, the CPU stores the address in CR2 and enters the kernel's page-fault handler. Linux's handle_mm_fault then decides:

What the handler findsWhat it doesKind
no VMA contains the addresssend SIGSEGV, si_code = SEGV_MAPERRerror
a VMA, but it forbids the access (write to code, execute data)SIGSEGV, SEGV_ACCERRerror
anonymous page never touchedzero-filled frameminor
file page already in the page cachemap the cached frameminor
file page not cachedread it from disk, then map itmajor
PTE says swap Sk, page still in the swap cachemap that frame againminor
PTE says swap Skread the slot from the swap devicemajor
write to a COW pagecopy it (or just make it writable if nobody else uses it)minor

After a fix, the handler returns and the CPU restarts the faulting instruction, which now finds a valid PTE. A minor fault needs no I/O and costs microseconds; a major fault puts the process to sleep until the disk answers, which costs anything from tens of microseconds on an SSD to milliseconds on a spinning disk. The mappings themselves (VMAs) come from execve and mmap; the program-loading page shows how an ELF file is mapped and then faulted in page by page (where real kernels also read ahead several pages per major fault).

Page replacement

A fault needs a frame but RAM is full, so the policy picks a victim. A clean file page such as prog's code is simply dropped and later read from the file again; an anonymous heap or stack page is written to swap slot S0, its PTE then says swap S0, and the next fault reads it back
Evicting a clean file page is free; an anonymous page must first go to swap, and its PTE remembers the slot.

When a fault needs a frame and RAM is full, some page must go. A clean file page can simply be dropped, because the file still has it. An anonymous page (heap, stack, a private copy) has no file behind it and must be written to swap first; its PTEs then keep the swap slot number, so the next fault knows where to read it back. Which page to pick is the replacement policy:

  • OPT (Belady's optimal) evicts the page used farthest in the future. It needs to know the future, so it is only a yardstick.
  • FIFO evicts the page loaded first, however busy it is. It also shows Belady's anomaly: on the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO has 9 faults with 3 frames but 10 with 4 (Demos 5a and 5b). LRU and OPT are stack algorithms and never get worse with more memory (LRU: 10 then 8).
  • LRU evicts the page unused for the longest time. Exact LRU would need a timestamp or a list update on every memory access, which no MMU does.
  • Clock (second chance) approximates LRU with the one accessed bit the hardware sets for free: the hand sweeps the frames, clears R = 1 bits, and evicts the first page with R = 0. Demos 4b and 4c show where it falls short: before the last reference (S) every R bit is 1, so the hand clears them all and evicts H3, used one step earlier, where LRU evicts H4, the page unused the longest. Enhanced clock also looks at the dirty bit and prefers clean pages, which cost no write.
FIFO on the reference string 1 2 3 4 1 2 5 1 2 3 4 5, frame contents after each reference: with 3 frames there are 9 faults, with 4 frames 10 faults
Belady's anomaly: with FIFO, giving the same reference string one more frame causes more faults (9 → 10).
Clock with 4 frames F0 H4, F1 H1, F2 H2, F3 H3 and the hand at F1. H5 faults: F1 has R = 1, so its bit is cleared and the hand moves on; F2 has R = 0, so H2 is evicted, H5 is loaded into F2 with R = 1 and the hand moves to F3
Clock gives every recently used page (R = 1) a second chance and evicts the first page under the hand with R = 0.

Linux reclaims ahead of time: kswapd wakes when free memory falls below a watermark and frees pages in the background, so faults rarely wait for reclaim. It keeps active and inactive lists for file and anonymous pages (a page is promoted on a second access), and since 6.1 can use MGLRU, which sorts pages into generations. vm.swappiness sets how willing it is to swap anonymous pages rather than drop file pages. The LRU cache page shows the same LRU idea in a software cache.

When the pages a process keeps using (its working set) do not fit in RAM, nearly every access faults and the system spends its time swapping: thrashing. If nothing can be freed at all, the OOM killer picks a process to kill.

fork and copy-on-write

fork must give the child an identical copy of the parent's memory. Copying gigabytes would be slow, and a child that calls exec right away would throw the copy away. So Linux copies only the page tables: every writable private page becomes read-only in both processes and the frame's refcount goes up. The first write by either one faults; the handler sees a COW page with refcount > 1, copies that single page, and gives the writer a writable PTE to its copy. When the last sharer writes, the refcount is 1 and the handler just makes the PTE writable again, without copying (Demo 6: one copy, one reuse).

  • fork + exec is cheap because exec throws the shared mappings away before anyone writes. vfork and posix_spawn skip even the page-table copy.
  • Redis BGSAVE forks a child that writes a snapshot while the parent keeps serving. Memory grows by one page for every page the parent writes during the save, so a write-heavy instance can briefly need up to twice its memory (see Redis Cluster).
  • Linux also avoids allocating memory for pages that are only read: the first read of an anonymous page maps a single shared, read-only zero page, and a real frame is allocated on the first write. The animation allocates a zeroed frame on the first read, to keep the replacement demos simple.

How to see it on a real system

cat /proc/<pid>/maps              # the VMAs: range, permissions, offset, file
cat /proc/<pid>/smaps             # per VMA: Rss, Pss (shared pages divided), Swap, Anonymous
grep -E 'VmRSS|VmSwap' /proc/<pid>/status
ps -o pid,min_flt,maj_flt,rss,cmd -p <pid>    # minor and major faults so far
perf stat -e page-faults,major-faults,minor-faults,dTLB-load-misses ./program
vmstat 1                          # si / so: pages swapped in / out per second
grep -E 'MemFree|Cached|SwapCached|AnonPages' /proc/meminfo

What the animation leaves out

  • It uses 32-bit two-level paging instead of x86-64's four levels: the same walk with half the hops, and addresses short enough to read.
  • Page-table pages are drawn in their own strip and are not counted in the N frames. In reality they are ordinary frames (never swapped out on x86 Linux).
  • The first read of an anonymous page allocates a zeroed frame; Linux maps the shared zero page and allocates on the first write.
  • Replacement is a global clock, LRU or FIFO over N frames, run only when a fault needs a frame, with 16 swap slots. Linux reclaims ahead of time with kswapd, watermarks and active/inactive lists or MGLRU.
  • fork copies every present PTE; Linux skips PTEs of file mappings with no private pages (they just fault in again).
  • A write that first needs a page read in takes two faults here (bring in read-only, then copy-on-write); Linux does it in one.
  • A process killed by SIGSEGV keeps its frames, drawn grey; Linux frees them on exit.
  • No readahead, no huge pages, no NUMA, no PCID/ASID, and one CPU (so no shootdown interrupts). The TLB caches only final translations; real CPUs also cache upper levels of the tree, so a real miss is often cheaper than a full walk.