/*
* 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 <stdbool.h>
#include <unistd.h>
#include <errno.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)sbrk(0);
uintptr_t brko = pbrk % BUCKET_ALIGN;
uintptr_t nbrk = (uintptr_t)sbrk(bucketw + brko);
if(errno != 0) return NULL; /* Fail on errno. */
bucket_t *bucket = (bucket_t*)(nbrk + brko);
DBGPRINT("malloc: got new bucket at %p\n", bucket);
*bucket = (bucket_t){
.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;
}
