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