Make a heap allocator.

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);
+}