Virtual Memory & Paging Architecture

Virtual memory provides every user-space process with the illusion of an exclusive, contiguous address space while decoupling execution from physical RAM limitations. It is the bedrock of process isolation, protection rings, memory sharing, and dynamic storage mapping in modern operating systems.

+-------------------------------------------------------------+
|               Virtual Address Space (Process)               |
|  [ Text (Code) ] [ Data/BSS ] [ Heap -> ] ... [ <- Stack ]  |
+-------------------------------------------------------------+
                               |
               Hardware Translation (MMU + TLB)
                               |
                               v
+-------------------------------------------------------------+
|               Physical RAM Frames / Swap Pages              |
|  [ Frame 0x1A00 ]  [ Frame 0x04F2 ]  [ Disk ZRAM / Swap ]   |
+-------------------------------------------------------------+

The Hardware Translation Pipeline (MMU & Paging)

Modern 64-bit microprocessors (x86-64 and ARM64) employ paged virtual memory orchestrated collaboratively by operating system kernel software and hardware Memory Management Units (MMU).

Virtual Address Deconstruction (4-Level Paging)

On standard x86-64 hardware with 48-bit canonical virtual addressing (4-level paging), the 64-bit virtual address is partitioned into five distinct bit fields to navigate a hierarchical radix-tree page table:

 63          47       38       29       20       11          0
+-----------+--------+--------+--------+--------+-------------+
| Sign Ext  |  PML4  |  PDPT  |   PD   |   PT   | Page Offset |
|  16 bits  | 9 bits | 9 bits | 9 bits | 9 bits |   12 bits   |
+-----------+--------+--------+--------+--------+-------------+

1. Sign Extension (Bits 48–63): Must match bit 47 (canonical addressing), enforcing a canonical divide between user space (0x0000000000000000 to 0x00007FFFFFFFFFFF) and kernel space (0xFFFF800000000000 to 0xFFFFFFFFFFFFFFFF).
2. PML4 Index (Bits 39–47): Indexes one of 512 entries (9 bits = $2^9$) in the Page Map Level 4 table. The physical address of PML4 is stored in the CPU control register (CR3 on x86, TTBR0_EL1/TTBR1_EL1 on ARM64).
3. PDPT Index (Bits 30–38): Indexes the Page Directory Pointer Table.
4. PD Index (Bits 21–29): Indexes the Page Directory.
5. PT Index (Bits 12–20): Indexes the Page Table, which yields the base physical Page Frame Number (PFN).
6. Offset (Bits 0–11): Preserved verbatim across translation ($2^{12} = 4096\text{ bytes} = 4\text{ KiB}$ base page size).

In 5-level paging (Paging57 on Intel Ice Lake+ and AMD Zen 4+), a 57-bit virtual address space adds a 9-bit PML5 level, expanding virtual addressable memory from 256 TiB to 128 PiB.

Page Table Entries (PTE) Flags & Hardware Bits

Each entry across the radix tree is an 8-byte (64-bit) descriptor containing physical frame base addresses and hardware-enforced permission bits:

