The TLB and Multi-Level Page Tables

Page-table translation as described so far is correct but slow and bulky. Slow, because every memory reference now needs a prior memory reference to read the PTE; translation doubles memory traffic. Bulky, because a flat table with one PTE per virtual page is gigantic for a modern address space. This lesson fixes both, with two independent ideas. The translation lookaside buffer (TLB) caches recent PTEs so the common case never touches the table at all. Multi-level page tables shrink the table itself by allocating only the parts a process actually uses. Together they make translation fast and cheap, and the lesson ends by tracing the full path an address takes.

The TLB: a cache of PTEs

The page table lives in DRAM, so reading a PTE is itself a slow memory access. But PTEs have excellent locality: a single page holds thousands of bytes, so consecutive references hit the same PTE over and over. That is the situation a cache is built for. The MMU keeps a small, fast hardware cache of recently-used PTEs, the TLB, indexed by the virtual page number.

On a reference the MMU presents the VPN to the TLB. A TLB hit returns the cached PTE immediately, and translation finishes in one MMU cycle: no DRAM read. A TLB miss means the MMU must read the PTE from the page table in the slower way (the page-table walk), install it in the TLB, and retry.

A TLB lookup. The VPN indexes the TLB; a hit returns the PTE (hence the PPN) in one fast step. On a miss the MMU walks the page table in DRAM, installs the PTE in the TLB, and retries. Most references hit, because one PTE covers a whole page.

TLB anatomy, bit by bit

A TLB is a set-associative cache whose address is the VPN and whose data is a PTE, so the VPN splits exactly the way a cache address did, except that there is no offset field, because a PTE is one indivisible payload. The low bits of the VPN are the TLB index (TLBI), selecting a set; the remaining high bits are the TLB tag (TLBT), compared against the tags stored in that set. Each entry holds a valid bit, the tag, and the cached PTE (PPN plus permission bits, so protection is enforced on hits too).

Concretely, give the example machine of the first lesson ( $n = 14$ , 64-byte pages, 8-bit VPN) a TLB with 16 entries, 4-way set associative. Then there are $16/4 = 4$ sets, so the TLBI takes $log_{2} 4 = 2$ bits and the TLBT the remaining $8 - 2 = 6$ . For virtual address 0x03D4, whose VPN is 0x0F = 0000 1111: the low two bits 11 select set 3, and the tag 0000 11 = 0x03 is compared against the four entries there.

The TLB fields of virtual address 0x03D4 on the example machine (8-bit VPN, 16-entry 4-way TLB, so 4 sets). The VPN's low 2 bits are the TLB index (set 3); its high 6 bits are the TLB tag (0x03). The VPO plays no part in the TLB lookup.

The index comes from the low VPN bits for the same reason it did in a data cache: adjacent pages then map to different sets, so a program marching through a contiguous region spreads across the whole TLB instead of thrashing one set.

What a miss costs

The TLB is judged by the same arithmetic as any cache. A hit adds essentially nothing: the lookup is folded into the MMU's address path and finishes within the cycle. A miss costs a page-table walk, and how bad that is depends on the table's shape:

Flat table: one extra memory read for the PTE: tens to a couple hundred cycles depending on where it is found (PTEs are ordinary memory, so they are cached in L2 and L3 like anything else).
Four-level table (below): up to four dependent reads: each level's entry supplies the address of the next, so they cannot overlap. If the walk hits in L2/L3, perhaps 100–200 cycles total; if every level goes to DRAM, closer to 800.

What rescues the average is the hit rate. A typical L1 TLB (64 entries, 4-way, backed by a larger, slower L2 TLB) hits well over 99% of references, so even a few-hundred-cycle walk amortizes to roughly a cycle per reference. The failure pattern to know: a TLB with 64 entries and 4 KB pages reaches only $64 \times 4 KB = 256 KB$ of memory. A program whose active data spans much more than that — a giant hash table, pointer-chasing across a big heap — misses in the TLB even though its data may sit happily in the L2 or L3 cache. Such workloads are why huge pages exist (end of this lesson).

Why a flat page table does not scale

Now the size problem, worked out exactly. A 64-bit machine using 48-bit virtual addresses with $4 KB$ pages ( $p = 12$ ) has VPNs of $48 - 12 = 36$ bits, so a flat table needs $2^{36}$ entries. At 8 bytes per PTE:

2^{36} PTEs \times 2^{3} bytes = 2^{39} bytes = 512 GB,

per process: thirty-two times the DRAM of a 16 GB machine, for the table alone, before storing a single byte of actual data. And almost all of it would describe virtual pages the process never uses. A flat table is sized by the address space, not by what the program actually touches, and that is the whole defect.

The fix exploits sparsity: a process's used pages — code, a little heap, a little stack near the top — occupy a tiny, clustered fraction of the space, with vast unallocated gaps between. We want a structure whose size tracks the used pages, not the whole space.

Multi-level page tables

