Dynamic Memory Allocator

Managing the heap

I wrote a memory allocator in C to understand how malloc and free manage the heap. It requests memory through sbrk() and mmap() and handles allocation without calling the standard library allocator.

The implementation is thread-safe and supports block splitting and coalescing. I wanted to keep fragmentation low without spending too much time searching for available memory.

Free lists

I track available blocks in a doubly linked free list. Each free block stores pointers to the next and previous free blocks, so an allocation search only visits unused memory. An implicit list would also have to visit allocated blocks.

When a free block is larger than the request, the allocator can split it and return the remainder to the free list. When memory is freed, it merges adjacent free blocks.

Block metadata

Headers and footers store each block’s size and allocation state. These boundary tags let the allocator find neighboring blocks during coalescing.

Block alignment leaves the lowest bit of the size field available. I use that bit to store the allocation flag. The free-list pointers are used only while the block is free.

/*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;