Chapter 2: Hardware Foundations and Address Translation

Updated

October 31, 2026

Chapter 2: Hardware Foundations and Address Translation

Virtual memory operates at the physical boundary where software abstractions meet silicon microarchitecture. While the Linux kernel defines the layout of address spaces, every single instruction fetch and data read must be translated into physical electrical signals across the memory bus in fractions of a nanosecond.

This chapter details the hardware foundations of memory management: Memory-Mapped I/O (MMIO), the internal architecture of the Memory Management Unit (MMU), multi-level page table structures, the Translation Lookaside Buffer (TLB), inter-processor TLB shootdowns, modern x86-64 4-level and 5-level paging, ARM64 and RISC-V translation architectures, memory caching attributes, and a complete worked example of walking an x86-64 page table by hand.

Memory-Mapped I/O and Physical Addressing

In modern computer architectures, physical memory addresses do not map solely to physical dynamic RAM (DRAM) chips:

┌────────────────────────────────────────────────────────────────────────┐
│                        PHYSICAL ADDRESS SPACE MAP                      │
│                                                                        │
│   0x0000000000000000 ──► Physical RAM (DRAM Bank 0)                    │
│   ...                                                                  │
│   0x000000007FFFFFFF ──► Physical RAM (2 GiB boundary)                 │
│   0x0000000080000000 ──► PCIe MMIO Window (Bar Registers, GPU, NIC)   │
│   ...                    (Writes directly manipulate device registers) │
│   0x00000000FFFFFFFF ──► High BIOS / SPI Flash ROM (Firmware)          │
│   0x0000000100000000 ──► Extended Physical RAM (Upper Banks)           │
└────────────────────────────────────────────────────────────────────────┘
  • Physical DRAM: Memory controllers map system DRAM sticks into designated spans of the physical address space.
  • Memory-Mapped I/O (MMIO): Hardware peripherals (NVMe storage controllers, PCIe network interface cards, GPUs) expose internal control registers and packet buffers as ranges within the physical address map. When the CPU executes a write to an MMIO physical address, the transaction routes across the PCIe root complex rather than DRAM.
  • Port I/O vs MMIO: While legacy x86 CPUs supported dedicated Port I/O instructions (IN / OUT), modern high-performance devices communicate almost exclusively via MMIO and direct memory access (DMA).

The Memory Management Unit Architecture

The Memory Management Unit (MMU) is the hardware component inside the CPU core responsible for translating virtual addresses into physical addresses.

┌────────────────────────────────────────────────────────────────────────┐
│                        CPU MMU TRANSLATION PIPELINE                    │
│                                                                        │
│   Instruction Pipeline generates Virtual Address: 0x7FFF50001ABC       │
│                               │                                        │
│                               ▼                                        │
│   ┌──────────────────────────────────────────────────────────────┐     │
│   │ Translation Lookaside Buffer (TLB) Lookup                    │     │
│   │ Check L1 Instruction / Data TLB                              │     │
│   └───────────────────────────┬──────────────────────────────────┘     │
│                               │                                        │
│            ┌──────────────────┴──────────────────┐                     │
│            ▼ TLB Hit (99% of cycles)             ▼ TLB Miss (< 1%)     │
│   ┌──────────────────────────────┐    ┌──────────────────────────────┐ │
│   │ Physical Address Output      │    │ Hardware Page Table Walker   │ │
│   │ (Latency: ~1 clock cycle)    │    │ Reads CR3 -> PGD -> P4D ->   │ │
│   │                              │    │ PUD -> PMD -> PTE from RAM   │ │
│   │                              │    │ (Latency: 10 - 50 ns)        │ │
│   └──────────────┬───────────────┘    └──────────────┬───────────────┘ │
│                  │                                   │                 │
│                  ▼                                   ▼                 │
│   Memory Controller / L1 Cache Access          Refill TLB and Return   │
└────────────────────────────────────────────────────────────────────────┘

