ref: 28e7dd47d568908702264977d70860c25467fb6e
parent: 96639193bad1db5ff22f17bacbcd4eeecd024ba9
author: Peter Mikkelsen <peter@pmikkelsen.com>
date: Thu Jul 8 13:07:15 EDT 2021
Add a mark-sweep garbage collector
--- 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,7 +504,7 @@
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;
@@ -511,7 +511,7 @@
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 @@
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;
--- a/eval.c
+++ b/eval.c
@@ -20,12 +20,12 @@
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 @@
}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 @@
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 @@
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 @@
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;
--- a/fns.h
+++ b/fns.h
@@ -76,4 +76,8 @@
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
--- /dev/null
+++ b/garbage.c
@@ -1,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
--- 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 @@
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 @@
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);
--- a/mkfile
+++ b/mkfile
@@ -15,7 +15,8 @@
streams.$O\
module.$O\
types.$O\
- arithmetic.$O
+ arithmetic.$O\
+ garbage.$O
HFILES=dat.h fns.h
--- a/module.c
+++ b/module.c
@@ -56,7 +56,7 @@
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 @@
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 @@
Module *
addemptymodule(Rune *name)
{
- Module *m = malloc(sizeof(Module));
+ Module *m = gmalloc(sizeof(Module));
m->name = name;
m->next = modules;
--- a/parser.c
+++ b/parser.c
@@ -264,8 +264,8 @@
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 @@
}
Term *result = terms[0];
- free(infos);
- free(terms);
return result;
}
@@ -409,6 +407,7 @@
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 @@
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;
--- a/repl.c
+++ b/repl.c
@@ -16,7 +16,7 @@
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 @@
print(".\n");
}
}
+
+ vlong amount = collectgarbage();
+ if(amount != 0)
+ print("Collected %lld bytes of garbage\n", amount);
}
}
--- a/streams.c
+++ b/streams.c
@@ -228,6 +228,7 @@
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;