Block Coalescing

1 / 6

The Problem

[100 free][200 used][100 free][100 free]

malloc(250) fails!
Total free: 300, but fragmented.

External fragmentation = gaps between blocks.

2 / 6

Solution: Merge Adjacent Free Blocks

Before: [A free][B free][C free]
After:  [ABC free - one big block]
3 / 6

Coalesce Next (Easy)

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

if (next->free) {
    block->size += sizeof(hdr) + next->size;
    block->next = next->next;
}
4 / 6

Coalesce Prev (Hard)

Options:

  1. Scan from list head (slow)
  2. Boundary tags (extra memory)
  3. Doubly-linked list
5 / 6

Full Coalesce

void free_coalesce(void *ptr) {
    block->free = 1;
    coalesce_next(block);
    coalesce_prev(block);
}

Now malloc(250) succeeds!

6 / 6
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.