Translation Lookaside Buffer

A Translation Lookaside Buffer is a small, fast, associative hardware cache built into the memory management unit that stores recent (virtual page number, physical frame number) pairs, so the CPU can translate an address without walking the full page table in memory. "Associative" here means the TLB is searched by content — you present a virtual page number and the hardware checks, in parallel across all entries, whether any entry matches — rather than by index, the way a normal RAM array works. This parallel, content-addressable search is what makes TLB lookups fast: on the order of a single clock cycle or a few cycles, versus one or more full memory accesses for a page-table walk. Precisely, the TLB stores a table of entries, each holding at minimum: a virtual page number (VPN) tag, the corresponding physical frame number (PFN), and protection/status bits (valid, dirty, read/write/execute permissions). Many TLBs also store an ASID (Address Space Identifier), a small tag identifying which process's address space the entry belongs to, so that entries from different processes can coexist without collision. Because the TLB only has room for a few dozen to a few thousand entries (typical sizes range from 32 to a few thousand, split between separate instruction-TLB and data-TLB structures on modern chips), it functions exactly like a small, highly specialized cache memory, subject to the same hit/miss vocabulary and the same locality arguments that justify ordinary CPU caches. The key correctness property the TLB must satisfy is coherence with the page table: at every instant, if a TLB entry claims VPN p maps to PFN f, that mapping must currently be valid according to the page table (or the entry must be invalidated). This single invariant is why every operation that changes a page table entry — a page fault handler installing a new mapping, the OS revoking a mapping, or a context switch changing which page table is "current" — must also touch the TLB, either by invalidating the stale entry or by tagging entries so stale ones simply cannot match.

On every memory reference, the CPU (specifically the MMU) performs address translation using the TLB as the first stop, falling back to the page table only when necessary. ``` function TRANSLATE(virtual_address): vpn, offset = SPLIT(virtual_address) // page number, in-page offset asid = CURRENT_ASID() // active process tag, if used entry = TLB_LOOKUP(vpn, asid) if entry is not None and entry.valid: // ---- TLB HIT ---- if not PERMISSION_OK(entry, access_type): raise PROTECTION_FAULT physical_address = COMBINE(entry.pfn, offset) return physical_address // fast path: ~1 cycle // ---- TLB MISS ---- pte = WALK_PAGE_TABLE(vpn) // one or more memory accesses if pte is None or not pte.present: raise PAGE_FAULT // handled by the OS (demand paging) if not PERMISSION_OK(pte, access_type): raise PROTECTION_FAULT TLB_INSERT(vpn, pte.pfn, asid, pte.protection_bits) // evict an entry if TLB full physical_address = COMBINE(pte.pfn, offset) return physical_address ``` ``` function TLB_LOOKUP(vpn, asid): // Conceptually parallel: every TLB entry compares its tag simultaneously. for entry in TLB: // hardware does this in parallel, O(1) time if entry.valid and entry.vpn == vpn and (entry.asid == asid or entry.global_bit): return entry return None ``` ``` function TLB_INSERT(vpn, pfn, asid, prot): if TLB has a free slot: slot = free slot else: slot = SELECT_VICTIM() // LRU, pseudo-LRU, round-robin, or random TLB[slot] = { vpn, pfn, asid, prot, valid = true } ``` Two crucial events beyond the ordinary hit/miss path enforce the coherence invariant: ``` // Whenever the OS changes a page table entry (e.g., unmaps a page, // changes protection, or swaps a page out), it must invalidate stale entries. function ON_PAGE_TABLE_UPDATE(vpn, asid): TLB_INVALIDATE(vpn, asid) // single-entry shootdown, cheap // On a context switch to a new process: function ON_CONTEXT_SWITCH(new_asid): if TLB supports ASIDs: CURRENT_ASID = new_asid // old entries remain, tagged, harmless else: TLB_FLUSH_ALL() // must invalidate everything: O(TLB size) ``` Walk through why each branch is necessary. On a hit, the whole point is to avoid touching the page table — that's where the speed comes from. On a miss, the hardware or OS must consult the actual page table (this is the "page-table walk," and its cost depends on how many levels the table has — the very issue that motivates Multilevel Page Tables). If the page table itself says the page isn't resident in physical memory at all, that's not a TLB problem — it's a page fault, resolved by the operating system's page-fault handler, which is the doorway into Demand Paging. Only after a valid, permitted mapping is found does the hardware install it into the TLB for next time. The context-switch case is where the TLB's biggest subtlety lives. Suppose the TLB has no ASID tags. Process A's page 3 maps to frame 40; the OS switches to process B, whose page 3 maps to frame 12. If the TLB still holds the stale entry "page 3 → frame 40" from A, process B would silently read A's memory — a catastrophic correctness bug, not just a performance one. So without ASIDs, every context switch must flush the entire TLB, forcing every one of B's first memory accesses to miss and re-walk the page table, even though B may resume immediately after a very short quantum and reuse much of what was already cached. With ASIDs, each TLB entry additionally stores the owning process's tag; a lookup only matches when both the VPN and the ASID match (or a "global" bit marks an entry as shared, e.g., kernel mappings visible to all processes). This lets the OS simply switch the active ASID register on a context switch, leaving old entries harmlessly present but unreachable to the wrong process, dramatically reducing the number of TLB misses paid immediately after a switch.

