Paging & Page Tables

Paging is the mechanism by which the operating system takes the vast, unwieldy logical address space and carves it into manageable chunks called pages, while mapping those to equally uniform chunks of physical memory called frames. Without paging, a process requesting 500 KB of contiguous memory would fail if physical memory were fragmented across a thousand small gaps — even if the total free memory exceeded 500 KB. Paging eliminates that problem entirely by making the mapping virtual, not physical.

Page tables are the data structures the OS builds and the hardware consults to perform this mapping on every single memory access. Understanding paging and page tables is essential for understanding virtual memory, memory protection, and the performance characteristics of virtually every program you have ever run.

Introduction

When to Use / When Not to Use

Paging is a fundamental OS mechanism — it is always in use. You do not choose to use it; your hardware and OS cooperate to apply it whether you want it or not. However, you make choices about how your application interacts with it.

When understanding paging helps you:

• Allocating large buffers with malloc — understanding page boundaries explains allocator alignment behavior
• Memory-mapping files with mmap — understanding page faults reveals why first access to mmap’d regions can be slow
• Debugging OOM kills or excessive page fault rates
• Writing lock-free data structures where cache line alignment and false sharing are concerns
• Database optimization (PostgreSQL huge pages, InnoDB buffer pool pages)

When you can ignore it:

• Purely functional, managed-language applications where the runtime handles all memory
• Applications where memory access patterns are uniformly distributed (no concentrated hot spots)

Architecture or Flow Diagram

Address translation under paging splits the logical address into three components: the page directory index, the page table index, and the offset within the page. The MMU walks this hierarchy before accessing DRAM.

flowchart TD
    LA["Logical Address<br/>31..22: PD Index<br/>21..12: PT Index<br/>11..00: Offset"]
    PD["Page Directory<br/>1024 entries<br/>(stored in physical memory)"]
    PT["Page Table<br/>1024 entries<br/>(stored in physical memory)"]
    PDE["Page Directory<br/>Entry<br/>+ Present bit<br/>+ Frame number"]
    PTE["Page Table<br/>Entry<br/>+ Present bit<br/>+ Frame number<br/>+ Access rights"]
    PF["Physical Frame<br/>Number"]
    PA["Physical Address<br/>= PF + Offset"]
    DRAM["Physical DRAM"]

    LA -->|"CR3 points to PD"| PD
    PD -->|indexed by<br/>PD Index| PDE
    PDE -->|"points to PT<br/>in physical memory"| PT
    PT -->|indexed by<br/>PT Index| PTE
    PTE -->|"frame number"| PF
    PF -->|appended with<br/>Offset| PA
    PA --> DRAM

    style LA stroke:#00fff9
    style PA stroke:#00fff9

On modern x86-64 systems, the page table hierarchy is four levels: PML4 (Page Map Level 4) → PDP (Page Directory Pointer) → PD (Page Directory) → PT (Page Table). The CR3 register points to the PML4 in physical memory.

Core Concepts

Pages and Frames

A page is a fixed-size block in the virtual address space — traditionally 4 KB on x86 and ARM. A frame is the equivalent block in physical memory. The page size is a power of two (almost always 4 KB for compatibility), which simplifies address splitting and indexing.

Pages can be in one of three states:

• Present: The page is mapped to a physical frame and accessible
• Not present (swapped): The page’s content has been moved to swap space on disk
• Not present (unmapped): The page has never been allocated — accessing it causes a fault

The OS maintains a page table for each process (actually a multi-level tree) where each entry maps one virtual page to either a physical frame or a swap location.

Multi-Level Page Tables

A flat page table for a full 32-bit address space with 4 KB pages would require 2^20 entries (1,048,576 entries). At 4 bytes per entry, that is 4 MB per process — acceptable for a few processes but not for thousands. Worse, the entire table must be resident in physical memory even if the process uses only a small fraction of its address space.

Multi-level page tables solve this by adding a tree structure. Only the page table pages that are actually needed are allocated. Unused portions of the virtual address space consume no physical memory.

On x86-64 with 4-level paging (Linux default):

• PML4 (Page Map Level 4): 512 entries, points to PDP pages
• PDP (Page Directory Pointer): 512 entries per PML4 entry, points to PD pages
• PD (Page Directory): 512 entries per PDP entry, points to PT pages
• PT (Page Table): 512 entries per PD entry, maps to physical frames

This means a process using only 4 pages (16 KB) of virtual memory needs: 1 PML4 page + 1 PDP page + 1 PD page + 1 PT page = 4 × 4 KB = 16 KB of page tables instead of 4 MB.

