diff options
Diffstat (limited to 'src/treewalk/gc.c')
-rw-r--r-- | src/treewalk/gc.c | 199 |
1 files changed, 199 insertions, 0 deletions
diff --git a/src/treewalk/gc.c b/src/treewalk/gc.c new file mode 100644 index 0000000..358a07e --- /dev/null +++ b/src/treewalk/gc.c | |||
@@ -0,0 +1,199 @@ | |||
1 | #include "gc.h" | ||
2 | |||
3 | Environment * | ||
4 | alloc_env(void) { | ||
5 | if (array_size(gc.free_envs.offsets) == 0) { | ||
6 | mark_and_sweep(); | ||
7 | if (array_size(gc.free_envs.offsets) == 0) { | ||
8 | fprintf(stderr, "NO MORE ENV MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n"); | ||
9 | dump_gc(); | ||
10 | exit(EXIT_FAILURE); | ||
11 | // TODO: grow heap tables. | ||
12 | } | ||
13 | } | ||
14 | size_t slot = gc.free_envs.offsets[gc.free_envs.position++]; | ||
15 | array_head(gc.free_envs.offsets)->size--; | ||
16 | return &gc.envs[slot]; | ||
17 | } | ||
18 | |||
19 | void | ||
20 | push_root(Object *obj) { | ||
21 | array_push(gc.roots, obj); | ||
22 | } | ||
23 | |||
24 | Object * | ||
25 | pop_root(void) { | ||
26 | return array_pop(gc.roots); | ||
27 | } | ||
28 | |||
29 | void | ||
30 | push_active_env(Environment *env) { | ||
31 | array_push(gc.active_envs, env); | ||
32 | } | ||
33 | |||
34 | Environment * | ||
35 | pop_active_env(void) { | ||
36 | return array_pop(gc.active_envs); | ||
37 | } | ||
38 | |||
39 | void | ||
40 | gc_init(void) { | ||
41 | gc = (GC){0}; | ||
42 | |||
43 | array_init(gc.objects, GC_OBJS_CAP); | ||
44 | array_init(gc.roots, GC_ROOTS_CAP); | ||
45 | array_init(gc.active_envs, GC_ACTIVE_ENVS_CAP); | ||
46 | array_init(gc.envs, GC_ENVS_CAP); | ||
47 | array_init(gc.free_objects.offsets, GC_OBJS_CAP); | ||
48 | array_init(gc.free_envs.offsets, GC_ENVS_CAP); | ||
49 | |||
50 | // The free list stores the offset from the initial position for all | ||
51 | // available slots. | ||
52 | for (size_t i = 0; i < GC_OBJS_CAP; i++) { | ||
53 | array_push(gc.free_objects.offsets, i); | ||
54 | } | ||
55 | for (size_t i = 0; i < GC_ENVS_CAP; i++) { | ||
56 | array_push(gc.free_envs.offsets, i); | ||
57 | } | ||
58 | } | ||
59 | |||
60 | void | ||
61 | mark_environment(Environment *env) { | ||
62 | if (env == NULL || env->marked) { | ||
63 | return; | ||
64 | } | ||
65 | env->marked = true; | ||
66 | HashTablePair *pairs = env->table->pairs; | ||
67 | for (size_t i = 0; i < array_cap(pairs); i++) { | ||
68 | if (pairs[i].key != NULL) { | ||
69 | mark_obj(pairs[i].key); | ||
70 | mark_obj(pairs[i].value); | ||
71 | } | ||
72 | } | ||
73 | } | ||
74 | |||
75 | void | ||
76 | mark_obj(Object *obj) { | ||
77 | if (obj->marked) { | ||
78 | return; | ||
79 | } | ||
80 | obj->marked = true; | ||
81 | if (obj->type == OBJ_TYPE_PAIR) { | ||
82 | mark_obj(obj->car); | ||
83 | mark_obj(obj->cdr); | ||
84 | } | ||
85 | if (obj->type == OBJ_TYPE_LAMBDA) { | ||
86 | mark_obj(obj->params); | ||
87 | mark_obj(obj->body); | ||
88 | mark_environment(obj->env); | ||
89 | } | ||
90 | } | ||
91 | |||
92 | void | ||
93 | mark_and_sweep(void) { | ||
94 | // Mark. | ||
95 | for (size_t i = 0; i < array_size(gc.active_envs); i++) { | ||
96 | mark_environment(gc.active_envs[i]); | ||
97 | } | ||
98 | for (size_t i = 0; i < array_size(gc.roots); i++) { | ||
99 | mark_obj(gc.roots[i]); | ||
100 | } | ||
101 | |||
102 | // Reset the free list. | ||
103 | gc.free_objects.position = 0; | ||
104 | array_head(gc.free_objects.offsets)->size = 0; | ||
105 | gc.free_envs.position = 0; | ||
106 | array_head(gc.free_envs.offsets)->size = 0; | ||
107 | |||
108 | // Sweep. | ||
109 | for (size_t i = 0; i < array_cap(gc.objects); i++) { | ||
110 | Object *obj = &gc.objects[i]; | ||
111 | if (!obj->marked) { | ||
112 | // Free heap allocated memory for this object if needed. | ||
113 | if (obj->type == OBJ_TYPE_SYMBOL) { | ||
114 | array_free(obj->symbol); | ||
115 | } else if (obj->type == OBJ_TYPE_STRING) { | ||
116 | array_free(obj->string); | ||
117 | } | ||
118 | gc.free_objects.offsets[array_head(gc.free_objects.offsets)->size++] = i; | ||
119 | } | ||
120 | obj->marked = false; | ||
121 | } | ||
122 | for (size_t i = 0; i < array_cap(gc.envs); i++) { | ||
123 | Environment *env = &gc.envs[i]; | ||
124 | if (!env->marked) { | ||
125 | ht_free(env->table); | ||
126 | gc.free_envs.offsets[array_head(gc.free_envs.offsets)->size++] = i; | ||
127 | } | ||
128 | env->marked = false; | ||
129 | } | ||
130 | } | ||
131 | |||
132 | void | ||
133 | dump_gc(void) { | ||
134 | printf("-------------- ROOTS -------------- \n"); | ||
135 | for (size_t i = 0; i < array_size(gc.roots); i++) { | ||
136 | display(gc.roots[i]); | ||
137 | printf("\n"); | ||
138 | } | ||
139 | printf("--------- OBJECTS (TOP 20) -------- \n"); | ||
140 | for (size_t i = 0; i < 20; i++) { | ||
141 | printf("i: %ld -> ", i); | ||
142 | Object *obj = &gc.objects[i]; | ||
143 | display(obj); | ||
144 | bool is_free = false; | ||
145 | for (size_t j = 0; j < array_cap(gc.objects); j++) { | ||
146 | if (gc.free_objects.offsets[j] == i) { | ||
147 | is_free = true; | ||
148 | break; | ||
149 | } | ||
150 | } | ||
151 | if (is_free) { | ||
152 | printf(" [FREE]"); | ||
153 | } | ||
154 | printf("\n"); | ||
155 | } | ||
156 | printf("-------------- MISC --------------- \n"); | ||
157 | printf("gc.roots.size: %ld\n", array_size(gc.roots)); | ||
158 | printf("gc.roots.cap: %ld\n", array_size(gc.roots)); | ||
159 | printf("gc.active_envs.size: %ld\n", array_size(gc.active_envs)); | ||
160 | printf("gc.active_envs.cap: %ld\n", array_cap(gc.active_envs)); | ||
161 | printf("gc.obj_cap: %ld\n", array_cap(gc.objects)); | ||
162 | printf("gc.free_objects.size: %ld\n", array_size(gc.free_objects.offsets)); | ||
163 | printf("gc.free_objects.cap: %ld\n", array_cap(gc.free_objects.offsets)); | ||
164 | printf("gc.free_objects.position: %ld\n", gc.free_objects.position); | ||
165 | printf("array_size(gc.free_envs.offsets): %ld\n", array_size(gc.free_envs.offsets)); | ||
166 | printf("gc.free_envs.cap: %ld\n", array_cap(gc.free_envs.offsets)); | ||
167 | printf("gc.free_envs.position: %ld\n", gc.free_envs.position); | ||
168 | printf("gc.envs.size: %ld\n", array_size(gc.envs)); | ||
169 | printf("gc.envs.cap: %ld\n", array_cap(gc.envs)); | ||
170 | } | ||
171 | |||
172 | Object * | ||
173 | alloc_object(ObjectType type) { | ||
174 | if (array_head(gc.free_objects.offsets)->size == 0) { | ||
175 | mark_and_sweep(); | ||
176 | if (array_head(gc.free_objects.offsets)->size == 0) { | ||
177 | fprintf(stderr, "NO MORE OBJ MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n"); | ||
178 | dump_gc(); | ||
179 | exit(EXIT_FAILURE); | ||
180 | // TODO: grow heap tables. | ||
181 | // NOTE: When growing the tables, we WILL lose the pointer | ||
182 | // references! Should we work with offsets all the way? That is for | ||
183 | // cdr and car? Should we have a utility function? All in all, we | ||
184 | // need to refactor the codebase first to work with pointer offsets | ||
185 | // rather than objects. This issue is very important, if we are in | ||
186 | // the middle of an operation that tries to allocate memory but we | ||
187 | // had saved pointers to some object, the pointer references may be | ||
188 | // invalidated, crashing or worse, silently returning garbage! Let's | ||
189 | // move on for now implementing the GC and we will revisit this part | ||
190 | // later. | ||
191 | } | ||
192 | } | ||
193 | size_t slot = gc.free_objects.offsets[gc.free_objects.position++]; | ||
194 | array_head(gc.free_objects.offsets)->size--; | ||
195 | Object *obj = &gc.objects[slot]; | ||
196 | obj->type = type; | ||
197 | obj->marked = false; | ||
198 | return obj; | ||
199 | } | ||