The idea: every access needs a translation

A program only sees virtual addresses. Before the CPU can load or store anything, the MMU (memory management unit) must turn the virtual address into a physical address in RAM. The map lives in RAM too, as a tree of page tables. Reading that tree for every access would make every load four times slower, so the CPU keeps the last few answers in a tiny cache, the TLB (translation lookaside buffer).

The virtual address 0x7ffd5a3c1e40 split into PML4 255, PDPT 501, PD 209, PT 449 and offset 0xe40. The TLB is checked first; on a miss CR3 leads to the PML4, whose entry 255 leads to the PDPT, then the PD, then the PT, whose entry 449 gives frame 0x8e1000. The frame plus the offset is the physical address.
A TLB hit skips the four tables; a miss reads one entry from each, starting at CR3.

This page follows one access at a time: the split of the address, the TLB lookup, and on a miss the four reads of the page walk, the TLB fill, and the final physical address. For page faults, copy-on-write and how Linux fills the tables, see Linux Virtual Memory.

Splitting the address

x86-64 uses 48 of the 64 bits (4-level paging). Bits 63–48 must copy bit 47, so user addresses start with 0x0000 and kernel addresses with 0xffff. The rest is five numbers:

bitsfieldwhat it picks0x7ffd5a3c1e40
47–39PML4 indexone of 512 entries in the top table (each covers 512 GiB)255
38–30PDPT indexan entry in the page-directory-pointer table (1 GiB each)501
29–21PD indexan entry in the page directory (2 MiB each)209
20–12PT indexan entry in the page table (one 4 KiB page)449
11–0offsetthe byte inside the page, copied unchanged0xe40

Each table is one 4 KiB page holding 512 entries of 8 bytes, which is why each index has 9 bits. Linux calls the same four levels PGD, PUD, PMD and PTE.

One walk, step by step

CR3 holds the physical address of the current process's PML4. The MMU reads the entry at CR3 + PML4 index × 8. If its present bit (P) is set, the entry holds the physical address of the next table; the MMU reads that table's entry at its own index, and so on. The PT entry finally gives the frame, and the physical address is the frame plus the offset. That is four dependent memory reads before the one the program asked for (Demo: miss, walk, fill, then hit).

Neighbouring pages share the upper tables: 0x401234 and 0x402010 use the same PML4, PDPT, PD and PT, and differ only in the PT index. The stack at 0x7ffd5a3c1e40 starts at PML4 entry 255 and goes down a different branch of the tree (Demo: another page, another walk). On this page each walk costs four reads either way.

The TLB: a small cache of translations

The TLB stores page → frame pairs with their permission bits. All entries are compared at once (here: fully associative), so a hit costs about a cycle and no memory read. Only after a miss does the MMU walk, and then it writes the result into the TLB (the fill). When the TLB is full, an old entry is evicted; this page uses LRU, least recently used (Demo: TLB full, LRU eviction).

this pagea recent x86 core (roughly)
L1 data TLB4 entries, 4 KiB and 2 MiB mixed64–96 entries for 4 KiB pages, a separate small array for 2 MiB / 1 GiB
L2 (shared) TLBnone1,500–3,000 entries
hitno memory read0–1 extra cycles (L1), ~7 cycles (L2)
miss4 memory reads4 reads, often served from the data caches and the page-walk caches: tens of cycles, hundreds if they miss to RAM

The memory a TLB can map without missing is its reach: 64 entries × 4 KiB = 256 KiB. A program that jumps around a bigger working set keeps missing even when all its data is in the CPU caches.

Huge pages: a shorter walk and more reach

A PD entry with the PS (page size) bit set does not point to a page table: it maps a whole 2 MiB page. The walk stops after three reads, the low 21 bits are the offset, and one TLB entry covers what would take 512 entries with 4 KiB pages (Demo: 2 MiB huge page: one miss, then 0x40123456 and 0x401ff000 hit). A PDPT entry with PS = 1 maps 1 GiB.

Left, a 4 KiB page: CR3, PML4, PDPT, PD, PT, frame, four reads, 512 TLB entries for 2 MiB. Right, a 2 MiB page: CR3, PML4, PDPT, PD with PS equal to 1, frame, three reads, one TLB entry for 2 MiB.
With PS = 1 in the PD entry, the walk is one read shorter and one TLB entry maps 512 times more memory.

Linux gives huge pages through hugetlbfs or, automatically, through transparent huge pages (THP); databases and JVMs ask for them because their heaps are far larger than the TLB's reach.

Context switches: flush, or tag with PCID

Two processes can use the same virtual address for different frames. Here A's page 0x401000 is frame 0x5a1000 and B's is 0x9b1000. When the kernel switches process it writes the new PML4 address into CR3, and the TLB must not keep giving A's answers to B.

  • PCID off: writing CR3 flushes every TLB entry (except global kernel pages). B starts with an empty TLB, and when A runs again it misses on pages it had just used (Demo: context switch without PCID: 4 misses, 0 hits).
  • PCID on: the low 12 bits of CR3 carry a process-context identifier and every TLB entry is tagged with it. Bit 63 of the value written to CR3 says "do not flush". A lookup matches only entries with the current PCID, so A's entries stay and A hits when it comes back (Demo: context switch with PCID: 3 misses, 1 hit).
Two timelines A, B, A. Without PCID the TLB is emptied at each switch, so A's return misses. With PCID the TLB holds entries tagged 1 for A and 2 for B, and A's return hits on its tagged entry.
Without a tag every switch starts cold; with PCID each process's entries wait for it.

ARM and RISC-V call the same tag an ASID (address-space identifier). Linux uses PCID on x86 since 4.14; it became important after Meltdown, when kernel page-table isolation (KPTI) started switching CR3 on every system call too.

When the walk finds nothing

If an entry on the way has P = 0, the walk stops and the CPU raises a page fault (#PF) with the address in CR2. No TLB entry is made: the TLB only ever caches present translations (Demo: not present, page fault). The kernel's handler then maps a page and retries the instruction, or sends SIGSEGV; Linux Virtual Memory animates that side, and Paging and Page Replacement shows what happens when RAM is full.

Changing a present entry is the opposite problem: the TLB may still hold the old one. The kernel removes it with INVLPG on this CPU, and with an inter-processor interrupt (a TLB shootdown) on the other CPUs that run the same process.

How to see it on a real system

  • perf stat -e dTLB-loads,dTLB-load-misses,dtlb_load_misses.walk_completed ./prog counts TLB misses and finished walks.
  • grep -o -w pcid /proc/cpuinfo | head -1 shows if the CPU supports PCID.
  • grep -i huge /proc/meminfo shows AnonHugePages (THP) and the hugetlbfs pool.
  • cat /proc/<pid>/pagemap (as root) gives the frame of each virtual page.

See also Virtual Memory in Hardware for a one-level page table and the TLB in the textbook MIPS design, CPU caches for the caches the walk reads through, and Linux Context Switch for where switch_mm writes CR3.

What the page leaves out

Real CPUs have two or three TLB levels, separate instruction and data TLBs, and separate arrays per page size; they are set-associative, not fully associative, and do not use exact LRU. They also keep page-walk caches (paging-structure caches) for the upper levels, so a walk next to a recent one often needs only the PT read. The page leaves out permission bits (R/W, U/S, NX) and the accessed and dirty bits the walk sets, global pages, 1 GiB pages, 5-level paging (LA57, 57-bit addresses), INVPCID, and the second, nested walk of a virtual machine (EPT / NPT), where one miss can cost up to 24 reads.