The TLB and Memory Protection

A Translation Lookaside Buffer is a small associative cache that maps virtual page numbers (VPNs) to physical frame numbers (PFNs), storing the most recently used translations so the CPU can avoid repeatedly consulting the full page table in memory. Structurally, it is just another cache: entries have tags (the VPN, sometimes combined with an address-space identifier), data (the PFN plus flags), and a replacement policy, and it can be direct-mapped, set-associative, or fully associative exactly as described for ordinary Set-Associative Caches. The key architectural difference is what it caches — not data bytes, but the mapping metadata that every other memory access depends on. Because address translation must happen before (or in parallel with) every cache access, the TLB sits at the very front of the memory pipeline. Each TLB entry stores not just the PFN but a permission field: bits indicating whether the page is readable, writable, or executable, whether user-mode code may access it at all (or only supervisor/kernel mode), a valid bit marking whether the entry is currently meaningful, an accessed bit set on any reference (used by the OS for page-replacement heuristics), and a dirty bit set on any write (telling the OS the page must be written back if evicted). These bits are checked by hardware in the same cycle as the translation lookup, so enforcing protection costs no extra time — the check is free because the lookup was already happening. This dual role — cache and guard — is what distinguishes the TLB conceptually from a plain data cache. A data cache miss just costs time. A TLB miss can cost time or trigger a fault: either "this translation isn't cached, go fetch it" (a soft miss, resolved by walking the page table) or "this access isn't allowed, ever" (a protection violation, resolved by trapping to the operating system, typically terminating or signaling the offending process). The TLB is therefore the hardware chokepoint through which the operating system's page-table-based protection policy is actually enforced on every single memory reference, cheaply enough to be unconditional rather than optional.

Structure of a lookup. A virtual address is split into a virtual page number (high-order bits) and a page offset (low-order bits, unchanged by translation). The TLB is indexed by some bits of the VPN (for a set-associative TLB) or searched fully associatively across all entries (common for TLBs, since they are small — typically 32 to 1536 entries per level). Each way of the indexed set is checked in parallel: does its stored VPN tag match, and is the entry valid? If exactly one way matches, that entry's PFN is concatenated with the unchanged page offset to form the physical address, and the entry's permission bits are checked against the type of access being performed (read, write, execute) and the current privilege level (user vs. supervisor).

On a TLB hit with valid permissions: the physical address is produced immediately (often in the same cycle or with one extra pipeline stage) and handed to the cache hierarchy as normal.

On a TLB hit with a permission violation: the memory access is squashed and a protection fault (general protection fault, segmentation fault, etc.) is raised, trapping into the OS.

On a TLB miss: either the hardware itself walks the multi-level page table (as in x86, which has a hardware page-table walker), or a trap is delivered to software, which walks the page table itself (as in classic MIPS and many RISC designs, using a "TLB miss handler"). If the walk finds a valid mapping with acceptable permissions, a new TLB entry is installed (possibly evicting another one) and the original instruction is retried. If the walk finds no valid page-table entry, or the page is marked "not present" because it was swapped out, a page fault is raised instead — this is a different, heavier-weight event that may involve disk I/O. ```pseudocode function translate(virtual_address, access_type, mode): vpn, offset = split(virtual_address)

# Step 1: TLB lookup entry = TLB.lookup(vpn, current_ASID) if entry is not None and entry.valid:

# Step 2: permission check (happens in parallel with lookup) if not permission_ok(entry, access_type, mode): raise ProtectionFault(virtual_address, access_type) entry.accessed = true if access_type == WRITE: entry.dirty = true return combine(entry.pfn, offset) # TLB HIT

# Step 3: TLB miss -> walk page table pte = page_table_walk(vpn, current_process) if pte is None or not pte.present: raise PageFault(virtual_address, access_type) # not mapped / swapped out if not permission_ok(pte, access_type, mode): raise ProtectionFault(virtual_address, access_type)

# Step 4: install new translation, evicting if necessary TLB.insert(vpn, current_ASID, pte.pfn, pte.permissions) return combine(pte.pfn, offset) # TLB MISS, now resolved

function permission_ok(entry, access_type, mode): if mode == USER and entry.supervisor_only: return false if access_type == WRITE and not entry.writable: return false if access_type == EXEC and not entry.executable: return false return true

function on_context_switch(new_process): if hardware_supports_ASID: current_ASID = new_process.ASID # entries auto-disambiguated, no flush else: TLB.flush_all() # coarse: safe but expensive current_page_table_base = new_process.page_table_root ``` The `on_context_switch` step is essential: virtual addresses are only meaningful relative to a particular process's page table. Without ASID tagging, VPN 0x400 in process A and VPN 0x400 in process B are unrelated, but a naive TLB would confuse them and let process B read a stale translation belonging to process A — a serious isolation bug, not just a performance one. Systems either tag every TLB entry with an ASID (so stale entries from other processes are simply ignored by the lookup, no flush needed) or flush the entire TLB on every switch (correct but costly, since the next several thousand memory accesses will all miss).

