Memory Allocator.

Context

malloc and free, written from scratch against a raw heap: the allocator hands out blocks, reclaims them, and fights fragmentation, judged on two axes that pull against each other: memory utilization and throughput. A design that chases one usually pays for it in the other.

As UT coursework, the source stays private; this is the design and what it taught me.

Approach

Explicit free lists. The naive approach scans every block in the heap looking for a free one. Instead, free blocks form a doubly-linked list threaded through the free blocks' own payload space. A freed block is unused memory, so it can store the pointers. Allocation walks only free blocks, which is the difference between O(all blocks) and O(free blocks) per request.

Boundary tags and coalescing. Every block carries its size in a header, and free blocks mirror it in a footer. When a block is freed, the footer of its left neighbor and the header of its right neighbor are one pointer-step away, so the allocator can tell in constant time whether either neighbor is free and merge them into one block on the spot. Without this, the heap decays into confetti: plenty of free bytes, none of them contiguous enough to use.

Alignment and splitting. Everything is 16-byte aligned. When a free block is larger than a request, it splits, and the remainder goes back on the free list, but only above a minimum split size, because a 16-byte splinter is fragmentation wearing a free-list costume.

The hard part: debugging a liar

An allocator bug rarely crashes the allocator. It corrupts a block header, and the crash arrives thousands of requests later, in unrelated code, with a stack trace that points nowhere. The single highest-leverage thing I built was a heap consistency checker: a function that walks the entire heap and validates every invariant: headers match footers, no two free blocks sit adjacent (coalescing worked), every free-list pointer targets a valid free block, everything is aligned. Run after every operation in debug mode, it converts "mystery crash in three thousand requests" into "invariant violated by the operation that just ran."

Results

• 85% average memory utilization across the benchmark trace suite
• 1,750 requests per second throughput
• The consistency checker catches corruption, misalignment, and invalid frees at the operation that causes them

Takeaways

The checker was the lesson: in any system where cause and symptom are separated by time, the tool that collapses that distance is worth more than any clever data structure. I now reach for invariant-checking machinery first, not after the third mystery crash.