Translation Lookaside Buffer (TLB)

The TLB is a hardware cache of recent virtual-to-physical address translations. Every memory access goes through the MMU, which first checks the TLB. On a TLB hit, the translation is instantaneous (one cycle). On a TLB miss, the MMU walks the page table hierarchy in physical memory — an expensive operation.

Modern TLBs:

• x86 L1 D-TLB: 64 entries (some architectures, 4-way set associative)
• x86 L1 I-TLB: 64 entries
• Last-level TLB (L2 TLB): 512-1024 entries
• AMD Zen 3: 512-entry L1 TLB, 4096-entry L2 TLB

When context switching between processes, the TLB entries for the old process are generally invalid for the new process. On hardware without PCID (Process Context ID), the entire TLB is flushed on every context switch. With PCID (supported on Intel Haswell+ and AMD Zen+), each TLB entry is tagged with an address space ID, so entries from different processes coexist in the TLB.

Page Fault Handling

When a process accesses a page that is not present (not in physical memory), the CPU triggers a page fault exception. The OS page fault handler executes this sequence:

1. Identify the faulting address: The CPU stores it in the CR2 register (x86)
2. Determine fault type: Is the page just not loaded, or is the access invalid (protection violation)?
3. If valid and not present: Allocate a physical frame (from the free frame list or page cache)
4. If swapped out: Locate the page on the swap device, schedule a disk I/O read
5. Update the page table entry: Set the frame number and mark the page as present
6. Resume the instruction: The CPU retries the faulting memory access

The critical subtlety is that the faulting instruction is restartable only if the memory access used a base register (like [rbx + rsi]) and not a computed displacement that would differ after resolution. The x86 ISA is designed to make all memory accesses restartable, which is a core invariant the OS relies upon.

Production Failure Scenarios

Thrashing: Excessive Page Faults

Failure: When the total working set of all running processes exceeds physical memory capacity, the OS spends more time swapping pages in and out than executing useful work. Each process generates page faults, triggering disk I/O, which slows all other processes, generating more memory pressure — a feedback loop that collapses throughput to near-zero.

Mitigation: Monitor pgscank and pgscand columns in vmstat 1. Tune the swappiness parameter (/proc/sys/vm/swappiness — lower values prefer reclaiming page cache over swapping process pages). Add physical RAM. Use cgroups to limit per-service memory. Use memory limits in container runtimes (docker --memory, Kubernetes requests/limits).

Excessive TLB Miss Rate on Large Working Sets

Failure: Applications with working sets that exceed the TLB coverage (e.g., a 512 MB working set on a system where each TLB entry maps only 4 KB) generate TLB misses on nearly every access. Each miss requires a multi-level page table walk, adding ~25-50 cycles per memory access — a 5-10x slowdown compared to TLB-hit access.

Mitigation: Use huge pages (2 MB or 1 GB pages) so one TLB entry covers more memory. Linux transparent huge pages (echo always > /sys/kernel/mm/transparent_hugepage/enabled) automate huge page usage for mmap’d regions. PostgreSQL’s huge_pages setting explicitly uses 2 MB pages for the buffer pool.

Page Table Memory Overhead for Large Mappings

Failure: Memory-mapping a 100 GB file with 4 KB pages requires 100 GB / 4 KB = 25,638,400 page table entries. At 8 bytes per entry (x86-64), that is ~200 MB of page table memory just to describe the mapping, even though no physical memory is allocated yet.

Mitigation: Use mmap(MAP_HUGETLB) to map with 2 MB pages, reducing page table entries by 512x. Filesystems like ext4 and XFS support huge pages. Some databases use a dedicated I/O path that bypasses the page cache entirely (e.g., O_DIRECT in Linux) to avoid double-buffering.

Trade-off Table

Strategy	Page Size	TLB Efficiency	Internal Fragmentation	Page Table Overhead	Best Use Case
4 KB pages (standard)	4 KB	Low (many entries needed)	~2 KB avg per mapping	High (many entries)	General application workloads
2 MB huge pages	2 MB	High (one entry = 512× coverage)	~1 MB avg per mapping	512× smaller	Databases, JVM heaps, kernel memory
1 GB huge pages	1 GB	Very high	Large (GB-scale waste)	Minimal	Very large memory-mapped files
Multi-level page tables	4 KB	N/A	N/A	Minimal for sparse address spaces	All modern general-purpose OSes
Inverted page tables	Variable	Lower (hash lookup)	N/A	Fixed size regardless of mappings	Embedded systems, database engines

Implementation Snippets

