Add mark-sweep algorithm for GC and RootNodes

1 files changed, 102 insertions, 8 deletions

diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c
index fff4201..8ca99b7 100644
--- a/src/bootstrap/gc.c
+++ b/src/bootstrap/gc.c
@@ -1,26 +1,50 @@
+// Stack of root nodes.
+typedef struct RootNodes {
+    Object **buf;
+    size_t size;
+    size_t cap;
+} RootNodes;
+
 typedef struct GC {
+    RootNodes roots;
     Object *obj_list;
     // Free list keeps track of the offset numbers from the obj_list
     size_t *free_list;
-    size_t obj_size;
     size_t obj_cap;
     size_t fl_pos;
     size_t available_slots;
 } GC;
 
 // FIXME: small value for testing purposes
-#define GC_INITIAL_HEAP 100000
+#define GC_INITIAL_HEAP 16
+#define GC_ROOTS_CAP 8
 
 static GC gc;
 
 void
+push_root(Object *obj) {
+    if (gc.roots.size == gc.roots.cap) {
+        gc.roots.cap *= 2;
+        gc.roots.buf = realloc(gc.roots.buf, gc.roots.cap * sizeof(Object *));
+    }
+    gc.roots.buf[gc.roots.size++] = obj;
+}
+
+Object *
+pop_root(void) {
+    return gc.roots.buf[gc.roots.size--];
+}
+
+void
 init_gc(void) {
     gc = (GC){
         .obj_cap = GC_INITIAL_HEAP,
         .available_slots = GC_INITIAL_HEAP,
     };
-    gc.free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t *));
-    gc.obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object *));
+    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.
@@ -30,19 +54,89 @@ init_gc(void) {
 }
 
 Object *
+get_obj(size_t offset) {
+    return gc.obj_list + offset;
+}
+
+void
+mark_obj(Object *obj) {
+    if (obj->marked) {
+        return;
+    }
+    obj->marked = true;
+    if (obj->type == OBJ_TYPE_PAIR) {
+        mark_obj(obj->car);
+        mark_obj(obj->cdr);
+    }
+}
+
+void
+mark_and_sweep(void) {
+    // Mark.
+    for (size_t i = 0; i < gc.roots.size; i++) {
+        if (gc.roots.buf[i]->marked) {
+            continue;
+        }
+        mark_obj(gc.roots.buf[i]);
+    }
+
+    // Reset the free list.
+    gc.fl_pos = 0;
+    gc.available_slots = 0;
+
+    // Sweep.
+    for (size_t i = 0; i < gc.obj_cap; i++) {
+        if (!gc.obj_list[i].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);
+            }
+
+            gc.free_list[gc.available_slots++] = i;
+        }
+        gc.obj_list[i].marked = false;
+    }
+}
+
+Object *
 alloc_object(ObjectType type) {
     if (gc.available_slots == 0) {
-        // TODO: trigger garbage collection.
+        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");
+            }
+            exit(EXIT_FAILURE);
             // TODO: grow heap tables.
-            // NOTE: When growing the tables, we might lose the pointer
+            // NOTE: When growing the tables, we WILL lose the pointer
             // references! Should we work with offsets all the way?  That is for
-            // cdr and car? Should we have a utility function?
+            // cdr and car? Should we have a utility function? All in all, we
+            // need to refactor the codebase first to work with pointer offsets
+            // rather than objects.  This issue is very important, if we are in
+            // the middle of an operation that tries to allocate memory but we
+            // had saved pointers to some object, the pointer references may be
+            // invalidated, crashing or worse, silently returning garbage! Let's
+            // move on for now implementing the GC and we will revisit this part
+            // later.
         }
     }
     size_t slot = gc.free_list[gc.fl_pos++];
     gc.available_slots--;
-    Object *obj = gc.obj_list + slot;
+    Object *obj = get_obj(slot);
     obj->type = type;
     return obj;
 }