Add stack protection for recursive funcs

1 files changed, 107 insertions, 37 deletions

diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c
index b63ee2b..381ab6b 100644
--- a/src/bootstrap/gc.c
+++ b/src/bootstrap/gc.c
@@ -5,38 +5,63 @@ typedef struct RootNodes {
     size_t cap;
 } RootNodes;
 
+// Stack of active environments.
+typedef struct ActiveEnvs {
+    Environment **buf;
+    size_t size;
+    size_t cap;
+} ActiveEnvs;
+
 typedef struct Environments {
     Environment *buf;
     size_t size;
     size_t cap;
 } Environments;
 
+typedef struct FreeList {
+    size_t *buf;
+    size_t size;
+    size_t cap;
+    size_t position;
+} FreeList;
+
 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;
+    Object *objects;
     size_t obj_cap;
-    size_t fl_pos;
-    size_t available_slots;
+    FreeList free_objects;
+    FreeList free_envs;
+    ActiveEnvs active_envs;
 } GC;
 
 // FIXME: small value for testing purposes
-// #define GC_INITIAL_HEAP 32
-#define GC_INITIAL_HEAP 1024 * 1.5
+// #define GC_OBJS_CAP 1024 * 1024 * 10
+// #define GC_ROOTS_CAP 1024
+// #define GC_ENVS_CAP 1024 * 1024 * 2
+#define GC_OBJS_CAP  1024 * 1024
 #define GC_ROOTS_CAP 1024 * 1024
-#define GC_ENVS_CAP 1024 * 1024
+#define GC_ENVS_CAP  1024 * 1024
 
 static GC gc;
 
