Why this matters: every decision in this problem is a trade with named costs, and interviewers grade whether you make the trades on purpose. This lesson builds the model the way you'd narrate it live: each structure introduced by the requirement that forces it, each policy chosen against the stated objective, and the invariants said out loud at the end.

The block format: what free-takes-no-size forces

Since free(ptr) must learn the block's size from the pointer alone, the allocator writes a header immediately before every payload it hands out:

[ header | payload ........ ][ header | payload .. ] ...
  8 bytes  caller's bytes

header = block size (including header) + an allocated? flag

free(ptr) finds its header at a fixed negative offset — the same intrusive-metadata move as aligned_malloc's stash, scaled up. And the alignment requirement pays for itself here: all sizes are multiples of 8, so a size's low three bits are always zero, and the allocated flag packs into one of them. One 8-byte word carries everything.

A second consequence deserves narration: because each header stores its block's full size, the next block's header sits at a computable address — header address plus size. The buffer becomes a chain you can walk by arithmetic alone. That walkability is what makes the rest of the design possible.

Tracking free blocks: the storage is already there

The allocator must find free blocks quickly. Walking the entire buffer and checking each header's flag works — it's the implicit list — but an allocation then costs a walk over every block, allocated or not. The better structure notices something elegant: a free block's payload is unused by definition, so the allocator can store its own bookkeeping there. Thread next and prev pointers through the payloads of free blocks, and you have an explicit free list — a doubly-linked list whose nodes cost zero extra memory, connecting exactly the blocks worth visiting.

This is the decision to name a principle at: the free list is intrusive by necessity — an allocator cannot ask anyone else for memory to track its memory, so its data structures must live inside the very bytes it manages. Interviewers listen for whether that constraint was noticed or lucked into.

Splitting: don't hand out more than was asked

First-fit search will often find a free block far larger than the request. Handing the whole thing over wastes the remainder, so the allocator splits: carve the requested size (plus header) off, and the remainder becomes a new, smaller free block with its own header, back on the free list.

The subtlety worth stating is the minimum split size: a remainder must be big enough to hold a header plus the smallest useful payload — otherwise splitting manufactures fragments too small to ever satisfy anything, pure bookkeeping debris. Below the minimum, don't split; give the caller slightly more than they asked for and record the true size in the header. That over-grant is internal fragmentation, and naming it as the deliberate cost of the minimum-split rule is exactly the kind of honesty this round rewards.

Coalescing: undoing the splits

Splitting cuts the buffer into ever-smaller blocks; without a reverse process the allocator grinds toward a state where free memory is plentiful but every piece is small — external fragmentation. The reverse is coalescing: when a block is freed, merge it with an adjacent free neighbor into one larger block.

The next neighbor is cheap: its header is at a computed address, one flag check away. The previous neighbor is the asymmetry every candidate must confront: headers let you walk forward, not backward, so finding the previous block's header means either walking from the start of the buffer — O(blocks) — or paying extra metadata (a topic lesson 04 develops properly). Our core design chooses immediate one-sided coalescing — merge with the next block on every free — and states the cost honestly: some adjacent-free pairs will sit unmerged until the pattern of frees happens to present them in the favorable order. That's a real limitation, chosen consciously against the latency objective, and saying it plainly beats pretending it away.

Placement policy: chosen by the objective, not by taste

Where multiple free blocks could satisfy a request, which one wins?

• First-fit — take the first block big enough. Cheap scans, but small leftover fragments accumulate near the front of the list.
• Best-fit — scan everything, take the tightest fit. Better packing on average, but every allocation pays a full scan, and the leftovers it creates are the tiniest, least useful slivers.

Our requirements said latency over utilization — so first-fit, and the justification writes itself. This is the parking-lot lesson in systems clothing: policies are preferences serving objectives, and a policy chosen because of the stated objective is defensible in a way "I always use first-fit" never is.

The invariants

- every byte of the buffer belongs to exactly one block
- blocks are contiguous: header + size lands on the next header;
  walking by arithmetic visits every block exactly once
- every header's size includes the header itself and is a multiple of 8
- the free list contains exactly the blocks whose flag says free
- no two adjacent blocks are both free after the free path runs
  (up to the one-sided limitation, stated above)
- returned pointers are 8-byte aligned

The fourth line is the one bugs love: the flag and the list membership are two records of one fact, and every path that changes one must change the other. Flagging that fragility yourself, before any probe, is a senior move.