# Page Tables and the TLB: The Cost of Every Address

> Every pointer dereference triggers a virtual-to-physical translation through a four-level radix tree. The only reason your machine isn't 5x slower is a tiny cache called the TLB — and when it misses, you feel it.

URL: https://harshith.in/blog/page-tables-and-the-tlb/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: memory, kernel, performance

Virtual memory means every single memory access your program makes — every load,
every store, every instruction fetch — names an address that doesn't physically
exist. Something has to translate it, every time. That something is a four-level
tree walk through memory, which sounds ruinously expensive because it would be:
done naively, one load becomes five. The reason it isn't is a cache you can't see
in any profiler by default, and whose misses are one of the great hidden taxes in
large-memory workloads.

## The Radix Tree

x86-64 translates 48-bit virtual addresses (57 with five-level paging on recent
CPUs) through four levels of tables, each indexed by 9 bits of the address:

```text
  virtual address:  [ 9b PGD | 9b PUD | 9b PMD | 9b PTE | 12b offset ]

  CR3 ─▶ PGD ─▶ PUD ─▶ PMD ─▶ PTE ─▶ physical frame + offset
```

Each level is a 4 KB table of 512 entries; the leaf entry holds the physical
frame number plus the permission/dirty/accessed bits. The tree shape is the
point: a flat table for 48 bits of address space would need 512 GB *per process*,
but the tree only materializes paths that are actually mapped — a small process
touches a handful of 4 KB tables. This is also what `fork` copies (the tables,
not the memory), and what the kernel edits on `mmap`/`mprotect`.

A full walk is four dependent memory accesses. If every user access paid that,
memory would be ~5× slower.

## The TLB

The **Translation Lookaside Buffer** caches recent translations —
virtual-page → physical-frame, permissions included. Typical shape on a modern
core: 64–128 entries L1 dTLB, ~1.5–2K entries shared L2 TLB. A hit is free
(checked in parallel with the L1 cache lookup). A miss triggers the hardware
page-table walker: those four dependent loads, 20–100+ cycles, potentially
missing in the data cache themselves.

Do the coverage math, because it's grim: 1,500 entries × 4 KB = **6 MB of
address space covered**. Your L3 cache is bigger than your TLB reach. Any
workload that strides randomly through more than a few MB — graph analytics,
large hash tables, databases, JVM heaps — misses in the TLB *before* it misses
in cache. That's the hidden tax: people tune for cache misses and never measure

```bash
perf stat -e dTLB-loads,dTLB-load-misses,dtlb_load_misses.walk_active ./app
```

A dTLB miss rate over ~1% on a memory-bound workload is worth acting on;
`walk_active` cycles tell you directly what fraction of runtime the walker is
eating.

## Huge Pages: Buying Reach

The lever is page size. A 2 MB **huge page** uses one PMD-level entry instead of
512 PTEs: one TLB entry now covers 512× the memory, and walks are one level
shorter. 1 GB pages go further still. Two ways to get them:

- **Explicit hugetlbfs** (`mmap` with `MAP_HUGETLB`): reserved at boot or via
  `/proc/sys/vm/nr_hugepages`, guaranteed, never swapped — the database way
  (PostgreSQL `huge_pages=on`, also the standard fix for TLB-thrashy VM guests
  via KVM).
- **Transparent huge pages (THP)**: the kernel opportunistically back-fills
  anonymous memory with 2 MB pages (`madvise` mode is the sane default;
  `khugepaged` compacts in the background). Free wins for big heaps — with the
  known caveat that `always`-mode THP plus jemalloc-style allocators produced
  legendary latency-spike and memory-bloat incidents at Redis/MongoDB scale.
  Measure with `grep AnonHugePages /proc/meminfo`.

Typical results on TLB-bound code: 10–30% wall-time improvement for flipping
THP/huge pages on a random-access 10+ GB working set. It's one of the few
order-nothing optimizations left.

## Two Footnotes That Bite

**Context switches**: the TLB is per-address-space state. Old x86 flushed it all
on CR3 write; modern CPUs tag entries with a PCID so switches don't nuke
translation state — one reason the *indirect* cost of context switching fell.
Meltdown mitigation (KPTI) doubled down on this machinery: kernel and user now
use separate tables, and PCIDs are what keep the syscall path from being a full
TLB flush each way.

**Shootdowns**: on `munmap`/`mprotect`, stale entries on *other cores* must die.
The kernel sends IPIs — inter-processor interrupts — and every core pauses to
invalidate. An application that maps/unmaps frantically across a 64-core box can
spend whole percents of machine time in TLB shootdowns (`/proc/interrupts`, the
`TLB` row). Allocators that `madvise(MADV_FREE)` instead of unmapping exist
partly for this reason.

## Takeaways

- Every access translates through a 4-level radix tree; the TLB is why that's
  survivable.
- TLB reach is ~6 MB with 4 KB pages — smaller than L3. Big random working sets
  are TLB-bound; `perf stat -e dTLB-load-misses` proves it either way.
- 2 MB huge pages multiply reach 512×; THP-madvise is the low-risk default,
  hugetlbfs the guaranteed one.
- Frequent unmapping on many-core machines pays in TLB-shootdown IPIs.
- PCID/KPTI made "context switch flushes the TLB" only half-true — the cost
  moved, it didn't vanish.