Details about the Post

Introduction

Before diving into this article, I recommend reviewing the relevant chapters from Computer Systems: A Programmer’s Perspective (CSAPP), Chris Kanich’s lectures, and Operating Systems: Three Easy Pieces. These resources cover how memory allocation works and what happens under the hood when malloc is called. You’ll also want to understand the brk and sbrk system calls. Use any LLM if you’d like help parsing this material. this post is not a substitute for those references.

Goals of This Series

  • Implement a simple memory allocator using only brk/sbrk
  • Add a free list with a first-fit strategy using a linked list
  • Improve allocation efficiency and reduce fragmentation
    • Support block splitting and reuse
  • Implement a slab allocator
    • Use mmap for large allocations
  • Add concurrency support with locks
  • (Maybe) Explore atomic operations

Subscribe for free to receive updates when I add new article .

Implementing simple allocator using brk/sbrk. Whole code can be found at the end of the post.

Malloc and brk/sbrk

At a high level, malloc is a function that takes a size in bytes and returns a void* pointing to the beginning of a block of memory. When it comes time to release that memory using free, you only need to pass the starting address of the block—the same pointer returned by malloc. This simplicity on the surface hides a key detail: your custom memory allocator must internally track each allocation to properly handle free operations.

Without this internal bookkeeping, there’s no way to verify whether the pointer being freed is valid, has already been freed, or was never allocated in the first place. As part of a robust implementation, your free function should detect such issues and raise appropriate errors to prevent undefined behavior or memory corruption.

It’s also important to understand that malloc and free are not system calls—they’re part of the C standard library. On most systems, they’re implemented in the GNU C Library (glibc). However, alternative memory allocators exist that offer improved performance or memory usage for specific workloads. Two well-known examples are jemalloc and tcmalloc, which are used in high-performance applications like databases and web servers.

Allocator Structure

Below is defined a Block struct to track each allocated or free memory chunk:

typedef struct block {
    size_t size;            // how much memory the user asked for
    struct block* next;     // pointer to the next block
    int free;               // flag indicating if the block is free or used
} Block;

#define BLOCK_SIZE sizeof(Block);

Block * free_list = NULL;

malloc & free

free is straight forward. It retrives the block metadata by subtracting the metadata size from the ptr. Why subtracting?

We are assuming block will be like as below, hence to get the actual block we need to subtract the metadata from given ptr.

+------------------------+-------------------+
|       Metadata         |   User Memory     |
| (struct Block)         |   (return ptr)    |
|                        |                   |
| size | next | free bit | <--- malloc ptr   |
+------------------------+-------------------+


# void *ptr = malloc(100);

+-------------+---------------------+
|  Metadata   |    100 bytes        |
+-------------+---------------------+
              ↑
             ptr

void free(void *ptr)
{
    if (!ptr) 
        return;     // Should ideally raise an error but we are writing error-free code so...

    Block *block = (Block *)ptr - 1;
    block->free = 1;
}

Now malloc, Below are responsibilities it should do,

  • For best memory alignment, asked memory size should be converted to multiple of 8.
  • Go through the available block for first fit. Whatever size of the block is found we’ll occupy.
  • If not found, ask OS for more heap allocation using sbrk and get the new block and return the address after metadata is assgined.

Before going into malloc, there is a concern, Malloc will be slow. It searches through the whole list, It should only check the blocks which are free. avoiding checking all the blocks linearly. for this to accomodate we need to do some change to the block and do some small bookkeeping in free. We’ll just remove free flag from block struct.


typedef struct block {
    size_t size;            // how much memory the user asked for
    struct block* next;     // pointer to the next block
} Block;

void free(void *ptr)
{
    if (!ptr) 
        return;     // Silently return, not failing not. It should fail.

    Block *block = (Block *)ptr - 1;
    
    // Add block to the beginning of the list.
    block->next = free_list;
    free_list = block;
}

Now malloc,

void *malloc(size_t size)
{
    size = (size + 7) & ~7;     // Use LLM to understand this. I did.

    Block* prev = NULL;         // Time to show your Leetcode skill.
    Block* current = free_list;

    while(current)
    {
        if (size <= current->size)
        {
            // found. remove from the list
            // its in middle of the list
            if (prev)
                prev->next = current->next;
            else
                // First block itself.
                free_list = current->next;
        }

        prev = current;
        current = current->next;
    }

    // No reusable block found. Ask OS for new memory.
    void *new_block = sbrk(size + BLOCK_SIZE);
    if (new_block == (void*) -1)
        return NULL; // sbrk failed. 

    Block *block = (Block*)new_block;
    block->size = size;
    return (void*)(block + 1);
}

Limitations

This allocator is extremely minimal and has several limitations:

  • No coalescing of adjacent free blocks
  • No splitting of large blocks (leads to fragmentation)
  • No thread safety
  • No proper error handling

Still, this is a solid foundation and a fun. Who knows—your billion-dollar allocator could start here. (Just kidding. Don’t ship this to production. Please. (but you can though! (no, you should not (…)) ))

Next let’s implement coalesing of adjacent free blocks and splitting of large blocks.

Example code for this post here .