Add a mark-sweep garbage collector

10 files changed, 213 insertions, 24 deletions

diff --git a/builtins.c b/builtins.c
index bebf0d1..56576a8 100644
--- a/builtins.c
+++ b/builtins.c
@@ -8,7 +8,7 @@
 #define BuiltinProto(name) int name(Term *, Binding **, Module *)
 #define Match(X, Y) (runestrcmp(name, X) == 0 && arity == Y)
 #define Throw(What) do{\
-	Goal *g = malloc(sizeof(Goal)); \
+	Goal *g = gmalloc(sizeof(Goal)); \
 	g->goal = What; \
 	g->module = usermodule; \
 	g->catcher = nil; \
@@ -504,14 +504,14 @@ builtincatch(Term *goal, Binding **bindings, Module *module)
 	Term *catcher = catchgoal->next;
 	Term *recover = catcher->next;
 
-	Goal *catchframe = malloc(sizeof(Goal));
+	Goal *catchframe = gmalloc(sizeof(Goal));
 	catchframe->goal = recover;
 	catchframe->module = module;
 	catchframe->catcher = catcher;
 	catchframe->next = goalstack;
 	goalstack = catchframe;
 
-	Goal *g = malloc(sizeof(Goal));
+	Goal *g = gmalloc(sizeof(Goal));
 	g->goal = catchgoal;
 	g->module = module;
 	g->catcher = nil;
@@ -543,7 +543,7 @@ builtinthrow(Term *goal, Binding **bindings, Module *module)
 				return 0;
 			}else{
 				goalstack = g->next;
-				Goal *newgoal = malloc(sizeof(Goal));
+				Goal *newgoal = gmalloc(sizeof(Goal));
 				newgoal->goal = copyterm(g->goal, nil);
 				newgoal->module = module;
 				newgoal->catcher = nil;
diff --git a/eval.c b/eval.c
index d482b7d..e490eb6 100644
--- a/eval.c
+++ b/eval.c
@@ -20,12 +20,12 @@ evalquery(Term *query, Binding **resultbindings)
 		and to get the result we can unify the original query with the one at the bottom of the stack, to get the bindings
 		applied.
 	*/
-		goalstack = malloc(sizeof(Goal));
+		goalstack = gmalloc(sizeof(Goal));
 		goalstack->goal = copyterm(query, nil);
 		goalstack->module = usermodule;
 		goalstack->catcher = nil;
 		goalstack->next = nil;
-		Goal *protector = malloc(sizeof(Goal));
+		Goal *protector = gmalloc(sizeof(Goal));
 		protector->goal = nil;
 		protector->module = usermodule;
 		protector->catcher = mkvariable(L"catch-var");
@@ -125,7 +125,7 @@ addgoals(Goal *goals, Term *t, Module *module)
 			}else
 				t = typeerror(L"module", moduleterm);
 		}
-		Goal *g = malloc(sizeof(Goal));
+		Goal *g = gmalloc(sizeof(Goal));
 		g->goal = t;
 		g->module = module;
 		g->catcher = nil;
@@ -198,7 +198,7 @@ unify(Term *a, Term *b, Binding **bindings)
 			if(runestrcmp(left->text, L"_") == 0)
 				continue; /* _ doesn't introduce a new binding */
 
-			Binding *b = malloc(sizeof(Binding));
+			Binding *b = gmalloc(sizeof(Binding));
 			b->name = left->text;
 			b->nr = left->clausenr;
 			b->value = right;
