Memory Arena

A memory arena (or linear allocator, or bump allocator, or region-based allocator) is a memory allocator that grows linearly.

Data structures and more complicated allocators can be built on top of or composed with a memory arena. Examples include dynamic arrays, linked lists or pools. See A simple, arena-backed, generic dynamic array for C and Composition With More Complex Allocators.

Growing strategies:

Fixed Size Arenas that reallocate (can't take pointers)
Leveraging Virtual Memory
Chaining arenas in a linked list

Types of arenas:

Scratch arena: Arena for intermediate computations that don't persist
Frame arena: Resets every frame, can be back-buffered to remember last frame

API

nullprogram

typedef struct {
    char *beg;
    char *end;
} arena;

arena newarena(ptrdiff_t cap)
{
    arena a = {0};
    a.beg = malloc(cap);
    a.end = a.beg ? a.beg+cap : 0;
    return a;
}

void *alloc(arena *a, ptrdiff_t size, ptrdiff_t align, ptrdiff_t count)
{
    ptrdiff_t avail = a->end - a->beg;
    ptrdiff_t padding = -(uintptr_t)a->beg & (align - 1);
    if (count > (avail - padding)/size) {
        abort();  // one possible out-of-memory policy
    }
    ptrdiff_t total = size * count;
    char *p = a->beg + padding;
    a->beg += padding + total;
    return memset(p, 0, total);
}

digital grove

Characteristics:

Arena is part of its own allocated memory block
Aligned memory
Temporary arena is own type
Reserves and commits
No linked list of arenas as growing strategy
No out-of-memory fallback strategy

API:

#define ARENA_COMMIT_GRANULARITY Kilobytes(4)
#define ARENA_DECOMMIT_THRESHOLD Megabytes(64)

typedef struct Arena Arena;
struct Arena
{
    U64 pos;
    U64 commit_pos;
    U64 align;
    U64 size;
    Arena *ptr; /* unused */
    U64 _unused_[3];
};

Arena* ArenaAlloc(U64 size);              /* create */
void*  ArenaPush(Arena *arena, U64 size); /* alloc */
void   ArenaClear(Arena *arena);          /* reset */
void   ArenaRelease(Arena *arena);        /* destroy */

void   ArenaPopTo(Arena *arena, U64 pos); /* used for temp arena */
void   ArenaPop(Arena *arena, U64 size);  /* used primarily for strings */

Arena* ArenaAllocDefault(void); /* helper */
U64    ArenaPos(Arena *arena);  /* helper */

/* helper macros */
#define PushArrayNoZero(arena, type, count) (type *)ArenaPushNoZero((arena), sizeof(type)*(count))
#define PushArray(arena, type, count)       (type *)ArenaPush((arena), sizeof(type)*(count))

/* temporary arenas */
typedef struct Temp {
    Arena *arena;
    U64 pos;
} Temp;
Temp TempBegin(Arena *arena) { Temp temp = {0}; temp.arena = arena; temp.pos = arena->pos; return temp; }
void TempEnd(Temp temp) { ArenaPopTo(temp.arena, temp.pos); }
#define ArenaTempBlock(arena, name) Temp name = {0}; DeferLoop(name = TempBegin(arena), TempEnd(name))

Implementation:

Arena* ArenaAlloc(U64 size)
{
    /* arena is always a multiple of 64MB */
    U64 size_roundup_granularity = Megabytes(64);
    size += size_roundup_granularity-1;
    size -= size%size_roundup_granularity;

    /* allocate from os */
    void *block = ArenaImpl_Reserve(size);

    /* commit in 4KB chunks */
    U64 initial_commit_size = ARENA_COMMIT_GRANULARITY;
    Assert(initial_commit_size >= sizeof(Arena));
    ArenaImpl_Commit(block, initial_commit_size);

    /* init arena */
    Arena *arena = (Arena *)block;
    arena->pos = sizeof(Arena);
    arena->commit_pos = initial_commit_size;
    arena->align = 8;
    arena->size = size;

    return arena;
}

void* ArenaPush(Arena *arena, U64 size)
{
    void *result = 0;

    if (arena->pos + size <= arena->size) {

        U8 *base = (U8 *)arena;

        /* align the pushed size */
        U64 post_align_pos = (arena->pos + (arena->align-1));
        post_align_pos -= post_align_pos%arena->align;
        U64 align = post_align_pos - arena->pos;
        result = base + arena->pos + align;
        arena->pos += size + align;

        /* commit if necessary */
        if (arena->commit_pos < arena->pos) {
            U64 size_to_commit = arena->pos - arena->commit_pos;
            size_to_commit += ARENA_COMMIT_GRANULARITY - 1;
            size_to_commit -= size_to_commit%ARENA_COMMIT_GRANULARITY;
            ArenaImpl_Commit(base + arena->commit_pos, size_to_commit);
            arena->commit_pos += size_to_commit;
        }
    } else { /* fallback strategy: fail for now */ }

    /* zero out memory by default */
    MemoryZero(result, size);

    return result;
}

raddebugger

Utilizes ASan for poisoned memory inside the arena

API:

#define ARENA_HEADER_SIZE              128
#define ARENA_RESERVE_SIZE             MB(64)
#define ARENA_COMMIT_SIZE              KB(64)
#define ARENA_RESERVE_SIZE_LARGE_PAGES MB(8)
#define ARENA_COMMIT_SIZE_LARGE_PAGES  MB(2)

typedef struct Arena Arena;
struct Arena
{
    struct Arena *prev;
    struct Arena *current;
    U64 base_pos;
    U64 pos;
    U64 cmt;
    U64 res;
    U64 align;
    B8 grow;
    B8 large_pages;
};

typedef struct Temp Temp;
struct Temp
{
    Arena *arena;
    U64 pos;
};

/* implementation */
internal Arena* arena_alloc__sized(U64 init_res, U64 init_cmt);
internal Arena* arena_alloc(void);
internal void   arena_release(Arena *arena);
internal void*  arena_push__impl(Arena *arena, U64 size);
internal U64    arena_pos(Arena *arena);
internal void   arena_pop_to(Arena *arena, U64 pos);
internal void   arena_absorb(Arena *arena, Arena *sub);

/* wrappers */
internal void* arena_push(Arena *arena, U64 size);
internal void* arena_push_contiguous(Arena *arena, U64 size);
internal void  arena_clear(Arena *arena);
internal void  arena_push_align(Arena *arena, U64 align);
internal void  arena_put_back(Arena *arena, U64 amt);

internal Temp  temp_begin(Arena *arena);
internal void  temp_end(Temp temp);

/* mini-arena helper */
internal B32 ensure_commit(void **cmt, void *pos, U64 cmt_block_size);

/* helper macros */
#define push_array_no_zero(a,T,c) (T*)arena_push((a), sizeof(T)*(c))
#define push_array(a,T,c) (T*)MemoryZero(push_array_no_zero(a,T,c), sizeof(T)*(c))

Implementation:

Arena* arena_alloc__sized(U64 init_res, U64 init_cmt)
{
  ProfBeginFunction();
  Assert(ARENA_HEADER_SIZE < init_cmt && init_cmt <= init_res);

  void *memory = 0;
  U64 res = 0;
  U64 cmt = 0;
  B32 large_pages = os_large_pages_enabled();
  if(large_pages)
  {
    U64 page_size = os_large_page_size();
    res = AlignPow2(init_res, page_size);
#if OS_WINDOWS
    cmt = res;
#else
    cmt = AlignPow2(init_cmt, page_size);
#endif
    memory = os_reserve_large(res);
    if(!os_commit_large(memory, cmt))
    {
      memory = 0;
      os_release(memory, res);
    }
  }
  else
  {
    U64 page_size = os_page_size();
    res = AlignPow2(init_res, page_size);
    cmt = AlignPow2(init_cmt, page_size);
    memory = os_reserve(res);
    if(!os_commit(memory, cmt))
    {
      memory = 0;
      os_release(memory, res);
    }
  }

  Arena *arena = (Arena*)memory;
  if(arena)
  {
      /* ASan support */
      AsanPoisonMemoryRegion(memory, cmt);
      AsanUnpoisonMemoryRegion(memory, ARENA_HEADER_SIZE);

      /* init arena */
      arena->prev        = 0;
      arena->current     = arena;
      arena->base_pos    = 0;
      arena->pos         = ARENA_HEADER_SIZE;
      arena->cmt         = cmt;
      arena->res         = res;
      arena->align       = 8;
      arena->grow        = 1;
      arena->large_pages = large_pages;
  }

  ProfEnd();
  return arena;
}

Scratch Arena (Temporary/Transient Arena)

API designs

Two options to design APIs using scratch arenas:

Option 1: Make caller pass in scratch arena when the function needs it

/* caller */
mem_arena_t scratch = mem_arena_scratch(0);
compute_number(3.5f, scratch);


/* callee */
int compute_number(float value, mem_arena_t scratch)
{
    void* data = mem_arena_alloc(&scratch, sizeof(float) * 5);
    // ...
}

Option 2: Pass normal arena and let function create scratch arena

/* caller */
compute_number(3.5f, arena);

/* callee */
int compute_number(float value, mem_arena_t* arena)
{
    mem_arena_t scratch = mem_arena_scratch(arena);
    void* scratch = mem_arena_alloc(&scratch, sizeof(float) * 5);
    // ...
    mem_arena_unscratch(&scratch);
}

But how do we use a scratch arena for a throwaway computation and then push the result onto the arena without overlapping with the scratch arena? a) Push onto the arena before using the scratch b) Have fixed scratch arenas that get reused

