Heap Layout

An allocator hands out pieces of one contiguous region. After this lesson your program will keep a header in front of every block, find a block again from nothing but its data address, and reuse a freed block when a later request has exactly the same size.

Where the region comes from

On Linux a user-space allocator gets its raw material from the kernel by two routes: sbrk(n) grows the program break (the legacy path), and mmap with MAP_ANONYMOUS maps fresh zeroed pages (the modern path). Either way the allocator receives undifferentiated bytes and has to impose its own structure on them, because of one hard constraint in the C API:

free(p) receives ONLY a pointer.

No size, no length, no hint. 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 distance 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 the data address p, the header lives at p - HDR. free(p) steps back, reads {size, state}, 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 flag": a naive {size_t size; bool free;} pads to 16 bytes on x86-64 and doubles the overhead. Production allocators round every size to a multiple of 8 or 16, so the low bits of the size field are always zero and can carry the flags. glibc keeps three flags in those bits.

Addresses are data addresses

The second block in the diagram starts its header at byte 104, but the number the caller gets back is 108, the first byte it may write. Every address in this course is a DATA address, and the header sits HDR bytes below it. That is why the second ALLOC prints 108 and not 104.

Alignment: the real-world rule this model skips

x86-64 requires 16-byte-aligned pointers from malloc (the ABI promises it for long double and SSE types), so real allocators round each request up. This simulator deliberately skips that: addresses are exact byte arithmetic (4, 108, 158) so you can verify the header math without rounding noise. The Fragmentation lesson prices what rounding costs.

This lesson's policy

• INIT <size>: an empty heap of that many bytes, no blocks yet. Print OK.
• ALLOC <size>: first look for a FREE block of EXACTLY this size, scanning in address order, and reuse it (print its data address). Otherwise carve a fresh block at the end of the last block: header at that end, data HDR bytes later. It fits only if the data would end at or before the end of the heap; if not, print OOM and change nothing.
• FREE <addr>: mark the USED block whose data starts at addr as free and print OK. Anything else prints BAD: a block that is already free, an address that is not the start of any block, or an address in the middle of one.
• BLOCKS: one line per block in heap order, <addr>:<size>:<used|free>.

Exact-size reuse is deliberately crude. A freed 200-byte block satisfies a later request for 200 but not one for 150, because there is no way to cut a block in two yet. The next lessons fix that, one mechanism at a time.

Common mistakes

• Putting the second block's data at the end of the first block's data (104 instead of 108). Every block carries its own header.
• Checking capacity against the block's header position instead of its data end. A block fits if data address + size does not pass the end of the heap, so an exactly-full heap succeeds.
• Reusing a free block of a different size. ALLOC 150 must not take a free 200-byte block; it carves a new block and the 200 stays free.
• Letting FREE succeed twice on the same block. The second one is the double free that corrupts real heaps; here it prints BAD.

Your exercise

The starter parses the commands and prints the answers; you maintain the list of blocks. Watch two boundaries: a heap that the last block fills exactly, and the case where two free blocks have the same size and the lower address must win.