Skip to main content
Be Bitwise

Address Spaces & Page Tables

Virtual Memory Internals · OS Core Internals track

6 min read

Part ofSystems Programming Companion, week 10

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:

  1. PML4 (Page Map Level 4) - the root table, pointed to by the CR3 register
  2. PDPT (Page Directory Pointer Table)
  3. PD (Page Directory)
  4. PT (Page Table) - the final level, containing the physical page address
Key Concept

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:

BitsFieldValueMeaning
47-39PML4 index254Entry 254 of the table CR3 points at
38-30PDPT index232Entry 232 of the PDPT that entry led to
29-21PD index225Entry 225 of the page directory
20-12PT index128Entry 128 of the final page table
11-0Offset0x5a0Byte 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)

Bit-field breakdown
VPN1
1100
= 12 (0xC)
VPN2
0010
= 2 (0x2)
VPN3
1000
= 8 (0x8)
VPN4
0000
= 0 (0x0)
Offset
010110100000
= 1440 (0x5A0)
Level 1 Page Table
0→PPN 0x16
1→invalid
2→invalid
3→PPN 0x62
4→PPN 0xBE
5→PPN 0xF6
6→PPN 0x2A
7→PPN 0x82
8→PPN 0x56
9→PPN 0x2E
10→PPN 0xFA
11→PPN 0x22
12→PPN 0x4E
13→invalid
14→invalid
15→PPN 0xC2
Level 2 Page Table
0→PPN 0x32
1→PPN 0xFA
2→PPN 0x26
3→PPN 0x4E
4→PPN 0x92
5→PPN 0x1A
6→PPN 0xCE
7→invalid
8→PPN 0x72
9→PPN 0x4A
10→PPN 0xE6
11→invalid
12→PPN 0x52
13→PPN 0x6A
14→PPN 0x3E
15→PPN 0xE6
Level 3 Page Table
0→PPN 0x4E
1→PPN 0xE6
2→invalid
3→PPN 0xAA
4→invalid
5→PPN 0x3E
6→PPN 0xE2
7→invalid
8→PPN 0x1E
9→PPN 0x66
10→PPN 0xC2
11→PPN 0xFA
12→PPN 0xB6
13→PPN 0x4E
14→PPN 0x22
15→invalid
Level 4 Page Table
0→PPN 0x6A
1→PPN 0xC2
2→PPN 0xFE
3→PPN 0xB6
4→PPN 0x4A
5→PPN 0x22
6→PPN 0x86
7→PPN 0xEE
8→PPN 0x3A
9→invalid
10→PPN 0x2E
11→PPN 0xD6
12→PPN 0x9A
13→invalid
14→invalid
15→PPN 0xBE
Ready

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.