/**
* heap.h
* 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.h
* Author : Jon Santmyer <jon@jonsantmyer.com>
* Date : 10.12.2021
*
* A simple thread-unsafe double linked-list bucket heap allocator.
* Written for moderately fast variable size object allocations without
* external memory regions
* Heap object is expected to be allocated by the system
* Heap members (lists, buckets, crates) are stored in the heap memory region.
* Users are expected to write wrapper functions that handles errors and
* provides a locking mechanism for threaded applications.
*
* Required functions and headers:
* stdint.h
* uintptr_t, uintmax_t
* stddef.h
* size_t
* string.h
* memset
*
* Lists are defined by the elements they contain: they are named thusly.
* The first element of the list is suffixed by _tail
* The last element of the list is suffixed by _head
*
* Crates are page-sized bucket containers allocated inside of heap memory
* designed to allow the heap to dynamically create and destroy buckets.
* The amount of buckets each crate can hold depends on the preset size defined
* in HEAP_CRATE_SIZE, calculated in HEAP_CRATE_BUCKETS.
* Crates are stored in the previous crate's reserved bucket, except for the
* initial crate, which stores itself.
* Crates are singly linked, with the head and tail stored in the heap
* data structure.
*
* Buckets hold information about which memory region it represents, it's
* neighbors, and if it's been taken by an allocation.
* Buckets determine if they are taken by setting the first bit in the
* sizetaken field. 0 represents free, 1 represents taken.
* Buckets currently in-use by the heap are stored in the general
* buckets list, with buckets reserved for future allocations stored in
* the buckets_unused list.
*
* The heap datatype stores information about where allocations can take
* place, the buckets allocated, a list of crates, and a list of
* unused buckets.
* Unused buckets are taken when a bucket is split into two, or a bucket needs
* to be appended to the heap.
*
* When buckets assigned to an allocation are bigger than the needed size, the
* bucket is "split". the difference in sizes are stored, the bucket is
* resized to the requested size, and a new bucket is appended to the old
* bucket with the difference as it's size.
* When a bucket is freed, the bucket checks it's neighbors to see if it can be
* combined. If two adjacent buckets are not taken, they are "merged".
* both buckets' sizes are added into the left-most bucket, and the right-most
* bucket is released into the unused list.
* These actions are made to ensure that memory allocations are as compact
* as possible.
*
* When the unused list is empty and a bucket needs to be appended, the heap
* calls for a new crate to be created. The new crate occupies the reserved
* bucket of the head crate, and the bucket is pointed to the last address
* in the bucket list. The crates' buckets are initialized to link with
* eachother and are set as the head of the unused list.
*/
#ifndef JSH_HEAP_H
#define JSH_HEAP_H 1
#include <stdint.h>
#include <stddef.h>
//I want the crate to be loaded into the l1 cache
#define HEAP_CRATE_SIZE 4096
#define HEAP_BUCKET_SIZE sizeof(struct bucket)
#define HEAP_CRATE_BUCKETS (((HEAP_CRATE_SIZE - sizeof(uintptr_t)) / HEAP_BUCKET_SIZE) - 1)
#define HEAP_BUCKET_TAKEN(b) (b->sizetaken & 1)
#define HEAP_ALLOC_GRAN sizeof(uintptr_t)
struct bucket
{
uintptr_t address;
uintmax_t sizetaken;
struct bucket *prev;
struct bucket *next;
};
struct crate
{
struct bucket buckets[HEAP_CRATE_BUCKETS];
struct bucket reserved;
struct crate *next;
};
struct heap
{
uintptr_t start;
size_t size;
size_t used;
struct crate *crates_tail;
struct crate *crates_head;
struct bucket *buckets_tail;
struct bucket *buckets_head;
struct bucket *buckets_unused_tail;
};
/* Fills a heap datastructure with passed arguments and populates the first crate
* If len is less than MODIT_HEAP_CRATE_SIZE, function fails
* */
int heap_create(struct heap *heap, uintptr_t at, size_t len);
/* Expands the heap's allocation area. Does not support reallocations
* */
void heap_resize(struct heap *heap, size_t newsize);
/* Allocates a block of memory atleast [size] bytes long in heap
* */
void *heap_alloc(struct heap *heap, size_t size);
/* Frees the memory pointed at by [ptr] for later allocations.
* Returns 0 if memory was found and freed
* */
int heap_free(struct heap *heap, void *ptr);
#endif
