6.1 Virtual Addresses, Page Tables, and TLB

Caches narrow the CPU-to-memory speed gap. Address translation solves a different problem: ordinary processes usually have separate virtual address spaces, with mappings, protection, and sharing managed by the OS and MMU. Identical pointer values need not name the same physical memory.

The cache answers, "How far is this physical data from the core?" Virtual memory first answers, "Which physical page does the program's address point to?" This lesson tracks the process of address translation; the next one will cover demand paging, page faults, and mmap.

The Same Address Can Name Different Physical Memory

Two processes can both print a pointer such as 0x7f.... Each has its own page table, which can map that same virtual address to different physical pages or intentionally map both addresses to one shared physical page.

A process's virtual address space isn't a pre-filled block of physical memory; it's a collection of mappings and gaps. The operating system maintains records of mapping ranges, permissions, and backing objects. The MMU performs address translation during load, store, and fetch operations by consulting the current process's page table.

Virtual memory provides three key capabilities:

• Isolation: User processes can only access memory mappings and permissions explicitly allowed by their page tables;
• Relocation: Consecutive virtual pages can be mapped to scattered physical pages, allowing programs to operate without knowing the physical layout;
• Sharing: Different virtual address ranges can point to the same file page, shared memory page, or copy-on-write page.

Isolation reduces the risk of ordinary wild pointers corrupting other processes, but it's not a complete security boundary. Kernel vulnerabilities, misconfigured device DMA, and side-channel attacks still require additional protective mechanisms.

First, Observe the Mapping, Don't Guess a Fixed Layout

Linux processes can inspect the current virtual memory area (VMA) via /proc/self/maps. This Linux program uses POSIX APIs to print object addresses and the process’s maps path. Save as show_maps.c and compile with cc -std=c17 -Wall -Wextra -Werror show_maps.c -o show_maps. While it runs, execute the printed cat command in another terminal, then press Enter to finish:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

static int global_value = 42;

int main(void) {
    int stack_value = 10;
    int *heap_value = malloc(sizeof *heap_value);
    if (heap_value == NULL) {
        perror("malloc");
        return 1;
    }
    *heap_value = 20;

    printf("pid: %ld\n", (long)getpid());
    printf("global object: %p\n", (void *)&global_value);
    printf("heap object:   %p\n", (void *)heap_value);
    printf("stack object:  %p\n", (void *)&stack_value);
    printf("inspect: cat /proc/%ld/maps\n", (long)getpid());

    if (fflush(stdout) == EOF) {
        perror("fflush");
        free(heap_value);
        return 1;
    }
    int result = 0;
    if (getchar() == EOF && ferror(stdin)) {
        perror("getchar");
        result = 1;
    }
    free(heap_value);
    return result;
}

Running this multiple times often causes ASLR to shift the addresses of the stack, heap, shared libraries, and PIE executables, making it impossible to predict that two consecutive virtual addresses will be identical. The layout also depends on the operating system, ABI, linking method, resource limits, and runtime allocators.

malloc returns a memory region that satisfies language constraints. It may split from an existing allocator arena or request a new mapping; the behavior "allocates a page only on first write and registers a VMA on each malloc" is not a universal sequential pattern. Physical page allocation occurs on-demand and must be observed in the context of specific mappings and allocator state.

Split an Address into Page Number and Offset

Set page size to 2^p bytes. A virtual address can be expressed as:

virtual address = virtual page number (VPN) | page offset

The lower p bits represent the page offset and are preserved unchanged during translation. The higher-order VPN portion is translated via the page table to obtain the physical frame number (PFN):

physical address = PFN × page_size + offset

If the page size is 4096 bytes, then p = 12. For address 0x...6D00, the offset is 0xD00. Page size is determined by the architecture and memory mapping strategy and should not be assumed to always be 4096 bytes across platforms. POSIX provides sysconf(_SC_PAGESIZE) to query the standard page size.

Each page table entry stores the PFN and includes flags such as present/valid, read/write, user/supervisor, execute permission, accessed, and dirty status. The exact bit positions for these flags are defined by the instruction set architecture (ISA) and paging mode, so a specific x86 page table layout cannot be directly applied to RISC-V or ARM.

x86-64 Four-Level Translation Example

In the classic x86-64 four-level paging mode using 48-bit canonical virtual addresses and 4 KiB pages, the lower 48 bits are split as follows:

