TLBs and Address Translation

The multi-level page table of Chapter 41 costs three to five DRAM accesses per translation. At a 3 GHz clock with 100 ns DRAM, a single translation through the walker costs about 1000 cycles. If every memory access paid this cost, the machine would spend almost all of its time translating addresses rather than touching data. The architecture solves the problem the same way it solves every other memory-latency problem: with a small, fast cache. The translation lookaside buffer or TLB, sits in parallel with the L1 cache lookup and supplies the physical address in time for the cache tag check to complete.

A representative microarchitecture has a 64-entry L1 data TLB delivered in one cycle, a 1536-entry L2 unified TLB delivered in seven to ten cycles, and the page walker visible only on L2 TLB misses. At a TLB hit rate above 99.9 percent for the L1 and above 99 percent for the L2, the average translation cost is well below one cycle. Achieving those hit rates without losing the multi-level mapping flexibility of the page table is the engineering problem this chapter develops.

The chapter starts with the structural choices for the TLB itself, walks through hardware versus software miss handling, develops the ASID and PCID mechanism that lets TLBs survive context switches, covers the TLB shootdown protocol required in multiprocessors, and closes with nested page tables, the mechanism that lets a hypervisor host guest virtual machines without a complete software translation layer.

01.TLB Organization

A TLB is a content-addressable cache of recent translations. Each entry holds a virtual page number, a physical page number, the access permissions from the leaf PTE, and an ASID or PCID tag. A lookup presents a virtual address and an ASID and receives either a matching physical address (a hit) or a miss signal.

The most aggressive design point is a small fully associative TLB. A 64-entry data TLB compares the incoming VPN against all 64 stored VPNs in parallel using content-addressable memory. This delivers a one-cycle lookup at modest power, but scaling past about 128 entries becomes infeasible because the comparator count and the match-line search energy grow linearly with entry count, and the resulting search delay soon exceeds the one-cycle budget. The Intel Skylake L1 data TLB is fully associative with 64 entries. The ARM Cortex-A77 L1 data TLB is fully associative with 48 entries. The L1 data TLB on a SiFive U74 RISC-V core is fully associative with 40 entries.

The second tier is a set-associative TLB, usually 4-way or 8-way, with a few hundred to a few thousand total entries. The set is selected by bits of the virtual page number, identical to the cache indexing of Chapter 37. The L2 unified TLB on Skylake is 12-way with 1536 entries. The Cortex-A77 has 1280 entries with 5-way associativity. The U74’s L2 TLB has 64 entries with 8-way associativity. The L2 TLB is structurally larger than the L1 cache of translations alone would need to be, because it backs up an L1 TLB that already handles the common case.

Huge pages introduce a wrinkle. A 2 MiB huge page has a different VPN width than a 4 KiB page (9 bits less), and a TLB optimized for 4 KiB entries cannot simply store huge-page entries in the same slots. Three approaches appear in real designs.

Separate huge-page TLB. Intel Skylake has a 32-entry fully-associative DTLB dedicated to 2 MiB pages and an 8-entry fully-associative DTLB dedicated to 1 GiB pages, parallel to the 64-entry 4 KiB DTLB. This is clean but spends area on TLB structures that may be unused.

Page-size-aware set-associative TLB. ARM and some recent Intel designs use a single TLB structure that can hold entries of any supported size, with the set-indexing bits selected based on the smallest supported page. Larger entries are then constrained to a subset of the sets, and a portion of the TLB capacity is effectively wasted when the workload uses only one size.

Skewed associativity. A research direction that uses different hash functions for entries of different sizes, allowing the TLB to fit multiple page sizes without per-size partitioning. Some recent server cores adopt variants of this scheme.

The L1 TLB lookup is on the critical path of the L1 cache hit. A common technique to hide this latency is to perform the TLB lookup in parallel with the L1 cache way lookup, then use the physical address from the TLB to select the matching way. This requires a virtually-indexed, physically-tagged cache. The L1 cache must be small enough that the index bits fit within the page offset, which is why L1 caches stalled at 32 KiB for nearly two decades despite process scaling allowing larger structures.

02.Hardware vs. Software Miss Handling

When the L2 TLB misses, the hardware needs to perform a page-table walk. Two designs have appeared.

Hardware walker. RISC-V, ARMv8, and x86-64 all use a dedicated state machine that walks the page table on a TLB miss without invoking software. The walker issues physical memory references that go through the data cache hierarchy (sometimes through a dedicated walk cache that holds only intermediate-level PTEs), updates the A and D bits when the implementation supports hardware updates, and finally installs the resulting translation in the L1 TLB. The walker is invisible to software except in the performance counter that reports its activity. A hardware walk on a 4-level page table costs roughly 4 DRAM accesses when the walk cache misses, or 1 to 2 DRAM accesses when the walk cache hits the upper levels.

