Line data Source code
1 : // wok_arena -- bump allocator implementation. See wok_arena.h for the
2 : // contract: one growable list of malloc'd blocks, no frees of individual
3 : // allocations, teardown frees the whole list at once. The allocation fast
4 : // path is inline in the header; this file owns creation, growth and
5 : // teardown.
6 :
7 : #include "wok_arena.h"
8 :
9 : #include <stdbool.h>
10 : #include <stdio.h>
11 : #include <stdlib.h>
12 : #include <string.h>
13 :
14 : #define WOK_ARENA_DEFAULT_BLOCK ((usize)(64u * 1024u))
15 : #define WOK_ARENA_MAX_GROWTH ((usize)(8u * 1024u * 1024u))
16 :
17 0 : [[noreturn]] static void wok_arena_oom(void) {
18 0 : (void)fprintf(stderr, "wok: out of memory allocating arena block\n");
19 0 : abort();
20 : }
21 :
22 80513 : static WokArenaBlock *wok_arena_new_block(usize capacity) {
23 80513 : WokArenaBlock *blk = (WokArenaBlock *)malloc(sizeof(WokArenaBlock) + capacity);
24 80513 : if (blk == nullptr) wok_arena_oom();
25 80513 : blk->next = nullptr;
26 80513 : blk->capacity = capacity;
27 80513 : blk->used = 0;
28 80513 : return blk;
29 : }
30 :
31 1545 : static uptr wok_align_up(uptr value, usize align) {
32 1545 : uptr a = (uptr)align;
33 1545 : return (value + a - (uptr)1) & ~(a - (uptr)1);
34 : }
35 :
36 78968 : WokArena *wok_arena_new(usize first_block) {
37 78968 : usize cap = first_block != 0 ? first_block : WOK_ARENA_DEFAULT_BLOCK;
38 :
39 78968 : WokArena *a = (WokArena *)malloc(sizeof(WokArena));
40 78968 : if (a == nullptr) wok_arena_oom();
41 :
42 78968 : a->head = wok_arena_new_block(cap);
43 78968 : a->block_count = 1;
44 78968 : a->bytes_out = 0;
45 78968 : a->growth_capacity = cap;
46 78968 : return a;
47 : }
48 :
49 78968 : void wok_arena_free(WokArena *a) {
50 78968 : if (a == nullptr) return;
51 :
52 78968 : WokArenaBlock *blk = a->head;
53 159481 : while (blk != nullptr) {
54 80513 : WokArenaBlock *next = blk->next;
55 80513 : free(blk);
56 80513 : blk = next;
57 : }
58 78968 : free(a);
59 : }
60 :
61 1545 : void *wok_arena_grow(WokArena *a, usize size, usize align) {
62 1545 : usize footprint = size == 0 ? (usize)1 : size;
63 :
64 : // `needed` is a safe upper bound on what a fresh block must hold, since a
65 : // brand new block's payload is already max-aligned and align worst-case
66 : // slop is bounded by `align` itself.
67 1545 : usize needed = footprint + align;
68 1545 : bool dedicated = needed > WOK_ARENA_MAX_GROWTH;
69 1545 : usize new_cap;
70 1545 : if (dedicated) {
71 : new_cap = needed;
72 : } else {
73 1545 : usize doubled = a->growth_capacity > WOK_ARENA_MAX_GROWTH / 2
74 : ? WOK_ARENA_MAX_GROWTH
75 1545 : : a->growth_capacity * 2;
76 1545 : new_cap = doubled > needed ? doubled : needed;
77 1545 : if (new_cap > WOK_ARENA_MAX_GROWTH) new_cap = WOK_ARENA_MAX_GROWTH;
78 : }
79 :
80 1545 : WokArenaBlock *nb = wok_arena_new_block(new_cap);
81 1545 : nb->next = a->head;
82 1545 : a->head = nb;
83 1545 : a->block_count += 1;
84 1545 : if (!dedicated) a->growth_capacity = new_cap;
85 :
86 1545 : uptr nbase = (uptr)nb->payload;
87 1545 : uptr naligned = wok_align_up(nbase, align);
88 1545 : usize npad = (usize)(naligned - nbase);
89 1545 : nb->used = npad + footprint;
90 1545 : a->bytes_out += size;
91 1545 : return (void *)naligned;
92 : }
93 :
94 107024 : char *wok_arena_copy(WokArena *a, const char *src, usize n) {
95 107024 : char *dst = (char *)wok_arena_alloc(a, n + 1, alignof(char));
96 107024 : memcpy(dst, src, n);
97 107024 : dst[n] = '\0';
98 107024 : return dst;
99 : }
100 :
101 0 : usize wok_arena_bytes(const WokArena *a) { return a->bytes_out; }
102 :
103 0 : usize wok_arena_blocks(const WokArena *a) { return a->block_count; }
|