Passed-by-value Arenas

Take following arena with its implied memory layout:

struct arena_t {
    // arena bounds, will get reset implicitly when passed by value
    u8* beg;
    u8* end;
};

/*
    Memory layout (if arena is allocated in-place):

           +-------------+
           |     +-------|------------------------
           |     |       |                       |
        |-----|-----|----v-----------------------v
        | beg | end |xxxxx                       |
        |-----------|----------------------------|
           arena_t      memory
*/

If the arena is passed-by-reference, allocations from it persists after the call. If the arena is passed-by-value, allocations are "forgotten" after the call (i.e. it acts as a scratch arena);

void do_stuff(int param1, arena_t* arena, arena_t scratch)
{
    void* scratch_data = arena_alloc(&scratch, 1024);

    /* compute intermediate result using scratch */

    void* persist_data = arena_alloc(arena, sizeof(float));

    /* write result into persistent arena */

    return;
}

We can upgrade the arena structure to support keeping track of its commit position when it's passed by value:

struct arena_t {
    u8*   beg;
    u8*   end;
    u8**  commit // commit bound, data is located elsewhere stable
};

The memory layout would look something like this (i.e. there would be an additional header for the arena):

                +-----------------------+
                |     +-----------------|----------------------+
                |     |                 |                      |
|------------|--------|-----------|-----v----------------------v
| commit_pos | beg | end | commit |xxxxx_____________          |
|-----^------|---------------|----|------------------^---------|
      |        arena_t       |           memory      |
      +----------------------+                   commit_pos

