aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--heap.c218
1 files changed, 218 insertions, 0 deletions
diff --git a/heap.c b/heap.c
new file mode 100644
index 0000000..586bdfc
--- /dev/null
+++ b/heap.c
@@ -0,0 +1,218 @@
+/* Simple heap allocator.
+ *
+ * I saw this article: https://samwho.dev/memory-allocation/
+ * and was inspired to re-write the heap allocator I made a
+ * while ago to try to make it faster and less wasteful.
+ *
+ * How it works:
+ * The allocator is given a buffer where all of the allocations
+ * will go. Each allocation is given a "block" from the buffer
+ * that is the size of the allocation plus a "header size". The
+ * header of each block is four bytes: The most significant
+ * 31 bits represent the size of the allocation and the least
+ * significant bit (or the "taken" bit) is 1 if the block
+ * currently represents an allocation and 0 if it's free and
+ * available for use.
+ *
+ * On initialisation, the allocator is given a single free
+ * block that is the size of the entire buffer.
+ *
+ * When heap_alloc is called:
+ * First, all of the current blocks are iterated. If a free
+ * block is found that's the same size as the requested
+ * allocation, then the block's "taken" bit is set to 1 and
+ * the block's allocation is returned.
+ * Otherwise, a free block that is larger than the requested
+ * allocation may be found. In this case, the block is split
+ * in two such that two blocks remain: A block of the same
+ * size as the allocation and a block containing the remaining
+ * half of the block. The former is returned. The free block
+ * from the split is placed before the returned block (in
+ * other words, the buffer is filled from back to front),
+ * that way when the allocator is called on again it might
+ * well find a suitable block within a few iterations.
+ * Otherwise, no free blocks were found to be big enough
+ * and thus the program is out of memory. Here, it just calls
+ * abort, but this case may want handling more cleanly.
+ *
+ * When heap_free is called:
+ * The header to the allocation is first calculated - it's
+ * simply the four bytes that come directly before the
+ * pointer that is given. The header's "taken" bit is set
+ * to zero to indicate a freed block.
+ * Then, the allocator is de-fragmented. What this boils
+ * down to is iterating all of the blocks and recording the
+ * first free block that is seen. Then, all free blocks after
+ * that are iterated until a "taken" block is found. Every
+ * block between the first free block and the first "taken"
+ * block is coagulated into a single free block before
+ * continuing from the first step until every block has been
+ * visited.
+ *
+ * There are also functions for aligning allocations, as
+ * that is also an integral part of any allocator. By default,
+ * allocations are given an alignment of 4 bytes, which is
+ * typical of general-purpose allocators on PCs.
+ */
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct {
+ char* buffer;
+ int size, blocks;
+} Heap;
+
+void init_heap(Heap* heap, char* buf, int size) {
+ heap->buffer = buf;
+ heap->size = size;
+ heap->blocks = 1;
+ ((int*)buf)[0] = size << 1;
+}
+
+static uintptr_t align_address(
+ uintptr_t address,
+ size_t align
+) {
+ size_t m;
+ m = align - 1;
+ return (address + m) & ~m;
+}
+
+static void* heap_alloc_impl(Heap* h, int size) {
+ int* header, * nh, s, f, i, as, p;
+ i = 0;
+ as = size + sizeof *header;
+ p = 0;
+ for (i = 0; i < h->blocks; i++) {
+ header = (int*)(h->buffer + p);
+ s = header[0];
+ f = !(s & 1);
+ s >>= 1;
+ if (f) {
+ /* There's no point creating blocks smaller than
+ * the header. */
+ if (as < s - sizeof *header - 1) {
+ s -= as;
+ header[0] = (s << 1);
+ nh = (int*)(h->buffer + p + s);
+ nh[0] = (as << 1) | 1;
+ h->blocks++;
+ return nh + 1;
+ } else if (s == as) {
+ header[0] |= 1;
+ return header + 1;
+ }
+ }
+ p += s;
+ }
+ abort();
+ return 0;
+}
+
+static void heap_free_impl(Heap* h, void* ptr) {
+ int* header, *h2, i, j, s, f, d, n, ns, p;
+ header = &((int*)ptr)[-1];
+ *header &= INT32_MAX << 1;
+ p = n = 0;
+ for (i = 0; i < h->blocks; i++) {
+ header = (int*)(h->buffer + p);
+ s = header[0];
+ f = !(s & 1);
+ s >>= 1;
+ if (f) {
+ ns = s;
+ p += s;
+ d = 0;
+ for (j = i + 1; j < h->blocks; j++) {
+ h2 = (int*)(h->buffer + p);
+ s = h2[0];
+ f = !(s & 1);
+ if (!f) { break; }
+ s >>= 1;
+ p += s;
+ ns += s;
+ d++;
+ }
+ i = j - 1;
+ n += d;
+ if (d)
+ header[0] = ns << 1;
+ } else
+ p += s;
+ }
+ h->blocks -= n;
+}
+
+void heap_print_blocks(const Heap* h) {
+ const int* header;
+ int s, f, p, i;
+ p = 0;
+ printf("%8s %8s %s\n", "offset", "size", "free");
+ for (i = 0; i < h->blocks; i++) {
+ header = (const int*)(h->buffer + p);
+ s = header[0];
+ f = !(s & 1);
+ s >>= 1;
+ printf("%8d %8d %d\n", p, s, f);
+ p += s;
+ }
+}
+
+void* heap_alloc_aligned(Heap* h, int size, unsigned align) {
+ unsigned char* p, * a;
+ ptrdiff_t shift;
+ size += (int)align;
+ p = heap_alloc_impl(h, size);
+ a = (unsigned char*)align_address((uintptr_t)p, align);
+ a += align * (unsigned)(p == a);
+ shift = a - p;
+ a[-1] = shift & 0xff;
+ return a;
+}
+
+void heap_free_aligned(Heap* h, void* ptr) {
+ unsigned char* a;
+ ptrdiff_t shift;
+ a = ptr;
+ shift = a[-1];
+ shift += 256 * shift == 0;
+ a -= shift;
+ heap_free_impl(h, a);
+}
+
+void* heap_alloc(Heap* h, int size) {
+ return heap_alloc_aligned(h, size, 4);
+}
+
+void heap_free(Heap* h, void* ptr) {
+ heap_free_aligned(h, ptr);
+}
+
+int main() {
+ char buffer[4096];
+ Heap heap;
+ int i, s;
+ void* allocs[64];
+ init_heap(&heap, buffer, sizeof buffer);
+ srand(500);
+ /* Test: allocate a bunch of random blocks,
+ * then free them randomly, then allocate some
+ * more and print the state. */
+ for (i = 0; i < 64; i++) {
+ s = rand() % 32 + 1;
+ allocs[i] = heap_alloc(&heap, s);
+ }
+ for (i = 0; i < 64; i++) {
+ if (rand() % 5 == 0) {
+ heap_free(&heap, allocs[i]);
+ }
+ }
+ for (i = 0; i < 32; i++) {
+ s = rand() % 32 + 1;
+ heap_alloc(&heap, s);
+ }
+ heap_print_blocks(&heap);
+}