Where does the memory actually come from in the first place?

When you call malloc, you aren't magically creating memory; you're asking the operating system for a chunk of the heap. In a simple allocator, we usually do this by moving the "program break," which is the end of the process's data segment. On Unix-like systems, the system call for this is sbrk().

I like to think of sbrk as pushing a wall further back to make more room in a room. If you call sbrk(1024), the OS moves the break up by 1024 bytes and returns a pointer to the start of that new area. If it returns (void*)-1, you're out of luck—the system is out of memory.

void *request_space(size_t size) {
    void *p = sbrk(size);
    if (p == (void*)-1) {
        return NULL; // The OS said no.
    }
    return p;
}

If I give the user a pointer, how do I know how big the block is when they call free()?

This is the "aha!" moment of allocator design. The user only sees the pointer to the memory they can use, but you, the allocator, need to know the size of that block to mark it as free. The trick is to hide a small piece of metadata—a header—immediately before the pointer you return to the user.

I usually define a simple struct for this. When the user asks for 100 bytes, I actually allocate sizeof(struct block_header) + 100. I write the size into the header, then return a pointer that is offset by the size of that header.

struct block_header {
    size_t size;
    int is_free;
    struct block_header *next;
};

void* my_malloc(size_t size) {
    size_t total_size = sizeof(struct block_header) + size;
    struct block_header *header = request_space(total_size);
    header->size = size;
    header->is_free = 0;
    header->next = NULL;
    
    // Return the address immediately AFTER the header
    return (void*)(header + 1);
}

When the user calls my_free(ptr), you just cast the pointer back to a block_header* and subtract one from the pointer to find your metadata. It's a bit of a shell game, but it's how almost every basic allocator works.

What stops the heap from becoming a "Swiss cheese" of tiny, useless gaps?

If you just mark blocks as free, you'll eventually end up with a hundred 8-byte holes that are useless when the user asks for 64 bytes. This is external fragmentation. To fix this, you need to implement "coalescing."

Essentially, whenever you free a block, you should look at the next block in your list. If that block is also free, you merge them into one giant block by updating the size of the first block. I've found that doing this "eagerly" (every time free is called) keeps the heap much cleaner than doing it "lazily" (only when a malloc fails).

The logic looks something like this: while the current block is free and the next block is also free, add the next block's total size (header + data) to the current block's size and skip over the next header. It transforms two small gaps into one useful hole.

📋 Practical Task

Implement a First-Fit Allocator with Coalescing

Your task is to build a functional dynamic memory allocator. You must implement the following two functions: void* my_malloc(size_t size) and void my_free(void* ptr).

• my_malloc: Should first scan the existing linked list of blocks for a free block that is large enough to hold the requested size (First-Fit strategy). If no such block exists, use sbrk() to extend the heap.
• my_free: Should mark the block as free and then immediately perform coalescing: if the subsequent block in the list is also free, merge them into a single larger block.

Test your implementation by allocating several blocks of different sizes, freeing a few in the middle, and then allocating a larger block that can only fit if the middle blocks were successfully coalesced.