Segmentation Address Translation

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

#include <stdio.h>
#include <stdint.h>
 
/*
 * Physical Address Formation
 * 
 * The fundamental operation that converts logical addresses
 * to physical addresses in a segmented memory system.
 */
 
// Segment Table Entry
typedef struct {
    uint32_t base;     // Physical starting address
    uint32_t limit;    // Segment size
    uint8_t  present;  // Segment in memory?
} SegmentEntry;
 
// Simple segment table
SegmentEntry segment_table[] = {
    { 0x00100000, 8192,  1 },  // Segment 0: Code
    { 0x00200000, 16384, 1 },  // Segment 1: Data
    { 0x00300000, 4096,  1 },  // Segment 2: Stack
    { 0x00400000, 32768, 1 },  // Segment 3: Heap
};
 
/**
 * Form physical address from segment and offset
 * This is the heart of segmented address translation
 */
uint32_t form_physical_address(uint16_t segment, uint16_t offset) {
    if (segment >= sizeof(segment_table)/sizeof(segment_table[0])) {
        printf("ERROR: Invalid segment number %u\n", segment);
        return 0xFFFFFFFF;  // Invalid marker
    }
    
    SegmentEntry* entry = &segment_table[segment];
    
    if (!entry->present) {
        printf("ERROR: Segment %u not present in memory\n", segment);
        return 0xFFFFFFFF;
    }
    
    if (offset >= entry->limit) {
        printf("ERROR: Offset %u exceeds limit %u for segment %u\n",
               offset, entry->limit, segment);
        return 0xFFFFFFFF;
    }
    
    // THE KEY OPERATION: base + offset
    uint32_t physical_address = entry->base + offset;
    
    return physical_address;
}
 
void demonstrate_translation(uint16_t segment, uint16_t offset) {
    printf("Logical: (Segment %u, Offset %u)\n", segment, offset);
    
    if (segment < sizeof(segment_table)/sizeof(segment_table[0])) {
        SegmentEntry* entry = &segment_table[segment];
        printf("  Base:   0x%08X\n", entry->base);
        printf("  Offset: 0x%08X\n", offset);
        printf("  ------------------------\n");
    }
    
    uint32_t physical = form_physical_address(segment, offset);
    
    if (physical != 0xFFFFFFFF) {
        printf("  Physical Address: 0x%08X\n", physical);
    }
    printf("\n");
}
 
int main() {
    printf("=== Physical Address Formation Demo ===\n\n");
    
    printf("Segment Table:\n");
    printf("  Seg 0 (Code):  Base=0x00100000, Limit=8192\n");
    printf("  Seg 1 (Data):  Base=0x00200000, Limit=16384\n");
    printf("  Seg 2 (Stack): Base=0x00300000, Limit=4096\n");
    printf("  Seg 3 (Heap):  Base=0x00400000, Limit=32768\n\n");
    
    printf("=== Translation Examples ===\n\n");
    
    // Valid accesses
    demonstrate_translation(0, 0);      // First byte of code
    demonstrate_translation(0, 100);    // 100 bytes into code
    demonstrate_translation(1, 1000);   // 1000 bytes into data
    demonstrate_translation(2, 2048);   // Middle of stack
    demonstrate_translation(3, 32767);  // Last byte of heap
    
    printf("=== Error Cases ===\n\n");
    
    // Invalid accesses
    demonstrate_translation(0, 10000);  // Exceeds limit
    demonstrate_translation(5, 0);      // Invalid segment
    
    return 0;
}
 
/*
 * Key Insight:
 * 
 * The addition base + offset is the entire mechanism for relocation.
 * 
 * Without it: Programs would need absolute addresses, loading at
 * a different location would require rewriting all addresses.
 * 
 * With it: Programs use offsets from 0, the OS can place them
 * anywhere by setting the base, and no address rewriting is needed.
 */

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

#include <stdio.h>
#include <stdint.h>
 
/*
 * Comparing Base Address Computation Methods
 * 
 * Different architectures obtain the segment base differently.
 */
 
// ============================================
// Method 1: Intel 8086 Real Mode
// Physical = Segment × 16 + Offset
// ============================================
 
uint32_t real_mode_translate(uint16_t segment, uint16_t offset) {
    // Shift segment left by 4 bits (multiply by 16)
    uint32_t base = (uint32_t)segment << 4;
    uint32_t physical = base + offset;
    
    // Result is 20 bits (1 MB address space)
    return physical & 0xFFFFF;
}
 
