diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/bootstrap/gc.c | 110 |
1 files changed, 102 insertions, 8 deletions
diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c index fff4201..8ca99b7 100644 --- a/src/bootstrap/gc.c +++ b/src/bootstrap/gc.c | |||
@@ -1,26 +1,50 @@ | |||
1 | // Stack of root nodes. | ||
2 | typedef struct RootNodes { | ||
3 | Object **buf; | ||
4 | size_t size; | ||
5 | size_t cap; | ||
6 | } RootNodes; | ||
7 | |||
1 | typedef struct GC { | 8 | typedef struct GC { |
9 | RootNodes roots; | ||
2 | Object *obj_list; | 10 | Object *obj_list; |
3 | // Free list keeps track of the offset numbers from the obj_list | 11 | // Free list keeps track of the offset numbers from the obj_list |
4 | size_t *free_list; | 12 | size_t *free_list; |
5 | size_t obj_size; | ||
6 | size_t obj_cap; | 13 | size_t obj_cap; |
7 | size_t fl_pos; | 14 | size_t fl_pos; |
8 | size_t available_slots; | 15 | size_t available_slots; |
9 | } GC; | 16 | } GC; |
10 | 17 | ||
11 | // FIXME: small value for testing purposes | 18 | // FIXME: small value for testing purposes |
12 | #define GC_INITIAL_HEAP 100000 | 19 | #define GC_INITIAL_HEAP 16 |
20 | #define GC_ROOTS_CAP 8 | ||
13 | 21 | ||
14 | static GC gc; | 22 | static GC gc; |
15 | 23 | ||
16 | void | 24 | void |
25 | push_root(Object *obj) { | ||
26 | if (gc.roots.size == gc.roots.cap) { | ||
27 | gc.roots.cap *= 2; | ||
28 | gc.roots.buf = realloc(gc.roots.buf, gc.roots.cap * sizeof(Object *)); | ||
29 | } | ||
30 | gc.roots.buf[gc.roots.size++] = obj; | ||
31 | } | ||
32 | |||
33 | Object * | ||
34 | pop_root(void) { | ||
35 | return gc.roots.buf[gc.roots.size--]; | ||
36 | } | ||
37 | |||
38 | void | ||
17 | init_gc(void) { | 39 | init_gc(void) { |
18 | gc = (GC){ | 40 | gc = (GC){ |
19 | .obj_cap = GC_INITIAL_HEAP, | 41 | .obj_cap = GC_INITIAL_HEAP, |
20 | .available_slots = GC_INITIAL_HEAP, | 42 | .available_slots = GC_INITIAL_HEAP, |
21 | }; | 43 | }; |
22 | gc.free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t *)); | 44 | gc.free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t)); |
23 | gc.obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object *)); | 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; | ||
24 | 48 | ||
25 | // The free list stores the offset from the initial position for all | 49 | // The free list stores the offset from the initial position for all |
26 | // available slots. | 50 | // available slots. |
@@ -30,19 +54,89 @@ init_gc(void) { | |||
30 | } | 54 | } |
31 | 55 | ||
32 | Object * | 56 | Object * |
57 | get_obj(size_t offset) { | ||
58 | return gc.obj_list + offset; | ||
59 | } | ||
60 | |||
61 | void | ||
62 | mark_obj(Object *obj) { | ||
63 | if (obj->marked) { | ||
64 | return; | ||
65 | } | ||
66 | obj->marked = true; | ||
67 | if (obj->type == OBJ_TYPE_PAIR) { | ||
68 | mark_obj(obj->car); | ||
69 | mark_obj(obj->cdr); | ||
70 | } | ||
71 | } | ||
72 | |||
73 | void | ||
74 | mark_and_sweep(void) { | ||
75 | // Mark. | ||
76 | for (size_t i = 0; i < gc.roots.size; i++) { | ||
77 | if (gc.roots.buf[i]->marked) { | ||
78 | continue; | ||
79 | } | ||
80 | mark_obj(gc.roots.buf[i]); | ||
81 | } | ||
82 | |||
83 | // Reset the free list. | ||
84 | gc.fl_pos = 0; | ||
85 | gc.available_slots = 0; | ||
86 | |||
87 | // Sweep. | ||
88 | for (size_t i = 0; i < gc.obj_cap; i++) { | ||
89 | if (!gc.obj_list[i].marked) { | ||
90 | // Free heap allocated memory for this object if needed. | ||
91 | Object obj = gc.obj_list[i]; | ||
92 | if (obj.type == OBJ_TYPE_SYMBOL) { | ||
93 | free(obj.symbol); | ||
94 | } else if (obj.type == OBJ_TYPE_STRING) { | ||
95 | free(obj.string); | ||
96 | } | ||
97 | |||
98 | gc.free_list[gc.available_slots++] = i; | ||
99 | } | ||
100 | gc.obj_list[i].marked = false; | ||
101 | } | ||
102 | } | ||
103 | |||
104 | Object * | ||
33 | alloc_object(ObjectType type) { | 105 | alloc_object(ObjectType type) { |
34 | if (gc.available_slots == 0) { | 106 | if (gc.available_slots == 0) { |
35 | // TODO: trigger garbage collection. | 107 | printf("triggering GC\n"); |
108 | mark_and_sweep(); | ||
36 | if (gc.available_slots == 0) { | 109 | if (gc.available_slots == 0) { |
110 | printf("NOT MORE MEMORY AVAILABLE\n"); | ||
111 | printf("-------------- ROOTS -------------- \n"); | ||
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); | ||
37 | // TODO: grow heap tables. | 124 | // TODO: grow heap tables. |
38 | // NOTE: When growing the tables, we might lose the pointer | 125 | // NOTE: When growing the tables, we WILL lose the pointer |
39 | // references! Should we work with offsets all the way? That is for | 126 | // references! Should we work with offsets all the way? That is for |
40 | // cdr and car? Should we have a utility function? | 127 | // cdr and car? Should we have a utility function? All in all, we |
128 | // need to refactor the codebase first to work with pointer offsets | ||
129 | // rather than objects. This issue is very important, if we are in | ||
130 | // the middle of an operation that tries to allocate memory but we | ||
131 | // had saved pointers to some object, the pointer references may be | ||
132 | // invalidated, crashing or worse, silently returning garbage! Let's | ||
133 | // move on for now implementing the GC and we will revisit this part | ||
134 | // later. | ||
41 | } | 135 | } |
42 | } | 136 | } |
43 | size_t slot = gc.free_list[gc.fl_pos++]; | 137 | size_t slot = gc.free_list[gc.fl_pos++]; |
44 | gc.available_slots--; | 138 | gc.available_slots--; |
45 | Object *obj = gc.obj_list + slot; | 139 | Object *obj = get_obj(slot); |
46 | obj->type = type; | 140 | obj->type = type; |
47 | return obj; | 141 | return obj; |
48 | } | 142 | } |