Segmentation
we would like to not waste the large space between the heap and stack
Generalized Base/Bounds
Break the address space into segments
- Program Code (
.text) - Heap
- Stack
and maintain base/bounds per segment
Segmentation Fault
occurs from illegal memory access on segmented machines
Which Segment are we referring to?
in the assembly plenty of different addresses are present. How does the hardware know which address to use?
The explicit approach
Create segments based on the top two bits of the virtual address. e.g.
0x10xxxxx is the stack segment, 0x00xxxxx is the .text segment etc.
Notice this creates an extra unused segment. To avoid wasting this space, some systems put code in the same segment as the heap and thus use only one bit to select which segment to use.
This also has the added detriment of limiting your address space to a maximum size.
The implicit approach
Similar to interposition ig. The hardware determines how the address was formed. If if formed by pc register then you know it is in .text. If it is based off of the stack or base pointer, then it must be in the heap. I don’t understand how that works though.
What about the stack?
The stack grows downwards, in the physical memory, thus when calculating the offset for the bounds check the hardware will have to take care of that too. For that we add another bit that tracks the direction in which a segment grows.
Support for Sharing
Share certain memory segments between address spaces. For this we need to protect this shared memory segments, thus we add protection bits. This is the idea behind dynamic libraries ig.
Fine-grained vs Coarse-grained Segmentation
We have been only considering three segments. We can call that coarse-grained segmentation. However if there were a number of small segments, that would be fine-grained segmentation.
Supporting fine-grained segmentation would require further hardware support. Introduce the segment table.
OS Support
- What does the OS do in a context switch? → store all the newly introduced registers and restore them
- What if the segment needs to grow beyond the
bounds? → extend the segment withmalloc(), i.esbrksyscall - How does the OS manage free memory? (avoid fragmentation) → one option is to compact memory by rearranging segments (os can move segments when they are interrupted) → a better option is to use a free-list management algorithm that tries to keep large extents of memory available.
[1] https://www.cs.hmc.edu/~oneill/gc-library/Wilson-Alloc-Survey-1995.pdf → a review of some of these algorithms
Summary
all the hardware registers we have introduced so far by example
| Segment | Base | Size (Bound) | Grows Positive? | Protection |
|---|---|---|---|---|
| Code(00) | 32K | 2K | 1 | r-x |
| Heap(01) | 34K | 3K | 1 | rw- |
| Stack(00) | 28K | 2K | 0 | rw- |