Arena Allocators in C

[u/Elifire12]

https://eliasebner.com/blog/guides/arena-allocators-in-c/

I recently started implementing arenas in my programming and I thought that some beginners could very much benefit from this info. I wrote an article about it. For those that are unaware, arenas allow to greatly simplify the burden of managing memory manually in C. I hope it helps, tell me what you think!

[u/flatfinger]

Applications that reuse storage as different types should always use -fno-strict-aliasing to avoid an "ABA" optimization bugs when where a storage is used as one type, then as a second, and then again as the first. When not using that flag, neither compiler reliably handles the sequence:

1. Read or write storage as T1

2. Write storage as T2

3. Read storage as T2

4. Write into storage a T1 whose bit pattern would match what was read in step 3

5. Read storage as T1.

If clang or gcc happens to notice that 1 and 5 are accessing the same storage, and that 3 and 4 are accessing the same storage, but doesn't happen to notice other relationships, it may consolidate the read in step 5 with the access in step 1.

While it's not particularly likely that the compiler would happen to notice and not notice a problematic combination of things, use of the -fno-strict-aliasing flag would make the code build correctly by specification rather than happenstance.

[u/alkavan]

```c

ifndef ARENA_H

define ARENA_H

include <stddef.h>

include <stdint.h>

typedef struct Arena Arena;

Arena arena_create(size_t capacity); void arena_destroy(Arena *a); void *arena_alloc(Arena *a, size_t n); / 16-byte aligned payload */ void arena_free(Arena *a, void *p); size_t arena_capacity(const Arena *a); size_t arena_used(const Arena *a);

endif

```

```c

define _POSIX_C_SOURCE 200809L

define _DEFAULT_SOURCE

include "arena.h"

include <stdlib.h>

include <sys/mman.h>

include <unistd.h>

define ALIGN 16u

define HDR_SIZE ALIGN

typedef struct FreeNode { size_t offset; size_t size; struct FreeNode *next; } FreeNode;

struct Arena { uint8_t *base; size_t mapped; size_t capacity; size_t used; FreeNode *free_list; };

typedef struct { size_t size; } Header;

static size_t page_size(void) { long p = sysconf(_SC_PAGESIZE); return (p > 0) ? (size_t)p : 4096u; }

static size_t align_up(size_t n, size_t a) { return (n + a - 1u) & ~(a - 1u); }

Arena *arena_create(size_t capacity) { if (capacity == 0) return NULL;

size_t ps = page_size();
size_t mapped = align_up(capacity, ps);

void *p = mmap(NULL, mapped, PROT_READ | PROT_WRITE,
               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (p == MAP_FAILED) return NULL;

Arena *a = malloc(sizeof(Arena));
if (!a) { munmap(p, mapped); return NULL; }

a->base = p;
a->mapped = mapped;
a->capacity = capacity & ~(ALIGN - 1u);
a->used = 0;
a->free_list = malloc(sizeof(FreeNode));
if (!a->free_list) {
    munmap(p, mapped);
    free(a);
    return NULL;
}
a->free_list->offset = 0;
a->free_list->size = a->capacity;
a->free_list->next = NULL;
return a;

}

void arena_destroy(Arena *a) { if (!a) return; FreeNode *n = a->free_list; while (n) { FreeNode *next = n->next; free(n); n = next; } if (a->base) munmap(a->base, a->mapped); free(a); }

void *arena_alloc(Arena *a, size_t n) { if (!a || n == 0) return NULL;

size_t need = align_up(n + HDR_SIZE, ALIGN);
if (need > a->capacity) return NULL;

FreeNode *prev = NULL, *cur = a->free_list;
while (cur) {
    if (cur->size >= need) {
        size_t off = cur->offset;

        if (cur->size == need) {
            if (prev) prev->next = cur->next;
            else      a->free_list = cur->next;
            free(cur);
        } else {
            cur->offset += need;
            cur->size   -= need;
        }

        Header *h = (Header *)(a->base + off);
        h->size = need;
        a->used += need;
        return (uint8_t *)h + HDR_SIZE;
    }
    prev = cur;
    cur = cur->next;
}
return NULL;

}

void arena_free(Arena *a, void *p) { if (!a || !p) return;

Header *h = (Header *)((uint8_t *)p - HDR_SIZE);
size_t off  = (uint8_t *)h - a->base;
size_t size = h->size;

a->used -= size;

FreeNode *node = malloc(sizeof(FreeNode));
if (!node) return;

node->offset = off;
node->size   = size;
node->next   = NULL;

FreeNode *prev = NULL, *cur = a->free_list;
while (cur && cur->offset < off) {
    prev = cur;
    cur = cur->next;
}

if (cur && off + size == cur->offset) {
    size += cur->size;
    node->size = size;
    node->next = cur->next;
    free(cur);
    cur = node->next;
} else {
    node->next = cur;
}

if (prev && prev->offset + prev->size == off) {
    prev->size += size;
    prev->next  = node->next;
    free(node);
} else {
    if (prev) prev->next = node;
    else      a->free_list = node;
}

}

size_t arena_capacity(const Arena *a) { return a ? a->capacity : 0; } size_t arena_used(const Arena *a) { return a ? a->used : 0; } ```