void demo_real_mode() {
    printf("=== Intel 8086 Real Mode ===\n");
    printf("Formula: Physical = Segment × 16 + Offset\n\n");
    
    // Classic example: 0000:0000 = 0x00000
    printf("0000:0000 = 0x%05X\n", real_mode_translate(0x0000, 0x0000));
    
    // 1000:0000 = 0x10000
    printf("1000:0000 = 0x%05X\n", real_mode_translate(0x1000, 0x0000));
    
    // FFFF:000F = 0xFFFF0 + 0x000F = 0xFFFFF (max address)
    printf("FFFF:000F = 0x%05X\n", real_mode_translate(0xFFFF, 0x000F));
    
    // Overlapping addresses: different segment:offset, same physical
    printf("\nOverlap demonstration:\n");
    printf("0100:0000 = 0x%05X\n", real_mode_translate(0x0100, 0x0000));
    printf("00FF:0010 = 0x%05X\n", real_mode_translate(0x00FF, 0x0010));
    printf("00F0:0100 = 0x%05X\n", real_mode_translate(0x00F0, 0x0100));
    printf("(All three map to physical 0x01000!)\n\n");
}
 
// ============================================
// Method 2: Protected Mode with Table Lookup
// Physical = Base_from_Descriptor + Offset
// ============================================
 
typedef struct {
    uint32_t base;
    uint32_t limit;
    uint16_t attributes;
} DescriptorCache;
 
// Global Descriptor Table (simplified)
typedef struct {
    uint16_t limit_low;
    uint16_t base_low;
    uint8_t  base_mid;
    uint8_t  access;
    uint8_t  limit_high_flags;
    uint8_t  base_high;
} GDTEntry;
 
// Simulated GDT
GDTEntry gdt[] = {
    {0, 0, 0, 0, 0, 0},  // Null descriptor
    {0xFFFF, 0x0000, 0x10, 0x9A, 0xCF, 0x00},  // Code: base=0x100000
    {0xFFFF, 0x0000, 0x20, 0x92, 0xCF, 0x00},  // Data: base=0x200000
};
 
// Extract base address from GDT entry
uint32_t get_base_from_descriptor(GDTEntry* entry) {
    return entry->base_low | 
           ((uint32_t)entry->base_mid << 16) |
           ((uint32_t)entry->base_high << 24);
}
 
uint32_t protected_mode_translate(uint16_t selector, uint32_t offset) {
    // Extract index (bits 3-15 of selector)
    uint16_t index = selector >> 3;
    
    if (index >= sizeof(gdt)/sizeof(gdt[0])) {
        printf("Invalid selector\n");
        return 0xFFFFFFFF;
    }
    
    GDTEntry* entry = &gdt[index];
    uint32_t base = get_base_from_descriptor(entry);
    
    return base + offset;
}
 
void demo_protected_mode() {
    printf("=== Intel Protected Mode ===\n");
    printf("Formula: Physical = Base_from_GDT[Selector>>3] + Offset\n\n");
    
    // Selector 0x08 = index 1, code segment
    printf("Selector 0x08, Offset 0x1000:\n");
    printf("  Physical = 0x%08X\n\n", protected_mode_translate(0x08, 0x1000));
    
    // Selector 0x10 = index 2, data segment
    printf("Selector 0x10, Offset 0x2000:\n");
    printf("  Physical = 0x%08X\n\n", protected_mode_translate(0x10, 0x2000));
}
 
