Address Spaces & Page Tables
Virtual Memory Internals · OS Core Internals track
6 min read
In this module
Virtual Addresses Are a Lie
Every pointer your program uses is a virtual address. It doesn't refer to a physical location in RAM. The CPU's memory management unit (MMU) translates each virtual address into a physical one on every single memory access. This translation is driven by a data structure called a page table, the foundation of modern memory management.
The illusion is powerful: every process thinks it owns the entire address space. In reality, physical memory is shared, fragmented, and constantly shuffled around by the kernel.
Pages: The Unit of Memory
The kernel doesn't manage memory byte by byte. It works in fixed-size blocks called pages. On x86-64 the standard page size is 4 KB (4096 bytes), and every virtual-to-physical mapping operates at page granularity.
A virtual address splits into two parts: the upper bits pick a page, and the lower 12 bits give the page offset, the position within that 4 KB page.
Four-Level Page Tables on x86-64
With a 48-bit virtual address space (the practical limit on x86-64, giving 256 TB of addressable memory), a flat page table would be absurdly large. x86-64 uses a four-level hierarchical page table instead:
- PML4 (Page Map Level 4) - the root table, pointed to by the CR3 register
- PDPT (Page Directory Pointer Table)
- PD (Page Directory)
- PT (Page Table) - the final level, containing the physical page address
x86-64 splits a 48-bit virtual address into four 9-bit indices (one per page table level) plus a 12-bit page offset. Each level holds 512 entries (2^9), and only the levels that map actual memory need to exist. The structure stays sparse and memory-efficient.
The translation process, the page table walk, goes like this:
Each page table entry also carries permission bits: whether the page is readable, writable, executable, accessible from user mode, or present in physical memory at all. These bits enforce memory protection at the hardware level.
Why Hierarchical?
A flat page table for a 48-bit address space would need 2³⁶ entries of 8 bytes each: 512 GiB of page table, per process, before a single byte of real data. Hopeless. The hierarchical structure is sparse: only the page table entries that map actual memory need to exist. A process using 100 MB of virtual memory only needs page table entries covering those 100 MB, not the full 256 TB.
This sparsity is what makes virtual memory practical on real hardware.
Worked Example: Walking One Address
Take an address you might see in a libc mapping: 0x00007f3a1c2805a0. The top 16 bits are just copies of bit 47 (zeros here), so the 48 bits that matter split like this:
| Bits | Field | Value | Meaning |
|---|---|---|---|
| 47-39 | PML4 index | 254 | Entry 254 of the table CR3 points at |
| 38-30 | PDPT index | 232 | Entry 232 of the PDPT that entry led to |
| 29-21 | PD index | 225 | Entry 225 of the page directory |
| 20-12 | PT index | 128 | Entry 128 of the final page table |
| 11-0 | Offset | 0x5a0 | Byte 1,440 within the 4 KB page |
The walk reads four 8-byte entries from memory, one per level. Each entry holds the physical address of the next table, plus permission bits. The fourth gives the physical frame, and the offset 0x5a0 is added to it unchanged. That's four extra memory reads for one load, which is exactly why the TLB, the cache of finished translations, matters so much: a TLB hit skips all four.
You can do the split yourself without converting to binary. The offset is always the last three hex digits. For the indices, shift right and mask: (addr >> 39) & 0x1ff, (addr >> 30) & 0x1ff, (addr >> 21) & 0x1ff and (addr >> 12) & 0x1ff, where 0x1ff is nine one-bits.
Predict: a brand-new process maps exactly one 4 KB page. How much memory do its page tables need to map it?
16 KB: one 4 KB table at each of the four levels. Every level needs at least one table to hold a single entry, even though that table has room for 512. So mapping the first page costs four times its own size. The good news is that the next 511 pages in the same 2 MB region need no new tables at all, which is why the overhead disappears in real programs. Some systems use 2 MB "huge pages", where the walk stops at the page directory and skips the last level entirely.
Newer Intel and AMD processors also support five-level paging, which adds another 9-bit level on top and stretches virtual addresses to 57 bits. Linux turns it on only when the hardware supports it and the kernel is built for it; the walk works the same way, with one more step.
Explore the Walk
The walker below is a scaled-down four-level machine: each index is 4 bits instead of 9, so the whole virtual address is 28 bits (seven hex digits) with the same 12-bit offset. It's loaded with the last seven hex digits of the worked example, 0x0C2805A0. With 4-bit indices, each level's index is simply one hex digit (C, 2, 8, 0) and the offset is still 0x5A0. Step through the walk and confirm that the offset passes through untouched while each level picks one entry and leads to the next. The physical frames come from the tool's made-up tables, not a real machine.
Page Table Walker (4-level, 4096B pages)
Page Table Entries in Practice
Each page table entry on x86-64 is 8 bytes (64 bits). Beyond the physical address, the flags that matter most are:
- Present (P) - is this page in physical memory? If not, accessing it triggers a page fault.
- Read/Write (R/W) - is the page writable or read-only?
- User/Supervisor (U/S) - can user-mode code access this page?
- No Execute (NX) - can code on this page be executed? This bit is the hardware foundation of DEP/NX protection.
These hardware-enforced permissions are the basis of memory safety, exploit mitigations, and kernel self-protection. Understanding how addresses translate is step one to understanding how those protections come under attack.