The TLB and Virtual-to-Physical, Revisited

A second translation hiding inside every load

From the virtual-memory rung you already carry the headline fact: the address in your pointer is a lie the kernel tells your process. Every address your code computes is a virtual address, and somewhere a page table maps the page it sits in onto a real physical frame in DRAM. What that rung let you skip over — reasonably, because you were learning the idea — is the timing. When does that mapping actually get applied? The answer is brutal: on every memory access your program makes. Every load, every store, every instruction fetch. Before the CPU can ask the cache or DRAM for the bytes at your address, it must first turn that virtual address into a physical one.

Now put that next to what the last two guides taught you. You learned that an L1 cache line arrives in a handful of cycles, and that the whole memory hierarchy exists to keep that hit rate sky-high. But the cache is addressed — at least in part — by a physical address. So if translating virtual to physical itself required walking a page table in DRAM, every single L1 hit would secretly drag a 100-plus-cycle memory trip behind it. That is absurd: the fast cache would be chained to slow memory by the very translation that precedes it. There has to be a cache for the translation itself. That cache is the TLB, the translation lookaside buffer, and it is the quiet hero of this guide.

What is actually being looked up

Recall how a virtual address splits. The low bits are the offset inside a page; the high bits are the virtual page number. On a typical x86-64 system with 4 KiB pages, the bottom 12 bits are the offset (because 2^12 = 4096 = 4 KiB), and everything above them names the page. Translation never touches the offset — your byte sits at the same offset within its frame as within its page. The only thing that gets translated is the page number: the memory management unit takes your virtual page number and produces a physical frame number, then glues the untouched offset back on the bottom.

virtual address  (x86-64, 4 KiB pages):

  63        12 11         0
  +-----------+-----------+
  | page num  |  offset   |
  +-----------+-----------+
        |           |
        |           +------------------> copied straight through
        v
  TLB / page walk: page num  -->  frame num
        |
        v
  +-----------+-----------+
  | frame num |  offset   |   = physical address
  +-----------+-----------+

So the TLB is, in shape, exactly like the set-associative cache you met last guide — except instead of caching data lines keyed by address, it caches frame numbers keyed by page number. A typical L1 TLB holds only on the order of 64 entries; an L2 TLB might hold 1024 to 2048. Tiny. Each entry says "virtual page 0x7fff_a maps to frame 0x1c3, and here are its permission bits." When your load's page number is in the TLB, the physical address is ready in a single cycle and the data cache lookup proceeds with no extra delay. That is the happy path, and on real workloads it is the overwhelmingly common one — which is the whole reason such a small table is worth building.

The miss: a page walk in slow motion

Now the unhappy path. Your page number is not in the TLB — a TLB miss. The hardware must now find the translation the slow way, by reading the actual page table out of memory. On x86-64 this is no single lookup: the page table is a multi-level page table, a tree four levels deep. The MMU takes your virtual page number, chops it into four index fields, and walks the tree one level at a time, each level living in physical memory. This is the page walk, and on modern chips it is done by dedicated hardware, not the kernel.

1. Start at the root table whose physical address sits in a control register (CR3 on x86-64). Use the top index field of the virtual page number to pick one entry in this level-4 table.
2. That entry holds the physical address of the next-level table. Read it from memory, then use the second index field to pick an entry there. Repeat down through level 3 and level 2.
3. At the deepest level the entry is the leaf: the page-table entry that finally holds the frame number plus permission and status bits. Glue the original offset onto that frame and you have the physical address.
4. Install the freshly found page-to-frame mapping into the TLB so the next access to this same page is a one-cycle hit, then finally let the original load proceed.

Count the cost honestly. A four-level walk is up to four dependent memory reads, each of which could itself miss in the data cache and reach all the way to DRAM. In the worst case a single TLB miss can cost hundreds of cycles — the price of several ordinary cache misses stacked back to back, because each level's address depends on the previous level's result, so they cannot overlap. In practice the upper page-table levels are themselves hot in the cache, so a typical miss is far cheaper than the worst case. But the shape of the danger is real: a workload that misses the TLB constantly pays a tax that no amount of data-cache tuning can remove, because the tax is levied before the data cache is even consulted.

TLB reach, and why huge pages exist

Here is the number that matters and that almost nobody computes for themselves: TLB reach. Each TLB entry covers exactly one page — 4 KiB. So an L1 TLB of 64 entries can map, at any instant, only 64 × 4 KiB = 256 KiB of address space. Read that again. Your data caches might hold many megabytes, but if your hot data is spread across more than 256 KiB of distinct pages, the TLB cannot hold a translation for all of them at once, and you start thrashing translations even while your bytes sit comfortably in L2 or L3. This is the failure mode the cache-line tuning of the previous guides cannot touch, and it is why locality matters at the granularity of pages, not just lines.

The hardware's answer is huge pages: instead of 4 KiB pages, the page table can describe a 2 MiB page (or even 1 GiB) with a single entry. The translation tree gets shorter — the walk stops one level early because that level is the leaf — and, more importantly, one TLB entry now covers 2 MiB instead of 4 KiB. With huge pages the same 64-entry TLB reaches 64 × 2 MiB = 128 MiB, a 512-fold increase in reach for a workload that streams through large buffers. Databases, language runtimes, and scientific codes that touch gigabytes routinely turn huge pages on for exactly this reason.

When the kernel must reach in: context switches and flushes

One last layer ties this back to processes. Every process has its own virtual address space, so virtual page 0x1000 in process A and virtual page 0x1000 in process B almost certainly map to different physical frames. The TLB caches mappings without, in the simplest design, recording which process they belong to. So on a page-table switch — every time the scheduler context-switches from A to B — those stale A-mappings would be catastrophically wrong for B. The classic fix is brutal: flush the entire TLB on every context switch, throwing away all 64 (or 2048) hard-won translations. That is why a context switch is so much more expensive than it first looks: it is not just saving registers, it silently empties this cache and forces the new process to re-walk the page table for its first touches.

Modern CPUs soften this with an address-space identifier (Intel calls it a PCID, ARM an ASID): a small tag stored inside each TLB entry naming the address space it belongs to. With tagged entries the CPU can keep A's and B's translations side by side and simply ignore the ones whose tag does not match the current process — so a switch back to A finds its translations still warm, no flush needed. This is why enabling PCIDs measurably speeds up context-switch-heavy workloads, and why a security mitigation that forces extra flushes (such as the kernel/user page-table split introduced for Meltdown) showed up as a real, measurable slowdown: it was paying the flush tax this hardware was specifically built to avoid.