Challenge: Arena allocator

Implement a complete arena allocator with watermarks, supporting aligned allocation and rollback to any previous position.

An arena allocator with watermarks supports not just "free everything" but "free back to a saved position" — the watermark. This is used in Lua, SQLite, and many compiler front-ends to implement scoped lifetimes without the cost of individual frees.

Specification

Implement the following API in arena.h and arena.c:

typedef struct Arena Arena;

/* Create an arena backed by a heap-allocated buffer of `capacity` bytes. */
Arena *arena_create(size_t capacity);

/* Allocate `size` bytes with at least `alignment` alignment.
   Returns NULL if out of space. */
void *arena_alloc(Arena *a, size_t size, size_t alignment);

/* Save the current allocation position as a watermark. */
size_t arena_watermark(const Arena *a);

/* Roll back all allocations after the given watermark.
   Calls after this watermark are freed, prior ones remain valid. */
void arena_rollback(Arena *a, size_t mark);

/* Reset the entire arena (free everything). */
void arena_reset(Arena *a);

/* Destroy the arena and its backing buffer. */
void arena_destroy(Arena *a);

Requirements

All memory comes from a single malloc call in arena_create.
arena_alloc must return correctly aligned memory. Use the alignment rounding technique from the simple allocator lesson.
arena_watermark returns an offset (bytes from the start of the arena) that uniquely identifies the current position.
arena_rollback(a, mark) must make the memory after mark available again.
Passing a mark that is past the current position to arena_rollback is a user error — your implementation may assert or silently no-op.
Verify with AddressSanitizer (-fsanitize=address): no use-after-rollback.

Test harness

/* test_arena.c */
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "arena.h"

int main(void) {
    Arena *a = arena_create(4096);
    assert(a != NULL);

    /* Basic allocation */
    int *nums = arena_alloc(a, 10 * sizeof(int), _Alignof(int));
    assert(nums != NULL);
    for (int i = 0; i < 10; i++) { nums[i] = i; }
    assert(nums[9] == 9);

    /* Save watermark and allocate more */
    size_t mark = arena_watermark(a);
    char *buf = arena_alloc(a, 64, _Alignof(char));
    assert(buf != NULL);
    strcpy(buf, "temporary");

    /* Rollback to watermark */
    arena_rollback(a, mark);

    /* nums is still valid */
    assert(nums[0] == 0);
    assert(nums[9] == 9);

    /* Allocate again -- should reuse the rolled-back space */
    double *vals = arena_alloc(a, 5 * sizeof(double), _Alignof(double));
    assert(vals != NULL);
    vals[0] = 1.0;

    arena_reset(a);
    arena_destroy(a);

    printf("All tests passed.\n");
    return 0;
}

Suggested implementation structure

/* arena.c */
#include "arena.h"
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

struct Arena {
    char   *base;
    size_t  capacity;
    size_t  offset;
};

Arena *arena_create(size_t capacity) {
    Arena *a = malloc(sizeof(Arena));
    if (!a) { return NULL; }
    a->base = malloc(capacity);
    if (!a->base) { free(a); return NULL; }
    a->capacity = capacity;
    a->offset = 0;
    return a;
}

void *arena_alloc(Arena *a, size_t size, size_t alignment) {
    uintptr_t current = (uintptr_t)(a->base + a->offset);
    uintptr_t aligned = (current + alignment - 1) & ~(uintptr_t)(alignment - 1);
    size_t new_offset = (size_t)(aligned - (uintptr_t)a->base) + size;
    if (new_offset > a->capacity) { return NULL; }
    a->offset = new_offset;
    return (void *)aligned;
}

size_t arena_watermark(const Arena *a) {
    return a->offset;
}

void arena_rollback(Arena *a, size_t mark) {
    assert(mark <= a->offset);
    a->offset = mark;
}

void arena_reset(Arena *a) {
    a->offset = 0;
}

void arena_destroy(Arena *a) {
    free(a->base);
    free(a);
}

Build and verify

gcc -Wall -Wextra -g -fsanitize=address -std=c11 \
    test_arena.c arena.c -o test_arena
./test_arena

Zero ASan errors required.

Extension: scratch regions

Add arena_scratch_begin and arena_scratch_end that save/restore the watermark implicitly via a struct:

typedef struct { Arena *a; size_t mark; } ScratchRegion;

ScratchRegion arena_scratch_begin(Arena *a);
void          arena_scratch_end(ScratchRegion scratch);

This lets you write ScratchRegion s = arena_scratch_begin(arena); at the start of a function and arena_scratch_end(s); at the end, automatically reclaiming all temporary allocations made during the function.

What you practised

Aligned pointer arithmetic using uintptr_t
The watermark pattern for scoped lifetimes
Building a complete allocator with a clean API
Verifying memory safety with AddressSanitizer

The next module is Concurrency with pthreads — creating threads, synchronising with mutexes, and avoiding data races.

Finished reading? Mark it complete to track your progress.