Time complexity. A TLB lookup is architecturally O(1): because the TLB is small and fully (or set-) associative, the hardware compares the requested VPN against all resident tags simultaneously, in a single clock cycle (or a small constant number of cycles for pipelined comparison across ways in a set-associative design). This is fundamentally different from searching an ordinary array, which would take O(n) time for n entries; the TLB achieves O(1) by paying for parallel comparator hardware per entry, which is exactly why TLBs must stay small — the comparator hardware does not scale to thousands of entries cheaply. A TLB miss costs the time of a full page-table walk. For a page table with L levels (see Multilevel Page Tables), a hardware-managed TLB miss costs up to L sequential memory accesses (one per level) plus the eventual data/instruction access itself, so miss cost is O(L) memory accesses, i.e., a small constant determined by the paging structure (commonly 2–5 for modern 64-bit systems). Software-managed TLBs (as in MIPS or SPARC designs) instead trap to an OS-written miss handler, whose cost includes trap overhead plus however the OS chooses to look up the mapping.

Effective Access Time (EAT). Let: ``` h = TLB hit ratio (fraction of accesses that hit), 0 ≤ h ≤ 1 t = time for a single memory access (e.g., in nanoseconds) ε = TLB lookup time (often folded into t, or added separately) ``` On a hit, the total time is one TLB lookup plus one memory access: `ε + t`. On a miss, the total time is the TLB lookup, plus the page-table walk (say it costs `t` per level for an L-level table, i.e. `L·t`), plus the final memory access: `ε + L·t + t`. The effective access time is the probability-weighted average: ``` EAT = h · (ε + t) + (1 − h) · (ε + L·t + t) ``` For the classic single-level textbook case (page table itself is a single array in memory, one extra access), this reduces to the familiar form: ``` EAT = h · (ε + t) + (1 − h) · (ε + 2t) ``` since a miss costs one memory access to fetch the page table entry, plus one more to fetch the actual data. This formula is the quantitative reason TLB hit ratio matters so much: with `t = 100 ns` and `h = 0.99`, EAT is barely above `t`; with `h = 0.80`, EAT climbs noticeably, because every miss doubles (or worse) the cost of that access.

Correctness argument. The correctness of the whole scheme rests on one invariant, stated precisely: > TLB Coherence Invariant. At any time a memory access is issued, for every valid TLB entry `(vpn, pfn, asid)` matching the current `(vpn, asid)`, the page table for that address space currently maps `vpn → pfn` with at least the permissions recorded in the entry. The algorithm preserves this invariant by construction:

