Page tables and multi-level paging: Visual walkthrough

Prerequisites we lean on gently: Virtual Memory, Bit Manipulation and Masking, Address Space Layout. The speed fix at the end connects to TLB and Translation Caching and Cache Memory Basics.

Step 1 — An address is a row of bits, nothing more

WHAT. A virtual address is the number a program hands to the hardware when it says "read from here." On a 32-bit machine that number is exactly 32 binary digits — 32 boxes, each holding a 0 or 1. Nothing magic: it is a whole number between $0$ and $2^{32} - 1$ .

WHY start here. Everything that follows is just slicing this row of boxes into groups and treating each group as a small number. If you see the address as a row of bits, the rest is bookkeeping.

PICTURE. Below, the 32 boxes are drawn left (high bits, worth the most) to right (low bits, worth the least). The example address is 0x00402ABC.

Figure — Page tables and multi-level paging

Step 2 — Why the bottom bits are special: the page

WHAT. Memory is chopped into equal blocks called pages. A common size is 4 KiB $= 4096$ bytes $= 2^{12}$ bytes. Call the page size $P$ , so here $P = 2^{12}$ .

WHY this exact idea. Ask: how many bits do I need to name one particular byte inside a single page? A page holds $P$ consecutive bytes, numbered $0$ to $P - 1$ . To count up to $P$ different positions you need

$p = "how many bits to name P things" lo g_{2} P$

Here $p = lo g_{2} 2^{12} = 12$ . Those bottom $12$ bits are the offset: they say where inside a page the byte sits. The tool $lo g_{2}$ appears because each extra bit doubles how many things you can name — and doubling is exactly what $lo g_{2}$ inverts. No other function answers "how many bits for $P$ items?"

PICTURE. The same 32 boxes, now with the low $12$ split off in coral. That coral chunk is the offset; it will ride through translation untouched.

Step 3 — The rest of the address names which page

WHAT. Everything above the offset is the virtual page number (VPN). With a $V = 32$ bit address and $p = 12$ offset bits, the VPN is

$v = V - p = 32 - 12 = 20 bits.$

WHY. We only ever need to translate which page a byte lives in, never where inside the page (Step 4 proves why). So we peel off the top $v$ bits and treat them as one number, the VPN:

$VPN = ⌊ \frac{addr}{P} ⌋$

$\frac{addr}{P}$ — divide by page size; this throws away the offset.
$⌊ \cdot ⌋$ — floor (round down) discards any fractional leftover, leaving a clean whole page number.

PICTURE. Lavender = the 20-bit VPN, coral = the 12-bit offset. Two clean fields.

For 0x00402ABC, the top 20 bits are 0x00402.

Step 4 — Why the offset never changes

WHAT. During translation the VPN is replaced by a physical frame number (PFN), but the offset is copied verbatim.

WHY. A frame is a block of physical RAM the same size $P$ as a page. Because they are the same size, byte number $k$ inside a page lands on byte number $k$ inside its frame — the " $k$ " is unchanged. Translation only decides which frame, i.e. it only rewrites the top bits.

PICTURE. A page (lavender box, bytes $0 \dots P - 1$ ) is placed onto a frame (mint box). The coral offset arrow points to the same slot in both.

Step 5 — One flat table would be enormous

WHAT. The simplest translator is one giant array: entry number $VPN$ holds that page's frame number. With $v = 20$ VPN bits it needs $2^{20} \approx 1, 048, 576$ entries.

WHY show this. To justify the tree, we must first feel the pain. Each entry (a PTE) is about $4$ bytes:

$2^{20} \times 4 B = 4 MiB per process.$

Most of those million entries point to nothing — a program touches only a few pages. That is wasted RAM, and on 64-bit machines ( $2^{52}$ entries) the flat table is impossible.

PICTURE. A tall table with a handful of used (lavender) rows and a vast sea of empty (grey) rows.

Step 6 — Split the VPN into two indexes: the tree

WHAT. Cut the 20-bit VPN into two 10-bit fields. Now the address has three fields:

$addr = [10 bits i_{1} ∥ 10 bits i_{2} ∥ 12 bits offset]$

$i_{1}$ — outer index: picks a row in the top table (the "directory").
$i_{2}$ — inner index: picks a row in the second-level table the directory pointed to.
$offset$ — unchanged from Step 2.

WHY 10 / 10. $2^{10} = 1024$ entries $\times 4$ bytes $= 4$ KiB — each table is exactly one page. And crucially: if a whole 1024-page region is unused, its inner table is simply never allocated. We only spend memory on branches we actually use — that is the whole saving.

