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

// Original program compiled for address 0
// Relocation table included in executable
EXECUTABLE FILE:
    Header:
        entry_point: 0x0100        // Relative to start
        text_size: 0x1000          // Code section size
        data_size: 0x0500          // Data section size
        relocation_entries: 4      // Number of addresses to fix
        
    Relocation Table:              // Offsets needing adjustment
        [0x0102, 0x0108, 0x0202, 0x0208]
        
    Code Section (at relative 0x0000):
        0x0100: CALL 0x0200        // Call increment() - NEEDS RELOCATION
        0x0106: MOV R1, [0x0300]   // Load global_counter - NEEDS RELOCATION
        0x010C: RET
        
        0x0200: INC [0x0300]       // Write global_counter - NEEDS RELOCATION
        0x0206: RET
        
    Data Section (at relative 0x0300):
        0x0300: .word 0            // global_counter
 
// Loader relocates to address 0x50000
PROCEDURE LoadWithRelocation(executable: File, load_address: ADDRESS):
    // Load code and data into memory at load_address
    CopyToMemory(executable.code, load_address)
    CopyToMemory(executable.data, load_address + executable.text_size)
    
    // Apply relocation to each entry
    FOR EACH offset IN executable.relocation_table:
        physical_location := load_address + offset
        original_value := ReadMemory(physical_location)
        adjusted_value := original_value + load_address
        WriteMemory(physical_location, adjusted_value)
    END FOR
    
    // Calculate actual entry point
    entry := load_address + executable.entry_point
    RETURN entry
 
// After relocation at 0x50000:
MEMORY AT 0x50000:
    0x50100: CALL 0x50200        // Fixed: 0x0200 + 0x50000
    0x50106: MOV R1, [0x50300]   // Fixed: 0x0300 + 0x50000
    0x5010C: RET
    
    0x50200: INC [0x50300]       // Fixed: 0x0300 + 0x50000
    0x50206: RET
    
    0x50300: .word 0             // global_counter at 0x50300

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

// Hardware unit for dynamic address relocation
HARDWARE_UNIT RelocationUnit:
 
    // The relocation register (privileged - only OS can modify)
    RelocationRegister: REGISTER[32 bits]
    
    // This function executes on EVERY memory access
    // It happens in parallel with address generation (zero additional cycles)
    FUNCTION TranslateAddress(logical_address: ADDRESS) -> ADDRESS:
        
        // Simply add the relocation register value
        physical_address := logical_address + RelocationRegister
        
        RETURN physical_address
        
    END FUNCTION
 
// Context switch updates the relocation register
KERNEL_PROCEDURE SwitchProcess(old_proc: PCB, new_proc: PCB):
    // Save old relocation value
    IF old_proc != NULL THEN
        old_proc.saved_relocation_reg := CPU.RelocationRegister
    END IF
    
    // Load new relocation value
    CPU.RelocationRegister := new_proc.saved_relocation_reg
    
    // All subsequent memory accesses from new_proc will
    // be translated using the new relocation value
 
END PROCEDURE
 
// Loading a process with dynamic relocation
KERNEL_PROCEDURE LoadProcess(program: Executable, base_address: ADDRESS):
    // Copy program code and data to memory (no address modification needed!)
    CopyToMemory(program.code, base_address)
    CopyToMemory(program.data, base_address + program.code_size)
    
    // Create process control block
    pcb := AllocatePCB()
    pcb.saved_relocation_reg := base_address  // Key: store base address
    pcb.program_counter := program.entry_point // Logical entry point
    
    // When this process runs, hardware will translate addresses
    AddToReadyQueue(pcb)
 
END PROCEDURE

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

/*
 * Combined relocation and protection hardware simulation
 * This represents what happens in hardware on every memory access
 */
 
#include <stdint.h>
#include <stdbool.h>
 
typedef struct {
    uint32_t base;      /* Relocation register (physical base) */
    uint32_t limit;     /* Limit register (region size) */
    bool user_mode;     /* Current execution mode */
} cpu_protection_state;
 
typedef enum {
    ACCESS_OK,
    ACCESS_VIOLATION,
    ACCESS_PRIVILEGE_ERROR
} access_result;
 
/* This function represents hardware logic - executes every memory access */
access_result translate_and_check(
    cpu_protection_state *cpu,
    uint32_t logical_address,
    uint32_t *physical_address_out,
    int access_type  /* READ, WRITE, EXECUTE */
) {
    /* 
     * Supervisor mode: no translation or checking
     * The kernel accesses physical memory directly
     */
    if (!cpu->user_mode) {
        *physical_address_out = logical_address;
        return ACCESS_OK;
    }
    
    /*
     * User mode: enforce protection
     * Step 1: Check bounds BEFORE translation
     */
    if (logical_address >= cpu->limit) {
        /*
         * PROTECTION VIOLATION
         * The hardware will:
         * 1. Cancel the memory access (it never reaches the bus)
         * 2. Save the current PC and state
         * 3. Switch to supervisor mode
         * 4. Jump to the protection fault handler
         */
        return ACCESS_VIOLATION;
    }
    
    /*
     * Step 2: Address translation (relocation)
     * Add base to get physical address
     */
    *physical_address_out = cpu->base + logical_address;
    
    /*
     * The translated address is now used for the actual memory access
     * The process NEVER sees the physical address
     */
    return ACCESS_OK;
}
 
/*
 * Example: Process A loaded at 0x50000 with 64KB region
 *          Process B loaded at 0x60000 with 128KB region
 */