Simulating Two-Level Page Table Lookup (Python)

#!/usr/bin/env python3
"""Simplified two-level page table simulation.
Demonstrates how address translation works:
  - VPN (Virtual Page Number) split into:
      PD_INDEX (top bits) + PT_INDEX (bottom bits)
  - Each level is an array of entries
  - PFN (Page Frame Number) + offset = Physical Address
"""

import struct

PAGE_BITS = 12          # 4 KB pages: 2^12 = 4096 bytes
PAGE_SIZE = 1 << PAGE_BITS
ADDR_BITS = 20          # Simplified 20-bit logical address space (1 MB range)

# How many bits for each level of the page table
PD_BITS = 10
PT_BITS = PAGE_BITS      # Remaining bits for PT index

PD_SIZE = 1 << PD_BITS   # 1024 entries
PT_SIZE = 1 << PT_BITS   # 1024 entries

class PageTableEntry:
    """Simulates a single page table entry (PTE)."""
    def __init__(self, present: bool = False, pfn: int = 0, readonly: bool = False):
        self.present = present
        self.pfn = pfn          # Physical Frame Number
        self.readonly = readonly

    def to_int(self) -> int:
        # Simplified PTE encoding
        val = (self.pfn << 12) | (0b1 if self.present else 0) | (0b10 if self.readonly else 0)
        return val

    @classmethod
    def from_int(cls, val: int):
        present = bool(val & 0b1)
        readonly = bool(val & 0b10)
        pfn = val >> 12
        return cls(present, pfn, readonly)

class PageDirectory:
    """Top-level page directory. Contains PT_BASE addresses."""
    def __init__(self):
        self.entries = [None] * PD_SIZE

    def set_pt_base(self, pd_index: int, pt_base_phys: int):
        self.entries[pd_index] = pt_base_phys

    def get_pt_base(self, pd_index: int):
        return self.entries[pd_index]

class PageTable:
    """Second-level page table. Contains PFN mappings."""
    def __init__(self):
        self.entries = [PageTableEntry() for _ in range(PT_SIZE)]

    def map_page(self, pt_index: int, pfn: int, readonly: bool = False):
        self.entries[pt_index] = PageTableEntry(present=True, pfn=pfn, readonly=readonly)

def translate(logical_addr: int, pd: PageDirectory, pt_pages: dict) -> int:
    """Translate a logical address to a physical address."""
    # Split VPN into PD index and PT index
    pd_index = (logical_addr >> (ADDR_BITS - PD_BITS)) & ((1 << PD_BITS) - 1)
    pt_index = (logical_addr >> PAGE_BITS) & ((1 << PT_BITS) - 1)
    offset   = logical_addr & (PAGE_SIZE - 1)

    # Lookup PD entry to find PT location
    pt_base = pd.get_pt_base(pd_index)
    if pt_base is None:
        raise PageFaultException(f"Page table not present at PD[{pd_index}]")

    # Get PTE from the page table
    pte = pt_pages[pt_base].entries[pt_index]
    if not pte.present:
        raise PageFaultException(f"Virtual page {pt_index} not present")

    # Compute physical address
    physical_addr = (pte.pfn << PAGE_BITS) | offset
    return physical_addr

class PageFaultException(Exception):
    pass

# Example: Map logical pages 0, 1, 2 to physical frames 0x1A, 0x2B, 0x3C
pd = PageDirectory()
# In real hardware, these would be physical addresses of the page tables themselves
PT_BASE = 0x1000
pt_pages = {}

for pd_index in range(2):  # Just PD[0] and PD[1]
    pt_phys = PT_BASE + pd_index
    pt_pages[pt_phys] = PageTable()
    pd.set_pt_base(pd_index, pt_phys)

# Map 3 virtual pages: PD[0]->PT[0..511], PD[1]->PT[0]
pt_pages[PT_BASE + 0].map_page(0, 0x1A)   # VPage 0 -> PFrame 0x1A
pt_pages[PT_BASE + 0].map_page(1, 0x2B)   # VPage 1 -> PFrame 0x2B
pt_pages[PT_BASE + 1].map_page(0, 0x3C)   # VPage 512 (PD[1],PT[0]) -> PFrame 0x3C

# Test translations
print("Logical addr 0x00000 -> Physical 0x{:05X}".format(translate(0x00000, pd, pt_pages)))
print("Logical addr 0x01000 -> Physical 0x{:05X}".format(translate(0x01000, pd, pt_pages)))
print("Logical addr 0x20000 -> Physical 0x{:05X}".format(translate(0x20000, pd, pt_pages)))

