Virtual Memory Primer

Without virtual memory, each process would see physical RAM directly. Three things would be broken:

• Isolation. Any process could read or write any memory belonging to any other process, including the kernel. There would be no way to run untrusted code safely. Multi-tenant servers, containers, browsers running untrusted JavaScript — all rely on the kernel and CPU enforcing that one process cannot touch another's memory.
• Address-space planning. If processes shared one physical address space, every program would need to be compiled to run at a specific address, and two programs would collide if they both wanted the same address. Linkers and loaders would be insane. With virtual memory, every program is linked to run at the same fixed virtual address — and the kernel maps it to wherever in physical RAM is free.
• Overcommit. Real programs allocate way more virtual memory than they ever use. A 200 GB Java heap on a 64 GB machine is perfectly normal — virtual memory lets the kernel back only the pages that are actually touched with physical RAM, and back the rest with swap (or just never allocate it). This is also what makes fork()'s COW cheap and what lets mallocreturn immediately even for huge sizes.

The mechanism in one paragraph

The hardware adds an extra step to every memory access. Instead of instructions referring directly to physical addresses, they refer tovirtual addresses, which the CPU translates to physical addresses on the fly via a per-process page table (next section). The translation is cached in a small hardware table called the TLB (section 3) so the common case costs nothing. When a virtual address has no physical backing, the CPU raises a page fault (section 4) and the kernel decides what to do — allocate a page, swap one in from disk, or kill the process for accessing unmapped memory.

The cost

Translation isn't free. Every memory access carries the overhead of a TLB lookup. A TLB miss means the CPU walks the page table (4 memory reads on x86-64) before the actual access can complete. The kernel maintains the page tables, which themselves consume memory (~0.2% of the process's mapped size). And the kernel must keep the physical-memory pool balanced — eviction, swap, demand paging are all kernel decisions made on every page fault.

Despite the cost, virtual memory is non-negotiable on any general-purpose OS. The cases where the cost is unacceptable — embedded real-time systems, GPU shaders — either avoid virtual memory entirely (single trusted program, statically known memory) or use simpler variants (large pages, fixed translations).

Memory is managed in pages: fixed-size aligned chunks, 4 KB on every common modern CPU (8 KB on Apple Silicon for performance reasons, but the same idea). Translation operates at page granularity: the bottom 12 bits of a virtual address pass straight through unchanged (within-page offset), and the top bits select which physical page backs this region of the virtual address space.

Why a tree

A flat table that maps every virtual page to a physical frame would need 2³⁶ entries (for 48-bit virtual addresses on 4 KB pages) — 64 GB of table per process. That's obviously absurd. The solution is a tree: levels are populated only where they're needed. Most processes use a few GB at most; their page tables consume a few MB.

x86-64 uses a 4-level tree: PML4 → PDPT → PD → PT. Each level has 512 entries (9 bits of index), each entry is 8 bytes, each table fits in exactly one 4 KB page. 4 × 9 = 36 bits of indices plus 12 bits of offset = 48-bit virtual address. Linux extended to 5 levels on Ice Lake+ (2019) for 57-bit virtual addresses (128 PB), but this is only used when the kernel needs the room.

What an entry contains

Each table entry is 8 bytes containing: the physical address of the next-level table (or the final page, at the leaf), and a handful of bits for permissions and state. The permission bits enforce read, write, execute (separate, since x86-64 added NX bit ~2003), and user-vs-kernel — the CPU faults on any access that violates these. The state bits include Present (set if this entry actually points somewhere), Accessed (set by the CPU on any read), and Dirty (set on any write). The kernel uses Accessed/Dirty to decide which pages to evict.

Huge pages — short-circuiting the walk

A "huge page" is just a page-table entry where the PS (page-size) bit is set, telling the CPU that this level's entry already points to the final page, no further walk needed. On x86-64: a PDPT entry with PS set is a 1 GB page; a PD entry with PS set is a 2 MB page; otherwise, it's the normal 4 KB.

Huge pages have two performance benefits: fewer levels to walk on a TLB miss (3 instead of 4 for 2 MB, 2 instead of 4 for 1 GB), and each TLB entry covers 512× or 262 144× more memory (so the same TLB capacity reaches a much larger working set). The cost is internal fragmentation (a 100 KB allocation rounded to a 2 MB huge page wastes 1.9 MB) and harder defragmentation. Linux Transparent Huge Pages (THP) transparently promotes 4 KB allocations to 2 MB when allocations are large and contiguous.

Switching address spaces

The CR3 register on x86 (or TTBR0_EL1 on ARM64) holds the physical address of the top-level table. Changing it changes the entire address space the CPU sees. This is what happens on a process context switch — and on every kernel↔user transition under post-Meltdown KPTI, which doubled the per-syscall cost.

The Translation Lookaside Buffer is a content-addressed cache of recently-used (virtual page → physical frame) mappings. On a hit, the translation completes in essentially zero additional time (~0.5 ns, fully overlapped with the memory access). On a miss, the CPU walks the page table — 4 reads on x86-64, 5 with the recent extension.

TLB hierarchy

Modern Intel cores have a small L1 dTLB (~64 entries for 4 KB pages) directly accessed on every load/store, and a larger L2 TLB (~1500 entries) consulted on L1 miss. A miss in both triggers a hardware page-table walker, which itself benefits from the data cache holding the page-table pages — so a TLB miss with cached page tables is ~100 cycles, with uncached tables possibly 500+ cycles.

