diff options
Diffstat (limited to 'src/bootstrap/gc.c')
-rw-r--r-- | src/bootstrap/gc.c | 144 |
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 { | |||
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; |