int main() {
    demo_real_mode();
    demo_protected_mode();
    
    printf("=== Key Difference ===\n");
    printf("Real Mode: Base is computed from segment value (segment × 16)\n");
    printf("Protected Mode: Base is looked up from descriptor table\n");
    printf("Protected Mode base can be any 32-bit value, enabling flexible placement.\n");
    
    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

Physical Address Adder - Hardware View:
 
Inputs:
  - Base[31:0]: 32-bit base address from segment table
  - Offset[15:0]: 16-bit offset (zero-extended to 32 bits)
 
Output:
  - Physical[31:0]: 32-bit physical address
 
Circuit (Carry-Lookahead Adder):
 
     Base[31:0]          Offset[31:0] (zero-extended)
         │                     │
         └───────┬─────────────┘
                 │
         ┌───────▼───────┐
         │   32-bit CLA  │
         │     Adder     │
         │               │
         │  P = B + O    │
         └───────┬───────┘
                 │
         Physical[31:0]
 
Timing Analysis:
  - Input latch: 1 cycle
  - CLA addition: ~log2(32) = 5 gate delays
  - Output buffer: 1 cycle
  - Total: approximately 1-2 clock cycles
 
Parallel with Bounds Check:
  
  Time ─────────────────────────────────────▶
  
  Bounds │ Compare │ Result │
  Check  │ offset  │ valid/ │
         │ < limit │ fault  │
         
  Address│ Add base│ Physical│ Gate   │ Output
  Calc   │+ offset │ ready   │ check  │ to bus
  
  Both paths complete in approximately the same time.
  The gate only passes the physical address if bounds check passed.

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

#include <stdio.h>
#include <stdint.h>
 
/*
 * Special Cases in Physical Address Formation
 */
 
#define ADDR_BITS 32
#define ADDR_MASK ((1ULL << ADDR_BITS) - 1)
 
// Simulate different wraparound behaviors
enum WrapBehavior { WRAP_TRUNCATE, WRAP_FAULT };
 
uint64_t form_address_with_wrap(uint32_t base, uint32_t offset, 
                                 enum WrapBehavior behavior,
                                 int* wrapped) {
    uint64_t sum = (uint64_t)base + (uint64_t)offset;
    *wrapped = (sum > ADDR_MASK);
    
    switch (behavior) {
        case WRAP_TRUNCATE:
            return sum & ADDR_MASK;
        case WRAP_FAULT:
            if (*wrapped) return 0xFFFFFFFFFFFFFFFF;  // Invalid marker
            return sum;
    }
    return sum;
}
 
void test_special_case(const char* name, uint32_t base, uint32_t offset) {
    int wrapped;
    
    printf("Case: %s\n", name);
    printf("  Base: 0x%08X, Offset: 0x%08X\n", base, offset);
    
    // 64-bit sum to see overflow
    uint64_t raw_sum = (uint64_t)base + (uint64_t)offset;
    printf("  Raw sum (64-bit): 0x%016llX\n", (unsigned long long)raw_sum);
    
    // Truncating behavior
    uint64_t truncated = form_address_with_wrap(base, offset, WRAP_TRUNCATE, &wrapped);
    printf("  Truncate (32-bit): 0x%08X%s\n", 
           (uint32_t)truncated, wrapped ? " [WRAPPED]" : "");
    
    // Fault behavior
    uint64_t fault_check = form_address_with_wrap(base, offset, WRAP_FAULT, &wrapped);
    if (fault_check == 0xFFFFFFFFFFFFFFFF) {
        printf("  Fault check: FAULT (overflow detected)\n");
    } else {
        printf("  Fault check: 0x%08X (valid)\n", (uint32_t)fault_check);
    }
    printf("\n");
}
 
int main() {
    printf("=== Special Cases in Physical Address Formation ===\n\n");
    
    // Normal case
    test_special_case("Normal", 0x00100000, 0x00001000);
    
    // Zero base
    test_special_case("Zero Base", 0x00000000, 0x00001000);
    
    // Zero offset
    test_special_case("Zero Offset", 0x00100000, 0x00000000);
    
    // Near end of address space
    test_special_case("Near Edge", 0xFFFF0000, 0x0000FF00);
    
    // Overflow case
    test_special_case("Overflow", 0xFFFFF000, 0x00002000);
    
    printf("=== Intel 8086 A20 Gate Example ===\n\n");
    
    // The A20 gate masked bit 20 of the address for 8086 compatibility
    uint32_t addr = real_mode_example(0xFFFF, 0x0010);
    printf("Real mode FFFF:0010 = 0x%05X\n", addr & 0xFFFFF);
    printf("With A20 gate disabled: 0x%05X (bit 20 masked)\n", 
           addr & 0xEFFFF);
    
    return 0;
}
 
// Intel 8086 real mode calculation
uint32_t real_mode_example(uint16_t seg, uint16_t off) {
    return ((uint32_t)seg << 4) + off;
}

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

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
 
/*
 * Complete Segmented Address Translation Pipeline
 * 
 * Implements all steps from logical address to physical address.
 */
 
// Access types for permission checking
typedef enum {
    ACCESS_READ   = 0x01,
    ACCESS_WRITE  = 0x02,
    ACCESS_EXEC   = 0x04
} AccessType;
 
// Segment Table Entry
typedef struct {
    uint32_t base;
    uint32_t limit;
    bool     present;
    uint8_t  permissions;  // Combination of AccessType flags
    bool     accessed;
    bool     dirty;
} SegmentTableEntry;
 
// Translation result
typedef struct {
    bool     success;
    uint32_t physical_address;
    char     error_message[100];
} TranslationResult;
 
// Simulated segment table
#define MAX_SEGMENTS 16
SegmentTableEntry segment_table[MAX_SEGMENTS];
uint32_t STLR = 5;  // Segment Table Length Register
 
void init_segment_table() {
    // Segment 0: Code (Read + Execute)
    segment_table[0] = (SegmentTableEntry){
        .base = 0x00100000, .limit = 8192, .present = true,
        .permissions = ACCESS_READ | ACCESS_EXEC
    };
    // Segment 1: Data (Read + Write)
    segment_table[1] = (SegmentTableEntry){
        .base = 0x00200000, .limit = 16384, .present = true,
        .permissions = ACCESS_READ | ACCESS_WRITE
    };
    // Segment 2: Stack (Read + Write)
    segment_table[2] = (SegmentTableEntry){
        .base = 0x00300000, .limit = 4096, .present = true,
        .permissions = ACCESS_READ | ACCESS_WRITE
    };
    // Segment 3: Heap (Read + Write)
    segment_table[3] = (SegmentTableEntry){
        .base = 0x00400000, .limit = 32768, .present = true,
        .permissions = ACCESS_READ | ACCESS_WRITE
    };
    // Segment 4: Not present (swapped out)
    segment_table[4] = (SegmentTableEntry){
        .base = 0, .limit = 8192, .present = false,
        .permissions = ACCESS_READ | ACCESS_WRITE
    };
}
 
/**
 * Complete translation pipeline
 */
TranslationResult translate_address(uint16_t segment, uint16_t offset, 
                                     AccessType access_type) {
    TranslationResult result = { .success = false };
    
    // Step 1: Check segment number against STLR
    if (segment >= STLR) {
        snprintf(result.error_message, sizeof(result.error_message),
                "Invalid segment: %u >= STLR(%u)", segment, STLR);
        return result;
    }
    
    // Step 2: Look up segment table entry
    SegmentTableEntry* ste = &segment_table[segment];
    
    // Step 3: Check present bit
    if (!ste->present) {
        snprintf(result.error_message, sizeof(result.error_message),
                "Segment %u not present in memory", segment);
        return result;
    }
    
    // Step 4: Check permissions
    if ((ste->permissions & access_type) != access_type) {
        const char* access_name = 
            access_type == ACCESS_READ ? "read" :
            access_type == ACCESS_WRITE ? "write" : "execute";
        snprintf(result.error_message, sizeof(result.error_message),
                "Permission denied: cannot %s segment %u", access_name, segment);
        return result;
    }
    
    // Step 5: Bounds checking
    if (offset >= ste->limit) {
        snprintf(result.error_message, sizeof(result.error_message),
                "Bounds violation: offset %u >= limit %u", offset, ste->limit);
        return result;
    }
    
    // Step 6: Form physical address
    result.physical_address = ste->base + offset;
    result.success = true;
    
    // Update accessed/dirty bits
    ste->accessed = true;
    if (access_type == ACCESS_WRITE) {
        ste->dirty = true;
    }
    
    return result;
}
 
void test_translation(uint16_t seg, uint16_t off, AccessType access) {
    const char* access_str = 
        access == ACCESS_READ ? "READ" :
        access == ACCESS_WRITE ? "WRITE" : "EXEC";
    
    printf("Translate: (Seg %u, Off %u) [%s]\n", seg, off, access_str);
    
    TranslationResult result = translate_address(seg, off, access);
    
    if (result.success) {
        printf("  SUCCESS: Physical = 0x%08X\n", result.physical_address);
    } else {
        printf("  FAULT: %s\n", result.error_message);
    }
    printf("\n");
}
 
int main() {
    printf("=== Complete Translation Pipeline Demo ===\n\n");
    
    init_segment_table();
    
    printf("--- Successful Translations ---\n\n");
    test_translation(0, 1000, ACCESS_READ);   // Read from code
    test_translation(0, 1000, ACCESS_EXEC);   // Execute from code
    test_translation(1, 2000, ACCESS_WRITE);  // Write to data
    test_translation(2, 500, ACCESS_READ);    // Read from stack
    
    printf("--- Fault Conditions ---\n\n");
    test_translation(0, 1000, ACCESS_WRITE);  // Write to code (no permission)
    test_translation(1, 20000, ACCESS_READ);  // Offset exceeds limit
    test_translation(4, 0, ACCESS_READ);      // Segment not present
    test_translation(10, 0, ACCESS_READ);     // Invalid segment number
    
    return 0;
}