diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/bootstrap/environment.c | 2 | ||||
-rw-r--r-- | src/bootstrap/gc.c | 144 | ||||
-rwxr-xr-x | src/bootstrap/main.c | 1 | ||||
-rw-r--r-- | src/bootstrap/primitives.c | 22 |
4 files changed, 127 insertions, 42 deletions
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) { | |||
105 | 105 | ||
106 | Environment * | 106 | Environment * |
107 | env_extend(Environment *parent, Environment *extra) { | 107 | env_extend(Environment *parent, Environment *extra) { |
108 | Environment *env = env_create(parent); | 108 | Environment *env = parent; |
109 | for (size_t i = 0; i < extra->size; i++) { | 109 | for (size_t i = 0; i < extra->size; i++) { |
110 | EnvEntry entry = extra->buf[i]; | 110 | EnvEntry entry = extra->buf[i]; |
111 | Environment *tmp = env; | 111 | 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 { | |||
5 | size_t cap; | 5 | size_t cap; |
6 | } RootNodes; | 6 | } RootNodes; |
7 | 7 | ||
8 | // Stack of active environments. | ||
9 | typedef struct ActiveEnvs { | ||
10 | Environment **buf; | ||
11 | size_t size; | ||
12 | size_t cap; | ||
13 | } ActiveEnvs; | ||
14 | |||
8 | typedef struct Environments { | 15 | typedef struct Environments { |
9 | Environment *buf; | 16 | Environment *buf; |
10 | size_t size; | 17 | size_t size; |
11 | size_t cap; | 18 | size_t cap; |
12 | } Environments; | 19 | } Environments; |
13 | 20 | ||
21 | typedef struct FreeList { | ||
22 | size_t *buf; | ||
23 | size_t size; | ||
24 | size_t cap; | ||
25 | size_t position; | ||
26 | } FreeList; | ||
27 | |||
14 | typedef struct GC { | 28 | typedef struct GC { |
15 | RootNodes roots; | 29 | RootNodes roots; |
16 | Environments envs; | 30 | Environments envs; |
17 | Object *obj_list; | 31 | Object *objects; |
18 | // Free list keeps track of the offset numbers from the obj_list | ||
19 | size_t *free_list; | ||
20 | size_t obj_cap; | 32 | size_t obj_cap; |
21 | size_t fl_pos; | 33 | FreeList free_objects; |
22 | size_t available_slots; | 34 | FreeList free_envs; |
35 | ActiveEnvs active_envs; | ||
23 | } GC; | 36 | } GC; |
24 | 37 | ||
25 | // FIXME: small value for testing purposes | 38 | // FIXME: small value for testing purposes |
26 | // #define GC_INITIAL_HEAP 32 | 39 | // #define GC_OBJS_CAP 1024 * 1024 * 10 |
27 | #define GC_INITIAL_HEAP 1024 * 1.5 | 40 | // #define GC_ROOTS_CAP 1024 |
41 | // #define GC_ENVS_CAP 1024 * 1024 * 2 | ||
42 | #define GC_OBJS_CAP 1024 * 1024 | ||
28 | #define GC_ROOTS_CAP 1024 * 1024 | 43 | #define GC_ROOTS_CAP 1024 * 1024 |
29 | #define GC_ENVS_CAP 1024 * 1024 | 44 | #define GC_ENVS_CAP 1024 * 1024 |
30 | 45 | ||
31 | static GC gc; | 46 | static GC gc; |
32 | 47 | ||
48 | void mark_and_sweep(void); | ||
49 | void dump_gc(void); | ||
50 | |||
33 | Environment * | 51 | Environment * |
34 | alloc_env(void) { | 52 | alloc_env(void) { |
35 | if (gc.envs.size < gc.envs.cap) { | 53 | if (gc.free_envs.size == 0) { |
36 | return &gc.envs.buf[gc.envs.size++]; | 54 | mark_and_sweep(); |
55 | if (gc.free_envs.size == 0) { | ||
56 | fprintf(stderr, "NO MORE ENV MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n"); | ||
57 | dump_gc(); | ||
58 | exit(EXIT_FAILURE); | ||
59 | // TODO: grow heap tables. | ||
60 | } | ||
37 | } | 61 | } |
38 | fprintf(stderr, "error: not enough room for more environments\n"); | 62 | size_t slot = gc.free_envs.buf[gc.free_envs.position++]; |
39 | return NULL; | 63 | gc.free_envs.size--; |
64 | return &gc.envs.buf[slot]; | ||
40 | } | 65 | } |
41 | 66 | ||
42 | void | 67 | void |
@@ -54,12 +79,24 @@ pop_root(void) { | |||
54 | } | 79 | } |
55 | 80 | ||
56 | void | 81 | void |
82 | push_active_env(Environment *env) { | ||
83 | if (gc.active_envs.size == gc.active_envs.cap) { | ||
84 | gc.active_envs.cap *= 2; | ||
85 | gc.active_envs.buf = realloc(gc.active_envs.buf, gc.active_envs.cap * sizeof(Environment *)); | ||
86 | } | ||
87 | gc.active_envs.buf[gc.active_envs.size++] = env; | ||
88 | } | ||
89 | |||
90 | Environment * | ||
91 | pop_active_env(void) { | ||
92 | return gc.active_envs.buf[gc.active_envs.size--]; | ||
93 | } | ||
94 | |||
95 | void | ||
57 | init_gc(void) { | 96 | init_gc(void) { |
58 | gc = (GC){ | 97 | gc = (GC){ |
59 | .free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t)), | 98 | .objects = malloc(GC_OBJS_CAP * sizeof(Object)), |
60 | .obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object)), | 99 | .obj_cap = GC_OBJS_CAP, |
61 | .obj_cap = GC_INITIAL_HEAP, | ||
62 | .available_slots = GC_INITIAL_HEAP, | ||
63 | .envs = (Environments){ | 100 | .envs = (Environments){ |
64 | .buf = malloc(GC_ENVS_CAP * sizeof(Environment)), | 101 | .buf = malloc(GC_ENVS_CAP * sizeof(Environment)), |
65 | .size = 0, | 102 | .size = 0, |
@@ -70,25 +107,43 @@ init_gc(void) { | |||
70 | .size = 0, | 107 | .size = 0, |
71 | .cap = GC_ROOTS_CAP, | 108 | .cap = GC_ROOTS_CAP, |
72 | }, | 109 | }, |
110 | .free_objects = (FreeList){ | ||
111 | .buf = malloc(GC_OBJS_CAP * sizeof(size_t)), | ||
112 | .size = GC_OBJS_CAP, | ||
113 | .cap = GC_OBJS_CAP, | ||
114 | }, | ||
115 | .free_envs = (FreeList){ | ||
116 | .buf = malloc(GC_ENVS_CAP * sizeof(size_t)), | ||
117 | .size = GC_ENVS_CAP, | ||
118 | .cap = GC_ENVS_CAP, | ||
119 | }, | ||
120 | .active_envs = (ActiveEnvs){ | ||
121 | .buf = malloc(GC_ROOTS_CAP * sizeof(Environment*)), | ||
122 | .size = 0, | ||
123 | .cap = GC_ROOTS_CAP, | ||
124 | }, | ||
73 | }; | 125 | }; |
74 | 126 | ||
75 | // The free list stores the offset from the initial position for all | 127 | // The free list stores the offset from the initial position for all |
76 | // available slots. | 128 | // available slots. |
77 | for (size_t i = 0; i < gc.obj_cap; i++) { | 129 | for (size_t i = 0; i < GC_OBJS_CAP; i++) { |
78 | gc.free_list[i] = i; | 130 | gc.free_objects.buf[i] = i; |
131 | } | ||
132 | for (size_t i = 0; i < GC_ENVS_CAP; i++) { | ||
133 | gc.free_envs.buf[i] = i; | ||
79 | } | 134 | } |
80 | } | 135 | } |
81 | 136 | ||
82 | Object * | 137 | Object * |
83 | get_obj(size_t offset) { | 138 | get_obj(size_t offset) { |
84 | return &gc.obj_list[offset]; | 139 | return &gc.objects[offset]; |
85 | } | 140 | } |
86 | 141 | ||
87 | void mark_obj(Object *obj); | 142 | void mark_obj(Object *obj); |
88 | 143 | ||
89 | void | 144 | void |
90 | mark_environment(Environment *env) { | 145 | mark_environment(Environment *env) { |
91 | if (env->marked) { | 146 | if (env == NULL || env->marked) { |
92 | return; | 147 | return; |
93 | } | 148 | } |
94 | env->marked = true; | 149 | env->marked = true; |
@@ -119,8 +174,8 @@ mark_obj(Object *obj) { | |||
119 | void | 174 | void |
120 | mark_and_sweep(void) { | 175 | mark_and_sweep(void) { |
121 | // Mark. | 176 | // Mark. |
122 | for (size_t i = 0; i < gc.envs.size; i++) { | 177 | for (size_t i = 0; i < gc.active_envs.size; i++) { |
123 | mark_environment(&gc.envs.buf[i]); | 178 | mark_environment(gc.active_envs.buf[i]); |
124 | } | 179 | } |
125 | 180 | ||
126 | for (size_t i = 0; i < gc.roots.size; i++) { | 181 | for (size_t i = 0; i < gc.roots.size; i++) { |
@@ -129,28 +184,43 @@ mark_and_sweep(void) { | |||
129 | } | 184 | } |
130 | mark_obj(gc.roots.buf[i]); | 185 | mark_obj(gc.roots.buf[i]); |
131 | } | 186 | } |
132 | // dump_gc() | ||
133 | 187 | ||
134 | // Reset the free list. | 188 | // Reset the free list. |
135 | gc.fl_pos = 0; | 189 | gc.free_objects.position = 0; |
136 | gc.available_slots = 0; | 190 | gc.free_objects.size = 0; |
191 | gc.free_envs.position = 0; | ||
192 | gc.free_envs.size = 0; | ||
137 | 193 | ||
138 | // Sweep. | 194 | // Sweep. |
139 | for (size_t i = 0; i < gc.obj_cap; i++) { | 195 | for (size_t i = 0; i < gc.obj_cap; i++) { |
140 | Object *obj = &gc.obj_list[i]; | 196 | Object *obj = &gc.objects[i]; |
141 | if (!obj->marked) { | 197 | if (!obj->marked) { |
142 | // Free heap allocated memory for this object if needed. | 198 | // Free heap allocated memory for this object if needed. |
143 | if (obj->type == OBJ_TYPE_SYMBOL) { | 199 | if (obj->type == OBJ_TYPE_SYMBOL) { |
144 | free(obj->symbol); | 200 | free(obj->symbol); |
201 | obj->symbol = NULL; | ||
202 | obj->symbol_n = 0; | ||
145 | } else if (obj->type == OBJ_TYPE_STRING) { | 203 | } else if (obj->type == OBJ_TYPE_STRING) { |
146 | free(obj->string); | 204 | free(obj->string); |
205 | obj->string = NULL; | ||
206 | obj->string_n = 0; | ||
147 | } | 207 | } |
148 | gc.free_list[gc.available_slots++] = i; | 208 | gc.free_objects.buf[gc.free_objects.size++] = i; |
149 | } | 209 | } |
150 | obj->marked = false; | 210 | obj->marked = false; |
151 | } | 211 | } |
152 | for (size_t i = 0; i < gc.envs.size; i++) { | 212 | for (size_t i = 0; i < gc.envs.cap; i++) { |
153 | gc.envs.buf[i].marked = false; | 213 | Environment *env = &gc.envs.buf[i]; |
214 | if (!env->marked) { | ||
215 | if (env->buf != NULL) { | ||
216 | free(env->buf); | ||
217 | env->buf = NULL; | ||
218 | env->size = 0; | ||
219 | env->cap = 0; | ||
220 | } | ||
221 | gc.free_envs.buf[gc.free_envs.size++] = i; | ||
222 | } | ||
223 | env->marked = false; | ||
154 | } | 224 | } |
155 | } | 225 | } |
156 | 226 | ||
@@ -165,11 +235,11 @@ dump_gc(void) { | |||
165 | // for (size_t i = 0; i < gc.obj_cap; i++) { | 235 | // for (size_t i = 0; i < gc.obj_cap; i++) { |
166 | for (size_t i = 0; i < 20; i++) { | 236 | for (size_t i = 0; i < 20; i++) { |
167 | printf("i: %ld -> ", i); | 237 | printf("i: %ld -> ", i); |
168 | Object *obj = &gc.obj_list[i]; | 238 | Object *obj = &gc.objects[i]; |
169 | display(obj); | 239 | display(obj); |
170 | bool is_free = false; | 240 | bool is_free = false; |
171 | for (size_t j = 0; j < gc.obj_cap; j++) { | 241 | for (size_t j = 0; j < gc.obj_cap; j++) { |
172 | if (gc.free_list[j] == i) { | 242 | if (gc.free_objects.buf[j] == i) { |
173 | is_free = true; | 243 | is_free = true; |
174 | break; | 244 | break; |
175 | } | 245 | } |
@@ -179,16 +249,16 @@ dump_gc(void) { | |||
179 | } | 249 | } |
180 | printf("\n"); | 250 | printf("\n"); |
181 | } | 251 | } |
182 | printf("FREE OBJECTS: %ld\n", gc.available_slots); | 252 | printf("FREE OBJECTS: %ld\n", gc.free_objects.size); |
183 | printf("ENVIRONMENTS: %ld\n", gc.envs.size); | 253 | printf("ENVIRONMENTS: %ld\n", gc.envs.size); |
184 | } | 254 | } |
185 | 255 | ||
186 | Object * | 256 | Object * |
187 | alloc_object(ObjectType type) { | 257 | alloc_object(ObjectType type) { |
188 | if (gc.available_slots == 0) { | 258 | if (gc.free_objects.size == 0) { |
189 | mark_and_sweep(); | 259 | mark_and_sweep(); |
190 | if (gc.available_slots == 0) { | 260 | if (gc.free_objects.size == 0) { |
191 | fprintf(stderr, "NOT MORE MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n"); | 261 | fprintf(stderr, "NO MORE OBJ MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n"); |
192 | dump_gc(); | 262 | dump_gc(); |
193 | exit(EXIT_FAILURE); | 263 | exit(EXIT_FAILURE); |
194 | // TODO: grow heap tables. | 264 | // TODO: grow heap tables. |
@@ -204,8 +274,8 @@ alloc_object(ObjectType type) { | |||
204 | // later. | 274 | // later. |
205 | } | 275 | } |
206 | } | 276 | } |
207 | size_t slot = gc.free_list[gc.fl_pos++]; | 277 | size_t slot = gc.free_objects.buf[gc.free_objects.position++]; |
208 | gc.available_slots--; | 278 | gc.free_objects.size--; |
209 | Object *obj = get_obj(slot); | 279 | Object *obj = get_obj(slot); |
210 | obj->type = type; | 280 | obj->type = type; |
211 | return obj; | 281 | 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) { | |||
47 | global_env = env_create(NULL); | 47 | global_env = env_create(NULL); |
48 | // TODO: make sure we create symbols and strings only once (interning | 48 | // TODO: make sure we create symbols and strings only once (interning |
49 | // strings?) | 49 | // strings?) |
50 | push_active_env(global_env); | ||
50 | 51 | ||
51 | // Primitive symbols. | 52 | // Primitive symbols. |
52 | MAKE_ENV_VAR(global_env, "else", obj_true); | 53 | 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); | |||
5 | Object * | 5 | Object * |
6 | eval(Environment *env, Object *root) { | 6 | eval(Environment *env, Object *root) { |
7 | Object* lambda; | 7 | Object* lambda; |
8 | Object* ret = NULL; | ||
8 | bool recursion_active = false; | 9 | bool recursion_active = false; |
9 | eval_start: | 10 | eval_start: |
10 | switch (root->type) { | 11 | switch (root->type) { |
@@ -15,7 +16,8 @@ eval_start: | |||
15 | case OBJ_TYPE_BOOL: | 16 | case OBJ_TYPE_BOOL: |
16 | case OBJ_TYPE_NIL: | 17 | case OBJ_TYPE_NIL: |
17 | case OBJ_TYPE_STRING: { | 18 | case OBJ_TYPE_STRING: { |
18 | return root; | 19 | ret = root; |
20 | goto eval_success; | ||
19 | } break; | 21 | } break; |
20 | case OBJ_TYPE_SYMBOL: { | 22 | case OBJ_TYPE_SYMBOL: { |
21 | Object *val = env_lookup(env, root); | 23 | Object *val = env_lookup(env, root); |
@@ -26,7 +28,8 @@ eval_start: | |||
26 | }); | 28 | }); |
27 | return obj_err; | 29 | return obj_err; |
28 | } | 30 | } |
29 | return val; | 31 | ret = val; |
32 | goto eval_success; | ||
30 | } break; | 33 | } break; |
31 | case OBJ_TYPE_PAIR: { | 34 | case OBJ_TYPE_PAIR: { |
32 | if (root->car->type == OBJ_TYPE_SYMBOL) { | 35 | if (root->car->type == OBJ_TYPE_SYMBOL) { |
@@ -64,7 +67,8 @@ eval_start: | |||
64 | } | 67 | } |
65 | goto eval_start; | 68 | goto eval_start; |
66 | } | 69 | } |
67 | return val->proc(env, root->cdr); | 70 | ret = val->proc(env, root->cdr); |
71 | goto eval_success; | ||
68 | } | 72 | } |
69 | if (val->type == OBJ_TYPE_LAMBDA) { | 73 | if (val->type == OBJ_TYPE_LAMBDA) { |
70 | lambda = val; | 74 | lambda = val; |
@@ -86,8 +90,12 @@ eval_lambda: | |||
86 | args = root->cdr; | 90 | args = root->cdr; |
87 | Object *params = lambda->params; | 91 | Object *params = lambda->params; |
88 | if (!recursion_active) { | 92 | if (!recursion_active) { |
89 | env = env_extend(lambda->env, env); | ||
90 | recursion_active = true; | 93 | recursion_active = true; |
94 | // Protect current stack. | ||
95 | Environment *tmp = env_create(lambda->env); | ||
96 | push_active_env(tmp); | ||
97 | // Extend environment. | ||
98 | env = env_extend(tmp, env); | ||
91 | } | 99 | } |
92 | while (params != obj_nil) { | 100 | while (params != obj_nil) { |
93 | if (args == obj_nil) { | 101 | if (args == obj_nil) { |
@@ -138,6 +146,12 @@ eval_lambda: | |||
138 | .value = ERR_UNKNOWN_OBJ_TYPE, | 146 | .value = ERR_UNKNOWN_OBJ_TYPE, |
139 | }); | 147 | }); |
140 | return obj_err; | 148 | return obj_err; |
149 | eval_success: | ||
150 | if (recursion_active) { | ||
151 | // Remove stack protector. | ||
152 | pop_active_env(); | ||
153 | } | ||
154 | return ret; | ||
141 | } | 155 | } |
142 | 156 | ||
143 | Object * | 157 | Object * |