47          39 38          30 29          21 20          12 11       0
+--------------+--------------+--------------+--------------+----------+
| PML4 index   | PDPT index   | PD index     | PT index     | offset   |
| 9 bit        | 9 bit        | 9 bit        | 9 bit        | 12 bit   |
+--------------+--------------+--------------+--------------+----------+

The translation process conceptually proceeds as:

1. CR3 points to the base physical address of the top-level table and associated context;
2. The PML4 entry points to the next page-directory-pointer table;
3. The PDPT entry points to the page directory;
4. The PD entry points to the page table;
5. The PT entry provides the 4 KiB physical frame and associated permissions;
6. The PFN combined with the original offset forms the final physical address.

Each level must verify the present bit and permissions; permissions at intermediate levels also contribute to the final result. If a PDPT or PD entry selects a huge page, the walk terminates early and uses a larger internal offset.

Modern x86-64 also supports five-level paging, extending the effective virtual address space to 57 bits. Whether the processor supports it, whether the OS enables it, and what range is available to user space are distinct questions. The statement "a 64-bit CPU has full 2^64 user address space" is not valid.

RISC-V Sv39, Sv48, and AArch64 translation tables use their own levels, PTE formats, and address rules. After understanding the commonality between virtual page number (VPN) translation, multi-level indexing, and physical frame number (PFN), refer to the specific ISA manual for the target architecture.

Why Hierarchical Page Tables Are Well-Suited for Sparse Address Spaces

With a 48-bit virtual address and 4 KiB pages, there are 2^36 virtual pages. If each entry is 8 bytes, a single flat page table would require:

2^36 × 8 bytes = 512 GiB

This is just the mapping array for one address space, clearly impractical to preallocate for every process.

A hierarchical page table transforms this into a radix tree. Large, unused regions of address space are marked as "not present" at higher levels, avoiding the allocation of child page-table pages below. Each 4 KiB page table holds 512 entries of 8 bytes, which is exactly what a 9-bit index can address.

The cost is that sparse mappings still require physical memory for actual leaf PTEs and the intermediate nodes leading to them. A 4-KiB-aligned contiguous 100 MiB mapping requires 25,600 pages of 4 KiB, translating to roughly 200 KiB of leaf PTEs alone, plus several levels of directory pages. Keep mapped data pages, PTE bytes, and allocated page-table pages distinct. Huge pages can reduce PTE count and alleviate TLB pressure, but they introduce internal fragmentation, complicate allocation and migration, and may prolong certain kernel operations.

The page table itself consumes physical memory and can be cached in CPU caches. Each level of a page walk doesn’t necessarily access DRAM; upper-level entries or entire walks may hit paging-structure caches or ordinary CPU caches.

Extract Four-Level Indices with Code

def split_x86_4k_48(virtual_address: int) -> dict[str, int]:
    if not 0 <= virtual_address < (1 << 64):
        raise ValueError("address must fit in 64 bits")

    low48 = virtual_address & ((1 << 48) - 1)
    sign = (low48 >> 47) & 1
    expected_high = 0xFFFF if sign else 0x0000
    if virtual_address >> 48 != expected_high:
        raise ValueError("non-canonical 48-bit virtual address")

    return {
        "pml4": (virtual_address >> 39) & 0x1FF,
        "pdpt": (virtual_address >> 30) & 0x1FF,
        "pd": (virtual_address >> 21) & 0x1FF,
        "pt": (virtual_address >> 12) & 0x1FF,
        "offset": virtual_address & 0xFFF,
    }

parts = split_x86_4k_48(0x00007F3A4B5C6D00)
assert parts == {
    "pml4": 0xFE,
    "pdpt": 0xE9,
    "pd": 0x5A,
    "pt": 0x1C6,
    "offset": 0xD00,
}

kernel_style = 0xFFFF800000001234
assert split_x86_4k_48(kernel_style)["offset"] == 0x234

This verifies bit splitting and the canonical-address rule, without reading actual page tables. User processes typically cannot directly access arbitrary physical page tables; Linux's /proc interface, debuggers, or kernel tools are also subject to permission and security policies.

The TLB Caches Translation Results

If every load operation had to traverse the four-level page table structure from scratch, the translation overhead would consume a significant portion of execution time. The translation lookaside buffer (TLB) caches recent virtual-to-physical page number (VPN to PFN) mappings along with associated permissions.

virtual address
  ├─ TLB hit  -> check cached permissions -> PFN or protection fault
  └─ TLB miss -> hardware/software page-table walk
                  ├─ valid mapping -> populate TLB, retry access
                  └─ no valid translation/permission failure -> page fault

