The Free List

The allocator from the last lesson could only reuse a freed block when a later request matched its size exactly. Real allocators remember ALL freed memory and search it. After this lesson your program will keep an address-ordered list of free blocks, hand out the first one that is big enough, and measure what that costs.

Remembering free memory

A bump allocator forgets a block the moment it creates it. To support free, an allocator must record the block, and to support malloc it must search those records for something big enough. The classic structure is the free list.

Where does the list itself live? In one of the oldest tricks in systems programming: inside the free blocks. A free block's payload is unused by definition, so the allocator writes the list links straight into those bytes and the bookkeeping costs no extra memory:

used block:  [ header: size, USED ][ payload: the caller's bytes ............ ]
free block:  [ header: size, FREE ][ next ptr ][ prev ptr ][ unused ......... ]

That has a consequence you will model in this lesson: a free block must be large enough to hold its own two links, 16 bytes on a 64-bit machine. So the smallest payload any block may have is MINP = 16, even if the caller asked for 5 bytes. The header also grows to one real 64-bit word, HDR = 8.

First-fit

When several free blocks could satisfy a request, the allocator needs a rule for choosing. First-fit walks the blocks in address order and takes the FIRST free one whose size is at least what was asked. It stops early, so it is cheap. Best-fit (scan everything, take the tightest) and worst-fit are compared in the Fit Strategies lesson; here the rule is first-fit and nothing else.

This lesson's model: whole blocks

• The heap starts empty. Blocks are placed one after another: a block's header sits where the previous block's data ended, and its data starts HDR bytes later.
• ALLOC n needs a payload of m = max(n, MINP). If a free block with size at least m exists, the first one in address order is handed out WHOLE: it keeps its full size even if that is much more than m. Otherwise a new block of exactly m bytes is carved after the last block, and the request fails with OOM if its data would run past the end of the heap.
• FREE addr marks a used block free. It reappears on the list at its full size. An address that is not the start of a used block prints BAD.
• FREELIST prints <addr>:<size> for every free block, in address order.
• WASTE prints the total of size - n over all used blocks, where n is what the caller asked for. That slack is trapped inside live blocks; it is internal fragmentation.

A worked trace on a different heap, so you can see the shape:

INIT 500
ALLOC 60      -> 8     block 8:60      (header at 0, ends at 68)
ALLOC 40      -> 76    block 76:40     (header at 68, ends at 116)
FREE 8        -> OK
ALLOC 10      -> 8     the freed 60-byte block fits; handed out whole
WASTE         -> 50    (60 - 10) for block 8, plus (40 - 40) for block 76

Read that last line carefully: the waste is the SUM over used blocks of what each holds beyond its request, and a 10-byte request sitting in a 60-byte block strands 50 bytes until it is freed. Whole-block hand-out is simple and it is also expensive; the next lesson cuts the oversized block in two.

Common mistakes

• Taking a free block that is too small. size >= m is the test, and a 100-byte block does not satisfy a 200-byte request even though it is the first free one.
• Forgetting MINP. ALLOC 5 creates a block of 16, so after FREE the list shows <addr>:16, not <addr>:5.
• Shrinking a reused block. A 500-byte block handed to an ALLOC 20 stays 500; freeing it lists 500 again.
• Choosing by free order instead of address order. If block B was freed before block A, a request that both could satisfy still gets the one at the lower address.

Your exercise

The starter reads commands and prints; you write the search, the carve-from-the-end step, and the two accounting commands. Test inputs free blocks in an order that differs from address order, and ask for sizes that skip over a too-small free block.