A multi-level (hierarchical) page table is a tree of tables. The VPN is split into several index fields, one per level. The top-level index selects an entry in the level-1 table; that entry, if present, points to a level-2 table; its index selects the PTE (or points to a deeper level). The space saving is simple and exact: a sub-table is allocated only if at least one of its pages is in use. A level-1 entry covering an unused region of the address space is simply marked absent, and the entire level-2 table it would have pointed to is never created.

A two-level page table. The VPN splits into a level-1 index and a level-2 index. The level-1 entry points to a level-2 table; its entry is the PTE giving the PPN. Level-1 entries for unused regions are null, so their level-2 tables are never allocated — the table tracks used pages, not the whole space.

The savings are large. With a two-level scheme over the same 36-bit VPN (say 18 bits per level), a process that uses only a handful of regions needs the single level-1 table plus a few level-2 tables, a few kilobytes total instead of half a terabyte. The tree is only as big as the address space is dense. The cost is that a TLB miss now requires several dependent memory reads to walk down the levels, which is precisely why the TLB matters, since it skips the walk entirely on a hit.

The x86-64 four-level walk

Real x86-64 hardware uses four levels, and the split of the 48-bit virtual address is worth memorizing because everything about it is forced. Each table must hold 8-byte entries and it is convenient for a table to be exactly one page: $4 KB /8 B = 512 = 2^{9}$ entries, so each level consumes 9 bits of VPN. Four levels cover the $36$ -bit VPN exactly:

VPN1 9 + VPN2 9 + VPN3 9 + VPN4 9 + VPO 12 = 48 bits .

The walk starts at the CR3 register, which holds the physical address of the current process's level-1 table (loading CR3 is how a context switch swaps address spaces). VPN1 indexes that table; the selected entry holds the physical address of a level-2 table; VPN2 indexes it; and so on, until the level-4 entry is the actual PTE with the PPN. The physical address is that 40-bit PPN with the 12-bit VPO appended: a 52-bit physical address space.

The x86-64 four-level page-table walk. The 48-bit virtual address splits 9+9+9+9+12. CR3 holds the physical address of the level-1 table; each level's selected entry gives the base of the next table; the level-4 entry is the PTE, whose PPN joins the VPO to form the physical address. Each table is 512 entries of 8 bytes: one page.

Trace one walk on a concrete address. Take the canonical Linux user address 0x0000_5555_5555_6008 and slice off the low 48 bits, 0x5555_5555_6008. The bottom 12 bits, 0x008, are the VPO. The four 9-bit VPN fields, read from the top of the 36-bit VPN down, come out as

VPN1 = 0x0AA, VPN2 = 0x155, VPN3 = 0x0AA, VPN4 = 0x156 .

The hardware reads CR3 to find the level-1 table, indexes entry 0x0AA to get the level-2 table's physical base, indexes entry 0x155 there for the level-3 base, then entry 0x0AA for the level-4 base, and finally entry 0x156 is the PTE holding the PPN. Four dependent reads, each feeding the next table's address, and the PPN then joins VPO 0x008 to form the physical address. Every one of the four reads is a full memory access on a TLB miss — which is why the TLB, skipping all four on a hit, is essential.

Now the sparsity payoff, with numbers. One level-2 entry stands for $2^{9} \times 2^{9} \times 4 KB = 1 GB$ of virtual space; one level-4 table maps $512 \times 4 KB = 2 MB$ . A small process — a few MB of code, heap, and stack in three clusters — needs the level-1 table, about one level-2 and level-3 table per cluster, and a few level-4 tables: perhaps a dozen pages of table, under 50 KB, against the 512 GB a flat table demands. The table grows one 4 KB page at a time, in proportion to what the process actually maps.

End to end: one reference, all the machinery

Everything in this module now composes into a single path, the same organization the Core i7 uses (two levels of TLB, four-level walk, physically addressed caches). For one load instruction:

The CPU emits a 48-bit virtual address; the MMU splits off the VPN.
The VPN's low bits index the L1 TLB, its high bits are compared as the tag. On a hit, the usual case, the PPN is available immediately.
On a miss, the L2 TLB is tried; failing that, the hardware walks the four levels from CR3, faulting to the OS if the PTE is invalid, and installs the PTE in the TLB.
The PPN plus the untouched VPO form the physical address, which goes to the L1 data cache, and on a miss, out through L2, L3, and DRAM.

The combined translation pipeline. The VPN tries the TLB; a hit yields the PPN. A TLB miss triggers a page-table walk (and a page fault if not resident), then fills the TLB. The resulting physical address goes to the cache, then to memory on a cache miss.

To see actual bits move, run the example machine once more, end to end. Recall its parameters: 14-bit VA, 64-byte pages, the 16-entry 4-way TLB from earlier, and give it a small L1 cache: direct-mapped, 16 sets, 4-byte lines, so a 12-bit physical address splits into a 6-bit cache tag (CT), 4-bit set index (CI), and 2-bit block offset (CO). The load of 0x03D4:

Split: VPN 0x0F, VPO 0x14.
TLB: TLBI 3, TLBT 0x03, a hit; the cached PTE gives PPN 0x0D. No page-table access.
Physical address: 0x0D joined with 0x14 is 0x354.
Cache: 0x354 = 0011 0101 0100 splits into CO 0, CI 0x5, CT 0x0D. Set 5's tag matches, a hit, and the word comes back with no DRAM access at all.

One load, end to end, with real values: VA 0x03D4 splits; the TLB hits in set 3 with tag 0x03 and supplies PPN 0x0D; the physical address 0x354 splits into cache fields CT 0x0D, CI 0x5, CO 0; the L1 cache hits. Two table-free, DRAM-free lookups serve the reference.

Note that the cache tag 0x0D is the PPN, because on this machine both happen to be the high 6 bits of the physical address. Which raises the last question of the module: if the cache needs the physical address, must it sit idle while the TLB works?

Virtual memory meets the cache: the overlap trick

Caches on real machines are physically addressed: tags and indices come from the PA, after translation. This is the sane choice: two processes mapping the same frame hit the same cache lines (sharing works), and one process's cached data never answers another's virtual address. But it appears to put the TLB in series with the L1 cache on every single load, adding its latency to the most latency-critical path in the machine.

The way out is in the bit fields. Translation changes only the page number; the low 12 bits, the VPO, pass through untouched, and are available the moment the CPU emits the virtual address. So if the cache's set index and block offset fit entirely inside those low 12 bits, the cache can select its set and start reading lines in parallel with the TLB lookup, and use the PPN only at the end, for the tag comparison. TLB and cache overlap almost completely.

The overlap trick. The cache index (CI) and block offset (CO) of a Core-i7-style L1 (64 sets, 64-byte lines) occupy exactly the low 12 bits, which equal the VPO and need no translation. The cache reads its set while the TLB translates the VPN; only the tag comparison waits for the PPN.

This is a deliberate design constraint on the L1. A cache indexed by untranslated bits can have at most $2^{12}$ bytes per way, so the classic 32 KB L1 is 8-way associative precisely so that $64 sets \times 64 B = 4 KB$ per way fits inside the page offset. Growing the L1 means growing associativity, not sets, one of the cleanest examples in the whole machine of a size chosen by an address-bit boundary rather than by silicon budget.

Huge pages

One last lever. x86-64 lets a walk stop early: a level-3 entry can declare itself a terminal PTE mapping a 2 MB page (its 21 low bits all offset), and a level-2 entry a 1 GB page. One TLB entry then covers 512 or 262,144 ordinary pages, multiplying TLB reach from 256 KB toward 128 MB or beyond, and the walk shortens by one or two levels. Databases, JVM heaps, and hypervisors — workloads whose working sets dwarf ordinary TLB reach — use huge pages routinely. The price is coarser granularity: a 2 MB page is allocated, swapped, and protected as one unit, so huge pages suit big, long-lived, uniformly-used regions rather than general allocation.

Walkers, ASIDs, and virtualization

The translation path in this lesson is a decades-old design under active pressure, and the modern refinements all attack the same cost: the walk.

Hardware page-table walkers were not always standard. Early RISC machines (MIPS, SPARC) took a TLB miss as a software trap and let the OS walk the table in a handler — flexible, but slow, since every miss paid a pipeline flush and a handler. x86 has always walked in hardware, and that choice won: the walker is a small state machine that reads the four levels itself, and it caches the upper levels in paging-structure caches so that references sharing a high-order prefix skip the top of the walk. The end result is that a TLB miss on modern x86 costs a handful of cache-resident reads, not four DRAM trips.

Context switches used to flush the whole TLB, because every entry belonged to the outgoing address space. The fix is the address-space identifier (ASID, or Intel's PCID): tag each TLB entry with the process it belongs to, so entries from several processes coexist and a switch need not flush. This became urgent after Meltdown forced kernel and user page tables apart (kernel page-table isolation), which would otherwise flush the TLB on every system call; PCID tagging is what keeps that mitigation affordable.

Huge pages and virtualization are where TLB reach matters most today. A guest running under a hypervisor faces two-dimensional page walking: the guest's virtual address translates through the guest's tables to a guest-physical address, which then translates through the hypervisor's nested / extended page tables to a real physical address — and because each guest-level access is itself a guest-physical address needing its own walk, a single miss can cost up to $(4 + 1) \times (4 + 1) = 25$ memory references in the worst case (Bhargava et al., 2008, ASPLOS, which introduced nested paging). Huge pages cut both dimensions of that walk and multiply TLB reach, which is why databases and virtualization hosts depend on them; the mechanism is the early-terminating walk this lesson described.

That completes the virtual-memory machinery. A page fault, raised when a PTE is invalid, is one member of a broader family of events that divert the processor from its normal flow — interrupts, traps, faults, and aborts. The next module, exceptional control flow, takes up that mechanism in full.