From dbeab0d63b21c14e9c462c08c8f776e9428b853c Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Sun, 17 Oct 2021 12:51:51 +0200 Subject: Add stack protection for recursive funcs --- src/bootstrap/gc.c | 144 +++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 107 insertions(+), 37 deletions(-) (limited to 'src/bootstrap/gc.c') 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 @@ -53,13 +78,25 @@ pop_root(void) { return gc.roots.buf[gc.roots.size--]; } +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; -- cgit v1.2.1