Skip to main content
Be Bitwise

Page Tables Deep Dive

Advanced Memory Management · Memory & Systems track

7 min read

In this module

From Virtual to Physical

Earlier modules covered the headline trick: virtual memory hands each process the illusion of a private, contiguous address space. The CPU translates virtual addresses into physical ones using page tables — data structures the OS kernel maintains and the CPU hardware walks. This lesson digs into how that translation actually plays out.

Key Concept

Every memory access goes through a multi-level page-table walk that turns a virtual address into a physical one. The TLB caches recent translations so the CPU doesn't pay the walk cost on every load.

Multi-Level Page Tables

A 64-bit virtual address could in theory point at 16 exabytes of memory. In practice x86-64 only uses 48 bits (256 TB), and even that is silly-big. A flat page table covering every 4KB page in 48-bit space would need 2^36 entries — 8 bytes each gives 512 GB per process. Obviously a non-starter.

The solution is a multi-level (hierarchical) page table. x86-64 uses 4 levels:

Page Table Walker (4-level, 4096B pages)

Bit-field breakdown
VPN1
0000
= 0 (0x0)
VPN2
0000
= 0 (0x0)
VPN3
0000
= 0 (0x0)
VPN4
0001
= 1 (0x1)
Offset
101000111111
= 2623 (0xA3F)
TLB (0/4 entries)
Empty
Level 1 Page Table
0→PPN 0x16
1→invalid
2→invalid
3→PPN 0x62
4→PPN 0xBE
5→PPN 0xF6
6→PPN 0x2A
7→PPN 0x82
8→PPN 0x56
9→PPN 0x2E
10→PPN 0xFA
11→PPN 0x22
12→PPN 0x4E
13→invalid
14→invalid
15→PPN 0xC2
Level 2 Page Table
0→PPN 0x32
1→PPN 0xFA
2→PPN 0x26
3→PPN 0x4E
4→PPN 0x92
5→PPN 0x1A
6→PPN 0xCE
7→invalid
8→PPN 0x72
9→PPN 0x4A
10→PPN 0xE6
11→invalid
12→PPN 0x52
13→PPN 0x6A
14→PPN 0x3E
15→PPN 0xE6
Level 3 Page Table
0→PPN 0x4E
1→PPN 0xE6
2→invalid
3→PPN 0xAA
4→invalid
5→PPN 0x3E
6→PPN 0xE2
7→invalid
8→PPN 0x1E
9→PPN 0x66
10→PPN 0xC2
11→PPN 0xFA
12→PPN 0xB6
13→PPN 0x4E
14→PPN 0x22
15→invalid
Level 4 Page Table
0→PPN 0x6A
1→PPN 0xC2
2→PPN 0xFE
3→PPN 0xB6
4→PPN 0x4A
5→PPN 0x22
6→PPN 0x86
7→PPN 0xEE
8→PPN 0x3A
9→invalid
10→PPN 0x2E
11→PPN 0xD6
12→PPN 0x9A
13→invalid
14→invalid
15→PPN 0xBE
Ready

Each level is a page-sized (4KB) table with 512 entries of 8 bytes each. The CPU walks the tree:

  1. The CR3 register holds the physical address of the PML4 (Page Map Level 4) table.
  2. The top 9 bits of the virtual address index into PML4, yielding the physical address of a PDPT (Page Directory Pointer Table).
  3. The next 9 bits index into the PDPT, yielding a PD (Page Directory).
  4. The next 9 bits index into the PD, yielding a PT (Page Table).
  5. The final 9 bits index into the PT, yielding the physical page address.
  6. The 12-bit page offset is appended to get the final physical address.

Worked Example: Slicing a Real Address

Take the user-space address 0x00007f1234567abc. Write its low 48 bits in binary and cut from the right: 12 bits of offset, then four 9-bit indices.

text
0111 1111 0 | 001 0010 00 | 11 0100 010 | 1 0110 0111 | 1010 1011 1100
PML4 | PDPT | PD | PT | offset
0x0fe | 0x048 | 0x1a2 | 0x167 | 0xabc

A quick check without binary: shift right by 39 and you get 0xfe, which is 254, so this address sits in the 255th of the PML4's 512 slots. That fits: user space ends at 0x00007fffffffffff, the bottom half of the PML4. The walker below is the real thing at full size, four levels of 9 bits each. The table contents are made up, with only the one path this address needs filled in. Step it, then try 0x00007f1234567000 (same page, so a TLB hit) and 0x00007f1234568abc (the next page, a PT index of 0x168, which has no entry and faults).

x86-64 four-level walk (illustrative tables)

Bit-field breakdown
PML4
011111110
= 254 (0xFE)
PDPT
001001000
= 72 (0x48)
PD
110100010
= 418 (0x1A2)
PT
101100111
= 359 (0x167)
Offset
101010111100
= 2748 (0xABC)
TLB (0/4 entries)
Empty
PML4 table
0xFE→next table @ frame 0x1A3C4
PDPT table
0x48→next table @ frame 0x2B710
PD table
0x1A2→next table @ frame 0x30F5E
PT table
0x167→frame 0x7D2E1
Ready

