The Free List

A bump allocator forgets a block the moment it creates it. To support free, an allocator must REMEMBER free memory — and the classic structure for that is the free list: on free, record the block; on malloc, search the records for a block big enough.

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 by definition unused, so the allocator writes the list links straight into those bytes. The bookkeeping costs zero extra memory:

struct free_block {
    size_t size;
    int    is_free;
    struct free_block* next;   // stored IN the free payload
    struct free_block* prev;
};

This is why allocators enforce a minimum block size: a free block must be able to hold its own links.

First-fit

When several free blocks could satisfy a request, this lesson uses first-fit: walk the blocks in address order and take the FIRST free one whose size is sufficient. It is the fastest policy — early exit, no full scan. Whether it beats best-fit (scan everything, take the tightest match) is a fifty-year-old argument that measurement settled: on real workloads they roughly tie. The Fit Strategies lesson has you implement three policies and watch them diverge on the same input; here we stay with first-fit.

This lesson's model — deliberately no splitting

• INIT <size> creates ONE free block spanning the heap: header at 0 (HDR = 8), data address 8, size size - 8.
• ALLOC <size> takes the first free block with size >= request and marks the WHOLE block used. No trimming.
• FREE <addr> marks a used block free again — it reappears on FREELIST at full size. Unknown addresses print BAD.
• FREELIST prints <addr>:<size> for FREE blocks only.

Watch what whole-block allocation costs:

INIT 1024        [free 8:1016]
ALLOC 100 -> 8   [used 8:1016]    the ENTIRE 1016 bytes are consumed
FREELIST         (prints nothing — the list is empty)

A 100-byte request burned 1016 bytes; the 916 spare bytes are trapped inside a used block until it is freed. That is internal fragmentation at its most extreme, and it is exactly why the next lesson adds splitting. But the core free-list loop is already real: FREE 8 returns the block, and the next ALLOC reuses it. Test 7 runs that cycle twice with 500-byte requests and expects address 8 both times — recycling in action.

Your exercise

Test 2 is the whole-block rule in miniature: INIT 200 makes one free block 8:192. ALLOC 50 consumes it ENTIRELY and prints 8; the second ALLOC 50 finds no free block and must print OOM. Expected output, exactly: OK, 8, OOM. If you split off a remainder (next lesson's behavior), your second ALLOC prints an address and fails — and test 0 catches the same bug earlier: after INIT 1024 and ALLOC 100, FREELIST must print NOTHING, so a learner who splits sees a spurious 108:916 line rejected by the grader. Also keep FREE honest: FREE 999 on test 6 must print BAD, not crash or print OK.