Coalescing free blocks: memory neighbours, not free-list neighbours

Concept illustration: four 64-byte blocks in a 256-byte arena. Free C and D touch and can merge; live B separates free A from C. Free-list order D to A to C differs from physical order.

Coalescing free blocks in a C memory allocator means merging blocks that are both free and physically adjacent within the same arena. A free-list link does not prove that two blocks touch: list order can reflect when blocks were freed rather than where they live. Merge only after checking the physical boundary, then update the free list so it contains the merged block exactly once.

Why coalescing free blocks depends on physical adjacency

Keep two relationships separate:

  • Physical successor: the block immediately after this block in the arena. With total-span metadata, its offset is the current block’s start plus its span.
  • Free-list successor: the next entry in an index of reusable blocks. It can be anywhere in that arena.

A span includes the header footprint, payload space and padding. Using only the requested payload size to find the next block lands inside the layout, not at its boundary.

For two blocks ordered by arena offset, the adjacency test is:

left + left_span == right

Both blocks must also be free. Validate offsets and spans before doing the addition: each start must be inside the arena, and each span must fit in the remaining bytes. Use offsets relative to one arena; do not try to establish adjacency by subtracting or ordering pointers into unrelated allocations.

The CS 208 notes on explicit free lists make this distinction directly: list entries may be in any order, but coalescing still follows neighbours in memory.

A 256-byte example: three free blocks, only two can merge

Consider a snapshot before a coalescing pass. One arena contains four blocks, each with a total span of 64 bytes:

  • A is free at [0, 64).
  • B is allocated at [64, 128).
  • C is free at [128, 192).
  • D is free at [192, 256).

Suppose the explicit free list is D → A → C. D and A are consecutive list entries, but they do not touch. C and D do touch, even though they are not consecutive entries in that list.

Merge C and D into one free block at offset 128 with span 128. A stays separate because B is live. The result has 192 free bytes in total, but its largest free span is only 128 bytes. A request needing a 160-byte total block cannot fit. Adding all free spans together does not produce a usable contiguous allocation.

If B is then freed, A, B and the merged C–D block form one continuous free range. They can become a single 256-byte block. This does not move any live payload: coalescing changes the partition and metadata of free space, not the location of allocated objects.

For the block format and alignment rules behind those spans, start with the small C allocator model.

Handle all four neighbour states when a block is freed

Let X be the block just freed. Treat an arena boundary as having no mergeable neighbour. The physical predecessor and successor determine the result:

  1. Neither neighbour is free: X remains a standalone free block.
  2. Only the predecessor is free: the predecessor survives, with its span increased by X’s span.
  3. Only the successor is free: X survives, with its span increased by the successor’s span.
  4. Both neighbours are free: the predecessor survives and covers all three spans.

The surviving header is at the lowest offset in the merged range. Interior headers cease to be block boundaries; an implicit physical walk skips them using the new total span. You need not erase their old bytes for traversal correctness.

These four cases assume the heap was already fully coalesced before X was freed. If you allow deferred coalescing, a neighbour may itself belong to a longer run of free blocks. Continue until the entire run is merged; stopping after one pair can leave adjacent free blocks behind.

Find the predecessor from layout metadata, not a list backlink

A header containing the total span can identify the physical successor. It cannot, by itself, identify the physical predecessor.

For a first teaching allocator, scan from the arena start and remember the previous block. That costs linear time in the number of physical blocks, but needs no footer.

Boundary tags are another design: a size field at a block’s end lets the allocator recover the preceding block’s extent. A common optimization keeps footers only in free blocks and records whether the predecessor is allocated in the current header. That changes the metadata contract; account for it in minimum block sizes and every split or merge.

An address-ordered free list can help find candidate neighbours, but you must still check that their spans touch. A doubly linked free list in arbitrary order does not solve predecessor discovery: its prev link is another index link, not a physical boundary.

Unlink neighbours before overwriting their metadata

For a single-threaded explicit-list allocator, a straightforward update sequence is:

  1. Validate X and discover its physical neighbours. Reject an invalid or already-free allocation according to your allocator’s contract.
  2. Remove every existing free-list entry participating in the merge, including a free predecessor even when its header will survive. Preserve whatever links are needed to unlink each entry.
  3. Write the merged block’s span and free state at the surviving start. Update any footer and neighbour-state flags required by your format.
  4. Insert the merged block into the free list exactly once.

This sequence assumes X has not yet been inserted. If your free operation inserts X first, remove its entry too before inserting the merged result. For a deferred pass over already-listed free blocks, remove all participating entries before reinsertion.

Unlinking first matters when list pointers occupy free payload space. Writing the merged metadata or links before reading the old links can destroy the information needed to remove an entry. Leaving an absorbed node in the list creates a second route into the middle of the merged block; a later allocation may hand out overlapping space. Leaving the surviving predecessor listed and inserting it again can instead create a duplicate entry or a cycle.

Test the partition and the index separately

Exercise the four neighbour states with three 64-byte blocks, freeing the middle one. Expected physical block counts are three, two, two and one respectively. Also test the four-block example above: merge C–D without crossing B, then free B and recover the whole 256-byte arena.

After every operation, check:

  • Physical blocks cover the arena exactly, with no gaps or overlaps and valid aligned spans.
  • Every physical free block appears in the explicit free list exactly once, and the list has no cycle.
  • Every list entry starts at a real free block boundary, never at an absorbed header.
  • With immediate coalescing, no physical neighbours are both free. With deferred coalescing, enforce that after a full coalescing pass instead.
  • Byte patterns in still-live payloads are unchanged.

Repeat tests with different free-list orders and frees at the first and last block. These expose accidental reliance on index order and attempts to read a nonexistent neighbour.

Coalescing makes larger free ranges available; allocation may later split them again. See when a remainder is large enough to split for the other half of that transition.

Work through the allocator mechanism

Heapcraft’s free first-lesson preview offers a smaller related exercise: implement align_offset and arena_take to reserve aligned slices in a 64-byte arena, then run seven C tests without registering. Try the free lesson; guest code and completion are unsaved, and registration is needed only to save work and continue. The lesson teaches alignment and bounds checks, not free-list operations or coalescing. The full guided allocator course is separate and unavailable, with no launch date; join its waitlist for updates.

Coalescing free blocks: memory neighbours, not free-list neighbours · Heapcraft