summaryrefslogblamecommitdiffstats
path: root/heap.c
blob: dc739fdf48390eeb790f9f5c7a05bd8dff49dc3c (plain) (tree)



















































































































































































































































































                                                                                
/*
 * heap.c
 * Copyright (c) 2021 Jon Santmyer <jon@jonsantmyer.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/**
 * File              : heap.c
 * Author            : Jon Santmyer <jon@jonsantmyer.com>
 * Date              : 10.12.2021
 */

#include "heap.h"
#include <string.h>

int
heap_create(struct heap *heap, uintptr_t at, size_t len)
{
    struct crate *firstcrate = NULL;
    struct bucket *cratebucket = NULL;
    struct bucket *freebucket = NULL;

    memset(heap, 0, sizeof(struct heap));
    
    heap->start = at;
    heap->size = len;

    /*check if heap can fit crate*/
    if(len < HEAP_CRATE_SIZE) return -1;

    /*Populate first crate*/
    heap->crates_tail = heap->crates_head = firstcrate = (struct crate*)at;
    cratebucket = &firstcrate->buckets[0];

    heap->used = HEAP_CRATE_SIZE;
    memset(firstcrate, 0, HEAP_CRATE_SIZE);

    /*Allocate first bucket for crate*/
    heap->buckets_tail = heap->buckets_head = cratebucket;
    cratebucket->address = (uintptr_t)firstcrate;
    cratebucket->sizetaken = HEAP_CRATE_SIZE | 1;

    /*Set buckets after 1 to link to free list*/
    for(size_t i = 2; i < HEAP_CRATE_BUCKETS; i++) {
        struct bucket *prev = &firstcrate->buckets[i - 1];
        struct bucket *bucket = &firstcrate->buckets[i];

        prev->next = bucket;
        bucket->prev = prev;
    }
    heap->buckets_unused_tail = &firstcrate->buckets[1];

    return 0;
}

struct bucket*
__heap_bucket_findbest(struct heap *heap, size_t size)
{
    struct bucket *best = NULL;
    for(struct bucket *bucket = heap->buckets_tail; 
            bucket != NULL;
            bucket = bucket->next)
    {
        if(HEAP_BUCKET_TAKEN(bucket)) continue;
        if(bucket->sizetaken < size) continue;
        if(best == NULL) best = bucket;
        if(best->sizetaken > bucket->sizetaken) best = bucket;
    }

    return best;
}

struct bucket*
__heap_crate_create(struct heap *heap)
{
    size_t remaining = heap->size - heap->used;
    struct bucket *head = heap->buckets_head;
    struct bucket *crate_bucket = NULL;
    struct crate *crate = NULL;

    /*Check for room in heap*/
    if(remaining < HEAP_CRATE_SIZE) {
        return NULL;
    }

    /*Take crate bucket from crate head*/
    crate_bucket = &heap->crates_head->reserved;

    /*Populate crate bucket*/
    crate_bucket->address = heap->start + heap->used;
    crate_bucket->sizetaken = HEAP_CRATE_SIZE | 1;
    crate_bucket->prev = heap->buckets_head;
    heap->buckets_head = crate_bucket;

    /*Populate crate, linking buckets together*/
    crate = (struct crate*)crate_bucket->address;
    memset(crate, 0, HEAP_CRATE_SIZE);

    for(size_t i = 0; i < HEAP_CRATE_BUCKETS; i++) {
        struct bucket *bucket = &crate->buckets[i];
        struct bucket *prev = &crate->buckets[i-1];

        bucket->prev = prev;
        prev->next = bucket;
    }

    /*Set unused tail to first bucket*/
    heap->buckets_unused_tail = &crate->buckets[0];

    /*Add crate to crate list*/
    heap->crates_head->next = crate;
    heap->crates_head = crate;

    /*Add used memory to heap info*/
    heap->used += HEAP_CRATE_SIZE;

    return heap->buckets_unused_tail;
}

