Memory Management: Paging, Virtual Memory, and the MMU

When your C program calls malloc(4096), the pointer that comes back doesn’t point to a physical location on your RAM sticks. It points into a virtual address space — a private, process-specific mapping that the hardware translates into physical addresses on every memory access.

This indirection solves two real problems. Without it, a buggy process could corrupt any memory on the machine, including kernel data structures. And physical RAM fragments over time — finding a contiguous 100 MB physical block for a new allocation becomes increasingly unlikely as the system runs. Virtual memory lets the OS present each process with a clean, contiguous address space regardless of how fragmented physical memory actually is.

The mechanism that makes this work is a collaboration between the OS and a dedicated hardware unit: the Memory Management Unit (MMU).

Pages and Frames

Memory is managed in fixed-size chunks rather than byte-by-byte. If the OS tracked individual byte locations, the translation table would consume more memory than the RAM it was describing.

The standard unit on x86_64 is 4 KB (4096 bytes):

• A 4 KB region of virtual address space is a page
• A 4 KB region of physical RAM is a frame

The OS maps pages to frames. Because both are the same size, the byte offset within a page is identical to the byte offset within the corresponding frame — only the base address changes during translation.

The 4 KB default isn’t the only option. Linux supports huge pages: 2 MB pages (enabled per-mapping with mmap(MAP_HUGETLB)) and 1 GB pages. Huge pages reduce TLB pressure for workloads that touch large, contiguous memory regions — databases and HPC applications use them extensively. The trade-off is internal fragmentation: a 2 MB page wasted on a 5 KB allocation is expensive.

The 4-Level Page Table

The mapping from virtual pages to physical frames lives in physical RAM, structured as a multi-level radix tree. A flat array mapping every possible virtual page in a 64-bit address space would require petabytes of storage just for the table itself. The tree structure allows sparse representation — only the paths corresponding to actually-mapped virtual addresses need to exist.

On x86_64 with standard 4-level paging, the hardware uses 48 bits of the 64-bit virtual address (bits 47–0). The upper 16 bits must be copies of bit 47 (sign extension). The 48 usable bits are divided into five fields:

Each level has $2^9 = 512$ entries. The 12-bit offset covers $2^{12} = 4096$ bytes. Total addressable space: $2^{48}$ = 256 TB of virtual address space per process.

Note: modern Intel (Ice Lake and later) and AMD processors support 5-level paging (PML5), extending this to 57-bit addresses and 128 PB of virtual space. The kernel enables it at boot when hardware support is detected.

The Page Walk

The physical address of the PML4 table root is stored in CR3 (Control Register 3). The OS writes CR3 during process creation and on every context switch. The MMU walk for any memory access:

1. Read CR3 → physical address of PML4 table
2. Use bits 47–39 to index PML4 → physical address of PDP table
3. Use bits 38–30 to index PDP → physical address of PD table
4. Use bits 29–21 to index PD → physical address of PT table
5. Use bits 20–12 to index PT → physical base address of the frame
6. Add the 12-bit offset to the frame base → final physical address

Each step is a physical memory read. Unoptimized, that’s four memory accesses before touching the actual data — addressed below.

Page Table Entry Flags

Each entry in the page table is 8 bytes on x86_64, and the lower 12 bits (which would otherwise be part of a 4 KB-aligned physical address) are used as control flags:

• Present (P): Is this page currently in physical RAM?
• Read/Write (R/W): Is the page writable, or read-only?
• User/Supervisor (U/S): Accessible from Ring 3 (user space), or Ring 0 only?
• Dirty: Has this page been written to since it was last loaded? (Used by the OS to decide whether to write back to disk on eviction)
• Accessed: Has this page been read or written recently? (Used for LRU approximation in page replacement)
• NX (No-Execute): Prohibits instruction fetch from this page — critical for W^X enforcement

These flags are enforced by the MMU in hardware. An attempt to write to a read-only page, or to execute from an NX page, triggers a fault before the access completes.

Page Faults

