Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 17, Arpaci-Dusseau & Arpaci-Dusseau

Free-Space Management

A short detour from virtualization: how any memory manager tracks free space — a user-level malloc/free library or the OS placing variable-sized segments.

Fixed-size units (paging) make this easy: keep a list of free slots, hand out the first. Variable-sized units are harder — and interesting.

The problem: external fragmentation

[ free 10 ] [ used 10 ] [ free 10 ]     total free = 20 bytes

A request for 15 bytes fails — no single contiguous chunk is large enough, even though 20 bytes are free. That is external fragmentation.

Crux: how manage free space for variable-sized requests? Which strategies limit fragmentation? What are the time and space costs?

Assumptions

Most of this chapter follows user-level allocators (Wilson’s survey [W+95]).

Assumption	Meaning
`malloc(size)` / `free(ptr)`	Classic C heap API
`free` has no size	Library recovers size from a header before `ptr`
Heap + free list	Track free chunks in the managed region
Focus on external fragmentation	Internal waste (padding) exists but we de-emphasize it
No compaction	Once handed out, C pointers pin the block — cannot move it
Fixed-size heap region	Real libraries may grow via `sbrk`; we keep life simple

Compaction is possible in the OS for segmentation (previous chapter) or in GC languages that can rewrite all references.

Low-level mechanisms

Splitting and coalescing

30-byte heap with free list (addr:0,len:10) and (addr:20,len:10):

Request > 10 → fail (NULL)
Request 10 → either free chunk works
Request 1 → split: return address 20; free list becomes (0,10) and (21,9)

Coalescing: when free(10) returns the middle used block, do not leave three separate 10-byte free nodes. Merge neighbors → one (0,30) entry so a later malloc(20) can succeed.

Tracking size: headers

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

User gets ptr after the header. On free:

void free(void *ptr) {
    header_t *hptr = (void *)ptr - sizeof(header_t);
    // assert(hptr->magic == 1234567);
    // free region size = header + hptr->size
}

Critical detail: a request for N bytes needs a free chunk of size N + header (e.g. 100 + 8 = 108).

Embedding a free list

You cannot call malloc inside the allocator to build list nodes. Store { size, next } inside the free memory itself:

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

node_t *head = mmap(...);           // e.g. 4096-byte heap
head->size = 4096 - sizeof(node_t); // 4088
head->next = NULL;

After malloc(100) with an 8-byte header: allocate 108 bytes, shrink free node to 3980. Three such allocs leave free size 3764. Freeing the middle chunk without coalescing fragments the list; free everything without coalescing → Figure 17.7 mess; merge neighbors to restore one contiguous free region.

Growing the heap

Out of space? Fail with NULL, or ask the OS (sbrk / mmap) for more pages, then continue allocating.

Basic strategies

Ideal: fast and low fragmentation. Arbitrary request streams mean no policy always wins.

Policy	Rule	Pros / cons
Best fit	Smallest free chunk that still fits	Less leftover waste; full list scan
Worst fit	Largest chunk; leave big remainder	Tries to avoid tiny splinters; often worse + still expensive
First fit	First chunk that fits	Fast; can pollute the head of the list with small leftovers
Next fit	Like first fit, resume from last search point	Spreads searches; similar to first fit

Example free list: sizes 10, 30, 20. Request 15:

Policy	Picks	Leftover list idea
Best	20	10, 30, 5
Worst	30	10, 15, 20
First	30 (first big enough)	same leftover shape as worst, cheaper search

Address-ordered free lists make coalescing easier and can reduce fragmentation.

Quiz

Rank the sequence

1 / 1

Order the steps of allocating and later freeing memory with a free-list allocator (top = first).

OrderDrag the handle to rearrange — top should be first.

1Later, free(ptr) locates the block via its header
2Coalesce the freed block with adjacent free neighbors
3Return the pointer to the user, just past the header
4Split the chosen chunk if it is larger than needed
5Search the free list using a placement policy (e.g. best fit)

Drag items into the correct order (or use ↑↓), then check.

Other approaches

Segregated lists

Keep a separate free list for popular object sizes; everything else goes to a general allocator. Fast path, less fragmentation for those sizes.

Slab allocator (Bonwick, Solaris kernel) [B94]: caches for locks, inodes, …; when low, pull slabs (multiples of a page) from a general allocator; reclaim empty slabs when VM needs memory. Free objects often kept pre-initialized to skip costly init/destroy.

Buddy allocation

Binary buddy [K65]: free space starts as size (2^N). Split by two until a block fits (further split would be too small). Only power-of-two sizes → internal fragmentation possible.

Beauty: on free, check the buddy (address differs by one bit at that level); if free, coalesce up the tree. Coalescing is simple by design.

Scaling & multiprocessors

List searches do not scale. Real allocators use trees, or designs like Hoard [B+00] and jemalloc [E06] for multithreaded heaps. See also glibc malloc deep-dives [S15].

No best allocator

If a thousand policies exist, none is universally great. Know the workload — or avoid variable-sized allocation entirely (paging, next).

Interactive

Try: external fragmentation · split · coalesce · best/worst/first · buddy splits.

Check your understanding

Quiz