Paging vs. Segmentation and Hierarchical Page Tables

Why flat page tables fail at 32-bit and 64-bit scale, how segmentation differs from paging, and how radix multi-level page tables solve the memory overhead.

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 physical base address, a exact limit (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 PropertySegmentationPaging
GranularityVariable-size logical segmentsFixed-size blocks ($4\text{ KiB}$, $2\text{ MiB}$, $1\text{ GiB}$)
External FragmentationSevere: Variable-length segments leave unusable gaps in physical RAM as processes exit.Zero: Any free physical frame fits any virtual page.
Internal FragmentationZero: 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}$
1
2
3
4
5
6
7
8
Paging: Internal Fragmentation Only          Segmentation: External Fragmentation
β”Œβ”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”    β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”
β”‚Frame 0β”‚Frame 1β”‚Frame 2β”‚Frame 3β”‚Frame 4β”‚    β”‚  Proc A    β”‚ Free β”‚  Proc B  β”‚ Free β”‚
β”‚Proc A β”‚Proc B β”‚Proc A β”‚Proc A β”‚ Free  β”‚    β”‚ .text Seg  β”‚ Hole β”‚.data Seg β”‚ Hole β”‚
β”‚ (4 K) β”‚ (4 K) β”‚ (4 K) β”‚(1.5 K)β”‚       β”‚    β”‚  (1.2 MB)  β”‚0.1 MBβ”‚ (0.8 MB) β”‚0.2 MBβ”‚
β””β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β–²β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”˜    β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β–²β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β–²β”€β”€β”€β”˜
                            β”‚                                β”‚                 β”‚
                 2.5 KB internal waste            Scattered external holes in RAM

How x86 Combined Them: Segmented Paging

In 32-bit x86 Protected Mode, Intel layered both schemes into a two-stage pipeline:

  1. Segmentation Unit: Evaluates a logical address (Selector : Offset) against the Global Descriptor Table (GDT), enforces privilege rings (Ring 0 kernel vs. Ring 3 user), and adds the segment base to produce a 32-bit Linear Address.
  2. 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:

1
2
3
4
5
6
7
8
9
31                 22 21                 12 11                  0
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚  Directory Index   β”‚    Table Index      β”‚    Page Offset     β”‚
β”‚      (10 bits)     β”‚      (10 bits)      β”‚     (12 bits)      β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
          β”‚                     β”‚                    β”‚
          β–Ό                     β–Ό                    β–Ό
   Page Directory         2nd-Level Table      4 KiB Physical Frame
  (1024 entries = 4 KB)  (1024 entries = 4 KB)
  1. 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.
  2. 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):

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

enum {
    OFFSET_BITS = 12,
    INDEX_BITS  = 10,
    PAGE_SIZE   = 1U << OFFSET_BITS, // 4096 bytes
    TABLE_SIZE  = 1U << INDEX_BITS,  // 1024 entries per level
    OFFSET_MASK = PAGE_SIZE - 1U,
    INDEX_MASK  = TABLE_SIZE - 1U
};

typedef struct {
    uint32_t pfn      : 20;
    uint32_t present  : 1;
    uint32_t writable : 1;
    uint32_t user     : 1;
} PageTableEntry;

typedef struct {
    PageTableEntry entries[TABLE_SIZE];
} PageTable;

typedef struct {
    PageTable *table;
    bool       present;
    bool       writable;
    bool       user;
} PageDirectoryEntry;

typedef struct {
    PageDirectoryEntry dirs[TABLE_SIZE];
    size_t             allocated_tables;
} AddressSpace;

// Map a virtual page to a physical frame, allocating the 2nd-level table on demand
bool vm_map_page(AddressSpace *as, uint32_t vaddr, uint32_t pfn, bool writable) {
    const uint32_t dir_idx = (vaddr >> (OFFSET_BITS + INDEX_BITS)) & INDEX_MASK;
    const uint32_t tbl_idx = (vaddr >> OFFSET_BITS) & INDEX_MASK;

    PageDirectoryEntry *pde = &as->dirs[dir_idx];
    if (!pde->present) {
        PageTable *new_table = calloc(1, sizeof(PageTable));
        if (!new_table) return false;

        pde->table    = new_table;
        pde->present  = true;
        pde->writable = true;
        pde->user     = true;
        as->allocated_tables++;
    }

    pde->table->entries[tbl_idx] = (PageTableEntry){
        .pfn      = pfn,
        .present  = 1,
        .writable = writable ? 1U : 0U,
        .user     = 1,
    };
    return true;
}

// Hardware-style two-level radix page walk
bool vm_translate(const AddressSpace *as, uint32_t vaddr, uint32_t *out_paddr) {
    const uint32_t dir_idx = (vaddr >> (OFFSET_BITS + INDEX_BITS)) & INDEX_MASK;
    const uint32_t tbl_idx = (vaddr >> OFFSET_BITS) & INDEX_MASK;
    const uint32_t offset  = vaddr & OFFSET_MASK;

    const PageDirectoryEntry *pde = &as->dirs[dir_idx];
    if (!pde->present) {
        return false; // Unmapped 4 MiB region (Level-1 fault)
    }

    const PageTableEntry *pte = &pde->table->entries[tbl_idx];
    if (!pte->present) {
        return false; // Unmapped 4 KiB page (Level-2 fault)
    }

    *out_paddr = (pte->pfn << OFFSET_BITS) | offset;
    return true;
}

void vm_destroy(AddressSpace *as) {
    for (size_t i = 0; i < TABLE_SIZE; ++i) {
        if (as->dirs[i].present) {
            free(as->dirs[i].table);
        }
    }
}

int main(void) {
    AddressSpace as = {0};

    // Map a low code page (0x00401000 -> frame 42) and a high stack page (0xBFFFE000 -> frame 99)
    vm_map_page(&as, 0x00401000U, 42, false);
    vm_map_page(&as, 0xBFFFE000U, 99, true);

    uint32_t paddr = 0;
    if (vm_translate(&as, 0xBFFFE123U, &paddr)) {
        printf("vaddr 0xBFFFE123 -> paddr 0x%08X (2nd-level tables allocated: %zu / %d)\n",
               paddr, as.allocated_tables, TABLE_SIZE);
    }

    vm_destroy(&as);
    return EXIT_SUCCESS;
}

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:

  1. 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.
  2. 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.