How Does a TLB Cache Virtual-to-Physical Translations?

A Translation Lookaside Buffer, or TLB, is a small, high-speed hardware cache inside a processor's memory management unit that stores recent virtual-to-physical memory address translations. When a program accesses memory, the processor checks the TLB first to see if the translation is already available. If the entry is present, the processor immediately obtains the physical address without reading the slower page tables stored in main memory. If the entry is missing, the hardware or operating system must perform a page table walk to find the mapping and then load it into the TLB for future accesses.

Virtual Memory and the Cost of Page Table Walks

Modern operating systems give each process its own virtual address space, which isolates programs from one another and simplifies memory allocation. Before the CPU can read or write data in RAM, it must translate each virtual address into a physical address.

Operating systems store these mappings in hierarchical page tables in main memory. On a 64-bit architecture with 4-level paging, a single memory access without caching would require four separate memory reads just to traverse the page table, followed by a fifth read for the actual data. Because main memory latency is orders of magnitude slower than CPU clock cycles, performing a full page table walk on every instruction fetch or data load would severely degrade performance.

Structure of a TLB Entry

To eliminate most page table walks, the TLB stores a compact table of recently used page translations. A virtual address of \(N\) bits is split into a Virtual Page Number (VPN) and a page offset:

\[\text{Virtual Address} = (\text{VPN}, \text{Offset})\]

For a standard \(4\text{ KiB}\) page, the offset is \(12\text{ bits}\) (\(2^{12} = 4096\text{ bytes}\)), and the remaining upper bits form the VPN. The offset remains unchanged during translation because it identifies the exact byte within the page.

Each TLB entry typically contains:

  • Tag (VPN): The virtual page number being matched.
  • Physical Frame Number (PFN): The corresponding physical page location in RAM.
  • Valid bit: Indicates whether the entry currently holds an active translation.
  • Protection and status bits: Permissions such as read, write, execute, user/supervisor mode, and dirty or accessed flags.
  • Address Space Identifier (ASID): An optional process tag that allows entries from multiple processes to coexist in the TLB without flushing on every context switch.

How a TLB Lookup Works

When the CPU generates a virtual address, the Memory Management Unit (MMU) extracts the VPN and searches the TLB in parallel using Content-Addressable Memory (CAM) or a set-associative lookup.

TLB Hit

If an entry matches the VPN, has its valid bit set, and passes the ASID and permission checks, a TLB hit occurs. The MMU combines the PFN from the TLB entry with the original page offset to form the physical address:

\[\text{Physical Address} = (\text{PFN}, \text{Offset})\]

This lookup typically completes in a single CPU cycle, allowing the processor to proceed directly to the L1 cache or main memory.

TLB Miss

If no matching entry is found, a TLB miss occurs. The system must resolve the translation through a page table walk:

  1. Hardware-managed TLB: On architectures like x86-64, a dedicated hardware page table walker reads the page table hierarchy starting from a base register (such as CR3), retrieves the PFN, and inserts the new translation into the TLB.
  2. Software-managed TLB: On some RISC architectures, a TLB miss triggers a trap to the operating system kernel, which walks the page tables in software and executes a privileged instruction to load the TLB entry.

If the TLB is full when inserting a new entry, a replacement policy—commonly Least Recently Used (LRU) or a pseudo-LRU approximation—evicts an older entry.

Multi-Level TLBs and Performance

Just like data caches, modern processors use a hierarchy of TLBs to balance speed and capacity:

  • L1 TLB: Very small (often 32 to 128 entries) and split into separate Instruction TLB (iTLB) and Data TLB (dTLB) structures for single-cycle access.
  • L2 TLB: Larger (often 512 to 2048+ entries) and unified, catching misses from the L1 TLBs before triggering a full page table walk.

Because programs exhibit spatial and temporal locality, a single TLB entry covering a \(4\text{ KiB}\) page (or a \(2\text{ MiB}\) / \(1\text{ GiB}\) huge page) can serve thousands of consecutive memory accesses, keeping TLB hit rates above \(99\%\) in typical workloads.