diff options
Diffstat (limited to 'src/bootstrap/gc.c')
-rw-r--r-- | src/bootstrap/gc.c | 128 |
1 files changed, 99 insertions, 29 deletions
diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c index 8ca99b7..6e15c63 100644 --- a/src/bootstrap/gc.c +++ b/src/bootstrap/gc.c | |||
@@ -5,8 +5,15 @@ typedef struct RootNodes { | |||
5 | size_t cap; | 5 | size_t cap; |
6 | } RootNodes; | 6 | } RootNodes; |
7 | 7 | ||
8 | typedef struct Environments { | ||
9 | Environment *buf; | ||
10 | size_t size; | ||
11 | size_t cap; | ||
12 | } Environments; | ||
13 | |||
8 | typedef struct GC { | 14 | typedef struct GC { |
9 | RootNodes roots; | 15 | RootNodes roots; |
16 | Environments envs; | ||
10 | Object *obj_list; | 17 | Object *obj_list; |
11 | // Free list keeps track of the offset numbers from the obj_list | 18 | // Free list keeps track of the offset numbers from the obj_list |
12 | size_t *free_list; | 19 | size_t *free_list; |
@@ -16,11 +23,22 @@ typedef struct GC { | |||
16 | } GC; | 23 | } GC; |
17 | 24 | ||
18 | // FIXME: small value for testing purposes | 25 | // FIXME: small value for testing purposes |
19 | #define GC_INITIAL_HEAP 16 | 26 | // #define GC_INITIAL_HEAP 32 |
20 | #define GC_ROOTS_CAP 8 | 27 | #define GC_INITIAL_HEAP 1024 * 1.5 |
28 | #define GC_ROOTS_CAP 1024 * 1024 | ||
29 | #define GC_ENVS_CAP 1024 * 1024 | ||
21 | 30 | ||
22 | static GC gc; | 31 | static GC gc; |
23 | 32 | ||
33 | Environment * | ||
34 | alloc_env(void) { | ||
35 | if (gc.envs.size < gc.envs.cap) { | ||
36 | return &gc.envs.buf[gc.envs.size++]; | ||
37 | } | ||
38 | printf("error: not enough room for more environments\n"); | ||
39 | return NULL; | ||
40 | } | ||
41 | |||
24 | void | 42 | void |
25 | push_root(Object *obj) { | 43 | push_root(Object *obj) { |
26 | if (gc.roots.size == gc.roots.cap) { | 44 | if (gc.roots.size == gc.roots.cap) { |
@@ -38,13 +56,21 @@ pop_root(void) { | |||
38 | void | 56 | void |
39 | init_gc(void) { | 57 | init_gc(void) { |
40 | gc = (GC){ | 58 | gc = (GC){ |
59 | .free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t)), | ||
60 | .obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object)), | ||
41 | .obj_cap = GC_INITIAL_HEAP, | 61 | .obj_cap = GC_INITIAL_HEAP, |
42 | .available_slots = GC_INITIAL_HEAP, | 62 | .available_slots = GC_INITIAL_HEAP, |
63 | .envs = (Environments){ | ||
64 | .buf = malloc(GC_ENVS_CAP * sizeof(Environment)), | ||
65 | .size = 0, | ||
66 | .cap = GC_ENVS_CAP, | ||
67 | }, | ||
68 | .roots = (RootNodes){ | ||
69 | .buf = malloc(GC_ROOTS_CAP * sizeof(Object*)), | ||
70 | .size = 0, | ||
71 | .cap = GC_ROOTS_CAP, | ||
72 | }, | ||
43 | }; | 73 | }; |
44 | gc.free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t)); | ||
45 | gc.obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object)); | ||
46 | gc.roots.buf = malloc(GC_ROOTS_CAP * sizeof(Object*)); | ||
47 | gc.roots.cap = GC_ROOTS_CAP; | ||
48 | 74 | ||
49 | // The free list stores the offset from the initial position for all | 75 | // The free list stores the offset from the initial position for all |
50 | // available slots. | 76 | // available slots. |
@@ -55,7 +81,22 @@ init_gc(void) { | |||
55 | 81 | ||
56 | Object * | 82 | Object * |
57 | get_obj(size_t offset) { | 83 | get_obj(size_t offset) { |
58 | return gc.obj_list + offset; | 84 | return &gc.obj_list[offset]; |
85 | } | ||
86 | |||
87 | void mark_obj(Object *obj); | ||
88 | |||
89 | void | ||
90 | mark_environment(Environment *env) { | ||
91 | if (env->marked) { | ||
92 | return; | ||
93 | } | ||
94 | env->marked = true; | ||
95 | for (size_t i = 0; i < env->size; i++) { | ||
96 | EnvEntry entry = env->buf[i]; | ||
97 | mark_obj(entry.symbol); | ||
98 | mark_obj(entry.value); | ||
99 | } | ||
59 | } | 100 | } |
60 | 101 | ||
61 | void | 102 | void |
@@ -68,17 +109,27 @@ mark_obj(Object *obj) { | |||
68 | mark_obj(obj->car); | 109 | mark_obj(obj->car); |
69 | mark_obj(obj->cdr); | 110 | mark_obj(obj->cdr); |
70 | } | 111 | } |
112 | if (obj->type == OBJ_TYPE_LAMBDA) { | ||
113 | mark_obj(obj->params); | ||
114 | mark_obj(obj->body); | ||
115 | mark_environment(obj->env); | ||
116 | } | ||
71 | } | 117 | } |
72 | 118 | ||
73 | void | 119 | void |
74 | mark_and_sweep(void) { | 120 | mark_and_sweep(void) { |
75 | // Mark. | 121 | // Mark. |
122 | for (size_t i = 0; i < gc.envs.size; i++) { | ||
123 | mark_environment(&gc.envs.buf[i]); | ||
124 | } | ||
125 | |||
76 | for (size_t i = 0; i < gc.roots.size; i++) { | 126 | for (size_t i = 0; i < gc.roots.size; i++) { |
77 | if (gc.roots.buf[i]->marked) { | 127 | if (gc.roots.buf[i]->marked) { |
78 | continue; | 128 | continue; |
79 | } | 129 | } |
80 | mark_obj(gc.roots.buf[i]); | 130 | mark_obj(gc.roots.buf[i]); |
81 | } | 131 | } |
132 | // dump_gc() | ||
82 | 133 | ||
83 | // Reset the free list. | 134 | // Reset the free list. |
84 | gc.fl_pos = 0; | 135 | gc.fl_pos = 0; |
@@ -86,40 +137,59 @@ mark_and_sweep(void) { | |||
86 | 137 | ||
87 | // Sweep. | 138 | // Sweep. |
88 | for (size_t i = 0; i < gc.obj_cap; i++) { | 139 | for (size_t i = 0; i < gc.obj_cap; i++) { |
89 | if (!gc.obj_list[i].marked) { | 140 | Object *obj = &gc.obj_list[i]; |
141 | if (!obj->marked) { | ||
90 | // Free heap allocated memory for this object if needed. | 142 | // Free heap allocated memory for this object if needed. |
91 | Object obj = gc.obj_list[i]; | 143 | if (obj->type == OBJ_TYPE_SYMBOL) { |
92 | if (obj.type == OBJ_TYPE_SYMBOL) { | 144 | free(obj->symbol); |
93 | free(obj.symbol); | 145 | } else if (obj->type == OBJ_TYPE_STRING) { |
94 | } else if (obj.type == OBJ_TYPE_STRING) { | 146 | free(obj->string); |
95 | free(obj.string); | ||
96 | } | 147 | } |
97 | |||
98 | gc.free_list[gc.available_slots++] = i; | 148 | gc.free_list[gc.available_slots++] = i; |
99 | } | 149 | } |
100 | gc.obj_list[i].marked = false; | 150 | obj->marked = false; |
151 | } | ||
152 | for (size_t i = 0; i < gc.envs.size; i++) { | ||
153 | gc.envs.buf[i].marked = false; | ||
101 | } | 154 | } |
102 | } | 155 | } |
103 | 156 | ||
157 | void | ||
158 | dump_gc(void) { | ||
159 | printf("-------------- ROOTS -------------- \n"); | ||
160 | for (size_t i = 0; i < gc.roots.size; i++) { | ||
161 | display(gc.roots.buf[i]); | ||
162 | printf("\n"); | ||
163 | } | ||
164 | printf("------------- OBJECTS ------------- \n"); | ||
165 | // for (size_t i = 0; i < gc.obj_cap; i++) { | ||
166 | for (size_t i = 0; i < 20; i++) { | ||
167 | printf("i: %ld -> ", i); | ||
168 | Object *obj = &gc.obj_list[i]; | ||
169 | display(obj); | ||
170 | bool is_free = false; | ||
171 | for (size_t j = 0; j < gc.obj_cap; j++) { | ||
172 | if (gc.free_list[j] == i) { | ||
173 | is_free = true; | ||
174 | break; | ||
175 | } | ||
176 | } | ||
177 | if (is_free) { | ||
178 | printf(" [FREE]"); | ||
179 | } | ||
180 | printf("\n"); | ||
181 | } | ||
182 | printf("FREE OBJECTS: %ld\n", gc.available_slots); | ||
183 | printf("ENVIRONMENTS: %ld\n", gc.envs.size); | ||
184 | } | ||
185 | |||
104 | Object * | 186 | Object * |
105 | alloc_object(ObjectType type) { | 187 | alloc_object(ObjectType type) { |
106 | if (gc.available_slots == 0) { | 188 | if (gc.available_slots == 0) { |
107 | printf("triggering GC\n"); | ||
108 | mark_and_sweep(); | 189 | mark_and_sweep(); |
109 | if (gc.available_slots == 0) { | 190 | if (gc.available_slots == 0) { |
110 | printf("NOT MORE MEMORY AVAILABLE\n"); | 191 | printf("NOT MORE MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n"); |
111 | printf("-------------- ROOTS -------------- \n"); | 192 | dump_gc(); |
112 | for (size_t i = 0; i < gc.roots.size; i++) { | ||
113 | display(gc.roots.buf[i]); | ||
114 | printf("\n"); | ||
115 | } | ||
116 | printf("------------- OBJECTS ------------- \n"); | ||
117 | for (size_t i = 0; i < gc.obj_cap; i++) { | ||
118 | printf("i: %ld -> ", i); | ||
119 | Object *obj = &gc.obj_list[i]; | ||
120 | display(obj); | ||
121 | printf("\n"); | ||
122 | } | ||
123 | exit(EXIT_FAILURE); | 193 | exit(EXIT_FAILURE); |
124 | // TODO: grow heap tables. | 194 | // TODO: grow heap tables. |
125 | // NOTE: When growing the tables, we WILL lose the pointer | 195 | // NOTE: When growing the tables, we WILL lose the pointer |