[6] Understanding Segmentation in Computer Systems

As you can see, even though the space between the stack and heap isn't used by the process, it still takes up physical memory when we move the whole address space to physical memory. This makes using a base and bounds register pair to virtualize memory pretty wasteful. It also makes it tough to run a program when the whole address space doesn’t fit into memory, so base and bounds isn't very flexible.

To solve this problem, the concept of segmentation was introduced in the early 1960s. Instead of managing the entire virtual address space with a single base and bounds pair, segmentation allows the operating system to divide the address space into logically distinct segments, such as code, heap, and stack. Each of these segments is then assigned its own base and bounds pair, allowing for independent placement in physical memory.

Segmentation is especially useful for handling sparse address spaces—those with large areas of unused memory—by only allocating physical memory to the segments that are actively used. This ensures that physical memory is not wasted on unallocated virtual address space.

How Segmentation Works

In this model, the hardware includes base and bounds registers for each segment. For example, consider a system where physical memory is divided into 64KB blocks, with the following segment allocation:

• Code segment: Base = 32KB, Size = 2KB

• Heap segment: Base = 34KB, Size = 2KB

• Stack segment: Base = 28KB, Size = 2KB

To translate a virtual address, the hardware adds the offset (the virtual address within a segment) to the base of that segment. It then checks if the result is within the segment’s bounds.

For example, if we have a virtual address of 100 in the code segment, the hardware adds this offset to the code segment’s base (32KB), giving a physical address of 32,868. The hardware then checks if the offset 100 is within the code segment’s bounds of 2KB, and if it is, the memory access is allowed.

Address Translation in the Heap

Let’s say a process accesses virtual address 4200, which is in the heap segment. The heap starts at virtual address 4KB, so the offset is 4200 - 4096 = 104. This offset is added to the heap segment’s base (34KB), giving the physical address 104 + 34KB or 34,920.

Handling Illegal Memory Accesses

When an address goes beyond a segment’s limits, the hardware creates an exception, causing a segmentation fault. This happens, for example, when a process tries to access an address outside the allocated heap space. The hardware notices the violation and raises an exception, usually stopping the offending process.

Which Segment Are We Referring To?

To know which segment a virtual address refers to, hardware can use the top bits of the address. For instance, in a 14-bit virtual address space with three segments (code, heap, stack), the top two bits indicate the segment, and the remaining bits represent the offset within that segment. This method, used in systems like VAX/VMS, simplifies the translation process by allowing the hardware to directly select the appropriate base and bounds register for the segment.

In our example, If the top two bits are 00, the hardware knows the address is in the code segment and uses the code base and bounds. If the top two bits are 01, the hardware knows the address is in the heap and uses the heap base and bounds. For example, the virtual address 4200 in binary is:

The top two bits (01) tell the hardware which segment we're referring to. The bottom 12 bits are the offset: 0000 0110 1000, or hex 0x068, or 104 in decimal. By adding the base register to the offset, the hardware gets the final physical address. The offset also makes bounds checking easy: if the offset is less than the bounds, the address is legal; otherwise, it's illegal. So, the hardware would do something like this to get the physical address:

// get top 2 bits of 14-bit VA
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
// now get offset
Offset = VirtualAddress & OFFSET_MASK
if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT)
else
    PhysAddr = Base[Segment] + Offset
    Register = AccessMemory(PhysAddr)

In our running example, we can fill in values for the constants above.

SEG_MASK would be set to 0x3000, SEG_SHIFT to 12, and OFFSET_MASK to 0xFFF.

What About The Stack?

So far, we haven't talked about an important part of the address space: the stack. In the diagram above, the stack starts at physical address 28KB but grows backwards. This means it starts at 28KB and goes back to 26KB in physical memory, which matches virtual addresses 16KB to 14KB. The hardware needs to handle this differently. It needs to know which way the segment grows. Instead of just base and bounds values, we need a bit that is set to 1 if the segment grows in the positive direction, and 0 if it grows in the negative direction.

With the hardware knowing segments can grow negatively, it translates such virtual addresses differently. For example, to access virtual address 15KB, which maps to physical address 27KB, the virtual address in binary is 11 1100 0000 0000 (hex 0x3C00). The top two bits (11) identify the segment, leaving an offset of 3KB. To get the correct negative offset, subtract the segment size (4KB) (in this example) from 3KB, resulting in -1KB. Adding -1KB to the base (28KB) gives the physical address: 27KB. The bounds check ensures the absolute value of the negative offset is within the segment’s size.

what should the OS do on a context switch?

You can probably guess: the segment registers must be saved and restored. Each process has its own virtual address space, so the OS must set up these registers correctly before the process runs again.

