Address Translation in Depth
In your undergraduate course you learned that
paging
chops the address space into fixed pages and stores, in a page table,
where each virtual page currently lives in physical memory. That picture is correct — and, for a modern
64-bit machine, quietly impossible to implement the way it is usually drawn. This lesson is about what
actually sits behind that one innocent phrase, "the page table", on real hardware running a real kernel.
The hardware side — the MMU walking the table, the
TLB caching the
result — you met in
architecture.
Here we take the operating system's view: how the OS builds and maintains these
structures, what they cost in memory, and why the flat array from the textbook has to be
replaced by a tree.
Why a flat page table cannot exist
Take the textbook design literally. A page table is an array indexed by virtual page number (VPN); entry
i tells you the physical frame for page i. With
4\,\text{KiB} pages the offset is 12 bits, so on a
machine with a 48-bit virtual address the VPN is
48 - 12 = 36 bits. That is
2^{36}\ \text{entries} \times 8\ \text{bytes/entry} \;=\; 2^{39}\ \text{bytes} \;=\; 512\ \text{GiB}.
Half a terabyte of page table — per process — to map an address space that is almost entirely
empty. And that is the friendly case: today's Intel and AMD chips also offer a
57-bit space, where the flat table would be
256\ \text{PiB}. The flat array pays for every page that could exist,
when a real process touches a few thousand. The fix is to make the structure sparse:
store table only where the address space is actually populated.
A big server process might map a few gigabytes — call it 2^{32} bytes, or
2^{20} pages. Against a 48-bit space that is
2^{20}/2^{36} = 2^{-16}, roughly 0.0015% occupancy. The
address space is not a warehouse that is nearly full; it is an almost-empty desert with a few small
cities (code, heap, stack, mapped files) scattered light-years apart. Any sane page-table design must
spend memory in proportion to the cities, not the desert — which is exactly what a radix tree does.
The radix (multi-level) page table
The winning design — used by x86-64, ARMv8, RISC-V Sv48/Sv57 — is a radix tree. Instead
of one giant array indexed by the whole 36-bit VPN, split the VPN into equal slices and use each slice to
index one level of the tree. On x86-64 with 4\,\text{KiB} pages the
36-bit VPN is cut into four 9-bit indices, giving a
four-level table (Intel's names: PML4 → PDPT → PD → PT). Each table is exactly
512 entries \times\, 8 bytes
= 4\,\text{KiB} — one page, deliberately. Walk the tree once for the whole
address:
The magic is that upper levels can be missing. If a whole 512\,\text{GiB}
region of the address space is unused, the single PML4 entry that would point into it is simply marked
not present, and none of the tables beneath it need exist. A process touching a few megabytes
needs only a handful of tables — a few tens of kilobytes — instead of half a terabyte. The tree spends
memory on the cities, not the desert.
- the virtual page number is split into k equal indices; each indexes one
level of a tree of tables, so a lookup is k dependent memory reads;
- x86-64 uses k=4 levels of 9-bit indices
(48-bit VA), or k=5 for the
57-bit space; each table is one 4\,\text{KiB} page of
512 eight-byte entries;
- a not-present upper entry prunes an entire subtree, so table memory scales with the
pages actually mapped, not with the size of the address space.
Walk it by hand, then by code
Translation is pure bit-slicing. Given a virtual address, the bottom
12 bits are the byte offset (they are not translated
— they pass straight through). The next four groups of 9 bits, read from the
top, index PML4, PDPT, PD and PT in turn:
\text{VA} = \underbrace{i_4}_{47\text{–}39}\;\underbrace{i_3}_{38\text{–}30}\;\underbrace{i_2}_{29\text{–}21}\;\underbrace{i_1}_{20\text{–}12}\;\underbrace{\text{offset}}_{11\text{–}0}.
Each index selects an 8-byte entry that holds the physical address of the
next table (or, at the last level, of the data frame) plus permission and status bits. Run the
translator below: it splits an address, prints the four indices, and tallies the memory the walk touches.
// x86-64 style four-level translation of a 48-bit virtual address.
// 4 KiB pages -> 12-bit offset; four 9-bit table indices (PML4, PDPT, PD, PT).
const VA = 0x5f3c2a15abc; // a virtual address (< 2^48)
const offset = VA % 4096; // low 12 bits
const index = (level: number): number => // level 0 = PT ... 3 = PML4
Math.floor(VA / 2 ** (12 + 9 * level)) % 512;
const names = ["PT", "PD", "PDPT", "PML4"];
console.log(`VA = 0x${VA.toString(16)}`);
for (let level = 3; level >= 0; level--) {
console.log(` ${names[level].padEnd(4)} index = ${index(level)} (9 bits)`);
}
console.log(` offset = ${offset} (passes through untranslated)`);
// Cost of the walk: four table reads, one page per level.
console.log(`translation touches 4 tables x 4 KiB = ${4 * 4} KiB, then 1 data read`);
console.log("=> up to 4 extra memory accesses per reference -- which is why the TLB exists");
The other shapes: inverted and hashed page tables
The radix tree is per-process and its size grows with the virtual memory a process maps. A
different idea flips the question around. An inverted page table has one entry per
physical frame, not per virtual page — so its size is fixed by how much RAM the machine has, not
by how many processes or how large their address spaces are. To translate, you search the table for the
entry holding (\text{pid}, \text{VPN}); to make that search fast you keep a
hash of (\text{pid}, \text{VPN}) — a hashed page
table. IBM's PowerPC and PA-RISC used exactly this.
| Structure | Size scales with | Lookup | Used by |
|---|
| Flat (single-level) | virtual address space (huge) | 1 read | nobody, on 64-bit |
| Radix / multi-level | pages actually mapped | k dependent reads | x86-64, ARMv8, RISC-V |
| Inverted / hashed | physical RAM | hash + chain walk | PowerPC, PA-RISC, Itanium |
Inverted tables shine when RAM is small relative to the address space and you have many big, sparse
processes — they cost the same no matter how much virtual memory is mapped. But sharing a page between
processes is awkward (one physical frame, many virtual mappings), and every miss pays a hash lookup that
the MMU must be built to do. x86-64 bet on the radix tree instead, because upper-level entries
are shareable and the walk is a dumb, cacheable pointer-chase the hardware does brilliantly.
Four levels of 9-bit indices reach 4 \times 9 + 12 = 48
bits — a 256\,\text{TiB} virtual space, and (with matching physical addressing)
enough to map a few terabytes of RAM comfortably. But big-memory servers began bumping into that ceiling,
and memory-mapped persistent storage wants to map far more than sits in DRAM. So Intel added
5-level paging: one more 9-bit level (PML5) on top, reaching
57 bits — a 128\,\text{PiB} address space. Linux
keeps it off by default and turns it on only when a process asks for a mapping above the 47-bit line, so
the common case still pays for four levels, not five. It is the radix tree's best trick: growing the
address space costs exactly one more pointer indirection.
A tempting but wrong mental model is that page tables are some special CPU register file. They are not —
they are ordinary data structures sitting in physical RAM, and the entries hold
physical frame numbers (if they held virtual addresses you would need to translate them,
and translation would never terminate). The CPU's \texttt{CR3} register holds
the physical address of the top table; the MMU follows physical pointers all the way down. This
is also why the OS, when it edits a page table, must reason in physical addresses and cannot simply
dereference a pointer — and why a stray write into page-table memory is catastrophic. The tables are
data, but they are the data that defines what all other data means.
What the OS actually does
None of this walking is the OS's job at run time — the MMU does the walk in hardware. The kernel's role is
to be the architect and janitor of the tree. On \texttt{fork}
or \texttt{exec} it allocates the top table and enough lower tables for the
initial mappings; on a page fault into a valid-but-unmapped region it allocates a table on demand
and fills in the entry; on \texttt{munmap} or exit it tears tables down and can
free ones that have become empty. It sets the permission and status bits the hardware reads (present,
writable, user/supervisor, no-execute) and the ones the hardware writes (accessed and dirty),
which the
page-replacement
policy later harvests. Mechanism (the walk) is the hardware's; policy and bookkeeping (the tree's shape and
contents) are the kernel's.