Block Coalescing

Splitting creates many small blocks. Without merging them back, you get external fragmentation.

The Problem: External Fragmentation

Free list after many operations:
[100 free] [200 used] [100 free] [100 free] [200 used]

malloc(250) fails!
Total free: 300 bytes
But no single block is large enough.

The Solution: Coalesce on Free

When freeing a block, merge it with adjacent free blocks:

Before free(middle):
[100 free] [100 used] [100 free]

After free with coalescing:
[300 free]  (all three merged!)

Coalescing with Next Block

Finding the next block in memory is easy:

block_header_t *next = (block_header_t*)(
    (char*)block + sizeof(block_header_t) + block->size
);

Merging is just arithmetic:

int coalesce_next(block_header_t *block) {
    block_header_t *next = next_in_memory(block);

    // Check bounds
    if ((void*)next >= sbrk(0)) return 0;

    // Check if free
    if (!next->free) return 0;

    // Merge!
    block->size += sizeof(block_header_t) + next->size;
    block->next = next->next;  // Skip 'next' in list

    return 1;
}

Coalescing with Previous Block

This is harder. With a singly-linked list, you can't go backward.

Option 1: Scan from Head

block_header_t *coalesce_prev(block_header_t *block) {
    block_header_t *candidate = free_list_head;

    while (candidate) {
        block_header_t *candidate_next = next_in_memory(candidate);

        if (candidate_next == block && candidate->free) {
            // Merge: candidate absorbs block
            candidate->size += sizeof(block_header_t) + block->size;
            candidate->next = block->next;
            return candidate;  // Return merged block
        }
        candidate = candidate->next;
    }

    return block;  // No merge
}

Slow (O(n)) but works with existing structure.

Option 2: Boundary Tags

Store size at both ends of each block:

+--------+-----------------+--------+
| header | data            | footer |
+--------+-----------------+--------+
         ^                 ^
         Both store size and free flag

To find previous block:

1. Look at the word before your header
2. That's the previous block's footer (contains size)
3. Subtract size to find previous header

Fast (O(1)) but uses more memory.

Option 3: Doubly-Linked List

Add prev pointer to header. Direct access to previous block in list.

Full Coalescing

block_header_t *coalesce(block_header_t *block) {
    // First, coalesce forward (simpler)
    coalesce_next(block);

    // Then, coalesce backward (may change returned block)
    return coalesce_prev(block);
}

void my_free_coalesce(void *ptr) {
    if (!ptr) return;

    block_header_t *block = payload_to_block(ptr);
    block->free = 1;

    coalesce(block);
}

The Payoff

Before (fragmented):
[A:100 free] -> [B:50 free] -> [C:100 free]

malloc(200) would FAIL

After coalescing:
[ABC: 250 + 2*header free]

malloc(200) SUCCEEDS

Deferred Coalescing

Some allocators don't coalesce immediately. They batch it up:

• Coalesce only when malloc fails to find space
• Or coalesce periodically

Trade-off: faster free(), but fragmentation may grow temporarily.

Summary

Both are essential for a production allocator.