Heap Layout

An allocator's raw material is one CONTIGUOUS region of memory. On Linux it arrives via sbrk(n) (grow the program break — the legacy path) or mmap with MAP_ANONYMOUS (map fresh zeroed pages — the modern path). Either way the allocator receives undifferentiated bytes and must impose its own structure, because of one hard constraint baked into the C API:

free(p) receives ONLY a pointer.

No size. No length argument. From p alone the allocator must recover how big the block is and whether it is legal to release. The universal answer is metadata at a fixed offset from p — a header immediately before every block's data:

byte:  0     4            104   108          158
       [hdr] [data 100 B] [hdr] [data 50 B]  ...unused tail...
              ^                  ^
              ALLOC 100 -> 4     ALLOC 50 -> 108

Given p, the header lives at p - HDR. free(p) steps back four bytes, reads {size, is_free}, and knows everything it needs. This lesson's model uses HDR = 4; real 64-bit allocators use one 8-byte word. Note "one word", not "a struct with a size and a bool" — that naive struct pads to 16 bytes on x86-64 and doubles the overhead. dlmalloc's trick: block sizes are always multiples of 16, so the low 4 bits of the size field are guaranteed zero, and the flags hide in them. One word carries both facts.

Alignment: the real-world rule our model skips

Production allocators on x86-64 return 16-byte-aligned pointers — the ABI requires it for long double and SSE vector types — so real malloc rounds every request up to keep addresses on 16-byte boundaries. Our simulator deliberately skips that: addresses here are exact byte arithmetic (4, 108, 158) so you can verify the header math without rounding noise. The arithmetic is identical in real allocators; they just round sizes first. The Fragmentation lesson prices what that rounding costs.

This lesson's allocation policy

• INIT <size> — one empty heap, no blocks yet. Print OK.
• ALLOC <size> — first scan for a FREE block of EXACTLY this size and reuse it (print its data address). Otherwise carve a fresh block off the tail: header at the current end of the last block's data, data HDR bytes later. It fits if data_addr + size <= heap_size — exactly-full succeeds, just like the bump allocator. Otherwise print OOM.
• FREE <addr> — mark the USED block whose data starts at addr free (OK). Anything else — an already-free block, a stale address like 999 — prints BAD.
• BLOCKS — every block in heap order as <addr>:<size>:<state>.

Note what exact-size reuse means: a freed 200-byte block satisfies a later ALLOC 200 but not an ALLOC 150 — there is no way to split a block yet. Splitting, and smarter reuse, are the next three lessons.

Your exercise

The first test allocates 100 then 50 on a 1024-byte heap and expects addresses 4 and 108, then BLOCKS must print exactly 4:100:used and 108:50:used. The classic mistake is computing the second address as 104 — the end of the first block's data — forgetting that the second block carries its OWN 4-byte header. Test 2 checks reuse: after FREE 108, an ALLOC 50 must print 108 again (the recycled block), not 162 (a fresh carve past it). And on a 60-byte heap, ALLOC 50 then ALLOC 50 must print 4 then OOM — the second block's data would start at 58 and run to 108, past the end of the heap.