Two Philosophies of Memory Abstraction
Operating systems have historically relied on two distinct hardware mechanisms to map virtual addresses to physical RAM: segmentation and paging. Understanding their trade-offs explains both the legacy of the Intel x86 architecture and the design of modern 64-bit radix page tables.
Segmentation vs. Paging
- Segmentation partitions an address space into variable-length logical units matching the programmer’s view of a binary:
.text(executable code),.rodata,.data/.bss, the heap, and the stack. Each segment descriptor stores a physicalbaseaddress, a exactlimit(length in bytes), and access permissions (rwx). - Paging partitions both virtual and physical memory into fixed-size pages and frames (typically $4\text{ KiB}$), completely agnostic to program structure.
| Architectural Property | Segmentation | Paging |
|---|---|---|
| Granularity | Variable-size logical segments | Fixed-size blocks ($4\text{ KiB}$, $2\text{ MiB}$, $1\text{ GiB}$) |
| External Fragmentation | Severe: Variable-length segments leave unusable gaps in physical RAM as processes exit. | Zero: Any free physical frame fits any virtual page. |
| Internal Fragmentation | Zero: Segments are sized to the exact byte limit. | Minor: Up to $4\text{ KiB} - 1\text{ bytes}$ wasted on the final page of a mapping. |
| Hardware Translation | $\text{PA} = \text{Base}[\text{seg}] + \text{Offset}$ (faults if $\text{Offset} \ge \text{Limit}[\text{seg}]$) | $\text{PA} = (\text{PageTable}[\text{VPN}] \ll 12) \mid \text{Offset}$ |
| |
How x86 Combined Them: Segmented Paging
In 32-bit x86 Protected Mode, Intel layered both schemes into a two-stage pipeline:
- Segmentation Unit: Evaluates a logical address
(Selector : Offset)against the Global Descriptor Table (GDT), enforces privilege rings (Ring 0kernel vs.Ring 3user), and adds the segment base to produce a 32-bit Linear Address. - Paging Unit: Translates that 32-bit Linear Address into a Physical Address through the page tables.
When AMD introduced 64-bit x86-64 (Long Mode), hardware segmentation was largely retired: segment bases for CS, DS, ES, and SS are forced to 0 in hardware (with FS and GS retained as base registers for fast Thread-Local Storage), leaving paging as the sole mechanism for isolation and protection.
Why Flat Page Tables Collapse at Scale
Suppose we use a simple, single-level linear array for each process’s page table. How much physical memory does the page table itself consume?
- 32-bit Address Space ($4\text{ KiB}$ pages): There are $2^{32} / 2^{12} = 2^{20} = 1{,}048{,}576$ virtual pages per process. At $4\text{ bytes}$ per Page Table Entry (PTE), every single process requires $4\text{ MiB}$ of contiguous RAM just to hold its page tableβeven a tiny daemon that only uses $16\text{ KiB}$ of actual memory! With 200 running processes, $800\text{ MiB}$ of RAM vanishes into empty PTEs.
- 64-bit Address Space (48-bit canonical addresses): There are $2^{48} / 2^{12} = 2^{36}$ virtual pages per process. At $8\text{ bytes}$ per PTE, a single flat page table would require $512\text{ GiB}$ of physical RAM per process.
The root cause is that virtual address spaces are extremely sparse: a typical process uses a few pages at the bottom of memory (code/heap) and a few pages at the very top (stack/shared libraries), while $99.99%$ of the address space in between is unmapped.
Hierarchical (Multi-Level) Radix Page Tables
Instead of allocating one giant linear array covering the entire virtual address space, modern architectures page the page table itself into a fixed-depth radix tree.
Consider classic 32-bit two-level paging (and by extension, 4-level PML4 paging on x86-64). A 32-bit virtual address is partitioned into three bitfields:
| |
- Top-Level Page Directory ($10\text{ bits} = 1024\text{ entries}$): Always allocated ($4\text{ KiB}$ total). Entry $i$ covers a contiguous $4\text{ MiB}$ region of virtual memory and points to a second-level Page Table.
- Second-Level Page Tables ($10\text{ bits} = 1024\text{ entries}$): Allocated on demand. If a process never touches virtual addresses in a given $4\text{ MiB}$ range, the corresponding Page Directory Entry has
present = 0, and the second-level table is never allocated.
A minimal process using only code and stack now needs just three $4\text{ KiB}$ pages ($12\text{ KiB}$ total) for its page tables instead of $4\text{ MiB}$βa $340\times$ reduction in metadata overhead.
Implementing a Two-Level Radix Page Table in C
Below is a clean, self-contained implementation of a 32-bit two-level page walker in C, demonstrating on-demand allocation of second-level page tables (vm_map_page) and hardware-style radix bit-slicing (vm_translate):
| |
Scaling to 64-Bit: 4-Level Paging, Huge Pages, and Inverted Tables
On 64-bit x86-64 systems, the exact same radix design extends to 4 levels (48-bit virtual addresses: $9 + 9 + 9 + 9 + 12$ bits) or 5 levels (57-bit virtual addresses). However, deeper trees introduce a new cost: a TLB miss on a 4-level page table requires 4 sequential memory reads to walk the tree.
Modern systems mitigate page-walk latency using two techniques:
- Page-Walk Caches (PWC): Dedicated MMU caches that store intermediate pointers from upper levels of the radix tree (
PML4,PDPT,PD), cutting most 4-level walks down to 1 or 2 memory accesses. - Huge Pages ($2\text{ MiB}$ and $1\text{ GiB}$): By setting the
PS(Page Size) bit directly inside a Level-2 Page Directory Entry, the page walk terminates early and maps a contiguous $2\text{ MiB}$ frame with a single TLB entry. For large contiguous allocations (database buffer pools, JVM heaps, hypervisor guest RAM), $2\text{ MiB}$ huge pages reduce TLB pressure by $512\times$ and eliminate the lowest level of page-table memory overhead entirely.