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
|
#include <lcq/pit/arena.h>
#include <lcq/pit/runtime/gc.h>
/* copy a heavy value from fromspace to tospace, returning its new index */
static i64 gc_copy(pit_runtime *rt, pit_value_heavy *h) {
if (h->hsort == PIT_VALUE_HEAVY_SORT_FORWARDING_POINTER) {
return h->in.forwarding_pointer;
} else {
i64 ret = rt->backbuffer->next;
pit_value_heavy *g = pit_arena_alloc(rt->backbuffer);
*g = *h;
h->hsort = PIT_VALUE_HEAVY_SORT_FORWARDING_POINTER;
h->in.forwarding_pointer = ret;
return ret;
}
}
/* copy some lisp value from fromspace to tospace, returning the new value */
/* (this only changes heavy values, since they live on the heap) */
static pit_value gc_copy_value(pit_runtime *rt, pit_value v) {
if (pit_value_sort(v) == PIT_VALUE_SORT_REF) {
pit_ref r = pit_value_as_ref(rt, v);
pit_value_heavy *h = pit_value_ref_deref(rt, r);
i64 new = gc_copy(rt, h);
pit_annotation *ann = pit_annotation_get(rt, r);
if (ann != NULL) {
if (pit_hashtable_insert(pit_ref, pit_annotation)(rt->annotations_backbuffer, new, *ann) < 0)
pit_error(rt, "annotation overflow");
}
return pit_value_ref_new(rt, new);
} else {
return v;
}
}
/* collect garbage */
/* this uses Cheney's algorithm: https://en.wikipedia.org/wiki/Cheney%27s_algorithm */
/* note that only the symbol table, saved bindings, and VM state (code / value stacks) are roots */
/* any pit_value saved elsewhere could be invalidated by garbage collection if it is unreachable! */
void pit_gc(pit_runtime *rt) {
rt->frozen_values = 0;
rt->frozen_symtab = 0;
pit_arena *fromspace = rt->heap;
pit_arena *tospace = rt->backbuffer;
pit_hashtable(pit_ref, pit_annotation) *fromspace_ann = rt->annotations;
pit_hashtable(pit_ref, pit_annotation) *tospace_ann = rt->annotations_backbuffer;
pit_arena_reset(tospace);
pit_hashtable_reset(pit_ref, pit_annotation)(tospace_ann);
/* populate tospace with immediately reachable values */
/* any values saved directly to the runtime are reachable */
rt->msg_out_of_memory = gc_copy_value(rt, rt->msg_out_of_memory);
/* everything on the call stack is reachable */
for (i64 i = 0; i < rt->callstack->next; ++i) {
pit_callstack_entry *ent = pit_vec_get(pit_callstack_entry)(rt->callstack, i);
if (ent == NULL) continue; /* TODO warn on failure here? */
ent->tag = gc_copy_value(rt, ent->tag);
ent->bound = gc_copy_value(rt, ent->bound);
ent->code = gc_copy_value(rt, ent->code);
}
/* the symbol table is reachable */
for (i64 i = 0; i < rt->symtab->next; ++i) {
pit_symtab_entry *ent = pit_vec_get(pit_symtab_entry)(rt->symtab, i);
if (ent == NULL) continue; /* TODO warn on failure here? */
ent->name = gc_copy_value(rt, ent->name);
ent->value = gc_copy_value(rt, ent->value);
ent->function = gc_copy_value(rt, ent->function);
}
/* all saved bindings are reachable */
for (i64 i = 0; i < rt->saved_bindings->next; ++i) {
pit_value *v = pit_vec_get(pit_value)(rt->saved_bindings, i);
if (v != NULL) *v = gc_copy_value(rt, *v); /* TODO warn on failure here? */
}
/* the evaluation stack is reachable */
for (i64 i = 0; i < rt->result_stack->next; ++i) {
pit_value *v = pit_vec_get(pit_value)(rt->result_stack, i);
if (v != NULL) *v = gc_copy_value(rt, *v); /* TODO warn on failure here? */
}
/* recursively populate all reachable values from that initial set */
for (i64 scan = 0; scan < tospace->next; ++scan) {
pit_value_heavy *h = pit_arena_get(tospace, scan);
switch (h->hsort) {
case PIT_VALUE_HEAVY_SORT_CELL:
h->in.cell = gc_copy_value(rt, h->in.cell);
break;
case PIT_VALUE_HEAVY_SORT_CONS:
h->in.cons.car = gc_copy_value(rt, h->in.cons.car);
h->in.cons.cdr = gc_copy_value(rt, h->in.cons.cdr);
break;
case PIT_VALUE_HEAVY_SORT_ARRAY: {
i64 byte_len = 0; pit_mul(&byte_len, sizeof(pit_value), h->in.array.len);
pit_value *data = pit_arena_alloc_back(tospace, byte_len);
for (i64 i = 0; i < h->in.array.len; ++i) {
data[i] = gc_copy_value(rt, h->in.array.data[i]);
}
h->in.array.data = data;
break;
}
case PIT_VALUE_HEAVY_SORT_BYTES: {
u8 *data = pit_arena_alloc_back(tospace, h->in.bytes.len);
for (i64 i = 0; i < h->in.bytes.len; ++i) {
data[i] = h->in.bytes.data[i];
}
h->in.bytes.data = data;
break;
}
case PIT_VALUE_HEAVY_SORT_FUNC:
h->in.func.nm = gc_copy_value(rt, h->in.func.nm);
h->in.func.closure = gc_copy_value(rt, h->in.func.closure);
break;
case PIT_VALUE_HEAVY_SORT_NATIVEFUNC: break;
case PIT_VALUE_HEAVY_SORT_NATIVEDATA:
h->in.nativedata.tag = gc_copy_value(rt, h->in.nativedata.tag);
break;
case PIT_VALUE_HEAVY_SORT_FORWARDING_POINTER:
pit_error(rt, "garbage collection broken! encountered forwarding pointer in to-space");
break;
}
}
rt->heap = tospace;
rt->backbuffer = fromspace;
rt->annotations = tospace_ann;
rt->annotations_backbuffer = fromspace_ann;
pit_hashtable_reset(pit_ref, pit_annotation)(rt->annotations_backbuffer);
}
/* collect garbage if necessary. this is run between every instruction evaluation in the VM. */
/* currently we use a simple heuristic: if the heap is using more than 80% of the available space */
/* note that this is could be weird in a heap with very few heavy values but a lot of data (strings etc.) */
/* TODO do research on better heuristics */
void pit_gc_if_necessary(pit_runtime *rt) {
if (pit_arena_byte_idx(rt->heap, rt->heap->next * 5) > rt->heap->back * 4) {
pit_gc(rt);
}
}
|
