The C-lang Scrolls: Arena

Arena allocators are great fun, they simplify the concerns over lifetimes of objects-that-go-together. Perhaps morbidly stated as the maxim “things that live together die together” arenas are objects that help you manage allocations of objects, all while minimizing calls to malloc and trying to keep objects contiguous in memory.

In this post I want to provide a minimal implementation of arenas with some bells and whistles added for flare.

So what is this Arena anyway?

An arena is, at its core, a linked list of memory regions (why it’s also called region-based allocator) that are filled in monotonically, ie. from first to last until you are forced to add a new region.

The interface for an arena is quite simple, it lets you arena_allocate(arena, T), giving you a T* back; and you can arena_clear(arena) which clears its usage but doesn’t relinquish the memory back to the operating system; and you can arena_free(arena), which clears and frees the memory proper, setting the arena to it’s zero-initalized empty state.

struct arena {
    struct arena* next;
    void* buffer;
    size_t capacity, offset;
};

#define arena_allocate(arena, T) \
    ((typeof(T))*) arena_allocate_pro((arena), sizeof(T), alignof(typeof(T)))
void* arena_allocate_pro(struct arena*, size_t sz, size_t al);
void  arena_clear(struct arena*);
void  arena_free(struct arena*);

First Pass Implementation

An important detail that is often left out, and that tends to irk me quite a lot is the fact that alignment is important, so our “pro” allocation returns an aligned pointer as opposed to tightly fitting the elements.

static void* align_pointer_to(void* ptr, size_t alignment) {
    return (void*) (((uintptr_t) ptr + alignment - 1) & ~(alignment - 1));
}

static struct arena* last_region(struct arena* arena) {
    while (arena->offset == arena->capacity) {
        if (arena->next == NULL)
            return arena;
        else
            arena = arena->next;
    }
    return arena;
}

static bool region_can_fit(struct arena const* arena, size_t req) {
    return arena->offset + req < arena->capacity;
}

static struct arena* new_region(struct arena* arena, size_t cap) {
    assert(arena->next == NULL);
    *(arena->next = calloc(1, sizeof(*arena->next))) = (struct arena) {
        .buffer = malloc(cap),
        .capacity = cap
    };
    return arena->next;
}

static size_t region_size(size_t min) {
    static size_t const page_size = 1 << 14;
    if (min <= page_size)
        return page_size;
    size_t capacity = page_size;
    while (capacity < min)
        capacity = capacity << 1;
    return capacity;
}

void* arena_allocate_pro(struct arena* arena, size_t size, size_t align) {
    retry:
    arena = last_region(arena);
    void* ptr      = arena->buffer + arena_offset;
    void* aligned  = align_pointer_to(ptr, align);
    size_t padding = aligned - ptr;
    size_t used    = padding + size;

    if (region_can_fit(arena, used)) {
        arena->offset += used;
        memset(aligned, 0, size);
        return aligned;
    } else {
        arena->offset = arena->capacity;
        new_region(arena, region_size(size));
        goto retry;
    }
}

void arena_clear(struct arena* arena) {
    while (arena) {
        arena->offset = 0;
        arena = arena->next;
    }
}

void arena_free(struct arena* arena) {
    struct arena* dying = arena->next;
    free(arena->buffer);
    *arena = (struct arena){0};
    while (dying) {
        free(dying->buffer);
        struct arena* next = dying->next;
        free(dying);
        dying = next;
    }
}

Bells and Whistles

char* arena_strndup(struct arena* arena, char const* str, size_t n) {
    size_t len = n;
    for (size_t i = 0; i < len; i++)
        if (str[i] == '\0') len = i;
    char *buffer = arena_allocate_pro(arena, len + 1, alignof(char));
    if (!buffer)
        return NULL;
    memcpy(buffer, str, len);
    buffer[len] = '\0';
    return buffer;
}

char* arena_strdup(struct arena* arena, char const* str) {
    return arena_strndup(arena, str, strlen(str));
}

char* arena_format(struct arena*, char const* fmt, ...) {
    va_list ap;
    va_start(ap, fmt);
    size_t size = vsnprintf(NULL, 0, fmt, ap); 
    va_end(ap);

    char* buffer = arena_allocate(arena, size + 1, alignof(char));
    if (!buffer) 
        return NULL;
    va_start(ap, fmt);
    vsprintf(buffer, fmt, ap);
    va_end(ap);

    return buffer;
}

#define arena_copy(ar, p) \
    typeof((p)) arena_copy_pro((ar), (p), sizeof(*(p)), alignof(*(p)))

void* arena_copy_pro(struct arena* arena, void* ptr, size_t sz, size_t al) {
    void* buffer = arena_allocate_pro(arena, sz, al);
    memcpy(buffer, ptr, sz);
    return buffer;
}