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
|
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "encoding.h"
#include "heap.h"
#include "panic.h"
#include "value.h"
struct heap new_heap(struct val_slice gc_roots)
{
return (struct heap) {
.buf = NULL,
.active = { .size = 0 },
.standby = { .size = 0 },
.free_ptr = 0,
.last_free = 0,
.gc_roots = gc_roots,
};
}
static bool forwarded(struct heap *h, value *p)
{
if (!is_pointer(*p)) {
return false;
}
value *q = to_pointer(*p);
return h->active.buf <= q && q <= h->active.buf + h->active.size;
}
static size_t alloc_size(value *p)
{
return p[-1] >> 1;
}
static value *simple_alloc(struct heap *h, int64_t size)
{
h->active.buf[h->free_ptr] = size << 1;
value *p = h->active.buf + h->free_ptr + 1;
h->free_ptr += size;
return p;
}
static value process_gc_value(struct heap *h, value val)
{
if (!is_pointer(val)) {
return val;
}
value *p = to_pointer(val);
if (forwarded(h, p)) {
return *p;
}
size_t size = alloc_size(p);
// Allocate space in the new buffer.
value *q = simple_alloc(h, size);
// Copy values, recursively modifying pointers.
for (size_t i = 0; i < size; i++) {
q[i] = process_gc_value(h, p[i]);
}
// Write forwarding pointer.
p[0] = from_pointer(q);
return from_pointer(q);
}
static void collect_garbage(struct heap *h)
{
if (h->free_ptr < 2 * h->last_free) {
return;
}
// Swap the heaps.
struct val_slice temp = h->active;
h->active = h->standby;
h->standby = temp;
h->free_ptr = 0;
for (size_t i = 0; i < h->gc_roots.size; i++ ) {
h->gc_roots.buf[i] = process_gc_value(h, h->gc_roots.buf[i]);
}
}
static void more_space(struct heap *h, int64_t size_hint)
{
size_t new_size = h->active.size * 2 + size_hint;
value *new_buf = calloc(2 * new_size, sizeof(value));
if (!new_buf) {
panicf("Out of memory!\n");
}
memcpy(new_buf, h->active.buf, h->active.size * sizeof(value));
free(h->buf);
h->buf = new_buf;
h->active = (struct val_slice) { .size = new_size, .buf = new_buf };
h->standby = (struct val_slice) { .size = new_size, .buf = new_buf + new_size };
}
value *alloc(struct heap *h, int64_t size)
{
if (size <= 0) {
panicf("Alloc of zero size!\n");
}
collect_garbage(h);
if (h->free_ptr + size >= h->active.size) {
more_space(h, size);
}
return simple_alloc(h, size);
}
|
