Page Tables

When a process accesses memory address 0x7FFA4B20, how does the hardware know which physical memory location actually contains that data? The answer lies in one of the most elegant and performance-critical data structures in computer architecture: the page table.

Every memory access in a modern system—every instruction fetch, every variable read, every buffer write—involves a translation from virtual to physical addresses. This translation must happen fast (nanoseconds), correctly (no security holes), and efficiently (minimal memory overhead). The page table is the bridge that makes all of this possible.

To understand page table structure, we must first understand the problem they solve. In a paged virtual memory system:

• Virtual address space is divided into fixed-size units called pages (typically 4KB)
• Physical memory is divided into same-sized units called frames
• A process's pages can be scattered across any available frames in physical memory

This non-contiguous allocation provides tremendous flexibility—eliminating external fragmentation and enabling memory sharing—but creates a fundamental challenge: how do we track which virtual page maps to which physical frame?

The Conceptual Model:

At its simplest, a page table is an associative array (like a dictionary or map) where:

• Key: Virtual page number (VPN)
• Value: Physical frame number (PFN) plus metadata

When the CPU generates a virtual address, the Memory Management Unit (MMU) extracts the virtual page number, looks it up in the page table, retrieves the corresponding frame number, and combines it with the offset to form the physical address.

The Engineering Challenge:

A naive implementation as a simple array indexed by VPN would be catastrophically wasteful. A 32-bit address space with 4KB pages has 2^20 pages, requiring over a million entries per process—before we even consider 64-bit systems. The page table structure must be clever enough to handle sparse address spaces efficiently.

The simplest page table structure is a linear array indexed directly by the virtual page number. This approach is conceptually straightforward and was used in early systems, but understanding its characteristics illuminates why more complex structures became necessary.

Structure:

Page Table = Array[0 ... (Virtual_Address_Space_Size / Page_Size) - 1]

page_table[VPN] = PTE (Page Table Entry)

Each entry in the array is a Page Table Entry (PTE) containing:

• Physical frame number
• Valid bit (is this mapping valid?)
• Protection bits (read/write/execute permissions)
• Other control bits (dirty, accessed, etc.)

Why Study Linear Tables?

Despite their impracticality for large address spaces, linear page tables illuminate key concepts:

1. O(1) lookup: Given a VPN, we can find the PTE in constant time with a single array index operation
2. No search required: Unlike segment tables with variable sizes, paging with fixed-size pages enables direct indexing
3. Hardware simplicity: The MMU can compute page_table_base + (VPN × entry_size) directly

These properties—especially fast lookup—remain design goals for all page table structures. The challenge is achieving similar speed while handling sparse address spaces efficiently.

A page table must support several fundamental operations efficiently:

Core Operations:

1. Lookup (Translation): Given a virtual page number, find the corresponding physical frame number
2. Update: Mark a page as accessed, dirty, or change protection
3. Allocate: Create a new mapping when a process faults on an unmapped page
4. Deallocate: Remove a mapping when memory is freed or process terminates
5. Protection Check: Verify the access type matches the page's permissions

The organization of the page table directly affects the performance of each operation.

Memory Layout Regions:

A typical process's virtual address space has distinct regions that influence page table organization:

+---------------------------+ 0xFFFFFFFF (or higher)
|       Kernel Space        | ← Shared across processes
+---------------------------+
|         Stack ↓           | ← Grows downward
|           ...             |
|         Heap ↑            | ← Grows upward
+---------------------------+
|    Uninitialized Data     | ← BSS segment
+---------------------------+
|    Initialized Data       | ← Data segment  
+---------------------------+
|          Code             | ← Text segment
+---------------------------+ 0x00000000 (or near it)

Notice the large gap between heap and stack. This sparse region means most of the address space is unmapped. An efficient page table structure allocates entries only for the actually-mapped regions.

The solution to the sparsity problem is hierarchical (multi-level) page tables. Instead of one giant array, we use a tree structure where:

• The root table (page directory) contains pointers to second-level tables
• Second-level tables contain pointers to third-level tables (if needed)
• Leaf tables contain the actual virtual-to-physical mappings

Key Insight:

If an entire region of the address space is unmapped, we simply don't allocate the corresponding subtable. A single null pointer in the root can eliminate millions of unused entries.

Two-Level Example (32-bit, 4KB pages):

A 32-bit virtual address has 20 bits for the page number (4GB / 4KB = 2²⁰ pages). We split this into:

• 10 bits: Page Directory Index (1024 entries)
• 10 bits: Page Table Index (1024 entries per table)
• 12 bits: Page Offset (within the 4KB page)

Space Savings Analysis:

Consider a process using only:

• 4MB of code/data (at low addresses): needs 1,024 pages = 1 page table
• 4MB of heap (above data): needs 1,024 pages = 1 page table
• 4MB of stack (at high addresses): needs 1,024 pages = 1 page table

With a linear table: 4MB (1M entries × 4 bytes)

With two-level tables:

• 1 page directory: 4KB (1024 entries × 4 bytes)
• 3 page tables: 3 × 4KB = 12KB
• Total: 16KB (vs 4MB = 256× savings!)

The remaining ~1021 page directory entries are null, representing unmapped regions without wasting memory.

Each entry in a page table—called a Page Table Entry (PTE)—contains far more than just the frame number. The PTE is a carefully designed bit field that controls translation, protection, and status tracking.

