Address Translation

Efficient Translation

Goal: almost every virtual address translation should be able to proceed without kernel assistance.

Why?

Process: "Dear kernel, I’d like to use virtual address 0x10000. Please tell me what physical address this maps to. KTHXBAI!"

Does this work?

No! Unsafe! We can’t allow process to use physical addresses directly. All addresses must be translated.

Process: "Machine! Store to address 0x10000!"
MMU: "Where the heck is virtual address 0x10000 supposed to map to? Kernel…help!"
(Exception.)
Kernel: Machine, virtual address 0x10000 maps to physical address 0x567400.
MMU: Thanks! Process: store completed!
Process: KTHXBAI.

Simplest virtual address mapping approach.

Pro: simple! Hardware only needs to know base and bounds.
Pro: fast!
- Protection: one comparison.
- Translation: one addition.

Con: is this a good fit for our address space abstraction?
- No! Address spaces encourage discontiguous allocation. Base and bounds allocation must be mostly contiguous otherwise we will lose memory to internal fragmentation.
Con: also significant chance of external fragmentation due to large contiguous allocations.

One base and bounds isn’t a good fit for the address space abstraction.

But can we extend this idea?

We can assign each logical region of the address space—code, data, heap, stack—to its own segment.
- Each can be a separate size.
- Each can have separate permissions.

Segmentation works as follows:

Each segment has a start virtual address, base physical address, and bound.
Check: Virtual Address is OK if it inside some segment, or for some segment:
Segment Start < V.A. < Segment Start + Segment Bound.
Translate: For the segment that contains this virtual address:
Physical Address = (V.A. - Segment Start) + Segment Base

Have we found our ideal solution to the address translation challenge?

Pro: still fairly simple:
- Protection (Segment Exists): N comparisons for N segments.
- Translation: one addition. (Once segment located.)
Pro: can organize and protect regions of memory appropriately.
Pro: better fit for address spaces leading to less internal fragmentation.

Ideally, what would we like?

Common systems trick: when something is too slow, throw a cache at it.
Translation Lookaside Buffers—or TLBs—typically use content-addressable memory or CAMs to quickly search for a cached virtual-physical translation.

So at this point:

Segments are too large and lead to internal fragmentation.
Mapping individual bytes would mean that the TLB would not be able to cache many entries and performance would suffer.