From 5b1b3bec3f25ea5fc1f48c269f300c4211a1bac7 Mon Sep 17 00:00:00 2001 From: Jon Santmyer Date: Fri, 19 Apr 2024 16:11:24 -0400 Subject: initial commit; mostly documented. --- malloc.h | 176 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 176 insertions(+) create mode 100644 malloc.h (limited to 'malloc.h') diff --git a/malloc.h b/malloc.h new file mode 100644 index 0000000..b5540d1 --- /dev/null +++ b/malloc.h @@ -0,0 +1,176 @@ +#ifndef _MALLOC_H +#define _MALLOC_H 1 + +/* A bucket-based malloc implementation for 2^n sized objects. + * Allocates memory at pbrk for use in dynamic allocations, called "objects". + * Each object is pre-empted by metadata, which stores a checksum, the width, + * and a bit to mark it as taken. + * + * Each alloc-able region is pre-empted by a "bucket", which stores metadata + * about the bucket's state, the width, the first free object, and the next + * bucket in the chain. + * + * Buckets are allocated when needed. The width of the new bucket is determined + * by the object that needs the bucket. + * Buckets are always page aligned, and the size is a multiple of a page width. + * + * Dependencies: + * stddef.h + * stdint.h + * errno.h + * assert.h + * assert + * string.h + * memset + * memcpy + * unistd.h + * sbrk + * brk + * + * with MALLOC_DBG: + * stdio.h + * printf*/ + +#include +#include + +#define DBGPRINT(...) +#ifdef MALLOC_DBG +#include +#undef DBGPRINT +#define DBGPRINT(...) printf(__VA_ARGS__) +#endif + +/* Bucket checksum is a 64-bit value containing the string "BUCKET\0\0"*/ +#define OBJ_CHECKSUM \ + (((uintmax_t)'B') | \ + ((uintmax_t)'U' << 8) | \ + ((uintmax_t)'C' << 16) | \ + ((uintmax_t)'K' << 24) | \ + ((uintmax_t)'E' << 32) | \ + ((uintmax_t)'T' << 40)) + +/* For an object to be valid, the object must have the correct checksum.*/ +#define OBJ_VALID(obj) (obj->checksum == OBJ_CHECKSUM) + +/* Object width is assumed to be a multiple of two. The first bit is reserved + * for the taken flag.*/ +#define OBJ_WIDTH(obj) (obj->size_taken & ~1) +#define OBJ_TAKEN(obj) (obj->size_taken & 1) + +/* Gets the object struct after this object. + * Since objects are allocated in-place, we can get the next object using + * the object's size and it's pointer to the start of data. + * + * The same is true for getting the metadata for any given data pointer. + * We take the pointer and subtract the size of the object struct from it + * since the metadata is behind the actual data.*/ +#define OBJ_AFTER(obj) \ + ((bucket_obj_t*)(((uintptr_t)obj->data) + OBJ_WIDTH(obj))) +#define OBJ_FROM_PTR(ptr) ((bucket_obj_t*)((uintptr_t)ptr - sizeof(bucket_obj_t))); + +typedef struct bucket_obj +{ + uintmax_t checksum; + size_t size_taken; + char data[]; +} bucket_obj_t; + +#define LOG2(n) ((31) - __builtin_clz(n)) +/* Buckets are always aligned to the page boundary for cache friendliness.*/ +#define BUCKET_ALIGN (4096) +/* Buckets should always be a multiple of the page width, expanding with the + * initial object size.*/ +#define BUCKET_WIDTH(w) \ + (1UL << (12 + (w < BUCKET_ALIGN ? 0 : LOG2(w + 1) - 11))) + +/* Bucket metadata is stored behind the object metadata.*/ +typedef struct bucket +{ + size_t checksum; + struct bucket *next; + + uintptr_t limit; + bucket_obj_t *firstfree; /* Helpful for fast object allocations.*/ + char objs[]; +} bucket_t; + +/* The overall size of an object (data + metadata) should be 2*metadata.*/ +#define OBJ_SIZE_MIN (sizeof(bucket_obj_t)) +/* Data width is always a power of two.*/ +#define REALW(n) \ + (n < OBJ_SIZE_MIN ? OBJ_SIZE_MIN : (1UL << (LOG2(n + 1)))) + +typedef struct heap_cache +{ + bucket_t *head; + bucket_t *tail; +} heap_cache_t; + +/**Given the heap cache and an object, find the bucket to which the object + * belongs. + * Since buckets are always page aligned, we can check each page boundary + * for the checksum until we find it, then check the limit. + * Since we also know the first bucket in the cache, we can also check if the + * passed object is invalid and return NULL. + * @param heap cache. + * @param obj to find the bucket for. + * @return bucket owning obj, or NULL if obj is invalid.*/ +bucket_t *__bucket_from_obj(heap_cache_t *heap, bucket_obj_t *obj); + +/**Allocate w bytes into the given heap. + * If w == 0, returns NULL. + * If w is not a power of 2, rounds to the nearest pow2. + * If the heap is corrupted, assert fail. + * If the program is OOM, errno is assumed to be set and returns (void*)-1 + * @param heap cache. + * @param w n-bytes to allocate. + * @return pointer to allocated memory.*/ +void* __malloc_impl(heap_cache_t *heap, size_t w); + +/**Allocate a contiguous array of nmemb members each w wide. + * Newly allocated memory is zero'd. + * If w == 0 || nmemb == 0, returns NULL + * If w is not a power of 2, rounds to nearest pow2 + * If the heap is corrupted, assert fail + * If the program is OON, ernno is assumed to be set and returns (void*)-1 + * @param heap cache. + * @param nmemb number of members. + * @param w number of bytes per member. + * @return pointer to allocated memory.*/ +void* __calloc_impl(heap_cache_t *heap, size_t nmemb, size_t w); + +/**Resize the given allocated memory region to fit w. + * If w is less than the original width, does nothing. + * If w == 0, frees p + * If the heap is corrupted, assert fail. + * If the heap is OOM, errno is assumed to be set and returns (void*)-1 + * @param heap cache. + * @param p pointer to reallocate. + * @param w width to fit p to. + * @return pointer to memory allocated to fit w.*/ +void* __realloc_impl(heap_cache_t *heap, void *p, size_t w); + +/**Resize the given allocated contiguous array to fit nmemb members of w width + * objects. + * Zeros the new members excluding already existing data. + * If w * nmemb is less than the original width, does nothing. + * If w == 0 || nmemb == 0, frees p + * If the heap is corrupted, assert fail. + * If the heap is OOM, errno is assumed to be set and returns (void*)-1 + * @param heap cache. + * @param p pointer to reallocate. + * @param nmemb number of members. + * @param w width to fit p to. + * @return pointer to memory allocated to fit w * nmemb.*/ +void* __reallocarray_impl(heap_cache_t *heap, void *p, size_t nmemb, size_t w); + +/**Free a pointer in the given heap. + * If p == NULL, do nothing. + * If p does not fall in the range of heap, assert fail. + * If the heap is corrupted, assert fail. + * @param heap cache. + * @param p pointer to free.*/ +void __free_impl(heap_cache_t *heap, void *p); + +#endif -- cgit v1.2.1