@@ -280,7 +280,7 @@ Goal *
 copygoals(Goal *goals)
 {
 	if(goals != nil){
-		Goal *g = malloc(sizeof(Goal));
+		Goal *g = gmalloc(sizeof(Goal));
 		g->module = goals->module;
 		if(goals->goal)
 			g->goal = copyterm(goals->goal, nil);
@@ -308,7 +308,7 @@ addchoicepoints(Clause *clause, Term *goal, Goal *goals, Module *mod){
 		clause = findclause(alt, goal, &altbindings);
 		if(clause){
 			/* Add choicepoint here */
-			Choicepoint *cp = malloc(sizeof(Choicepoint));
+			Choicepoint *cp = gmalloc(sizeof(Choicepoint));
 			cp->goalstack = copygoals(goals);
 			cp->next = nil;
 			cp->alternative = clause;
diff --git a/fns.h b/fns.h
index 2238d56..4c8b682 100644
--- a/fns.h
+++ b/fns.h
@@ -76,4 +76,8 @@ Term *listhead(Term *);
 Term *listtail(Term *);
 
 /* arithmetic.c */
-Term *aritheval(Term *, int *);
\ No newline at end of file
+Term *aritheval(Term *, int *);
+
+/* garbage.c */
+void *gmalloc(ulong);
+vlong collectgarbage(void);
\ No newline at end of file
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
diff --git a/misc.c b/misc.c
index 08aa339..fd74a82 100644
--- a/misc.c
+++ b/misc.c
@@ -8,7 +8,7 @@
 Term *
 copyterm(Term *orig, uvlong *clausenr)
 {
-	Term *new = malloc(sizeof(Term));
+	Term *new = gmalloc(sizeof(Term));
 	memcpy(new, orig, sizeof(Term));
 	new->next = nil;
 	new->children = nil;
@@ -47,7 +47,7 @@ termslength(Term *list)
 Term *
 mkterm(int tag)
 {
-	Term *t = malloc(sizeof(Term));
+	Term *t = gmalloc(sizeof(Term));
 	t->tag = tag;
 	t->next = nil;
 	t->children = nil;
@@ -142,7 +142,7 @@ mklist(Term *elems)
 Clause *
 copyclause(Clause *orig, uvlong *clausenr)
 {
-	Clause *new = malloc(sizeof(Clause));
+	Clause *new = gmalloc(sizeof(Clause));
 	new->head = copyterm(orig->head, clausenr);
 	if(orig->body)
 		new->body = copyterm(orig->body, clausenr);
diff --git a/mkfile b/mkfile
index e74511b..6878070 100644
--- a/mkfile
+++ b/mkfile
@@ -15,7 +15,8 @@ OFILES=\
 	streams.$O\
 	module.$O\
 	types.$O\
-	arithmetic.$O
+	arithmetic.$O\
+	garbage.$O
 
 HFILES=dat.h fns.h
 
diff --git a/module.c b/module.c
index 8325fc9..45d0797 100644
--- a/module.c
+++ b/module.c
@@ -56,7 +56,7 @@ parsemodule(char *file)
 	Predicate *currentpred = nil;
 	Term *t;
 	for(t = terms; t != nil; t = t->next){
-		Clause *cl = malloc(sizeof(Clause));
+		Clause *cl = gmalloc(sizeof(Clause));
 		int arity;
 		cl->clausenr = 0;
 		cl->next = nil;
@@ -78,7 +78,7 @@ parsemodule(char *file)
 				m->predicates = appendpredicate(currentpred, m->predicates);
 			else
 				usermodule->predicates = appendpredicate(currentpred, usermodule->predicates);
-			currentpred = malloc(sizeof(Predicate));
+			currentpred = gmalloc(sizeof(Predicate));
 			currentpred->name = cl->head->text;
 			currentpred->arity = arity;
 			currentpred->clauses = cl;
@@ -109,7 +109,7 @@ getmodule(Rune *name)
 Module *
 addemptymodule(Rune *name)
 {
-	Module *m = malloc(sizeof(Module));
+	Module *m = gmalloc(sizeof(Module));
 	m->name = name;
 	m->next = modules;
 
diff --git a/parser.c b/parser.c
index dc86734..acca0cb 100644
--- a/parser.c
+++ b/parser.c
@@ -264,8 +264,8 @@ parseoperators(Term *list)
 	int i;
 	int length = termslength(list);
 	Term *t;
-	Term **terms = malloc(sizeof(Term *) * length);
-	OpInfo *infos = malloc(sizeof(OpInfo) * length);
+	Term **terms = gmalloc(sizeof(Term *) * length);
+	OpInfo *infos = gmalloc(sizeof(OpInfo) * length);
 
 	for(i = 0, t = list; i < length; i++){
 		Operator *op = getoperator(t->text);
@@ -346,8 +346,6 @@ parseoperators(Term *list)
 	}
 
 	Term *result = terms[0];
-	free(infos);
-	free(terms);
 	return result;
 }
 
@@ -409,6 +407,7 @@ initoperators(void)
 void
 addoperator(int level, int type, Rune *spelling)
 {
+	/* the operator table is never garbage collected, so just use normal malloc */
 	Operator *op = malloc(sizeof(Operator));
 	op->type = type;
 	op->level = level;
@@ -431,7 +430,7 @@ getoperator(Rune *spelling)
 		for(tmp = operators[level]; tmp != nil; tmp = tmp->next){
 			if(runestrcmp(tmp->spelling, spelling) == 0){
 				if(op == nil){
-					op = malloc(sizeof(Operator));
+					op = gmalloc(sizeof(Operator));
 					memcpy(op, tmp, sizeof(Operator));
 				}else
 					op->type |= tmp->type;
diff --git a/repl.c b/repl.c
index d179429..14e833c 100644
--- a/repl.c
+++ b/repl.c
@@ -16,7 +16,7 @@ repl(void)
 		Term *query = parse(fd, nil, 1);
 		Binding *bindings = nil;
 		choicestack = nil;
-		goalstack = nil; /* should free old choicestack and goalstack */
+		goalstack = nil;
 		int success;
 		int firsttime = 1;
 FindMore:
@@ -50,6 +50,10 @@ FindMore:
 				print(".\n");
 			}
 		}
+
+		vlong amount = collectgarbage();
+		if(amount != 0)
+			print("Collected %lld bytes of garbage\n", amount);
 	}
 }
 
diff --git a/streams.c b/streams.c
index 10d136d..cc9db63 100644
--- a/streams.c
+++ b/streams.c
@@ -228,6 +228,7 @@ writeterm(Term *stream, Term *options, Term *term)
 Stream *
 openstreamfd(int fd, Biobuf *bio, int type, int mode)
 {
+	/* streams are not garbage collected for now */
 	Stream *s = malloc(sizeof(Stream));
 	s->fd = fd;
 	s->bio = bio;