Virtual Memory and Address Translation
You have met
virtual memory from the operating system's side
— the illusion that every process owns a private, contiguous address space far larger than physical RAM.
This page looks at the same illusion from underneath, where the hardware makes it
real: on every single load and store, the processor must translate the program's
virtual address into the physical address of an actual DRAM byte, in a
handful of nanoseconds, or the whole machine grinds to a halt. Address translation is the busiest piece of
machinery in the entire chip.
Pages: the unit of translation
Translating every byte individually would need a map with billions of entries. Instead memory is carved
into fixed-size pages — classically 4\ \text{KB} — and we
translate a page at a time. This splits a virtual address exactly like a cache splits its address: the low
\log_2(\text{page size}) bits are the page offset (which byte
within the page, unchanged by translation), and the high bits are the virtual page number
(VPN). Translation maps the VPN to a physical page number (PPN), also called a
frame; the offset is copied straight through.
\underbrace{\text{VPN}}_{\text{translated}} \;\Big|\; \underbrace{\text{offset}}_{\text{copied}} \;\;\longrightarrow\;\; \underbrace{\text{PPN}}_{\text{from page table}} \;\Big|\; \underbrace{\text{offset}}_{\text{unchanged}}
The page table
The map itself is the page table, one per process, living in main memory. The VPN indexes
into it; the entry it lands on — the page table entry (PTE) — holds the PPN plus a bundle
of control bits: valid/present (is this page in RAM at all?), protection (read / write /
execute permissions), dirty and accessed bits for the OS, and user/supervisor.
So translation and protection happen in the same step: the hardware checks the PTE's
permission bits against the access type and faults if a program writes a read-only page or a user process
touches kernel memory.
Where does the hardware find the page table? In an architectural register — the page-table base
register (\texttt{CR3} on x86, \texttt{TTBR}
on ARM). This is the key architectural support for virtual memory: on a context switch the OS simply loads
a new base register value, and the very same virtual addresses now translate through a different
process's table. Point the register at a new table and you have swapped universes.
// Single-level translation: split the virtual address, look up the frame, form the physical address.
const PAGE = 4096; // 4 KB pages -> 12 offset bits
const offsetBits = Math.log2(PAGE);
// A tiny page table: VPN -> PPN (frame). Undefined = page fault.
const pageTable: Record<number, number> = { 0: 7, 1: 3, 2: 9 };
function translate(va: number): string {
const vpn = Math.floor(va / PAGE); // high bits
const offset = va % PAGE; // low `offsetBits` bits
const ppn = pageTable[vpn];
if (ppn === undefined) return `VA 0x${va.toString(16)}: VPN ${vpn} -> PAGE FAULT`;
const pa = ppn * PAGE + offset;
return `VA 0x${va.toString(16)}: VPN ${vpn}, off ${offset} -> PPN ${ppn} -> PA 0x${pa.toString(16)}`;
}
console.log(`offset bits = ${offsetBits}`);
for (const va of [0x0004, 0x1abc, 0x2010, 0x5000]) console.log(translate(va));
Why one flat table won't do: multi-level page tables
A 64-bit address space is astronomically large. A single flat page table covering it would need an
impossible number of entries — mostly for pages a process never uses. The fix is a multi-level
(hierarchical) page table: chop the VPN into several slices, one per level, and walk a
tree of small tables. x86-64 uses four levels (PML4 → PDPT → PD → PT); a slice indexes
each level's table, whose entry points to the next level's table, until the last gives the PPN. The genius:
entire subtrees for unused address ranges simply don't exist — the tree is sparse, so the table's size is
proportional to memory used, not memory addressable.
// A 4-level walk (x86-64 style): a 48-bit VA = 4 nine-bit indices + a 12-bit offset.
function decodeWalk(va: number) {
const offset = va & 0xFFF; // low 12 bits
const vpn = Math.floor(va / 4096);
const idx = [0, 1, 2, 3].map((lvl) => (vpn >>> (lvl * 9)) & 0x1FF); // 9-bit slices, level 0 = lowest
return { l4: idx[3], l3: idx[2], l2: idx[1], l1: idx[0], offset };
}
const va = 0x7f3c_1234 & 0xFFFFFFFF;
const d = decodeWalk(va);
console.log(`indices: PML4=${d.l4} PDPT=${d.l3} PD=${d.l2} PT=${d.l1}, offset=${d.offset}`);
console.log("a 4-level table => up to 4 memory accesses PER translation");
The cost: the page-table walk
Here is the sting. Each level of the tree lives in memory, so a page-table walk on a
4-level table is up to four dependent memory accesses — just to translate one
address — before the real load can even begin. On a machine where memory costs hundreds of
cycles, paying four such accesses for every load would be catastrophic, easily 4–5× slower. Two structures
rescue us: translations get cached in a
TLB
(so a hit skips the walk entirely), and the page-table entries themselves get cached in the ordinary data
caches (so a miss's walk mostly hits in L2/L3). The next page is entirely about that first rescue.
- every access splits into a VPN (translated) and a page offset
(copied unchanged);
- the page table maps VPN → PPN and, in the same step, enforces
protection via permission bits;
- a page-table base register (CR3/TTBR) names the current table, so a context switch
is one register write;
- a k-level table costs up to k dependent memory accesses per
translation — the price a TLB exists to avoid.
Because the page table can point a virtual page not at a DRAM frame but at a slot on disk. When a
program touches such a page, its PTE's present bit is clear, the hardware raises a page
fault, and the OS steps in: it finds the page on disk, evicts some other frame to make room
(writing it back if dirty), loads the wanted page into that frame, fixes up the PTE, and restarts the
instruction — which now translates and succeeds. The program never knows. This is demand paging,
and it is how 8 GB of RAM can host processes claiming terabytes: physical memory is just a cache for a
much larger virtual world backed by disk. The architecture provides the fault; the OS provides the policy.
A classic slip is to "translate the whole address". Translation replaces only the page number; the
offset (the low \log_2(\text{page size}) bits) is copied byte-for-byte
from virtual to physical. A byte 100 into virtual page 5 is byte 100 into whatever physical frame page 5
maps to. This is not a detail — it is the seam that makes the clever
VIPT L1 cache
trick possible, because the offset bits are known immediately, without waiting for translation.
Confuse offset with VPN and none of the TLB/cache overlap will make sense.