Skip to main content
Be Bitwise
CAdvanced Memory in C

Part ofSystems Programming Companion, week 11

Capstone: Build a Memory Allocator

For this capstone you'll build a working memory allocator from scratch: my_malloc and my_free, with block splitting, coalescing, and an mmap fast path for big requests. There's no project in systems programming that teaches more in fewer hours. You can't fake your way through it — every part demands a real grasp of memory layout, pointer arithmetic, and the trade-offs that allocators in the wild navigate every day.

The Design

The allocator keeps a free list inside a static heap buffer. Each block carries a header tracking its size and whether it's free. On allocation, walk the free list, find a fitting block, split it if it's bigger than needed. On free, flip the block's flag and merge it with any free neighbours.

Block Header

Every block plants a header right before the chunk of memory the user sees:

c
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>
typedef struct block_header {
size_t size; // Size of the usable area (not including header)
bool is_free;
struct block_header *next;
} block_header;
#define ALIGNMENT 16
#define ALIGN(n) (((n) + (ALIGNMENT - 1)) & ~(size_t)(ALIGNMENT - 1))
#define HEADER_SIZE ALIGN(sizeof(block_header)) // 32 bytes on x86-64
#define HEAP_SIZE (64 * 1024) // 64 KB
static _Alignas(ALIGNMENT) uint8_t heap[HEAP_SIZE];
static block_header *head = NULL;
static bool initialized = false;

Alignment does a lot of quiet work here. malloc promises memory aligned for any type, which on x86-64 means 16 bytes (SSE loads and long double care about this). The raw sizeof(block_header) is 24, so if headers were packed back to back every user pointer would land 8 bytes off. Rounding the header up to 32 and every request up to a multiple of 16 keeps each pointer we hand out on a 16-byte boundary. The _Alignas matters too: a plain uint8_t array only has to be 1-byte aligned, and treating a misaligned address as a block_header * is undefined behaviour.

The layout in memory looks like this:

Initialisation

c
static void heap_init(void) {
head = (block_header *)heap;
head->size = HEAP_SIZE - HEADER_SIZE;
head->is_free = true;
head->next = NULL;
initialized = true;
}

The entire heap starts as one big free block.

Finding a Free Block (First Fit)

c
static block_header *find_free_block(size_t size) {
block_header *current = head;
while (current != NULL) {
if (current->is_free && current->size >= size) {
return current;
}
current = current->next;
}
return NULL;
}

First-fit is dead simple, but it tends to chew up the heap with fragments. Smarter strategies — best-fit (pick the smallest block that fits) and next-fit (resume the search where it last stopped) — fragment less. We're sticking with first-fit because the goal here is clarity.

Splitting Blocks

When the chosen block has more space than the request, slice it in two: one piece for the caller, one piece left on the free list:

c
#define MIN_SPLIT 16
static void split_block(block_header *block, size_t size) {
// Compare before subtracting: size_t can't go negative, it wraps.
if (block->size < size + HEADER_SIZE + MIN_SPLIT) {
return; // Leftover too small to be useful; hand over the whole block
}
block_header *new_block = (block_header *)
((uint8_t *)block + HEADER_SIZE + size);
new_block->size = block->size - size - HEADER_SIZE;
new_block->is_free = true;
new_block->next = block->next;
block->size = size;
block->next = new_block;
}

The MIN_SPLIT threshold stops us minting tiny, useless blocks that no allocation could ever fit into.

Look hard at the order of that check. The tempting version computes size_t remaining = block->size - size - HEADER_SIZE; first and tests remaining < 16 afterwards. Reuse a freed 16-byte block for another 16-byte request and that subtraction is 16 - 16 - 32. An unsigned type can't hold -32, so it wraps to about 18 quintillion, the "too small" test passes as "plenty of room", and the allocator writes a fresh header straight over the next block's header. Your test program would print garbage, or crash three calls later somewhere unrelated. Unsigned underflow in size arithmetic is a classic source of real heap-corruption CVEs, so get into the habit of comparing first and subtracting second.

my_malloc

c
void *my_malloc(size_t size) {
if (!initialized) heap_init();
if (size == 0 || size > SIZE_MAX - HEADER_SIZE - ALIGNMENT) return NULL;
size = ALIGN(size); // Round up to a multiple of 16
block_header *block = find_free_block(size);
if (block == NULL) {
return NULL; // Out of memory
}
split_block(block, size);
block->is_free = false;
return (uint8_t *)block + HEADER_SIZE;
}
Key Concept

The pointer the user gets back sits HEADER_SIZE bytes past the header. On my_free, subtract HEADER_SIZE to recover the header. Real malloc implementations play exactly the same game.

The SIZE_MAX guard catches requests so large that rounding them up would wrap around to a small number. Without it, my_malloc(SIZE_MAX) would round to 0 and return a block the caller believes is enormous. glibc rejects the same requests for the same reason.

my_free with Coalescing

