Splitting Free Blocks

First-fit without splitting hands 1016 bytes to a 100-byte request. Splitting fixes the waste: carve the chosen free block into [used: exactly what was asked][free: the remainder], and put the remainder back to work for future allocations.

The model's arithmetic — read this carefully

In this simulator a split is pure bookkeeping on the block records:

before:   [free  addr=8    size=1016]
ALLOC 100:
after:    [used  addr=8    size=100]  [free  addr=108   size=916]
           remainder addr = 8 + 100    remainder size = 1016 - 100

The remainder starts at addr + request and keeps size - request bytes — the two sizes add back up exactly. A REAL allocator would also charge the remainder a fresh header (dlmalloc loses a word or two of metadata on every split); our simulator stores block metadata in records outside the byte counts, so no header is deducted after INIT. Keep the distinction in mind when you read production allocator code — but implement THIS model here, or every BLOCKS dump will be off by a header and the grader will reject it.

MIN_SPLIT: don't manufacture dust

Splitting always looks like a win until you split a 22-byte block for a 20-byte request and create a 2-byte free block. That fragment can never satisfy any request; it is pure list-walking overhead, forever. So allocators refuse to split when the remainder would be too small — here MIN_SPLIT = 16:

The no-split case leaves the spare bytes INSIDE the used block — it simply stays bigger than asked. That is internal fragmentation, capped at 15 bytes here, which is cheap compared to a permanent useless fragment. Real allocators make the same call: dlmalloc will not create a chunk smaller than 32 bytes, because a free chunk must at least hold its own header, footer, and two list pointers.

FREE still does not merge

FREE in this lesson marks a block free — full stop. Free neighbors stay separate:

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

Those two adjacent free blocks are the seed of external fragmentation and the entire subject of the next lesson. If your BLOCKS prints one merged 8:1016:free line here, you have implemented coalescing a lesson early and test 4 fails.

Your exercise

Tests 2 and 3 attack the threshold from both sides. INIT 30 creates free block 8:22; ALLOC 20 leaves remainder 2 — below 16 — so the whole block is used and BLOCKS must print exactly 8:22:used. INIT 40 creates 8:32; ALLOC 20 leaves remainder 12 — still below 16 — expected output 8:32:used. Split unconditionally and you print 8:20:used plus a 28:2:free dust block instead, failing both. When you DO split (test 0: 8:100:used then 108:916:free), insert the remainder immediately after the used block in address order — the most common free-list bug in real allocators is forgetting to relink the new remainder, and in this model the symptom is every later allocation landing at the wrong address.