struct bucket*
__heap_bucket_append(struct heap *heap, struct bucket *bucket, size_t size)
{
    /*Get free bucket from crate*/
    struct bucket *free = heap->buckets_unused_tail;
    if(free == NULL) {
        free = __heap_crate_create(heap);
        if(free == NULL) return NULL;
    }
    heap->buckets_unused_tail = heap->buckets_unused_tail->next;

    /*Append free to bucket chain*/
    free->prev = bucket;
    free->next = bucket->next;
    if(free->next != NULL) free->next->prev = free;
    bucket->next = free;

    /*Fix heap buckets_head*/
    if(free->next == NULL) heap->buckets_head = free;

    /*Populate free bucket*/
    free->address = bucket->address + bucket->sizetaken;
    free->sizetaken = size;

    return free;
}

void
__heap_bucket_release(struct heap *heap, struct bucket *bucket)
{
    /*Disconnect bucket from main chain*/
    if(bucket->prev != NULL) {
        bucket->prev->next = bucket->next;
    }else{
        heap->buckets_tail = bucket->next;
    }

    if(bucket->next != NULL) {
        bucket->next->prev = bucket->prev;
    }else{
        heap->buckets_head = bucket->prev;
    }

    /*Attach bucket to unused list*/
    bucket->next = heap->buckets_unused_tail;
    bucket->prev = NULL;

    heap->buckets_unused_tail = bucket;
}

void
__heap_bucket_split(struct heap *heap, struct bucket *bucket, size_t size)
{
    /*Check if split is required*/
    intmax_t diff = bucket->sizetaken - size;
    if(diff <= 0) return;

    /*Shrink bucket to required size*/
    bucket->sizetaken = size;
    
    /*Create new bucket with remainder*/
    __heap_bucket_append(heap, bucket, diff);
}

void
__heap_bucket_merge(struct heap *heap, struct bucket *bucket)
{
    struct bucket *prev = bucket->prev;
    struct bucket *next = bucket->next;

    /*Merge bucket with prev*/
    if(prev != NULL) {
        if(!HEAP_BUCKET_TAKEN(prev)) {
            prev->sizetaken += bucket->sizetaken;
            __heap_bucket_release(heap, bucket);
            __heap_bucket_merge(heap, prev);
            return;
        }
    }
    /*Merge bucket with next*/
    if(next != NULL) {
        if(!HEAP_BUCKET_TAKEN(next)) {
            bucket->sizetaken += next->sizetaken;
            __heap_bucket_release(heap, next);
            __heap_bucket_merge(heap, bucket);
        }
    }
}

void*
heap_alloc(struct heap *heap, size_t size)
{
    struct bucket *bestfit = NULL;
    size_t remaining = heap->size - heap->used;
    if(size == 0) return NULL;

    /*Check for room in heap*/
    if(remaining < size) return NULL;

    /*Resize to fit with granularity*/
    size = ((size + (HEAP_ALLOC_GRAN - 1)) / HEAP_ALLOC_GRAN) * HEAP_ALLOC_GRAN;

    bestfit = __heap_bucket_findbest(heap, size);
    if(bestfit == NULL) {
        if(!HEAP_BUCKET_TAKEN(heap->buckets_head)) {
            /*Expand empty head to fit*/
            heap->buckets_head->sizetaken = size;
            bestfit = heap->buckets_head;
        }else{
            /*Append new bucket to list*/
            bestfit = __heap_bucket_append(heap, heap->buckets_head, size);
        }
        if(bestfit == NULL) return NULL;    /*Heap ran out of space*/
    }

    /*Split bucket into perfectly sized piece*/
    __heap_bucket_split(heap, bestfit, size);

    /*Take memory in heap, mark bucket as taken*/
    heap->used += bestfit->sizetaken;
    bestfit->sizetaken |= 1;
    return (void*)bestfit->address;
}

int
heap_free(struct heap *heap, void *ptr)
{
    uintptr_t addr = (uintptr_t)ptr;
    for(struct bucket *bucket = heap->buckets_tail;
            bucket != NULL;
            bucket = bucket->next)
    {
        if(bucket->address == addr) {
            bucket->sizetaken &= ~1;
            __heap_bucket_merge(heap, bucket);
            return 0;
        }
    }
    return -1;
}