simgear/nasal/gc.c

   1 #include "nasal.h"
   2 #include "data.h"
   3
   4 #define MIN_BLOCK_SIZE 256
   5
   6 // "type" for an object freed by the collector
   7 #define T_GCFREED 123 // DEBUG
   8
   9 struct Block {
  10     int   size;
  11     char* block;
  12 };
  13
  14 // Decremented every allocation.  When it reaches zero, we do a
  15 // garbage collection.  The value is reset to 1/2 of the total object
  16 // count each collection, which is sane: it ensures that no more than
  17 // 50% growth can happen between collections, and ensures that garbage
  18 // collection work is constant with allocation work (i.e. that O(N)
  19 // work is done only every O(1/2N) allocations).
  20 static int GlobalAllocCount = 256;
  21
  22 static void appendfree(struct naPool*p, struct naObj* o)
  23 {
  24     // Need more space?
  25     if(p->freesz <= p->nfree) {
  26         int i, n = 1+((3*p->nfree)>>1);
  27         void** newf = naAlloc(n * sizeof(void*));
  28         for(i=0; i<p->nfree; i++)
  29             newf[i] = p->free[i];
  30         naFree(p->free);
  31         p->free = newf;
  32         p->freesz = n;
  33     }
  34
  35     p->free[p->nfree++] = o;
  36 }
  37
  38 static void naCode_gcclean(struct naCode* o)
  39 {
  40     naFree(o->byteCode);  o->byteCode = 0;
  41     naFree(o->constants); o->constants = 0;
  42 }
  43
  44 static void naGhost_gcclean(struct naGhost* g)
  45 {
  46     if(g->ptr) g->gtype->destroy(g->ptr);
  47     g->ptr = 0;
  48 }
  49
  50 static void freeelem(struct naPool* p, struct naObj* o)
  51 {
  52     // Mark the object as "freed" for debugging purposes
  53     o->type = T_GCFREED; // DEBUG
  54
  55     // Free any intrinsic (i.e. non-garbage collected) storage the
  56     // object might have
  57     switch(p->type) {
  58     case T_STR:
  59         naStr_gcclean((struct naStr*)o);
  60         break;
  61     case T_VEC:
  62         naVec_gcclean((struct naVec*)o);
  63         break;
  64     case T_HASH:
  65         naHash_gcclean((struct naHash*)o);
  66         break;
  67     case T_CODE:
  68         naCode_gcclean((struct naCode*)o);
  69         break;
  70     case T_GHOST:
  71         naGhost_gcclean((struct naGhost*)o);
  72         break;
  73     }
  74
  75     // And add it to the free list
  76     appendfree(p, o);
  77 }
  78
  79 static void newBlock(struct naPool* p, int need)
  80 {
  81     int i;
  82     char* buf;
  83     struct Block* newblocks;
  84
  85     if(need < MIN_BLOCK_SIZE)
  86         need = MIN_BLOCK_SIZE;
  87
  88     newblocks = naAlloc((p->nblocks+1) * sizeof(struct Block));
  89     for(i=0; i<p->nblocks; i++) newblocks[i] = p->blocks[i];
  90     naFree(p->blocks);
  91     p->blocks = newblocks;
  92     buf = naAlloc(need * p->elemsz);
  93     naBZero(buf, need * p->elemsz);
  94     p->blocks[p->nblocks].size = need;
  95     p->blocks[p->nblocks].block = buf;
  96     p->nblocks++;
  97
  98     for(i=0; i<need; i++) {
  99         struct naObj* o = (struct naObj*)(buf + i*p->elemsz);
 100         o->mark = 0;
 101         o->type = p->type;
 102         appendfree(p, o);
 103     }
 104 }
 105
 106 void naGC_init(struct naPool* p, int type)
 107 {
 108     p->type = type;
 109     p->elemsz = naTypeSize(type);
 110     p->nblocks = 0;
 111     p->blocks = 0;
 112     p->nfree = 0;
 113     p->freesz = 0;
 114     p->free = 0;
 115     naGC_reap(p);
 116 }
 117
 118 int naGC_size(struct naPool* p)
 119 {
 120     int i, total=0;
 121     for(i=0; i<p->nblocks; i++)
 122         total += ((struct Block*)(p->blocks + i))->size;
 123     return total;
 124 }
 125
 126 struct naObj* naGC_get(struct naPool* p)
 127 {
 128     // Collect every GlobalAllocCount allocations.
 129     // This gets set to ~50% of the total object count each
 130     // collection (it's incremented in naGC_reap()).
 131     if(--GlobalAllocCount < 0) {
 132         GlobalAllocCount = 0;
 133         naGarbageCollect();
 134     }
 135
 136     // If we're out, then allocate an extra 12.5%
 137     if(p->nfree == 0)
 138         newBlock(p, naGC_size(p)/8);
 139     return p->free[--p->nfree];
 140 }
 141
 142 // Sets the reference bit on the object, and recursively on all
 143 // objects reachable from it.  Clumsy: uses C stack recursion, which
 144 // is slower than it need be and may cause problems on some platforms
 145 // due to the very large stack depths that result.
 146 void naGC_mark(naRef r)
 147 {
 148     int i;
 149
 150     if(IS_NUM(r) || IS_NIL(r))
 151         return;
 152
 153     if(r.ref.ptr.obj->mark == 1)
 154         return;
 155
 156     // Verify that the object hasn't been freed incorrectly:
 157     if(r.ref.ptr.obj->type == T_GCFREED) *(int*)0=0; // DEBUG
 158
 159     r.ref.ptr.obj->mark = 1;
 160     switch(r.ref.ptr.obj->type) {
 161     case T_VEC:
 162         for(i=0; i<r.ref.ptr.vec->size; i++)
 163             naGC_mark(r.ref.ptr.vec->array[i]);
 164         break;
 165     case T_HASH:
 166         if(r.ref.ptr.hash->table == 0)
 167             break;
 168         for(i=0; i < (1<<r.ref.ptr.hash->lgalloced); i++) {
 169             struct HashNode* hn = r.ref.ptr.hash->table[i];
 170             while(hn) {
 171                 naGC_mark(hn->key);
 172                 naGC_mark(hn->val);
 173                 hn = hn->next;
 174             }
 175         }
 176         break;
 177     case T_CODE:
 178         naGC_mark(r.ref.ptr.code->srcFile);
 179         for(i=0; i<r.ref.ptr.code->nConstants; i++)
 180             naGC_mark(r.ref.ptr.code->constants[i]);
 181         break;
 182     case T_CLOSURE:
 183         naGC_mark(r.ref.ptr.closure->namespace);
 184         naGC_mark(r.ref.ptr.closure->next);
 185         break;
 186     case T_FUNC:
 187         naGC_mark(r.ref.ptr.func->code);
 188         naGC_mark(r.ref.ptr.func->closure);
 189         break;
 190     }
 191 }
 192
 193 // Collects all the unreachable objects into a free list, and
 194 // allocates more space if needed.
 195 void naGC_reap(struct naPool* p)
 196 {
 197     int i, elem, total = 0;
 198     p->nfree = 0;
 199     for(i=0; i<p->nblocks; i++) {
 200         struct Block* b = p->blocks + i;
 201         total += b->size;
 202         for(elem=0; elem < b->size; elem++) {
 203             struct naObj* o = (struct naObj*)(b->block + elem * p->elemsz);
 204             if(o->mark == 0)
 205                 freeelem(p, o);
 206             o->mark = 0;
 207         }
 208     }
 209
 210     // Add 50% of our total to the global count
 211     GlobalAllocCount += total/2;
 212
 213     // Allocate more if necessary (try to keep 25-50% of the objects
 214     // available)
 215     if(p->nfree < total/4) {
 216         int used = total - p->nfree;
 217         int avail = total - used;
 218         int need = used/2 - avail;
 219         if(need > 0)
 220             newBlock(p, need);
 221     }
 222 }
 223