Time complexity of a lookup. A TLB lookup is $O(1)$ with respect to the number of pages in the address space — it costs a fixed number of tag comparisons (equal to the associativity, typically 4–16 ways checked in parallel), regardless of how large the process's virtual address space is. This is the entire point: without a TLB, translation cost grows with the depth of the page-table hierarchy (a 4-level x86-64 page table costs up to 4 sequential memory accesses per translation, i.e. $O(\log_{2^k} N)$ in the number of pages $N$ for a $k$-bit-per-level radix tree). The TLB collapses that to $O(1)$ for the common case.

Effective access time. Let $h$ be the TLB hit rate, $t_{tlb}$ the TLB lookup time, and $t_{walk}$ the page-table-walk time (which itself includes further memory-hierarchy accesses, since the page table lives in DRAM but its own entries may be cached). Then: ``` EAT_translation = h · t_tlb + (1 − h) · (t_tlb + t_walk) = t_tlb + (1 − h) · t_walk ``` Because $t_{walk}$ is many times larger than $t_{tlb}$ (a walk touches DRAM two to five times; a TLB hit is typically 0.5–1 cycle), even a small miss rate matters. With a 99.5% hit rate, a 4-level walk costing ~100ns per access, and a TLB hit costing ~1ns, the effective translation time is roughly: ``` 1ns + 0.005 × (4 × 100ns) = 1ns + 2ns = 3ns ``` versus 1ns for a pure hit — a 3× slowdown from just a 0.5% miss rate, illustrating why real TLBs are designed for hit rates well above 99% (multi-level TLBs, larger reach via huge pages, and prefetching are the standard countermeasures). This composes multiplicatively with the data-cache hierarchy: a memory access is only as fast as translation and the cache lookup that follows it, so both must be optimized, and a TLB miss on a load stalls the whole pipeline exactly like a cache miss would, just with a different penalty source.