Examining Page Fault Types (bash)

#!/bin/bash
# Show page fault statistics for a target process
# Use after observing poor performance to identify page fault causes

PID=${1:-$$}
echo "=== Page fault analysis for PID $PID ==="

# Read page fault counts from /proc/PID/status
grep -E "VmPeak|VmSize|VmRSS|VmData|VmStk|VmExe|VmLib|PageFault" \
    /proc/$PID/status 2>/dev/null

echo ""
echo "=== Minor vs Major page faults over 2 samples ==="
for i in 1 2; do
    echo "--- Sample $i ---"
    cat /proc/$PID/status | grep -i "fault"
    sleep 1
done

echo ""
echo "=== Swap usage ==="
grep -i swap /proc/$PID/status 2>/dev/null || echo "No swap used or not found"

echo ""
echo "=== Memory map (first 10 entries) ==="
cat /proc/$PID/maps | head -10

Observability Checklist

• Minor vs major page fault rate: ps -o pid,comm,majflt,minflt — high majflt = swap thrashing
• TLB miss rate: perf stat -e dTLB-load-misses,dTLB-store-misses ./program
• Hardware page table walker (HWPM) events: Architecture-specific PMU events (e.g., perf stat -e r01d1,r20d1 on Intel for page walker counters)
• Number of page table pages allocated: grep -c "" /proc/PID/smaps (counts VMAs — not page table pages, but correlated)
• Huge page usage: cat /proc/meminfo | grep -i huge
• OOM killer invocation log: dmesg | grep -i "out of memory\|oom-killer"
• Swappiness setting: cat /proc/sys/vm/swappiness — default 60; reduce for database servers
• Page cache pressure: cat /proc/sys/vm/pagecache (older kernels) or cat /proc/sys/vm/vfs_cache_pressure

Common Pitfalls / Anti-Patterns

Page-level Access Control: Page table entries contain protection bits: read (R), write (W), execute (X), and user/supervisor (U/S). The OS sets these when allocating pages. User-space code cannot write to kernel-only pages (U=0), and code pages are marked non-writable (W=0). This is enforced by hardware on every memory access — no software check needed.

SMEP (Supervisor Mode Execution Prevention): If the U (user) bit is set in a page table entry, the kernel cannot access that page even in privileged mode. This prevents kernel exploits from dereferencing user-space pointers — even if an attacker hijacks kernel control flow and jumps to user-space shellcode, the kernel cannot execute it due to SMEP.

Page fault side-channel attacks: Meltdown exploited the timing difference between accessing a valid page versus accessing a faulting (invalid) page — the fault handler adds latency, but the speculative access still populates the cache. The fix (IBRS microcode) serializes the address translation path, ensuring no speculative memory access occurs before the protection bits are checked.

Cold boot attacks and memory forensics: RAM can retain data for seconds to minutes after power loss. Investigators can cold-boot a machine and image the physical memory to recover page tables, encryption keys, and process data. Full-disk encryption (FDE) with a TPM-bound key mitigates this for persistent data. For memory at rest, use memory encryption features like AMD SEV or Intel TME.

Common Pitfalls / Anti-patterns

Pitfall: Assuming that malloc returns zero-initialized memory. malloc returns uninitialized memory — whatever bits were in the physical frames are returned as-is. Use calloc if you need zeroed memory. This is not just a cleanliness issue — reading uninitialized memory from another process’s page frames is a security vulnerability called “uninitialized memory disclosure.”

Pitfall: Accessing mmap regions without understanding fault behavior. Memory-mapped regions are not backed by physical frames until first access. The first read or write to each page triggers a page fault, disk I/O (if from a file), and page table update. This is called demand paging. If you mmap a 10 GB file and then sequentially scan it, you get 10 GB / 4 KB = 2.6 million page faults. Use MAP_POPULATE (on Linux) to pre-fault pages and avoid the fault storm.

Pitfall: Using very large malloc without huge pages. A malloc(8GB) for an in-memory database working set causes massive page table overhead: 8 GB / 4 KB = 2 million entries, consuming ~16 MB of page table memory per process. Worse, every page of the working set requires a separate TLB entry — exhausting TLB entries and forcing constant page table walks. Allocating with 2 MB huge pages reduces this to 4,000 entries.

Anti-pattern: Writing code that assumes contiguous virtual memory. Assuming you can walk a 10 GB array with a simple pointer increment is fine in virtual terms. In physical terms, those pages are scattered across physical memory. But for TLB purposes, what matters is the virtual contiguity — one huge page TLB entry covers 2 MB of virtually contiguous space regardless of physical scatter.

