Virtual Memory Address Translation: Page Tables and TLB Caching in C

How the MMU translates virtual addresses into physical frames, why fixed-size pages eliminate external fragmentation, and how to simulate a Page Table and TLB in C.

virtual_memory_translation


The Illusion of Contiguous Private Memory

Every user-space process on a modern operating system operates under a convenient hardware illusion: it appears to own a vast, contiguous, private address space starting near zero, completely isolated from every other running program.

In physical reality, RAM is shared among dozens of concurrent processes, and the physical memory backing any single process is scattered across non-contiguous hardware framesβ€”or temporarily evicted to disk. The hardware-software mechanism that maintains this illusion is virtual memory paging, mediated by the CPU’s Memory Management Unit (MMU) and the kernel’s page tables.


Why Fixed-Size Pages?

Early operating systems allocated physical memory to processes in contiguous variable-sized blocks. As processes started, grew, and terminated, free physical RAM fractured into small, non-contiguous gapsβ€”external fragmentationβ€”where plenty of total free memory existed, yet no single contiguous region was large enough to fit a new process.

Paging eliminates external fragmentation by decoupling logical contiguity from physical contiguity:

  • The virtual address space seen by a process is partitioned into fixed-size blocks called pages (typically $4\text{ KiB} = 2^{12}\text{ bytes}$).
  • Physical RAM is partitioned into blocks of the exact same size called page frames.

Because every virtual page and every physical frame have the exact same size, any virtual page can map to any available physical frame. This gives the kernel four structural capabilities:

  1. Zero External Fragmentation: Any free physical frame can satisfy any single-page allocation request.
  2. Demand Paging: A process does not need all of its pages in RAM to execute; pages are allocated and loaded only when the CPU actually touches them.
  3. Process Isolation: Because Process A’s page table only contains mappings to Process A’s frames, it is impossible for Process A to even nameβ€”let alone corruptβ€”Process B’s private physical memory.
  4. Zero-Copy Sharing: Shared libraries (libc.so) and Copy-on-Write (fork) map the same physical frame into multiple page tables with read-only permissions.

The Mechanics of Address Translation

With a page size of $2^p$ bytes (for $4\text{ KiB}$ pages, $p = 12$), the hardware splits every $W$-bit virtual address $v$ into two bitfields without performing any division:

  • Virtual Page Number (VPN): The upper $W - p$ bits ($v \gg p$), which index into the process’s page table.
  • Page Offset: The lower $p$ bits ($v \mathbin{&} (2^p - 1)$), which specify the exact byte offset within the page. Because pages and frames are the same size, the offset passes through translation unchanged.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
Virtual Address (v = 12,345 = 0x3039, with 4 KiB pages)
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚  VPN = v >> 12 (3)   β”‚ Offset = v & 0xFFF   β”‚
β”‚       0x00003        β”‚     0x039 (57)       β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
           β”‚                      β”‚
           β–Ό                      β”‚
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”          β”‚
β”‚      Page Table      β”‚          β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€          β”‚
β”‚ VPN 0  β†’  PFN 11     β”‚          β”‚
β”‚ VPN 1  β†’  PFN 5      β”‚          β”‚
β”‚ VPN 2  β†’  PFN 9      β”‚          β”‚
β”‚ VPN 3  β†’  PFN 8      β”‚          β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜          β”‚
           β”‚                      β”‚
           β–Ό                      β–Ό
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚     PFN = 8          β”‚     Offset = 57      β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
Physical Address = (8 << 12) | 57 = 32,825 (0x8039)

When the MMU translates a virtual address:

  1. It indexes the process’s Page Table at entry $\text{VPN}$ to read the Page Table Entry (PTE).
  2. If the PTE’s present bit is 0, the page is not in RAM: the MMU raises a Page Fault exception, trapping into the kernel so the OS can allocate a physical frame, populate the PTE, and retry the instruction.
  3. If present == 1 and access permissions (writable, user) pass, the MMU extracts the Physical Frame Number (PFN), sets the hardware accessed bit (and dirty bit on writes), and forms the physical address:

