Virtual Memory: Page Tables, TLBs and Faults

The popular explanation, "virtual memory lets you use more memory than you have", is the least interesting of its benefits. Indirection between the address a program uses and the address the DRAM chip sees buys four properties at once:

• Isolation. A pointer in process A simply cannot name a byte in process B, because A's page tables never map it. This is enforced by hardware on every single access.
• Relocation. The linker can place your code at a fixed virtual address and the loader is free to put it anywhere physical.
• Overcommit and laziness. A mapping can exist with no physical page behind it until first touch.
• Uniform permissions. Read, write, execute, and user versus kernel access are bits in the translation itself, checked for free.

The cost of all four is that every load and store now requires a translation.

A flat array mapping every 4 KiB page of a 48-bit address space would need 2 to the 36 entries, hundreds of gigabytes per process. Unworkable. So translation is a sparse radix tree instead.

On x86-64 with the standard 4-level paging, a canonical virtual address splits into five fields: four 9-bit indices and a 12-bit offset. Nine bits selects one of 512 entries in a 4 KiB table, and each entry is 8 bytes. Four levels of 9 bits plus the 12-bit offset gives 48 usable bits, which is 256 TiB of address space.

CR3 holds the physical address of the top table, and switching CR3 is what switches address spaces. Intel's 5-level paging, enabled by setting bit 12 of CR4 (the LA57 bit) and first shipped in Ice Lake, adds a fifth 9-bit index for 57-bit addresses, 128 PiB.

A page walk on x86-64 costs up to four dependent memory accesses before the real access even starts. That is what the TLB exists to avoid.

The TLB is a small, fully associative cache of recent virtual-to-physical translations sitting in front of the page walker. A hit is essentially free, folded into the pipeline. A miss triggers the walk.

Mel Gorman measured the miss cost directly in his LWN huge pages series. On an Intel Core Duo T2600 he found the cost of a TLB miss at 19 clock cycles, or 8.80 nanoseconds; on an AMD Athlon 64 3000+ it was 37 cycles, 18.17 nanoseconds; and on a PPC970MP he calculated roughly 563 cycles. Same concept, an order of magnitude apart across architectures.

The number that actually matters is coverage. Gorman's x86 machine reported a 128-entry data TLB for 4 KiB pages. 128 times 4 KiB is 512 KiB of memory reachable without a walk. A process with a 2 GiB working set and random access misses constantly.

When the walk finds no valid translation, the CPU raises a page fault: a synchronous exception that hands control to the kernel with the faulting address and an error code describing the access.

The handler consults the process's list of virtual memory areas and picks one of three answers:

• Minor fault. The mapping is legitimate and the data is already in RAM, or needs only a zero page. No disk touched. This covers first touch of freshly allocated memory and hits on the page cache.
• Major fault. The mapping is legitimate but the content must come from storage, from a file or from swap. The task blocks and the scheduler runs somebody else.
• Invalid. No VMA covers the address, or the access violates the permission bits. The kernel delivers SIGSEGV.

A segfault is therefore not a special crash mechanism. It is the ordinary fault path reaching its third case.

Both are the kernel deliberately installing a page table entry that will fault, then doing the real work in the handler.

Demand paging. malloc() of a gigabyte returns instantly because nothing is backed yet. The VMA exists; the page table entries do not. Each first touch takes a minor fault and gets a physical frame then. This is why resident set size climbs as a program warms up while virtual size was already huge from the start.

Copy-on-write. On fork(), the kernel does not copy the address space. It copies the page tables and marks every writable private page read-only in both parent and child. The first write from either side traps as a protection fault, the handler allocates a fresh frame, copies 4 KiB into it, restores write permission for that one process, and returns. Pages nobody writes are never duplicated.

mmap() is how userspace asks for a VMA directly. Two independent axes decide what you get.

// File-backed, private: the classic executable/library mapping.
// Reads come from the page cache; writes trigger copy-on-write
// and are never visible in the file.
void *p = mmap(NULL, len, PROT_READ|PROT_WRITE,
               MAP_PRIVATE, fd, 0);

// File-backed, shared: writes go to the page cache pages that
// ARE the file. Other mappers of the same file see them.
void *q = mmap(NULL, len, PROT_READ|PROT_WRITE,
               MAP_SHARED, fd, 0);

// Anonymous: no file. This is what large malloc() calls become.
void *r = mmap(NULL, len, PROT_READ|PROT_WRITE,
               MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);

File-backed versus anonymous decides where a major fault reads from. Private versus shared decides whether a write copies or publishes. Every mapping in /proc/self/maps is one of these four combinations.

When free memory runs low the kernel reclaims pages rather than failing allocations. It keeps pages on active and inactive LRU lists, split into file-backed and anonymous.

File-backed clean pages are cheapest to reclaim: drop them, since the file still has the content. Dirty file pages must be written back first. Anonymous pages have nowhere to go unless swap exists, which is the entire purpose of swap: it makes anonymous memory reclaimable.

vm.swappiness, documented in the kernel's sysctl guide and defaulting to 60, biases the choice between evicting file pages and swapping anonymous ones. Setting it to 0 does not disable swap, it only makes the kernel avoid anonymous reclaim until it is nearly forced.

The failure mode is thrashing: the working set exceeds RAM, so every fault evicts a page someone is about to fault back in. Throughput collapses while the CPU sits idle waiting on I/O.

If a 128-entry TLB covers only 512 KiB with 4 KiB pages, the fix is bigger pages. x86-64 supports 2 MiB pages by stopping the walk one level early, and 1 GiB pages by stopping two levels early. One TLB entry then covers 512 times or 262144 times as much memory.

The kernel's transparent hugepage documentation names both wins: "a single TLB entry will be mapping a much larger amount of virtual memory in turn reducing the number of TLB misses", and taking one fault per 2 MiB region rather than 512, "reducing the enter/exit kernel frequency by a 512 times factor".

The gotcha is that 2 MiB of physically contiguous free memory has to exist. Under fragmentation, THP in always mode can stall an allocation while the kernel compacts memory. The documented default is madvise: huge pages only where the application asked via madvise(MADV_HUGEPAGE).

Linux overcommits by default: mmap() succeeds for more memory than exists, on the bet that most of it is never touched. When that bet loses and reclaim cannot free enough, the kernel invokes the OOM killer rather than returning failure to a caller that would not check it anyway.

select_bad_process() scores every task with oom_badness(). The score is essentially the task's resident memory plus page tables plus swap, normalised against total memory to a 0 to 1000 scale, so the heaviest user is the default victim. The kernel picks the highest scorer and kills it.

Userspace steers this through /proc/PID/oom_score_adj, documented in proc_pid_oom_score_adj(5) with a range of -1000 to +1000. The extremes are absolute: -1000 makes a process exempt, +1000 adds the equivalent of all system RAM and effectively volunteers it. Read the current verdict from /proc/PID/oom_score.

• Virtual size is not memory used. A process with 40 GiB of VSZ and 300 MiB of RSS is normal. Only RSS costs physical frames.
• Freeing memory does not always return it. Small free() calls go back to the allocator, not the kernel. Only munmap() or madvise(MADV_DONTNEED) releases frames.
• The OOM killer kills the biggest, not the guilty. A leaking helper can get your database killed instead. That is what oom_score_adj is for.
• Swap off is not the safe setting. With no swap, anonymous memory is unreclaimable, so pressure goes straight to the OOM killer instead of degrading gracefully.
• Page-table memory is real memory. Every mapped 4 KiB page costs 8 bytes of PTE, plus the upper levels. Thousands of processes mapping the same huge file is a measurable cost.