From 60622614731bc42dd44704d3cff55b4e4c4f492c Mon Sep 17 00:00:00 2001
From: Rose Hogenson <rhogenson@posteo.net>
Date: Sat, 11 Feb 2023 13:40:10 -0800
Subject: Write a garbage collector.

Does it work? No, but it compiles.
---
 bytecode/heap.c | 114 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 114 insertions(+)
 create mode 100644 bytecode/heap.c

(limited to 'bytecode/heap.c')

diff --git a/bytecode/heap.c b/bytecode/heap.c
new file mode 100644
index 0000000..863bf0c
--- /dev/null
+++ b/bytecode/heap.c
@@ -0,0 +1,114 @@
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "encoding.h"
+#include "heap.h"
+#include "panic.h"
+#include "value.h"
+
+struct heap new_heap(struct val_slice gc_roots)
+{
+	return (struct heap) {
+		.buf = NULL,
+		.active = { .size = 0 },
+		.standby = { .size = 0 },
+		.free_ptr = 0,
+		.last_free = 0,
+		.gc_roots = gc_roots,
+	};
+}
+
+static bool forwarded(struct heap *h, value *p)
+{
+	if (!is_pointer(*p)) {
+		return false;
+	}
+	value *q = to_pointer(*p);
+	return h->active.buf <= q && q <= h->active.buf + h->active.size;
+}
+
+static size_t alloc_size(value *p)
+{
+	return p[-1] >> 1;
+}
+
+static value *simple_alloc(struct heap *h, int64_t size)
+{
+	h->active.buf[h->free_ptr] = size << 1;
+	value *p = h->active.buf + h->free_ptr + 1;
+	h->free_ptr += size;
+	return p;
+}
+
+static value process_gc_value(struct heap *h, value val)
+{
+	if (!is_pointer(val)) {
+		return val;
+	}
+	value *p = to_pointer(val);
+	if (forwarded(h, p)) {
+		return *p;
+	}
+
+	size_t size = alloc_size(p);
+
+	// Allocate space in the new buffer.
+	value *q = simple_alloc(h, size);
+
+	// Copy values, recursively modifying pointers.
+	for (size_t i = 0; i < size; i++) {
+		q[i] = process_gc_value(h, p[i]);
+	}
+
+	// Write forwarding pointer.
+	p[0] = from_pointer(q);
+
+	return from_pointer(q);
+}
+
+static void collect_garbage(struct heap *h)
+{
+	if (h->free_ptr < 2 * h->last_free) {
+		return;
+	}
+
+	// Swap the heaps.
+	struct val_slice temp = h->active;
+	h->active = h->standby;
+	h->standby = temp;
+
+	h->free_ptr = 0;
+
+	for (size_t i = 0; i < h->gc_roots.size; i++ ) {
+		h->gc_roots.buf[i] = process_gc_value(h, h->gc_roots.buf[i]);
+	}
+}
+
+static void more_space(struct heap *h, int64_t size_hint)
+{
+	size_t new_size = h->active.size * 2 + size_hint;
+	value *new_buf = calloc(2 * new_size, sizeof(value));
+	if (!new_buf) {
+		panicf("Out of memory!\n");
+	}
+	memcpy(new_buf, h->active.buf, h->active.size * sizeof(value));
+	free(h->buf);
+
+	h->buf = new_buf;
+	h->active = (struct val_slice) { .size = new_size, .buf = new_buf };
+	h->standby = (struct val_slice) { .size = new_size, .buf = new_buf + new_size };
+}
+
+value *alloc(struct heap *h, int64_t size)
+{
+	if (size <= 0) {
+		panicf("Alloc of zero size!\n");
+	}
+	collect_garbage(h);
+
+	if (h->free_ptr + size >= h->active.size) {
+		more_space(h, size);
+	}
+	return simple_alloc(h, size);
+}
-- 
cgit v1.3.1