gc.c

   1 /* file: "gc.c" */
   2
   3 /*
   4  * Copyright 2004-2009 by Marc Feeley and Vincent St-Amour, All Rights Reserved.
   5  */
   6
   7 #include "picobit-vm.h"
   8
   9 void init_ram_heap () {
  10   uint8 i;
  11   obj o = MAX_RAM_ENCODING;
  12   uint16 bound = MIN_RAM_ENCODING + ((glovars + 1) >> 1);
  13
  14   free_list = 0;
  15
  16   while (o > bound) {
  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);
  21     free_list = o;
  22     o--;
  23   }
  24
  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));
  31
  32   for (i=0; i<glovars; i++)
  33     set_global (i, OBJ_FALSE);
  34
  35   arg1 = OBJ_FALSE;
  36   arg2 = OBJ_FALSE;
  37   arg3 = OBJ_FALSE;
  38   arg4 = OBJ_FALSE;
  39   cont = OBJ_FALSE;
  40   env  = OBJ_NULL;
  41 }
  42
  43
  44 void mark (obj temp) {
  45   /* mark phase */
  46
  47   obj stack;
  48   obj visit;
  49
  50   if (IN_RAM(temp)) {
  51     visit = NIL;
  52
  53   push:
  54
  55     stack = visit;
  56     visit = temp;
  57
  58     IF_GC_TRACE(printf ("push   stack=%d  visit=%d (tag=%d)\n", stack, visit, ram_get_gc_tags (visit)>>5));
  59
  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"));
  64     else {
  65       if (HAS_2_OBJECT_FIELDS(visit)) { // pairs and continuations
  66         IF_GC_TRACE(printf ("case 2\n"));
  67
  68       visit_field2:
  69
  70         temp = ram_get_cdr (visit);
  71
  72         if (IN_RAM(temp)) {
  73           IF_GC_TRACE(printf ("case 3\n"));
  74           ram_set_gc_tags (visit, GC_TAG_1_LEFT);
  75           ram_set_cdr (visit, stack);
  76           goto push;
  77         }
  78
  79         IF_GC_TRACE(printf ("case 4\n"));
  80
  81         goto visit_field1;
  82       }
  83
  84       if (HAS_1_OBJECT_FIELD(visit)) {
  85         IF_GC_TRACE(printf ("case 5\n"));
  86
  87       visit_field1:
  88
  89         temp = ram_get_car (visit);
  90
  91         if (IN_RAM(temp)) {
  92           IF_GC_TRACE(printf ("case 6\n"));
  93           ram_set_gc_tag0 (visit, GC_TAG_0_LEFT);
  94           ram_set_car (visit, stack);
  95
  96           goto push;
  97         }
  98
  99         IF_GC_TRACE(printf ("case 7\n"));
 100       }
 101       else
 102         IF_GC_TRACE(printf ("case 8\n"));
 103
 104       ram_set_gc_tag0 (visit, GC_TAG_0_LEFT);
 105     }
 106
 107   pop:
 108
 109     IF_GC_TRACE(printf ("pop    stack=%d  visit=%d (tag=%d)\n", stack, visit, ram_get_gc_tags (visit)>>6));
 110
 111     if (stack != NIL) {
 112       if (HAS_2_OBJECT_FIELDS(stack) && ram_get_gc_tag1 (stack)) {
 113         IF_GC_TRACE(printf ("case 9\n"));
 114
 115         temp = ram_get_cdr (stack);  /* pop through cdr */
 116         ram_set_cdr (stack, visit);
 117         visit = stack;
 118         stack = temp;
 119
 120         ram_set_gc_tag1(visit, GC_TAG_UNMARKED);
 121         // we unset the "1-left" bit
 122
 123         goto visit_field1;
 124       }
 125
 126       IF_GC_TRACE(printf ("case 11\n"));
 127
 128       temp = ram_get_car (stack);  /* pop through car */
 129       ram_set_car (stack, visit);
 130       visit = stack;
 131       stack = temp;
 132
 133       goto pop;
 134     }
 135   }
 136 }
 137
 138 #ifdef DEBUG_GC
 139 int max_live = 0;
 140 #endif
 141
 142 void sweep () {
 143   /* sweep phase */
 144
 145 #ifdef DEBUG_GC
 146   int n = 0;
 147 #endif
 148
 149   obj visit = MAX_RAM_ENCODING;
 150
 151   free_list = 0;
 152
 153   while (visit >= (MIN_RAM_ENCODING + ((glovars + 1) >> 1))) {
 154     // we don't want to sweep the global variables area
 155     if ((RAM_COMPOSITE(visit)
 156          && (ram_get_gc_tags (visit) == GC_TAG_UNMARKED)) // 2 mark bit
 157         || !(ram_get_gc_tags (visit) & GC_TAG_0_LEFT)) { // 1 mark bit
 158       /* unmarked? */
 159       if (RAM_VECTOR(visit)) {
 160         // when we sweep a vector, we also have to sweep its contents
 161         obj o = ram_get_cdr (visit);
 162         uint16 i = ram_get_car (visit); // number of elements
 163         ram_set_car (o, free_list_vec);
 164         ram_set_cdr (o, ((i + 3) >> 2)); // free length, in words
 165         free_list_vec = o;
 166         // TODO merge free spaces
 167       }
 168       ram_set_car (visit, free_list);
 169       free_list = visit;
 170     }
 171     else {
 172       if (RAM_COMPOSITE(visit))
 173         ram_set_gc_tags (visit, GC_TAG_UNMARKED);
 174       else // only 1 mark bit to unset
 175         ram_set_gc_tag0 (visit, GC_TAG_UNMARKED);
 176 #ifdef DEBUG_GC
 177       n++;
 178 #endif
 179     }
 180     visit--;
 181   }
 182
 183 #ifdef DEBUG_GC
 184   if (n > max_live) {
 185     max_live = n;
 186     printf ("**************** memory needed = %d\n", max_live+1);
 187     fflush (stdout);
 188   }
 189 #endif
 190 }
 191
 192 void gc () {
 193   uint8 i;
 194
 195   IF_TRACE(printf("\nGC BEGINS\n"));
 196
 197   IF_GC_TRACE(printf("arg1\n"));
 198   mark (arg1);
 199   IF_GC_TRACE(printf("arg2\n"));
 200   mark (arg2);
 201   IF_GC_TRACE(printf("arg3\n"));
 202   mark (arg3);
 203   IF_GC_TRACE(printf("arg4\n"));
 204   mark (arg4);
 205   IF_GC_TRACE(printf("cont\n"));
 206   mark (cont);
 207   IF_GC_TRACE(printf("env\n"));
 208   mark (env);
 209
 210   IF_GC_TRACE(printf("globals\n"));
 211   for (i=0; i<glovars; i++)
 212     mark (get_global (i));
 213
 214   sweep ();
 215 }
 216
 217 obj alloc_ram_cell () {
 218   obj o;
 219
 220 #ifdef DEBUG_GC
 221   gc ();
 222 #endif
 223
 224   if (free_list == 0) {
 225 #ifndef DEBUG_GC
 226     gc ();
 227     if (free_list == 0)
 228 #endif
 229       ERROR("alloc_ram_cell", "memory is full");
 230   }
 231
 232   o = free_list;
 233
 234   free_list = ram_get_car (o);
 235
 236   return o;
 237 }
 238
 239 obj alloc_ram_cell_init (uint8 f0, uint8 f1, uint8 f2, uint8 f3) {
 240   obj o = alloc_ram_cell ();
 241
 242   ram_set_field0 (o, f0);
 243   ram_set_field1 (o, f1);
 244   ram_set_field2 (o, f2);
 245   ram_set_field3 (o, f3);
 246
 247   return o;
 248 }
 249
 250 obj alloc_vec_cell (uint16 n) {
 251   obj o = free_list_vec;
 252   obj prec = 0;
 253   uint8 gc_done = 0;
 254
 255 #ifdef DEBUG_GC
 256   gc ();
 257   gc_done = 1;
 258 #endif
 259
 260   while ((ram_get_cdr (o) * 4) < n) { // free space too small
 261     if (o == 0) { // no free space, or none big enough
 262       if (gc_done) // we gc'd, but no space is big enough for the vector
 263         ERROR("alloc_vec_cell", "no room for vector");
 264 #ifndef DEBUG_GC
 265       gc ();
 266       gc_done = 1;
 267 #endif
 268       o = free_list_vec;
 269       prec = 0;
 270       continue;
 271     } // TODO merge adjacent free spaces, maybe compact ?
 272     prec = o;
 273     o = ram_get_car (o);
 274   }
 275
 276   // case 1 : the new vector fills every free word advertized, we remove the
 277   //  node from the free list
 278   if (((ram_get_cdr(o) * 4) - n) < 4) {
 279     if (prec)
 280       ram_set_car (prec, ram_get_car (o));
 281     else
 282       free_list_vec = ram_get_car (o);
 283   }
 284   // case 2 : there is still some space left in the free section, create a new
 285   //  node to represent this space
 286   else {
 287     obj new_free = o + ((n + 3) >> 2);
 288     if (prec)
 289       ram_set_car (prec, new_free);
 290     else
 291       free_list_vec = new_free;
 292     ram_set_car (new_free, ram_get_car (o));
 293     ram_set_cdr (new_free, ram_get_cdr (o) - ((n + 3) >> 2));
 294   }
 295
 296   return o;
 297 }