From bb58afb57221eb0316d6ee14e19c5f4c4a822ba1 Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Sat, 16 Oct 2021 21:22:08 +0200 Subject: Add a working GC with mark-and-sweep --- src/bootstrap/environment.c | 13 +++-- src/bootstrap/gc.c | 128 ++++++++++++++++++++++++++++++++++---------- src/bootstrap/main.c | 117 +++++++++++++++++----------------------- src/bootstrap/objects.c | 35 ------------ src/bootstrap/primitives.c | 47 ++++++++++++---- 5 files changed, 193 insertions(+), 147 deletions(-) (limited to 'src') diff --git a/src/bootstrap/environment.c b/src/bootstrap/environment.c index 78f31fb..57baea6 100644 --- a/src/bootstrap/environment.c +++ b/src/bootstrap/environment.c @@ -8,15 +8,18 @@ typedef struct Environment { EnvEntry *buf; size_t size; size_t cap; + bool marked; } Environment; static Environment *global_env; #define ENV_BUF_CAP 8 +Environment *alloc_env(void); + Environment * env_create(Environment *parent) { - Environment *env = malloc(sizeof(Environment)); + Environment *env = alloc_env(); env->parent = parent; env->buf = NULL; env->size = 0; @@ -66,7 +69,7 @@ env_update(Environment *env, Object *symbol, Object *value) { for (size_t i = 0; i < env->size; i++) { EnvEntry entry = env->buf[i]; if (obj_eq(symbol, entry.symbol)) { - env->buf[i].value = obj_duplicate(value); + env->buf[i].value = value; return obj_nil; } } @@ -94,9 +97,9 @@ void env_add_or_update_current(Environment *env, Object *symbol, Object *value) { ssize_t index = env_index_current(env, symbol); if (index == -1) { - env_add_symbol(env, obj_duplicate(symbol), obj_duplicate(value)); + env_add_symbol(env, symbol, value); } else { - env->buf[index].value = obj_duplicate(value); + env->buf[index].value = value; } } @@ -115,7 +118,7 @@ env_extend(Environment *parent, Environment *extra) { tmp = tmp->parent; } if (!found) { - env_add_symbol(env, obj_duplicate(entry.symbol), obj_duplicate(entry.value)); + env_add_symbol(env, entry.symbol, entry.value); } } return env; diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c index 8ca99b7..6e15c63 100644 --- a/src/bootstrap/gc.c +++ b/src/bootstrap/gc.c @@ -5,8 +5,15 @@ typedef struct RootNodes { size_t cap; } RootNodes; +typedef struct Environments { + Environment *buf; + size_t size; + size_t cap; +} Environments; + typedef struct GC { RootNodes roots; + Environments envs; Object *obj_list; // Free list keeps track of the offset numbers from the obj_list size_t *free_list; @@ -16,11 +23,22 @@ typedef struct GC { } GC; // FIXME: small value for testing purposes -#define GC_INITIAL_HEAP 16 -#define GC_ROOTS_CAP 8 +// #define GC_INITIAL_HEAP 32 +#define GC_INITIAL_HEAP 1024 * 1.5 +#define GC_ROOTS_CAP 1024 * 1024 +#define GC_ENVS_CAP 1024 * 1024 static GC gc; +Environment * +alloc_env(void) { + if (gc.envs.size < gc.envs.cap) { + return &gc.envs.buf[gc.envs.size++]; + } + printf("error: not enough room for more environments\n"); + return NULL; +} + void push_root(Object *obj) { if (gc.roots.size == gc.roots.cap) { @@ -38,13 +56,21 @@ pop_root(void) { void init_gc(void) { gc = (GC){ + .free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t)), + .obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object)), .obj_cap = GC_INITIAL_HEAP, .available_slots = GC_INITIAL_HEAP, + .envs = (Environments){ + .buf = malloc(GC_ENVS_CAP * sizeof(Environment)), + .size = 0, + .cap = GC_ENVS_CAP, + }, + .roots = (RootNodes){ + .buf = malloc(GC_ROOTS_CAP * sizeof(Object*)), + .size = 0, + .cap = GC_ROOTS_CAP, + }, }; - gc.free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t)); - gc.obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object)); - gc.roots.buf = malloc(GC_ROOTS_CAP * sizeof(Object*)); - gc.roots.cap = GC_ROOTS_CAP; // The free list stores the offset from the initial position for all // available slots. @@ -55,7 +81,22 @@ init_gc(void) { Object * get_obj(size_t offset) { - return gc.obj_list + offset; + return &gc.obj_list[offset]; +} + +void mark_obj(Object *obj); + +void +mark_environment(Environment *env) { + if (env->marked) { + return; + } + env->marked = true; + for (size_t i = 0; i < env->size; i++) { + EnvEntry entry = env->buf[i]; + mark_obj(entry.symbol); + mark_obj(entry.value); + } } void @@ -68,17 +109,27 @@ mark_obj(Object *obj) { mark_obj(obj->car); mark_obj(obj->cdr); } + if (obj->type == OBJ_TYPE_LAMBDA) { + mark_obj(obj->params); + mark_obj(obj->body); + mark_environment(obj->env); + } } void mark_and_sweep(void) { // Mark. + for (size_t i = 0; i < gc.envs.size; i++) { + mark_environment(&gc.envs.buf[i]); + } + for (size_t i = 0; i < gc.roots.size; i++) { if (gc.roots.buf[i]->marked) { continue; } mark_obj(gc.roots.buf[i]); } + // dump_gc() // Reset the free list. gc.fl_pos = 0; @@ -86,40 +137,59 @@ mark_and_sweep(void) { // Sweep. for (size_t i = 0; i < gc.obj_cap; i++) { - if (!gc.obj_list[i].marked) { + Object *obj = &gc.obj_list[i]; + if (!obj->marked) { // Free heap allocated memory for this object if needed. - Object obj = gc.obj_list[i]; - if (obj.type == OBJ_TYPE_SYMBOL) { - free(obj.symbol); - } else if (obj.type == OBJ_TYPE_STRING) { - free(obj.string); + if (obj->type == OBJ_TYPE_SYMBOL) { + free(obj->symbol); + } else if (obj->type == OBJ_TYPE_STRING) { + free(obj->string); } - gc.free_list[gc.available_slots++] = i; } - gc.obj_list[i].marked = false; + obj->marked = false; + } + for (size_t i = 0; i < gc.envs.size; i++) { + gc.envs.buf[i].marked = false; } } +void +dump_gc(void) { + printf("-------------- ROOTS -------------- \n"); + for (size_t i = 0; i < gc.roots.size; i++) { + display(gc.roots.buf[i]); + printf("\n"); + } + printf("------------- OBJECTS ------------- \n"); + // for (size_t i = 0; i < gc.obj_cap; i++) { + for (size_t i = 0; i < 20; i++) { + printf("i: %ld -> ", i); + Object *obj = &gc.obj_list[i]; + display(obj); + bool is_free = false; + for (size_t j = 0; j < gc.obj_cap; j++) { + if (gc.free_list[j] == i) { + is_free = true; + break; + } + } + if (is_free) { + printf(" [FREE]"); + } + printf("\n"); + } + printf("FREE OBJECTS: %ld\n", gc.available_slots); + printf("ENVIRONMENTS: %ld\n", gc.envs.size); +} + Object * alloc_object(ObjectType type) { if (gc.available_slots == 0) { - printf("triggering GC\n"); mark_and_sweep(); if (gc.available_slots == 0) { - printf("NOT MORE MEMORY AVAILABLE\n"); - printf("-------------- ROOTS -------------- \n"); - for (size_t i = 0; i < gc.roots.size; i++) { - display(gc.roots.buf[i]); - printf("\n"); - } - printf("------------- OBJECTS ------------- \n"); - for (size_t i = 0; i < gc.obj_cap; i++) { - printf("i: %ld -> ", i); - Object *obj = &gc.obj_list[i]; - display(obj); - printf("\n"); - } + printf("NOT MORE MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n"); + dump_gc(); exit(EXIT_FAILURE); // TODO: grow heap tables. // NOTE: When growing the tables, we WILL lose the pointer diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c index ce1fdfe..66b1300 100755 --- a/src/bootstrap/main.c +++ b/src/bootstrap/main.c @@ -43,54 +43,56 @@ init(void) { push_root(obj_err); push_root(obj_quote); -// // Global environment. -// global_env = env_create(NULL); - -// // Primitive symbols. -// MAKE_ENV_VAR(global_env, "else", obj_true); -// MAKE_ENV_VAR(global_env, "nil", obj_nil); - -// // Primitive procedures. -// MAKE_ENV_PROC(global_env, "eval", proc_eval); -// MAKE_ENV_PROC(global_env, "quote", proc_quote); -// MAKE_ENV_PROC(global_env, "car", proc_car); -// MAKE_ENV_PROC(global_env, "cdr", proc_cdr); -// MAKE_ENV_PROC(global_env, "cons", proc_cons); -// MAKE_ENV_PROC(global_env, "list", proc_list); -// MAKE_ENV_PROC(global_env, "+", proc_sum); -// MAKE_ENV_PROC(global_env, "-", proc_sub); -// MAKE_ENV_PROC(global_env, "*", proc_mul); -// MAKE_ENV_PROC(global_env, "/", proc_div); -// MAKE_ENV_PROC(global_env, "%", proc_mod); -// MAKE_ENV_PROC(global_env, "print", proc_print); -// MAKE_ENV_PROC(global_env, "display", proc_display); -// MAKE_ENV_PROC(global_env, "newline", proc_newline); -// MAKE_ENV_PROC(global_env, "boolean?", proc_is_boolean); -// MAKE_ENV_PROC(global_env, "nil?", proc_is_nil); -// MAKE_ENV_PROC(global_env, "symbol?", proc_is_symbol); -// MAKE_ENV_PROC(global_env, "string?", proc_is_string); -// MAKE_ENV_PROC(global_env, "fixnum?", proc_is_fixnum); -// MAKE_ENV_PROC(global_env, "pair?", proc_is_pair); -// MAKE_ENV_PROC(global_env, "procedure?", proc_is_procedure); -// MAKE_ENV_PROC(global_env, "error?", proc_is_error); -// MAKE_ENV_PROC(global_env, "not", proc_not); -// MAKE_ENV_PROC(global_env, "and", proc_and); -// MAKE_ENV_PROC(global_env, "or", proc_or); -// MAKE_ENV_PROC(global_env, "if", proc_if); -// MAKE_ENV_PROC(global_env, "cond", proc_cond); -// MAKE_ENV_PROC(global_env, "<", proc_num_less_than); -// MAKE_ENV_PROC(global_env, "<=", proc_num_lesseq_than); -// MAKE_ENV_PROC(global_env, ">", proc_num_greater_than); -// MAKE_ENV_PROC(global_env, ">=", proc_num_greatereq_than); -// MAKE_ENV_PROC(global_env, "=", proc_num_equal); -// MAKE_ENV_PROC(global_env, "eq?", proc_equal); -// MAKE_ENV_PROC(global_env, "def", proc_define); -// MAKE_ENV_PROC(global_env, "set!", proc_set); -// MAKE_ENV_PROC(global_env, "lambda", proc_lambda); -// MAKE_ENV_PROC(global_env, "fun", proc_fun); - -// // Runtime procedures. -// MAKE_ENV_PROC(global_env, "supress-errors", proc_supress_errors); + // Global environment. + global_env = env_create(NULL); + // TODO: make sure we create symbols and strings only once (interning + // strings?) + + // Primitive symbols. + MAKE_ENV_VAR(global_env, "else", obj_true); + MAKE_ENV_VAR(global_env, "nil", obj_nil); + + // Primitive procedures. + MAKE_ENV_PROC(global_env, "eval", proc_eval); + MAKE_ENV_PROC(global_env, "quote", proc_quote); + MAKE_ENV_PROC(global_env, "car", proc_car); + MAKE_ENV_PROC(global_env, "cdr", proc_cdr); + MAKE_ENV_PROC(global_env, "cons", proc_cons); + MAKE_ENV_PROC(global_env, "list", proc_list); + MAKE_ENV_PROC(global_env, "+", proc_sum); + MAKE_ENV_PROC(global_env, "-", proc_sub); + MAKE_ENV_PROC(global_env, "*", proc_mul); + MAKE_ENV_PROC(global_env, "/", proc_div); + MAKE_ENV_PROC(global_env, "%", proc_mod); + MAKE_ENV_PROC(global_env, "print", proc_print); + MAKE_ENV_PROC(global_env, "display", proc_display); + MAKE_ENV_PROC(global_env, "newline", proc_newline); + MAKE_ENV_PROC(global_env, "boolean?", proc_is_boolean); + MAKE_ENV_PROC(global_env, "nil?", proc_is_nil); + MAKE_ENV_PROC(global_env, "symbol?", proc_is_symbol); + MAKE_ENV_PROC(global_env, "string?", proc_is_string); + MAKE_ENV_PROC(global_env, "fixnum?", proc_is_fixnum); + MAKE_ENV_PROC(global_env, "pair?", proc_is_pair); + MAKE_ENV_PROC(global_env, "procedure?", proc_is_procedure); + MAKE_ENV_PROC(global_env, "error?", proc_is_error); + MAKE_ENV_PROC(global_env, "not", proc_not); + MAKE_ENV_PROC(global_env, "and", proc_and); + MAKE_ENV_PROC(global_env, "or", proc_or); + MAKE_ENV_PROC(global_env, "if", proc_if); + MAKE_ENV_PROC(global_env, "cond", proc_cond); + MAKE_ENV_PROC(global_env, "<", proc_num_less_than); + MAKE_ENV_PROC(global_env, "<=", proc_num_lesseq_than); + MAKE_ENV_PROC(global_env, ">", proc_num_greater_than); + MAKE_ENV_PROC(global_env, ">=", proc_num_greatereq_than); + MAKE_ENV_PROC(global_env, "=", proc_num_equal); + MAKE_ENV_PROC(global_env, "eq?", proc_equal); + MAKE_ENV_PROC(global_env, "def", proc_define); + MAKE_ENV_PROC(global_env, "set!", proc_set); + MAKE_ENV_PROC(global_env, "lambda", proc_lambda); + MAKE_ENV_PROC(global_env, "fun", proc_fun); + + // Runtime procedures. + MAKE_ENV_PROC(global_env, "supress-errors", proc_supress_errors); } void @@ -113,24 +115,6 @@ process_source(const StringView *source) { Object *root = parse_tree(&visitor); gc.roots.size = root_stack_size; push_root(root); - // printf("AFTER: %ld\n", gc.roots.size); - // return the stack before parsing to previous state except we now have - // the root object as well. - // printf("-----------\n"); - // printf("ROOTS: \n"); - // for (size_t i = 0; i < gc.roots.size; i++) { - // display(gc.roots.buf[i]); - // printf("\n"); - // } - // printf("...........\n"); - for (size_t i = 0; i < gc.obj_cap; i++) { - Object *obj = &gc.obj_list[i]; - printf("marked? : %d ", obj->marked); - printf("type: %d ", obj->type); - display(obj); - printf("\n"); - } - // printf("===========\n"); if (root == obj_err || errors_n != 0) { break; } @@ -141,7 +125,6 @@ process_source(const StringView *source) { printf("\n"); } pop_root(); - // mark_and_sweep(); } if (tokens.buf != NULL) { diff --git a/src/bootstrap/objects.c b/src/bootstrap/objects.c index 2bd5b1a..09076db 100644 --- a/src/bootstrap/objects.c +++ b/src/bootstrap/objects.c @@ -116,41 +116,6 @@ append_string(Object *obj, const StringView sv) { obj->string_n += sv.n; } -Object * -obj_duplicate(Object *obj) { - Object *copy = obj_err; - switch (obj->type) { - case OBJ_TYPE_BOOL: - case OBJ_TYPE_NIL: - case OBJ_TYPE_PROCEDURE: - case OBJ_TYPE_LAMBDA: // TODO: should we duplicate everything inside? - case OBJ_TYPE_ERR: { - copy = obj; - } break; - case OBJ_TYPE_FIXNUM: { - copy = make_fixnum(obj->fixnum); - } break; - case OBJ_TYPE_SYMBOL: { - copy = make_symbol((StringView){obj->symbol, obj->symbol_n}); - } break; - case OBJ_TYPE_STRING: { - copy = make_string(); - append_string(copy, (StringView){obj->string, obj->string_n}); - } break; - case OBJ_TYPE_PAIR: { - Object *root = make_pair(obj_duplicate(obj->car), obj_nil); - copy = root; - obj = obj->cdr; - while (obj != obj_nil) { - root->cdr = make_pair(obj_duplicate(obj->car), obj_nil); - root = root->cdr; - obj = obj->cdr; - } - } break; - } - return copy; -} - void display(Object *root); void diff --git a/src/bootstrap/primitives.c b/src/bootstrap/primitives.c index 35208b0..abb87e7 100644 --- a/src/bootstrap/primitives.c +++ b/src/bootstrap/primitives.c @@ -2,7 +2,6 @@ Object * eval(Environment* env, Object *root) { - return obj_nil; // DEBUG: gc switch (root->type) { case OBJ_TYPE_ERR: case OBJ_TYPE_PROCEDURE: @@ -95,7 +94,8 @@ eval_lambda: }; root = root->cdr; } - return eval(env, root->car); + root = eval(env, root->car); + return root; } } break; } @@ -630,9 +630,20 @@ proc_cons(Environment *env, Object *obj) { }); return obj_err; } - Object *a = eval(env, obj->car); - Object *b = eval(env, obj->cdr->car); - return make_pair(a, b); + Object *head = make_pair(obj_nil, obj_nil); + push_root(head); + head->car = eval(env, obj->car); + if (head->car == obj_err) { + pop_root(); + return obj_err; + } + head->cdr = eval(env, obj->cdr->car); + if (head->cdr == obj_err) { + pop_root(); + return obj_err; + } + pop_root(); + return head; } Object * @@ -640,14 +651,28 @@ proc_list(Environment *env, Object *obj) { if (obj == obj_nil) { return obj_nil; } - Object *head = make_pair(eval(env, obj->car), obj_nil); + + Object *head = make_pair(obj_nil, obj_nil); + push_root(head); + Object *tmp = eval(env, obj->car); + if (tmp == obj_err) { + pop_root(); + return obj_err; + } + head->car = tmp; Object *curr = head; obj = obj->cdr; while (obj != obj_nil) { - curr->cdr = make_pair(eval(env, obj->car), obj_nil); + tmp = eval(env, obj->car); + if (tmp == obj_err) { + pop_root(); + return obj_err; + } + curr->cdr = make_pair(tmp, obj_nil); curr = curr->cdr; obj = obj->cdr; } + pop_root(); return head; } @@ -753,8 +778,8 @@ proc_lambda(Environment *env, Object *obj) { } Object *body = obj->cdr; Object *fun = alloc_object(OBJ_TYPE_LAMBDA); - fun->params = obj_duplicate(params); - fun->body = obj_duplicate(body); + fun->params = params; + fun->body = body; fun->env = env; return fun; } @@ -788,8 +813,8 @@ proc_fun(Environment *env, Object *obj) { } Object *body = obj->cdr->cdr; Object *fun = alloc_object(OBJ_TYPE_LAMBDA); - fun->params = obj_duplicate(params); - fun->body = obj_duplicate(body); + fun->params = params; + fun->body = body; fun->env = env; env_add_or_update_current(env, name, fun); return obj_nil; -- cgit v1.2.1