+void mark_and_sweep(void);
+void dump_gc(void);
+
 Environment *
 alloc_env(void) {
-    if (gc.envs.size < gc.envs.cap) {
-        return &gc.envs.buf[gc.envs.size++];
+    if (gc.free_envs.size == 0) {
+        mark_and_sweep();
+        if (gc.free_envs.size == 0) {
+            fprintf(stderr, "NO MORE ENV MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
+            dump_gc();
+            exit(EXIT_FAILURE);
+            // TODO: grow heap tables.
+        }
     }
-    fprintf(stderr, "error: not enough room for more environments\n");
-    return NULL;
+    size_t slot = gc.free_envs.buf[gc.free_envs.position++];
+    gc.free_envs.size--;
+    return &gc.envs.buf[slot];
 }
 
 void
@@ -54,12 +79,24 @@ pop_root(void) {
 }
 
 void
+push_active_env(Environment *env) {
+    if (gc.active_envs.size == gc.active_envs.cap) {
+        gc.active_envs.cap *= 2;
+        gc.active_envs.buf = realloc(gc.active_envs.buf, gc.active_envs.cap * sizeof(Environment *));
+    }
+    gc.active_envs.buf[gc.active_envs.size++] = env;
+}
+
+Environment *
+pop_active_env(void) {
+    return gc.active_envs.buf[gc.active_envs.size--];
+}
+
+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,
+        .objects = malloc(GC_OBJS_CAP * sizeof(Object)),
+        .obj_cap = GC_OBJS_CAP,
         .envs = (Environments){
             .buf = malloc(GC_ENVS_CAP * sizeof(Environment)),
             .size = 0,
@@ -70,25 +107,43 @@ init_gc(void) {
             .size = 0,
             .cap = GC_ROOTS_CAP,
         },
+        .free_objects = (FreeList){
+            .buf = malloc(GC_OBJS_CAP * sizeof(size_t)),
+            .size = GC_OBJS_CAP,
+            .cap = GC_OBJS_CAP,
+        },
+        .free_envs = (FreeList){
+            .buf = malloc(GC_ENVS_CAP * sizeof(size_t)),
+            .size = GC_ENVS_CAP,
+            .cap = GC_ENVS_CAP,
+        },
+        .active_envs = (ActiveEnvs){
+            .buf = malloc(GC_ROOTS_CAP * sizeof(Environment*)),
+            .size = 0,
+            .cap = GC_ROOTS_CAP,
+        },
     };
 
     // The free list stores the offset from the initial position for all
     // available slots.
-    for (size_t i = 0; i < gc.obj_cap; i++) {
-        gc.free_list[i] = i;
+    for (size_t i = 0; i < GC_OBJS_CAP; i++) {
+        gc.free_objects.buf[i] = i;
+    }
+    for (size_t i = 0; i < GC_ENVS_CAP; i++) {
+        gc.free_envs.buf[i] = i;
     }
 }
 
 Object *
 get_obj(size_t offset) {
-    return &gc.obj_list[offset];
+    return &gc.objects[offset];
 }
 
 void mark_obj(Object *obj);
 
 void
 mark_environment(Environment *env) {
-    if (env->marked) {
+    if (env == NULL || env->marked) {
         return;
     }
     env->marked = true;
@@ -119,8 +174,8 @@ mark_obj(Object *obj) {
 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.active_envs.size; i++) {
+        mark_environment(gc.active_envs.buf[i]);
     }
 
     for (size_t i = 0; i < gc.roots.size; i++) {
@@ -129,28 +184,43 @@ mark_and_sweep(void) {
         }
         mark_obj(gc.roots.buf[i]);
     }
-    // dump_gc()
 
     // Reset the free list.
-    gc.fl_pos = 0;
-    gc.available_slots = 0;
+    gc.free_objects.position = 0;
+    gc.free_objects.size = 0;
+    gc.free_envs.position = 0;
+    gc.free_envs.size = 0;
 
     // Sweep.
     for (size_t i = 0; i < gc.obj_cap; i++) {
-        Object *obj = &gc.obj_list[i];
+        Object *obj = &gc.objects[i];
         if (!obj->marked) {
             // Free heap allocated memory for this object if needed.
             if (obj->type == OBJ_TYPE_SYMBOL) {
                 free(obj->symbol);
+                obj->symbol = NULL;
+                obj->symbol_n = 0;
             } else if (obj->type == OBJ_TYPE_STRING) {
                 free(obj->string);
+                obj->string = NULL;
+                obj->string_n = 0;
             }
-            gc.free_list[gc.available_slots++] = i;
+            gc.free_objects.buf[gc.free_objects.size++] = i;
         }
         obj->marked = false;
     }
-    for (size_t i = 0; i < gc.envs.size; i++) {
-        gc.envs.buf[i].marked = false;
+    for (size_t i = 0; i < gc.envs.cap; i++) {
+        Environment *env = &gc.envs.buf[i];
+        if (!env->marked) {
+            if (env->buf != NULL) {
+                free(env->buf);
+                env->buf = NULL;
+                env->size = 0;
+                env->cap = 0;
+            }
+            gc.free_envs.buf[gc.free_envs.size++] = i;
+        }
+        env->marked = false;
     }
 }
 
@@ -165,11 +235,11 @@ dump_gc(void) {
         // 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];
+            Object *obj = &gc.objects[i];
             display(obj);
             bool is_free = false;
             for (size_t j = 0; j < gc.obj_cap; j++) {
-                if (gc.free_list[j] == i) {
+                if (gc.free_objects.buf[j] == i) {
                     is_free = true;
                     break;
                 }
@@ -179,16 +249,16 @@ dump_gc(void) {
             }
             printf("\n");
         }
-        printf("FREE OBJECTS: %ld\n", gc.available_slots);
+        printf("FREE OBJECTS: %ld\n", gc.free_objects.size);
         printf("ENVIRONMENTS: %ld\n", gc.envs.size);
 }
 
 Object *
 alloc_object(ObjectType type) {
-    if (gc.available_slots == 0) {
+    if (gc.free_objects.size == 0) {
         mark_and_sweep();
-        if (gc.available_slots == 0) {
-            fprintf(stderr, "NOT MORE MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
+        if (gc.free_objects.size == 0) {
+            fprintf(stderr, "NO MORE OBJ MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
             dump_gc();
             exit(EXIT_FAILURE);
             // TODO: grow heap tables.
@@ -204,8 +274,8 @@ alloc_object(ObjectType type) {
             // later.
         }
     }
-    size_t slot = gc.free_list[gc.fl_pos++];
-    gc.available_slots--;
+    size_t slot = gc.free_objects.buf[gc.free_objects.position++];
+    gc.free_objects.size--;
     Object *obj = get_obj(slot);
     obj->type = type;
     return obj;