Heap Management and Dynamic Allocation

The heap is a contiguous (or logically contiguous) region of a process's address space, distinct from the stack and from static/global storage, that is managed at runtime rather than at compile time. Memory in the heap is obtained via an explicit allocation request (conceptually `alloc(size)`, realized as `malloc` in C or `new` in C++) and released via an explicit deallocation request (`free(ptr)`). Unlike a stack frame, whose lifetime is tied to a single function call and can therefore be managed with a simple pointer bump, a heap block's lifetime is arbitrary: it may be allocated in one function and freed in a completely different, much later, call — or never freed at all, in a leak. The central object an allocator manages is the block: a contiguous run of heap bytes, tagged as either allocated (in use by the program) or free (available for reuse). Because the allocator itself needs to know each block's size and status without the program telling it again, every block carries a small amount of metadata, typically a header word stored just before the pointer returned to the caller, encoding the block's size and a free/allocated bit. Some allocators also store a footer (a boundary tag) at the end of the block, duplicating the size, so that a neighboring block can be inspected in O(1) time from either side — this is what enables fast coalescing, discussed below. The free list is the data structure that ties all currently free blocks together, usually as a singly or doubly linked list threaded through the free blocks themselves (using the freed memory to store `next`/`prev` pointers, since a free block has no live data to protect). An allocation request scans this list for a block large enough to satisfy it — the scanning placement policy (first-fit, best-fit, worst-fit, next-fit) is one of the most consequential design decisions in an allocator, because it directly determines how quickly usable memory gets fragmented: split into a landscape of gaps too small to satisfy future requests, even though the total free memory would be sufficient if it were contiguous.

A heap allocator must implement two operations against a shared pool of memory: `alloc(size)` and `free(ptr)`. We build up the classic explicit free-list allocator design, which underlies the intuition (if not the exact code) of production allocators like `dlmalloc` and glibc's `ptmalloc`.

Block layout. Each block, whether free or allocated, is prefixed by a header encoding its size (including the header itself) and a status bit. A common convention packs the status bit into the low bit of the size field, since block sizes are word-aligned and their low bits are otherwise always zero: ``` [ header: size | alloc-bit ] [ payload ... ] [ optional footer: size | alloc-bit ] ```

Initialization. The allocator starts with one giant free block spanning the whole heap arena, linked into a free list of size one.

Allocation (`alloc`). Given a requested payload size, round it up to satisfy alignment (commonly 8 or 16 bytes) and add header/footer overhead, producing the true block size needed. Search the free list for a block big enough — this is the placement policy. If the chosen free block is significantly larger than needed, split it: carve off the front portion as the new allocated block, and shrink the remainder into a smaller free block that stays on the free list. If no block is found, the allocator requests more memory from the operating system (via `sbrk` or `mmap`) and retries.

Deallocation (`free`). Mark the block's header as free, and attempt to coalesce it with its immediate neighbors in memory (not in free-list order — physical order) if they are also free, merging two or three adjacent blocks into one larger free block. This is exactly what the footer/boundary-tag technique enables: to check whether the block immediately before this one (in memory) is free, the allocator reads that neighbor's footer, which sits directly before this block's header, in O(1) time — no free-list traversal required. ``` function ALLOC(requestedSize): size = ALIGN(requestedSize + HEADER_SIZE + FOOTER_SIZE) block = FIND_FIT(size) # first-fit / best-fit / etc. if block == NULL: block = REQUEST_MORE_MEMORY(size) # extend heap via sbrk/mmap if block == NULL: return NULL # out of memory REMOVE_FROM_FREE_LIST(block) if SIZE(block) - size >= MIN_BLOCK_SIZE: SPLIT(block, size) # carve block into [alloc part][remainder] INSERT_FREE_LIST(remainder) SET_HEADER(block, SIZE(block), ALLOCATED) return PAYLOAD_POINTER(block) function FREE(ptr): block = BLOCK_FROM_PAYLOAD(ptr) SET_HEADER(block, SIZE(block), FREE) prevBlock = PHYSICAL_PREV(block) # via footer of prevBlock nextBlock = PHYSICAL_NEXT(block) # via header, size lookup if prevBlock != NULL and IS_FREE(prevBlock): REMOVE_FROM_FREE_LIST(prevBlock) block = MERGE(prevBlock, block) if nextBlock != NULL and IS_FREE(nextBlock): REMOVE_FROM_FREE_LIST(nextBlock) block = MERGE(block, nextBlock) INSERT_FREE_LIST(block) function FIND_FIT(size): # FIRST-FIT variant for each block in freeList: if SIZE(block) >= size: return block return NULL ``` `FIND_FIT` is the pluggable heart of the allocator. First-fit returns the first block encountered large enough to satisfy the request; it is simple and fast on average but tends to fragment the low-address end of the heap over time. Best-fit scans the entire free list and returns the smallest block that still fits, minimizing wasted space per allocation but at the cost of a full scan, and — counterintuitively — it tends to produce many tiny, useless leftover slivers, a distinct kind of fragmentation. Worst-fit deliberately picks the largest available block, on the theory that the leftover remainder will be large enough to be useful later; in practice it usually performs worse than both. Next-fit is a variant of first-fit that resumes scanning from where the previous search left off rather than always restarting from the head of the list, spreading allocations more evenly across the heap.

