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/environment.c | 2 +- src/bootstrap/gc.c | 144 ++++++++++++++++++++++++++++++++------------ src/bootstrap/main.c | 1 + src/bootstrap/primitives.c | 22 +++++-- 4 files changed, 127 insertions(+), 42 deletions(-) (limited to 'src') diff --git a/src/bootstrap/environment.c b/src/bootstrap/environment.c index 57baea6..570c5d4 100644 --- a/src/bootstrap/environment.c +++ b/src/bootstrap/environment.c @@ -105,7 +105,7 @@ env_add_or_update_current(Environment *env, Object *symbol, Object *value) { Environment * env_extend(Environment *parent, Environment *extra) { - Environment *env = env_create(parent); + Environment *env = parent; for (size_t i = 0; i < extra->size; i++) { EnvEntry entry = extra->buf[i]; Environment *tmp = env; 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; diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c index 66b1300..7251e60 100755 --- a/src/bootstrap/main.c +++ b/src/bootstrap/main.c @@ -47,6 +47,7 @@ init(void) { global_env = env_create(NULL); // TODO: make sure we create symbols and strings only once (interning // strings?) + push_active_env(global_env); // Primitive symbols. MAKE_ENV_VAR(global_env, "else", obj_true); diff --git a/src/bootstrap/primitives.c b/src/bootstrap/primitives.c index a814e40..0403e3a 100644 --- a/src/bootstrap/primitives.c +++ b/src/bootstrap/primitives.c @@ -5,6 +5,7 @@ Object * proc_if(Environment *env, Object *obj); Object * eval(Environment *env, Object *root) { Object* lambda; + Object* ret = NULL; bool recursion_active = false; eval_start: switch (root->type) { @@ -15,7 +16,8 @@ eval_start: case OBJ_TYPE_BOOL: case OBJ_TYPE_NIL: case OBJ_TYPE_STRING: { - return root; + ret = root; + goto eval_success; } break; case OBJ_TYPE_SYMBOL: { Object *val = env_lookup(env, root); @@ -26,7 +28,8 @@ eval_start: }); return obj_err; } - return val; + ret = val; + goto eval_success; } break; case OBJ_TYPE_PAIR: { if (root->car->type == OBJ_TYPE_SYMBOL) { @@ -64,7 +67,8 @@ eval_start: } goto eval_start; } - return val->proc(env, root->cdr); + ret = val->proc(env, root->cdr); + goto eval_success; } if (val->type == OBJ_TYPE_LAMBDA) { lambda = val; @@ -86,8 +90,12 @@ eval_lambda: args = root->cdr; Object *params = lambda->params; if (!recursion_active) { - env = env_extend(lambda->env, env); recursion_active = true; + // Protect current stack. + Environment *tmp = env_create(lambda->env); + push_active_env(tmp); + // Extend environment. + env = env_extend(tmp, env); } while (params != obj_nil) { if (args == obj_nil) { @@ -138,6 +146,12 @@ eval_lambda: .value = ERR_UNKNOWN_OBJ_TYPE, }); return obj_err; +eval_success: + if (recursion_active) { + // Remove stack protector. + pop_active_env(); + } + return ret; } Object * -- cgit v1.2.1