A TLB hit can still fail a permission check, while a miss does not imply an absent physical page. The diagram covers paging translation; non-canonical addresses and other invalid inputs may raise different ISA exceptions, not necessarily a page fault.

A TLB hit is not universally just one cycle, and a TLB miss is not always a fixed number of hundreds of cycles. The cost varies depending on TLB hierarchy, page-walk cache behavior, cache hit rates, and whether parallel page walks are used.

TLBs are typically organized by page size or have different internal structures. A single entry for a 4 KiB page covers 4 KiB of address space, while a single entry for a 2 MiB page covers a much larger range. As a result, huge pages can improve TLB reach:

TLB reach ≈ entry_count × page_size

This can benefit workloads with large address spaces, but it is not universally optimal. Transparent huge page collapse, splitting, and compaction introduce latency. Databases or virtual machines may instead opt for explicit huge pages. Choose THP policy using workload and latency measurements. always is not appropriate for every workload, and global changes also affect other processes.

Address Space Switching and TLB Shootdown

When switching between processes, entries in the TLB from the previous address space cannot be reused for the new one. A simple implementation flushes the entire TLB; architectures with ASID or PCID support mark entries with their associated address space, reducing unnecessary flushes. The global kernel mapping has its own rules for handling such cases.

If the operating system removes a mapping, lowers permissions, or changes the page frame number (PFN), other CPUs might still hold cached translations. To handle this, the kernel must perform a TLB shootdown: signaling relevant cores to invalidate the affected entries and ensuring proper synchronization before the operation completes. Frequent mprotect, munmap, or large-scale changes in mappings can result in cross-core overhead.

TLB coherence and data-cache coherence are distinct issues: the former ensures consistency across translation caches, while the latter ensures that copies of the same physical data line are synchronized across multiple cores.

Cache and Translation: Which Happens First?

Many L1 caches use virtually indexed, physically tagged (VIPT) designs, allowing the page offset index bits to be queried in parallel with TLB lookups, with final validation using the physical tag. Other levels and architectures may differ.

This shows that the sequential model (“complete translation first, then access each cache level”) is merely a conceptual abstraction. Hardware instead operates in parallel and makes predictions to shorten the critical path, though it must ultimately preserve correct physical identity, permissions, and alias behavior.

Page Permissions Cause Errors to Fail Early at Boundaries

Common page permission mappings include readable, writable, executable, and user-accessible. Operating systems use these to implement:

• Code pages are typically executable but not writable;
• Stack and heap pages are usually writable but not executable;
• Copy-on-write pages are initially read-only; a write faults, copying if needed or restoring write permission when the page is already exclusive;
• Guard pages remain unmapped or inaccessible and fault when an overrun touches them; they do not catch every out-of-bounds access;
• Read-only code pages of shared libraries can be mapped by multiple processes.

The W^X (writable XOR executable) principle reduces the attack surface by preventing a page from being both writable and executable simultaneously. The rule permits a page to be neither writable nor executable; it is not literal logical XOR. JITs, dynamic linking, and platform policies can use controlled transitions, while aliases of the same physical page require separate consideration. NX (execute-never) is a hardware-enforced capability, but full security also requires additional measures such as ASLR, permission separation, and control-flow protection.

Page table permission checks occur during every valid memory access translation. TLB entries cache the corresponding permissions; therefore, when permissions are modified, the old entry must be properly invalidated to maintain consistency.

Hands-on Trace a Load

1. Dissect a virtual address 0x0000123456789ABC under 48-bit four-level paging with 4 KiB pages.
2. Calculate how many leaf entries are required to map a 1 GiB contiguous region using 4 KiB pages versus 2 MiB pages.
3. Explain how the 512 GiB capacity in a flat page table is derived from two specific exponents.
4. Distinguish between a TLB miss and a page fault: which one can be resolved even when an effective PTE already exists?
5. Illustrate why one core still needs a TLB shootdown after modifying a PTE in a page table also used by another core.
6. Investigate the actual page size, supported huge page sizes, and address width of the target machine, without assuming it’s 64-bit.

A Mapping Does Not Guarantee Resident Data

An effective virtual address range may still lack corresponding physical anonymous pages, file pages might not be in the page cache, and read-only pages could still be waiting for copy-on-write. The next lesson, Demand paging, page faults, and mmap, explains how accessing memory turns these promises into actual resources.