Free-Space Management

Fragmentation Problems from Variable-Sized Allocations

Once free memory is cut into many pieces of differing sizes, a new larger request can fail even when the total remaining amount is enough, because no single contiguous region matches the need. This external fragmentation wastes usable space.

How Splitting and Coalescing Preserve Large Free Chunks

When a request is smaller than an existing free chunk, the allocator cuts that chunk, hands the needed part to the caller and leaves the leftover on the free structure. On free it inspects neighboring regions and, if they are also free, joins them into one larger contiguous area so space is not permanently shattered.

Using Headers to Quickly Learn Allocated Block Lengths

The free interface receives only a pointer, never a length, so the allocator must store a small header immediately before the user data that records the true size of the block. That lets the library instantly know how many bytes to reclaim and correctly update its free structure.

Pitfalls

• Forgetting to merge adjacent free blocks quickly produces unusable fragments
• The extra bytes occupied by headers reduce effective utilization for small objects

Minimum C11 · complete program · Download .c

#include <stdio.h>
int main(void) {
    printf("Initial heap: free[0-9] used[10-19] free[20-29]\n");
    printf("Free list: addr=0 len=10 -> addr=20 len=10\n");
    printf("Allocate 1 byte from second free chunk:\n");
    printf("Returned pointer: 20\n");
    printf("Updated free list: addr=0 len=10 -> addr=21 len=9\n");
    printf("Free the middle used block (addr=10):\n");
    printf("Without coalescing: addr=10 len=10 -> addr=0 len=10 -> addr=21 len=9\n");
    printf("With coalescing: addr=0 len=30\n");
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-17-free-space.c -o example && ./example

Expected result

Initial heap: free[0-9] used[10-19] free[20-29]
Free list: addr=0 len=10 -> addr=20 len=10
Allocate 1 byte from second free chunk:
Returned pointer: 20
Updated free list: addr=0 len=10 -> addr=21 len=9
Free the middle used block (addr=10):
Without coalescing: addr=10 len=10 -> addr=0 len=10 -> addr=21 len=9
With coalescing: addr=0 len=30

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A 30-byte heap currently has the first 10 bytes free, the middle 10 used and the last 10 free. If the middle block is freed without coalescing, will a later 15-byte request succeed? Explain why.

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.