commit 59fee5094b35f3615cf87b70557e51183d424245 from: Evan Burkey date: Tue Jul 16 17:49:08 2024 UTC arena allocator commit - 0c97ba45b1ebc1661fa4049ac3924291d51c8d77 commit + 59fee5094b35f3615cf87b70557e51183d424245 blob - 73f69e0958611ac6e00bde95641f6699030ad235 (mode 644) blob + /dev/null --- .idea/.gitignore +++ /dev/null @@ -1,8 +0,0 @@ -# Default ignored files -/shelf/ -/workspace.xml -# Datasource local storage ignored files -/dataSources/ -/dataSources.local.xml -# Editor-based HTTP Client requests -/httpRequests/ blob - 5934ec58a2d5ff5924de91f7dca772e1fc62675d (mode 644) blob + /dev/null --- .idea/.name +++ /dev/null @@ -1 +0,0 @@ -flint \ No newline at end of file blob - a4fac682180aaa43b90d1b53d9edf4d6700523c6 (mode 644) blob + /dev/null --- .idea/editor.xml +++ /dev/null @@ -1,91 +0,0 @@ - - - - - \ No newline at end of file blob - f08604bb65b25149b195f9e9f282f9683a428592 (mode 644) blob + /dev/null --- .idea/libfputs.iml +++ /dev/null @@ -1,2 +0,0 @@ - - \ No newline at end of file blob - 0b76fe5109ed5a73cc38eafcb1e879f8d1979bd4 (mode 644) blob + /dev/null --- .idea/misc.xml +++ /dev/null @@ -1,7 +0,0 @@ - - - - - - \ No newline at end of file blob - 2ff26f1fe0f24e050168c46a6ab5b13ed82604cf (mode 644) blob + /dev/null --- .idea/modules.xml +++ /dev/null @@ -1,8 +0,0 @@ - - - - - - - - \ No newline at end of file blob - 94a25f7f4cb416c083d265558da75d457237d671 (mode 644) blob + /dev/null --- .idea/vcs.xml +++ /dev/null @@ -1,6 +0,0 @@ - - - - - - \ No newline at end of file blob - fa09448298f620bf1b6c9500a71ad2f59b8ff92e blob + 2fd17e00ad933ad40ed49fb4cce439bb2a8c93ac --- CMakeLists.txt +++ CMakeLists.txt @@ -22,6 +22,7 @@ set(SOURCES src/crypto.c src/parsing.c src/network.c + src/memory.c ) if ((${CMAKE_SYSTEM_NAME} STREQUAL "Darwin")) blob - 48f11460e2836bc9a8f2c30eb9f6d0d64586e3f9 blob + 4c5917cf25d727fe6d588ba96f712d839156c428 --- docs/math.md +++ docs/math.md @@ -57,3 +57,11 @@ Works the same as `bresenham()` but uses the `Point` s ```c Point *bresenham_p(Point p1, Point p2, size_t *sz); ``` + +## is_power_of_two + +Returns `1` if `i` is a power of two, otherwise returns `1`. + +```c +int is_power_of_two(int i); +``` blob - /dev/null blob + 95e4709d9d572a60f692544d31c005e94627d3d9 (mode 644) --- /dev/null +++ docs/memory.md @@ -0,0 +1,99 @@ +# memory + +Custom allocators and memory functions + +# Arena Allocator + +A simple arena-style allocator + +## Structs + +### ArenaAllocator + +Represents an arena allocator. `ArenaAllocator` holds its own buffer, but managing its size is left to the user. Like +most structs in `libflint`, it must be malloced first before being passed to `arena_init()`. + +```c +typedef struct { + unsigned char* buf; + size_t buf_sz; + size_t offset_cur; + size_t offset_prev; +} ArenaAllocator; +``` + +## Functions + +### arena_init + +Initializes the `ArenaAllocator`. The struct must first be created by the user using `malloc()`, see the example below. +`buf_sz` is the size of the underlying buffer in bytes. + +```c +void arena_init(ArenaAllocator *allocator, size_t buf_sz); + +/* Usage */ +ArenaAllocator *a = malloc(sizeof(ArenaAllocator)); +arena_init(a, 1024); +``` + +### arena_free +Frees `allocator` and its underlying buffer. Users should set `allocator` to `NULL` after calling `arena_free()`. +```c +void arena_free(ArenaAllocator *allocator); + +/* Usage */ +arena_free(allocator); +allocator = NULL; +``` + +### arena_clear + +Resets the offset markers of the arena to `0`, but does not wipe the underlying buffer. Technically, any assigned pointers +will still work and + +```c +void arena_clear(ArenaAllocator *allocator); +``` + + +### *arena_malloc + +Request memory of `size` bytes in length from the arena. Returns `NULL` if the assignment failed. + +```c +void *arena_malloc(ArenaAllocator* allocator, size_t size); +``` + +### arena_resize_buf + +Reallocates the underlying buffer in the arena to `new_sz`. You can grow or shrink the arena using this function. Any +pointers allocated out of the arena are invalid after using this function. + +```c +void arena_resize_buf(ArenaAllocator *allocator, size_t new_sz); +``` + +### *arena_resize + +Resize an allocated pointer from the arena. See the example below for a simple use case + +```c +void *arena_resize(ArenaAllocator *allocator, void *mem, size_t old_sz, size_t new_sz); + +/* Usage */ +int *i = arena_malloc(a, sizeof(int)); +*i = 1; +long *l = arena_resize(a, i1, sizeof(int), sizeof(long)); +assert(*l == 1); +``` + +## Macros + +### arena_sz + +Convenience macro for getting the size of the arena's buffer + +```c +#define arena_sz(a) (a)->buf_sz +``` \ No newline at end of file blob - 34542bb9f0dac7c2beda6c53b8a0cb8418c43f41 blob + 09f75a4eebbfe103cfd27d9f4b491e10830143f8 --- include/lfmath.h +++ include/lfmath.h @@ -1,6 +1,8 @@ #ifndef LIBFLINT_H_MATH #define LIBFLINT_H_MATH +#include + #include "lfutility.h" int max_int(int a, int b); @@ -11,6 +13,8 @@ int clamp_int(int i, int low, int high); int binstr_to_int(const char *s); +int is_power_of_two(int i); + Point *bresenham(int x0, int y0, int x1, int y1, size_t *sz); Point *bresenham_p(Point p1, Point p2, size_t *sz); blob - /dev/null blob + 0aac0c339051fca83211429572341b6655965bd0 (mode 644) --- /dev/null +++ include/lfmemory.h @@ -0,0 +1,20 @@ +#ifndef LIBFLINT_H_MEMORY +#define LIBFLINT_H_MEMORY + +#include + +typedef struct { + unsigned char* buf; + size_t buf_sz; + size_t offset_cur; + size_t offset_prev; +} ArenaAllocator; + +void arena_init(ArenaAllocator *allocator, size_t buf_sz); +void arena_free(ArenaAllocator *allocator); +void *arena_malloc(ArenaAllocator* allocator, size_t size); +void arena_resize_buf(ArenaAllocator *allocator, size_t new_sz); +void *arena_resize(ArenaAllocator *allocator, void *mem, size_t old_sz, size_t new_sz); +void arena_clear(ArenaAllocator *allocator); + +#endif // LIBFLINT_H_MEMORY blob - 53efd3318ae2e30aa15871601735e741960d3dd0 blob + 14e275b908de1b802c8ebf3e5d73acc95d2f19aa --- src/math.c +++ src/math.c @@ -77,3 +77,6 @@ Point *bresenham_p(Point p1, Point p2, size_t *sz) { return bresenham(p1.x, p1.y, p2.x, p2.y, sz); } +int is_power_of_two(int i) { + return (i & (i - 1)) == 0; +} blob - /dev/null blob + f49db3be38495fbe7d6d41c118aaf54002386323 (mode 644) --- /dev/null +++ src/memory.c @@ -0,0 +1,109 @@ +#include +#include +#include +#include + +#include "lfmemory.h" + +#define arena_sz(a) (a)->buf_sz + +void arena_init(ArenaAllocator *allocator, size_t buf_sz) { + if (allocator == NULL) { + return; + } + + allocator->buf = malloc(sizeof(unsigned char) * buf_sz); + allocator->buf_sz = buf_sz; + allocator->offset_cur = 0; + allocator->offset_prev = 0; +} + +void arena_free(ArenaAllocator *allocator) { + free(allocator->buf); + free(allocator); +} + +void arena_clear(ArenaAllocator *allocator) { + allocator->offset_cur = 0; + allocator->offset_prev = 0; +} + +static uintptr_t align_forward(uintptr_t ptr, size_t align) { + uintptr_t p, a, m; + if (!is_power_of_two(align)) { + // TODO: Error + } + p = ptr; + a = (uintptr_t)align; + m = p & (a - 1); + + if (m != 0) { + p += a - m; + } + return p; +} + +static void *arena_malloc_align(ArenaAllocator *allocator, size_t size, size_t align) { + uintptr_t cur_ptr = (uintptr_t)allocator->buf + (uintptr_t)allocator->offset_cur; + + // Push forward to align, then change to relative offset + uintptr_t offset = align_forward(cur_ptr, align); + offset -= (uintptr_t)allocator->buf; + + if (offset + size <= allocator->buf_sz) { + void *ptr = &allocator->buf[offset]; + allocator->offset_prev = offset; + allocator->offset_cur = offset + size; + memset(ptr, 0, size); + return ptr; + } + + // Arena is full + return NULL; +} + +static void *arena_resize_align(ArenaAllocator *allocator, void *mem, size_t old_sz, size_t new_sz, size_t align) { + unsigned char *old_mem = (unsigned char *)mem; + if (!is_power_of_two(align)) { + // TODO: Error handling + } + + if (old_mem == NULL || old_sz == 0) { + return arena_malloc_align(allocator, new_sz, align); + } + + if (allocator->buf <= mem && mem < allocator->buf + allocator->buf_sz) { + if (allocator->buf + allocator->offset_prev == old_mem) { + allocator->offset_cur = allocator->offset_prev + new_sz; + if (new_sz > old_sz) { + // Zero out memory + memset(&allocator->buf[allocator->offset_cur], 0, new_sz - old_sz); + } + return old_mem; + } + + void *new_mem = arena_malloc_align(allocator, new_sz, align); + size_t copy_size = old_sz < new_sz ? old_sz : new_sz; + memmove(new_mem, old_mem, copy_size); + return new_mem; + } + + return NULL; +} + +void arena_resize_buf(ArenaAllocator *allocator, size_t new_sz) { + allocator->buf = realloc(allocator->buf, sizeof(unsigned char) * new_sz); +} + +#ifndef DEFAULT_ALIGNMENT +#define DEFAULT_ALIGNMENT (2*sizeof(void*)) +#endif // DEFAULT_ALIGNMENT + +void *arena_malloc(ArenaAllocator *allocator, size_t size) { + return arena_malloc_align(allocator, size, DEFAULT_ALIGNMENT); +} + +void *arena_resize(ArenaAllocator *allocator, void *mem, size_t old_sz, size_t new_sz) { + return arena_resize_align(allocator, mem, old_sz, new_sz, DEFAULT_ALIGNMENT); +} + blob - 663631f37f739d19158a37db96eaed3a4b6c30db blob + 725835799545adfb64abdf73c9c56d2acf7de59f --- tests/tests.c +++ tests/tests.c @@ -16,6 +16,7 @@ #include "lfcrypto.h" #include "lfparsing.h" #include "lfinput.h" +#include "lfmemory.h" #if defined(__APPLE__) || defined(__MACH__) #include "lfmacos.h" @@ -468,6 +469,30 @@ void test_macos() { } #endif +void test_memory() { + printf("\n--- MEMORY TEST ---\n"); + ArenaAllocator *a = malloc(sizeof(ArenaAllocator)); + arena_init(a, 1024); + + int *i1 = arena_malloc(a, sizeof(int)); + int *i2 = arena_malloc(a, sizeof(int)); + + *i1 = 1; + *i2 = 2; + + assert(i1 < i2); + assert(*i1 < *i2); + + long *l = arena_resize(a, i1, sizeof(int), sizeof(long)); + assert(*l == 1); + + unsigned char *c = arena_resize(a, i2, sizeof(int), sizeof(unsigned char)); + assert(*c == 2); + + arena_free(a); + printf("Passes all memory tests\n"); +} + int main() { test_ll(); test_set(); @@ -479,6 +504,7 @@ int main() { test_crypto(); test_parsing(); test_network(); + test_memory(); #if defined(__APPLE__) || defined(__MACH__) test_macos();