Another important issue is managing free space in physical memory. When a new address space is created, the OS needs to find space in physical memory for its segments.

External Fragmentation

The main problem is that physical memory quickly fills with small gaps of free space, making it hard to allocate new segments or expand existing ones. This issue is called external fragmentation. For example, if a process wants to allocate a 20KB segment, there might be 24KB free, but not in one continuous block (instead, in three separate chunks). So, the OS can't fulfill the 20KB request.

One solution to this problem is to compact physical memory by rearranging the existing segments. For example, the OS could pause the running processes, move their data to one continuous region of memory, update their segment register values to point to the new physical locations, and create a large free block of memory. This way, the OS can fulfill the new allocation request.

A simpler approach is to use a free-list management algorithm that tries to keep large blocks of memory available for allocation. Algorithms like best-fit, worst-fit, first-fit, and others can help with this.

Managing Free Space

Our problem is called external fragmentation: free space gets broken into small pieces of different sizes, making it fragmented. Future requests might fail because there isn't one large enough continuous space to meet the request, even if the total free space is enough.

The figure shows an example of this problem. There are 20 bytes of free space, split into two chunks of 10 bytes each. A request for 15 bytes will fail, even though there are 20 bytes available. This is the issue being discussed, so keep reading.

There is another type of fragmentation called internal fragmentation. This happens when memory is given out in fixed-size blocks, and a process doesn't use the whole block. The unused space within the block is wasted because other processes can't use it (Allocated but not used). Our focus here will be on external fragmentation only.

To manage free space in the heap efficiently, memory allocators use a free list. This is a data structure that keeps track of all the available (free) chunks of memory in the heap. It helps in efficiently allocating and deallocating memory blocks. The free list keeps references to memory blocks that are not in use and can be allocated for new requests.

Free List Management (Splitting and Coalescing)

The free list for the figure above contains two entries. One entry describes the first 10-byte free segment (bytes 0-9), and the other entry describes the second 10-byte free segment (bytes 20-29):

As mentioned above, a request for more than 10 bytes will fail (returning NULL) because there isn't a single continuous chunk of memory that size available.

A request for exactly 10 bytes can be easily fulfilled by either of the free chunks.

what happens if the request is for something smaller than 10 bytes?

Let's say we need just one byte of memory. The allocator will do something called splitting: it'll find a free chunk that fits the request and split it into two.

The first chunk goes to the caller, and the second chunk stays on the list. So, in our example, if we ask for 1 byte and the allocator uses the second free chunk, the call to malloc() would return 20 (the address of the 1-byte allocated region) and the list would look like this:

In the picture, the list mostly stays the same; the free region now starts at 21 instead of 20, and its length is now 9. Splitting is a common trick used by allocators for smaller requests.

what happens when an application calls free(10)?

Let's take a look at the free list we have again. If we just add this free space back into our list without overthinking it, we might end up with a list that looks like this:

Now, here's the problem: if a user asks for 20 bytes, a simple list traversal won't find a free chunk that big, and it'll fail.

Allocators solve this problem by doing Coalescing which is merging free space when a chunk of memory is freed. The idea is simple: when you return a free chunk, check its address and the addresses of nearby free chunks. If the new free space is next to one or two existing free chunks, combine them into a single larger free chunk. So, after merging, our final list should look like this:

With coalescing, an allocator can better ensure that large free spaces are available for the application.

How do allocators know the size of the space to be freed when calling free()?!!!

You might have noticed that the function free(void *ptr) does not take a size parameter. This means the malloc library must quickly figure out the size of the memory being freed and add it back to the free list. So, how does it do that?

To do this, most allocators store some extra information in a header block in memory, usually right before the allocated chunk.

In this example, we have an allocated block of 20 bytes, pointed to by ptr. Imagine the user called malloc() and stored the result in ptr like this: ptr = malloc(20);.

The header at least contains the size of the allocated region (in this case, 20 bytes). It might also have extra pointers to make deallocation faster, a magic number for integrity checks, and other details. Let's assume a simple header that includes the size of the region and a magic number, like this:

typedef struct __header_t {
    int size;
    int magic;
} header_t;

This example above would look like this:

When the user calls free(ptr), the library uses simple pointer arithmetic to find where the header starts:

void free(void *ptr) {
    header_t *hptr = (void *)ptr - sizeof(header_t);
    ...
}

After obtaining such a pointer to the header, the library can easily calculate the total size of the newly-freed region by adding the size of the header to size of the region).

The free region is the size of the header plus the size of the space allocated to the user. Thus, when a user requests bytes of memory, the library does not search for a free chunk of size ; rather, it searches for a free chunk of size plus the size of the header.

how do we build the free list inside the free space itself?

