Mechanism: Address Translation

Core Requirements for Memory Virtualization

Memory virtualization must simultaneously deliver efficiency, control and flexibility. Efficiency forbids software intervention on every access; control forbids any process from touching another process or the kernel; flexibility lets an application lay out code, heap and stack however it wishes, as if it owned a contiguous space beginning at address zero. Hardware address translation is the mechanism built exactly for these three goals.

Dynamic Relocation via Base and Bounds

The processor supplies a privileged pair of registers: the base register holds the physical starting location of a process, the bounds register holds the length of its address space. On every instruction fetch, load or store the hardware first compares the issued virtual address against the bounds; an out-of-range value raises a protection exception at once, otherwise the virtual address is added to the base to obtain the true physical address. The whole translation is invisible to user code, which continues to believe it runs from address zero.

How the OS Configures the Hardware

Hardware only supplies the fast path of translation and checking; policy remains with the operating system. The kernel keeps a list of free physical regions, allocates a large enough contiguous slot for a new process, writes the slot’s starting address into the base register and the address-space size into the bounds register. Both registers must be updated together on every context switch, otherwise the incoming process would see an incorrect mapping. An out-of-bounds exception is caught by the kernel, which typically terminates the offending process so the rest of the system stays unharmed.

Pitfalls

• Thinking only data accesses need translation and forgetting that instruction fetches also pass through the base-bounds check
• Believing software can relocate every access itself while ignoring the enormous performance cost
• Updating only a page-table pointer on context switch and forgetting to keep the base and bounds registers in sync

Minimum C11 · complete program · Download .c

#include <stdio.h>
#include <stdint.h>

int main(void) {
    const uint32_t base = 40960; /* 40 KB */
    const uint32_t bound = 16384; /* 16 KB */
    printf("Simulating hardware address translation\n");
    printf("Base register: %u (0x%x)\n", base, base);
    printf("Bounds register: %u (0x%x)\n\n", bound, bound);
    uint32_t test_vas[] = {0, 8192, 16383, 16384, 20480};
    int n = 5;
    for (int i = 0; i < n; ++i) {
        uint32_t va = test_vas[i];
        printf("Virtual address %u (0x%x): ", va, va);
        if (va >= bound) {
            printf("OUT OF BOUNDS - exception raised\n");
        } else {
            uint32_t pa = va + base;
            printf("translates to physical %u (0x%x)\n", pa, pa);
        }
    }
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-15-address-translation.c -o example && ./example

Expected result

Simulating hardware address translation
Base register: 40960 (0xa000)
Bounds register: 16384 (0x4000)

Virtual address 0 (0x0): translates to physical 40960 (0xa000)
Virtual address 8192 (0x2000): translates to physical 49152 (0xc000)
Virtual address 16383 (0x3fff): translates to physical 57343 (0xdfff)
Virtual address 16384 (0x4000): OUT OF BOUNDS - exception raised
Virtual address 20480 (0x5000): OUT OF BOUNDS - exception raised

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A process has a 16 KB address space that the OS has placed at physical address 40 KB. What physical address corresponds to virtual address 8 KB? What does the hardware do if the process accesses virtual address 20 KB?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.