Memory management I: address spaces, paging and segmentation

Every running program believes it owns a large, private, contiguous range of memory addresses. In reality, physical memory is shared by hundreds of processes and the kernel, and a program's data may be scattered in small pieces across physical memory, or not in memory at all. Creating this illusion efficiently and safely is one of an operating system's central jobs. This lesson covers the address space abstraction, the history from fixed partitions and segmentation to paging, and how modern processors and kernels translate addresses with multi-level page tables and the translation lookaside buffer (TLB). Lesson 9 builds on this to cover virtual memory: demand paging, page replacement and memory allocation.

CMPUT-229 explained the hardware side: the memory hierarchy, caches, page tables and the TLB from the processor's point of view. Here we take the operating system's view: how the kernel lays out address spaces, builds and maintains page tables, and uses them for protection and sharing.

Goals of memory management

A memory manager has four goals. Isolation: one process must not read or modify another's memory, or the kernel's. Relocation: a program should run correctly wherever in physical memory it is placed, and be movable. Efficiency: little memory should be wasted, and translation should add almost no time to each access. Sharing: processes should be able to share memory deliberately, for example the code of a shared library loaded by a hundred processes, without copying it a hundred times. All modern designs meet these goals with the same idea: programs use virtual addresses, and hardware translates each one to a physical address on every access, using tables the kernel controls.

The address space of a process

On Linux and other Unix-like systems, a process's virtual address space has a standard layout. Near the bottom are the program's text (machine code, read-only and executable), its initialized data and its uninitialized data, the bss, which the kernel fills with zeros. Above them the heap grows upward as malloc obtains memory with brk or mmap. Far above, memory-mapped regions hold shared libraries and mapped files. At the top of the user range the stack grows downward, and above that, out of reach of user code, is the kernel. On x86-64 with four-level paging, user space spans the lower 128 TiB of a 48-bit address space.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int global_init = 42;                  /* initialized data */
int global_zero;                       /* uninitialized data (bss) */

/* Find which mapping in /proc/self/maps contains address p */
static const char *region_of(const void *p) {
    static char name[300]; char line[512];
    FILE *f = fopen("/proc/self/maps", "r");
    strcpy(name, "?");
    while (fgets(line, sizeof line, f)) {
        unsigned long lo, hi; char perms[5], path[256] = "";
        sscanf(line, "%lx-%lx %4s %*s %*s %*s %255s", &lo, &hi, perms, path);
        if ((unsigned long)p >= lo && (unsigned long)p < hi) {
            const char *base = strrchr(path, '/');
            snprintf(name, sizeof name, "%s  %s", perms,
                     path[0] ? (base ? base + 1 : path) : "(anonymous)");
            break;
        }
    }
    fclose(f);
    return name;
}

int main(void) {
    int local = 7;
    int *heap = malloc(sizeof *heap);
    printf("page size: %ld bytes\n", sysconf(_SC_PAGESIZE));
    printf("main()      -> %s\n", region_of((void *)main));
    printf("global_init -> %s\n", region_of(&global_init));
    printf("global_zero -> %s\n", region_of(&global_zero));
    printf("heap block  -> %s\n", region_of(heap));
    printf("local var   -> %s\n", region_of(&local));
    printf("printf()    -> %s\n", region_of((void *)printf));
    free(heap);
    return 0;
}

$ gcc -O0 -Wall -g toy.c -o toy
$ ./toy
page size: 4096 bytes
main()      -> r-xp  toy
global_init -> rw-p  toy
global_zero -> rw-p  toy
heap block  -> rw-p  [heap]
local var   -> rw-p  [stack]
printf()    -> r-xp  libc.so.6

The permissions column shows protection at work. The code is readable and executable but not writable (r-xp), so a bug cannot overwrite instructions; data, heap and stack are readable and writable but not executable (rw-p), which blocks the classic attack of injecting code into a buffer and jumping to it. Linux also randomizes where each region starts, address space layout randomization (ASLR), so the exact addresses change from run to run; the region names stay the same. CMPUT-331 covers why these protections matter for security.

From contiguous allocation to segmentation

Early systems placed each program in one contiguous block of physical memory, using a base register (added to every address) and a limit register (checked against every address) to relocate and protect it. Simple, but as programs of different sizes start and finish, free memory breaks into scattered holes too small to use, external fragmentation. Compaction, moving programs together, fixes it at a high cost. Allocation policies such as first fit, best fit and worst fit change how quickly fragmentation develops but cannot prevent it.

