--- title: The TLB and Multi-Level Page Tables module: Virtual Memory moduleNumber: 7 lessonNumber: 3 order: 703 summary: > A page-table read on every access would double memory traffic; a flat table for a 48-bit space would occupy 512 GB per process. The TLB fixes the first: a small set-associative cache of PTEs inside the MMU whose tag and index come from the VPN. Multi-level page tables fix the second, allocating only the sub-tables a process uses; x86-64 walks four levels with a 9+9+9+9+12 split. We trace one reference end to end through TLB, walk, and cache, and close with the overlap trick that lets the L1 cache start before translation ends. topics: [Virtual Memory] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §9 Virtual Memory" - book: Bistriceanu ref: "Computer Architecture Notes — §10 Virtual Memory" --- [Page-table translation](/computer-architecture/virtual-memory/page-tables-and-page-faults) 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](/computer-architecture/memory-hierarchy/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. > **Definition (TLB).** A **translation lookaside buffer** is a small cache, > inside the MMU, holding recently-used **page-table entries**. It is indexed by > the **virtual page number**; a **TLB hit** returns the PPN in a single fast > lookup, with no page-table access at all. 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. $$ % caption: A TLB lookup. The VPN indexes the TLB; a hit returns the PTE (hence the % caption: PPN) in one fast step. On a miss the MMU walks the page table in DRAM, % caption: installs the PTE in the TLB, and retries. Most references hit, because % caption: one PTE covers a whole page. \begin{tikzpicture}[font=\footnotesize,>=stealth, box/.style={draw, minimum height=10mm, inner sep=3pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[box, minimum width=14mm] (vpn) at (0,0) {VPN}; \node[box, minimum width=16mm, fill=acc!8] (tlb) at (3.0,0) {TLB}; \node[box, minimum width=16mm] (ppn) at (6.4,0) {PPN}; \node[box, minimum width=24mm] (pt) at (3.0,-2.0) {page table\\(DRAM walk)}; % VPN -> TLB \draw[->] (vpn.east) -- (tlb.west); % hit path \draw[->,acc] (tlb.east) -- (ppn.west) node[midway,above] {hit}; % miss path down and back \draw[->] (tlb.south) -- (pt.north) node[midway,right] {miss}; \draw[->] (pt.east) -| (ppn.south) node[pos=0.25,below] {install + retry}; \end{tikzpicture} $$ ## TLB anatomy, bit by bit A TLB is a [set-associative cache](/computer-architecture/memory-hierarchy/set-associative-and-write-policies) 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](/computer-architecture/virtual-memory/address-spaces-and-translation) ($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. $$ % caption: The TLB fields of virtual address 0x03D4 on the example machine % caption: (8-bit VPN, 16-entry 4-way TLB, so 4 sets). The VPN's low 2 bits are % caption: the TLB index (set 3); its high 6 bits are the TLB tag (0x03). The VPO % caption: plays no part in the TLB lookup. \begin{tikzpicture}[font=\footnotesize,>=stealth, bit/.style={draw, minimum size=6mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % TLBT bits (high 6 of VPN): 000011 \foreach \i/\v in {0/0,1/0,2/0,3/0,4/1,5/1} \node[bit, fill=acc!8] at (\i*0.6,0) {\v}; % TLBI bits (low 2 of VPN): 11 \foreach \i/\v in {6/1,7/1} \node[bit, draw=acc, thick] at (\i*0.6,0) {\v}; % VPO bits (unused by the TLB): 010100 \foreach \i/\v in {8/0,9/1,10/0,11/1,12/0,13/0} \node[bit, draw=black, text=black] at (\i*0.6,0) {\v}; \node[anchor=south] at (1.5,0.4) {TLBT = \texttt{0x03}}; \node[anchor=south] at (3.9,0.4) {TLBI = \texttt{3}}; \node[anchor=south, text=black] at (6.3,0.4) {VPO}; \draw[<->] (-0.3,-0.55) -- (4.5,-0.55) node[midway,below] {VPN = \texttt{0x0F}}; \end{tikzpicture} $$ 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\,\text{KB} = 256\,\text{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\,\text{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} \;\text{PTEs} \times 2^3 \;\text{bytes} = 2^{39} \;\text{bytes} = 512\,\text{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. $$ % caption: A two-level page table. The VPN splits into a level-1 index and a % caption: level-2 index. The level-1 entry points to a level-2 table; its entry % caption: is the PTE giving the PPN. Level-1 entries for unused regions are null, % caption: so their level-2 tables are never allocated — the table tracks used % caption: pages, not the whole space. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} % VPN split + of\/fset (top) \node[draw, fill=acc!8, minimum width=18mm, minimum height=7mm, inner sep=0pt, anchor=west] (l1) at (0.3,3.2) {L1 index}; \node[draw, minimum width=18mm, minimum height=7mm, inner sep=0pt, anchor=west] (l2) at (l1.east) {L2 index}; \node[draw, minimum width=16mm, minimum height=7mm, inner sep=0pt, anchor=west] (off) at (l2.east) {of\/fset}; % level-1 table (always allocated) \node[draw, minimum width=20mm, minimum height=26mm, fill=acc!8] (t1) at (1.6,0.6) {}; \node[draw, minimum width=17mm, minimum height=5mm] (t1e) at (1.6,0.8) {}; \node[anchor=north, font=\scriptsize] at (1.6,-0.85) {level 1}; \node[anchor=north, font=\scriptsize, align=center] at (1.6,-1.35) {(n\/ull entries:\\no L2 table)}; % level-2 table \node[draw, minimum width=20mm, minimum height=20mm] (t2) at (4.6,0.3) {}; \node[draw, minimum width=17mm, minimum height=5mm, fill=acc!8] (t2e) at (4.6,-0.1) {PTE}; \node[anchor=north, font=\scriptsize] at (4.6,-0.85) {level 2}; % PPN out (right) \node[draw, minimum width=14mm, minimum height=7mm, fill=acc!8] (ppn) at (7.3,-0.1) {PPN}; % index arrows drop into the table tops \draw[->,acc] (l1.south) -- (t1.north); \draw[->,acc] (l2.south) -- (t2.north); % L1 entry holds the base address of the L2 table \draw[->] (t1e.east) -- (t2.west |- t1e.east); % L2 PTE -> PPN \draw[->] (t2e.east) -- (ppn.west); \end{tikzpicture} $$ 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\,\text{KB} / 8\,\text{B} = 512 = 2^9$ entries, so each level consumes **9 bits** of VPN. Four levels cover the $36$-bit VPN exactly: $$ \underbrace{9}_{\texttt{VPN1}} + \underbrace{9}_{\texttt{VPN2}} + \underbrace{9}_{\texttt{VPN3}} + \underbrace{9}_{\texttt{VPN4}} + \underbrace{12}_{\text{VPO}} = 48 \;\text{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. $$ % caption: The x86-64 four-level page-table walk. The 48-bit virtual address % caption: splits 9+9+9+9+12. CR3 holds the physical address of the level-1 % caption: table; each level's selected entry gives the base of the next table; % caption: the level-4 entry is the PTE, whose PPN joins the VPO to form the % caption: physical address. Each table is 512 entries of 8 bytes: one page. \begin{tikzpicture}[font=\footnotesize,>=stealth, f/.style={draw, minimum height=7mm, inner sep=1pt}, tb/.style={draw, minimum width=14mm, minimum height=20mm}, en/.style={draw, minimum width=11mm, minimum height=5mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} % address f\/ields (top row) \node[f, minimum width=14mm, anchor=west] (f1) at (0.6,3.2) {\texttt{VPN1}}; \node[f, minimum width=14mm, anchor=west] (f2) at (f1.east) {\texttt{VPN2}}; \node[f, minimum width=14mm, anchor=west] (f3) at (f2.east) {\texttt{VPN3}}; \node[f, minimum width=14mm, anchor=west] (f4) at (f3.east) {\texttt{VPN4}}; \node[f, minimum width=16mm, anchor=west] (fo) at (f4.east) {VPO}; \node[anchor=south, font=\scriptsize] at (f1.north) {9}; \node[anchor=south, font=\scriptsize] at (f2.north) {9}; \node[anchor=south, font=\scriptsize] at (f3.north) {9}; \node[anchor=south, font=\scriptsize] at (f4.north) {9}; \node[anchor=south, font=\scriptsize] at (fo.north) {12}; % tables (bottom row) \node[tb] (t1) at (1.5,0.6) {}; \node[tb] (t2) at (3.5,0.6) {}; \node[tb] (t3) at (5.5,0.6) {}; \node[tb] (t4) at (7.5,0.6) {}; \node[anchor=north, font=\scriptsize] at (1.5,-0.45) {level 1}; \node[anchor=north, font=\scriptsize] at (3.5,-0.45) {level 2}; \node[anchor=north, font=\scriptsize] at (5.5,-0.45) {level 3}; \node[anchor=north, font=\scriptsize] at (7.5,-0.45) {level 4}; % selected entries \node[en] (e1) at (1.5,0.9) {}; \node[en] (e2) at (3.5,0.9) {}; \node[en] (e3) at (5.5,0.9) {}; \node[en, fill=acc!8] (e4) at (7.5,0.9) {PTE}; % CR3 into level 1 \node[draw, minimum width=12mm, minimum height=6mm] (cr3) at (-0.7,0.9) {\texttt{CR3}}; \draw[->] (cr3.east) -- (t1.west); % index arrows from f\/ields into tables \draw[->,acc] (f1.south) -- (t1.north); \draw[->,acc] (f2.south) -- (t2.north); \draw[->,acc] (f3.south) -- (t3.north); \draw[->,acc] (f4.south) -- (t4.north); % entry -> next table \draw[->] (e1.east) -- (t2.west); \draw[->] (e2.east) -- (t3.west); \draw[->] (e3.east) -- (t4.west); % PTE -> PPN \node[draw, minimum width=12mm, minimum height=6mm, fill=acc!8] (ppn) at (9.4,0.9) {PPN}; \draw[->] (e4.east) -- (ppn.west); \node[anchor=north, font=\scriptsize] at (9.4,0.5) {+ VPO = PA}; \end{tikzpicture} $$ 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 $$ \texttt{VPN1} = \texttt{0x0AA},\quad \texttt{VPN2} = \texttt{0x155},\quad \texttt{VPN3} = \texttt{0x0AA},\quad \texttt{VPN4} = \texttt{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\,\text{KB} = 1\,\text{GB}$ of virtual space; one level-4 table maps $512 \times 4\,\text{KB} = 2\,\text{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: 1. The CPU emits a 48-bit virtual address; the MMU splits off the VPN. 2. 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. 3. 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. 4. 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](/computer-architecture/memory-hierarchy/storage-technologies-and-the-latency-gap). $$ % caption: The combined translation pipeline. The VPN tries the TLB; a hit yields % caption: the PPN. A TLB miss triggers a page-table walk (and a page fault if not % caption: resident), then fills the TLB. The resulting physical address goes to % caption: the cache, then to memory on a cache miss. \begin{tikzpicture}[font=\footnotesize,>=stealth, box/.style={draw, minimum width=18mm, minimum height=10mm, inner sep=3pt, align=center}, num/.style={draw, circle, fill=acc!8, inner sep=1pt, minimum size=4.5mm, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[box, fill=acc!8] (tlb) at (0,0) {TLB}; \node[box] (pt) at (0,-2.3) {page-table\\walk}; \node[box] (cache) at (4.2,0) {L1\\cac\/he}; \node[box] (mem) at (8.4,0) {main\\memory}; % VPN in \draw[->] ($(tlb.west)+(-1.2,0)$) -- (tlb.west) node[midway,above] {VPN}; % TLB hit -> cache (carries PA) \draw[->,acc] (tlb.east) -- (cache.west) node[midway,above] {PA}; \node[num] at (2.1,0.55) {1}; % TLB miss -> walk -> back to TLB \draw[->] (tlb.south) -- (pt.north) node[midway,right] {miss}; \node[num] at (-0.55,-1.15) {2}; \draw[->] (pt.east) -| ($(cache.south)+(0,0)$) node[pos=0.2,below] {f\/ill TLB, get PA}; % cache miss -> memory \draw[->] (cache.east) -- (mem.west) node[midway,above] {miss}; \node[num] at (6.3,0.55) {3}; \end{tikzpicture} $$ 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. $$ % caption: One load, end to end, with real values: VA 0x03D4 splits; the TLB hits % caption: in set 3 with tag 0x03 and supplies PPN 0x0D; the physical address % caption: 0x354 splits into cache fields CT 0x0D, CI 0x5, CO 0; the L1 cache % caption: hits. Two table-free, DRAM-free lookups serve the reference. \begin{tikzpicture}[font=\footnotesize,>=stealth, st/.style={draw, minimum width=23mm, minimum height=11mm, inner sep=2pt, align=center}] \definecolor{acc}{HTML}{2348F2} % row 1: VA -> split -> TLB -> PPN \node[st] (va) at (0,1.5) {VA \texttt{0x03D4}}; \node[st] (sp) at (3.1,1.5) {VPN \texttt{0x0F}\\VPO \texttt{0x14}}; \node[st, fill=acc!8] (tlb) at (6.2,1.5) {TLB set \texttt{3}\\tag \texttt{0x03}: hit}; \node[st] (ppn) at (9.3,1.5) {PPN \texttt{0x0D}}; \draw[->] (va.east) -- (sp.west); \draw[->] (sp.east) -- (tlb.west); \draw[->,acc] (tlb.east) -- (ppn.west); % row 2: PA -> cache split -> L1 hit -> data \node[st] (pa) at (0,-1.5) {PA \texttt{0x354}}; \node[st] (cs) at (3.1,-1.5) {CT \texttt{0x0D}\\CI \texttt{0x5}, CO \texttt{0}}; \node[st, fill=acc!8] (l1) at (6.2,-1.5) {L1 set \texttt{0x5}\\tag matc\/h: hit}; \node[st] (dat) at (9.3,-1.5) {data to CPU}; \draw[->] (pa.east) -- (cs.west); \draw[->] (cs.east) -- (l1.west); \draw[->,acc] (l1.east) -- (dat.west); % wrap: PPN + VPO -> PA \draw[->] (ppn.south) -- ($(ppn.south)+(0,-0.6)$) -| (pa.north); \node[font=\scriptsize, anchor=south] at (4.65,0.42) {PA = PPN with the VPO app\/ended}; \end{tikzpicture} $$ 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. $$ % caption: The overlap trick. The cache index (CI) and block offset (CO) of a % caption: Core-i7-style L1 (64 sets, 64-byte lines) occupy exactly the low 12 % caption: bits, which equal the VPO and need no translation. The cache reads its % caption: set while the TLB translates the VPN; only the tag comparison waits for % caption: the PPN. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} % VA row (top) \node[draw, minimum width=40mm, minimum height=8mm, inner sep=0pt, anchor=west] (vpn) at (0.4,2.6) {VPN (36 bits)}; \node[draw, fill=acc!8, minimum width=24mm, minimum height=8mm, inner sep=0pt, anchor=west] (vpo) at (vpn.east) {VPO (12 bits)}; \node[anchor=east] at (0.2,2.6) {VA}; % PA row (bottom), cache view \node[draw, minimum width=44mm, minimum height=8mm, inner sep=0pt, anchor=west] (ct) at (0.0,1.0) {CT (40 bits)}; \node[draw, fill=acc!8, minimum width=12mm, minimum height=8mm, inner sep=0pt, anchor=west] (ci) at (ct.east) {CI}; \node[draw, fill=acc!8, minimum width=12mm, minimum height=8mm, inner sep=0pt, anchor=west] (co) at (ci.east) {CO}; \node[anchor=east] at (-0.2,1.0) {PA}; % alignment of the low 12 bits \draw[dashed, acc] (4.4,0.55) -- (4.4,3.05); \draw[->,acc,thick] (5.6,2.2) -- (5.6,1.4) node[midway,right] {same bits}; % annotations \node[anchor=north, align=center, font=\scriptsize] at (5.6,0.5) {index the cac\/he now,\\before translation}; \node[anchor=north, align=center, font=\scriptsize] at (2.2,0.5) {tag compare waits\\for the PPN}; \end{tikzpicture} $$ 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 \;\text{sets} \times 64\,\text{B} = 4\,\text{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. > **Takeaway.** The **TLB** is a small set-associative cache of PTEs inside the > MMU: the VPN splits into **TLBT** and **TLBI**, a hit costs nothing, and a > miss costs a walk, tolerable only because hit rates exceed 99%. A **flat** > 48-bit table would be $2^{36} \times 8\,\text{B} = 512\,\text{GB}$ per > process; **multi-level tables** allocate only what is used, and x86-64 walks > **four levels** under a $9{+}9{+}9{+}9{+}12$ split starting at `CR3`. The full > path is **TLB, then walk, then cache, then memory**, with the L1 cache > overlapped against the TLB because its index and offset live in the > untranslated VPO, and **huge pages** stretching TLB reach when working sets > outgrow it. 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](/computer-architecture/exceptions-and-io/exceptional-control-flow), takes up that mechanism in full.