Writing a simple allocator

The system malloc is a general-purpose allocator — it handles any size of allocation and any pattern of frees. That generality has a cost: it is slow for high-frequency small allocations, and it can fragment the heap. Understanding how to write custom allocators is an advanced but important C skill, used in game engines, databases, parsers, and any system where allocation performance matters.

The bump allocator

The simplest possible allocator: an arena with a single pointer that advances ("bumps") with each allocation. Freeing is not supported individually — you free the entire arena at once.

#include <stdio.h>
#include <stddef.h>
#include <string.h>
#include <stdint.h>

typedef struct {
    char   *start;   /* beginning of the arena */
    char   *ptr;     /* current allocation position */
    char   *end;     /* one past the end */
} BumpAllocator;

void bump_init(BumpAllocator *a, void *buffer, size_t size) {
    a->start = buffer;
    a->ptr   = buffer;
    a->end   = (char *)buffer + size;
}

void *bump_alloc(BumpAllocator *a, size_t size, size_t alignment) {
    /* Align ptr up to the required alignment */
    uintptr_t ptr = (uintptr_t)a->ptr;
    uintptr_t aligned = (ptr + alignment - 1) & ~(alignment - 1);

    if ((char *)aligned + size > a->end) {
        return NULL; /* out of space */
    }

    a->ptr = (char *)aligned + size;
    return (void *)aligned;
}

void bump_reset(BumpAllocator *a) {
    a->ptr = a->start; /* free everything at once */
}

int main(void) {
    char buffer[1024];
    BumpAllocator arena;
    bump_init(&arena, buffer, sizeof(buffer));

    int *nums = bump_alloc(&arena, 10 * sizeof(int), _Alignof(int));
    double *vals = bump_alloc(&arena, 5 * sizeof(double), _Alignof(double));

    if (!nums || !vals) { fprintf(stderr, "OOM\n"); return 1; }

    for (int i = 0; i < 10; i++) { nums[i] = i * i; }
    for (int i = 0; i < 5; i++)  { vals[i] = i * 3.14; }

    printf("nums[9] = %d\n", nums[9]);
    printf("vals[4] = %.2f\n", vals[4]);

    bump_reset(&arena); /* free everything */
    return 0;
}

Advantages: O(1) allocation. Zero fragmentation within the arena. No free list to maintain.

Disadvantages: Cannot free individual allocations. Arena must be large enough upfront.

Use cases: Per-frame allocations in game engines. Per-request allocations in web servers. Parsing temporary data structures.

A free-list allocator (conceptual sketch)

The system malloc maintains a free list: a linked list of available memory blocks. When you call malloc(n):

1. Walk the free list for a block of at least n + sizeof(header) bytes.
2. Split the block: use n + sizeof(header) bytes for this allocation, return the remainder to the free list.
3. Return a pointer past the header.

When you call free(p):

1. Find the header just before p.
2. Mark the block as free.
3. Coalesce with adjacent free blocks (to prevent fragmentation).
4. Return to the free list.

/* The header stored before each allocation */
typedef struct BlockHeader {
    size_t size;               /* usable size (not including header) */
    int    free;               /* 1 if free, 0 if in use */
    struct BlockHeader *next;  /* next block in the free list */
} BlockHeader;

Implementing a full free-list allocator is the challenge in the next lesson. The key insight: the memory for the free list nodes is carved out of the same arena being managed.

Why custom allocators matter

The challenge in the arena allocator challenge will ask you to implement an arena allocator that handles multiple allocation lifetimes via a "watermark" mechanism. Real uses:

• Game engines (Unity, Unreal): frame allocator frees all per-frame data in one call. Level allocator lives for the duration of a level load.
• Database query engines: each query gets an arena; the allocator is reset when the query completes.
• Compilers: AST nodes, token lists, and IR all allocated from arenas per compilation unit.
• Network servers: per-connection arenas, freed when the connection closes.

Where to go next

Next: the arena allocator challenge — you will implement a complete arena allocator with watermarks, supporting allocation and rollback to previous watermarks, and verify correctness under AddressSanitizer.