$$\text{Physical Address} = (\text{PFN} \ll 12) ;\mid; \text{Offset}.$$


Accelerating Lookups with the TLB

There is a glaring performance problem with naive page table translation: the page table itself lives in main memory. If every CPU load or store instruction required reading a Page Table Entry from RAM before reading the target data from RAM, every memory access would take twice as long.

Hardware solves this by placing a small, associative hardware cache inside the MMU called the Translation Lookaside Buffer (TLB). The TLB caches recent $\text{VPN} \to \text{PFN}$ translations along with their permission bits:

  • TLB Hit (< 1 cycle): The MMU translates the address immediately on-chip without touching the page table in RAM.
  • TLB Miss: The hardware page walker (or OS trap handler on software-managed TLBs) reads the Page Table Entry from RAM, inserts the mapping into the TLB, and completes the access.

Because programs exhibit strong spatial and temporal localityβ€”accessing variables on the same $4\text{ KiB}$ stack or heap page hundreds of times in a rowβ€”even a 64-entry TLB achieves hit rates above $99%$.


Simulating an MMU, Page Table, and TLB in C

Let’s implement a complete, self-contained simulation of an MMU with demand-allocated frames, permission enforcement, and a round-robin TLB in modern C.

Instead of returning magic signed -1 values inside unsigned address types, we return an explicit MmuStatus result enum and use bitwise shifts (>> 12, & 0xFFF) exactly as hardware does:

  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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

enum {
    PAGE_SHIFT   = 12,
    PAGE_SIZE    = 1U << PAGE_SHIFT, // 4096 bytes
    OFFSET_MASK  = PAGE_SIZE - 1U,
    NUM_FRAMES   = 64,
    NUM_PAGES    = 128,
    TLB_CAPACITY = 16
};

typedef enum {
    MMU_OK = 0,
    MMU_ERR_OUT_OF_BOUNDS,
    MMU_ERR_PERMISSION,
    MMU_ERR_OUT_OF_MEMORY
} MmuStatus;

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

typedef struct {
    uint32_t vpn;
    uint32_t pfn;
    bool     writable;
    bool     valid;
} TlbEntry;

typedef struct {
    PageTableEntry page_table[NUM_PAGES];
    TlbEntry       tlb[TLB_CAPACITY];
    size_t         tlb_hand;
    uint64_t       tlb_hits;
    uint64_t       tlb_misses;
    uint64_t       page_faults;
    bool           frame_used[NUM_FRAMES];
    uint8_t        phys_ram[NUM_FRAMES * PAGE_SIZE];
} VirtualMemorySystem;

static bool alloc_physical_frame(VirtualMemorySystem *vm, uint32_t *out_pfn) {
    for (uint32_t i = 0; i < NUM_FRAMES; ++i) {
        if (!vm->frame_used[i]) {
            vm->frame_used[i] = true;
            *out_pfn = i;
            return true;
        }
    }
    return false;
}

static bool tlb_lookup(VirtualMemorySystem *vm, uint32_t vpn, uint32_t *out_pfn, bool *out_writable) {
    for (size_t i = 0; i < TLB_CAPACITY; ++i) {
        if (vm->tlb[i].valid && vm->tlb[i].vpn == vpn) {
            *out_pfn      = vm->tlb[i].pfn;
            *out_writable = vm->tlb[i].writable;
            return true;
        }
    }
    return false;
}

static void tlb_insert(VirtualMemorySystem *vm, uint32_t vpn, uint32_t pfn, bool writable) {
    vm->tlb[vm->tlb_hand] = (TlbEntry){
        .vpn      = vpn,
        .pfn      = pfn,
        .writable = writable,
        .valid    = true,
    };
    vm->tlb_hand = (vm->tlb_hand + 1) % TLB_CAPACITY;
}

