Virtual Memory & Paging

Every process on your machine believes it has the same clean, private address space starting at zero. They're all wrong, and they're all wrong safely. That lie — told per-process, enforced by hardware, maintained by the kernel — is virtual memory, and paging is the machinery that tells it.

The problem being solved

Run two programs with physical addresses only, and you have three disasters: they can read each other's memory (no isolation), they must be compiled to run at different addresses (no relocation), and memory fragments into unusable gaps (no contiguity). Paging solves all three with one idea: put a translation table between every address the CPU sees and every address the RAM sees.

Addresses the program uses are virtual. Addresses on the memory bus are physical. The kernel owns the mapping.

The mechanics: split the address

Memory is managed in fixed-size pages — 4 KiB is the x86 default. A virtual address splits into two parts:

virtual address = [ virtual page number (VPN) | offset within page ]

With PAGE_SIZE = 4096 = 2^12, the low 12 bits are the offset and the rest is the VPN:

vaddr 0x1A234:
  offset = 0x1A234 & 0xFFF        = 0x234
  vpn    = 0x1A234 >> 12          = 0x1A

Translation is a lookup: the page table is an array indexed by VPN, whose entries hold a physical frame number (PFN) plus flag bits. The physical address is reassembled as:

paddr = (PFN << 12) | offset

The offset passes through untouched — pages map onto frames whole. This is exactly the translator you'll implement in this lesson's exercise: parse a page size, load a table of VPN→PFN mappings, translate addresses, and fault on anything unmapped. Get the bit math fluent now; every later lesson builds on it.

Page table entries: PFN + truth

A real PTE packs the frame number with the bits that make memory safe:

• Present — is this page mapped at all? If clear, any access raises a page fault.
• Writable — clear it and writes fault. This is how read-only code segments stay read-only.
• User — clear it and ring-3 access faults. This single bit is what keeps every process out of kernel memory.
• Accessed / Dirty — the CPU sets these on read/write. The kernel reads them to decide what's cold enough to evict and what must be written back first.
• NX (no-execute) — data pages that can never be run as code. Half of modern exploit mitigation hangs off this bit.

Page faults are a feature

A page fault is not (only) a crash. It's the CPU calling the kernel back: "translation failed, you decide." The kernel inspects why and chooses:

• Unmapped page, valid area → allocate a frame now, map it, retry the instruction. This is demand paging — memory allocated the first moment it's actually touched, not when requested.
• Write to a read-only shared page → copy the frame, remap privately, retry. Copy-on-write, which is why fork() is cheap.
• Genuinely invalid → the segfault your programs know and love.

The faulting instruction re-executes after the kernel fixes the mapping — the process never knows anything happened.

The TLB: making the lie fast

If every memory access required reading the page table first, memory would be half speed. The CPU caches recent translations in the TLB (Translation Lookaside Buffer) — a tiny, fully-associative cache of VPN→PFN entries. Hits are free. The costs appear on change: write CR3 (switch processes) and the TLB must flush; change one mapping and you must invlpg that address. "Why is this stale mapping still live" is a rite-of-passage kernel bug.

Why real tables are trees

A flat array for a 48-bit address space at 4 KiB/page needs 2³⁶ entries — 512 GiB of table per process. Absurd, and almost all of it would say "not present." So x86-64 uses a 4-level radix tree (9 bits of VPN per level, three levels of it pointing at other table pages): empty regions cost nothing because whole subtrees simply don't exist. Your exercise uses a single level to nail the core math — the tree is the same lookup, applied four times.