Segmentation generalizes the idea: an address space consists of several segments (code, data, stack and so on), each with its own base, limit and permissions, and an address names a segment and an offset within it. Segments match the logical structure of a program and make sharing a whole segment easy. But segments are still variable-sized blocks of physical memory, so external fragmentation remains. The x86 architecture kept segment registers for decades; in 64-bit mode they are almost entirely vestigial, used only for thread-local storage pointers (the FS and GS registers).

# Segmentation: each segment has a base and a limit; offsets beyond the limit trap
segments = {"code": (0x4000, 0x1800), "data": (0x9000, 0x0800), "stack": (0xC000, 0x1000)}
def translate(seg, off):
    base, limit = segments[seg]
    if off >= limit:
        return f"{seg}+{off:#06x}: offset beyond limit {limit:#06x} -> segmentation fault"
    return f"{seg}+{off:#06x}: physical {base + off:#06x}"
for seg, off in [("code", 0x0123), ("data", 0x07FF), ("data", 0x0800), ("stack", 0x0FF0)]:
    print(translate(seg, off))
# external fragmentation: free holes after allocations and frees in a 64 KiB memory
holes = [6, 3, 9, 2, 4]                      # KiB
need = 12
print(f"free memory total {sum(holes)} KiB in {len(holes)} holes; largest {max(holes)} KiB")
print(f"a {need} KiB segment {'fits' if max(holes) >= need else 'does not fit'} despite enough total free space")

code+0x0123: physical 0x4123
data+0x07ff: physical 0x97ff
data+0x0800: offset beyond limit 0x0800 -> segmentation fault
stack+0x0ff0: physical 0xcff0
free memory total 24 KiB in 5 holes; largest 9 KiB
a 12 KiB segment does not fit despite enough total free space

Paging

Paging removes external fragmentation by cutting both virtual and physical memory into fixed-size pieces: pages in virtual memory and frames in physical memory, typically 4 KiB each. Any page can go in any frame, so there are no awkward holes; a free frame anywhere will do. A virtual address is split into a page number and an offset within the page. A page table, one per process, maps each virtual page number to a physical frame number plus permission bits. The hardware memory management unit (MMU) does the translation on every access: it looks up the page number, checks the permissions and combines the frame number with the unchanged offset.

Each page-table entry holds more than a frame number. A present (valid) bit says whether the page is in memory; access to a non-present page causes a page fault, which Lesson 9 uses for demand paging. Read, write and execute bits enforce protection; the no-execute (NX) bit stops code running from data pages. A user/supervisor bit keeps kernel pages out of reach of user mode. Accessed and dirty bits, set by hardware, tell the kernel which pages have been used and which have been modified since they were loaded, which page replacement depends on.

Paging trades external fragmentation for a little internal fragmentation: on average half a page is wasted at the end of each region. With 4 KiB pages that is negligible. Larger pages reduce the number of page-table entries and TLB misses but waste more memory and make each page fault move more data. Modern processors support huge pages, 2 MiB and 1 GiB on x86-64, which databases and virtual machine hosts use for large, long-lived memory, and Apple's processors use 16 KiB base pages.

Multi-level page tables

A single flat page table for a 48-bit address space with 4 KiB pages would need 2^36 entries, 512 GiB per process at 8 bytes each, most describing addresses the process never uses. Multi-level page tables solve this by making the page table itself a tree that is allocated only where needed. On x86-64 with four levels, the 48-bit virtual address is split into four 9-bit indexes and a 12-bit offset. The top-level table (PML4) has 512 entries, each pointing to a level-3 table, and so on down to level-1 tables whose entries hold frame numbers. Each table is exactly one 4 KiB page. A process that uses a few small regions needs only a handful of tables.

# x86-64 four-level paging: split a 48-bit virtual address into four 9-bit indexes and a 12-bit offset
va = 0x00007f3a_9c2d_1e48
offset = va & 0xFFF
idx = [(va >> shift) & 0x1FF for shift in (39, 30, 21, 12)]
names = ["PML4 (level 4)", "PDPT (level 3)", "page directory (level 2)", "page table (level 1)"]
print(f"virtual address  {va:#018x}")
for n, i in zip(names, idx):
    print(f"  {n:<25} index {i:>3}")
