Loading learning content...
We've learned to split a logical address into page number and offset. Now comes the critical step: using the page number to find the physical frame where the page actually resides. This lookup—an array indexing operation at its core—is where the virtual-to-physical mapping materializes.
The page table is essentially a function: given a page number, return a frame number (or signal an error if the page isn't in memory). Every memory access your programs make triggers this lookup. Understanding frame lookup means understanding the data structure at the center of memory virtualization.
By the end of this page, you will understand the page table as a lookup structure, how the page number indexes into the table to find the frame number, the contents of a page table entry (PTE) beyond just the frame number, how the TLB accelerates lookups, and what happens when a lookup fails (page faults). This knowledge is essential for understanding memory management and virtual memory systems.
The page table is a data structure maintained by the operating system that maps virtual page numbers to physical frame numbers. Conceptually, it's an array where the index is the page number and the value is a Page Table Entry (PTE) containing the frame number and metadata.
Conceptual Model:
PageTable[page_number] → PageTableEntry containing frame_number
For a 32-bit system with 4KB pages:
Why an Array-Based Structure?
The page table uses array indexing rather than more complex data structures (hash tables, trees) for several critical reasons:
Array-based page tables consume memory proportional to the virtual address space, not the physical memory used. A 32-bit process needs a 4MB page table even if it only uses 1MB of memory. This is why multi-level page tables and sparse representations evolved—to avoid wasting memory on unused portions of the address space.
A Page Table Entry (PTE) contains far more than just the frame number. It includes metadata essential for memory management, protection, and optimization. Understanding the PTE structure is crucial for grasping how the OS manages virtual memory.
| Field | Bits | Purpose | Modified By |
|---|---|---|---|
| Frame Number | 20+ bits | Physical frame address (frame base = frame# × page_size) | OS only |
| Valid/Present | 1 bit | 1 = page in physical memory, 0 = page fault if accessed | OS only |
| Read/Write | 1 bit | 0 = read-only, 1 = read/write allowed | OS only |
| User/Supervisor | 1 bit | 0 = kernel only, 1 = user accessible | OS only |
| Accessed | 1 bit | Set by hardware when page is read | Hardware; cleared by OS |
| Dirty | 1 bit | Set by hardware when page is written | Hardware; cleared by OS |
| Write-Through | 1 bit | Cache write policy for this page | OS only |
| Cache Disable | 1 bit | Disable caching for this page (MMIO) | OS only |
| Global | 1 bit | Page not flushed on context switch (kernel pages) | OS only |
| No Execute | 1 bit | Prevent code execution from this page | OS only |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
#include <stdio.h>#include <stdint.h>#include <stdbool.h> /* * Page Table Entry Structure (x86-64 style, simplified) * * Actual x86-64 PTEs are 64 bits with architecture-specific layouts. * This simplified version illustrates the key concepts. */ // Bit positions in a 64-bit PTE (x86-64 style)#define PTE_PRESENT (1ULL << 0) // Page is in physical memory#define PTE_WRITABLE (1ULL << 1) // Page is writable#define PTE_USER (1ULL << 2) // User-mode accessible#define PTE_WRITE_THRU (1ULL << 3) // Write-through caching#define PTE_CACHE_DIS (1ULL << 4) // Disable caching#define PTE_ACCESSED (1ULL << 5) // Page has been accessed#define PTE_DIRTY (1ULL << 6) // Page has been modified#define PTE_HUGE (1ULL << 7) // Huge page (2MB/1GB)#define PTE_GLOBAL (1ULL << 8) // Global (don't flush on CR3 load)#define PTE_NO_EXECUTE (1ULL << 63) // Execute disable (NX bit) // Frame number is in bits 12-51 (40 bits for physical address)#define PTE_FRAME_MASK 0x000FFFFFFFFFF000ULL#define PTE_FRAME_SHIFT 12 /** * Decode a Page Table Entry and print its contents */void decode_pte(uint64_t pte, int page_number) { printf("\n╔══════════════════════════════════════════════════════════════╗\n"); printf("║ Page Table Entry Analysis - Page %d ║\n", page_number); printf("╠══════════════════════════════════════════════════════════════╣\n"); printf("║ Raw PTE Value: 0x%016llX ║\n", (unsigned long long)pte); printf("╠══════════════════════════════════════════════════════════════╣\n"); // Extract frame number uint64_t frame = (pte & PTE_FRAME_MASK) >> PTE_FRAME_SHIFT; printf("║ Frame Number: 0x%llX (%llu) ║\n", (unsigned long long)frame, (unsigned long long)frame); printf("║ Frame Base Address: 0x%012llX ║\n", (unsigned long long)(frame << 12)); printf("╠══════════════════════════════════════════════════════════════╣\n"); printf("║ Flags: ║\n"); // Decode flags printf("║ [%c] Present - Page is in physical memory ║\n", (pte & PTE_PRESENT) ? '✓' : ' '); printf("║ [%c] Writable - Write access permitted ║\n", (pte & PTE_WRITABLE) ? '✓' : ' '); printf("║ [%c] User - User-mode access permitted ║\n", (pte & PTE_USER) ? '✓' : ' '); printf("║ [%c] Accessed - Page has been read ║\n", (pte & PTE_ACCESSED) ? '✓' : ' '); printf("║ [%c] Dirty - Page has been written ║\n", (pte & PTE_DIRTY) ? '✓' : ' '); printf("║ [%c] Global - Not flushed on context switch ║\n", (pte & PTE_GLOBAL) ? '✓' : ' '); printf("║ [%c] No Execute - Code execution prohibited ║\n", (pte & PTE_NO_EXECUTE) ? '✓' : ' '); printf("║ [%c] Cache Dis. - Caching disabled (for MMIO) ║\n", (pte & PTE_CACHE_DIS) ? '✓' : ' '); printf("╚══════════════════════════════════════════════════════════════╝\n");} /** * Create a PTE with specified attributes */uint64_t create_pte(uint64_t frame_number, bool writable, bool user, bool no_execute) { uint64_t pte = PTE_PRESENT; // Must be present to be valid pte |= (frame_number << PTE_FRAME_SHIFT); if (writable) pte |= PTE_WRITABLE; if (user) pte |= PTE_USER; if (no_execute) pte |= PTE_NO_EXECUTE; return pte;} /** * Simulate hardware setting the Accessed bit */void hw_set_accessed(uint64_t* pte) { *pte |= PTE_ACCESSED; printf("Hardware set ACCESSED bit on read\n");} /** * Simulate hardware setting the Dirty bit */void hw_set_dirty(uint64_t* pte) { *pte |= PTE_DIRTY; printf("Hardware set DIRTY bit on write\n");} int main() { printf("╔══════════════════════════════════════════════════════════════╗\n"); printf("║ PAGE TABLE ENTRY (PTE) STRUCTURE ║\n"); printf("╚══════════════════════════════════════════════════════════════╝\n"); // Create example PTEs for different scenarios // Code page: readable, executable, not writable uint64_t code_pte = create_pte(0x100, false, true, false); decode_pte(code_pte, 0); // Data page: readable, writable, not executable uint64_t data_pte = create_pte(0x5A2, true, true, true); decode_pte(data_pte, 18); // Kernel page: readable, writable, supervisor only uint64_t kernel_pte = create_pte(0xFFF, true, false, false); decode_pte(kernel_pte, 256); // Demonstrate hardware flag setting printf("\n═══════════════════════════════════════════════════════════════\n"); printf(" HARDWARE FLAG UPDATES \n"); printf("═══════════════════════════════════════════════════════════════\n\n"); uint64_t test_pte = create_pte(0x200, true, true, true); printf("Initial PTE: 0x%016llX\n", (unsigned long long)test_pte); printf("Accessed: %s, Dirty: %s\n\n", (test_pte & PTE_ACCESSED) ? "Yes" : "No", (test_pte & PTE_DIRTY) ? "Yes" : "No"); printf("Simulating memory read...\n"); hw_set_accessed(&test_pte); printf("PTE now: 0x%016llX\n", (unsigned long long)test_pte); printf("Accessed: %s, Dirty: %s\n\n", (test_pte & PTE_ACCESSED) ? "Yes" : "No", (test_pte & PTE_DIRTY) ? "Yes" : "No"); printf("Simulating memory write...\n"); hw_set_dirty(&test_pte); printf("PTE now: 0x%016llX\n", (unsigned long long)test_pte); printf("Accessed: %s, Dirty: %s\n", (test_pte & PTE_ACCESSED) ? "Yes" : "No", (test_pte & PTE_DIRTY) ? "Yes" : "No"); return 0;}The Accessed and Dirty bits represent a fascinating hardware-software collaboration. Hardware automatically sets these bits during memory operations, but only the OS can clear them. The OS uses these bits for page replacement decisions (LRU approximation) and to determine which pages need to be written back to disk before eviction.
When the CPU needs to access a virtual address, the frame lookup proceeds through a well-defined sequence. Let's trace through this process step by step.
The Lookup Sequence in Detail:
Step 1: TLB Check (Fast Path)
Before consulting the page table, the MMU checks the TLB—a small, fast cache of recent translations. If the page number is found (TLB hit), the frame number is immediately available, and translation completes in ~1 cycle.
Step 2: Page Table Walk (Slow Path)
On a TLB miss, the page table must be consulted. The Page Table Base Register (PTBR) points to the current process's page table:
PTE_Address = PTBR + (Page_Number × PTE_Size)
Step 3: PTE Validation
The PTE is fetched from memory (which itself may involve TLB lookups for the page table pages!). The Present bit is checked:
Step 4: Permission Check
Even if present, permissions must be verified:
Step 5: Frame Number Extraction
If all checks pass, the frame number is extracted from the PTE and combined with the offset to form the physical address.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292
#include <stdio.h>#include <stdint.h>#include <stdbool.h>#include <string.h> /* * Frame Lookup Simulation * * This simulates the complete page table lookup process, * including TLB caching, validation, and permission checking. */ #define PAGE_SIZE 4096#define OFFSET_BITS 12#define TLB_SIZE 16#define PAGE_TABLE_SIZE 1024 // Access typestypedef enum { ACCESS_READ, ACCESS_WRITE, ACCESS_EXECUTE} AccessType; // Privilege levelstypedef enum { PRIVILEGE_USER, PRIVILEGE_KERNEL} PrivilegeLevel; // Page Table Entrytypedef struct { uint32_t frame_number; bool present; bool writable; bool user_accessible; bool executable; bool accessed; bool dirty;} PTE; // TLB Entrytypedef struct { uint32_t page_number; uint32_t frame_number; bool valid; bool writable; bool user_accessible; bool executable;} TLBEntry; // System statetypedef struct { PTE page_table[PAGE_TABLE_SIZE]; TLBEntry tlb[TLB_SIZE]; int tlb_next_victim; // Simple round-robin replacement uint64_t tlb_hits; uint64_t tlb_misses; uint64_t page_faults; uint64_t protection_faults;} MMU; MMU mmu; // Translation resulttypedef struct { bool success; uint64_t physical_addr; bool tlb_hit; const char* error;} TranslationResult; void init_mmu(void) { memset(&mmu, 0, sizeof(mmu)); // Initialize some page table entries mmu.page_table[0] = (PTE){.frame_number = 0x100, .present = true, .writable = true, .user_accessible = true, .executable = false}; mmu.page_table[1] = (PTE){.frame_number = 0x101, .present = true, .writable = false, .user_accessible = true, .executable = true}; // Code page mmu.page_table[18] = (PTE){.frame_number = 0x5A2, .present = true, .writable = true, .user_accessible = true, .executable = false}; mmu.page_table[42] = (PTE){.frame_number = 0, .present = false}; // Not in RAM mmu.page_table[100] = (PTE){.frame_number = 0xFFF, .present = true, .writable = true, .user_accessible = false, .executable = true}; // Kernel page} // TLB lookupint tlb_lookup(uint32_t page_number) { for (int i = 0; i < TLB_SIZE; i++) { if (mmu.tlb[i].valid && mmu.tlb[i].page_number == page_number) { return i; // TLB hit } } return -1; // TLB miss} // TLB insertvoid tlb_insert(uint32_t page_number, PTE* pte) { int slot = mmu.tlb_next_victim; mmu.tlb_next_victim = (mmu.tlb_next_victim + 1) % TLB_SIZE; mmu.tlb[slot].valid = true; mmu.tlb[slot].page_number = page_number; mmu.tlb[slot].frame_number = pte->frame_number; mmu.tlb[slot].writable = pte->writable; mmu.tlb[slot].user_accessible = pte->user_accessible; mmu.tlb[slot].executable = pte->executable;} // Main translation functionTranslationResult translate_address(uint64_t virtual_addr, AccessType access, PrivilegeLevel privilege) { TranslationResult result = {.success = false, .tlb_hit = false}; uint32_t page_number = virtual_addr >> OFFSET_BITS; uint32_t offset = virtual_addr & (PAGE_SIZE - 1); printf("\n┌─ Translation Request ─────────────────────────────────────────┐\n"); printf("│ Virtual Address: 0x%08llX │\n", (unsigned long long)virtual_addr); printf("│ Page Number: %u, Offset: %u │\n", page_number, offset); printf("│ Access: %s, Privilege: %s │\n", access == ACCESS_READ ? "READ" : (access == ACCESS_WRITE ? "WRITE" : "EXEC"), privilege == PRIVILEGE_USER ? "USER" : "KERNEL"); printf("├────────────────────────────────────────────────────────────────┤\n"); // Step 1: TLB Check int tlb_index = tlb_lookup(page_number); uint32_t frame_number; bool writable, user_ok, exec_ok; if (tlb_index >= 0) { // TLB Hit mmu.tlb_hits++; result.tlb_hit = true; printf("│ TLB: HIT (entry %d) │\n", tlb_index); frame_number = mmu.tlb[tlb_index].frame_number; writable = mmu.tlb[tlb_index].writable; user_ok = mmu.tlb[tlb_index].user_accessible; exec_ok = mmu.tlb[tlb_index].executable; } else { // TLB Miss - Page Table Walk mmu.tlb_misses++; printf("│ TLB: MISS - Walking page table... │\n"); if (page_number >= PAGE_TABLE_SIZE) { result.error = "Page number out of range"; printf("│ ERROR: %s │\n", result.error); printf("└────────────────────────────────────────────────────────────────┘\n"); return result; } PTE* pte = &mmu.page_table[page_number]; // Step 2: Present Check if (!pte->present) { mmu.page_faults++; result.error = "PAGE FAULT - Page not in memory"; printf("│ PAGE FAULT: Page %u not present in physical memory │\n", page_number); printf("│ OS would now: load page from disk, update PTE, retry │\n"); printf("└────────────────────────────────────────────────────────────────┘\n"); return result; } printf("│ Page Table: Entry found, Frame = 0x%X │\n", pte->frame_number); frame_number = pte->frame_number; writable = pte->writable; user_ok = pte->user_accessible; exec_ok = pte->executable; // Update TLB tlb_insert(page_number, pte); printf("│ TLB: Updated (cached for future accesses) │\n"); // Set accessed bit pte->accessed = true; } // Step 3: Permission Check printf("├────────────────────────────────────────────────────────────────┤\n"); printf("│ Permission Check: │\n"); // User accessing kernel page? if (privilege == PRIVILEGE_USER && !user_ok) { mmu.protection_faults++; result.error = "PROTECTION FAULT - User cannot access kernel page"; printf("│ FAILED: %s │\n", result.error); printf("└────────────────────────────────────────────────────────────────┘\n"); return result; } // Write to read-only page? if (access == ACCESS_WRITE && !writable) { mmu.protection_faults++; result.error = "PROTECTION FAULT - Write to read-only page"; printf("│ FAILED: %s │\n", result.error); printf("└────────────────────────────────────────────────────────────────┘\n"); return result; } // Execute from non-executable page? if (access == ACCESS_EXECUTE && !exec_ok) { mmu.protection_faults++; result.error = "PROTECTION FAULT - Execute on non-executable page"; printf("│ FAILED: %s │\n", result.error); printf("└────────────────────────────────────────────────────────────────┘\n"); return result; } printf("│ PASSED: Access permitted │\n"); // Step 4: Form Physical Address result.physical_addr = ((uint64_t)frame_number << OFFSET_BITS) | offset; result.success = true; printf("├────────────────────────────────────────────────────────────────┤\n"); printf("│ Physical Address Formation: │\n"); printf("│ Frame 0x%X << 12 = 0x%08X │\n", frame_number, frame_number << OFFSET_BITS); printf("│ + Offset 0x%03X = 0x%08llX │\n", offset, (unsigned long long)result.physical_addr); printf("├────────────────────────────────────────────────────────────────┤\n"); printf("│ SUCCESS: Physical Address = 0x%08llX │\n", (unsigned long long)result.physical_addr); printf("└────────────────────────────────────────────────────────────────┘\n"); return result;} void print_stats(void) { printf("\n═══════════════════════════════════════════════════════════════\n"); printf(" MMU STATISTICS \n"); printf("═══════════════════════════════════════════════════════════════\n"); printf("TLB Hits: %llu\n", (unsigned long long)mmu.tlb_hits); printf("TLB Misses: %llu\n", (unsigned long long)mmu.tlb_misses); printf("TLB Hit Rate: %.1f%%\n", mmu.tlb_hits + mmu.tlb_misses > 0 ? 100.0 * mmu.tlb_hits / (mmu.tlb_hits + mmu.tlb_misses) : 0.0); printf("Page Faults: %llu\n", (unsigned long long)mmu.page_faults); printf("Protection Faults: %llu\n", (unsigned long long)mmu.protection_faults); printf("═══════════════════════════════════════════════════════════════\n");} int main() { init_mmu(); printf("╔══════════════════════════════════════════════════════════════╗\n"); printf("║ FRAME LOOKUP SIMULATION ║\n"); printf("╚══════════════════════════════════════════════════════════════╝\n"); // Normal read - should succeed, TLB miss then hit translate_address(0x00012345, ACCESS_READ, PRIVILEGE_USER); translate_address(0x00012500, ACCESS_READ, PRIVILEGE_USER); // Same page, TLB hit // Write to data page - should succeed translate_address(0x00000100, ACCESS_WRITE, PRIVILEGE_USER); // Execute from code page - should succeed translate_address(0x00001000, ACCESS_EXECUTE, PRIVILEGE_USER); // Write to code page - should fail (read-only) translate_address(0x00001100, ACCESS_WRITE, PRIVILEGE_USER); // Page fault - page not in memory translate_address(0x0002A000, ACCESS_READ, PRIVILEGE_USER); // Protection fault - user accessing kernel page translate_address(0x00064000, ACCESS_READ, PRIVILEGE_USER); // Kernel accessing kernel page - should succeed translate_address(0x00064000, ACCESS_READ, PRIVILEGE_KERNEL); print_stats(); return 0;}A page table walk requires reading memory to fetch the PTE—but that memory access itself needs address translation! The page table is typically mapped in virtual memory, so walking it may involve multiple levels of translation. This recursive nature is why TLB hits are so critical. A TLB miss on every memory access would make systems 10-100× slower.
The TLB is a specialized cache that stores recent page-to-frame translations. It's the critical optimization that makes paging practical—without it, every memory access would require multiple additional memory accesses just for translation.
| TLB Level | Page Size | Entries | Associativity | Hit Latency |
|---|---|---|---|---|
| L1 ITLB (Instruction) | 4KB | 64-128 | 4-8 way | ~1 cycle |
| L1 DTLB (Data) | 4KB | 64-128 | 4-8 way | ~1 cycle |
| L1 DTLB (Data) | 2MB/1GB | 32-64 | 4 way | ~1 cycle |
| L2 STLB (Shared) | 4KB | 1024-2048 | 8-12 way | ~7-12 cycles |
| L2 STLB (Shared) | 2MB | 64-256 | 8 way | ~7-12 cycles |
How the TLB Works:
Parallel Lookup: The TLB is typically implemented as a Content-Addressable Memory (CAM). All entries are compared simultaneously against the page number—not sequential search.
Split TLBs: Many CPUs have separate TLBs for instructions (ITLB) and data (DTLB), allowing parallel lookups for instruction fetch and data access.
Multi-Level: Like data caches, TLBs have hierarchy. L1 TLBs are small and fast; L2 TLBs are larger but slower.
Process Context: Each TLB entry is tagged with an Address Space Identifier (ASID) on modern CPUs, allowing entries from different processes to coexist.
TLB Coverage and Huge Pages:
With 64 TLB entries for 4KB pages, the TLB can cover:
64 × 4 KB = 256 KB
With 32 entries for 2MB huge pages:
32 × 2 MB = 64 MB
This is why huge pages are valuable for large-memory workloads—they dramatically increase TLB coverage without needing larger TLBs.
When the OS modifies a page table entry (e.g., unmapping a page), all cores must invalidate their cached TLB entries for that page. This 'TLB shootdown' requires inter-processor interrupts and is one of the most expensive operations in multi-core systems—another reason context switches and memory remapping have significant overhead.
In 64-bit systems, a single-level page table would require astronomical memory. Instead, hierarchical page tables are used, and frame lookup becomes a multi-step traversal.
The Walk Process:
Start at CR3: The CR3 register contains the physical address of the PML4 table.
Index into PML4: Use bits 47-39 of the virtual address. Read the PML4 entry to get the PDPT physical address.
Index into PDPT: Use bits 38-30. Read the PDPT entry either to get:
Index into PD: Use bits 29-21. Read the PD entry either to get:
Index into PT: Use bits 20-12. Read the PT entry to get the 4KB frame number.
Add Offset: Combine frame number with bits 11-0 to form the physical address.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
#include <stdio.h>#include <stdint.h> /* * Multi-Level Page Table Walk Simulation (x86-64) * * Demonstrates the 4-level page walk process used in * modern 64-bit x86 processors. */ // Extract indices from a 48-bit virtual address#define PML4_INDEX(addr) (((addr) >> 39) & 0x1FF)#define PDPT_INDEX(addr) (((addr) >> 30) & 0x1FF)#define PD_INDEX(addr) (((addr) >> 21) & 0x1FF)#define PT_INDEX(addr) (((addr) >> 12) & 0x1FF)#define OFFSET(addr) ((addr) & 0xFFF) // Simplified page table entrytypedef struct { uint64_t present : 1; uint64_t huge_page : 1; // 2MB or 1GB page uint64_t frame : 40; // Physical frame number (40 bits for 52-bit phys) uint64_t reserved : 22;} SimpleEntry; // Simulated page tables (just enough for demonstration)SimpleEntry pml4[512];SimpleEntry pdpt[512];SimpleEntry pd[512];SimpleEntry pt[512]; void init_page_tables() { // Set up a mapping for address 0x00007FFFF7DD5000 // (typical address for shared library text) // PML4[255] -> PDPT pml4[255].present = 1; pml4[255].frame = 0x1000; // PDPT at physical 0x1000000 // PDPT[511] -> PD pdpt[511].present = 1; pdpt[511].frame = 0x2000; // PD at physical 0x2000000 // PD[507] -> PT pd[507].present = 1; pd[507].frame = 0x3000; // PT at physical 0x3000000 // PT[469] -> Frame 0xABCDE pt[469].present = 1; pt[469].frame = 0xABCDE; // Actual data frame} typedef struct { bool success; uint64_t physical; int memory_accesses;} WalkResult; WalkResult walk_page_table(uint64_t virtual_addr) { WalkResult result = {.success = false, .memory_accesses = 0}; printf("\n╔══════════════════════════════════════════════════════════════╗\n"); printf("║ 4-Level Page Table Walk ║\n"); printf("║ Virtual Address: 0x%016llX ║\n", (unsigned long long)virtual_addr); printf("╠══════════════════════════════════════════════════════════════╣\n"); // Extract all indices uint64_t pml4_idx = PML4_INDEX(virtual_addr); uint64_t pdpt_idx = PDPT_INDEX(virtual_addr); uint64_t pd_idx = PD_INDEX(virtual_addr); uint64_t pt_idx = PT_INDEX(virtual_addr); uint64_t offset = OFFSET(virtual_addr); printf("║ Address Decomposition: ║\n"); printf("║ PML4 Index: %3llu (bits 47-39) ║\n", (unsigned long long)pml4_idx); printf("║ PDPT Index: %3llu (bits 38-30) ║\n", (unsigned long long)pdpt_idx); printf("║ PD Index: %3llu (bits 29-21) ║\n", (unsigned long long)pd_idx); printf("║ PT Index: %3llu (bits 20-12) ║\n", (unsigned long long)pt_idx); printf("║ Offset: 0x%03llX (bits 11-0) ║\n", (unsigned long long)offset); printf("╠══════════════════════════════════════════════════════════════╣\n"); // Step 1: Read PML4 printf("║ Step 1: Read PML4[%llu] ║\n", (unsigned long long)pml4_idx); result.memory_accesses++; if (!pml4[pml4_idx].present) { printf("║ NOT PRESENT - Page Fault! ║\n"); printf("╚══════════════════════════════════════════════════════════════╝\n"); return result; } printf("║ Present: Yes, Points to PDPT at frame 0x%llX ║\n", (unsigned long long)pml4[pml4_idx].frame); // Step 2: Read PDPT printf("║ Step 2: Read PDPT[%llu] ║\n", (unsigned long long)pdpt_idx); result.memory_accesses++; if (!pdpt[pdpt_idx].present) { printf("║ NOT PRESENT - Page Fault! ║\n"); printf("╚══════════════════════════════════════════════════════════════╝\n"); return result; } if (pdpt[pdpt_idx].huge_page) { // 1GB page - translation complete uint64_t frame_1gb = pdpt[pdpt_idx].frame; uint64_t offset_1gb = virtual_addr & 0x3FFFFFFF; // 30 bits result.physical = (frame_1gb << 30) | offset_1gb; result.success = true; printf("║ 1GB HUGE PAGE - Frame 0x%llX ║\n", (unsigned long long)frame_1gb); printf("╚══════════════════════════════════════════════════════════════╝\n"); return result; } printf("║ Present: Yes, Points to PD at frame 0x%llX ║\n", (unsigned long long)pdpt[pdpt_idx].frame); // Step 3: Read PD printf("║ Step 3: Read PD[%llu] ║\n", (unsigned long long)pd_idx); result.memory_accesses++; if (!pd[pd_idx].present) { printf("║ NOT PRESENT - Page Fault! ║\n"); printf("╚══════════════════════════════════════════════════════════════╝\n"); return result; } if (pd[pd_idx].huge_page) { // 2MB page - translation complete uint64_t frame_2mb = pd[pd_idx].frame; uint64_t offset_2mb = virtual_addr & 0x1FFFFF; // 21 bits result.physical = (frame_2mb << 21) | offset_2mb; result.success = true; printf("║ 2MB HUGE PAGE - Frame 0x%llX ║\n", (unsigned long long)frame_2mb); printf("╚══════════════════════════════════════════════════════════════╝\n"); return result; } printf("║ Present: Yes, Points to PT at frame 0x%llX ║\n", (unsigned long long)pd[pd_idx].frame); // Step 4: Read PT printf("║ Step 4: Read PT[%llu] ║\n", (unsigned long long)pt_idx); result.memory_accesses++; if (!pt[pt_idx].present) { printf("║ NOT PRESENT - Page Fault! ║\n"); printf("╚══════════════════════════════════════════════════════════════╝\n"); return result; } uint64_t frame = pt[pt_idx].frame; printf("║ Present: Yes, Frame = 0x%llX ║\n", (unsigned long long)frame); // Form physical address result.physical = (frame << 12) | offset; result.success = true; printf("╠══════════════════════════════════════════════════════════════╣\n"); printf("║ TRANSLATION COMPLETE ║\n"); printf("║ Physical Address: 0x%012llX ║\n", (unsigned long long)result.physical); printf("║ Memory Accesses Required: %d ║\n", result.memory_accesses); printf("╚══════════════════════════════════════════════════════════════╝\n"); return result;} int main() { init_page_tables(); printf("╔══════════════════════════════════════════════════════════════╗\n"); printf("║ MULTI-LEVEL PAGE TABLE WALK DEMONSTRATION ║\n"); printf("╚══════════════════════════════════════════════════════════════╝\n"); // Walk for a typical library address walk_page_table(0x00007FFFF7DD5000ULL); printf("\n═══════════════════════════════════════════════════════════════\n"); printf("INSIGHT: A TLB miss costs 4 memory accesses (one per level)\n"); printf("plus the final data access. Without TLB caching, memory access\n"); printf("would be 4-5× slower!\n"); printf("═══════════════════════════════════════════════════════════════\n"); return 0;}Modern CPUs cache intermediate page walk results. If you access multiple pages under the same PML4 entry, the PML4 entry read is cached and reused. This paging-structure cache reduces walk latency for addresses in the same higher-level region—another layer of optimization beyond the TLB.
Not every frame lookup succeeds. When the Present bit is clear, the page isn't in physical memory, and a page fault exception is raised. This triggers the OS to load the page from secondary storage (disk, swap) and retry the access.
The Page Fault Handler Sequence:
Performance Impact:
Page faults are expensive—potentially millions of times slower than a normal memory access:
| Operation | Latency |
|---|---|
| TLB hit | ~1 ns |
| TLB miss (page walk) | ~50-100 ns |
| Page fault (SSD) | ~100,000 ns (100 μs) |
| Page fault (HDD) | ~10,000,000 ns (10 ms) |
When page faults become too frequent—because the working set exceeds available physical memory—the system enters 'thrashing.' The CPU spends more time waiting for page I/O than doing useful work. This is why adequate RAM is critical for performance: page faults should be rare exceptions, not the common case.
Frame lookup is the core operation in paging—where the virtual-to-physical mapping is resolved. Understanding this process is essential for comprehending memory management, virtual memory, and system performance.
What's Next:
With frame lookup understood, we'll see how the final step—physical address formation—combines the translated frame number with the original offset to create the complete physical memory address. This is where virtual meets physical.
You now understand frame lookup—the central operation in paging that converts page numbers to frame numbers via page table consultation. Combined with the TLB for acceleration and multi-level tables for scalability, this mechanism enables modern virtual memory systems.