Worked examples — Page tables and multi-level paging

This page drills the parent topic through concrete numbers. We touch every kind of input the translation machinery can face: normal addresses, addresses that sit exactly on a page boundary, the very first and very last byte of a page, invalid (unmapped) entries, single-level vs multi-level walks, a 64-bit monster, a word problem, and an exam twist. Prerequisites we lean on: Virtual Memory, Bit Manipulation and Masking, and TLB and Translation Caching.

The scenario matrix

Every cell here is a distinct situation the reader must survive. Each example below is tagged with the cell(s) it covers.

Setup we reuse

Unless a problem says otherwise: 32-bit virtual addresses ($V=32$), page size $P=4\text{ KiB}=2^{12}$ bytes, so offset bits $p={\log }_2{2}^{12}=12$, and VPN bits $v=32-12=20$. Two-level split is 10 / 10 / 12 (outer index $i_1$ = 10 bits, inner index $i_2$ = 10 bits, offset = 12 bits).

Figure s01 shows this chop applied to a 32-bit address: the same knife-cut we will perform, by hand, in every example below. Notice the orange offset field on the right — that is the slice that rides through untranslated in Examples A–I.

Example A — Normal single-level translation (Cell A)

Steps.

1. offset $=\text{0x00003ABC}\&\text{0xFFF}=\text{0xABC}$. Why this step? The low 12 bits name a byte inside the page; they ride through untranslated.
2. VPN $=\text{0x00003ABC}\gg 12=\text{0x00003}=3$. Why this step? The remaining high bits say which page — the key into the table.
3. Look up table[3] → PFN = 0x00042, valid, so translation succeeds. Why this step? The array position is the VPN; the stored value is the frame.
4. PA $=(\text{PFN}\ll 12)|\text{offset}=(\text{0x00042}\ll 12)|\text{0xABC}=\text{0x00042ABC}$. Why this step? Reassemble: frame number in the high bits, original offset in the low bits.

