Multilevel Page Tables

A single-level (flat) page table maps every virtual page number (VPN) directly to a physical frame number via array indexing: entry `i` describes virtual page `i`. This is $O(1)$ per lookup, but its size is proportional to the entire virtual address space, not to how much of it is actually used. For a 32-bit address space with 4 KB pages this is already about 1 million entries (4 MB at 4 bytes/entry); for 64-bit address spaces it is astronomically larger, and per-process, since every process conceptually has its own full address space. A multilevel page table restructures this array as a tree. The virtual address is partitioned into several fixed-width index fields, ordered from most significant to least significant, plus a final page offset field. The first index selects an entry in a small top-level table (often called the page directory or page global directory); that entry is either invalid (meaning the entire subtree it would describe is unmapped) or a pointer to a second-level table. The second index repeats the process in that table, and so on, until the last index selects the actual page table entry (PTE) containing the physical frame number, protection bits, and status bits (present, dirty, accessed). The page offset is never used for indexing — it addresses bytes within the final physical frame and is copied through unchanged. The key structural property is sparsity preservation: an entire subtree — potentially covering gigabytes or terabytes of virtual address space — collapses to a single "not present" entry in its parent table if nothing in that region is mapped. Only tables along paths that lead to real, mapped pages are ever allocated. This is precisely what happens for a typical process: a small mapped region near address 0 (code, data), a small mapped region near the top of the address space (stack), and a growable heap — with an enormous unmapped gap in between that costs almost nothing to represent.

Splitting the address. For an $L$-level page table with $b$ bits of page offset and index fields of widths $k_1, k_2, \dots, k_L$ (from most to least significant), the virtual address layout is: ``` [ index_1 | index_2 | ... | index_L | offset ] k_1 k_2 k_L b ``` with $k_1 + k_2 + \dots + k_L + b =$ (virtual address width). Classic 32-bit x86 uses $L = 2$, $k_1 = k_2 = 10$, $b = 12$ (4 KB pages). Modern x86-64 (4-level paging) uses $L = 4$, $k_i = 9$ for each level, $b = 12$, covering 48 bits of virtual address; 5-level paging extends this to $L=5$, covering 57 bits.

Walking the tree. Translation is a chain of table lookups, each producing the base address of the next table (or, at the last level, the frame): ```pseudocode function TRANSLATE(virtual_address, page_table_base): // Split into L index fields and an offset, MSB to LSB idx[1..L], offset = SPLIT(virtual_address) table_base = page_table_base // physical address of top-level table for level = 1 to L: entry_addr = table_base + idx[level] ENTRY_SIZE entry = MEMORY_READ(entry_addr) // physical memory access if not entry.present: raise PAGE_FAULT(virtual_address, level) if level < L: table_base = entry.next_table_base // descend one level else: frame = entry.frame_number // final PTE reached CHECK_PERMISSIONS(entry, requested_access) // else PAGE_FAULT physical_address = frame FRAME_SIZE + offset return physical_address ``` Each iteration of the loop is one physical memory access (barring caching), so an $L$-level walk costs up to $L$ memory accesses before the data itself is even fetched. This is the price paid for sparsity, and it is exactly what the Translation Lookaside Buffer exists to amortize: the TLB caches the end-to-end result (VPN → frame number), so a TLB hit skips the entire walk and costs one access, identical to the flat-table case. Only a TLB miss pays the full $L$-step page-table walk.

Populating the tree lazily. Tables are created on demand: ```pseudocode function MAP_PAGE(virtual_address, frame_number, perms, page_table_base): idx[1..L], _ = SPLIT(virtual_address) table_base = page_table_base for level = 1 to L - 1: entry_addr = table_base + idx[level] ENTRY_SIZE entry = MEMORY_READ(entry_addr) if not entry.present: new_table = ALLOCATE_FRAME() // zero-fill: all entries "not present" entry.next_table_base = new_table entry.present = true MEMORY_WRITE(entry_addr, entry) table_base = entry.next_table_base // last level: install the real mapping entry_addr = table_base + idx[L] ENTRY_SIZE MEMORY_WRITE(entry_addr, PTE(frame_number, perms, present=true)) ``` Notice that mapping a single new page in a previously untouched region may require allocating $L-1$ new intermediate tables — but subsequent pages mapped nearby (sharing the same higher-level indices) reuse those tables. This is why multilevel tables are efficient specifically for clustered/sparse access patterns (a few contiguous regions), not for address spaces with pages scattered uniformly at random.