So far, we have introduced the free list as a list that describes the free chunks of memory in the heap.

But how do we build such a list inside the free space itself?

In a typical list, you would call malloc() for a new node. But within the memory-allocation library, you can't do this. Instead, you need to build the list inside the free space itself. It may sound strange, but it's not too hard to do!

Assume we have a 4096-byte chunk of memory to manage (i.e., the heap is 4KB). To manage this as a free list, we first need to set up the list. Initially, the list should have one entry, with a size of 4096 bytes (minus the header size). Here is what a node of the list looks like:

typedef struct __node_t {
    int size;
    struct __node_t *next;
} node_t;

Now let’s check out some code that sets up the heap and adds the first element to the free list.

// mmap() returns a pointer to a chunk of free space os size 4096
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

After running this code, the free list has a single entry, of size 4088.

The head pointer holds the starting address of this range. Visually, the heap looks like this:

Now, let’s imagine that a chunk of memory is requested, say of size 100 bytes. The space in the heap will look like this:

Assuming an 8-byte header, the library finds a chunk big enough for the request. Upon the request for 100 bytes, the library allocates 108 bytes out of the existing one free chunk and returns a pointer ptr to it. Since there is only one free chunk (size: 4088), it will be chosen and split into two: one chunk for the request (plus the header) and the remaining free chunk.

Now let’s look at the heap when there are three allocated regions, each of 100 bytes (or 108 bytes including the header).

As observed, the first 324 bytes of the heap are now allocated, which includes three headers and three 100-byte regions used by the calling program. The free list still contains a single node (pointed to by head), but its size is now reduced to 3764 bytes after the three splits. The next question to consider is what occurs when the calling program returns some memory using free().

Imagine we want to free the second 100-byte region where sptr is shown. We just call free(16500) how??!. This is the virtual address plus the first 100-byte region and its header, plus the header of the second 100-byte region (16*1024+108+8).

The library immediately figures out the size of the free region, and then adds the free chunk back onto the free list. Assuming we insert at the head of the free list, the space now looks like this:

And now we have a list that starts with a small free chunk (100 bytes, pointed to by the head of the list) and a large free chunk (3764 bytes).

As you can see, the free space is now fragmented. But imagine that the last two 100-byte regions are freed. Our free list will look something like this:

As you can see from the figure, we now have a big mess! Why is that? Simple, we forgot to coalesce the list. simply go through the list and merge neighboring chunks; when finished, the heap will be whole again.

what should you do if the heap runs out of space?

Most traditional allocators start with a small heap and request more memory from the OS when needed. They usually make a system call (like sbrk in most UNIX systems) to expand the heap and then allocate the new memory from there.

Basic strategies for managing free space

Our target is to make allocators both fast and minimizes fragmentation. Unfortunately, because the stream of allocation and free requests can be random (since they are determined by the programmer), any specific strategy can perform poorly with the wrong set of inputs. Therefore, we will not describe a "best" approach but will instead talk about some basic strategies and discuss their pros and cons.

Best Fit

The best fit strategy searches the free list for chunks of memory that are as big or bigger than the requested size, then returns the smallest chunk in that group. This aims to reduce wasted space. However, it can be slow because it requires a thorough search for the right block.

Worst Fit

The worst fit approach finds the largest chunk and returns the requested amount, keeping the remaining large chunk on the free list. It aims to keep big chunks free instead of creating many small chunks like best fit. However, it requires a full search of free space, making it costly. Studies show it performs poorly, causing excess fragmentation and high overheads.

First Fit

The first fit method finds the first block that is big enough and gives the user the requested amount. The leftover free space is kept for future requests.

First fit is fast because it doesn't search all free spaces. However, it can clutter the start of the free list with small objects. Managing the order of the free list is important. Ordering the list by the address of the free space makes merging easier and reduces fragmentation.

Next Fit

Instead of starting the search at the beginning of the list, the next fit algorithm keeps a pointer to where the last search ended. This spreads out the searches, preventing the start from getting cluttered. Its performance is similar to first fit as it avoids a full search.

---

Here are a few examples of these strategies. Imagine a free list with three elements sized 10, 30, and 20 (we'll skip headers and other details, focusing on how the strategies work):

Assume an allocation request of size 15.

A best-fit approach would search the entire list and find that 20 is the best fit, as it is the smallest free space that can handle the request. The resulting free list:

What happens is a small free chunk is now left over.

A worst-fit approach works similarly but finds the largest chunk. In this example, it would choose the 30-sized chunk. The resulting list:

The first-fit strategy in this example works like worst-fit, finding the first free block that can handle the request. The difference is in the search cost; both best-fit and worst-fit search the whole list, while first-fit only looks at free chunks until it finds one that fits, reducing the search cost.