blob: 8820ef55ea0a351193a1ac9288aa167fbac61fdb [file] [log] [blame]
swissChili6d6525e2021-06-15 21:20:53 -07001#include "gc.h"
2#include "lisp.h"
swissChilie9fec8b2021-06-22 13:59:33 -07003#include "plat/plat.h"
swissChili6d6525e2021-06-15 21:20:53 -07004
swissChili9e57da42021-06-15 22:22:46 -07005value_t *gc_base;
swissChilie9fec8b2021-06-22 13:59:33 -07006THREAD_LOCAL static unsigned int gc_mark;
swissChili6d6525e2021-06-15 21:20:53 -07007
swissChili9e57da42021-06-15 22:22:46 -07008void __attribute__((noinline)) gc_set_base_here()
9{
10 // Move the current stack top address to gc_base. This works nicely because
11 // it means that when another (presumably lisp) function is called right
12 // after this, the stack top for it will be the same as for this function.
13 asm("movl %%esp, %0" : "=g"(gc_base));
14}
15
swissChilie9fec8b2021-06-22 13:59:33 -070016void _mark(value_t value, unsigned int *marked)
swissChili9e57da42021-06-15 22:22:46 -070017{
18 if (heapp(value))
19 {
swissChilie9fec8b2021-06-22 13:59:33 -070020 void *pointer = (void *)(value & ~HEAP_MASK);
21 struct alloc *alloc = pointer - sizeof(struct alloc);
swissChili9e57da42021-06-15 22:22:46 -070022
swissChilie9fec8b2021-06-22 13:59:33 -070023 // Only recursively mark if this hasn't been marked yet. i.e. prevent
24 // marking circular references twice
25 if (alloc->mark != gc_mark)
26 {
27 ++*marked;
28
29 alloc->mark = gc_mark;
30
31 // printf("[ GC ] val =");
32 // printval(alloc_to_value(alloc), 2);
33
34 switch (alloc->type_tag)
35 {
36 case CONS_TAG: {
37 struct cons_alloc *cons = (struct cons_alloc *)alloc;
38 _mark(cons->cons.car, marked);
39 _mark(cons->cons.cdr, marked);
40 break;
41 }
swissChiliddc97542021-07-04 11:47:42 -070042 case CLOSURE_TAG: {
43 struct closure_alloc *closure = (void *)alloc;
44
45 for (int i = 0; i < closure->closure.num_captured; i++)
46 {
47 _mark(closure->closure.data[i], marked);
48 }
49
50 break;
51 }
swissChilie9fec8b2021-06-22 13:59:33 -070052 }
53 }
swissChili9e57da42021-06-15 22:22:46 -070054 }
swissChili6d6525e2021-06-15 21:20:53 -070055}
56
swissChilie9fec8b2021-06-22 13:59:33 -070057value_t alloc_to_value(struct alloc *a)
58{
59 void *val = ((void *)a) + sizeof(struct alloc);
60 return (unsigned int)val | a->type_tag;
61}
62
swissChili6d6525e2021-06-15 21:20:53 -070063void _sweep()
64{
swissChili5db22a02021-06-30 22:04:33 -070065 for (struct alloc *a = first_a; a;)
swissChilie9fec8b2021-06-22 13:59:33 -070066 {
swissChilib8fd4712021-06-23 15:32:04 -070067 if (pool_alive(a->pool) || a->mark == gc_mark)
68 {
69 // Marked or in living pool
swissChili5db22a02021-06-30 22:04:33 -070070 a = a->next;
swissChilib8fd4712021-06-23 15:32:04 -070071 }
72 else
73 {
swissChilib8fd4712021-06-23 15:32:04 -070074 // Free and remove from allocation list
75 struct alloc *p = a->prev, *n = a->next;
76 free_aligned(a);
77
78 a = n;
79
80 if (p)
81 p->next = n;
82
83 if (n)
84 n->prev = p;
85 }
swissChilie9fec8b2021-06-22 13:59:33 -070086 }
swissChili6d6525e2021-06-15 21:20:53 -070087}
88
89void _do_gc(unsigned int esp, unsigned int ebp)
90{
swissChili9e57da42021-06-15 22:22:46 -070091 value_t *esp_p = (value_t *)esp,
92 *ebp_p = (value_t *)ebp;
swissChili6d6525e2021-06-15 21:20:53 -070093
swissChilie9fec8b2021-06-22 13:59:33 -070094 unsigned int num_marked = 0;
95
96 gc_mark++;
97
swissChili9e57da42021-06-15 22:22:46 -070098 // For every stack frame until the base of the stack
99 while (esp_p < gc_base)
swissChili6d6525e2021-06-15 21:20:53 -0700100 {
swissChili9e57da42021-06-15 22:22:46 -0700101 // Walk up the stack until we reach either the frame pointer or the base
102 // of the stack. Basically walk to the top of this function's stack
103 // frame.
104 for (; esp_p < ebp_p && esp_p < gc_base; esp_p++)
105 {
swissChilie9fec8b2021-06-22 13:59:33 -0700106 _mark(*esp_p, &num_marked);
swissChili9e57da42021-06-15 22:22:46 -0700107 }
108
109 // Set the frame pointer to the frame pointer on the stack
110 ebp_p = (value_t *)*esp_p;
111
112 // Step up two stack slots, one for the frame pointer and one for the
113 // return address.
114 esp_p += 2;
swissChili6d6525e2021-06-15 21:20:53 -0700115 }
swissChili9e57da42021-06-15 22:22:46 -0700116
swissChilie9fec8b2021-06-22 13:59:33 -0700117 _sweep();
swissChili6d6525e2021-06-15 21:20:53 -0700118}
swissChilib8fd4712021-06-23 15:32:04 -0700119
120void free_all()
121{
122 for (struct alloc *a = first_a; a;)
123 {
124 struct alloc *next = a->next;
125 free_aligned(a);
126 a = next;
127 }
128}