Hardware vs. software walks. On x86-64 the CPU's memory management unit (MMU) performs the walk in hardware on a TLB miss, reading the page-directory/page-table chain itself and inserting the result into the TLB. On some architectures (classic MIPS, some RISC designs) the walk is done by a software TLB-miss handler, giving the OS full control of the table format at the cost of trap overhead. Either way, the algorithm above is what executes.

Time. A page-table walk with $L$ levels performs exactly $L$ sequential physical memory reads on a TLB miss: $O(L)$ time, where $L$ is a small constant (2 to 5 in real systems), so effectively $O(1)$ per translation. On a TLB hit — the overwhelmingly common case, since TLB hit rates typically exceed 95–99% in practice — translation costs $O(1)$ regardless of $L$, because the TLB stores the final frame number directly, bypassing the walk entirely. The amortized cost of translation is therefore dominated by the miss rate and $L$, not by $L$ alone:

where $p$ is the TLB miss probability and the $+1$ accounts for the final data access itself. Because $p$ is small and $L$ is small, this stays close to $O(1)$ in practice, though every additional level does add real latency to every miss (this is exactly the cost that motivates caching partial walks — see below — and, at the far end of the design space, motivates abandoning the tree structure altogether in Inverted Page Tables).

Space. This is the entire point of the design, so it deserves an honest derivation. Let the address space have $N$ total virtual pages, and let $M \le N$ pages actually be mapped, clustered into $R$ contiguous regions ($R \ll M$ in typical processes: text, data, heap, stack, a few mmap'd libraries). For an $L$-level tree with fan-out $F$ per table (i.e., $2^{k_i} = F$ entries per level, assuming equal index widths for simplicity):

• A flat table needs $N$ entries: $O(N)$ space, independent of usage.
• A multilevel table needs, in the worst case, one full path of $L$ tables per region, plus the actual leaf tables covering the $M$ mapped pages:

Since $F$ (table fan-out, e.g. 512 or 1024) and $L$ are both constants, this is $O(R + M)$ — linear in the amount of address space actually used, not in the size of the address space itself. For a process using a few megabytes out of an exabyte-scale virtual address space, this is the difference between kilobytes of page-table memory and an impossibility. The tradeoff is explicit: multilevel tables shrink space from $O(N)$ to $O(R+M)$ at the cost of raising per-miss time from $O(1)$ to $O(L)$. This is a textbook space–time tradeoff, and it is a good one precisely because TLB caching hides the time cost on the overwhelming majority of accesses while the space savings apply unconditionally, on every process, all the time.

Correctness argument. The invariant maintained by `MAP_PAGE` and relied upon by `TRANSLATE` is: > For every virtual address $v$ with a valid mapping, following the index chain derived from $v$, starting at the page-table base register, reaches a present PTE containing exactly the frame most recently mapped for $v$ (or a fault, if unmapped). This holds by induction on the number of calls to `MAP_PAGE`. Base case: an empty tree (all top-level entries not-present) correctly signals a fault for every address, since nothing is mapped. Inductive step: `MAP_PAGE(v, f, ...)` walks the same index chain that `TRANSLATE(v)` would walk (both derive indices from $v$ via the identical `SPLIT` function), allocating any missing intermediate table it encounters and never disturbing entries reached by a different index chain (each entry is indexed by a distinct combination of index bits, so writes are disjoint across addresses that diverge at any level). Hence after the call, translating $v$ reaches the newly written frame, and translating any $v' \ne v$ is unaffected unless $v'$ shares a full prefix of index bits with $v$ (in which case it correctly shares the intermediate tables, which is exactly the desired sharing behavior for pages within the same region). Termination is immediate since both algorithms loop exactly $L$ times.

Take the classic 32-bit two-level x86 layout: 4 KB pages ($b=12$), two 10-bit indices ($k_1=k_2=10$), 4-byte entries, so each table has $2^{10}=1024$ entries and occupies exactly one 4 KB page (1024 × 4 bytes). Suppose a process maps virtual address `0x00402018` (code) and we trace the read of one byte there.

Step 1 — split the address.

Check: `0x00402018` = `0000 0000 0100 0000 0010 0000 0001 1000`₂. Splitting at bit 22 and bit 12 confirms idx1 = 1, idx2 = 2, offset = 24. ✓.

Step 2 — read the Page Directory entry. The CR3 register holds the physical base of the page directory, say `0x00100000`. The MMU reads entry 1:

Suppose this entry contains `present=1`, `next_table_base=0x00105000`.

Step 3 — read the Page Table entry. Using the second-level table at `0x00105000`, index 2:

Suppose this entry contains `present=1`, `frame=0x340`, `R/W=1`, `U/S=1`.

Step 4 — assemble the physical address.

Total cost: 2 memory reads (page directory, page table) plus the final data read — 3 physical accesses on a TLB miss, matching $O(L)$ with $L=2$. On a subsequent access to the same page, the TLB already holds `0x00402 → 0x340` (VPN → frame), so the translation costs one lookup, not three, until that TLB entry is evicted.

Space comparison for this process. Suppose this process maps 3 regions totaling 600 pages (2.4 MB): a 200-page code segment, a 150-page heap, and a 250-page stack, scattered across a 32-bit (4 GB) address space of $2^{20}$ possible pages.

• Flat table: $2^{20}$ entries × 4 bytes = 4 MB, always, regardless of usage.
• Two-level table: at most 3 page-directory entries occupied (one per region, assuming each region fits within one 4 MB directory-entry span; a 250-page stack might span 2 entries in the worst case, so say 4 directory entries) plus one 4 KB second-level table per occupied directory entry, plus the page directory itself (4 KB, since it must exist in full — 1024 entries — even though only a handful are present).

20 KB versus 4 MB — a 200× reduction for this process, and the ratio grows without bound as the mapped fraction of the address space shrinks further (which is the norm on 64-bit systems).

The multilevel page table is less the invention of a single person than the convergent solution multiple hardware architects reached once virtual address spaces grew past what flat tables could afford. Its lineage runs through the paging hardware of the Atlas and Multics projects, through Digital Equipment Corporation's VAX architecture (one of the first widely deployed two-level schemes), and into the x86 and RISC architectures that standardized it for mass-market operating systems.

Every mainstream general-purpose operating system kernel — Linux, Windows, macOS/XNU, the BSDs — implements multilevel page tables as the default translation structure for user and kernel address spaces on x86-64 and ARM64. Linux's generic `pgd/p4d/pud/pmd/pte` naming directly mirrors the up-to-five-level hardware hierarchy; hypervisors add a second, nested layer of multilevel tables (extended/nested page tables) to translate guest-physical to host-physical addresses for virtual machines. Database systems and language runtimes that request huge sparse address-space reservations (for copy-on-write snapshots, garbage-collector heaps, or address-space-layout-randomization guard gaps) depend on the OS's ability to represent those reservations without paying for every unmapped page. Understanding this mechanism is also the necessary foundation for appreciating why some architectures (notably early PowerPC and some historical Itanium designs) instead chose a completely different data structure — the inverted page table — sized by physical memory rather than virtual address space, trading the tree's simplicity for a hash-table lookup and a different set of tradeoffs around shared mappings and reverse lookups.

Ask the tutor: How would the space and time formulas change if we used a hashed multilevel scheme, or moved to an inverted page table entirely?