Verify: the low three hex digits ABC are unchanged (offset untouched — exactly the parent's rule). Only the page portion 003 → 042 moved. $0\text{x}42\times 4096+0\text{xABC}=270336+2748=273084=\text{0x42ABC}$. ✓

Example B — Offset zero, page boundary (Cell B, F-flavour)

Steps.

1. offset $=\text{0x7000}\&\text{0xFFF}=\text{0x000}=0$. Why this step? 0x7000 is a multiple of 0x1000 = 4096 = $P$, so it sits exactly at the start of a page. Offset 0 means "byte 0 of the frame."
2. VPN $=\text{0x7000}\gg 12=\text{0x7}=7$. Why this step? Discarding the low 12 bits leaves the page number — the key we index the table with, exactly as in Example A.
3. Look up table[7] → PFN 0x00100. Why this step? The array position 7 is the VPN; the stored value 0x100 is the frame that page lives in.
4. PA $=(\text{0x00100}\ll 12)|0=\text{0x00100000}$. Why this step? Reassemble: slide the PFN into the high bits, drop the offset (here 0) into the low bits.

Verify: a boundary address maps to a boundary address — PA also ends in 000. $0\text{x}100\times 4096=1048576=\text{0x100000}$. ✓ This is the smallest address in that frame.

Example C — Last byte of a page, offset = P−1 (Cell C)

Steps.

1. offset $=\text{0x7FFF}\&\text{0xFFF}=\text{0xFFF}=4095=P-1$. Why this step? 0xFFF is the largest value 12 bits can hold — the very last byte of the page.
2. VPN $=\text{0x7FFF}\gg 12=\text{0x7}=7$. Why this step? Crucial: even though the address looks big, everything up to 0x7FFF still belongs to page 7. The next byte, 0x8000, is the first byte of page 8.
3. table[7] → PFN 0x00100. Why this step? Same page number 7 as Example B, so it indexes the same row and yields the same frame — the maximum offset did not change which page we're in.
4. PA $=(\text{0x00100}\ll 12)|\text{0xFFF}=\text{0x00100FFF}$. Why this step? Reassemble: the frame is unchanged from Example B; only the offset (now 0xFFF) rides into the low bits, landing us at the last byte of the frame.

Verify: Example B (0x7000) and Example C (0x7FFF) share PFN 0x100; their physical addresses differ only in the offset 000 vs FFF. Both stay inside frame 0x100. Add one more byte (0x8000) and the VPN becomes 8 — a different table row. ✓ This is the off-by-one that traps people: 0x8000 is not in page 7.

Example D — Two-level walk, all fields non-zero (Cell D)

Steps.

1. offset $=\text{0x00402ABC}\&\text{0xFFF}=\text{0xABC}$. Why this step? Low 12 bits, as always.
2. VPN $=\text{0x00402ABC}\gg 12=\text{0x00402}=1026$. Why this step? We now have the 20-bit page number that we must split again.
3. inner index $i_2=(\text{VPN}\gg 0)\&\text{0x3FF}=1026\&1023=2$. Why this step? The inner index is the lowest VPN slice, so shift $s=0$ (nothing below it); 0x3FF keeps its 10 bits.
4. outer index $i_1=(\text{VPN}\gg 10)\&\text{0x3FF}=(1026\gg 10)\&1023=1$. Why this step? The outer index sits above the 10 inner bits, so shift $s=10$ first, then keep 10 bits — the high slice of the VPN.
5. Walk: read L1[1] → gives L2 base; read L2[2] → PFN 0x0009C. Why this step? Two memory accesses, one per level, matching the parent's cost formula ($n$ reads for $n$ levels).
6. PA $=(\text{0x0009C}\ll 12)|\text{0xABC}=\text{0x0009CABC}$. Why this step? Reassemble, exactly as in the single-level case: the final-level PFN slides into the high bits, the untranslated offset drops into the low bits — the tree only changed how we found the PFN, not how we build the address from it.

Verify: Reassemble the VPN from the two indices: $(i_1\ll 10)|i_2=(1\ll 10)|2=1024+2=1026=\text{0x402}$. ✓ Matches the parent note's worked walk exactly.

Figure s02 draws this exact walk as a tree: L1[1] (plum) hands us the L2 base, L2[2] (teal) hands us frame 0x9C (orange), and the offset 0xABC selects the byte inside it. Follow the two arrows — each one is a memory read.

Example E — Invalid PTE: translation fails at either level (Cell E)

Steps (Case E1 — top-level fault).

1. offset $=\text{0x00801000}\&\text{0xFFF}=0$. Why this step? Same first move as every example: peel off the low 12 bits so the rest is a pure page number, whether or not it turns out to be mapped.
2. VPN $=\text{0x00801000}\gg 12=\text{0x00801}=2049$. Why this step? We need the page number to compute the indices — a missing mapping is discovered during the walk, so we still chop first.
3. $i_1=(2049\gg 10)\&\text{0x3FF}=2$; $i_2=(2049\gg 0)\&\text{0x3FF}=1$. Why this step? Same chop as Example D — the mechanics don't change just because an entry is missing.
4. Read L1[2]: valid = 0. Stop immediately — there is no L2 table to walk into. Why this step? The parent's "omit empty subtrees" insight lives here — an unallocated branch is exactly an invalid top-level entry. We never even read L2.

Steps (Case E2 — second-level fault).

1. Chop as in Example D: $i_1=1$, $i_2=2$, offset 0xABC.
2. Read L1[1]: valid = 1 → gives a real L2 base. Proceed. Why this step? The top branch exists, so we take the second memory read — unlike E1.
3. Read L2[2]: valid = 0. Stop. The L2 table exists but this leaf maps no frame. Why this step? Sparsity can occur at any level; a present inner table may still have unmapped rows.
4. Hardware raises a page fault — there is no PFN to return, so the CPU cannot build a PA and must hand control to the OS. Why this step? A valid = 0 leaf means "this virtual page currently maps to no frame"; the only correct response is to signal the OS (map a frame on demand, or kill the process) rather than fabricate an address.

Both cases: the OS decides — map a new frame (demand paging) or kill the process (illegal access). See Page Faults and Demand Paging.

Verify: neither case yields a PA — that absence is the answer. E1 costs 1 table read before faulting; E2 costs 2. A valid-bit of 0 must never be treated as PFN 0 (that would silently read frame 0). ✓ Together E1 and E2 cover every fault point a two-level walk has.

Example F — The degenerate address 0x0 (Cell F)

Steps.

1. offset $=0\&\text{0xFFF}=0$. Why this step? Even for the smallest address we still peel off the offset — the recipe never changes, and confirming offset = 0 tells us we're at the very first byte of a page.
2. VPN $=0\gg 12=0$, so $i_1=0$, $i_2=0$. Why this step? Zero shifts and masks to zero — the smallest possible everything.
3. L1[0] → L2[0] → PFN 0x00000. Why this step? We still walk both levels: index 0 of the root points to an L2 table, index 0 of which stores the frame — zero indices are ordinary array positions, not a special case.
4. PA $=(0\ll 12)|0=0$. Why this step? Reassemble as always; with PFN 0 and offset 0 the high and low bits are both empty, so the physical address is 0.

Verify: PA = 0x0. Note this is a choice of the mapping, not a law: virtual 0 maps to physical 0 only because that PTE happened to store PFN 0. In real systems address 0 is usually left unmapped (so null-pointer dereferences fault) — which would instead be an Example-E situation. ✓ Both readings are legitimate; the difference is entirely in the valid bit.

Example G — 64-bit, 4-level walk (Cell G)

Steps.

1. offset $=\text{addr}\&\text{0xFFF}=\text{0xB04}$. Why this step? Page size is still 4 KiB, so $p=12$ regardless of address width.
2. VPN $=\text{addr}\gg 12$. Each level now uses a 9-bit slice, so the mask is 0x1FF ($2^9-1$) and the shift $s$ jumps by 9 per level (generalising the "$s=10(k-1)$" rule to 9-bit levels: $s=9(k-1)$, counting from the bottom):
   • $i_4=(\text{VPN}\gg 0)\&\text{0x1FF}$ — lowest slice, $s=0$, nothing below it.
   • $i_3=(\text{VPN}\gg 9)\&\text{0x1FF}$ — skip the 9 bits of $i_4$ first.
   • $i_2=(\text{VPN}\gg 18)\&\text{0x1FF}$ — skip the 18 bits of $i_4,i_3$.
   • $i_1=(\text{VPN}\gg 27)\&\text{0x1FF}$ — skip the 27 bits below it. Why this step? Same knife as the 32-bit case, just narrower teeth. Each shift discards exactly the index bits below the slice we want, then the mask keeps the 9 bits we want and drops everything above. $9\times 4+12=48$ bits total — the split must exhaust the address.
3. Numerically this gives $i_1=497,i_2=48,i_3=336,i_4=337$ (computed in Verify).
4. Walk L1[i1] → L2[i2] → L3[i3] → L4[i4] = 4 memory reads, then 1 more for the data. Why this step? Parent's rule: $n$-level table ⇒ $n$ reads per translation before caching. Here $n=4$, so a TLB miss is expensive — exactly why TLB and Translation Caching matters more as levels grow.

Verify: $9\cdot 4+12=48$ = $V$ ✓. And reassembling: $((((i_1\ll 9|i_2)\ll 9|i_3)\ll 9|i_4)\ll 12)|\text{0xB04}$ should return the original 48-bit address (checked below). ✓

Example H — Word problem: how much memory did the tree save? (Cell H)

Steps.

1. Flat table size $=2^{20}\text{entries}\times 4\text{B}=4194304\text{B}=4\text{MiB}$. Why this step? One entry per possible page, whether used or not.
2. Two-level: top table = always 1 table of 4 KiB. Why this step? The root must exist to hold pointers.
3. Two-level: inner tables = 3 (worst case, one per distinct top-level entry) × 4 KiB = 12 KiB. Why this step? Each used branch gets exactly one inner table; the other 1021 top entries are invalid → no table.
4. Total tree $=4\text{KiB}+12\text{KiB}=16\text{KiB}$.
5. Savings $=4\text{MiB}-16\text{KiB}=4096\text{KiB}-16\text{KiB}=4080\text{KiB}$.

Verify: ratio $=4194304/16384=256\times$ smaller. The tree uses about 0.39% of the flat table's memory here. ✓ Units check: bytes vs bytes throughout. If all 3 pages shared one top entry, only 1 inner table is needed → 8 KiB total (even cheaper) — the worst case above bounds it.

Example I — Exam twist: run translation backwards (Cell I)

Steps.

1. Extract offset from PA $=\text{0x0009CABC}\&\text{0xFFF}=\text{0xABC}$. Why this step? The offset is shared by virtual and physical addresses — the one field we can trust across the divide.
2. The trap: the PA gives us the frame number 0x9C, but not the VPN. Many virtual pages can map to the same frame (shared memory). So PA alone is insufficient — we needed the walk info $(i_1,i_2)$. Why this step? Translation is many-to-one in general; reversing needs extra data.
3. Rebuild VPN from the walk indices $=(i_1\ll 10)|i_2=(1\ll 10)|2=1026=\text{0x402}$. Why this step? The indices are the VPN, split; concatenating them restores it.
4. Rebuild virtual address $=(\text{VPN}\ll 12)|\text{offset}=(\text{0x402}\ll 12)|\text{0xABC}=\text{0x00402ABC}$. Why this step? This is the reassemble move of our chop→look up→reassemble recipe, run in reverse: having recovered the VPN in Step 3, we slide it left by $p=12$ to put it back in the page-number position and drop the untranslated offset into the low bits — exactly the inverse of the Step-1 chop.

Verify: this is exactly Example D's original virtual address — the round trip closes. ✓ Forward: 0x00402ABC → 0x0009CABC; backward (with walk data): 0x0009CABC + $(i_1,i_2)$ → 0x00402ABC. The offset ABC survives both directions untouched.

Active Recall