Why this matters: allocator code is pointer arithmetic wearing a thin disguise, and the difference between a passing and a strong implementation act is whether the arithmetic is walked — real addresses, real sizes, invariants checked at each step. This lesson builds the core in the order you'd write it live, with the numbers alongside.
The header, packed
#define HEADER_SIZE 8
#define MIN_BLOCK 32 // header + smallest payload we'll split off
#define ALIGN8(x) (((x) + 7) & ~(size_t)7)
typedef struct Header {
size_t size_and_flags; // size (multiple of 8) | flags in low bits
} Header;
size_t blk_size(Header* h) { return h->size_and_flags & ~(size_t)7; }
bool blk_free(Header* h) { return (h->size_and_flags & 1) == 0; }
Header* next_blk(Header* h) { return (Header*)((char*)h + blk_size(h)); }Narrate the packing: sizes are multiples of 8, so bit 0 is spare — it becomes the allocated flag. next_blk is the walkability claim from lesson 02 as one line of arithmetic.
Free blocks additionally store list links in their payload:
typedef struct FreeNode { // overlaid on a free block's payload
struct FreeNode* next;
struct FreeNode* prev;
} FreeNode;That overlay is why MIN_BLOCK is 32: a free block must hold a header (8) plus two pointers (16), rounded to alignment — a block smaller than that can't even be tracked.
The layout, on real numbers
Initialization makes the whole buffer one free block. Say the buffer starts at 0x100000:
init: [ hdr @0x100000 size=0x100000 (1 MiB), free ]
free list: the single block
alloc(24): need = ALIGN8(24) + HEADER = 24 + 8 = 32 bytes
first-fit finds the big block; split it:
[ hdr @0x100000 size=32, ALLOCATED | payload @0x100008 ]
[ hdr @0x100020 size=0xFFFE0, free ... ]
return 0x100008
Check the invariants on the digits: 0x100000 + 32 = 0x100020 — the remainder's header lands exactly where arithmetic says; the returned payload 0x100008 is 8-aligned; both sizes are multiples of 8; every byte is in exactly one block. That verification, spoken while writing, is the act's real content.
alloc: first-fit, then split
void* alloc(size_t size) {
if (size == 0) return NULL;
size_t need = ALIGN8(size) + HEADER_SIZE;
for (FreeNode* n = free_list; n != NULL; n = n->next) { // first-fit
Header* h = header_of(n);
if (blk_size(h) < need) continue;
list_remove(n); // claimed
if (blk_size(h) - need >= MIN_BLOCK) { // split?
Header* rest = (Header*)((char*)h + need);
set_size_free(rest, blk_size(h) - need);
list_push(rest); // remainder rejoins
set_size_alloc(h, need);
} else {
set_alloc(h); // over-grant; true size stays
}
return payload_of(h);
}
return NULL; // the refusal path
}Two narration beats. The claim happens before the split — the block leaves the free list, then gets carved — so the list never contains a block that's mid-surgery (the flag/list invariant from lesson 02, enforced by ordering). And the else-branch is the minimum-split rule made visible: below MIN_BLOCK of remainder, the caller silently receives the extra bytes and the header records the truth.
free: flag, coalesce forward, relist
void free_(void* p) {
if (p == NULL) return;
Header* h = (Header*)((char*)p - HEADER_SIZE); // the forced lookup
Header* n = next_blk(h);
if (in_buffer(n) && blk_free(n)) { // one-sided coalesce
list_remove(node_of(n));
set_size(h, blk_size(h) + blk_size(n)); // absorb next
}
set_free(h);
list_push(node_of(h));
}Walk it on the earlier layout. Suppose a second alloc(24) took 0x100020..0x10003F, and now both blocks are freed, second first:
free(0x100028): h = 0x100020; next @0x100040 is the big free block
-> absorb: size becomes 0xFFFE0 + 32 = 0x100000 - 32
-> block @0x100020 free, back on list
free(0x100008): h = 0x100000; next @0x100020 is now free
-> absorb: size becomes 32 + (0x100000-32) = 0x100000
-> ONE free block again; buffer fully recovered
The favorable order healed everything. Freed in the other order, the first free's next-neighbor is still allocated, so no merge happens until the second free absorbs forward — one-sided coalescing's limitation, visible in the walk rather than hidden behind a claim.
What you'd say about complexity
alloc: O(F) in free blocks — first-fit scans until a fit; that's the price of the policy, said plainly. free: O(1) — header lookup, one neighbor check, list operations. Space: 8 bytes of header per block plus internal fragmentation from alignment and the minimum-split rule. The honest summary sentence: this allocator buys O(1) frees and simple invariants, and pays with a linear allocation scan and imperfect packing — consistent with the latency-over-utilization objective it was built against.
Key takeaway
The implementation is the walkable layout made executable: one packed header word, free-list nodes overlaid on free payloads, first-fit that claims before it splits, a minimum below which over-granting is recorded truthfully, and a free that absorbs its computed next neighbor. Walk the addresses — 0x100000, 0x100020, the re-merged 1 MiB — and every invariant becomes a checkable fact instead of a claim.