writing a memory allocator in c: from sbrk to free lists

Apr 5, 2026•system

what malloc actually does

when you call malloc(n), the C library asks the OS for memory using sbrk() or mmap(), then manages that memory in user space. the OS only knows about large pages — malloc is the layer that gives you arbitrary-sized allocations.

writing your own allocator teaches you exactly how this works.

the heap and sbrk

sbrk(n) extends the heap by n bytes and returns a pointer to the start of the new region:

#include <unistd.h>

void *sbrk(intptr_t increment);

// request 4096 bytes from the OS
void *mem = sbrk(4096);
if (mem == (void *)-1) {
    // allocation failed
}

a simple free list allocator

the most common allocator design uses a free list — a linked list of free blocks:

#include <unistd.h>
#include <string.h>

typedef struct Block {
    size_t       size;
    int          free;
    struct Block *next;
} Block;

#define BLOCK_SIZE sizeof(Block)

Block *freeList = NULL;

Block *find_free_block(size_t size) {
    Block *curr = freeList;
    while (curr) {
        if (curr->free && curr->size >= size) return curr;
        curr = curr->next;
    }
    return NULL;
}

Block *request_space(size_t size) {
    Block *block = sbrk(0); // current heap end
    void  *req   = sbrk(BLOCK_SIZE + size);
    if (req == (void*)-1) return NULL;

    block->size = size;
    block->free = 0;
    block->next = NULL;
    return block;
}

void *my_malloc(size_t size) {
    if (size == 0) return NULL;

    Block *block = find_free_block(size);
    if (block) {
        block->free = 0;
        return (block + 1); // return pointer past the header
    }

    block = request_space(size);
    if (!block) return NULL;

    if (!freeList) freeList = block;
    return (block + 1);
}

void my_free(void *ptr) {
    if (!ptr) return;
    Block *block = (Block*)ptr - 1; // get the header
    block->free = 1;
    // TODO: coalesce adjacent free blocks
}

fragmentation and coalescing

after many malloc/free cycles, the heap becomes fragmented — lots of small free blocks that cannot satisfy a large request even though the total free space is sufficient.

the fix is coalescing: when freeing a block, merge it with adjacent free blocks:

void coalesce(Block *block) {
    // merge with next block if it is free
    if (block->next && block->next->free) {
        block->size += BLOCK_SIZE + block->next->size;
        block->next  = block->next->next;
    }
}

void my_free(void *ptr) {
    if (!ptr) return;
    Block *block = (Block*)ptr - 1;
    block->free  = 1;
    coalesce(block);
}

splitting large blocks

if a free block is much larger than needed, split it to avoid wasting space:

void split(Block *block, size_t size) {
    if (block->size >= size + BLOCK_SIZE + 1) {
        Block *newBlock = (Block*)((char*)(block + 1) + size);
        newBlock->size  = block->size - size - BLOCK_SIZE;
        newBlock->free  = 1;
        newBlock->next  = block->next;
        block->size     = size;
        block->next     = newBlock;
    }
}

what real allocators do

jemalloc and tcmalloc go much further:

size classes: separate free lists for each size class (8, 16, 32, 64... bytes), reducing fragmentation
thread caches: per-thread allocation pools to avoid lock contention
huge pages: using 2MB pages for large allocations to reduce TLB pressure