From 9f254f0c7b03236be615b1235cf3fc765d6000ea Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Thu, 13 Jul 2023 08:22:18 -0700 Subject: Add mem allocator, remove listpool. --- mem/include/mem.h | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 149 insertions(+) create mode 100644 mem/include/mem.h (limited to 'mem/include/mem.h') diff --git a/mem/include/mem.h b/mem/include/mem.h new file mode 100644 index 0000000..30c24fc --- /dev/null +++ b/mem/include/mem.h @@ -0,0 +1,149 @@ +/* + * Block-based Memory Allocator. + * + * Clients should use the macros to define and use allocators. They make the API + * type-safe. + * + * Like a pool/block-based allocator, this allocator stores data in fixed-size + * blocks. However, this allocator also supports allocation of contiguous chunks + * of a variable number of blocks. + * + * Chunk information is stored in a separate array so that client data is + * contiguous in the main pool of memory and better cached. + */ +#pragma once + +#include +#include +#include +#include + +/// Define a typed memory allocator backed by a statically-allocated array. +#define DEF_MEM(MEM, TYPE, NUM_BLOCKS) \ + typedef struct MEM { \ + Memory mem; \ + Chunk chunks[NUM_BLOCKS]; \ + TYPE blocks[NUM_BLOCKS]; \ + } MEM; + +/// Define a typed memory allocator backed by a dynamically-allocated array. +#define DEF_MEM_DYN(MEM, TYPE) \ + typedef struct MEM { \ + Memory mem; \ + Chunk* chunks; \ + TYPE* blocks; \ + } MEM; + +/// Initialize a statically-backed memory allocator. +#define mem_make(MEM) \ + { \ + assert(MEM); \ + const size_t block_size = sizeof((MEM)->blocks[0]); \ + const size_t num_blocks = sizeof((MEM)->blocks) / block_size; \ + mem_make_( \ + &(MEM)->mem, (MEM)->chunks, (MEM)->blocks, num_blocks, block_size); \ + } + +/// Initialize a dynamically-backed memory allocator. +#define mem_make_dyn(MEM, num_blocks, block_size) \ + mem_make_(&(MEM)->mem, 0, 0, num_blocks, block_size) + +/// Destroy the allocator. +/// +/// If the allocator is dynamically-backed, then this function frees the +/// underlying memory. +#define mem_del(MEM) mem_del_(&(MEM)->mem) + +/// Clear the allocator. +/// +/// This function frees all of the allocator's blocks. The resulting allocator +/// is as if it were newly created. +#define mem_clear(MEM) mem_clear_(&(MEM)->mem) + +/// Allocate a new chunk of N blocks. +/// Return a pointer to the first block of the chunk, or 0 if there is no memory +/// left. +/// New chunks are conveniently zeroed out. +#define mem_alloc(MEM, num_blocks) mem_alloc_(&(MEM)->mem, num_blocks) + +/// Free the chunk. +/// The chunk pointer is conveniently set to 0. +#define mem_free(MEM, CHUNK) mem_free_(&(MEM)->mem, (void**)CHUNK) + +/// Return a pointer to a chunk given the chunk's handle. +/// The chunk must have been allocated. +#define mem_get_chunk(MEM, HANDLE) \ + ((__typeof__((MEM)->blocks[0])*)mem_get_chunk_(&(MEM)->mem, HANDLE)) + +/// Get the handle to the given chunk. +#define mem_get_chunk_handle(MEM, CHUNK_PTR) \ + mem_get_chunk_handle_(&(MEM)->mem, CHUNK_PTR) + +/// Iterate over the used chunks of the allocator. +/// +/// The caller can use 'i' as the index of the current chunk. +/// +/// It is valid to mem_free() the chunk at each step of the iteration. +#define mem_foreach(MEM, ITER, BODY) \ + size_t i = 0; \ + do { \ + if ((MEM)->chunks[i].used) { \ + __typeof__((MEM)->blocks[0])* ITER = &(MEM)->blocks[i]; \ + (void)ITER; \ + BODY; \ + } \ + i = (MEM)->chunks[i].next; \ + } while (i); + +// ----------------------------------------------------------------------------- + +/// Chunk information. +/// +/// Every chunk represents a contiguous array of some number of blocks. The +/// allocator begins as one big unused chunk. +/// +/// Allocation looks for a free chunk large enough to hold to requested number +/// of blocks. If the free chunk is larger than the requested chunk size, then +/// the requested chunk is carved out of the larger block. +/// +/// Deallocation frees the chunk back and merges it with free neighbouring +/// chunks. Two free chunks are never contiguous in memory. +/// +/// 'next' and 'prev' always point to a valid chunk (e.g., 0). Allocation stops +/// looking for free chunks when it loops over. +typedef struct Chunk { + size_t num_blocks; + size_t prev; + size_t next; + bool used; +} Chunk; + +typedef struct Memory { + size_t block_size_bytes; + size_t num_blocks; + size_t next_free_chunk; + bool dynamic; /// True if blocks and chunks are dynamically-allocated. + Chunk* chunks; /// Array of chunk information. + uint8_t* blocks; /// Array of blocks; +} Memory; + +/// Create a memory allocator. +/// +/// 'chunks' and 'blocks' may be user-provided (statically-backed allocator) or +/// null (dynamically-backed allocator). +/// - If null, the allocator malloc()s the memory for them. +/// - If given: +/// - `chunks` must be at least `num_blocks` chunks. +/// - `blocks` must be at least `num_blocks` * `block_size_bytes` bytes. +/// +/// All blocks are zeroed out for convenience. +bool mem_make_( + Memory* mem, Chunk* chunks, void* blocks, size_t num_blocks, + size_t block_size_bytes); + +void mem_del_(Memory*); +void mem_clear_(Memory*); +void* mem_alloc_(Memory*, size_t num_blocks); +void mem_free_(Memory*, void** chunk_ptr); +void* mem_get_chunk_(const Memory*, size_t chunk_handle); +size_t mem_get_chunk_handle_(const Memory*, const void* chunk); -- cgit v1.2.3