Time complexity. With an explicit free list of length $k$ (the number of currently free blocks), `alloc` performs a linear scan in `FIND_FIT`, costing $O(k)$ time in the worst case for first-fit or next-fit, and $O(k)$ always for best-fit or worst-fit, since they must examine every block to find the true minimum/maximum. `free` is $O(1)$: updating the header, checking at most two neighbors via header/footer, splicing the free list, and merging blocks are all constant-time pointer operations, provided boundary tags are used so neighbor status is available without a search. Without footers, checking whether the physically-next block is free is still O(1) (walk forward by the current block's size), but checking the physically-previous block would require a linear scan backward or a separate index — this is precisely why the boundary-tag technique is standard: it makes coalescing genuinely constant-time in both directions. More sophisticated allocators improve the $O(k)$ search bound. Segregated free lists (also called size-class or "bucket" allocators) maintain a separate free list per size class (e.g., 16, 32, 48, ... bytes, or exponentially: 16, 32, 64, 128, ...), so `alloc` for a common size goes directly to the matching bucket in $O(1)$ expected time, only falling back to splitting a larger block when the exact bucket is empty. The buddy system organizes the heap as a binary hierarchy of power-of-two block sizes, giving $O(\log(\text{heap size}))$ allocation and coalescing, since merging a freed block only ever needs to check its unique "buddy" (computable by an address XOR trick) rather than an arbitrary neighbor.

Space complexity. The overhead is the header (and optional footer) per block: a constant $c$ bytes per allocation, independent of payload size, plus internal fragmentation from alignment rounding — an allocator with 16-byte alignment wastes on average up to 15 bytes per allocation to rounding. For $n$ live allocations this is $O(n)$ total metadata overhead, which is asymptotically negligible relative to payload size for reasonably large objects, but can dominate for workloads with many tiny objects (a classic reason custom small-object allocators exist).

Correctness argument. The key invariant an allocator must preserve is: at every point in time, the set of blocks with the "free" bit set is exactly linked into the free list, no two free blocks are ever adjacent in memory, and every allocated block's returned pointer lies inside a block correctly marked allocated with a correctly recorded size. The "no two free blocks adjacent" clause is maintained by immediate coalescing on every `free` call — if it were violated, external fragmentation would be strictly worse than necessary, because two adjacent free blocks that could serve one large request would incorrectly appear as two separate, smaller opportunities. Splitting preserves the invariant because it only ever converts one free block into one allocated block plus one (still correctly free, correctly sized) remainder. Coalescing preserves it because merging updates the header/footer sizes atomically with the free-list splice, so no window exists where the metadata is inconsistent with reality (assuming single-threaded execution; multi-threaded allocators need locks or lock-free structures to preserve this atomically, a significant added complexity real allocators handle with per-thread arenas). The honest tradeoff: no placement policy is fragmentation-free in general. It is a classical result that first-fit and best-fit can both be forced into $\Theta(\log n)$-factor memory waste relative to optimal offline packing on adversarial allocation/deallocation sequences (this is a heap-allocation instance of the online bin-packing problem, which has no constant-competitive online algorithm in the worst case). Practical allocators accept this and instead engineer for the common case — small, similarly-sized, short-lived objects — via size classes, rather than trying to solve the worst case optimally.

Consider a tiny 200-unit heap (units abstract away exact byte counts; header and footer cost 8 units each) and the request sequence: ``` alloc(40) -> P1 alloc(30) -> P2 alloc(50) -> P3 free(P2) alloc(20) -> P4 free(P1) free(P3) alloc(60) -> P5 ``` Assume first-fit placement and immediate coalescing on free.

The trace exposes two crucial phenomena that a single tidy example would hide: at step 5, splitting a marginally-too-big free block leaves a 10-unit sliver that is smaller than any realistic header-plus-payload, so it sits dead in the free list until a neighbor frees and coalescing rescues it — precisely what happens at step 7. This is why real allocators track a minimum block size and refuse to split when the remainder would fall below it, instead handing out the whole block with some internal fragmentation rather than manufacturing an unusable free sliver.

Dynamic memory allocation as a formal subject grew out of early Lisp and operating-systems work, where researchers needed principled ways to manage a shared, mutable pool of memory across unpredictable request patterns. The theory of fragmentation, free-list search strategies, and buddy systems was substantially developed and analyzed through the 1960s–70s, turning allocator design from folklore into an area with provable worst-case bounds.

Every C and C++ program, and the runtimes of most other languages (the JVM's native heap, Python's object allocator `pymalloc`, Go's allocator before its garbage collector reclaims), rests on some variant of the mechanisms described here. Operating system kernels manage their own internal heaps (the Linux kernel's `kmalloc`/slab allocator, a segregated size-class design) for kernel data structures, separate from user-space `malloc`. High-performance systems — game engines, databases, network servers — frequently replace the default general-purpose allocator with a specialized one (`jemalloc`, `tcmalloc`, custom slab or arena allocators) precisely because fragmentation and lock contention in general-purpose allocators become measurable bottlenecks under sustained load. Security research treats heap allocator internals as a primary attack surface, since corrupting free-list metadata is a classical technique for turning a memory bug into arbitrary code execution. And understanding manual heap management is the essential prerequisite for appreciating why languages adopted automatic memory management: garbage collectors must solve the same free-space bookkeeping problem, but without ever being told explicitly when an object's lifetime ends.

Ask the tutor: How would this allocator design need to change to safely support multiple threads calling `alloc`/`free` concurrently?