Archive Notes

2. Segmentation

4 min read

Some simple solutions to the address-binding problem are:

  • load-time relocation
  • base and limit registers
  • segmentation

Load-time relocation

We already have to load (“copy”) programs into memory. So we can rewrite the program’s references to memory during the write.

Let’s say we have the given text segment:

We rewrite the text segment as such

Using this method, we can share the physical address space between processes:

Problems with load-time relocation

This creates several problems:

  • Memory can be fragmented in two ways: internally to a process and externally all over memory.
  • There is no fault isolation: one incompetent process could trash another’s memory or the operating system’s.
  • There is no security preventing a malicious process from reading / writing to another’s memory; it may be even worse as physical address space often includes devices.
  • It might be slow to do rewriting
  • It might stop us sharing memory

However, this is possible without any hardware support.

Base and limit registers

We can extend the hardware with base and limit registers, creating a simple memory management unit (MMU). In modern CPUs, this is integrated but we look at this conceptually.

Each memory access is checked against the base and limit by the hardware.

  • If the check fails, a hardware interrupt is raised and the OS kills the process.
  • We set the base and limit using privileged instructions in kernel mode.
  • We save and reset (restore on return) when a system call is called.
  • When the context is switched, we save to be restored later.

Compared to load-time relocation:

  • The fault isolation and security is pretty good.
  • We can avoid paying the “rewriting cost” now.
  • Fragmentation is still a problem:
    • Internal: if the base and limit must stay fixed
    • External: if the OS does not support growing processes

Segmentation

We can improve this design by defining a (base, limit) pair as a segment of memory, and if the MMU can work with many such pairs, then it supports segmentation.

Some hardware may also enforce permissions on segments:

  • can’t write to a text segment
  • can’t execute a stack segment
  • permission bits can be stored alongside base and length

Implicit selection of segments

Instructions that refer to memory are usually written to work with only one kind of memory, such as the stack, code or other data.

On a segmented machine we can say each instruction has a default segment, e.g. a jump would jump within the text segment. This allows us to easily extend the address space of small-word-size machines.

cmp $0x2,%di
push %bx        ; access stack segment via %sp
je 139d         ; jump within text segment
xor %di,%di
call 1330       ; call within text segment
mov (%si),%di   ; %si holds an address within data segment
mov %si,%bx
call 18f0       ; another call
mov $0x3f0d,%si

A complete address is a pair of segment and offset. A lot of the time, a program only needs to specify the offset but some instruction sets have more complex overrides.

Different processes have different segments which is fine. Segmented address spaces can have a weird shape:

  • Segments may be different sizes: in a small segment, offset does not exist.
  • Segments may overlap: they are still defined by just base and limit in physical memory; aliasing can complicate both hardware and software

Older instruction set design

Some older instruction sets such as the Intel 80286 (1982) was designed around segmentation to extend the user address space.

Segmentation compared to simple MMU

  • The fault isolation is much better as protection is much more fine-grained and can have specified permissions. Can protect a process from itself to an extent.
  • Security is still good as processes cannot refer to private memory of another process.
  • Rewriting is no longer an issue are instructions are all implicitly or explicitly segment-relative; address-binding is a matter of creating segments.
  • Fragmentation is still a problem:
    • Internally: no problem; can have many segments; any size
    • External: need contiguous physical memory

Graph View