Splitting Free Blocks

Handing a 1000-byte block to a 100-byte request strands 900 bytes inside a live allocation. After this lesson your allocator will cut the block in two, give the caller exactly what it asked for, and put the remainder back to work as a new free block with its own header.

The heap starts as one free block

The unused end of the heap from the last lesson was really just a free block nobody had named yet. From here on, INIT creates exactly that: a single free block whose header sits at byte 0, so its data starts at 8 and its size is heap - 8. ALLOC never carves "from the end" any more; it only ever finds a free block and, if it is much too big, splits it.

The split, with every byte accounted for

A block is HDR bytes of header followed by its payload. Cutting a free block of payload S for a request m produces two blocks, and the second needs a header of its own, which comes out of the remainder:

before:   [hdr][ free  S = 414 ........................................ ]

ALLOC 70 with HDR = 8:

after:    [hdr][ used 70 ][hdr][ free 414 - 70 - 8 = 336 ............... ]
                          ^ remainder header sits right after the 70 bytes

In terms of this lesson's numbers: the used block keeps its address and shrinks to m; the remainder's data starts at addr + m + HDR and has S - m - HDR bytes. The bookkeeping invariant that catches almost every bug: add up HDR + size over all blocks and you must get the heap size back. An off-by-one in the remainder shows up as bytes appearing or vanishing.

m is max(n, MINP) as before, with HDR = 8 and MINP = 16.

MIN_SPLIT: do not manufacture dust

Splitting always looks like a win until you split a block for a request that leaves 3 spare payload bytes. That remainder can never satisfy any request, since even the smallest block needs MINP bytes to hold its free-list links, and every later scan must still step over it. So the rule is: split only if the remainder's payload S - m - HDR is at least MINP. Otherwise hand over the whole block and let the caller carry the few spare bytes.

The no-split case leaves the spare bytes inside the used block, so WASTE (the sum of size - n over used blocks, as in the last lesson) shows what the threshold costs. Real allocators make the same call: dlmalloc will not create a chunk smaller than its minimum size, because a free chunk must hold its header, footer and list pointers.

FREE still does not merge

FREE marks the block free and stops. Two neighbouring free blocks stay two blocks, each with its own header:

INIT 1024 ; ALLOC 100 ; FREE 8
BLOCKS ->  8:100:free
           116:908:free        two blocks, NOT one

Those adjacent free blocks are the seed of external fragmentation and the entire subject of the next lesson. If your BLOCKS prints one merged line here, you implemented the next lesson early.

Common mistakes

• Giving the remainder S - m bytes. The remainder has to pay for its own header: S - m - HDR.
• Using > instead of >= in the threshold, so a remainder of exactly MINP is refused.
• Splitting every time. A block whose remainder would be 15 bytes must be handed out whole.
• Inserting the remainder at the end of the block list instead of directly after the used block, which scrambles every later address.
• Splitting a freed block differently from a fresh one. A block returned by FREE and reused is cut by the same rule.

Your exercise

The starter parses commands and prints BLOCKS and WASTE; you write the allocation step that finds, splits and marks a block, and the free step. Check the two sides of the threshold, and a request that consumes the entire heap.