Quick Recap Checklist

• Paging divides the virtual address space into uniform 4 KB pages and physical memory into 4 KB frames
• Page tables map virtual pages to physical frames; multi-level trees minimize memory overhead for sparse address spaces
• The TLB caches recent translations to avoid the cost of page table walks on every memory access
• A page fault triggers when a process accesses a not-present page; the OS loads it from disk or zero-fills it
• Multi-level page tables (PML4→PDP→PD→PT on x86-64) reduce page table overhead from 4 MB to proportional sizes
• Huge pages (2 MB or 1 GB) reduce TLB pressure and page table overhead for large working sets
• Thrashing occurs when processes’ combined working sets exceed physical memory, causing constant page-in/page-out
• Tools: vmstat 1 (swapping), perf stat -e dTLB-load-misses (TLB misses), /proc/PID/maps (VMA layout)
• Page table entries contain protection bits (R/W/X) enforced by the MMU on every memory access
• Copy-on-write (COW) defers physical page copies after fork() until either process writes — optimizing fork() cost

Interview Questions

Further Reading

x86-64 Paging Deep Dive

On x86-64, the paging structure is four levels:

PML4 (Page Map Level 4)

• 512 entries, each pointing to a PDP page
• CR3 register points to the PML4 (physical address)
• Bit 47:0 used for address translation on 48-bit VA systems

PDP (Page Directory Pointer)

• 512 entries per PML4 entry, each pointing to a PD page

PD (Page Directory)

• 512 entries per PDP entry, each pointing to a PT page

PT (Page Table)

• 512 entries per PD, each maps to a 4 KB physical frame

For a 48-bit virtual address (256 TB user space):

• Bits 63:48 are sign-extended bits 47
• Bits 47:39 select PML4 entry
• Bits 38:30 select PDP entry
• Bits 29:21 select PD entry
• Bits 20:12 select PT entry
• Bits 11:0 are the page offset

Huge pages: PML4, PDP, and PD entries can have their “PS” (page size) bit set, mapping 1 GB, 2 MB, or 512 GB ranges directly without going through lower levels.

Page Table Entry Fields (x86-64)

Field	Bits	Purpose
P (Present)	0	Page is in physical memory
RW	1	Read/Write (0=read-only, 1=read-write)
US	2	User/Supervisor (0=kernel only, 1=user accessible)
PWT	3	Page Write-Through
PCD	4	Page Cache Disable
A	5	Accessed (set by hardware on access)
D	6	Dirty (set by hardware on write)
PS	7	Page Size (1=large page, 0=normal)
G	8	Global (not flushed on context switch if CR4.PGE=1)
Available	9-11	OS-defined
PFN	12-51	Physical Frame Number

TLB Shootdown Optimization

On context switches, if the incoming process uses the same ASID (PCID), the TLB entries from the previous process are still valid. Linux uses invpcid to invalidate only entries matching the target ASID rather than flushing the entire TLB.

When PCID is not available (older hardware), the kernel flushes the TLB via mov cr3, cr3 or INVLPG for individual pages.

Key Takeaways

• Paging divides virtual and physical memory into uniform 4 KB pages (or larger for huge pages)
• Multi-level page tables (PML4 → PDP → PD → PT on x86-64) allocate memory proportional to actual usage
• TLB caches translations — TLB misses trigger expensive page table walks
• Page faults are restartable — the OS saves the faulting address in CR2 and preserves the instruction pointer
• Huge pages reduce TLB pressure and page table overhead for large working sets

Conclusion

Paging is the mechanism that makes virtual memory possible — dividing both logical and physical memory into uniform 4 KB pages (or larger for huge pages) allows the OS to map any virtual page to any physical frame, eliminating external fragmentation and enabling memory protection at page granularity.

Multi-level page tables (PML4→PDP→PD→PT on x86-64) minimize the memory overhead of page tables for sparse address spaces. A process using only a few pages of virtual memory needs just a handful of page table pages, not the 4 MB a flat page table would require. The TLB caches recent translations to avoid the cost of page table walks on every memory access — TLB misses cost 20-50 cycles while TLB hits complete in a single cycle.

Page faults trigger when a process accesses a not-present page. The OS resolves minor faults by allocating a frame and updating the page table; major faults require disk I/O to load pages from swap. Copy-on-write optimizes fork() by deferring physical memory copies until either process writes.

For your next step, explore virtual memory to understand how the OS uses swap space as a backing store when physical memory is exhausted, or process scheduling to see how the OS decides which process gets CPU time when multiple processes compete for resources.