Write a garbage collector.

Does it work? No, but it compiles.

7 files changed, 174 insertions, 7 deletions

diff --git a/bytecode/encoding.c b/bytecode/encoding.c
index 62c9762..520b6c3 100644
--- a/bytecode/encoding.c
+++ b/bytecode/encoding.c
@@ -34,7 +34,7 @@ static local parse_local(struct reader *r)
 		panicf("local: no data!\n");
 	}
 	local res = r->data.buf[0];
-	if (res > 7) {
+	if (res >= NUM_LOCALS) {
 		panicf("Invalid local (out of range): %d\n", res);
 	}
 	advance(r, 1);
diff --git a/bytecode/encoding.h b/bytecode/encoding.h
index 49357f6..fed187b 100644
--- a/bytecode/encoding.h
+++ b/bytecode/encoding.h
@@ -9,6 +9,8 @@
 
 typedef uint8_t local;
 
+#define NUM_LOCALS 8
+
 // An arg can be a value or a constant.
 struct arg {
 	local local;
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);
+}
diff --git a/bytecode/heap.h b/bytecode/heap.h
new file mode 100644
index 0000000..c8d7e2c
--- /dev/null
+++ b/bytecode/heap.h
@@ -0,0 +1,27 @@
+#ifndef _HEAP_H_
+#define _HEAP_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include "slice.h"
+#include "value.h"
+
+struct heap {
+	// The heap is divided into two halves for garbage collection.
+	// buf holds the malloc'd heap buffer.
+	value *buf;
+	// active and standby are slices that partition buf.
+	struct val_slice active;
+	struct val_slice standby;
+
+	size_t free_ptr;
+
+	size_t last_free;
+	struct val_slice gc_roots;
+};
+
+struct heap new_heap(struct val_slice);
+value *alloc(struct heap *, int64_t);
+
+#endif
diff --git a/bytecode/oper.c b/bytecode/oper.c
index ed4a681..fcb7d77 100644
--- a/bytecode/oper.c
+++ b/bytecode/oper.c
@@ -2,6 +2,7 @@
 #include <stdlib.h>
 
 #include "encoding.h"
+#include "heap.h"
 #include "panic.h"
 #include "slice.h"
 #include "value.h"
@@ -10,7 +11,8 @@
 
 struct st {
 	size_t i;
-	value locals[8];
+	value locals[NUM_LOCALS];
+	struct heap heap;
 };
 
 static value read_arg(struct st *s, struct arg arg)
@@ -21,9 +23,9 @@ static value read_arg(struct st *s, struct arg arg)
 	return s->locals[arg.local];
 }
 
-static void alloc(struct st *s, struct op oper)
+static void oalloc(struct st *s, struct op oper)
 {
-	s->locals[oper.alloc.out] = from_pointer(calloc(to_int(read_arg(s, oper.alloc.size)), sizeof(value)));
+	s->locals[oper.alloc.out] = from_pointer(alloc(&s->heap, to_int(read_arg(s, oper.alloc.size))));
 }
 
 static void call(struct st *s)
@@ -57,7 +59,7 @@ static void op(struct st *s, struct op oper)
 {
 	switch (oper.code) {
 	case OALLOC:
-		alloc(s, oper);
+		oalloc(s, oper);
 		break;
 	case OCALL:
 		call(s);
@@ -85,6 +87,7 @@ void run(struct slice prog)
 		.i = 0,
 		.locals = { 0 },
 	};
+	s.heap = new_heap((struct val_slice) { .size = NUM_LOCALS, .buf = s.locals });
 	while (true) {
 		struct result oper = parse(slice1(prog, s.i));
 		s.i += oper.n;
diff --git a/bytecode/slice.c b/bytecode/slice.c
index c7b2820..0739a4a 100644
--- a/bytecode/slice.c
+++ b/bytecode/slice.c
@@ -10,6 +10,16 @@ struct slice slice(struct slice a, size_t i, size_t j)
 
 struct slice slice1(struct slice a, size_t i)
 {
-	assert(i <= a.size);
-	return (struct slice) { .size = a.size - i, .buf = a.buf + i };
+	return slice(a, i, a.size);
+}
+
+struct val_slice val_slice(struct val_slice a, size_t i, size_t j)
+{
+	assert(i <= a.size && j <= a.size && i <= j);
+	return (struct val_slice) { .size = j - i, .buf = a.buf + i };
+}
+
+struct val_slice val_slice1(struct val_slice a, size_t i)
+{
+	return val_slice(a, i, a.size);
 }
diff --git a/bytecode/slice.h b/bytecode/slice.h
index 509f7ca..577befd 100644
--- a/bytecode/slice.h
+++ b/bytecode/slice.h
@@ -4,13 +4,24 @@
 #include <stddef.h>
 #include <stdint.h>
 
+#include "value.h"
+
 struct slice {
 	size_t size;
 	uint8_t *buf;
 };
 
+struct val_slice {
+	size_t size;
+	value *buf;
+};
+
 struct slice slice(struct slice, size_t, size_t);
 
 struct slice slice1(struct slice, size_t);
 
+struct val_slice val_slice(struct val_slice, size_t, size_t);
+
+struct val_slice val_slice1(struct val_slice, size_t);
+
 #endif