This can be further generalized by adding the concept of a persistent arena_header_t that never gets passed (by value or otherwise). Instead, arena_t keeps a pointer to it:

struct arena_t {
    arena_header_t* header;
    u8*   beg;
    u8*   end;
};

                +-----------------------+
                |     +-----------------|----------------------+
                |     |                 |                      |
|------------|--------|-----------|-----v----------------------v
|    ...     | beg | end | header |xxxxx_____________          |
|-----^------|---------------|----|----------------------------|
      |        arena_t       |           memory
      +----------------------+

The header can contain information about chained arenas, commit positions, alignment and so on, i.e. everything that should not get reset when returning from a function using the arena as scratch.

struct arena_header_t {
    u8* commit;
    arena_header_t* next; // chained arenas
};

Handling Cleanup of Resources

Problem arises when we need to clean up resources like file handles, network sockets, thread locks, etc. For this, we need a mechanism to keep track of these resources and call their destructors.

One possibility is to maintain a linked list of these resources and their cleanup functions inside the arena via a new arena API call.

struct mem_arena_t {
    // ...
    /* arena fields */
    // ...
    cleanup_node_t* head;
};
struct cleanup_node_t  {
    cleanup_node_t* next;
    void (*func)(void*);
    void* args;
};

mem_arena_add_cleanup(void (*cleanup)(void*), void* args)

mem_arena_release() {
    /* traverse linked list of cleanup nodes */
    for_each(node)  {
        node->func(node->args);
    }
}

/* usage */
resource_t* res = mem_arena_alloc(...);
mem_arena_add_cleanup(&res_release, &res);

See Scope Stack Allocation