Page Tables

Conceptually the page table is exactly what the interactive shows: a row per virtual page with a physical frame, a present bit and permissions. The CPU takes the virtual page number, reads the row, checks present and permissions against the access being made, and forms the physical address from the frame number and the page offset. That model is correct for every architecture; what differs is how the rows are stored.

Do the arithmetic. A 48-bit address space with 4 kB pages has 2³⁶ = 68 billion pages. At 8 bytes per entry a flat table is 2³⁹ bytes — 512 GB — per process, before the process has allocated anything. Even the 32-bit case, 4 MB per process, was too much in 1985 for a machine with 4 MB of RAM and twenty processes. And almost all of it would be empty: a typical process maps a few hundred regions totalling a few hundred MB, scattered across a space of 128 TB.

The address space is sparse, so the map should be sparse. The standard structure is a radix tree (a trie over the address bits, the same idea as the DSA Trie over characters): the virtual page number is split into fixed-width chunks, each chunk indexes one level of table, and a table at any level exists only if something below it is mapped. Empty subtrees cost nothing. A process with 50 MB mapped needs a few dozen 4 kB tables instead of 512 GB.

On x86-64 with 4-level paging a 48-bit address is split into 9 + 9 + 9 + 9 + 12 bits. Each 9-bit chunk indexes a table of 512 eight-byte entries — exactly one 4 kB page, which is not a coincidence: tables are themselves pages, allocated from the same frames as everything else. The walk starts at the top-level table, reads the entry selected by the first 9 bits, follows it to the next table, and so on; the fourth level yields the PTE with the frame number, and the final 12 bits are the offset. Linux names the levels PGD → PUD → PMD → PTE (with a P4D inserted for 5-level paging); Intel calls them PML4 → PDPT → PD → PT. ARM64 uses the same shape with level numbers.

Every level can short-circuit. An entry marked not-present at level 2 means an entire 1 GB range is unmapped, and the walk stops with a fault. An entry at level 3 with the page-size bit set maps a 2 MB huge page directly, skipping the last level — which is why huge pages save both table memory and walk steps (Paging). The walk is done by the CPU’s page-walker hardware, with no software involved, and the result is cached in the The TLB; the kernel only ever *writes* the tables.

The walk has to start somewhere, and that somewhere is a single privileged register holding the physical address of the top-level table: CR3 on x86-64, TTBR0_EL1 (user) and TTBR1_EL1 (kernel) on ARM64, SATP on RISC-V. Writing it is the address-space switch in Context Switching; reading it from user mode is impossible. Because the register holds a *physical* address, the top-level table is the one thing the kernel must know the physical location of directly — everything below is reached by walking.

On x86-64 the kernel half of the space lives in the top 256 entries of every process’s top-level table, and Linux simply copies those entries into each new process’s PGD so that all processes share the same kernel subtree. ARM64 avoids even that copy by giving the kernel its own base register (TTBR1) that never changes on context switch. Both are ways of expressing "the kernel is mapped everywhere" from The Virtual Address Space.

The kernel keeps more than the hardware tables. Linux’s VMAs describe regions with a backing and permissions and are the source of truth; the hardware tables are a cache of them, populated on fault and torn down on munmap. Reverse maps (rmap) let the kernel go from a physical frame to every PTE referencing it, which reclaim needs when it wants to unmap a shared page from every process at once.

A four-level walk is four dependent memory reads before the actual load or store can even be issued — five memory accesses for one. If each hit L1 cache the walk costs ~20 cycles; if the tables are cold it is four DRAM round trips, ~300 ns, for a load that should take 1 ns. Doing that on every access would make virtual memory unusable, which is why the walk result is cached in the TLB and why the CPU also caches intermediate levels in page-walk caches (so that a TLB miss to a nearby page redoes only the last level). The The TLB lesson is where those numbers become the dominant term.

The size of the tables is a cost of its own: a database with a 200 GB shared buffer mapped by 500 backend processes has 500 copies of the page tables for that region — 400 MB each at 4 kB pages, 200 GB in total, which is more than the buffer. That is not a hypothetical; it is the case PostgreSQL’s huge_pages setting exists for, and huge pages cut it by 512×.