Newer
Older
// Arena allocation
// Michal Vlasák, FIT CTU, 2023
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#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;
};