When the MMU encounters a Present bit of 0 during a walk, it raises a page fault exception (#PF). The CPU saves its current state and vectors to the kernel’s page fault handler via the Interrupt Descriptor Table (IDT) — the instruction that triggered the fault is suspended, not completed.

The handler inspects the faulting address and the reason code in the CR2 register, then decides what to do:

Demand paging: The OS doesn’t actually back virtual allocations with physical RAM until the first access. malloc(10 * 1024 * 1024 * 1024) can succeed even on a machine with 8 GB of RAM because no physical frames are allocated yet — only virtual address space is reserved. On first write, a page fault fires, the kernel allocates a physical frame, maps it into the page table, sets the Present bit, and retries the faulting instruction. The process has no visibility into this pause.

Copy-on-Write (CoW): When a process calls fork(), the child inherits the parent’s address space without physically copying all the data. Both processes share the same physical frames, but their page table entries are marked read-only. The first write from either process triggers a page fault; the kernel copies just that one frame at that point, remaps it writable in the writing process’s page table, and retries. This makes fork() fast regardless of process size.

Swapping: If the system is under memory pressure, the kernel can evict a frame to disk and clear its Present bit. When the process accesses that page again, the page fault handler reads the frame back from disk before retrying. This is transparent to the application but has obvious latency implications.

Illegal access: If the faulting address has no valid mapping (accessing NULL, stack overflow, use-after-free), the kernel sends SIGSEGV to the process.

Linux’s memory overcommit policy (/proc/sys/vm/overcommit_memory) controls how aggressively the OS grants virtual allocations without physical backing. In overcommit mode (default), malloc almost never fails — instead, the OOM killer terminates processes when the system actually runs out of physical frames to back committed pages.

The TLB

Four memory accesses per virtual address access would make the system unusable. The CPU contains a Translation Lookaside Buffer (TLB): a small, fast SRAM cache inside the MMU that stores recent virtual-to-physical translations. A TLB hit resolves a translation in a single cycle; a miss requires the full four-level walk.

TLB hit rates in typical workloads are high (98%+) because of temporal and spatial locality — the same pages are accessed repeatedly, and nearby addresses share page table entries. The TLB effectively collapses most of the four-level overhead.

Context switches complicate this. Changing CR3 (switching to a different process’s address space) historically required a full TLB flush, since the new process has different mappings for the same virtual addresses. Modern processors support PCID (Process-Context Identifiers): CR3 can be written with a 12-bit tag that lets the CPU maintain separate TLB entries per process without flushing. Linux has used PCID since kernel 4.14, significantly reducing context switch overhead on hardware that supports it.

KPTI (Kernel Page Table Isolation), added as a Spectre/Meltdown mitigation, partially undoes this: it maintains separate page tables for user and kernel modes, forcing a TLB-affecting CR3 swap on every syscall entry and exit. PCID mitigates but doesn’t eliminate this overhead.

malloc and the Kernel

One detail worth clarifying: the kernel has no concept of malloc. It manages memory at page granularity via mmap() and brk(). The malloc in glibc is a user-space heap allocator that requests pages from the kernel in bulk and sub-divides them to satisfy small allocations. For large requests (typically over 128 KB), glibc calls mmap(MAP_ANONYMOUS) directly to get pages from the kernel, and munmap() to return them. For small allocations, it manages a free list within already-mapped pages and almost never makes a syscall.

This is why valgrind and ASAN can intercept allocations without kernel involvement — they replace the user-space malloc implementation.

Simulating the MMU in C

The following simulates a simplified 32-bit two-level MMU (10-bit page directory, 10-bit page table, 12-bit offset) to make the bit manipulation concrete. The 32-bit variant keeps the arithmetic readable; the x86_64 version adds two more levels but the logic is identical.

Verifying the bit decomposition of 0xDEADBEEF manually:

• Binary: 1101 1110 1010 1101 1011 1110 1110 1111
• PD index (bits 31–22): 1101 1110 10 = 890
• PT index (bits 21–12): 1011 0110 11 = 727
• Offset (bits 11–0): 1110 1110 1111 = 0xEEF = 3823

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

#define PAGE_SIZE    4096
#define OFFSET_MASK  0x00000FFFu   /* bits 11–0  */
#define PT_MASK      0x003FF000u   /* bits 21–12 */
#define PD_MASK      0xFFC00000u   /* bits 31–22 */

/* Simulated page tables in "physical memory" */
static uint32_t sim_page_table[1024];
static uint32_t sim_page_directory[1024];

/* CR3 points to the active page directory */
static uint32_t *CR3 = sim_page_directory;

static void init_mappings(void)
{
    /*
     * Map virtual address 0xDEADBEEF:
     *   PD index = 890, PT index = 727, offset = 0xEEF
     * to physical frame base 0x55555000
     * → physical address 0x55555EEF
     */
    sim_page_directory[890] = (uint32_t)(uintptr_t)sim_page_table;
    sim_page_table[727]     = 0x55555000u;
}

static uint32_t mmu_translate(uint32_t va)
{
    uint32_t pd_idx  = (va & PD_MASK)     >> 22;
    uint32_t pt_idx  = (va & PT_MASK)     >> 12;
    uint32_t offset  = (va & OFFSET_MASK);

    printf("[MMU] VA 0x%08X → PD[%u] PT[%u] +%u\n", va, pd_idx, pt_idx, offset);

    /* Step 1: index the page directory via CR3 */
    uint32_t pd_entry = CR3[pd_idx];
    if (pd_entry == 0) {
        printf("[MMU] #PF: page directory entry not present\n");
        return 0;
    }

    /* Step 2: index the page table */
    uint32_t *pt = (uint32_t *)(uintptr_t)pd_entry;
    uint32_t frame_base = pt[pt_idx];
    if (frame_base == 0) {
        printf("[MMU] #PF: page table entry not present\n");
        return 0;
    }

    /* Step 3: add offset to frame base */
    uint32_t pa = frame_base + offset;
    printf("[MMU] PA 0x%08X\n", pa);
    return pa;
}

int main(void)
{
    init_mappings();
    mmu_translate(0xDEADBEEF);

    /* Demonstrate a fault: no mapping for 0x00001000 */
    printf("\n");
    mmu_translate(0x00001000);

    return 0;
}

[MMU] VA 0xDEADBEEF → PD[890] PT[727] +3823
[MMU] PA 0x55555EEF

[MMU] VA 0x00001000 → PD[0] PT[1] +0
[MMU] #PF: page directory entry not present

The second call demonstrates the fault path: PD index 0 has no entry (simulating an unmapped region), so the handler returns early. In a real kernel, this would vector to the page fault handler which would either map a frame and retry, or deliver SIGSEGV.

The process running this code sees 0xDEADBEEF as a valid address and has no visibility into the translation. From the application’s perspective, memory is a flat array. The address decomposition, table walks, and physical frame lookup happen entirely within the MMU, invisible to the instruction stream that requested the data.