Paging Address Translation Mechanisms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

#include <stdio.h>
#include <stdint.h>
 
/*
 * 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
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <stdio.h>
#include <stdint.h>
 
/*
 * 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
 
/*
 * 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include <stdio.h>
#include <stdint.h>
 
/*
 * 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;
}