• P (Present, Bit 0): 1 if the page resides in physical RAM; 0 if the page is unmapped or swapped out, causing the CPU to generate a Page Fault (#PF).
• R/W (Read/Write, Bit 1): 0 = Read-only; 1 = Read/Write. Enforces page write protection.
• U/S (User/Supervisor, Bit 2): 0 = Kernel mode (Ring 0) only; 1 = User mode (Ring 3) accessible.
• A (Accessed, Bit 5): Set by CPU hardware whenever the page is read or written. Used by kernel page replacement algorithms (Clock / LRU).
• D (Dirty, Bit 6): Set by CPU hardware whenever data is written to the page. Indicates whether page-out requires writeback to persistent storage or swap.
• NX / XD (No-Execute / Execute-Disable, Bit 63): Enforces $W \oplus X$ (Write XOR Execute) memory protection. If set, instruction fetches from this address trigger a Page Fault, neutralizing buffer overflow shellcode execution.

Translation Lookaside Buffer (TLB) & Multi-Core Coherence

Traversing a 4-level page table requires four sequential memory accesses for every single instruction or operand fetch. Without caching, system performance would degrade by 400–800%.

The Translation Lookaside Buffer (TLB) is a specialized, fully associative hardware cache within the CPU core that stores recent virtual-to-physical address mappings.

TLB Miss Penalty & Huge Pages

• TLB Hit: Address translation resolves in 1 clock cycle (0.5–1 ns).
• TLB Miss: The hardware page table walker performs 4 to 5 DRAM accesses (~50–200 ns).

To mitigate TLB capacity exhaustion under large memory footprints (databases, JVMs, hypervisors), kernels utilize Huge Pages:

• Standard Page: 4 KiB (offset 12 bits, requires 4 translation steps).
• Large Page: 2 MiB (bypasses level 1 PT; PD entry points directly to a 2 MiB frame; offset 21 bits).
• Gigantic Page: 1 GiB (bypasses PT and PD; PDPT entry points directly to a 1 GiB frame; offset 30 bits).

A single 2 MiB TLB entry covers 512 times more memory than a 4 KiB entry, preventing TLB thrashing in high-throughput workloads.

TLB Shootdowns & Inter-Processor Interrupts (IPI)

When the kernel alters a page mapping (unmapping memory, page migration, permissions change, or swapping out), the stale TLB entries on all CPU cores caching that translation must be invalidated:

1. Kernel modifies the in-memory Page Table Entry (PTE).
2. Initiating CPU broadcasts an Inter-Processor Interrupt (IPI) to all other CPU cores sharing that virtual address space.
3. Receiving cores pause user execution, execute the interrupt handler, flush their local TLB entry (INVLPG instruction on x86, TLBI on ARM64), and issue an acknowledgment.
4. Initiating core waits for all ACKs before resuming execution.

Frequent TLB shootdowns inflict severe multi-core latency penalties.

PCID & ASID: Eliminating Context-Switch TLB Flushes

Historically, every process context switch required loading a new CR3 register, which unconditionally flushed the entire non-global TLB.

Modern processors avoid this through hardware address tagging:

• x86-64 PCID (Process Context Identifiers): 12-bit tags in CR3 (bits 0–11) associating TLB entries with specific processes (up to 4096 active contexts).
• ARM64 ASID (Address Space Identifier): 8-bit or 16-bit tags associated with TTBR0_EL1.

When switching between processes, the CPU simply switches the active PCID/ASID without invalidating cached translations belonging to other processes.

Page Fault Handling (#PF) & Kernel Allocation Strategies

A Page Fault is not necessarily an error; it is an architected CPU hardware exception (Interrupt Vector 14 on x86) through which the operating system implements dynamic memory virtualization.

Instruction access -> MMU checks PTE Present bit:
  - If Present == 1: Physical address fetched.
  - If Present == 0: CPU raises #PF (CR2 holds faulting virtual address)
                           |
                           v
              Kernel do_page_fault() handler
                           |
       +-------------------+--------------------+
       |                                        |
  Valid VMA range?                         Invalid address?
       |                                        |
       v                                        v
  Demand Paging / CoW / Swap-in            SIGSEGV / Access Violation

1. Demand Paging & Zero-Fill-on-Demand (ZFOD)

When a program requests heap memory via malloc(), brk(), or mmap(), the OS does not allocate physical RAM immediately. Instead, it merely records an entry in the process Virtual Memory Area (VMA) tree.

• When the process first reads or writes to the page, the CPU triggers a minor #PF.
• The kernel allocates a physical frame from the free page pool, initializes it with zeros (Zero-Fill-on-Demand) to prevent leaking previous processes' data, populates the PTE, sets Present = 1, and resumes the process.

2. Copy-on-Write (CoW) in Process Creation

When a Unix process invokes fork(), duplicating the entire physical address space of a multi-gigabyte process would be prohibitively slow:

1. fork() duplicates the parent's page tables rather than the physical frames.
2. The kernel marks all shared PTEs as Read-Only in both parent and child page tables, incrementing the page frame reference counters.
3. When either process attempts a write, the CPU raises a #PF (Protection Violation).
4. The kernel inspects the VMA: if the write is legitimately allowed, the kernel allocates a new physical frame, copies the 4 KiB content from the original frame, updates the faulting process's PTE to point to the new frame with Write permissions enabled, and decrements the old frame's reference count.

3. Swap & Compressed RAM (ZRAM, zswap, Jetsam)

When physical RAM exhaustion approaches, the kernel's page reclaim daemon (kswapd on Linux, vm_pageout on BSD/macOS) reclaims memory:

• File-backed pages: Dropped immediately if clean (can be re-read from disk); written back if dirty.
• Anonymous pages (Heap, Stack): Swapped to disk or compressed in memory:
  • Linux ZRAM / zswap: Compressed virtual RAM block devices using LZ4/zstd, trading minor CPU cycles for a 2–3x memory capacity multiplier.
  • macOS Jetsam & WKdm: In-kernel memory compressor (WKdm algorithm) that compresses inactive memory pages into a compressed cache before writing to swapfile.
  • Android: Pure RAM compression (ZRAM) with no physical disk swapfile, relying on lmkd (Low Memory Killer Daemon) to terminate background processes when compression saturates.

Kernel vs User Address Space Isolation & Security

32-bit vs 64-bit Address Splits

• 32-bit Architecture (4 GiB address space):
  • Linux standard: 3 GiB User / 1 GiB Kernel (PAGE_OFFSET = 0xC0000000).
  • Windows standard: 2 GiB User / 2 GiB Kernel (or 3 GiB User with /3GB boot flag).
• 64-bit Architecture:
  • Distinct canonical split separated by a vast "non-canonical hole": lower half assigned to user space, upper half to kernel virtual mapping.

Kernel Page Table Isolation (KPTI)

Prior to 2018, the kernel space was permanently mapped into every user process's page table (protected by the Supervisor bit) to eliminate TLB invalidation costs during system calls.

The Meltdown CPU vulnerability (CVE-2017-5754) revealed that out-of-order speculative CPU execution could read supervisor memory across the protection boundary before permission checks retired, leaking kernel secrets via cache timing side-channels.

Operating systems deployed KPTI (Kernel Page Table Isolation, originally KAISER):

• Each process maintains two distinct page tables:
  1. User Page Table: Contains only user space mappings, plus the bare minimum trampolines needed to enter the kernel (syscall entry/exit stubs, interrupt handlers).
  2. Kernel Page Table: Full address space mapping (kernel code, stacks, data, plus user mappings).
• System calls require switching CR3 on entry and exit, re-introducing context-switching overhead on older processors lacking PCID support.

Comparative Overview: Virtual Memory Across Kernels

Feature	Linux	Windows NT	macOS (XNU)	Android
Paging Hierarchy	4-level (48-bit) or 5-level (57-bit) PML5	4-level paging (PML4)	4-level paging (ARM64 16 KiB pages standard)	4-level paging (ARM64 standard)
Base Page Size	4 KiB (x86/ARM64) or 64 KiB (ARM64 option)	4 KiB	16 KiB on Apple Silicon; 4 KiB on x86	4 KiB (transitioning to 16 KiB in Android 15)
Address Allocation	mmap() / brk()	VirtualAlloc() (Reserve vs Commit)	vm_allocate() / Mach VM map	Linux mmap() via ART heap
Swap / Pressure Mechanism	Swap partition/file, zswap, ZRAM, OOM killer	Pagefile (pagefile.sys), working set trimming	WKdm compressed memory + dynamic swapfile	ZRAM compression + userspace lmkd (no disk swap)
Hardware Isolation	KPTI, ASLR, KASLR, W^X	KVA Shadow (KPTI), ASLR, DEP, HVCI	KPTI, KASLR, Page Protection Layer (PPL)	KASLR, SELinux per-page permissions, pKVM