Paging & Page Tables

Paging is the mechanism that makes virtual memory work. It divides both virtual and physical memory into fixed-size chunks (pages), and maintains a translation table that maps virtual pages to physical ones.

Pages — 4KB Chunks

Why divide memory into pages? Managing memory byte-by-byte would be impossibly slow. Pages (4096 bytes on x86-64) are the minimum unit of allocation and protection. Every memory permission (read/write/execute) and every mapping applies to whole pages.

Page Tables — The Translation Map

x86-64 uses four-level page tables. A virtual address is split into five parts, each indexing into the next level of the table:

Virtual address (48 bits used):
  Bits 47-39: PGD index (Page Global Directory)
  Bits 38-30: PUD index (Page Upper Directory)
  Bits 29-21: PMD index (Page Middle Directory)
  Bits 20-12: PTE index (Page Table Entry)
  Bits 11-0:  Offset within the 4KB page

PGD → PUD → PMD → PTE → Physical page address + offset

Each process has its own PGD (top-level page table). CR3 register points to the current process's PGD. On context switch, CR3 is updated, instantly switching to the new process's address space.

The TLB — Translation Lookaside Buffer

Isn't walking 4 levels of tables for every memory access incredibly slow? Yes — without help. The TLB is a hardware cache inside the CPU that stores recent virtual→physical translations. A TLB hit means instant translation (no table walk). A TLB miss triggers the page table walk (handled by hardware on x86). TLB has limited entries — too many different pages = thrashing the TLB.

Context switches flush the TLB (or use Process Context IDs to avoid flushing). This is part of why context switching has overhead.

Page Faults — Three Types

Type	Cause	Action	Cost
Minor	Page in RAM but not mapped in page table yet (e.g., after fork() CoW)	Update page table entry	Very fast — no disk I/O
Major	Page not in RAM — must read from disk (swap or mmap'd file)	Find page on disk, read into RAM, update table	Slow — disk latency (milliseconds)
Segfault	Access to unmapped or protected address	Send SIGSEGV to process	Process may die

# Monitor page faults for a command
/usr/bin/time -v my-program 2>&1 | grep "Page faults"
# Major (I/O required) page faults: 12
# Minor (reclaiming) page faults: 4521