ARM has similar structure. Apple M-series allegedly has unusually large TLBs (~3000 L2 entries on recent generations), which is part of why M-series CPUs cope so well with the working sets of large software.

TLB coverage and the working-set cliff

Multiply TLB entries by page size to get how much memory the TLB can cover before missing. With 1500 L2 entries × 4 KB pages = 6 MB of coverage. A workload that randomly accesses more than ~6 MB of memory will miss the TLB on most accesses and pay the page-walk penalty.

Huge pages dramatically extend coverage. The same 1500 L2 entries with 2 MB pages = 3 GB of coverage; with 1 GB pages, 1.5 TB. This is why databases (Redis, MongoDB), JVMs, and HPC codes care so much about huge pages — they push the TLB-miss cliff out by 500× to 260 000×.

TLB flushes

The TLB holds translations for the current process's page tables. Any change that invalidates a translation — a page being evicted, an mmap region being unmapped, a copy-on-write fault rewriting a page-table entry — requires invalidating the corresponding TLB entry. Architectures provide specific instructions (INVLPG on x86) to flush a single entry, or a full flush.

The expensive flush is the address-space switch. BeforeASID (Address Space Identifier) tagging (Westmere 2010 on Intel, all modern ARM), switching to a different process meant blowing the entire TLB — every translation lost. With ASIDs, TLB entries carry a process tag, so switches preserve each process's entries and only blow the conflicting ones. This is the single biggest reason context switches got cheaper in the 2010s.

Measuring TLB pressure

On Linux: perf stat -e dTLB-load-misses,iTLB-load-missesfor total miss counts; divide by dTLB-loads for miss rate. A miss rate above 1% on a workload claiming to be in cache suggests the working set has outgrown the TLB even though it fits in L1/L2 — at which point huge pages or smaller working sets are the fix.

When the CPU encounters a present-bit-not-set page-table entry (or a permission violation, or a not-yet-walkable level), it traps to the kernel. The kernel reads the faulting address from CR2, looks up what should be there in its bookkeeping (the VMA — virtual memory area — list per process), and either fixes the situation and returns, or kills the process with SIGSEGV.

Demand paging

When you malloc a gigabyte, the kernel doesn't actually allocate a gigabyte of physical memory. It marks the virtual addresses as "allowed but not yet backed" in your VMA list, and returns immediately. Only when you actually touch a page does the page fault fire, the kernel allocate a physical frame, zero it, wire it into the page table, and resume your code. Allocations that are never touched cost nothing. This is what makes overcommit work.

mmap

mmap creates a VMA backed by a file or by anonymous zeroed memory. Reading a memory-mapped file just dereferences the pointer; the page fault on first access reads the file into a physical frame and maps it. Subsequent accesses are cache-hit speed. Writing to a writable mapping eventually triggers writeback to the file (via the page cache, see the file-system primer).

mmap is also how shared libraries get loaded (every process maps libc.so as read-only-shared), and how shared memory between processes works (shm_open + mmap).

Copy-on-write

fork() duplicates the page table but marks every page read-only and increments the physical frame's reference count. Both parent and child see identical pages until one writes — at which point the write triggers a fault, the kernel allocates a fresh frame, copies the page, updates that one process's page table, and resumes. Pages that are never written stay shared forever; pages that are written cost one copy each.

COW is what makes fork() instant even for processes with multi-gigabyte heaps. It's also why a small modification to one page in a redis BGSAVE child process can use much less memory than the redis dataset size — only the modified pages get duplicated.

Swap

When physical memory runs short, the kernel evicts pages: chooses one with the least-recently-used heuristic, writes it to swap (a disk partition or file), updates the page table to mark it not-present-but-in-swap, and frees the physical frame. When the process eventually accesses that page again, the fault triggers a read from swap back into a physical frame — milliseconds of latency for what looks like an ordinary memory access.

Swap is a safety valve, not a performance feature. A working set actively spilling into swap shows up as the application going unresponsive in bursts of seconds. Production servers usually run with vm.swappiness=0 or low values and tight memory budgets to avoid swap entirely.

OOM killer

When physical memory + swap are exhausted and the kernel still needs more, it picks a process to kill via the OOM killer. The score considers memory usage, niceness, and oom_score_adj (an explicit per-process bias). A misconfigured system can OOM-kill the database or the SSH daemon. Setting oom_score_adj on mission-critical processes (or running them under a cgroup with a memory reservation) is how you protect them.

Red flags in code review

• Massive memory reservation up-front without using it. Doesn't cost physical RAM but does cost page-table memory and slows accesses (TLB pressure on the whole range). Map only what you'll touch.
• Repeatedly mmap-ing and munmap-ing small regions. Each is a syscall and an expensive page-table modification. Pool allocations or use a larger fixed mmap region.
• Pinning memory with mlock on huge ranges. Locks pages out of swap and prevents the kernel from balancing memory. Use for security (preventing secrets from hitting swap), not for performance.
• fork() in a process with a large recent writeburst. Every recently-written page is dirty and will get COW-copied on the next write by either parent or child. A fork-heavy server with a big mutable working set duplicates most of its memory.
• Ignoring vm.overcommit_memory in production. The kernel default (1 = always allow) lets malloc succeed on requests that physical memory + swap can't satisfy; the OOM killer fires later, often killing the wrong process. Set 2(strict) on memory-critical hosts and tune overcommit_ratio.