4 * Copyright 2004-2009 by Marc Feeley and Vincent St-Amour, All Rights Reserved.
7 #include "picobit-vm.h"
9 void init_ram_heap () {
11 obj o
= MAX_RAM_ENCODING
;
12 uint16 bound
= MIN_RAM_ENCODING
+ ((glovars
+ 1) >> 1);
17 // we don't want to add globals to the free list, and globals occupy the
18 // beginning of memory at the rate of 2 globals per word (car and cdr)
19 ram_set_gc_tags (o
, GC_TAG_UNMARKED
);
20 ram_set_car (o
, free_list
);
25 free_list_vec
= MIN_VEC_ENCODING
;
26 ram_set_car (free_list_vec
, 0);
27 // each node of the free list must know the free length that follows it
28 // this free length is stored in words, not in bytes
29 // if we did count in bytes, the number might need more than 13 bits
30 ram_set_cdr (free_list_vec
, (VEC_BYTES
>> 2));
32 for (i
=0; i
<glovars
; i
++)
33 set_global (i
, OBJ_FALSE
);
44 void mark (obj temp
) {
58 IF_GC_TRACE(printf ("push stack=%d visit=%d (tag=%d)\n", stack
, visit
, ram_get_gc_tags (visit
)>>5));
60 if ((HAS_1_OBJECT_FIELD (visit
) && ram_get_gc_tag0 (visit
))
61 || (HAS_2_OBJECT_FIELDS (visit
)
62 && (ram_get_gc_tags (visit
) != GC_TAG_UNMARKED
)))
63 IF_GC_TRACE(printf ("case 1\n"));
65 if (HAS_2_OBJECT_FIELDS(visit
)) { // pairs and continuations
66 IF_GC_TRACE(printf ("case 2\n"));
70 temp
= ram_get_cdr (visit
);
73 IF_GC_TRACE(printf ("case 3\n"));
74 ram_set_gc_tags (visit
, GC_TAG_1_LEFT
);
75 ram_set_cdr (visit
, stack
);
79 IF_GC_TRACE(printf ("case 4\n"));
84 if (HAS_1_OBJECT_FIELD(visit
)) {
85 IF_GC_TRACE(printf ("case 5\n"));
89 // closures have the pointer in the cdr, not in the car as others
90 if (RAM_CLOSURE(visit
))
91 temp
= ram_get_cdr (visit
);
93 temp
= ram_get_car (visit
);
96 IF_GC_TRACE(printf ("case 6\n"));
97 ram_set_gc_tag0 (visit
, GC_TAG_0_LEFT
);
98 if (RAM_CLOSURE(visit
))
99 ram_set_cdr (visit
, stack
);
101 ram_set_car (visit
, stack
);
106 IF_GC_TRACE(printf ("case 7\n"));
109 IF_GC_TRACE(printf ("case 8\n"));
111 ram_set_gc_tag0 (visit
, GC_TAG_0_LEFT
);
116 IF_GC_TRACE(printf ("pop stack=%d visit=%d (tag=%d)\n", stack
, visit
, ram_get_gc_tags (visit
)>>6));
119 if (HAS_2_OBJECT_FIELDS(stack
) && ram_get_gc_tag1 (stack
)) {
120 IF_GC_TRACE(printf ("case 9\n"));
122 temp
= ram_get_cdr (stack
); /* pop through cdr */
123 ram_set_cdr (stack
, visit
);
127 ram_set_gc_tag1(visit
, GC_TAG_UNMARKED
);
128 // we unset the "1-left" bit
133 if (RAM_CLOSURE(stack
)) {
134 // closures have one object field, but it's in the cdr
135 IF_GC_TRACE(printf ("case 10\n"));
137 temp
= ram_get_cdr (stack
); /* pop through cdr */
138 ram_set_cdr (stack
, visit
);
145 IF_GC_TRACE(printf ("case 11\n"));
147 temp
= ram_get_car (stack
); /* pop through car */
148 ram_set_car (stack
, visit
);
168 obj visit
= MAX_RAM_ENCODING
;
172 while (visit
>= (MIN_RAM_ENCODING
+ ((glovars
+ 1) >> 1))) {
173 // we don't want to sweep the global variables area
174 if ((RAM_COMPOSITE(visit
)
175 && (ram_get_gc_tags (visit
) == GC_TAG_UNMARKED
)) // 2 mark bit
176 || !(ram_get_gc_tags (visit
) & GC_TAG_0_LEFT
)) { // 1 mark bit
178 if (RAM_VECTOR(visit
)) {
179 // when we sweep a vector, we also have to sweep its contents
180 obj o
= ram_get_cdr (visit
);
181 uint16 i
= ram_get_car (visit
); // number of elements
182 ram_set_car (o
, free_list_vec
);
183 ram_set_cdr (o
, ((i
+ 3) >> 2)); // free length, in words
185 // TODO merge free spaces
187 ram_set_car (visit
, free_list
);
191 if (RAM_COMPOSITE(visit
))
192 ram_set_gc_tags (visit
, GC_TAG_UNMARKED
);
193 else // only 1 mark bit to unset
194 ram_set_gc_tag0 (visit
, GC_TAG_UNMARKED
);
205 printf ("**************** memory needed = %d\n", max_live
+1);
214 IF_TRACE(printf("\nGC BEGINS\n"));
216 IF_GC_TRACE(printf("arg1\n"));
218 IF_GC_TRACE(printf("arg2\n"));
220 IF_GC_TRACE(printf("arg3\n"));
222 IF_GC_TRACE(printf("arg4\n"));
224 IF_GC_TRACE(printf("arg5\n"));
226 IF_GC_TRACE(printf("cont\n"));
228 IF_GC_TRACE(printf("env\n"));
231 IF_GC_TRACE(printf("globals\n"));
232 for (i
=0; i
<glovars
; i
++)
233 mark (get_global (i
));
238 obj
alloc_ram_cell () {
245 if (free_list
== 0) {
250 ERROR("alloc_ram_cell", "memory is full");
255 free_list
= ram_get_car (o
);
260 obj
alloc_ram_cell_init (uint8 f0
, uint8 f1
, uint8 f2
, uint8 f3
) {
261 obj o
= alloc_ram_cell ();
263 ram_set_field0 (o
, f0
);
264 ram_set_field1 (o
, f1
);
265 ram_set_field2 (o
, f2
);
266 ram_set_field3 (o
, f3
);
271 obj
alloc_vec_cell (uint16 n
) {
272 obj o
= free_list_vec
;
281 while ((ram_get_cdr (o
) * 4) < n
) { // free space too small
282 if (o
== 0) { // no free space, or none big enough
283 if (gc_done
) // we gc'd, but no space is big enough for the vector
284 ERROR("alloc_vec_cell", "no room for vector");
292 } // TODO merge adjacent free spaces, maybe compact ?
297 // case 1 : the new vector fills every free word advertized, we remove the
298 // node from the free list
299 if (((ram_get_cdr(o
) * 4) - n
) < 4) {
301 ram_set_car (prec
, ram_get_car (o
));
303 free_list_vec
= ram_get_car (o
);
305 // case 2 : there is still some space left in the free section, create a new
306 // node to represent this space
308 obj new_free
= o
+ ((n
+ 3) >> 2);
310 ram_set_car (prec
, new_free
);
312 free_list_vec
= new_free
;
313 ram_set_car (new_free
, ram_get_car (o
));
314 ram_set_cdr (new_free
, ram_get_cdr (o
) - ((n
+ 3) >> 2));