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         // closures have the pointer in the cdr, not in the car as others
  90         temp = ram_get_car (visit);
  91
  92         if (IN_RAM(temp)) {
  93           IF_GC_TRACE(printf ("case 6\n"));
  94           ram_set_gc_tag0 (visit, GC_TAG_0_LEFT);
  95           ram_set_car (visit, stack);
  96
  97           goto push;
  98         }
  99
 100         IF_GC_TRACE(printf ("case 7\n"));
 101       }
 102       else
 103         IF_GC_TRACE(printf ("case 8\n"));
 104
 105       ram_set_gc_tag0 (visit, GC_TAG_0_LEFT);
 106     }
 107
 108   pop:
 109
 110     IF_GC_TRACE(printf ("pop    stack=%d  visit=%d (tag=%d)\n", stack, visit, ram_get_gc_tags (visit)>>6));
 111
 112     if (stack != NIL) {
 113       if (HAS_2_OBJECT_FIELDS(stack) && ram_get_gc_tag1 (stack)) {
 114         IF_GC_TRACE(printf ("case 9\n"));
 115
 116         temp = ram_get_cdr (stack);  /* pop through cdr */
 117         ram_set_cdr (stack, visit);
 118         visit = stack;
 119         stack = temp;
 120
 121         ram_set_gc_tag1(visit, GC_TAG_UNMARKED);
 122         // we unset the "1-left" bit
 123
 124         goto visit_field1;
 125       }
 126
 127       IF_GC_TRACE(printf ("case 11\n"));
 128
 129       temp = ram_get_car (stack);  /* pop through car */
 130       ram_set_car (stack, visit);
 131       visit = stack;
 132       stack = temp;
 133
 134       goto pop;
 135     }
 136   }
 137 }
 138
 139 #ifdef DEBUG_GC
 140 int max_live = 0;
 141 #endif
 142
 143 void sweep () {
 144   /* sweep phase */
 145
 146 #ifdef DEBUG_GC
 147   int n = 0;
 148 #endif
 149
 150   obj visit = MAX_RAM_ENCODING;
 151
 152   free_list = 0;
 153
 154   while (visit >= (MIN_RAM_ENCODING + ((glovars + 1) >> 1))) {
 155     // we don't want to sweep the global variables area
 156     if ((RAM_COMPOSITE(visit)
 157          && (ram_get_gc_tags (visit) == GC_TAG_UNMARKED)) // 2 mark bit
 158         || !(ram_get_gc_tags (visit) & GC_TAG_0_LEFT)) { // 1 mark bit
 159       /* unmarked? */
 160       if (RAM_VECTOR(visit)) {
 161         // when we sweep a vector, we also have to sweep its contents
 162         obj o = ram_get_cdr (visit);
 163         uint16 i = ram_get_car (visit); // number of elements
 164         ram_set_car (o, free_list_vec);
 165         ram_set_cdr (o, ((i + 3) >> 2)); // free length, in words
 166         free_list_vec = o;
 167         // TODO merge free spaces
 168       }
 169       ram_set_car (visit, free_list);
 170       free_list = visit;
 171     }
 172     else {
 173       if (RAM_COMPOSITE(visit))
 174         ram_set_gc_tags (visit, GC_TAG_UNMARKED);
 175       else // only 1 mark bit to unset
 176         ram_set_gc_tag0 (visit, GC_TAG_UNMARKED);
 177 #ifdef DEBUG_GC
 178       n++;
 179 #endif
 180     }
 181     visit--;
 182   }
 183
 184 #ifdef DEBUG_GC
 185   if (n > max_live) {
 186     max_live = n;
 187     printf ("**************** memory needed = %d\n", max_live+1);
 188     fflush (stdout);
 189   }
 190 #endif
 191 }
 192
 193 void gc () {
 194   uint8 i;
 195
 196   IF_TRACE(printf("\nGC BEGINS\n"));
 197
 198   IF_GC_TRACE(printf("arg1\n"));
 199   mark (arg1);
 200   IF_GC_TRACE(printf("arg2\n"));
 201   mark (arg2);
 202   IF_GC_TRACE(printf("arg3\n"));
 203   mark (arg3);
 204   IF_GC_TRACE(printf("arg4\n"));
 205   mark (arg4);
 206   IF_GC_TRACE(printf("cont\n"));
 207   mark (cont);
 208   IF_GC_TRACE(printf("env\n"));
 209   mark (env);
 210
 211   IF_GC_TRACE(printf("globals\n"));
 212   for (i=0; i<glovars; i++)
 213     mark (get_global (i));
 214
 215   sweep ();
 216 }
 217
 218 obj alloc_ram_cell () {
 219   obj o;
 220
 221 #ifdef DEBUG_GC
 222   gc ();
 223 #endif
 224
 225   if (free_list == 0) {
 226 #ifndef DEBUG_GC
 227     gc ();
 228     if (free_list == 0)
 229 #endif
 230       ERROR("alloc_ram_cell", "memory is full");
 231   }
 232
 233   o = free_list;
 234
 235   free_list = ram_get_car (o);
 236
 237   return o;
 238 }
 239
 240 obj alloc_ram_cell_init (uint8 f0, uint8 f1, uint8 f2, uint8 f3) {
 241   obj o = alloc_ram_cell ();
 242
 243   ram_set_field0 (o, f0);
 244   ram_set_field1 (o, f1);
 245   ram_set_field2 (o, f2);
 246   ram_set_field3 (o, f3);
 247
 248   return o;
 249 }
 250
 251 obj alloc_vec_cell (uint16 n) {
 252   obj o = free_list_vec;
 253   obj prec = 0;
 254   uint8 gc_done = 0;
 255
 256 #ifdef DEBUG_GC
 257   gc ();
 258   gc_done = 1;
 259 #endif
 260
 261   while ((ram_get_cdr (o) * 4) < n) { // free space too small
 262     if (o == 0) { // no free space, or none big enough
 263       if (gc_done) // we gc'd, but no space is big enough for the vector
 264         ERROR("alloc_vec_cell", "no room for vector");
 265 #ifndef DEBUG_GC
 266       gc ();
 267       gc_done = 1;
 268 #endif
 269       o = free_list_vec;
 270       prec = 0;
 271       continue;
 272     } // TODO merge adjacent free spaces, maybe compact ?
 273     prec = o;
 274     o = ram_get_car (o);
 275   }
 276
 277   // case 1 : the new vector fills every free word advertized, we remove the
 278   //  node from the free list
 279   if (((ram_get_cdr(o) * 4) - n) < 4) {
 280     if (prec)
 281       ram_set_car (prec, ram_get_car (o));
 282     else
 283       free_list_vec = ram_get_car (o);
 284   }
 285   // case 2 : there is still some space left in the free section, create a new
 286   //  node to represent this space
 287   else {
 288     obj new_free = o + ((n + 3) >> 2);
 289     if (prec)
 290       ram_set_car (prec, new_free);
 291     else
 292       free_list_vec = new_free;
 293     ram_set_car (new_free, ram_get_car (o));
 294     ram_set_cdr (new_free, ram_get_cdr (o) - ((n + 3) >> 2));
 295   }
 296
 297   return o;
 298 }