How I Built `malloc` and `free` in C From Scratch

Memory allocation is one of the most fundamental concepts in programming, but many developers rarely stop to think about how it actually works under the hood. In this post, I’ll walk you through how I built my own versions of malloc and free in C from scratch.

Why Build Your Own malloc?

C provides malloc and free to dynamically allocate and deallocate memory. But these functions are just abstractions on top of lower-level memory management. By building our own, you get:

• A deeper understanding of memory management
• Insight into fragmentation and heap management
• Hands-on experience with pointers and structs in C

Let’s dive in.

---

Step 1: Understand the Basics

At its core, dynamic memory allocation involves:

1. A large memory pool: This could be a chunk of memory obtained from the system using sbrk() or mmap().
2. A bookkeeping system: To know which parts of memory are free and which are allocated.
3. Allocation logic: To find a free block large enough to satisfy a request.
4. Deallocation logic: To mark memory as free and possibly merge adjacent free blocks.

---

Step 2: Define a Memory Block Structure

We need a structure to represent each memory block:

typedef struct Block {
    size_t size;         // Size of the block
    int free;            // 1 if free, 0 if allocated
    struct Block *next;  // Pointer to the next block
} Block;

• size tells us how much memory is in the block.
• free indicates whether the block is currently available.
• next links all blocks into a linked list for easy traversal.

---

Step 3: Create a Memory Pool

For simplicity, we’ll create a fixed-size memory pool:

#define POOL_SIZE 1024 * 1024  // 1 MB
char memory_pool[POOL_SIZE];
Block *free_list = (Block*)memory_pool;

Initially, the entire pool is one big free block:

free_list->size = POOL_SIZE - sizeof(Block);
free_list->free = 1;
free_list->next = NULL;

---

Step 4: Implement malloc

malloc needs to:

1. Traverse the free list
2. Find a block large enough
3. Split the block if it’s bigger than needed
4. Mark it as allocated

void* my_malloc(size_t size) {
    Block *curr = free_list;
    while (curr) {
        if (curr->free && curr->size >= size) {
            // Split the block if too large
            if (curr->size > size + sizeof(Block)) {
                Block *new_block = (Block*)((char*)curr + sizeof(Block) + size);
                new_block->size = curr->size - size - sizeof(Block);
                new_block->free = 1;
                new_block->next = curr->next;
                curr->next = new_block;
                curr->size = size;
            }
            curr->free = 0;
            return (char*)curr + sizeof(Block);
        }
        curr = curr->next;
    }
    return NULL; // Out of memory
}

• Notice how we return a pointer after the Block struct, so the user only sees usable memory.
• Splitting prevents wasting large blocks when only a small amount of memory is requested.

---

Step 5: Implement free

free needs to:

1. Convert the user pointer back to the block pointer
2. Mark it as free
3. Optionally merge adjacent free blocks (coalescing)

void my_free(void *ptr) {
    if (!ptr) return;

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

    // Coalesce adjacent free blocks
    Block *curr = free_list;
    while (curr) {
        if (curr->free && curr->next && curr->next->free) {
            curr->size += sizeof(Block) + curr->next->size;
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }
}

• Coalescing helps reduce fragmentation over time.

---

Step 6: Test It

Here’s a simple test:

int main() {
    int *arr = (int*)my_malloc(10 * sizeof(int));
    for (int i = 0; i < 10; i++) arr[i] = i;

    for (int i = 0; i < 10; i++) printf("%d ", arr[i]);
    printf("\n");

    my_free(arr);
    return 0;
}

You should see 0 1 2 3 4 5 6 7 8 9 printed. Memory is correctly allocated and freed.

---

Step 7: Limitations & Next Steps

Our simple malloc has limitations:

• Fixed memory pool size
• No thread safety
• No best-fit or worst-fit strategies
• No memory returned to the OS

Next steps could include:

• Using sbrk() or mmap() to request memory dynamically
• Implementing different allocation strategies
• Adding realloc support
• Handling multithreading with mutexes

---

Conclusion

Building malloc and free from scratch is a fantastic exercise for understanding memory management in C. Even this simple implementation shows how:

• Memory is tracked in blocks
• Allocation requires splitting blocks
• Freeing memory can involve coalescing to reduce fragmentation

This knowledge will make you a better C programmer and help you understand what happens behind the scenes every time you call malloc.