void demonstrate_isolation(void) {
    cpu_protection_state proc_a = { 
        .base = 0x50000, 
        .limit = 0x10000,  /* 64KB */
        .user_mode = true 
    };
    
    cpu_protection_state proc_b = { 
        .base = 0x60000, 
        .limit = 0x20000,  /* 128KB */
        .user_mode = true 
    };
    
    uint32_t physical;
    
    /* Process A: legitimate access to its own memory */
    /* Logical 0x1000 -> Physical 0x51000 (in A's region) */
    translate_and_check(&proc_a, 0x1000, &physical, ACCESS_READ);
    /* Result: ACCESS_OK, physical = 0x51000 */
    
    /* Process A: attempt to access beyond its limit */
    /* Logical 0x15000 (exceeds 64KB limit) */
    translate_and_check(&proc_a, 0x15000, &physical, ACCESS_READ);
    /* Result: ACCESS_VIOLATION (trapped to OS) */
    
    /* Process A: cannot access B's memory */
    /* Even if A knew B's physical address (0x60000), it can't issue it */
    /* A's logical address 0x10000 exceeds its limit of 0x10000 */
    /* Any address >= 0x10000 violates A's protection */
    
    /* Process B: separate address space */
    /* Logical 0x1000 -> Physical 0x61000 (in B's region) */
    translate_and_check(&proc_b, 0x1000, &physical, ACCESS_READ);
    /* Result: ACCESS_OK, physical = 0x61000 */
    /* Note: same logical address, different physical address! */
}

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

// Memory compaction with dynamic relocation
PROCEDURE CompactMemory():
    // Suspend all processes (no scheduling during compaction)
    PauseScheduler()
    
    // Disable interrupts (critical section)
    DisableInterrupts()
    
    // Calculate new positions for all processes
    new_base := OS_BOUNDARY  // Start just after OS
    FOR EACH process IN processes_ordered_by_current_base:
        process.new_base := new_base
        new_base := new_base + process.size
    END FOR
    
    // Move processes that need moving
    // IMPORTANT: Move in order to avoid overwriting uncopied data
    FOR EACH process IN processes_ordered_by_current_base:
        IF process.new_base != process.base THEN
            // Copy entire process image to new location
            CopyMemory(
                source: process.base,
                destination: process.new_base,
                size: process.size
            )
            
            // Update relocation register in process's PCB
            process.saved_relocation_reg := process.new_base
            
            // If this process is current, update hardware register too
            IF process == current_process THEN
                CPU.RelocationRegister := process.new_base
            END IF
            
            // Old location is now free (part of consolidated hole)
            process.base := process.new_base
        END IF
    END FOR
    
    // Update free list: now one large hole at top
    free_list := CreateHole(new_base, MEMORY_TOP - new_base)
    
    // Resume normal operation
    EnableInterrupts()
    ResumeScheduler()
    
    // All processes continue transparently
    // They don't know they were moved!
    
END PROCEDURE
 
// The key insight: no process code is modified during compaction
// Only the relocation register values change
// Processes are completely unaware of the move
 
EXAMPLE:
    Before: Process P2 at Base=0x30000, accessing logical 0x1000
            -> Physical 0x31000
    
    After compaction: P2 moved to Base=0x20000
                     P2 still accesses logical 0x1000
                     -> Physical 0x21000 (different location, same content)
    
    P2's code is identical. Only the PCB's relocation register changed.

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

/*
 * Modern relocation concepts: GOT and PLT
 * This is how shared libraries achieve position independence
 */
 
/*
 * Traditional code (non-PIC) - problematic for shared libraries:
 * 
 * CALL 0x12345678    ; Absolute address of printf
 * MOV EAX, [0x87654321]  ; Absolute address of global_var
 * 
 * These addresses would need to change based on where the
 * library is loaded - requiring separate copies of the code!
 */
 
/*
 * Position-Independent Code (PIC) - modern approach:
 * 
 * Code references (function calls) use PLT (Procedure Linkage Table):
 * 
 * CALL printf@PLT    ; Call through PLT entry
 *                    ; PLT entry contains:
 *                    ; JMP *[GOT entry for printf]
 * 
 * Data references use GOT (Global Offset Table):
 * 
 * MOV EAX, global_var@GOT  ; Get GOT offset (known at compile time)
 * ADD EAX, [GOT_BASE]      ; Add GOT base (found at runtime via PC)
 * MOV EAX, [EAX]           ; Load actual address from GOT
 * MOV EBX, [EAX]           ; Finally access the variable
 */
 
/* Example of how GOT works conceptually */
struct global_offset_table {
    void *printf_addr;        /* Filled by dynamic linker */
    void *malloc_addr;        /* Filled by dynamic linker */
    int  *global_var_addr;    /* Filled by dynamic linker/loader */
    /* ... more entries */
};
 
/* The GOT itself is at a fixed offset from the code (known at link time) */
/* The GOT entries are filled at load time with actual addresses */
 
/* 
 * Runtime flow:
 * 1. Loader loads shared library at random address (ASLR)
 * 2. Loader/dynamic linker fills in GOT entries with actual addresses
 * 3. Code uses PC-relative access to find GOT
 * 4. Code uses GOT entries to find actual function/data addresses
 * 
 * Result: Same code works at any load address!
 * This is essentially dynamic relocation, but more sophisticated
 */
 
/*
 * Compiling for position independence:
 * 
 * $ gcc -fPIC -shared -o libexample.so example.c
 * 
 * -fPIC: Generate position-independent code
 * -shared: Create shared library (not executable)
 */