How do multi-level page tables work? Calculate the size of the page tables.
Short answer: A single flat page table for a large address space is huge and mostly empty, so the virtual page number is split into several indexes. The first index selects an entry in a top-level table, which points to a second-level table, and so on; the last level gives the physical frame. Tables for unused parts of the address space are simply not allocated, which saves most of the memory.
Worked example: 32-bit addresses, 4 KB pages, 4-byte entries
- Offset: 4 KB = 2¹² → 12 bits.
- Page number: 32 − 12 = 20 bits → 2²⁰ = 1,048,576 pages.
- Single-level table: 2²⁰ entries × 4 B = 4 MB per process, even for a tiny program.
- Two-level, 10 + 10 bits (classic 32-bit x86 and ARMv7 short-descriptor style):
- Level 1: 2¹⁰ = 1024 entries × 4 B = 4 KB (one page).
- Each level-2 table: 1024 entries × 4 B = 4 KB, and it maps 1024 × 4 KB = 4 MB of address space.
- A process using 8 MB of code and data at the bottom plus one stack page at the top needs: 1 level-1 table + 2 level-2 tables (for 8 MB) + 1 level-2 table (for the stack) = 4 pages = 16 KB instead of 4 MB.
- Worst case (every page mapped): 4 KB + 1024 × 4 KB = 4 MB + 4 KB, slightly more than a single-level table. Multi-level tables save space only because real address spaces are sparse.
ARM64 with 4 KB granule and 48-bit virtual addresses
47 39 38 30 29 21 20 12 11 0
[ L0 idx ][ L1 idx ][ L2 idx ][ L3 idx ][ offset ]
9 bits 9 bits 9 bits 9 bits 12 bits
Each table holds 512 entries of 8 bytes = exactly 4 KB. Higher-level entries can also be block entries that map 1 GB (L1) or 2 MB (L2) directly ("huge pages"), skipping the lower levels.
Cost: each extra level adds a memory access to every TLB miss. Four levels means up to four reads before the real access, which is why TLBs and page-walk caches are essential.
Formula to remember: with page size 2ᵖ and entry size 2ᵉ, each table has 2^(p−e) entries, so each level resolves p − e bits. For 4 KB pages and 8-byte entries: 12 − 3 = 9 bits per level.