Correctness argument. The TLB's correctness rests on one invariant that must hold at every instant during execution: > TLB Coherence Invariant. At any point in time, for any (VPN, ASID) pair with a valid TLB entry, that entry's (PFN, permissions) must equal what an immediate, from-scratch page-table walk for that (VPN, ASID) would currently produce. This invariant can be violated in exactly three ways, each of which the architecture must guard against: 1. Stale entries across address spaces. If process B's page table maps VPN 0x400 differently than process A's did, a leftover TLB entry from A must not be visible during B's execution. This is guaranteed either by tagging entries with an ASID (so the lookup key includes ASID, and B's lookups simply never match A's entries) or by flushing the TLB on every context switch (so no entries persist across a switch at all). 2. Stale entries after the OS changes a mapping. If the OS unmaps a page, changes its permissions, or reassigns its physical frame (e.g., during paging, `mprotect`, or copy-on-write), any existing TLB entry for that page is now wrong. Architectures require the OS to explicitly invalidate the affected entry (`invlpg` on x86, `tlbi` on ARM) as part of updating the page table; forgetting this step is a classic OS bug that produces access to a stale physical frame. 3. Multi-core staleness. On a multiprocessor, one core updating a shared page table does not automatically invalidate the corresponding entries cached in other cores' TLBs. This requires a TLB shootdown: the updating core sends an inter-processor interrupt asking every other core to invalidate the relevant entry before the update is considered complete, and it must wait for acknowledgments before proceeding — otherwise another core could keep using a mapping that has since been revoked, a real cross-core isolation hole. Given the invariant holds, the whole scheme is transparent: a program computing with virtual addresses behaves exactly as if translation happened by walking the full page table on every access — the TLB only changes when the answer is computed, never what the answer is. Protection correctness follows the same logic: the permission bits cached in the TLB entry are copied verbatim from the page-table entry at fill time, so a permission check against the TLB entry is equivalent to a permission check against the authoritative page table, as long as the coherence invariant holds.

Tradeoffs. Higher associativity and more entries improve hit rate but cost silicon area, power, and lookup latency (fully associative search over many entries is expensive, which is why large TLBs are usually set-associative rather than fully associative). ASID tagging avoids flush overhead but requires extra tag bits per entry and a limited-width ASID namespace (reused ASIDs require careful invalidation). Software-managed TLB misses (MIPS-style) give the OS flexibility (custom page-table formats, easier huge-page support) at the cost of a slower miss handler; hardware page-table walkers (x86-style) are faster on miss but fix the page-table format in the ISA.

Consider a system with a 4-entry, fully associative TLB (for simplicity), 4 KiB pages, and two processes, P1 and P2, tagged with ASIDs 1 and 2. The OS has set up these page tables:

TLB starts empty. Trace of accesses:

This trace demonstrates all three qualitatively different outcomes an architecture must support: an ordinary hit (2), an ordinary miss resolved by a walk (1, 3), a permission fault caught by a cached entry (4), and a permission fault caught during the walk itself before anything is cached (6) — plus, crucially, step 5 shows that with ASID tagging, P1's and P2's identical VPN 0x10 never collide, so isolation holds without needing to flush the TLB at the switch.

The TLB concept emerged directly from the co-development of virtual memory and paging in the 1960s. As soon as researchers built working paged virtual memory systems, they discovered that a hardware cache for translations was mandatory, not optional — without it, paging's overhead made the whole idea impractical for general-purpose computing.

Every general-purpose operating system — Linux, Windows, macOS, BSD — depends on TLB-enforced permission bits to isolate process address spaces, protect the kernel from user code, and implement copy-on-write for `fork()`, memory-mapped files, and shared libraries. Hypervisors extend the same mechanism one level further with nested/second-level translation (EPT on Intel, NPT on AMD), letting a guest OS's page tables be translated again by the hypervisor's tables, with the TLB caching the combined result to keep virtualization overhead low. Modern processors dedicate multiple levels of TLB (a small, very fast L1 TLB backed by a larger, slightly slower L2 TLB) exactly mirroring the cache hierarchy design used for data, because the same locality arguments and the same hit-rate-versus-latency tradeoffs apply. Huge pages (2 MiB or 1 GiB pages instead of 4 KiB) exist specifically to increase TLB reach — the total memory a fixed number of TLB entries can cover — which matters enormously for databases, virtual machines, and in-memory data stores that touch gigabytes of address space per query. Security features such as SMEP/SMAP (Supervisor Mode Execution/Access Prevention) and page-table-based sandboxing (e.g., browser process isolation, WebAssembly runtimes) are all ultimately enforced through the same permission-bit check that happens on every TLB lookup — making the TLB not just a performance optimization, but one of the load-bearing pillars of modern software isolation.

Ask the tutor: How do multi-level TLBs and huge pages actually interact when a large database process runs on a multicore server?