When an address cannot be translated—because no page table entry exists or permissions are violated—the MMU halts instruction execution and raises an Interrupt 14 (#PF - Page Fault Exception), saving the faulting virtual address into the CR2 control register and jumping into the kernel’s trap handler.

Page Tables: Structure, Levels, and Walks

Why are page tables structured as multi-level trees rather than a simple flat array?

On a 64-bit architecture with standard \(4\text{ KiB}\) pages, a 48-bit virtual address space contains \(2^{36} \approx 68.7\text{ billion pages}\). A flat array mapping 68 billion pages would require:

\[68,719,476,736 \text{ entries} \times 8 \text{ bytes per entry} = 512 \text{ Gigabytes}\]

Every single process on the system would consume 512 GiB of RAM just to store its page table, before storing a single byte of application data!

Multi-Level Trees: Sparsity and Compactness

Multi-level page tables solve this by organizing translations as a sparse B-tree: - Intermediate levels are allocated only when valid memory mappings exist within that branch. - An application using 50 MiB of memory allocates only a handful of intermediate \(4\text{ KiB}\) directory tables, consuming less than 100 KiB of metadata memory.

Translation Lookaside Buffers and TLB Shootdowns

Because traversing a 4-level or 5-level page table requires up to five sequential memory accesses to DRAM (costing 50–100 ns), the MMU relies on the Translation Lookaside Buffer (TLB).

The TLB is a tiny, highly associative hardware cache holding the most recent translations: - L1 Data TLB (dTLB): Typically 64 entries; 1-cycle access latency. - L1 Instruction TLB (iTLB): Typically 64–128 entries. - L2 Shared TLB (sTLB): Typically 1,024–2,048 entries; 4–8 cycle latency.

The TLB Shootdown Problem

When the kernel modifies a page table entry (e.g., during munmap(), page migration, or swapping) on a multi-core server, the old virtual-to-physical translation may still be cached inside the private hardware TLBs of dozens of other CPU cores running threads of that process.

To prevent other cores from reading or writing stale physical memory, the kernel must execute a TLB Shootdown: 1. The initiating core generates an Inter-Processor Interrupt (IPI) broadcast across the system interconnect to all sibling cores. 2. The sibling cores freeze execution, flush their local TLBs using the INVLPG instruction, and acknowledge the IPI. 3. The initiating core waits for all acknowledgments before proceeding.

On 128-core servers, high-frequency TLB shootdowns introduce massive synchronization overhead, consuming significant CPU cycles in interrupt handlers.

x86-64 Paging: Four-Level and Five-Level Page Tables

In 64-bit mode, modern x86 processors implement two paging models:

┌────────────────────────────────────────────────────────────────────────┐
│                        x86-64 4-LEVEL PAGE TRANSLATION                 │
│                                                                        │
│   Virtual Address (48 bits):                                           │
│   [47 ... 39]  [38 ... 30]  [29 ... 21]  [20 ... 12]  [11 ........ 0]  │
│     PGD (9b)     PUD (9b)     PMD (9b)     PTE (9b)     Offset (12b)   │
│        │            │            │            │               │        │
│   CR3 ─┘            │            │            │               │        │
│    │                │            │            │               │        │
│    ▼                ▼            ▼            ▼               ▼        │
│   [PGD Table] ──► [PUD Table] ─► [PMD Table] ─► [PTE Table] ──► + Offset│
│                                                               = PhysAddr│
└────────────────────────────────────────────────────────────────────────┘

1. Four-Level Paging (4-Level / 48-bit Canonical Addressing)

Uses bits 0 to 47 of the virtual address, providing a \(256\text{ TiB}\) address space split evenly between user-space (\(128\text{ TiB}\)) and kernel-space (\(128\text{ TiB}\)). Bits 48 to 63 must be a sign-extension of bit 47 (canonical address rule): - Level 4: Page Global Directory (PGD) (9 bits \(\rightarrow\) 512 entries) - Level 3: Page Upper Directory (PUD) (9 bits \(\rightarrow\) 512 entries) - Level 2: Page Middle Directory (PMD) (9 bits \(\rightarrow\) 512 entries) - Level 1: Page Table Entry (PTE) (9 bits \(\rightarrow\) 512 entries) - Physical Offset: Bits 0–11 (\(4096\text{ bytes}\)).

2. Five-Level Paging (5-Level Paging / 57-bit Addressing)

To support multi-petabyte memory configurations on modern server processors (Ice Lake, Sapphire Rapids, EPYC Genoa), Intel and AMD introduced 5-Level Paging (CONFIG_X86_5LEVEL): - Adds a fifth level: Page 4th Directory (P4D). - Expands virtual addressing to 57 bits (\(128\text{ Petabytes}\)).

ARM64 and RISC-V Virtual Memory Systems

  • ARM64 (AArch64): Uses the Translation Table Base Registers (TTBR0_EL1 and TTBR1_EL1). TTBR0 translates user-space virtual addresses (0x0000...), while TTBR1 translates kernel virtual addresses (0xFFFF...), eliminating the need to swap address tables during system calls. Supports \(4\text{ KiB}\), \(16\text{ KiB}\), and \(64\text{ KiB}\) page granules.
  • RISC-V: Standardizes virtual memory into formal translation modes configured via the satp register:
    • Sv39: 3-level page tables (39-bit virtual address, 512 GiB space).
    • Sv48: 4-level page tables (48-bit virtual address, 256 TiB space).
    • Sv57: 5-level page tables (57-bit virtual address, 128 PiB space).

Memory Types, Caching Attributes, and Access Permissions

Every 64-bit Page Table Entry (PTE) contains control flags evaluated by the MMU on every access:

┌────────────────────────────────────────────────────────────────────────┐
│                        64-BIT PTE FORMAT (x86-64)                      │
│                                                                        │
│   63   62 ... 52  51 .................................... 12  11 ... 0 │
│  ┌───┬──────────┬───────────────────────────────────────────┬────────┐ │
│  │NX │ Available│ Physical Frame Address (PFN 40-bits)      │ Flags  │ │
│  └───┴──────────┴───────────────────────────────────────────┴────────┘ │
└────────────────────────────────────────────────────────────────────────┘
  • P (Present - Bit 0): 1 if page resides in physical RAM; 0 if swapped out or unallocated (triggers page fault).
  • R/W (Read/Write - Bit 1): 0 = read-only; 1 = read-write.
  • U/S (User/Supervisor - Bit 2): 0 = Ring 0 kernel privilege only; 1 = Ring 3 user-space accessible.
  • PWT / PCD / PAT: Memory caching attributes: Write-Through, Cache-Disable (for MMIO registers), Write-Combining (for video framebuffers).
  • A (Accessed - Bit 5): Set to 1 by hardware whenever the page is read or written; used by Linux LRU reclaim.
  • D (Dirty - Bit 6): Set to 1 by hardware whenever the page is written to; used to track dirty writeback.
  • NX (No-Execute - Bit 63): Prevents instruction execution from data pages.

Walking a Page Table by Hand: A Practical Example

Let us trace a virtual address translation by hand on x86-64:

Suppose an application accesses Virtual Address: \[\text{VA} = \texttt{0x00007FFF5A241C80}\]

  1. Convert to Binary and Extract Field Offsets:
    • 0x00007FFF5A241C80 in binary: \[\underbrace{0000000000000000}_{\text{Sign extension}} \underbrace{011111111}_{\text{PGD}} \underbrace{111010010}_{\text{PUD}} \underbrace{010010001}_{\text{PMD}} \underbrace{000001100}_{\text{PTE}} \underbrace{110010000000}_{\text{Offset}}\]
    • PGD Index: 011111111_2 = 0x0FF = 255
    • PUD Index: 111010010_2 = 0x1D2 = 466
    • PMD Index: 010010001_2 = 0x091 = 145
    • PTE Index: 000001100_2 = 0x00C = 12
    • Page Offset: 110010000000_2 = 0xC80
  2. Step-by-Step Hardware Walk:
    • The CPU reads control register CR3 to get the base physical address of the PGD table (0x100000).
    • Reads entry at index 255: PGD[255] yields pointer to PUD table (0x205000).
    • Reads entry at index 466: PUD[466] yields pointer to PMD table (0x341000).
    • Reads entry at index 145: PMD[145] yields pointer to PTE table (0x489000).
    • Reads entry at index 12: PTE[12] contains physical frame address: 0x892A000 (PFN: 0x892A).
    • The CPU combines the physical frame address with the page offset: \[\text{Physical Address} = \texttt{0x892A000} + \texttt{0xC80} = \mathbf{\texttt{0x892AC80}}\]

The hardware issues a bus cycle to read physical byte 0x892AC80 from DRAM and populates the TLB for subsequent reads.