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

Segment Offset Properties Illustrated:
 
Segment: Code (Segment #0)
  Physical Base: 0x00100000
  Limit: 8192 bytes (8 KB)
  
Valid Offsets: 0 to 8191
  ┌────────────────────────────────────────────────┐
  │ Offset 0     → Physical 0x00100000 (first byte) │
  │ Offset 1     → Physical 0x00100001              │
  │ Offset 100   → Physical 0x00100064              │
  │ Offset 4096  → Physical 0x00101000 (midpoint)   │
  │ Offset 8191  → Physical 0x00101FFF (last byte)  │
  ├────────────────────────────────────────────────┤
  │ Offset 8192  → INVALID (exceeds limit)          │
  │ Offset 10000 → INVALID (exceeds limit)          │
  └────────────────────────────────────────────────┘
 
Key Insight: The offset is always relative to the segment's beginning,
never to physical address 0. This enables segments to be relocated
in physical memory without changing the logical addresses used by programs.
 
Programmer's Perspective:
  - Sees addresses 0 to 8191 within the code segment
  - Never knows or cares about physical address 0x00100000
  - Every pointer, instruction address, jump target uses offsets

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

#include <stdio.h>
#include <stdint.h>
 
/*
 * Offset Extraction from Segmented Logical Addresses
 * 
 * Demonstrates the bit masking operation used by hardware
 * to extract the offset (displacement) component.
 */
 
// Architecture configuration
#define LOGICAL_ADDR_BITS    16
#define SEGMENT_BITS          4
#define OFFSET_BITS          12   // LOGICAL_ADDR_BITS - SEGMENT_BITS
 
// Offset mask: m low-order bits set to 1
// For 12 bits: 0x0FFF = 4095 = 111111111111 (binary)
#define OFFSET_MASK          ((1U << OFFSET_BITS) - 1)
 
/**
 * Extract offset from logical address using bit masking
 */
uint16_t extract_offset(uint16_t logical_address) {
    return logical_address & OFFSET_MASK;
}
 
/**
 * Visualize the extraction process
 */
void demonstrate_offset_extraction(uint16_t logical_address) {
    uint16_t offset = extract_offset(logical_address);
    
    printf("Logical Address: 0x%04X\n", logical_address);
    printf("  Binary:        ");
    for (int i = 15; i >= 0; i--) {
        printf("%d", (logical_address >> i) & 1);
        if (i == OFFSET_BITS) printf(" ");  // Visual separator
    }
    printf("\n");
    
    printf("Offset Mask:     ");
    for (int i = 15; i >= 0; i--) {
        printf("%d", (OFFSET_MASK >> i) & 1);
        if (i == OFFSET_BITS) printf(" ");
    }
    printf(" (0x%04X)\n", OFFSET_MASK);
    
    printf("  AND Result:    ");
    for (int i = 15; i >= 0; i--) {
        printf("%d", (offset >> i) & 1);
        if (i == OFFSET_BITS) printf(" ");
    }
    printf("\n");
    
    printf("Extracted Offset: %u (0x%03X)\n\n", offset, offset);
}
 
/**
 * Demonstrate offset range for given segment width
 */
void show_offset_range() {
    uint16_t max_offset = OFFSET_MASK;
    
    printf("=== Offset Range Analysis ===\n");
    printf("Offset bits: %d\n", OFFSET_BITS);
    printf("Minimum offset: 0\n");
    printf("Maximum offset: %u (0x%03X)\n", max_offset, max_offset);
    printf("Total addressable bytes per segment: %u\n\n", max_offset + 1);
}
 
int main() {
    printf("=== Offset Extraction Demo ===\n\n");
    
    show_offset_range();
    
    printf("=== Extraction Examples ===\n\n");
    
    // Test various addresses
    demonstrate_offset_extraction(0x0000);  // Offset = 0
    demonstrate_offset_extraction(0x0001);  // Offset = 1
    demonstrate_offset_extraction(0x0FFF);  // Offset = 4095 (max)
    demonstrate_offset_extraction(0x1000);  // Seg 1, Offset = 0
    demonstrate_offset_extraction(0x1234);  // Seg 1, Offset = 564
    demonstrate_offset_extraction(0x3A5F);  // Seg 3, Offset = 2655
    demonstrate_offset_extraction(0xFFFF);  // Seg 15, Offset = 4095
    
    return 0;
}
 
/*
 * Sample Output:
 * 
 * === Offset Extraction Demo ===
 * 
 * === Offset Range Analysis ===
 * Offset bits: 12
 * Minimum offset: 0
 * Maximum offset: 4095 (0xFFF)
 * Total addressable bytes per segment: 4096
 * 
 * === Extraction Examples ===
 * 
 * Logical Address: 0x3A5F
 *   Binary:        0011 101001011111
 * Offset Mask:     0000 111111111111 (0x0FFF)
 *   AND Result:    0000 101001011111
 * Extracted Offset: 2655 (0xA5F)
 */

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

#include <stdio.h>
#include <stdint.h>
 
/*
 * Analyzing Segment Size Constraints
 * 
 * Demonstrates the relationship between offset width
 * and maximum segment size, plus actual vs maximum usage.
 */
 
typedef struct {
    uint32_t base;       // Physical base address
    uint32_t limit;      // Actual segment size (may be < maximum)
    const char* name;    // Segment name for display
} Segment;
 
void analyze_segment_sizes(int offset_bits) {
    uint64_t max_size = 1ULL << offset_bits;
    
    printf("=== Offset Width: %d bits ===\n", offset_bits);
    printf("Maximum possible segment size: ");
    
    if (max_size >= (1ULL << 30)) {
        printf("%.2f GB\n", max_size / (double)(1ULL << 30));
    } else if (max_size >= (1ULL << 20)) {
        printf("%.2f MB\n", max_size / (double)(1ULL << 20));
    } else if (max_size >= (1ULL << 10)) {
        printf("%.2f KB\n", max_size / (double)(1ULL << 10));
    } else {
        printf("%llu bytes\n", max_size);
    }
    
    printf("Maximum addressable offset: %llu (0x%llX)\n\n", 
           max_size - 1, max_size - 1);
}
 
void show_typical_segment_layout() {
    printf("=== Typical Process Segment Layout (12-bit offset = 4KB max) ===\n\n");
    
    const int MAX_SEGMENT_SIZE = 4096;  // 12-bit offset
    
    Segment segments[] = {
        {0x00100000, 2048, "Code"},      // Uses 50% of maximum
        {0x00101000, 1024, "Data"},      // Uses 25% of maximum
        {0x00102000, 512,  "BSS"},       // Uses 12.5% of maximum
        {0x00103000, 4096, "Heap"},      // Uses 100% of maximum
        {0x00104000, 3072, "Stack"},     // Uses 75% of maximum
    };
    
    int num_segments = sizeof(segments) / sizeof(segments[0]);
    
    printf("%-10s %-12s %-10s %-10s %-15s\n",
           "Segment", "Base", "Limit", "Max Size", "Utilization");
    printf("%-10s %-12s %-10s %-10s %-15s\n",
           "-------", "----", "-----", "--------", "-----------");
    
    for (int i = 0; i < num_segments; i++) {
        Segment* s = &segments[i];
        double utilization = (s->limit * 100.0) / MAX_SEGMENT_SIZE;
        
        printf("%-10s 0x%08X   %-10u %-10u %.1f%%\n",
               s->name, s->base, s->limit, MAX_SEGMENT_SIZE, utilization);
    }
    
    printf("\nKey Insight: Segments use only the memory they need.\n");
    printf("The limit field allows sizes smaller than the architectural maximum.\n");
}
 
int main() {
    // Analyze different offset widths
    analyze_segment_sizes(8);
    analyze_segment_sizes(12);
    analyze_segment_sizes(16);
    analyze_segment_sizes(20);
    analyze_segment_sizes(32);
    
    show_typical_segment_layout();
    
    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

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>  // for offsetof()
 
/*
 * How Compilers Generate Offsets
 * 
 * This demonstrates the various ways offsets appear
 * in compiled code for a segmented architecture.
 */
 
// Global variables - fixed offsets within data segment
int global_a = 100;    // Data segment offset determined at link time
int global_b = 200;    // Assigned next available offset
 
// Struct with field offsets
struct Example {
    int   field1;      // Offset 0
    char  field2;      // Offset 4
    // 3 bytes padding for alignment
    double field3;     // Offset 8
    char  field4[10];  // Offset 16
};  // Total size: 26 bytes (with padding: likely 32)
 
void demonstrate_offsets() {
    // Local variables - offsets relative to stack frame
    int local_x = 50;   // Offset from BP, e.g., [BP-4]
    int local_y = 60;   // Offset from BP, e.g., [BP-8]
    
    // Array - base offset + index computation
    int array[10];
    // array[5] computes: base_offset + (5 * sizeof(int))
    
    printf("=== Offset Analysis ===\n\n");
    
    // Global variable offsets (from data segment base)
    printf("Global Variables (Data Segment Offsets):\n");
    printf("  global_a at address: %p\n", (void*)&global_a);
    printf("  global_b at address: %p\n", (void*)&global_b);
    printf("  Relative offset: %td bytes\n\n",
           (char*)&global_b - (char*)&global_a);
    
    // Local variable offsets (from stack frame)
    printf("Local Variables (Stack Frame Offsets):\n");
    printf("  local_x at address: %p\n", (void*)&local_x);
    printf("  local_y at address: %p\n", (void*)&local_y);
    printf("  Relative offset: %td bytes\n", 
           (char*)&local_y - (char*)&local_x);
    printf("  (Negative = stack grows downward)\n\n");
    
    // Struct field offsets
    printf("Struct Field Offsets:\n");
    printf("  struct Example size: %zu bytes\n", sizeof(struct Example));
    printf("  field1 offset: %zu\n", offsetof(struct Example, field1));
    printf("  field2 offset: %zu\n", offsetof(struct Example, field2));
    printf("  field3 offset: %zu\n", offsetof(struct Example, field3));
    printf("  field4 offset: %zu\n\n", offsetof(struct Example, field4));
    
    // Array element offsets
    printf("Array Element Offsets:\n");
    printf("  array[0] at: %p\n", (void*)&array[0]);
    printf("  array[5] at: %p\n", (void*)&array[5]);
    printf("  Offset computation: 0 + (5 × %zu) = %zu bytes\n",
           sizeof(int), 5 * sizeof(int));
    
    // Function address (code segment offset)
    printf("\nFunction Address (Code Segment Offset):\n");
    printf("  demonstrate_offsets at: %p\n", (void*)demonstrate_offsets);
    printf("  main at: %p\n", (void*)main);
}
 
/*
 * Assembly perspective (x86 example):
 * 
 * ; Accessing struct.field3 (offset 8)
 * mov eax, [ebx+8]     ; EBX contains struct base, 8 is field offset
 * 
 * ; Accessing array[5] (offset = 5 * 4 = 20)
 * mov eax, [esi+20]    ; ESI contains array base, 20 is computed offset
 * 
 * ; Accessing local variable (offset from BP)
 * mov eax, [ebp-4]     ; Local at offset -4 from BP in stack segment
 * 
 * These offsets are all within the current segment.
 * The segment base is added by hardware during translation.
 */
 
int main() {
    demonstrate_offsets();
    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

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
 
/*
 * Segment Offset Bounds Checking
 * 
 * Demonstrates how hardware validates offsets
 * against segment limits before allowing access.
 */
 
typedef struct {
    uint32_t base;
    uint32_t limit;
    const char* name;
} Segment;
 
// Check if offset is valid for segment
bool is_offset_valid(Segment* seg, uint32_t offset, uint32_t access_size) {
    // Check if entire access is within bounds
    // (offset + access_size - 1) must be < limit
    // Using careful arithmetic to avoid overflow
    
    if (offset >= seg->limit) {
        return false;  // Starting offset beyond limit
    }
    
    if (access_size > (seg->limit - offset)) {
        return false;  // Access would extend beyond limit
    }
    
    return true;
}
 
void test_access(Segment* seg, uint32_t offset, uint32_t size) {
    printf("Access: Segment '%s', Offset %u, Size %u bytes\n",
           seg->name, offset, size);
    printf("  Segment limit: %u bytes\n", seg->limit);
    
    if (is_offset_valid(seg, offset, size)) {
        printf("  Result: VALID - access permitted\n");
        printf("  Physical range: 0x%08X to 0x%08X\n",
               seg->base + offset,
               seg->base + offset + size - 1);
    } else {
        printf("  Result: INVALID - SEGMENT FAULT!\n");
        printf("  Reason: Offset %u + size %u exceeds limit %u\n",
               offset, size, seg->limit);
    }
    printf("\n");
}
 
int main() {
    printf("=== Bounds Checking Demo ===\n\n");
    
    Segment data_seg = {
        .base = 0x00200000,
        .limit = 4096,
        .name = "Data"
    };
    
    // Valid accesses
    printf("--- Valid Accesses ---\n");
    test_access(&data_seg, 0, 4);        // First 4 bytes
    test_access(&data_seg, 100, 100);    // Middle range
    test_access(&data_seg, 4092, 4);     // Last 4 bytes (4092 + 4 = 4096)
    
    // Invalid accesses
    printf("--- Invalid Accesses (Would Cause Faults) ---\n");
    test_access(&data_seg, 4096, 1);     // Offset exactly at limit
    test_access(&data_seg, 4000, 100);   // Access extends past limit
    test_access(&data_seg, 5000, 4);     // Offset way beyond limit
    
    // Edge case: zero-size access
    printf("--- Edge Case ---\n");
    test_access(&data_seg, 4095, 1);     // Last valid byte
    test_access(&data_seg, 4095, 2);     // Would extend 1 byte past
    
    return 0;
}
 
/*
 * Hardware Implementation Note:
 * 
 * The bounds check is a simple comparison operation:
 *   if (offset >= limit) generate_fault();
 * 
 * For multi-byte accesses, hardware may check:
 *   if (offset + size > limit) generate_fault();
 * 
 * This comparison occurs in parallel with other translation
 * steps, adding minimal latency. The result gates whether
 * the physical address is actually used.
 */