1 // Copyright 2022 Alexey Kutepov <reximkut@gmail.com> 2 3 // Permission is hereby granted, free of charge, to any person obtaining 4 // a copy of this software and associated documentation files (the 5 // "Software"), to deal in the Software without restriction, including 6 // without limitation the rights to use, copy, modify, merge, publish, 7 // distribute, sublicense, and/or sell copies of the Software, and to 8 // permit persons to whom the Software is furnished to do so, subject to 9 // the following conditions: 10 11 // The above copyright notice and this permission notice shall be 12 // included in all copies or substantial portions of the Software. 13 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 15 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 16 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 17 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 18 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 19 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 20 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 21 22 #ifndef ARENA_H_ 23 #define ARENA_H_ 24 25 #include <stddef.h> 26 #include <stdint.h> 27 28 #ifndef ARENA_ASSERT 29 #include <assert.h> 30 #define ARENA_ASSERT assert 31 #endif 32 33 #define ARENA_BACKEND_LIBC_MALLOC 0 34 #define ARENA_BACKEND_LINUX_MMAP 1 35 #define ARENA_BACKEND_WIN32_VIRTUALALLOC 2 36 #define ARENA_BACKEND_WASM_HEAPBASE 3 37 38 #ifndef ARENA_BACKEND 39 #define ARENA_BACKEND ARENA_BACKEND_LIBC_MALLOC 40 #endif // ARENA_BACKEND 41 42 typedef struct Region Region; 43 44 struct Region { 45 Region *next; 46 size_t count; 47 size_t capacity; 48 uintptr_t data[]; 49 }; 50 51 typedef struct { 52 Region *begin, *end; 53 } Arena; 54 55 #define REGION_DEFAULT_CAPACITY (8*1024) 56 57 Region *new_region(size_t capacity); 58 void free_region(Region *r); 59 60 // TODO: snapshot/rewind capability for the arena 61 // - Snapshot should be combination of a->end and a->end->count. 62 // - Rewinding should be restoring a->end and a->end->count from the snapshot and 63 // setting count-s of all the Region-s after the remembered a->end to 0. 64 void *arena_alloc(Arena *a, size_t size_bytes); 65 void *arena_realloc(Arena *a, void *oldptr, size_t oldsz, size_t newsz); 66 67 void arena_reset(Arena *a); 68 void arena_free(Arena *a); 69 70 #endif // ARENA_H_ 71 72 #ifdef ARENA_IMPLEMENTATION 73 74 #if ARENA_BACKEND == ARENA_BACKEND_LIBC_MALLOC 75 #include <stdlib.h> 76 77 // TODO: instead of accepting specific capacity new_region() should accept the size of the object we want to fit into the region 78 // It should be up to new_region() to decide the actual capacity to allocate 79 Region *new_region(size_t capacity) 80 { 81 size_t size_bytes = sizeof(Region) + sizeof(uintptr_t)*capacity; 82 // TODO: it would be nice if we could guarantee that the regions are allocated by ARENA_BACKEND_LIBC_MALLOC are page aligned 83 Region *r = malloc(size_bytes); 84 ARENA_ASSERT(r); 85 r->next = NULL; 86 r->count = 0; 87 r->capacity = capacity; 88 return r; 89 } 90 91 void free_region(Region *r) 92 { 93 free(r); 94 } 95 #elif ARENA_BACKEND == ARENA_BACKEND_LINUX_MMAP 96 # error "TODO: Linux mmap backend is not implemented yet" 97 #elif ARENA_BACKEND == ARENA_BACKEND_WIN32_VIRTUALALLOC 98 # error "TODO: Win32 VirtualAlloc backend is not implemented yet" 99 #elif ARENA_BACKEND == ARENA_BACKEND_WASM_HEAPBASE 100 # error "TODO: WASM __heap_base backend is not implemented yet" 101 #else 102 # error "Unknown Arena backend" 103 #endif 104 105 // TODO: add debug statistic collection mode for arena 106 // Should collect things like: 107 // - How many times new_region was called 108 // - How many times existing region was skipped 109 // - How many times allocation exceeded REGION_DEFAULT_CAPACITY 110 111 void *arena_alloc(Arena *a, size_t size_bytes) 112 { 113 size_t size = (size_bytes + sizeof(uintptr_t) - 1)/sizeof(uintptr_t); 114 115 if (a->end == NULL) { 116 ARENA_ASSERT(a->begin == NULL); 117 size_t capacity = REGION_DEFAULT_CAPACITY; 118 if (capacity < size) capacity = size; 119 a->end = new_region(capacity); 120 a->begin = a->end; 121 } 122 123 while (a->end->count + size > a->end->capacity && a->end->next != NULL) { 124 a->end = a->end->next; 125 } 126 127 if (a->end->count + size > a->end->capacity) { 128 ARENA_ASSERT(a->end->next == NULL); 129 size_t capacity = REGION_DEFAULT_CAPACITY; 130 if (capacity < size) capacity = size; 131 a->end->next = new_region(capacity); 132 a->end = a->end->next; 133 } 134 135 void *result = &a->end->data[a->end->count]; 136 a->end->count += size; 137 return result; 138 } 139 140 void *arena_realloc(Arena *a, void *oldptr, size_t oldsz, size_t newsz) 141 { 142 if (newsz <= oldsz) return oldptr; 143 void *newptr = arena_alloc(a, newsz); 144 char *newptr_char = newptr; 145 char *oldptr_char = oldptr; 146 for (size_t i = 0; i < oldsz; ++i) { 147 newptr_char[i] = oldptr_char[i]; 148 } 149 return newptr; 150 } 151 152 void arena_reset(Arena *a) 153 { 154 for (Region *r = a->begin; r != NULL; r = r->next) { 155 r->count = 0; 156 } 157 158 a->end = a->begin; 159 } 160 161 void arena_free(Arena *a) 162 { 163 Region *r = a->begin; 164 while (r) { 165 Region *r0 = r; 166 r = r->next; 167 free_region(r0); 168 } 169 a->begin = NULL; 170 a->end = NULL; 171 } 172 173 #endif // ARENA_IMPLEMENTATION
