Build your own memory allocator, and watch fragmentation happen

Every C program calls malloc and free, and most C programmers picture them asking the operating system for memory one allocation at a time. That is not what happens. The kernel hands your process memory in big coarse chunks. malloc and free are a library, running in your process, that carves those chunks into the small pieces you actually ask for and remembers which pieces are in use. It is a data structure, and you can build it.

We will build a first-fit allocator with a free list over a single fixed arena. It is the same skeleton malloc has, minus the decades of optimization, and it is enough to make fragmentation, the reason long-running programs bloat, visible.

The one idea

Put a small header in front of every block of memory. The header records the block's size, whether it is free, and where the next block is. The blocks tile the arena end to end, and the free ones form a list threaded through the arena itself. Allocating is walking that list for a block big enough; freeing is flipping a flag. There is no separate bookkeeping structure, because the bookkeeping lives in the memory it manages.

#define ARENA 4096
static unsigned char arena[ARENA];

typedef struct Block {
    size_t size;          // usable bytes in this block
    int free;             // 1 if available
    struct Block *next;   // next block, in address order
} Block;

static Block *head = NULL;

Allocating: first fit, then split

my_malloc walks the list for the first free block large enough. If the block is much bigger than the request, it splits off the remainder into a new free block, so the leftover is not wasted.

static void *my_malloc(size_t want) {
    if (!head) heap_init();                       // one block spanning the arena
    want = (want + 7) & ~((size_t)7);             // align to 8 bytes
    for (Block *b = head; b; b = b->next) {
        if (b->free && b->size >= want) {
            if (b->size >= want + sizeof(Block) + 8) {   // room to split
                Block *rest = (Block *)((unsigned char *)(b + 1) + want);
                rest->size = b->size - want - sizeof(Block);
                rest->free = 1;
                rest->next = b->next;
                b->size = want;
                b->next = rest;
            }
            b->free = 0;
            return b + 1;                          // payload sits right after the header
        }
    }
    return NULL;                                   // arena exhausted
}

Three details that matter:

• The returned pointer is b + 1, the byte just past the header. When the caller later frees it, we recover the header with (Block *)p - 1. That pointer arithmetic is the whole trick that lets free take just a pointer and know the size.
• First fit is the simple policy. Best fit hunts for the tightest block, next fit resumes where it left off. Each trades speed against how much memory gets wasted. Real allocators use size-class bins to make this fast.
• Alignment matters. Returning an address that is not 8-byte aligned will crash on some architectures the moment the caller stores a double there.

Freeing: flip a flag, then coalesce

my_free recovers the header and marks it free. Then it tries to merge with the next block if that is also free, because two adjacent free blocks should become one big block. Otherwise the arena fills with unusable gaps.

static void my_free(void *p) {
    if (!p) return;
    Block *b = (Block *)p - 1;
    b->free = 1;
    if (b->next && b->next->free) {               // merge forward
        b->size += sizeof(Block) + b->next->size;
        b->next = b->next->next;
    }
}

Proof: allocate, free the middle, watch it reuse and fragment

char *a = my_malloc(100), *b = my_malloc(200), *c = my_malloc(50);
strcpy(a, "allocator");
printf("a holds: %s\n", a);
printf("free blocks with three live: %d\n", free_blocks());

my_free(b);
printf("after freeing the middle: %d\n", free_blocks());

char *d = my_malloc(150);
printf("reused the hole: %s\n", d == b ? "yes, same address" : "no");

Running it prints:

a holds: allocator
free blocks with three live: 1
after freeing the middle: 2
reused the hole: yes, same address

d came back at the exact address b used to occupy. The allocator found the hole and refilled it. That is the whole reason malloc is fast: it recycles.

Now the uncomfortable part. Our free only coalesces with the block after it, not before. Free the three allocations in an order that leaves gaps separated by live blocks and the arena ends up with several small free blocks that cannot merge, even though plenty of total memory is free. That is fragmentation: you have the bytes, just not in one contiguous run, so a large request fails while the free total says it should fit. Real allocators fight it with boundary tags that let a block find and merge with its previous neighbor too, and with size bins that keep similar allocations together.

Where this shows up

This is why a server that runs for weeks can slowly swell in memory even without a leak: the heap fragments. It is why game engines and databases often bypass malloc for arena or pool allocators that hand back everything at once. And it is the ground floor under garbage collectors, which automate the free you did by hand here.

If you want to build the rest, coalescing both directions, size-class bins, and an allocator that talks to the kernel for more memory, that is where the operating-systems track on IWTLP takes it next.