Custom Dynamic Memory Allocator

Project Overview #

When you are writing C, it is easy to take standard library functions like malloc and free for granted. To really understand what happens under the hood, I decided to build my own custom dynamic memory allocator from scratch to serve as a replacement for the libc defaults.

My main goal was to balance two competing forces: squeezing the most out of available memory (keeping fragmentation low) and maintaining high speed (minimizing the CPU cycles needed to service memory requests). To pull this off, the allocator bypasses the standard library entirely and manages the heap directly using the operating system’s sbrk() and mmap() system calls.

Architecture & Free List Management #

To keep track of which memory blocks are in use and which are available, I built an Explicit Free List architecture.

A simple approach (an implicit list) forces the system to scan every single block in the heap just to find a free spot. Instead, my implementation embeds pointers directly inside the unused memory blocks themselves, wiring them together into a doubly linked list. This optimization slashes the time complexity for allocations from O(N) down to O(F), where F is just the number of currently free blocks.

Block Header & Footer Design #

Every block of memory needs metadata to track its size and whether it is currently allocated. To ensure the allocator can instantly merge adjacent free blocks (achieving O(1) coalescing), I used a boundary tag system with headers and footers.

Because memory alignment guarantees that block sizes are always even numbers, the lowest bit is essentially unused. I was able to hijack that lowest bit of the size variable to act as the allocation flag, a bitwise trick that saves memory overhead.

/*Std struct for the allocator*/
typedef struct block_node {
    size_t size_and_allocated; //Size of the block + allocated flag in LSB
    struct block_node *next;   //Pointer to next free block (only valid if free)
    struct block_node *prev;   //Pointer to prev free block (only valid if free)
} block_node_t;