Software handler. MIPS and earlier SPARC took the opposite approach. A TLB miss raised a special exception that vectored to a short kernel routine. The routine consulted the operating system’s own page table representation (which could be any structure the OS chose, not necessarily a multi-level radix tree), formed a TLB entry, and used a special instruction to install it. The advantage is flexibility: the OS chose the page table format and could optimize for sparse address spaces, large pages, or special hardware. The disadvantage is cost: the exception entry and exit alone cost dozens of cycles, plus the cache misses on the OS’s page table data.

The two designs converged on hardware walking by the mid-1990s. The benchmark workloads of the era stressed TLB miss rate enough that the dozen-cycle exception overhead became the dominant cost. MIPS R10000 and later parts added hardware walkers as an option. Modern RISC-V leaves the choice in the specification (a Linux-class rv64gc core typically has a hardware walker, but a small embedded part may use software handling). ARMv8 and x86-64 require hardware walkers.

03.ASIDs, PCIDs, and Context Switches

A context switch from process A to process B changes the page-table root. Without further mechanism, every cached TLB entry from process A would now point at the wrong physical page when process B issues a load, because process B’s PTE for the same virtual address maps to a different frame. The legacy solution was to flush the entire TLB on every context switch, which made each switch cost hundreds of cycles of subsequent TLB misses as process B refilled the TLB from scratch.

The address space identifier mechanism avoids the flush. Each TLB entry is tagged with the ASID of the process that created it, and a TLB lookup matches only when both the virtual address and the ASID agree with the current process. After a context switch, process A’s entries remain in the TLB but are invisible to process B because the ASID does not match. When the scheduler later returns to process A, those entries become visible again.

RISC-V satp has a 16-bit ASID field [1], allowing up to 65,536 concurrent processes before the OS must recycle ASIDs. ARMv8 TTBR_EL1 has the same 16-bit field [2]. Intel and AMD use process-context identifiers on x86-64 [3][4]. The original PCID width was 12 bits (4096 PCIDs). The width has not grown since, but INVPCID gave software finer control over which PCIDs are invalidated.

The ASID width matters because the operating system has to manage the namespace. When the OS runs out of fresh ASIDs (a server with thousands of processes can run through 16-bit ASIDs in days), it has to invalidate all entries for some recycled ASID before reusing it for a new process. This is typically done as a global TLB flush once per ASID rollover, amortizing the cost across many context switches.

A subtle case is the kernel/user split. Most operating systems use the high half of the virtual address space for the kernel and the low half for user processes. The kernel pages are present in every process’s page table (so a syscall can transfer control to kernel code without changing CR3), and the kernel pages have the same physical mapping in every process. The G (global) bit in the PTE tells the TLB to ignore the ASID/PCID on lookups for that entry, so kernel TLB entries survive both context switches and ASID rollovers.

This optimization was undermined by the Meltdown vulnerability of 2017, which used speculative execution to leak kernel pages from user mode. The kernel page-table isolation (KPTI) mitigation strips kernel pages from each process’s page table and uses a separate kernel page table that is swapped in on syscall entry. KPTI doubles TLB pressure on kernel code paths and costs roughly 5 percent on syscall-heavy workloads. Newer hardware (Intel since the post-Meltdown microcode era, AMD Zen 2 and later, ARMv8.5-A) restores the kernel mappings into the user page table once the speculative bypass has been closed, allowing KPTI to be disabled without security loss.

04.TLB Shootdown

In a multiprocessor, every core has its own TLB. When one core unmaps a page (because the operating system is reclaiming it for swap or freeing it on process exit), the local TLB must be invalidated. Other cores may also have cached translations for the same virtual address, and those translations are now stale. The operating system must broadcast an invalidation to every core that might have the translation cached. This protocol is called the TLB shootdown.

A shootdown proceeds in four steps.

1. The initiating core updates the page table in DRAM to mark the entry invalid.

2. The initiating core executes a local TLB invalidation instruction (sfence.vma on RISC-V, TLBI on ARMv8, INVLPG on x86) to drop the entry from its own TLB.

3. The initiating core sends an inter-processor interrupt (IPI) to every other core that might be running the affected process.

4. Each remote core handles the IPI by invalidating the specified translation in its own TLB, then acknowledges the IPI. The initiating core spins waiting for all acknowledgments before proceeding.

The cost of a shootdown grows with core count and with the per-IPI latency. On a 16-core server, an IPI costs roughly 1 microsecond end to end, so a single shootdown costs about 16 microseconds of synchronous waiting. On a 96-core server, a shootdown can cost tens of microseconds. Workloads that unmap pages frequently (short-lived allocations with munmap, transparent huge page splits, memory ballooning in virtualization) can spend a large fraction of their runtime in shootdowns.