Anatomy of a Page Table Entry:

A typical PTE contains:

1. Physical Frame Number (PFN): The actual translation—which physical frame holds this page
2. Valid/Present Bit: Is this mapping currently valid and in physical memory?
3. Protection Bits: Read, Write, Execute permissions
4. User/Supervisor Bit: Can user-mode code access this page?
5. Accessed Bit: Has this page been read since loaded?
6. Dirty Bit: Has this page been written since loaded?
7. Cache Control Bits: Memory type (write-back, write-through, uncacheable)
8. Reserved/OS Bits: Available for operating system use

Why Each Field Matters:

Present Bit (P): The most critical bit. When P=0, the entire rest of the entry can be used by the OS for any purpose (e.g., storing swap location). Hardware will fault on access, and the OS can handle it.

Read/Write and User/Supervisor: These form the core protection matrix. A page might be:

• R/W=0, U/S=0: Kernel read-only (e.g., kernel code)
• R/W=1, U/S=0: Kernel read-write (e.g., kernel data structures)
• R/W=0, U/S=1: User read-only (e.g., user code, read-only data)
• R/W=1, U/S=1: User read-write (e.g., user heap, stack)

Accessed and Dirty Bits: These are set automatically by hardware, enabling the OS to implement page replacement algorithms without trapping every memory access. The OS periodically clears these bits to track recent usage patterns.

Page table size is a critical concern in system design. Tables consume physical memory, and in a system with many processes, this overhead can be substantial. Understanding these trade-offs is essential for both OS designers and systems programmers.

Factors Affecting Page Table Size:

1. Virtual Address Space Size: Larger address spaces require more levels or wider entries
2. Page Size: Larger pages mean fewer entries needed
3. Entry Size: Depends on physical address bits needed plus metadata
4. Address Space Sparsity: More unused regions = more savings from multi-level
5. Number of Processes: Each process needs its own page table(s)

Optimization Strategies:

Large/Huge Pages: Using 2MB or 1GB pages instead of 4KB dramatically reduces page table size:

• 4KB pages: 1GB memory = 262,144 PTEs
• 2MB pages: 1GB memory = 512 PTEs
• 1GB pages: 1GB memory = 1 PTE

Trade-off: Larger pages increase internal fragmentation and reduce sharing granularity.

Page Table Sharing: Read-only regions (like shared libraries) can share page table entries across processes. The kernel maps libc.so once and points multiple processes' PTEs to the same frames.

Lazy Allocation: Page tables themselves can be demand-allocated. A page directory entry stays null until a fault occurs in that region, at which point the OS allocates the needed page table.

One of the most important functions of page tables is process isolation—ensuring that one process cannot access another's memory without explicit permission. This isolation is the foundation of multi-process operating systems and modern security models.

How Isolation Works:

1. Each process has its own page table (or hierarchy of tables)
2. The CPU has a register (CR3 on x86) pointing to the current page table
3. On context switch, the OS updates this register to point to the new process's page table
4. All address translations now use the new process's mappings

Even if two processes use the same virtual address (e.g., both have code at 0x400000), they map to different physical frames.

Security Implications:

• Memory Protection: Process B cannot even form an address that maps to Process A's frames
• No Guessing Attacks: Even if B tries every possible virtual address, none will reach A's data
• Hardware Enforcement: The MMU enforces this on every single memory access—no software overhead

Shared Regions:

Despite isolation, processes need to share some memory:

• Kernel Space: The upper portion of every process's page table maps the same kernel frames
• Shared Libraries: libc, etc., map to the same physical frames (read-only) across processes
• Explicit Shared Memory: mmap() with MAP_SHARED creates shared mappings

These shared regions appear in multiple page tables pointing to the same physical frames, with appropriate protection bits.

Page tables require intimate cooperation between hardware and software. The CPU provides dedicated registers, the MMU implements the table walk algorithm, and the OS manages table contents. Understanding this division is crucial for systems programming.

Critical Hardware Components:

Page Table Base Register:

• x86: CR3 (Control Register 3)
• ARM: TTBR0/TTBR1 (Translation Table Base Registers)
• RISC-V: SATP (Supervisor Address Translation and Protection)

This register holds the physical address of the root page table. When the OS switches processes, it stores the new page table address here.

Software Responsibilities:

The operating system must:

1. Allocate Page Tables: Request physical frames for page table storage
2. Initialize Entries: Set up valid mappings with correct permissions
3. Maintain Consistency: Update tables when allocating/freeing memory
4. Handle Faults: Respond when hardware signals an unmapped or protected access
5. Manage CR3: Switch page tables on context switch
6. Flush TLB: Invalidate cached translations when tables change

The TLB Factor:

In practice, the MMU caches recent translations in the Translation Lookaside Buffer (TLB). Most memory accesses hit the TLB and skip the table walk entirely. This caching is why page tables can be relatively slow to access—most translations never touch them.

We've explored the fundamental architecture of page tables—the data structure that makes virtual memory possible. Let's consolidate the key insights:

What's Next:

Now that we understand the overall structure of page tables, we'll dive deeper into the Page Table Entry (PTE)—examining each field in detail, understanding the hardware semantics, and seeing how the OS uses these bits to implement sophisticated memory management policies.