Freeing a block has two parts: flag it free, then fuse it with any free neighbours. Skip the coalescing step and the heap fragments into uselessness within minutes:

c
static void coalesce(void) {
block_header *current = head;
while (current != NULL && current->next != NULL) {
if (current->is_free && current->next->is_free) {
// Merge current and next
current->size += HEADER_SIZE + current->next->size;
current->next = current->next->next;
// Do not advance - check if we can merge again
} else {
current = current->next;
}
}
}
void my_free(void *ptr) {
if (ptr == NULL) return;
block_header *block = (block_header *)
((uint8_t *)ptr - HEADER_SIZE);
block->is_free = true;
coalesce();
}

Coalescing sweeps the whole list and fuses any consecutive free blocks it finds. O(n), but fragmentation stays low.

Testing the Allocator

c
void print_heap(void) {
if (!initialized) heap_init();
block_header *current = head;
int i = 0;
while (current != NULL) {
printf("Block %d: size=%zu, free=%d\n",
i++, current->size, current->is_free);
current = current->next;
}
printf("---\n");
}
int main(void) {
printf("Initial heap:\n");
print_heap();
int *a = my_malloc(sizeof(int));
int *b = my_malloc(sizeof(int));
int *c = my_malloc(sizeof(int));
*a = 1; *b = 2; *c = 3;
printf("After 3 allocations:\n");
print_heap();
my_free(b);
printf("After freeing b:\n");
print_heap();
int *d = my_malloc(sizeof(int));
*d = 4;
printf("After allocating d (should reuse b's block):\n");
print_heap();
printf("d reused b's block: %s\n", (void *)d == (void *)b ? "yes" : "no");
printf("Values: %d %d %d\n", *a, *d, *c);
my_free(a);
my_free(c);
my_free(d);
printf("After freeing all:\n");
print_heap();
return 0;
}

Extending with mmap for Large Allocations

Real allocators reach for mmap when allocations get large. Keeps the main heap from being chewed up:

c
#include <sys/mman.h>
#define MMAP_THRESHOLD (32 * 1024) // 32 KB
void *my_malloc(size_t size) {
if (!initialized) heap_init();
if (size == 0 || size > SIZE_MAX - HEADER_SIZE - ALIGNMENT) return NULL;
size = ALIGN(size);
// Large allocations go through mmap
if (size >= MMAP_THRESHOLD) {
size_t total = HEADER_SIZE + size;
block_header *block = mmap(NULL, total,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (block == MAP_FAILED) return NULL;
block->size = size;
block->is_free = false;
block->next = NULL; // Never joins the free list
return (uint8_t *)block + HEADER_SIZE;
}
// Small allocations use the free list
block_header *block = find_free_block(size);
if (block == NULL) return NULL;
split_block(block, size);
block->is_free = false;
return (uint8_t *)block + HEADER_SIZE;
}

my_free now has to recognise an mmap'd block and hand it back to the kernel. Setting is_free on it would leak the mapping forever, since it isn't on the free list. You might be tempted to use next == NULL as the marker, but the last block in the heap has next == NULL too. The address itself is a reliable test: anything outside our static array came from mmap.

c
static bool in_heap(void *ptr) {
return (uint8_t *)ptr >= heap && (uint8_t *)ptr < heap + HEAP_SIZE;
}
void my_free(void *ptr) {
if (ptr == NULL) return;
block_header *block = (block_header *)((uint8_t *)ptr - HEADER_SIZE);
if (!in_heap(ptr)) {
munmap(block, HEADER_SIZE + block->size);
return;
}
block->is_free = true;
coalesce();
}

glibc does something similar: it sets a bit in the chunk's size field (IS_MMAPPED) when it creates the chunk, and free checks that bit before anything else.

Run the Whole Thing

Here's the finished allocator in one file, with the large-allocation path exercised as well. Run it, then break it on purpose: put the old subtract-first version of split_block back and watch what happens to c's value.

Try itThe complete allocator. Try a first-fit vs best-fit search, or shrink HEAP_SIZE until allocations start failing.
C (GCC 9.2.0)

What Real Allocators Do Differently

Production allocators like glibc malloc, jemalloc, and tcmalloc layer on a stack of optimisations:

  • Thread-local caches: Each thread has its own pool of recently freed blocks, reducing lock contention.
  • Size classes: Instead of a single free list, they maintain separate lists for different size ranges (8, 16, 32, 64... bytes).
  • Best-fit or buddy system: More sophisticated search strategies reduce fragmentation.
  • Metadata separation: Storing headers out-of-band prevents overwrites from corrupting allocator state.
  • Huge page support: Using 2 MB or 1 GB pages for large allocations reduces TLB misses.

Yours is the stripped-down version, but the bones are right. Every real allocator at heart is doing the same three things: maintaining a free list, splitting blocks, and coalescing free space.

Challenges

Implement a simple malloc and free using a free list. Allocate 3 blocks, free the middle one, allocate a new block that fits in the freed space, then print the values stored in all 3 blocks.

C (GCC 9.2.0)