The TLB

A load from a virtual address needs the physical address first, and the physical address is at the end of a walk through four page-table levels (Page Tables). That is four dependent memory reads — each waiting for the previous one — before the fifth, the one the program asked for. If the table entries are in L1 cache the walk costs around 20 cycles; if they are in DRAM it costs four round trips of 80–100 ns each. A program that runs at one memory access per cycle would run at one per five to one per four hundred.

The saving grace is locality. A program that touches address X will very probably touch X + 64 next, or X again, or something else on the same 4 kB page — and every address on that page has the *same* translation. Cache the translation once and the next thousand accesses to that page need no walk at all. That cache is the translation lookaside buffer, and it is the reason virtual memory costs a few percent instead of a few hundred.

The TLB is a small, fully or highly associative cache inside the core, keyed on virtual page number and holding the frame number plus the permission bits from the PTE. On a translation the CPU checks it in parallel with, or before, the L1 cache lookup; a hit delivers the physical address in about one cycle, and the memory access proceeds. A miss starts the page walker, which reads the four levels (using its own page-walk caches for the upper levels), installs the resulting entry in the TLB, evicting an older one, and retries. If the walk finds a not-present entry, the miss becomes a page fault and the kernel takes over (Page Faults).

Sizes are small because associative lookup is expensive: a modern x86 core has around 64 entries in the L1 data TLB, 128 in the instruction TLB, and 1,536–2,048 in a shared L2 TLB (the STLB), with separate or shared entries for 2 MB pages. Apple’s and ARM’s cores are in the same range. Replacement is approximately LRU — the same policy as the LRU Cache you built, in silicon, with the same weakness: a scan over more pages than entries evicts everything useful.

TLB reach is the amount of memory the TLB can translate without a miss: entries × page size. With 1,536 entries of 4 kB that is 6 MB. A process whose hot working set is 6 MB or less runs with essentially no translation cost; a process that randomly touches a 2 GB heap — a hash table, a graph, a database buffer pool — misses on almost every access, and each miss is a walk whose page-table entries are themselves probably not in cache. Measured overhead on such workloads is commonly 10–30% of run time, sometimes more; perf stat -e dtlb_load_misses.walk_completed makes it visible.

The page size is the lever. With 2 MB pages the same 1,536 entries reach 3 GB — 512× more — and the walk that fills them is one level shorter. This is the primary reason huge pages exist (Paging): not to save page-table memory, but to keep the translation of a large hot heap inside the TLB. JVMs, databases and packet-processing frameworks all expose a huge-page switch for this reason, and the gain on a TLB-bound workload is often larger than any code optimisation available.

The other lever is locality, and it is the bridge to DSA: an array traversal touches one page per 4 kB and misses once per 64 cache lines; a linked list or a pointer-chasing tree can miss on every node. Data-structure choices that look like "cache-friendliness" in the Breadth-First Search (BFS) vs Depth-First Search (DFS) or array-vs-list discussion are TLB-friendliness too, and on large working sets the TLB miss is the more expensive of the two.

A TLB entry is only valid for the page table it was walked from. When the kernel switches to another process it loads a new base register, and every cached translation is now wrong. The original answer was to flush the whole TLB on every address-space switch, which meant every context switch was followed by a burst of misses as the new process re-walked its working set — a large part of the indirect cost in Context Switching. Kernel entries survived because they are marked global and are the same in every table.

Tagging fixed that. ARM’s ASID and x86’s PCID (used by Linux since 4.14) attach an address-space identifier to each entry, so entries of several processes coexist and a switch only changes which tag is current. The kernel manages the small tag space (12 bits on x86; Linux uses 6 PCIDs per CPU) and flushes only when a tag is reused. This is also what made kernel page-table isolation survivable: the user and kernel tables of the same process have different PCIDs, so the switch on every syscall does not empty the TLB.

Tagging solves switches but not changes. When the kernel modifies a mapping — munmap, mprotect, reclaim unmapping a page, copy-on-write breaking a share — any core that may have cached the old entry must drop it. On x86 there is no hardware coherence for TLBs, so the kernel sends an inter-processor interrupt to every core running a thread of that process: a TLB shootdown, costing microseconds and scaling with thread count. A multi-threaded process that mmaps and munmaps per request pays a shootdown per call across all its threads, which is why allocators batch releases with madvise and why "the kernel is spending its time in flush_tlb_mm_range" is a recognisable performance pathology.

The TLB is a cache in every sense the Computer Architecture domain uses: a small fast memory holding recently used entries of a larger slow one, with hits, misses, associativity and a replacement policy. It differs from L1/L2/L3 only in what it caches (translations, not data) and in its coherence story (none in hardware; the kernel does it). Reasoning about a working set has to account for both hierarchies at once: a 12 MB working set fits L3 but not the 4 kB-page TLB; a 3 GB working set on huge pages fits the TLB but not any cache.

And it is the LRU Cache from DSA with a capacity of 1,536 and a hardware approximation of recency: the same structure, the same hit-rate reasoning, the same scan pathology, and the same answer — make the working set fit, or make the entries cover more (huge pages), or make the access pattern local. When the simulator shows hit rate collapsing as you raise the working set past reach, you are watching the LRU cache you implemented lose to a scan.