PICTURE. The 32 boxes regrouped into three coloured fields, with 0x00402 decoding to $i_{1} = 1$ , $i_{2} = 2$ .

Step 7 — The walk: follow the pointers to the frame

WHAT. Starting from a base register (CR3 on x86, holding the top table's physical address), we hop down the tree:

WHY two reads. Each level lives in RAM, so each hop is one memory access. Two levels ⇒ two reads before we even touch the data — the price of saving space (Step 9 fixes the speed).

PICTURE. CR3 → top table row 1 → inner table row 2 → frame 0x0009C, then the coral offset 0xABC snaps on the end.

Worked numbers: PFN $= 0x0009C$ , so $PA = (0x0009C ≪ 12) ∣ 0xABC = 0x0009C000 ∣ 0xABC = 0x0009CABC .$

Step 8 — The degenerate case: an unused branch

WHAT. Suppose $L1 [i_{1}]$ has its valid flag = 0 — the directory entry points to nothing.

WHY it matters. This is the normal case for most of the address space, and it is exactly how the tree saves memory. If the outer entry is invalid, there is no inner table at all — the walk stops immediately and the hardware raises a page fault (see Page Faults and Demand Paging). We never wasted 4 KiB on an inner table for pages nobody uses.

PICTURE. The directory with one green (valid) row and 1023 grey (invalid) rows; a grey row's arrow dead-ends into a "no table — fault" marker.

Step 9 — The speed we lost, and how the TLB gives it back

WHAT. The walk cost us $n$ memory reads per translation ( $n = 2$ here). The TLB is a tiny, fast cache remembering recent $VPN \to PFN$ results.

WHY. On a hit, the whole walk is skipped — translation is roughly one cycle. On a miss, we walk, then store the answer. Average cost:

$t_{avg} = t_{TLB} + (miss rate) \times (walk cost)$

$t_{TLB}$ — cost of the fast lookup (always paid).
$miss rate$ — fraction of accesses not found in the TLB.
$walk cost$ — the $n$ memory reads, paid only on a miss.

Because real programs revisit the same few pages constantly, the miss rate is tiny — so the tree keeps its memory savings and nearly recovers flat-table speed. More in TLB and Translation Caching.

PICTURE. Two paths from a VPN: green "TLB hit → PFN" fast lane; longer lavender "TLB miss → walk the tree → fill TLB" path.

The one-picture summary

Everything above in a single diagram: the 32-bit address splits into $i_{1} ∥ i_{2} ∥ offset$ ; $i_{1}$ walks the directory, $i_{2}$ walks the inner table, the PFN joins the untouched offset to name a byte in RAM; the TLB shortcuts the whole walk.

Recall Feynman: tell the whole walk in plain words

A program says "give me byte number 0x00402ABC." The bottom 12 bits, 0xABC, just say where inside a 4 KiB room the byte is — we never touch those. The top 20 bits say which room, but instead of one giant phone book of a million rooms, we split them: the first 10 bits pick a chapter in a small table of contents (the directory), the next 10 bits pick a page within that chapter (the inner table), and that page tells us the real room number in RAM — the frame. Glue the real room number to the "where inside" offset and you have the true byte. If the directory says "no chapter here," we stop — a page fault — and we never printed that chapter, which is how we save paper. Finally, we keep a sticky note (the TLB) of the last few lookups so we don't reread the directory every single time.

Active Recall

Why do the low

p

bits (the offset) never get translated?

Pages and frames are the same size

P

, so byte

k

of a page maps to byte

k

of its frame; only the page/frame number changes.

Where does

p = lo g_{2} P

come from?

You need

lo g_{2} P

bits to name any of the

P

byte-positions inside one page.

In the 10/10/12 split, what does

i_{1}

index vs

i_{2}

i_{1}

indexes the top-level directory;

i_{2}

indexes the inner table the directory points to.

Why choose 10/10 for a 20-bit VPN with 4 KiB pages?

2^{10} \times 4 B = 4

KiB, so each table fits exactly in one page.

For VA 0x00402ABC, PFN 0x0009C: what is the physical address?

(0x0009C << 12) | 0xABC = 0x0009CABC.

What happens when an outer PTE is invalid?

The walk stops, no inner table exists, and a page fault is raised — this is why unused branches cost no memory.

Does the tree improve time or space, and what recovers the other?

It saves space; the TLB recovers the lost translation time.