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/gc.c | 128 +++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 99 insertions(+), 29 deletions(-) (limited to 'src/bootstrap/gc.c') 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 -- cgit v1.2.1