7a:T147a,#include #include /* * Page Number Extraction Demonstration * * This program shows how the MMU extracts the page number * from a logical address. In hardware, this is a simple * bit shift that happens in nanoseconds. */ // Common page sizes (in bytes and their log2 values) #define PAGE_SIZE_4KB 4096 // 2^12 - most common on x86 #define PAGE_SIZE_2MB 2097152 // 2^21 - large pages #define PAGE_SIZE_1GB (1ULL << 30) // 2^30 - huge pages // Number of bits for offset (log2 of page size) #define OFFSET_BITS_4KB 12 #define OFFSET_BITS_2MB 21 #define OFFSET_BITS_1GB 30 /** * Extract page number from a logical address * * @param logical_addr The full logical address * @param offset_bits Number of bits used for offset (log2 of page size) * @return The page number */ uint64_t extract_page_number(uint64_t logical_addr, int offset_bits) { // Simply right-shift to discard the offset bits return logical_addr >> offset_bits; } /** * Extract offset from a logical address * * @param logical_addr The full logical address * @param page_size The size of a page in bytes * @return The offset within the page */ uint64_t extract_offset(uint64_t logical_addr, uint64_t page_size) { // Use bitwise AND with (page_size - 1) to mask off page number bits // This works because page_size is always a power of 2 return logical_addr & (page_size - 1); } void demonstrate_extraction(uint64_t addr, const char* addr_name) { printf(" === Analyzing Address: %s (0x%016llX) === ", addr_name, (unsigned long long)addr); // 4KB pages uint64_t page_4kb = extract_page_number(addr, OFFSET_BITS_4KB); uint64_t offset_4kb = extract_offset(addr, PAGE_SIZE_4KB); printf("With 4KB pages (12 offset bits): "); printf(" Page Number: 0x%llX (%llu) ", (unsigned long long)page_4kb, (unsigned long long)page_4kb); printf(" Offset: 0x%llX (%llu) ", (unsigned long long)offset_4kb, (unsigned long long)offset_4kb); printf(" Verification: %llu * 4096 + %llu = %llu ", (unsigned long long)page_4kb, (unsigned long long)offset_4kb, (unsigned long long)(page_4kb * PAGE_SIZE_4KB + offset_4kb)); printf(" Match: %s ", (page_4kb * PAGE_SIZE_4KB + offset_4kb == addr) ? "✓ YES" : "✗ NO"); // 2MB pages (large pages) uint64_t page_2mb = extract_page_number(addr, OFFSET_BITS_2MB); uint64_t offset_2mb = extract_offset(addr, PAGE_SIZE_2MB); printf("With 2MB pages (21 offset bits): "); printf(" Page Number: 0x%llX (%llu) ", (unsigned long long)page_2mb, (unsigned long long)page_2mb); printf(" Offset: 0x%llX (%llu) ", (unsigned long long)offset_2mb, (unsigned long long)offset_2mb); printf(" Match: %s ", (page_2mb * PAGE_SIZE_2MB + offset_2mb == addr) ? "✓ YES" : "✗ NO"); } int main() { printf("╔══════════════════════════════════════════════════════════════╗ "); printf("║ PAGE NUMBER EXTRACTION DEMONSTRATION ║ "); printf("╚══════════════════════════════════════════════════════════════╝ "); // Test with various addresses demonstrate_extraction(0x00001000, "Start of page 1"); demonstrate_extraction(0x00012345, "Address in page 18"); demonstrate_extraction(0x00B5F080, "Address in page 2911"); demonstrate_extraction(0xDEADBEEF, "Classic test pattern"); demonstrate_extraction(0x7FFFFFFF, "Top of 32-bit user space"); // Show the bit manipulation explicitly printf(" === Bit-Level View of Extraction === "); uint64_t addr = 0x00012345; printf("Address: 0x%08llX ", (unsigned long long)addr); printf("Binary: "); for (int i = 31; i >= 0; i--) { printf("%d", (int)((addr >> i) & 1)); if (i == 12) printf(" | "); // Show the split point else if (i % 4 == 0 && i != 0 && i != 12) printf(" "); } printf(" "); printf(" |--- Page Number ---| |-- Offset -----| "); printf(" 20 bits 12 bits "); return 0; } /* * Sample Output: * * ╔══════════════════════════════════════════════════════════════╗ * ║ PAGE NUMBER EXTRACTION DEMONSTRATION ║ * ╚══════════════════════════════════════════════════════════════╝ * * === Analyzing Address: Start of page 1 (0x0000000000001000) === * * With 4KB pages (12 offset bits): * Page Number: 0x1 (1) * Offset: 0x0 (0) * Verification: 1 * 4096 + 0 = 4096 * Match: ✓ YES * * With 2MB pages (21 offset bits): * Page Number: 0x0 (0) * Offset: 0x1000 (4096) * Match: ✓ YES */7b:Tc70,#include #include /* * Demonstration: How page size affects page number extraction * * The same logical address results in different page numbers * depending on the configured page size. */ typedef struct { const char* name; uint64_t size; int offset_bits; } PageSizeConfig; void analyze_address(uint64_t addr, PageSizeConfig configs[], int num_configs) { printf(" Logical Address: 0x%016llX ", (unsigned long long)addr); printf("%-15s | %-20s | %-15s | %s ", "Page Size", "Page Number", "Offset", "Page Boundary"); printf("%-15s-+-%-20s-+-%-15s-+-%s ", "---------------", "--------------------", "---------------", "-------------------------"); for (int i = 0; i < num_configs; i++) { uint64_t page_num = addr >> configs[i].offset_bits; uint64_t offset = addr & (configs[i].size - 1); uint64_t page_start = page_num * configs[i].size; printf("%-15s | 0x%-18llX | 0x%-13llX | 0x%llX - 0x%llX ", configs[i].name, (unsigned long long)page_num, (unsigned long long)offset, (unsigned long long)page_start, (unsigned long long)(page_start + configs[i].size - 1)); } } int main() { PageSizeConfig configs[] = { {"4 KB", 4096ULL, 12}, {"16 KB", 16384ULL, 14}, {"64 KB", 65536ULL, 16}, {"2 MB", 2097152ULL, 21}, {"1 GB", 1073741824ULL, 30}, }; int num_configs = sizeof(configs) / sizeof(configs[0]); printf("═══════════════════════════════════════════════════════════════ "); printf(" HOW PAGE SIZE AFFECTS PAGE NUMBER EXTRACTION "); printf("═══════════════════════════════════════════════════════════════ "); // Test addresses at interesting points analyze_address(0x00123456, configs, num_configs); analyze_address(0x00400000, configs, num_configs); // 4MB - common program start analyze_address(0x7FFFF000, configs, num_configs); // Near 2GB boundary analyze_address(0xDEADBEEF, configs, num_configs); // Classic test pattern printf(" ═══════════════════════════════════════════════════════════════ "); printf("KEY INSIGHT: The same address 0x00123456 is: "); printf(" • Page 291 with 4KB pages (offset 1110 bytes from page start) "); printf(" • Page 18 with 64KB pages (offset 9302 bytes from page start) "); printf(" • Page 0 with 2MB pages (offset 1193046 bytes from start) "); printf("═══════════════════════════════════════════════════════════════ "); return 0; }7c:T1a76,#include #include #include /* * Simulation: Page Number as Page Table Index * * This demonstrates how the extracted page number is used * to index into the page table to find the frame mapping. */ #define PAGE_SIZE 4096 #define OFFSET_BITS 12 #define PAGE_TABLE_SIZE 1024 // Simplified: 1024 entries // Page Table Entry structure (simplified) typedef struct { uint32_t frame_number : 20; // Physical frame number uint32_t present : 1; // Page is in physical memory uint32_t read_write : 1; // 0 = read-only, 1 = read/write uint32_t user_super : 1; // 0 = supervisor, 1 = user accessible uint32_t accessed : 1; // Page has been read uint32_t dirty : 1; // Page has been written uint32_t reserved : 7; // Reserved bits } PageTableEntry; // Simulated page table PageTableEntry page_table[PAGE_TABLE_SIZE]; // Initialize page table with sample mappings void init_page_table() { // Clear all entries for (int i = 0; i < PAGE_TABLE_SIZE; i++) { page_table[i].present = 0; page_table[i].frame_number = 0; } // Set up some valid mappings // Page 0 -> Frame 100 page_table[0].frame_number = 100; page_table[0].present = 1; page_table[0].read_write = 1; page_table[0].user_super = 1; // Page 1 -> Frame 55 page_table[1].frame_number = 55; page_table[1].present = 1; page_table[1].read_write = 1; page_table[1].user_super = 1; // Page 18 -> Frame 0x5A2 (1442) page_table[18].frame_number = 0x5A2; page_table[18].present = 1; page_table[18].read_write = 1; page_table[18].user_super = 1; // Page 42 -> Not present (page fault example) page_table[42].present = 0; } // Extract page number from logical address uint32_t get_page_number(uint64_t logical_addr) { return (uint32_t)(logical_addr >> OFFSET_BITS); } // Extract offset from logical address uint32_t get_offset(uint64_t logical_addr) { return (uint32_t)(logical_addr & (PAGE_SIZE - 1)); } // Simulate address translation bool translate_address(uint64_t logical_addr, uint64_t* physical_addr) { uint32_t page_num = get_page_number(logical_addr); uint32_t offset = get_offset(logical_addr); printf(" ┌─ Address Translation ─────────────────────────────────────┐ "); printf("│ Logical Address: 0x%08llX │ ", (unsigned long long)logical_addr); printf("├────────────────────────────────────────────────────────────┤ "); printf("│ Step 1: Extract page number │ "); printf("│ Logical >> 12 = 0x%08X >> 12 = 0x%05X │ ", (uint32_t)logical_addr, page_num); printf("│ Page Number (p) = %u │ ", page_num); printf("├────────────────────────────────────────────────────────────┤ "); printf("│ Step 2: Index into page table │ "); printf("│ PageTable[%u] │ ", page_num); if (page_num >= PAGE_TABLE_SIZE) { printf("│ ERROR: Page number exceeds table size! │ "); printf("└────────────────────────────────────────────────────────────┘ "); return false; } PageTableEntry* pte = &page_table[page_num]; printf("│ Frame: 0x%05X, Present: %d, R/W: %d │ ", pte->frame_number, pte->present, pte->read_write); if (!pte->present) { printf("├────────────────────────────────────────────────────────────┤ "); printf("│ RESULT: PAGE FAULT - Page not in physical memory! │ "); printf("└────────────────────────────────────────────────────────────┘ "); return false; } // Form physical address *physical_addr = ((uint64_t)pte->frame_number << OFFSET_BITS) | offset; printf("├────────────────────────────────────────────────────────────┤ "); printf("│ Step 3: Form physical address │ "); printf("│ Frame (0x%05X) << 12 | Offset (0x%03X) │ ", pte->frame_number, offset); printf("│ = 0x%05X000 | 0x%03X │ ", pte->frame_number, offset); printf("│ = 0x%08llX │ ", (unsigned long long)*physical_addr); printf("├────────────────────────────────────────────────────────────┤ "); printf("│ RESULT: Physical Address = 0x%08llX │ ", (unsigned long long)*physical_addr); printf("└────────────────────────────────────────────────────────────┘ "); return true; } int main() { init_page_table(); printf("═══════════════════════════════════════════════════════════════ "); printf(" PAGE NUMBER AS PAGE TABLE INDEX "); printf("═══════════════════════════════════════════════════════════════ "); uint64_t physical; // Test translations translate_address(0x00000500, &physical); // Page 0 translate_address(0x00001234, &physical); // Page 1 translate_address(0x00012345, &physical); // Page 18 translate_address(0x0002A000, &physical); // Page 42 - will fault return 0; }7d:T150a,#include #include /* * Multi-Level Page Number Extraction (x86-64 style) * * Demonstrates how a 48-bit virtual address is decomposed * into multiple indices for hierarchical page table lookup. */ // Bit positions for x86-64 4-level paging #define PML4_SHIFT 39 #define PDPT_SHIFT 30 #define PD_SHIFT 21 #define PT_SHIFT 12 #define INDEX_MASK 0x1FF // 9 bits = 512 entries typedef struct { uint16_t pml4_index; // Index into PML4 (Level 4) uint16_t pdpt_index; // Index into PDPT (Level 3) uint16_t pd_index; // Index into Page Directory (Level 2) uint16_t pt_index; // Index into Page Table (Level 1) uint16_t offset; // Offset within page } DecomposedAddress; DecomposedAddress decompose_virtual_address(uint64_t vaddr) { DecomposedAddress result; // Extract each component by shifting and masking result.pml4_index = (vaddr >> PML4_SHIFT) & INDEX_MASK; result.pdpt_index = (vaddr >> PDPT_SHIFT) & INDEX_MASK; result.pd_index = (vaddr >> PD_SHIFT) & INDEX_MASK; result.pt_index = (vaddr >> PT_SHIFT) & INDEX_MASK; result.offset = vaddr & 0xFFF; // Lower 12 bits return result; } void print_address_decomposition(uint64_t vaddr) { DecomposedAddress d = decompose_virtual_address(vaddr); printf(" ╔══════════════════════════════════════════════════════════════╗ "); printf("║ Virtual Address: 0x%016llX ║ ", (unsigned long long)vaddr); printf("╠══════════════════════════════════════════════════════════════╣ "); // Binary representation with groupings printf("║ Binary Layout: ║ "); printf("║ ┌─────────┬─────────┬─────────┬─────────┬────────────┐ ║ "); printf("║ │ PML4 │ PDPT │ PD │ PT │ Offset │ ║ "); printf("║ │ [47:39] │ [38:30] │ [29:21] │ [20:12] │ [11:0] │ ║ "); printf("║ └─────────┴─────────┴─────────┴─────────┴────────────┘ ║ "); printf("╠══════════════════════════════════════════════════════════════╣ "); printf("║ Extracted Indices: ║ "); printf("║ PML4 Index: %3u (0x%03X) → PML4[%3u] ║ ", d.pml4_index, d.pml4_index, d.pml4_index); printf("║ PDPT Index: %3u (0x%03X) → PDPT[%3u] ║ ", d.pdpt_index, d.pdpt_index, d.pdpt_index); printf("║ PD Index: %3u (0x%03X) → PD[%3u] ║ ", d.pd_index, d.pd_index, d.pd_index); printf("║ PT Index: %3u (0x%03X) → PT[%3u] ║ ", d.pt_index, d.pt_index, d.pt_index); printf("║ Offset: %4u (0x%03X) → Byte %u within page ║ ", d.offset, d.offset, d.offset); printf("╚══════════════════════════════════════════════════════════════╝ "); } int main() { printf("═══════════════════════════════════════════════════════════════ "); printf(" x86-64 MULTI-LEVEL PAGE NUMBER EXTRACTION "); printf("═══════════════════════════════════════════════════════════════ "); // User space addresses (canonical, positive) print_address_decomposition(0x0000000000001000ULL); // First 4KB page print_address_decomposition(0x00007FFFF7A3D000ULL); // Typical libc address print_address_decomposition(0x0000555555554000ULL); // Typical program text // Kernel space addresses (canonical, negative - top bits set) print_address_decomposition(0xFFFF800000000000ULL); // Start of kernel space print_address_decomposition(0xFFFFFFFF80000000ULL); // High kernel address printf(" ═══════════════════════════════════════════════════════════════ "); printf("NOTE: Each index (0-511) selects one of 512 entries in its table. "); printf("The full translation requires 4 table lookups + offset addition. "); printf("═══════════════════════════════════════════════════════════════ "); return 0; }72:{"json":{"id":"seed_8f5e1e6d3ff758d1f2530898680803be","slug":"paging-address-translation","category":"Operating Systems","topic":"Paging Address Translation","title":"Paging Address Translation Mechanisms","description":"Master the complete paging address translation process—from extracting page numbers and offsets to frame lookup and physical address formation. Develop deep understanding of how the CPU and MMU collaborate to map virtual addresses to physical memory locations, with comprehensive worked examples.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_7902e2c6368f2e9036f209db8af9435b","title":"Page Number Extraction","order":0,"content":[{"id":"opening-hook","title":"Decoding the Address: The First Split","content":[{"data":{"content":"Every memory access in a paged system begins with a simple but profound operation: **splitting a logical address into two components**. This division—invisible to programmers but fundamental to hardware—separates the *where among pages* (the page number) from the *where within a page* (the offset). Understanding page number extraction is understanding the first step the CPU takes every single time your program touches memory.\n\nWhen your program accesses address `0x00B5F080`, the hardware doesn't search through memory looking for this location. Instead, it extracts the page number as an *index* into a table—a direct lookup that transforms an arbitrary-seeming address into a structured, navigable reference. This extraction happens billions of times per second on modern systems, making it perhaps the most frequently executed operation in computing."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand exactly how the page number is extracted from a logical address through bit manipulation, why the page size determines the boundary between page number and offset, how different page sizes affect address decomposition, and how to manually extract page numbers from any given address. This knowledge is essential for understanding page table lookups and the complete translation process.","variant":"info"},"type":"callout"}]},{"id":"address-anatomy","title":"The Anatomy of a Logical Address","content":[{"data":{"content":"In a paged memory system, every logical (virtual) address is conceptually divided into two parts:\n\n> **Logical Address = Page Number (p) | Offset (d)**\n\nThis division is **not arbitrary**—it is dictated by the page size chosen for the system. The page size determines how many bits are devoted to each portion."},"type":"text"},{"data":{"height":"280px","mermaidSyntax":"graph LR\n subgraph \"32-bit Logical Address (4KB Pages)\"\n A[\"Bit 31 ... Bit 12\"] --> B[\"Page Number (p)\"]\n C[\"Bit 11 ... Bit 0\"] --> D[\"Offset (d)\"]\n end\n \n B --> E[\"20 bits = 2²⁰ = 1,048,576 possible pages\"]\n D --> F[\"12 bits = 2¹² = 4,096 bytes per page\"]"},"type":"mermaid-excalidraw"},{"data":{"content":"**The Mathematical Foundation:**\n\nFor a system with:\n- **Logical address size**: *m* bits\n- **Page size**: *P* = 2^n bytes (page sizes are always powers of 2)\n\nThe address splits as:\n- **Offset bits**: n (to address any byte within a page of size 2^n)\n- **Page number bits**: m - n (to identify which page)\n\n**Example with 32-bit addresses and 4KB pages:**\n\n- Logical address size: m = 32 bits\n- Page size: P = 4 KB = 4,096 bytes = 2^12 bytes, so n = 12\n- Offset bits: 12 (bits 0-11)\n- Page number bits: 32 - 12 = 20 (bits 12-31)\n\nThis creates an address space with:\n- **2^20 = 1,048,576 pages** (each page table can index this many pages)\n- **4,096 addressable locations within each page**"},"type":"text"},{"data":{"icon":"Info","title":"Why Powers of Two?","content":"Page sizes are constrained to powers of two (2^n) because this allows the address to be split using simple bit boundaries. If the page size were, say, 3000 bytes, extracting the page number would require expensive division operations on every memory access. With power-of-two sizes, extraction is instantaneous—just bit slicing, which is trivial in hardware.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"extraction-mechanism","title":"The Extraction Mechanism","content":[{"data":{"content":"Extracting the page number from a logical address is a simple bit operation: **right-shift the address by the number of offset bits**. This discards the offset and leaves only the page number.\n\n**Formula:**\n\n```\nPage Number = Logical Address >> n\n\nwhere n = log₂(page size in bytes)\n```\n\nAlternatively, this can be expressed as integer division:\n\n```\nPage Number = Logical Address / Page Size (integer division)\n```\n\nBoth operations are equivalent when the page size is a power of two."},"type":"text"},{"data":{"rows":[["0x00001000","0000 0000 0000 0000 0001 | 0000 0000 0000","0x00001 = 1","1 × 4096 = 4096 = 0x1000 ✓"],["0x00012345","0000 0000 0000 0001 0010 | 0011 0100 0101","0x00012 = 18","Page 18, offset 0x345"],["0x00B5F080","0000 0000 1011 0101 1111 | 0000 1000 0000","0x00B5F = 2911","Page 2911, offset 0x080"],["0xFFFFFFFF","1111 1111 1111 1111 1111 | 1111 1111 1111","0xFFFFF = 1,048,575","Last page, last byte"],["0x00000FFF","0000 0000 0000 0000 0000 | 1111 1111 1111","0x00000 = 0","Page 0, offset 4095"]],"caption":"Page Number Extraction Examples (4KB Pages)","headers":["Logical Address (Hex)","Logical Address (Binary, showing split)","Page Number","Verification"]},"type":"table"},{"data":{"code":"$7a","fileName":"page_number_extraction.c","showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"Hardware Implementation","content":"In actual hardware, page number extraction doesn't require any computation at all—it's achieved through *wiring*. The upper bits of the address bus are simply routed to the page table lookup circuitry, while the lower bits are held aside to be combined with the frame number later. The 'right shift' is implicit in how the address bits are connected.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"page-size-role","title":"The Role of Page Size in Address Decomposition","content":[{"data":{"content":"The page size fundamentally determines the division between page number and offset. Different page sizes result in dramatically different address structures, with profound implications for the system's behavior."},"type":"text"},{"data":{"rows":[["1 KB (2¹⁰)","10","22","4,194,304","4 GB"],["4 KB (2¹²)","12","20","1,048,576","4 GB"],["16 KB (2¹⁴)","14","18","262,144","4 GB"],["64 KB (2¹⁶)","16","16","65,536","4 GB"],["2 MB (2²¹)","21","11","2,048","4 GB"],["1 GB (2³⁰)","30","2","4","4 GB"]],"caption":"Address Decomposition for Common Page Sizes (32-bit Address Space)","headers":["Page Size","Offset Bits","Page Number Bits","Max Pages","Max Addressable"]},"type":"table"},{"data":{"content":"**The Tradeoff:**\n\n**Larger pages** mean:\n- Fewer bits for page number → smaller page tables (less memory overhead)\n- More bits for offset → larger contiguous blocks\n- Potentially more internal fragmentation (wasted space in partially-used pages)\n- Better TLB coverage (each TLB entry covers more memory)\n\n**Smaller pages** mean:\n- More bits for page number → larger page tables\n- Finer-grained memory allocation → less internal fragmentation\n- Worse TLB coverage (more entries needed to cover same memory)\n- More page faults for large sequential accesses"},"type":"text"},{"data":{"left":[{"data":{"items":["**Fine-grained allocation**: Processes can allocate memory in small increments without waste","**Low internal fragmentation**: On average, only 2KB wasted per allocation","**Good for varied workloads**: Works well for both small and large allocations","**Standard across architectures**: Universal support simplifies portability"],"title":{"icon":"CheckCircle","text":"Advantages of 4KB Pages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Better TLB hit rate**: Each entry covers 512× (2MB) or 262,144× (1GB) more memory","**Reduced page table memory**: Fewer entries to store and traverse","**Faster page walks**: Fewer levels of page table traversal","**Ideal for large datasets**: Databases, VMs, scientific computing benefit significantly"],"title":{"icon":"Zap","text":"Advantages of Large Pages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"code":"$7b","fileName":"page_size_comparison.c","showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Real-World Consideration","content":"Modern systems often support multiple page sizes simultaneously (e.g., 4KB, 2MB, and 1GB on x86-64). The page table structure must indicate which size applies to each mapping. The page number extraction logic in the MMU adapts based on flags in the page table entries, allowing fine-grained choice per memory region.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"page-table-index","title":"Page Number as Page Table Index","content":[{"data":{"content":"The extracted page number serves a critical purpose: it becomes the **index into the page table**. This index directly identifies which page table entry (PTE) contains the mapping information for the referenced page.\n\n**The Lookup Process:**\n\n1. Extract page number *p* from logical address\n2. Use *p* as an index: `PageTable[p]`\n3. The entry at that index contains the frame number (and metadata)\n4. Combine frame number with offset to form physical address"},"type":"text"},{"data":{"height":"320px","mermaidSyntax":"graph LR\n LA[Logical Address\n0x00012345] --> Split{Split}\n Split --> PN[Page Number\np = 0x12 = 18]\n Split --> OFF[Offset\nd = 0x345]\n \n PN --> PTL[Page Table Lookup\nPageTable#91;18#93;]\n PTL --> PTE[Page Table Entry\nFrame = 0x5A2, Valid=1]\n \n PTE --> FR[Frame Number\nf = 0x5A2]\n FR --> Combine{Combine}\n OFF --> Combine\n \n Combine --> PA[Physical Address\n0x005A2345]"},"type":"mermaid-excalidraw"},{"data":{"content":"**Page Table Base Register (PTBR):**\n\nThe CPU maintains a register pointing to the base address of the current process's page table. When a context switch occurs, the OS updates this register to point to the new process's page table. The page number is added to this base to locate the correct entry:\n\n```\nPTE Address = PTBR + (Page Number × Size of PTE)\n```\n\nFor a page table with 4-byte entries:\n```\nPTE Address = PTBR + (p × 4)\n```"},"type":"text"},{"data":{"code":"$7c","fileName":"page_table_indexing.c","showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"Direct Indexing Advantage","content":"The beauty of using the page number as a direct index is that it provides O(1) lookup time. Unlike data structures that require searching (linked lists, trees), the page table provides instantaneous access to any entry. Given page number p, the PTE is always at a calculable offset from the page table base. This constant-time translation is critical for performance.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"multi-level-decomposition","title":"Multi-Level Page Number Decomposition","content":[{"data":{"content":"In systems with large address spaces (64-bit), a single-level page table would be impractically large. Instead, the page number itself is further decomposed into multiple indices, each addressing a different level of a hierarchical page table structure.\n\n**Example: x86-64 with 4-Level Paging (4KB pages, 48-bit virtual addresses):**\n\nThe 48-bit virtual address is split as follows:\n- **Bits 47-39 (9 bits)**: Page Map Level 4 (PML4) index\n- **Bits 38-30 (9 bits)**: Page Directory Pointer Table (PDPT) index \n- **Bits 29-21 (9 bits)**: Page Directory (PD) index\n- **Bits 20-12 (9 bits)**: Page Table (PT) index\n- **Bits 11-0 (12 bits)**: Page offset"},"type":"text"},{"data":{"height":"400px","mermaidSyntax":"graph TB\n VA[48-bit Virtual Address] --> Split[Address Decomposition]\n \n Split --> PML4I[\"PML4 Index\nBits 47-39\n(9 bits = 512 entries)\"]\n Split --> PDPTI[\"PDPT Index\nBits 38-30\n(9 bits = 512 entries)\"]\n Split --> PDI[\"PD Index\nBits 29-21\n(9 bits = 512 entries)\"]\n Split --> PTI[\"PT Index\nBits 20-12\n(9 bits = 512 entries)\"]\n Split --> OFF[\"Offset\nBits 11-0\n(12 bits = 4096 bytes)\"]\n \n PML4I --> L1[\"Level 4 Lookup\"]\n PDPTI --> L2[\"Level 3 Lookup\"]\n PDI --> L3[\"Level 2 Lookup\"]\n PTI --> L4[\"Level 1 Lookup\"]\n OFF --> Final[\"Physical Address\"]"},"type":"mermaid-excalidraw"},{"data":{"rows":[["PML4","47-39 (9)","0-511","8 bytes","4 KB","Points to PDPT"],["PDPT","38-30 (9)","0-511","8 bytes","4 KB","Points to PD (or 1GB page)"],["PD","29-21 (9)","0-511","8 bytes","4 KB","Points to PT (or 2MB page)"],["PT","20-12 (9)","0-511","8 bytes","4 KB","Points to 4KB frame"],["Offset","11-0 (12)","0-4095","N/A","N/A","Byte within page"]],"caption":"Multi-Level Page Table Address Decomposition (x86-64)","headers":["Level","Index Bits","Index Range","Entry Size","Table Size","Purpose"]},"type":"table"},{"data":{"code":"$7d","fileName":"multilevel_page_extraction.c","showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"Why 9 Bits Per Level?","content":"With 9 bits per index level, each table has 512 entries. Each 8-byte entry means each table is exactly 4KB—the same size as a page. This elegant design means page tables themselves fit neatly into physical frames, simplifying memory management for the page tables themselves.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"hardware-perspective","title":"The Hardware Perspective","content":[{"data":{"content":"Understanding page number extraction from the hardware perspective reveals why this operation is so efficient. The Memory Management Unit (MMU) doesn't *compute* anything—it *routes* signals.\n\n**Hardware Implementation:**\n\nWhen the CPU generates a logical address:\n1. The address appears on internal address lines (wires)\n2. The upper address lines (page number bits) are connected to the TLB and page table walker\n3. The lower address lines (offset bits) are held in a buffer\n4. After translation, the frame number replaces the page number via a multiplexer\n5. The physical address (frame + offset) is presented to the memory bus"},"type":"text"},{"data":{"height":"350px","mermaidSyntax":"graph LR\n subgraph \"CPU Address Generation\"\n CPU[CPU Core] --> AR[Address Register\n32/64 bits]\n end\n \n subgraph \"Address Splitting (Wiring)\"\n AR --> Upper[Upper Bits\nPage Number]\n AR --> Lower[Lower Bits\nOffset]\n end\n \n subgraph \"Translation Unit (MMU)\"\n Upper --> TLB[TLB Lookup]\n TLB --> |Hit| Frame[Frame Number]\n TLB --> |Miss| PTW[Page Table Walker]\n PTW --> Frame\n end\n \n subgraph \"Address Formation\"\n Frame --> MUX[Multiplexer]\n Lower --> BUF[Offset Buffer]\n MUX --> PhysUpper[Physical Upper Bits]\n BUF --> PhysLower[Physical Lower Bits]\n end\n \n PhysUpper --> Bus[Memory Bus]\n PhysLower --> Bus"},"type":"mermaid-excalidraw"},{"data":{"content":"**Critical Hardware Properties:**"},"type":"text"},{"data":{"items":["**Zero Computation for Split**: The address lines are simply wired to different destinations. Bits 12-31 go to the translation unit; bits 0-11 go to the offset buffer. No arithmetic required.","**Parallel Operation**: While the TLB looks up the page number, the offset bits are already positioned and ready. The moment the frame number arrives, address formation completes.","**Transistor-Level Speed**: The bit routing happens at electronic signal speed—propagation delay through wires, not computation through logic gates.","**Fixed Latency**: The extraction always takes the same time regardless of the address value. There's no conditional branching or data-dependent timing."],"title":{"icon":"Zap","text":"Hardware Efficiency Features","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**The TLB as Cached Extraction:**\n\nThe Translation Lookaside Buffer (TLB) caches recent page-to-frame translations. When a logical address is presented:\n\n1. **TLB Hit** (common case): The page number directly matches a TLB entry. The frame number is returned immediately (typically 1 clock cycle).\n\n2. **TLB Miss** (rare case): The page number doesn't match any TLB entry. The page table walker traverses the page table hierarchy (20-200+ cycles). The result is cached in the TLB.\n\nThe TLB effectively caches the result of page table lookups, but the *extraction* of the page number happens identically in both cases—it's the lookup step that differs."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Why This Matters for Performance","content":"Memory access is on the critical path of virtually all software. Every instruction fetch, every data load, every store goes through address translation. If page number extraction required even a few clock cycles of computation, it would add nanoseconds to every memory access—slowing down everything. The zero-cost wiring approach ensures translation adds minimal latency.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Page Number Extraction","content":[{"data":{"content":"Page number extraction is the first—and simplest—step in the address translation process, yet its simplicity is what makes paging practical for high-performance systems."},"type":"text"},{"data":{"type":"ordered","items":["**Address Structure**: Every logical address is implicitly divided into page number (upper bits) and offset (lower bits).","**Page Size Determines Split**: For 2^n byte pages, the lower n bits are the offset; the rest form the page number.","**Extraction is Bit Manipulation**: Page number = Address >> n (right shift by offset bits).","**Page Number = Table Index**: The extracted page number directly indexes into the page table for O(1) lookup.","**Multi-Level Extension**: In hierarchical page tables, the page number is further decomposed into multiple indices.","**Hardware Efficiency**: Extraction requires no computation—it's implemented through signal routing (wiring)."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nWith page number extraction understood, we'll examine the complementary operation: **offset extraction**. While the page number identifies *which page*, the offset identifies *which byte within that page*. Together, they provide complete location information—one for coarse-grained lookup, one for fine-grained addressing."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand how the page number is extracted from a logical address—the fundamental first step in paging address translation. This knowledge forms the foundation for understanding the complete translation mechanism: from logical address to physical memory location.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_7ef29b5aca7ec1f6c3210dc6649bf9d4","title":"Offset Extraction","order":1,"content":null,"isLocked":true},{"id":"seed_09c67265c04b16c82b8c97b20d5da787","title":"Frame Lookup","order":2,"content":null,"isLocked":true},{"id":"seed_7201a64f108babedfee0f656f0a920c5","title":"Physical Address Formation","order":3,"content":null,"isLocked":true},{"id":"seed_3850b3fe1b48da1a36f1b386fe78336a","title":"Translation Example","order":4,"content":null,"isLocked":true}]}}