MmuStatus mmu_translate(VirtualMemorySystem *vm, uint32_t vaddr, bool is_write, uint32_t *out_paddr) {
    const uint32_t vpn    = vaddr >> PAGE_SHIFT;
    const uint32_t offset = vaddr & OFFSET_MASK;

    if (vpn >= NUM_PAGES) {
        return MMU_ERR_OUT_OF_BOUNDS;
    }

    uint32_t pfn      = 0;
    bool     writable = false;

    if (tlb_lookup(vm, vpn, &pfn, &writable)) {
        vm->tlb_hits++;
    } else {
        vm->tlb_misses++;
        PageTableEntry *pte = &vm->page_table[vpn];

        if (!pte->present) {
            // Demand-paging fault handler: allocate a physical frame on first touch
            vm->page_faults++;
            if (!alloc_physical_frame(vm, &pfn)) {
                return MMU_ERR_OUT_OF_MEMORY;
            }
            *pte = (PageTableEntry){
                .pfn      = pfn,
                .present  = 1,
                .writable = 1,
                .user     = 1,
            };
        }
        pfn      = pte->pfn;
        writable = pte->writable;
        tlb_insert(vm, vpn, pfn, writable);
    }

    if (is_write && !writable) {
        return MMU_ERR_PERMISSION;
    }

    vm->page_table[vpn].accessed = 1;
    if (is_write) {
        vm->page_table[vpn].dirty = 1;
    }

    *out_paddr = (pfn << PAGE_SHIFT) | offset;
    return MMU_OK;
}

MmuStatus vm_write_u8(VirtualMemorySystem *vm, uint32_t vaddr, uint8_t val) {
    uint32_t paddr = 0;
    MmuStatus st = mmu_translate(vm, vaddr, true, &paddr);
    if (st == MMU_OK) {
        vm->phys_ram[paddr] = val;
    }
    return st;
}

MmuStatus vm_read_u8(VirtualMemorySystem *vm, uint32_t vaddr, uint8_t *out_val) {
    uint32_t paddr = 0;
    MmuStatus st = mmu_translate(vm, vaddr, false, &paddr);
    if (st == MMU_OK) {
        *out_val = vm->phys_ram[paddr];
    }
    return st;
}

int main(void) {
    VirtualMemorySystem *vm = calloc(1, sizeof(VirtualMemorySystem));
    if (!vm) return EXIT_FAILURE;

    // First touch across 5 distinct pages: triggers 5 TLB misses and 5 demand page faults
    for (uint32_t i = 0; i < 5; ++i) {
        uint32_t vaddr = (i << PAGE_SHIFT) | (i * 8U);
        vm_write_u8(vm, vaddr, (uint8_t)('A' + i));
    }

    // Subsequent reads to the same 5 pages: served entirely by TLB hits
    for (uint32_t i = 0; i < 5; ++i) {
        uint32_t vaddr = (i << PAGE_SHIFT) | (i * 8U);
        uint8_t  val   = 0;
        vm_read_u8(vm, vaddr, &val);
        printf("vaddr 0x%05x -> '%c'\n", vaddr, val);
    }

    printf("Stats: TLB hits = %llu, TLB misses = %llu, Page faults = %llu\n",
           vm->tlb_hits, vm->tlb_misses, vm->page_faults);

    free(vm);
    return EXIT_SUCCESS;
}

Key Takeaways from the Simulation

  • Bitwise Decomposition: Extracting vpn = vaddr >> 12 and offset = vaddr & 0xFFF requires a single cycle in hardware because page sizes are always powers of two.
  • Cold Misses vs. Warm Hits: In main(), the first 5 writes touch 5 unmapped pages, triggering 5 TLB misses and 5 demand page faults. The subsequent 5 reads hit directly in the TLB (TLB hits = 5, TLB misses = 5, Page faults = 5).
  • Context-Switch Flushing: Because TLB entries map process-local VPNs to physical frames, switching to a different process requires either flushing the TLB (on CR3 reload) or tagging TLB entries with an Address Space Identifier (ASID / PCID) so multiple processes can coexist in the TLB without colliding.