From ace65b453151845bc361f21f3e5b651c35f9f126 Mon Sep 17 00:00:00 2001 From: Jon Santmyer Date: Wed, 22 May 2024 13:00:41 -0400 Subject: massive refactor for mp and organization --- memory/alloc/malloc.c | 206 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 206 insertions(+) create mode 100644 memory/alloc/malloc.c (limited to 'memory/alloc/malloc.c') diff --git a/memory/alloc/malloc.c b/memory/alloc/malloc.c new file mode 100644 index 0000000..ba1e2d2 --- /dev/null +++ b/memory/alloc/malloc.c @@ -0,0 +1,206 @@ +/* + * Copyright (c) Jon Santmyer. + * This source file is released under the LGPL Version 3 as detailed in + * the LICENSE file provided in the following repository: + * https://git.jonsantmyer.com/heap/ + * */ + +#include "malloc.h" +#include "assert.h" +#include "jove.h" +#include "memory/bump.h" + +/**Allocate memory for a new bucket in the heap. + * Automatically aligns new memory to BUCKET_ALIGN. + * Instantiates a new free object spanning the entire bucket. + * Then adds the new bucket to the heap cache. + * If sbrk encounters an error, pass through errno and return NULL. + * @param cache to allocate for. + * @param objw width of the object the bucket is assumed to hold. + * @return bucket created by this function.*/ +bucket_t* +s_bucket_new(heap_cache_t *cache, size_t objw) +{ + DBGPRINT("malloc: ask for new bucket for cache %p with objw %i\n", cache, objw); + size_t bucketw = BUCKET_WIDTH(objw); + /* Assuming sbrk allocates memory for after the program break, make sure + * we allocate enough for the requested bucket width and any adjustments + * to ensure page alignment.*/ + uintptr_t pbrk = (uintptr_t)bump_where(); + uintptr_t brko = pbrk % BUCKET_ALIGN; + uintptr_t nbrk = (uintptr_t)bump_alloc(bucketw + brko); + + bucket_t *bucket = (bucket_t*)(nbrk + brko); + DBGPRINT("malloc: got new bucket at %p\n", bucket); + + *bucket = (bucket_t){ + .checksum = OBJ_CHECKSUM, + .next = NULL, + .limit = (uintptr_t)bucket + bucketw, + }; + /* Create a new object spanning the entire bucket. This new object will + * be the first free.*/ + bucket_obj_t *obj0 = (bucket_obj_t*)bucket->objs; + *obj0 = (bucket_obj_t) { + .checksum = OBJ_CHECKSUM, + .size_taken = bucketw - sizeof(bucket_t) - sizeof(bucket_obj_t) + }; + bucket->firstfree = obj0; + + /* If the cache is empty, this will be the first and last bucket.*/ + if(cache->head == NULL) { + cache->head = cache->tail = bucket; + return bucket; + } + /* Add the bucket to the heap cache bucket list.*/ + cache->tail->next = bucket; + cache->tail = bucket; + return bucket; +} + +/**Given an existing object and a size, split the object so that the original + * has size w. + * If the object is smaller than or is already the correct size, do nothing. + * Space after the split is allocated to a new free object after the resized + * original. + * If the original == bucket->firstfree, the new object is assigned to + * that variable. + * If the heap is corrupted, assert fail. + * @param bucket object's parent bucket. + * @param parent object to split. + * @param w requested size for original object. */ +void +s_obj_take_split(bucket_t *bucket, bucket_obj_t *parent, size_t w) +{ + DBGPRINT("malloc: requesting to split object %p (last %p) for size %i (was %i)\n", + bucket, parent, w, parent->size_taken); + + /* Assert fail on corrupted heap.*/ + assert(OBJ_VALID(bucket)); + assert(OBJ_VALID(parent)); + assert(w >= OBJ_SIZE_MIN); + + size_t objw = OBJ_WIDTH(parent); + if(w == objw) { /* Obj is already correct size, take and ignore.*/ + if(bucket->firstfree == parent) + bucket->firstfree = OBJ_AFTER(parent); + /* Ensure that firstfree does not exceed bucket limits.*/ + if((uintptr_t)bucket->firstfree > bucket->limit) + bucket->firstfree = NULL; + DBGPRINT("malloc: Object is already right size, ignoring\n"); + + /* Mark object as taken.*/ + parent->size_taken = w | 1; + return; + } + /* New object created by split will be the original width minus the new + * width and metadata size. + * + * from: + * [meta| --------objw-------- ] + * + * to: + * [meta| -w- ][meta| -afterw- ]*/ + size_t afterw = objw - sizeof(bucket_obj_t) - w; + + parent->size_taken = w | 1; + bucket_obj_t *obj = OBJ_AFTER(parent); + DBGPRINT("malloc: New object created inplace at %p with size %i\n", + obj, afterw); + + /* In-place allocate after obj.*/ + *obj = (bucket_obj_t){ + .checksum = OBJ_CHECKSUM, + .size_taken = afterw, + }; + if(bucket->firstfree == parent) + bucket->firstfree = obj; +} + +/* Look for a free object in the given bucket that closest matches size w. + * Uses bucket->firstfree as a starting point to save checks against taken + * objects. + * If the heap is corrupted, assert fail. + * If there are no good objects in this bucket, return NULL. + * @param bucket to search in. + * @param w to search for. + * @return best-fitting object or NULL if none are found. + * */ +bucket_obj_t* +s_obj_bestfit(bucket_t *bucket, size_t w) +{ + assert(bucket != NULL); + assert(OBJ_VALID(bucket)); + + bucket_obj_t *best = NULL; + bucket_obj_t *obj = bucket->firstfree; + if(obj == NULL) return NULL; + for(; (uintptr_t)obj < bucket->limit; obj = OBJ_AFTER(obj)) + { + assert(OBJ_VALID(obj)); + if(OBJ_TAKEN(obj)) continue; + size_t objw = OBJ_WIDTH(obj); + if(objw < w) continue; + if(best == NULL) best = obj; + + size_t bestw = OBJ_WIDTH(best); + if(objw < bestw) best = obj; + } + + DBGPRINT("malloc: Bucket %p returns best fit at %p for size %i ", + bucket, best, w); + if(best != NULL) { DBGPRINT("(size %i)\n", best->size_taken); } + else { DBGPRINT("(is NULL)\n"); } + + return best; +} + +/**Searching through the entire heap, or until an object is found, find a + * free object that best fits the requested width and place the resulting + * bucket in the passed pointer. + * If the heap is corrupted, assert fail. + * If no object is found in any of the buckets, return NULL. + * @param cache heap to search through. + * @param w object width to search for. + * @param bucket pointer to bucket pointer owning the returned bucket. + * If no object is found, variable is untouched. + * @return object that fits the given width.*/ +bucket_obj_t* +s_bucket_bestfit(heap_cache_t *cache, size_t w, bucket_t **bucket) +{ + *bucket = cache->head; + for(; *bucket != NULL; *bucket = (*bucket)->next) + { + bucket_obj_t *obj = s_obj_bestfit(*bucket, w); + /* Object is already found, don't waste cycles searching through + * the entire heap.*/ + if(obj != NULL) return obj; + } + return NULL; +} + +void* +__malloc_impl(heap_cache_t *cache, size_t w) +{ + assert(cache != NULL); + /* w == 0 is ub, just return NULL.*/ + if(w == 0) return NULL; + /* Ensure that w is valid.*/ + w = REALW(w); + + DBGPRINT("malloc: Asking to malloc for size %i\n", w); + + bucket_t *bucket = NULL; + bucket_obj_t *obj = s_bucket_bestfit(cache, w, &bucket); + if(obj == NULL) { + /* No bucket in the heap has an appropriate space. + * Allocate a new bucket and take the first object. + * If the bucket allocation fails, return -1 and pass errno through.*/ + bucket = s_bucket_new(cache, w); + if(bucket == NULL) return (void*)(-1); + obj = (bucket_obj_t*)bucket->objs; + } + /* Split the bucket to make the object bestfit.*/ + s_obj_take_split(bucket, obj, w); + return obj->data; +} -- cgit v1.2.1