initial commit. working alloc and free

1 files changed, 145 insertions, 0 deletions

diff --git a/heap.h b/heap.h
new file mode 100644
index 0000000..56f7cc4
--- /dev/null
+++ b/heap.h
@@ -0,0 +1,145 @@
+/**
+ * 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);
+
+/*  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