// Arena allocation // Michal Vlasák, FIT CTU, 2023 #pragma once #include <stddef.h> #include <stdalign.h> // This header defines the API of two different Arena allocators - `Arena` and // `Garena`. In general arena allocators all "bump allocate" their memory. I.e. // they have a pointer to chunk of available memory from which they allocate // sequentially -- when allocation is requested the returned memory is in the // beginning of the first chunk: former free space pointer is returned and // new one is formed by incrementing the former by the allocated size ("bumped"). // This is very efficient, because it wastes no space on metadata and the code // for allocation is very fast. // metadata // // The problem is that since individual allocations are not tracked, it is not // possible to arbitrarily free allocations. But it is possible to deallocate // _all_ the memory at once. This may seem too restricting, but in fact a lot of // problem domains generate a lot of temporary objects and then get rid of all // of them (e.g. a web server serving a single request). // // Another problem with arena allocation is what to do when they exhaust the // free memory. There are a few options: // // (1) Abort, since the memory is exhausted. Easy to do, makes sense e.g. for // microcontrollers with limited amount or memory, or programs with known // upper bound on memory consumption. // // (2) Allocate a new chunk of memory to be used in addition to the old one (old // allocations are kept in old chunk(s). New allocations are performed in a // new chunk). This has the advantage that all pointers to previously // allocated data are kept valid, the disadvantage is that the memory is no // longer contiguous. // // (3) Allocate a new (bigger) chunk memory and _move_ the old allocations to // the new space. New allocations will be made in the rest of the new space. // This is dual to the previous approach, pointers to previous allocations // an be invalidated on every allocation, but the memory is kept contiguous // at all times. // // (4) Extend the current chunk by allocating the memory immediately following // it. This is a refinement that has advantages of both of the previous // approaches, while having none of their limitations. The problem is // achieving it. On modern systems it can be due to the use of virtual // memory. // // There are many great resources on Arenas and associated topics, I can // recommend at the very least: // // - https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator // - https://www.gingerbill.org/article/2019/02/01/memory-allocation-strategies-001/ // - https://en.wikipedia.org/wiki/Region-based_memory_management // This particular arena implementation is the approach (2). No pointers are ever // invalidated. The chunks are allocated with `malloc` and freed with `free`. // The current allocation position (even across chunks) can be saved and // restored, so not all allocated memory has to be deallocated at once. But the // "stack" principle still has to be obeyed. // // The `Arena` struct is defined in this header but should be regarded as an // implementation detail. `arena_` functions should be used for all manipulation // with the arena. typedef struct Arena Arena; // `arena_init` and `arena_destroy` are called on to initialize and deinitialize // an Arena. void arena_init(Arena *arena); void arena_destroy(Arena *arena); // `arena_alloc` allocates a piece of memory of particular `size`. void *arena_alloc(Arena *arena, size_t size); // Save current allocation position and restore to a previous allocation // position. Saves should be paired with respective restores (the stack // principle). size_t arena_save(Arena *arena); void arena_restore(Arena *arena, size_t pos); // The `GArena` ("growable arena") is an implementation of the approach (3). // When free space is exhausted new bigger chunk is allocated and old objects // are moved to it. Thus pointers returned by this allocator have to be used // carefully. // // Despite this limitation, with careful use (see the below macros), growable // arena essentially is a dynamic array and different parts of it can even // store different types of objects. The utility functions below are public, // but are only used in private parts of the parser and currently undocumented. typedef struct GArena GArena; void garena_init(GArena *arena); void garena_destroy(GArena *arena); void *garena_alloc(GArena *arena, size_t size, size_t alignment); size_t garena_save(GArena *arena); void *garena_restore(GArena *arena, size_t pos); #define move_to_arena(arena, garena, start, type) \ move_to_arena_((arena), (garena), (start), alignof(type)) void *move_to_arena_(Arena *arena, GArena *garena, size_t start, size_t alignment); void *garena_mem(GArena *arena); void *garena_from(GArena *arena, size_t start, size_t alignment); #define garena_cnt(arena, type) \ garena_cnt_from_((arena), 0, sizeof(type)) #define garena_cnt_from(arena, start, type) \ garena_cnt_from_((arena), (start), sizeof(type)) size_t garena_cnt_from_(GArena *arena, size_t start, size_t elem_size); #define garena_push(arena, type) \ ((type *)garena_alloc((arena), sizeof(type), alignof(type))) #define garena_push_value(arena, type, value) \ do { \ type tmp_pushed_ = (value); \ *garena_push((arena), type) = tmp_pushed_; \ } while (0) // PRIVATE IMPLEMENTATION DETAILS typedef struct ArenaChunk ArenaChunk; struct Arena { ArenaChunk *current; size_t prev_size_sum; }; struct ArenaChunk { size_t size; size_t pos; ArenaChunk *prev; // Allocated chunk memory follows. }; struct GArena { unsigned char *mem; size_t pos; size_t capacity; };