print(f"  page offset               {offset:#05x} ({offset})")
# a toy page-table walk: each level maps an index to the next table, the last to a physical frame
tables = {("root", idx[0]): "T3", ("T3", idx[1]): "T2", ("T2", idx[2]): "T1", ("T1", idx[3]): 0x1A2B3}
node = "root"
for level, i in enumerate(idx):
    node = tables[(node, i)]
frame = node
pa = (frame << 12) | offset
print(f"frame number {frame:#x} -> physical address {pa:#x}")
print("memory references for one translation without a TLB: 4 table reads + 1 data read = 5")

virtual address  0x00007f3a9c2d1e48
  PML4 (level 4)            index 254
  PDPT (level 3)            index 234
  page directory (level 2)  index 225
  page table (level 1)      index 209
  page offset               0xe48 (3656)
frame number 0x1a2b3 -> physical address 0x1a2b3e48
memory references for one translation without a TLB: 4 table reads + 1 data read = 5

# Why multi-level page tables: size of a flat page table vs what a small process actually needs
PAGE = 4096
PTE = 8                                   # bytes per page-table entry on x86-64
va_bits = 48
flat_entries = 2 ** va_bits // PAGE
print(f"flat table for a 48-bit address space: {flat_entries:,} entries = {flat_entries*PTE/2**30:.0f} GiB per process")
# a process using 3 regions: 8 MiB code+data near the bottom, 64 MiB heap, 8 MiB stack near the top
regions_mib = [8, 64, 8]
leaf_tables = sum(-(-mib * 2**20 // (512 * PAGE)) for mib in regions_mib)   # each leaf table maps 2 MiB
upper = 1 + 2 + 2                          # PML4 + a few level-3 and level-2 tables (regions far apart)
total_tables = leaf_tables + upper
print(f"4-level tables actually needed: {leaf_tables} leaf + {upper} upper = {total_tables} tables x 4 KiB = {total_tables*4} KiB")
# effective access time with a TLB
mem_ns, tlb_ns = 100, 1
for hit in (0.80, 0.98, 0.995):
    eat = hit * (tlb_ns + mem_ns) + (1 - hit) * (tlb_ns + 4 * mem_ns + mem_ns)
    print(f"TLB hit rate {hit:.1%}: effective access time {eat:.1f} ns")

flat table for a 48-bit address space: 68,719,476,736 entries = 512 GiB per process
4-level tables actually needed: 40 leaf + 5 upper = 45 tables x 4 KiB = 180 KiB
TLB hit rate 80.0%: effective access time 181.0 ns
TLB hit rate 98.0%: effective access time 109.0 ns
TLB hit rate 99.5%: effective access time 103.0 ns

Processors with large memories now support five-level paging (57-bit addresses, 128 PiB of virtual address space), which Linux enables on hardware that has it. Other designs exist too: inverted page tables keep one entry per physical frame and search it with a hash, saving memory on systems with huge address spaces; IBM POWER processors have used hashed page tables. RISC-V defines Sv39, Sv48 and Sv57 modes with three, four and five levels.

The translation lookaside buffer

Walking four levels of tables for every memory access would make each access five times slower. The TLB, a small, fast cache of recent translations inside the MMU, avoids this. With a hit rate of 99 per cent or more, typical for programs with good locality, most accesses pay only the TLB lookup. When the TLB misses, x86 and Arm processors walk the page tables in hardware; some RISC designs instead trap to the kernel, which walks them in software.

The TLB creates work for the kernel. When the kernel changes a page-table entry, for example to unmap a page or change its permissions, it must invalidate any cached copy of that translation, and on a multicore machine other cores may hold copies too, so the kernel sends inter-processor interrupts asking them to flush, a TLB shootdown. Context switches between processes change the page table, so their translations become invalid; processors tag TLB entries with an address-space identifier (ASID on Arm, PCID on x86) so that entries for several processes can coexist and the TLB need not be emptied on every switch.

Sharing and protection with page tables

Page tables make sharing natural. When a hundred processes load the C library, each process's page tables point to the same physical frames for the library's read-only code, so it exists once in memory. Processes can deliberately share memory with mmap or System V shared memory, mapping the same frames into both address spaces, which is the fastest form of communication between processes. Copy-on-write, introduced with fork in Lesson 2, is also implemented with page tables: shared pages are marked read-only, a write causes a protection fault, and the kernel copies the page and updates the writer's table.

Worked examples