Constructing my own heap allocator that supports in-place reallocation and free block coalescing

As the capstone project in my CS 107 course, I was tasked with building two heap allocators that could support the following memory allocation function: malloc, realloc and free. Our key goal is correctness, to be able to serve 100% of well-formed requests. On top of that, we should try to optimize for both utilization and efficiency. For utilization, we should recycle free blocks when capable, compactly use memory, and have low overhead costs. For efficiency, the allocator should be fast in finding open spots and setting memory.

When designing the implicit list allocator, I implemented malloc by searching the heap block-by-block for a free spot. I was able to traverse to a free location by checking the headers, starting from the beginning of the heap, that store information on size of block and whether it is currently free or not. Although this is a good first take, there is room here to improve in both efficiency and utilization. With the explicit list allocator, each header is double in size and stores next/prev pointers of each free block. Malloc only searches free blocks, resulting in faster allocation. On top of that, utilization is improved because for each free call, I check to see if there are neighboring free blocks to coalesce into one larger block. This both increases usable memory and gets rid of old headers. Finally, there is also in-place reallocation, where if client reallocates to a smaller size, or neighboring free blocks can absorb the size growth, these operations are done first before moving memory to a new location. Overall this leads to large gains in utilization and help with efficiency.

There are many skills I mastered during the course of this project, most notably becoming far more comfortable with C and the variety of data structures needed to build my own heap allocator. This includes experience with pointers, void pointer referencing, pointer arithmetic, doubly linked lists, memory management, and bit operations.