Optimizations target the broadcast. Some architectures allow broadcast TLB invalidation without IPIs. ARMv8 TLBI instructions implicitly broadcast to all cores in the inner-shareable domain, with the cores performing the invalidation in hardware and the initiating core issuing DSB to wait for completion. RISC-V Sv-mode implementations now generally include this in the privileged spec update. Intel and AMD x86 use IPIs. AMD’s newer parts have added hardware broadcast support behind a feature flag.

05.Nested Page Tables and Virtualization

Virtualization adds a second layer of address translation. A guest operating system inside a virtual machine believes it controls the physical memory of the machine, but in reality its physical addresses (called guest physical addresses) are just another level of virtual address that the hypervisor translates into actual machine memory (called host physical addresses or machine addresses).

Without hardware support, the hypervisor must shadow the guest’s page tables: every time the guest writes a new PTE, the hypervisor traps, composes the guest PTE with the host’s mapping, and installs the composed translation in a shadow page table that the hardware actually uses. This is functionally correct but slow, because every guest page table update incurs a hypervisor trap.

Hardware-assisted virtualization solves this with nested page tables. Each architecture has its own name for the same mechanism: Extended Page Tables (EPT) on Intel [3], Nested Page Tables (NPT) on AMD [4], and Stage 2 translation on ARMv8 [2]. RISC-V uses the H-extension to provide the same functionality [1].

The structure is two page tables walked in series. The guest’s page table (called Stage 1 on ARM, the guest page table on Intel/AMD/RISC-V) translates guest virtual to guest physical. The host’s nested page table (Stage 2, EPT, NPT, or hypervisor page table) translates guest physical to host physical. A translation that misses the TLB now requires walking both tables.

A 4-level guest page table walk in the nested case is not 4 DRAM accesses but rather $4 \times 5 + 4 = 24$ DRAM accesses in the worst case. Here is why. Each of the four guest PTEs the walker reads lives in guest physical memory, which itself must be translated to host physical through the nested page table. Each guest-PTE translation requires a 4-level nested walk, plus the final guest physical address itself requires a 4-level nested walk. That gives $4 \times 5 + 4 = 24$ accesses when both walks are 4-level, because each guest PTE fetch costs four nested accesses plus the fetch of the guest PTE itself, and the final guest physical address costs four more. If the nested table is 5-level the count rises to $4 \times 6 + 5 = 29$.

where $L_{\text{guest}}$ and $L_{\text{host}}$ are the page-table depths. For $L_{\text{guest}} = L_{\text{host}} = 4$, this gives 24 accesses. The nested walker amortizes most of this cost through a multi-level nested walk cache that caches intermediate PTEs of the nested page table, so the realistic cost is more like 6 to 8 DRAM accesses, but the worst case remains alarming.

The cost of nested translation is called the virtualization tax. A workload running natively at 100 percent of its peak runs in a virtual machine at roughly 95 to 99 percent. The 1 to 5 percent gap is dominated by the nested walks when the workload’s working set spills the L2 TLB. Operating systems running in virtual machines can recover most of the gap by using larger guest pages (2 MiB or 1 GiB), which cuts the depth of the guest walk, and by ensuring guest physical memory is backed by 2 MiB or 1 GiB host pages, which cuts the depth of the nested walk.

06.Performance Monitoring and Tuning

Real-world TLB performance tuning starts with measurement. Every modern CPU exposes performance counters for TLB misses at each level, walk-cache hits, walker cycles, and (on virtualized hardware) nested-walk cycles. The perf tool on Linux can report these directly.

Measuring TLB miss behavior with perf on Linux.

The most common pathologies are easy to diagnose. A TLB miss rate above 1 percent of memory references typically indicates a working set that exceeds the L2 TLB reach. The fix is usually to enable huge pages for the hot region (via madvise(MADV_HUGEPAGE) or by allocating from a huge-page pool), which extends TLB reach by a factor of 512 per page-size step.

Long latency tails on memory references in a virtualized workload often indicate nested walks that miss the nested walk cache. The fix is to back the guest physical address space with host huge pages, which shortens the nested walk.

A workload whose TLB miss rate spikes after each context switch indicates an OS that is flushing the TLB rather than relying on ASIDs. This was common pre-2017 and should be fixed by enabling PCID support and ensuring the OS distribution has the relevant kernel patches.

07.Worked Examples

08.Exercises

References

1. [1]Waterman, Andrew and Asanovi\'c (2024). “The RISC-V.”
2. [2](2024). “ARM.”
3. [3](2024). “Intel.”
4. [4](2024). “AMD64.”