Only the PML4 table is mandatory. Intermediate tables get allocated on demand. A process using 1 GB of memory carries far fewer page table pages than one using 100 GB.

5-Level Paging

Intel introduced 5-level paging (PML5) to extend the virtual address space to 57 bits (128 PB). This adds one more level of translation, with 512 more entries. Linux gained support for 5-level paging in kernel 4.14. The additional level is only used when the kernel is configured for it and the CPU supports it. Most applications do not need this much address space.

TLB Mechanics

A page table walk costs up to 4 (or 5) sequential memory accesses. Way too slow to do on every memory reference. The Translation Lookaside Buffer (TLB) caches recent translations.

Modern CPUs have multiple TLB levels:

  • L1 ITLB: instruction TLB, ~64 entries, ~1 cycle
  • L1 DTLB: data TLB, ~64 entries, ~1 cycle
  • L2 STLB: shared second-level TLB, ~1024-2048 entries, ~7-10 cycles
  • Page table walk: on TLB miss, ~10-100+ cycles

A TLB is content-addressable (you look up by virtual page number, not index) and highly associative: some small first-level TLBs are fully associative, so any entry can map any virtual page, while the bigger second-level TLBs are set-associative to keep lookups fast. Entries can also be tagged with address space identifiers (ASIDs) so translations from different processes coexist without flushing on context switches.

Context-switch a process and its TLB entries may be tossed. On older CPUs that meant flushing the entire TLB. Modern CPUs use PCID (Process Context ID) on x86 or ASID (Address Space ID) on ARM to tag entries, letting entries from multiple address spaces coexist. The cost of context switching plummets.

Meltdown (2018) made PCID matter far more. The Linux fix, kernel page-table isolation (KPTI), gives each process a second set of page tables with the kernel mostly unmapped, so every system call and interrupt switches CR3 twice. Without PCID each switch throws away most of the TLB; with it, the user and kernel halves get separate tags and survive. CPUs that aren't vulnerable to Meltdown skip KPTI altogether.

Huge Pages (Superpages)

Standard 4KB pages mean mapping 1 GB of memory eats 262,144 TLB entries — well beyond what any TLB can hold. Huge pages (2 MB on x86-64, using the PD-level entry directly) and gigantic pages (1 GB, using the PDPT level) ease TLB pressure by squeezing more memory into each entry.

At 2 MB pages, 1 GB of memory needs 512 TLB entries. At 1 GB pages, one entry covers the whole gig.

Linux exposes huge pages two ways:

  • Transparent Huge Pages (THP): the kernel auto-promotes contiguous 4KB pages to 2 MB huge pages where it can. No app changes, but promotion/demotion can spike latency.
  • Explicit huge pages (hugetlbfs): the admin reserves huge pages at boot and apps request them deliberately. More predictable, more configuration.

Page Table Walks in Detail

On a TLB miss, the CPU's page table walker — a dedicated hardware unit — traverses the page table hierarchy. On x86-64 it reads memory directly (often hitting the L1/L2 data caches for page table entries), following the chain from CR3 through each level.

Each page table entry contains:

  • Physical page address (the translated address)
  • Present bit: is this page mapped?
  • Read/Write bit: is writing allowed?
  • User/Supervisor bit: can user-mode code access this page?
  • Accessed bit: has this page been read? (set by hardware, used by OS for page replacement)
  • Dirty bit: has this page been written? (set by hardware, used by OS for write-back)
  • NX (No Execute) bit: can code be executed from this page?

Present bit clear? The CPU raises a page fault. The OS kernel handles it: maybe it allocates a physical page (demand paging), pulls data from disk (swap), kills the process (invalid access), or runs copy-on-write.

Faults that the kernel resolves without touching disk are called minor faults, and the kernel counts them for every process. This program allocates 32 MB, then touches one byte per 4 KB page twice over. Predict both fault counts before you run it.

Try itChange MB or touch every other page and watch the first count follow. Exact numbers vary a little from run to run.
C (GCC 9.2.0)

The first pass faults roughly once per page, because malloc only reserved the range and the kernel fills in page table entries on first touch. The second pass faults close to zero times. If the first count comes out far below the page count, the kernel is probably backing the buffer with transparent huge pages, one fault per 2 MB.

Performance Implications

Page table walks tangle with the cache hierarchy. Page table entries themselves can sit in L1/L2/L3, so repeated accesses to nearby virtual addresses (which share upper-level entries) ride cache warmth. A truly random access pattern across a big address space, on the other hand, kicks off both TLB misses and cache misses for the page table walk — easily hundreds of cycles per memory access.

For performance-sensitive code: keep the working set small enough to fit in the TLB, reach for huge pages on large memory regions, walk memory sequentially where you can (sequential accesses share TLB entries), and remember that NUMA can make remote page table walks even costlier.