Add a mark-sweep garbage collector

1 files changed, 180 insertions, 0 deletions

diff --git a/garbage.c b/garbage.c
new file mode 100644
index 0000000..ce5bc17
--- /dev/null
+++ b/garbage.c
@@ -0,0 +1,180 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+
+#include "dat.h"
+#include "fns.h"
+
+typedef struct Allocation Allocation;
+struct Allocation
+{
+	ulong size;
+	int reachable;
+	void *data;
+	Allocation *next;
+	Allocation *prev;
+};
+
+static void mark(void *);
+static void freealloc(Allocation *);
+static void markmodules(void);
+static void markgoalstack(Goal *);
+static void markchoicestack(void);
+static void markpredicates(Predicate *);
+static void markclauses(Clause *);
+static void markterm(Term *);
+static void markbindings(Binding *);
+
+static Allocation *allocations;
+
+void *
+gmalloc(ulong size)
+{
+	Allocation *a = malloc(sizeof(Allocation));
+	a->size = size;
+	a->reachable = 1;
+	a->data = malloc(size);
+	a->prev = nil;
+	a->next = allocations;
+	if(allocations)
+		allocations->prev = a;
+	allocations = a;
+
+	return a->data;
+}
+
+vlong
+collectgarbage(void)
+{
+	ulong collected = 0;
+	Allocation *a;
+
+	/* Start by marking all allocations as unreachable */
+	for(a = allocations; a != nil; a = a->next)
+		a->reachable = 0;
+
+	/* Go through root pointers and mark all allocations found as reachable.
+	   The root pointers are:
+		1) The modules
+		2) The goalstack
+		3) The choicestack
+	*/
+	markmodules();
+	markgoalstack(goalstack);
+	markchoicestack();
+
+	/* Free the allocations that were not marked as reachable */
+	a = allocations;
+	while(a != nil){
+		if(a->reachable)
+			a = a->next;
+		else{
+			Allocation *tmp = a;
+			collected += a->size;
+			a = a->next;
+			freealloc(tmp);
+		}
+	}
+	return collected;
+}
+
+static void
+mark(void *ptr)
+{
+	if(ptr == nil)
+		return;
+
+	Allocation *a;
+	for(a = allocations; a != nil; a = a->next){
+		if(a->data == ptr)
+			a->reachable = 1;
+	}
+}
+
+static void
+freealloc(Allocation *a)
+{
+	if(a->prev)
+		a->prev->next = a->next;
+	else
+		allocations = a->next;
+
+	if(a->next)
+		a->next->prev = a->prev;
+	free(a->data);
+	free(a);
+}
+
+static void 
+markmodules(void)
+{
+	Module *m;
+	for(m = modules; m != nil; m = m->next){
+		mark(m);
+		markpredicates(m->predicates);
+	}
+}
+
+static void 
+markgoalstack(Goal *goals)
+{
+	Goal *g;
+	for(g = goals; g != nil; g = g->next){
+		mark(g);
+		markterm(g->goal);
+		markterm(g->catcher);
+	}
+}
+
+static void 
+markchoicestack(void)
+{
+	Choicepoint *c;
+	for(c = choicestack; c != nil; c = c->next){
+		mark(c);
+		markgoalstack(c->goalstack);
+		markclauses(c->alternative);
+		markbindings(c->altbindings);
+	}
+}
+
+static void
+markpredicates(Predicate *preds)
+{
+	Predicate *p;
+	for(p = preds; p != nil; p = p->next){
+		mark(p);
+		markclauses(p->clauses);
+	}
+}
+
+static void
+markclauses(Clause *clauses)
+{
+	Clause *c;
+	for(c = clauses; c != nil; c = c->next){
+		mark(c);
+		markterm(c->head);
+		markterm(c->body);
+	}
+}
+
+static void
+markterm(Term *term)
+{
+	Term *t;
+	for(t = term; t != nil; t = t->next){
+		mark(t);
+		markterm(t->children);
+	}
+}
+
+static void
+markbindings(Binding *bindings)
+{
+	Binding *b;
+	for(b = bindings; b != nil; b = b->next){
+		mark(b);
+		markterm(b->value);
+	}
+}
\ No newline at end of file