• Insertion only happens immediately after a successful, permitted page-table walk (see `TLB_INSERT` above), so a freshly inserted entry is trivially consistent with the page table at that instant.
• Any operation that would break consistency — unmapping a page, changing its protection, or swapping it out — must explicitly invalidate the corresponding TLB entry (`TLB_INVALIDATE`, sometimes called a TLB shootdown on multiprocessors, because every core's TLB must be individually notified). If the OS forgets this step, a stale TLB entry could let a process access memory that has since been reassigned — a security and correctness disaster, not merely a slowdown.
• Context switches preserve the invariant either by flushing everything (trivially safe, since an empty TLB vacuously satisfies the invariant) or, with ASIDs, by ensuring lookups can never match an entry tagged for a different address space, so stale entries from other processes are simply unreachable rather than incorrect.

Tradeoffs. The TLB buys enormous average-case speed at the cost of: (1) extra hardware (parallel comparators, ASID tag storage), (2) the operational burden of keeping it coherent (shootdowns on multiprocessors are genuinely expensive, requiring inter-processor interrupts), and (3) a worst case that is no better, and sometimes slightly worse (extra lookup latency `ε`), than having no TLB at all when the hit ratio is poor — for instance, workloads that stride through memory far larger than the TLB's reach will thrash it, a phenomenon architects call TLB reach limitations, which is one motivation for supporting large/huge pages.

Consider a system with: ``` Memory access time t = 100 ns TLB lookup time ε = 20 ns (added on both hit and miss) Page table levels L = 1 (single flat page table, classic case) ```

Step 1 — compute EAT at several hit ratios, using `EAT = h·(ε + t) + (1 − h)·(ε + 2t)`:

This table makes the payoff concrete: a realistic hit ratio of 99% keeps effective access time only 21% above the raw memory speed, while a pathologically bad hit ratio (an unrealistic 0%, included for contrast) more than doubles access time. Real hit ratios in practice are typically 95–99.9%, which is exactly why the TLB is treated as "nearly free" in most performance discussions despite doing real work on every access.

Step 2 — trace a concrete address translation with ASIDs, using a tiny TLB with 4 entries and 4 KB pages (offset = 12 bits): Suppose Process A (ASID = 1) is running, and its TLB (shared physical structure, tagged) currently holds: ``` Slot 0: VPN 2, ASID 1 → PFN 40 valid Slot 1: VPN 5, ASID 1 → PFN 12 valid Slot 2: VPN 2, ASID 2 → PFN 77 valid (stale from process B, harmless) Slot 3: (empty) ``` Process A issues a load from virtual address `0x2ABC` (VPN = `0x2` = 2, offset = `0xABC`). 1. `TLB_LOOKUP(vpn=2, asid=1)` scans all 4 slots in parallel. 2. Slot 0 matches: `vpn == 2` and `asid == 1`. Slot 2 also has `vpn == 2` but `asid == 2` — it does not match, correctly ignored. 3. Hit. Physical address = `PFN 40` combined with offset `0xABC` → `0x28ABC`. Cost: `ε + t = 120 ns`. No page-table walk needed. Now the OS context-switches to Process B (ASID = 2), which issues a load from virtual address `0x2FFF` (VPN = 2, offset `0xFFF`). 1. `CURRENT_ASID` becomes 2 (no flush, because this TLB supports ASIDs). 2. `TLB_LOOKUP(vpn=2, asid=2)` scans all slots: slot 2 matches (`vpn=2, asid=2 → PFN 77`). 3. Hit, even immediately after the switch — this is the entire benefit of ASIDs. Physical address = `PFN 77` + offset `0xFFF`. Cost: `120 ns`, not the 220+ ns (plus flush overhead) it would have cost with a flush-on-switch design. If instead this hardware had no ASID support, step 1 above would have required `TLB_FLUSH_ALL()` on the switch, so Process B's very first several memory accesses would all be forced misses regardless of whether the data happened to already be cached — a direct, measurable performance cost paid purely because the hardware cannot distinguish "whose" translation an entry belongs to.

The TLB emerged directly out of the practical demands of building the first paged virtual memory systems, where researchers quickly discovered that a page table lookup on every memory reference was unacceptably slow without a hardware cache in front of it.

Every general-purpose operating system running on paged hardware — Linux, Windows, macOS/xnu, the BSDs — relies on the TLB as a silent, mandatory partner to its page-table code; kernel developers write explicit TLB-invalidation (`INVLPG`, ARM `TLBI`, etc.) calls at every point where page tables change. Hypervisors managing virtual machines must handle nested translation (guest virtual → guest physical → host physical), often supported by hardware features like tagged TLBs for virtual machine IDs, directly extending the ASID idea. Database systems and high-performance computing workloads that touch huge memory footprints are tuned around TLB reach, motivating the widespread use of "huge pages" (2 MB or 1 GB pages instead of 4 KB) specifically to make each TLB entry cover far more memory, reducing miss rates for large working sets. Real-time operating systems must account for worst-case TLB miss latency in their schedulability analysis, since an unlucky miss can blow a deadline. And the entire discipline of container and process isolation depends on the TLB-coherence invariant holding perfectly under concurrent multicore access — any bug there is a security vulnerability, not just a slowdown.

Ask the tutor: How would supporting variable page sizes (e.g., mixing 4 KB and 2 MB huge pages) change the design of the TLB's lookup and replacement logic?