Add a working GC with mark-and-sweep

1 files changed, 99 insertions, 29 deletions

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