Page Tables and Address Translation
Every load and store instruction a program issues names a virtual address. But memory chips only understand physical addresses. Something must translate one into the other. This must happen on every single memory access. It cannot become the slowest part of the computer. This article is about that something: the page table. It is the data structure that maps virtual page numbers to physical frame numbers. The problem is harder than it first looks. A modern 64-bit address space could in principle contain trillions of pages. A naive table indexed by virtual page number would itself be too large to fit in memory. Translation must also be fast. It happens on the critical path of every instruction fetch and every data access. It must also be safe. The mapping is what keeps one process from reading another process's memory. Page tables solve all three problems simultaneously. They exploit sparsity, since most of the address space is unused. They exploit locality, since translations can be cached. They attach protection bits directly to the mapping. So a permission check and an address translation are the same operation. This machinery is invisible to almost all software. Yet it underlies everything from `malloc` to `fork` to containers. When the operating system lazily allocates memory, it is manipulating page tables. The same happens when it delays loading a program's code until touched. It also happens when it isolates one virtual machine from another. When a program dereferences a null pointer, it crashes with a segmentation fault. That crash triggered a page-table lookup that failed by design. This article develops the mechanics precisely. It covers how a virtual address is split into a page number and offset. It explains how multi-level page tables keep the structure small despite huge address spaces. It describes what happens on a page fault. Finally, it shows why the whole scheme is correct. With hardware help, it is also fast enough to use on every access.
- A virtual address splits into a virtual page number (VPN) and a page offset; only the VPN is translated.
- A page table maps each VPN to a physical frame number (PFN); the offset is copied through unchanged.
- Multi-level (hierarchical) page tables avoid allocating table space for unused regions of a huge address space.
- A valid bit marks whether a page is currently mapped to physical memory; if not, a page fault traps to the OS.
- Page-table entries also carry protection bits (read/write/execute, user/supervisor), fusing translation with access control.
- Page tables are the software-visible mechanism; the Translation Lookaside Buffer is the hardware cache that makes them fast in practice.
A page table is a per-process lookup structure, indexed by virtual page number, that returns a physical frame number plus permission bits — turning "where is this data really stored?" into an O(1)-per-level array access instead of a search.
The idea
Virtual memory gives each process the illusion of a private, contiguous address space, independent of where data physically lives in RAM. Address translation is the mechanism that makes this illusion work: it converts a virtual address, generated by the running program, into a physical address, used to actually index memory. Both virtual and physical address spaces are divided into fixed-size chunks. A chunk of virtual address space is a page; the corresponding chunk of physical memory is a frame (or "page frame"). Pages and frames are the same size — typically 4 KiB, though 2 MiB and 1 GiB "huge pages" exist on modern hardware. Because the size is a power of two, an address splits cleanly into two fields: ``` virtual address = [ virtual page number (VPN) | page offset ] ``` The offset (log₂ of the page size, e.g., 12 bits for 4 KiB pages) is never translated — a byte at offset k within a page stays at offset k within whatever frame that page maps to. Only the VPN needs translation, and that's exactly what a page table does: it is an array-like structure, indexed by VPN, whose entries (page table entries, or PTEs) contain a physical frame number (PFN) plus status and permission bits. A PTE typically holds:
- Valid bit (V): is this virtual page currently backed by a physical frame?
- Physical frame number (PFN): if valid, which frame holds this page's data.
- Protection bits: read/write/execute permissions, and often a user/supervisor bit.
- Dirty bit (D): has this page been written since it was loaded?
- Reference/accessed bit (R): has this page been touched recently (used by replacement policies)?
If the valid bit is clear, the VPN has no current physical mapping — perhaps the page was never allocated, has been swapped to disk, or the access is illegal. Any of these causes a page fault: a hardware trap into the operating system, which decides whether to allocate a frame, fetch data from disk, or terminate the process for an illegal access. This is precisely how a single mechanism (table lookup) implements three distinct OS features — dynamic allocation, demand-driven loading, and Memory Protection and Isolation — using the same valid bit and protection bits.
How it works
The naive single-level table. The simplest design is one giant array: `PageTable[VPN]` for every possible VPN, one entry per page in the entire virtual address space. This is correct but wasteful. With 32-bit addresses and 4 KiB pages there are 2²⁰ (about a million) VPNs; with 64-bit addresses and 4 KiB pages there are 2⁵² VPNs — a table with that many entries, at say 8 bytes each, would need petabytes of memory per process, even though a typical process uses only a tiny fraction of its address space. Something smarter is needed.
The key exploit: sparsity. Real programs use only a small, clustered subset of their virtual address space — a stack, a heap, some code and data segments — leaving vast unused gaps. A multi-level (hierarchical) page table turns the flat array into a tree, so that regions of unused address space cost nothing: no leaf tables are allocated for VPN ranges the process never touches. The VPN is split into several fields, one per level: ``` virtual address = [ L1 index | L2 index | L3 index | ... | page offset ] ``` Translation walks the tree top to bottom. A page table base register (in x86, `CR3`) points to the root (level-1) table. Each level's index selects an entry that is a pointer to the next level's table — or, if that region is entirely unallocated, a null/invalid entry, so the walk stops early and a fault is signaled without ever allocating the lower levels. ``` ALGORITHM translate(virtual_address, page_table_base): // Split the virtual address into per-level indices and an offset (L1_idx, L2_idx, L3_idx, offset) = split(virtual_address) table = memory_read(page_table_base) // load level-1 table entry = table[L1_idx] if entry.valid == false: raise PAGE_FAULT(virtual_address, level=1) table = memory_read(entry.next_table_pointer) // load level-2 table entry = table[L2_idx] if entry.valid == false: raise PAGE_FAULT(virtual_address, level=2) table = memory_read(entry.next_table_pointer) // load level-3 table (leaf) entry = table[L3_idx] if entry.valid == false: raise PAGE_FAULT(virtual_address, level=3) if not permission_check(entry, requested_access): raise PROTECTION_FAULT(virtual_address) entry.referenced = true if requested_access == WRITE: entry.dirty = true physical_address = concatenate(entry.PFN, offset) return physical_address ``` ``` ALGORITHM handle_page_fault(virtual_address, level): if address_not_in_any_valid_region(virtual_address): terminate_process("segmentation fault") frame = allocate_physical_frame() if frame == NONE: victim = choose_victim_frame() // e.g. LRU / clock policy if victim.dirty: write_back_to_disk(victim) frame = victim.frame_number invalidate_old_mapping(victim) if page_is_backed_by_disk(virtual_address): read_page_from_disk(virtual_address, into=frame) else: zero_fill(frame) // brand-new page (e.g. heap growth) install_mapping(virtual_address, frame) // set PTE.PFN = frame, PTE.valid = true return // instruction is retried by hardware ``` Two details make this correct and efficient together. First, a missing intermediate table (a null entry at level 1 or 2) means the entire subtree of virtual addresses under it is unmapped — this is what saves memory, since an empty 512-GiB region on x86-64 costs zero leaf-table allocations, only a single null pointer. Second, after a page fault is serviced, the faulting instruction is re-executed from scratch, not resumed mid-instruction; this is why the trap handler must leave the machine state exactly as it was before the fault, and why the walk restarts at level 1 rather than continuing from wherever it stopped.
Complexity & correctness
Time complexity. A page-table walk with k levels performs exactly k sequential memory reads (one per level) plus one final memory access for the data itself — so a k-level walk costs k+1 memory references in the worst case, each of which may itself miss in the cache and go to DRAM. This is why real hardware never relies on a walk for every access: the Translation Lookaside Buffer caches recent VPN→PFN translations so that the overwhelmingly common case is a single associative lookup, not a multi-level walk. Without a TLB, x86-64's four-level tables would nearly quadruple every memory access's latency; with a well-tuned TLB, the walk's average cost is amortized to a small fraction of a percent of accesses, since TLB hit rates typically exceed 99% due to spatial and temporal locality.
Space complexity. This is the entire reason hierarchical tables exist. A single-level table needs one entry for every VPN in the address space — Θ(2^n / page size) entries for an n-bit address space, regardless of how much memory the process actually uses. A k-level hierarchical table needs table entries only along paths that lead to allocated pages: its space usage is proportional to the number of distinct pages actually mapped (plus one intermediate table per populated subtree at each level), not to the size of the address space. Formally, if a process maps m pages, the total table storage is O(m · k) in the worst case (each mapped page potentially requiring a fresh chain of intermediate tables down to a leaf) — a bound governed by the number of live mappings, not by 2ⁿ. This is why hierarchical tables make 64-bit address spaces practical: a process using a few megabytes of memory allocates a few kilobytes of page-table structure, not petabytes.
Correctness argument. The translation scheme is correct if it maintains one invariant per process: the set of (VPN → PFN) pairs reachable by walking the table from the base register, restricted to entries marked valid, equals exactly the set of virtual pages currently backed by physical memory for that process, with permissions matching the OS's intended access policy. Every operation that changes memory mappings — `mmap`, page-fault servicing, page eviction, `munmap`, `fork`'s copy-on-write setup — must update the table so this invariant holds before the corresponding instruction is allowed to retire or before any other process's translation can observe stale state. Two consequences follow directly from the invariant:
- Safety: if VPN has no valid entry (directly, or because an ancestor pointer is null), no physical address can be derived from it — a walk that hits an invalid entry at any level halts with a fault rather than reading garbage. This is what prevents accidental access to arbitrary physical memory: there is no code path from an invalid VPN to a physical address.
- Isolation: because each process has its own base-register value (its own root table), two processes' identical VPNs can map to disjoint PFNs, or one can be valid while the other is not — the invariant is scoped per process, which is exactly what per-process page tables are for.
Tradeoffs to be honest about. Hierarchical tables trade time for space: they save enormous amounts of memory versus a flat table, but a walk that misses the TLB entirely costs multiple sequential dependent memory accesses (each level's read depends on the previous level's result, so they cannot be parallelized). Deeper hierarchies (four or five levels on modern x86-64, to cover 48- or 57-bit address spaces) save more space at the cost of longer worst-case walks. Huge pages (2 MiB, 1 GiB) trade granularity for speed: fewer, larger pages mean fewer TLB entries are needed to cover a given amount of memory, at the cost of more wasted (internally fragmented) memory when an allocation doesn't fill a huge page exactly.
Worked example
Consider a toy 32-bit system with 4 KiB pages and a two-level page table, where the VPN is split into a 10-bit L1 index and a 10-bit L2 index (a simplified analog of classic x86 32-bit paging). ``` virtual address = 0x00403004 binary = 0000 0000 0100 0000 0011 0000 0000 0100 split (10|10|12) = L1=0x001, L2=0x003, offset=0x004 ``` Suppose `CR3` (the base register) points to a root table, and the relevant entries are:
| Level | Index | Entry contents | Valid? |
|---|---|---|---|
| L1 | 0x001 | pointer → L2 table at physical 0x9000, R/W | yes |
| L2 | 0x003 | PFN = 0x00A, R/W, user, dirty=0 | yes |
The walk proceeds: 1. Read root table at `CR3`, index by L1 = 0x001 → get pointer to L2 table at physical address `0x9000`. 2. Read L2 table at `0x9000`, index by L2 = 0x003 → get PFN = `0x00A`, valid, writable, present. 3. Permission check passes (say the access is a user-mode read). 4. Concatenate `PFN=0x00A` with `offset=0x004` (12 bits): physical address = `0x0000A004`. Now suppose instead the L2 entry at index `0x003` had its valid bit clear (the page was swapped out to disk). The hardware walk halts at step 2 and raises a page fault. The OS's fault handler: 1. Inspects the faulting virtual address `0x00403004` and confirms it lies in a legally mapped region (e.g., the process's heap) — not a segmentation violation. 2. Finds a free physical frame (or evicts a victim via its replacement policy, writing it back to disk first if dirty). 3. Reads the page's saved contents back from swap into the new frame, say frame `0x00A` again. 4. Updates the L2 PTE: sets `valid = 1`, `PFN = 0x00A`. 5. Returns from the trap; hardware re-executes the original instruction from scratch, which now walks the table again — this time succeeding, exactly as in the first trace above. This example shows the crucial asymmetry: a successful translation is a pure hardware walk (fast, no OS involvement), while a fault is a full software round-trip (slow, but rare if locality holds and physical memory suffices).
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Confusing "valid bit clear" with "protection violation" | Both cause a trap, but the OS response differs completely | Treating an unallocated page as illegal (or vice versa) crashes valid programs or lets illegal ones through |
| Forgetting to flush/invalidate TLB entries after changing a PTE | The TLB caches old translations independent of the page table | A process (or the OS) reads/writes through a stale mapping — a classic security and correctness bug |
| Assuming a page fault resumes mid-instruction | Some instructions touch multiple pages (e.g., a multi-byte access spanning a page boundary) | Handlers must restart the whole instruction, not just "continue," or partial side effects corrupt state |
| Off-by-one in bit-field splitting for VPN/offset | Page size must exactly match `2^offset_bits`; a miscount shifts every address | Every translation is silently wrong, aliasing arbitrary physical memory |
| Ignoring the dirty bit's cost implications | Every write sets the dirty bit, which the replacement policy relies on | Skipping writeback on eviction of a dirty page silently loses data |
| Assuming translation is purely a hardware concern | The OS installs/removes entries; hardware only walks whatever is currently there | A missing OS-side update (e.g., after `munmap`) leaves stale, exploitable mappings |
Pioneers & history
Page tables emerged from a very concrete pressure: 1960s computers had far less physical memory than the programs people wanted to run, and someone had to make the illusion of "more memory than you have" both automatic and fast.
Origins · 1 minTom Kilburn and how this was discovered
Kilburn led the team that built the Atlas computer, whose "one-level store" (1962) is widely credited as the first working virtual memory system with automatic paging — demand-paged, hardware-assisted, and managed by a resident supervisor program, the direct ancestor of the modern operating-system page-fault handler.
Where this matters
Every general-purpose operating system — Linux, Windows, macOS, the BSDs — relies on hardware page tables to implement process isolation, demand paging, memory-mapped files, and copy-on-write `fork`. Container runtimes (Docker, Kubernetes pods) rely on the same per-process page tables the kernel already provides; virtualization systems add a second layer of translation (guest-physical to host-physical, e.g., Intel EPT or AMD NPT), stacking two page-table walks so a hypervisor can safely multiplex physical memory among virtual machines. Databases and language runtimes exploit `mmap` and page faults to implement lazy file loading and copy-on-write snapshots. Garbage collectors in managed languages (the JVM, .NET) sometimes use page-table protection bits to implement write barriers cheaply, catching writes to specific regions via a deliberately triggered page fault. Understanding page tables is also the necessary foundation for two closely related mechanisms: the Translation Lookaside Buffer, which caches these translations to make them fast in the common case, and the broader topic of Memory Protection and Isolation, which page-table permission bits directly implement.
Ask the tutor: How does a TLB miss actually trigger a hardware page-table walk, and what does the CPU do differently on a TLB hit versus a full walk?
Why not just use one giant page table indexed directly by virtual page number?
Because it wastes enormous amounts of memory. A 64-bit address space with 4 KiB pages has roughly 2⁵² possible virtual pages; a flat table with one entry per VPN (even at just a few bytes each) would require far more storage than exists in any real machine, and it would need this much space per process, even for processes that use only a few megabytes. Multi-level page tables instead allocate structure only for the parts of the address space actually in use — an entirely unmapped gigabyte-sized region costs a single null pointer at some intermediate level, not millions of empty entries. The tradeoff is that translation now requires several sequential memory reads (one per level) instead of one, which is exactly the problem the Translation Lookaside Buffer is built to hide.
What exactly triggers a page fault, and is it always an error?
A page fault is any hardware trap raised when a page-table walk cannot complete successfully — because the valid bit is clear at some level, or because the requested access violates the entry's protection bits. It is not inherently an error condition. The OS's fault handler distinguishes several cases: a legitimate but not-yet-allocated page (e.g., first touch of heap or stack memory, handled by allocating a frame and zero-filling it), a page that was swapped to disk (handled by reading it back in), or a genuinely illegal access outside any region the process is permitted to touch (handled by delivering a segmentation-violation signal and typically terminating the process). The same trap mechanism serves all three; only the handler's logic differs.
What is the difference between a page table entry's valid bit and its protection bits?
The valid bit answers a binary question: does this virtual page currently correspond to any physical frame at all? If it is clear, there is no PFN to use, and the walk must fault regardless of what access was requested. Protection bits (read/write/execute, user/supervisor) apply only once a page is valid — they answer a different question: given that this page maps to a real frame, is this particular kind of access allowed? A valid, read-only page correctly permits loads but faults on stores; an invalid page faults on every access type, because there is no frame to check permissions against in the first place.
How many levels does a real page table have, and why not just one or two?
x86-64 processors commonly use four levels (five with newer extensions for even larger address spaces), each level's index typically 9 bits wide over a 4 KiB page. The number of levels is a tradeoff between space and walk latency: fewer levels means each level's table must cover a wider range of addresses, which (if kept sparse) requires proportionally larger index fields and more entries per table, increasing memory pressure and cache pressure per table. More levels shrink each table but lengthen every full walk. Four to five levels reflects decades of tuning for typical 64-bit address space usage patterns, keeping tables cache-friendly (a table page is usually exactly one page in size) while the Translation Lookaside Buffer absorbs most of the walk cost in practice.
Do page tables have anything to do with the CPU cache, or are they entirely separate systems?
They are conceptually separate but interact constantly. Page tables translate addresses; caches store data indexed by addresses (virtual or physical, depending on cache design). Every level of a page-table walk is itself a memory read, which can hit or miss in the ordinary data cache — a page-table walk on a cold TLB may itself benefit from cache locality if the relevant table pages were recently accessed. Some CPU caches are physically indexed and physically tagged, meaning a translation must complete before the cache lookup can even begin; this dependency is one more reason the Translation Lookaside Buffer exists, since waiting on a multi-level walk before every cache access would be prohibitively slow.
Why do page table entries need a dirty bit and a reference/accessed bit at all?
Both bits let hardware do cheap bookkeeping that the OS would otherwise have to compute expensively in software. The reference (accessed) bit is set automatically whenever a page is read or written; the OS periodically inspects and clears it to approximate which pages are "recently used," feeding page-replacement policies like clock/LRU-approximation without tracking every single access explicitly. The dirty bit is set automatically on any write, telling the OS whether a page's contents differ from what's stored on disk (or wherever it was originally loaded from); on eviction, a clean page can simply be discarded and reloaded later, while a dirty page must be written back first. Without these bits, the OS would need to trap on every access just to gather this information, which would defeat the purpose of hardware-assisted virtual memory entirely.
How do page tables relate to memory protection between processes?
Each process has its own page table (its own root pointed to by its own saved base-register value), so the same virtual address in two different processes can map to entirely different physical frames — or be valid in one and invalid in the other. This per-process indirection is the entire mechanism behind process isolation: a process can never construct a physical address that lands in another process's memory, because there is no virtual address in its own table that maps there. This is the foundation that Memory Protection and Isolation builds on: permission bits inside each PTE add a second layer (read/write/execute/user-supervisor) on top of this per-process spatial separation.