simgear/nasal/gc.c

   1 #include "nasal.h"
   2 #include "data.h"
   3 #include "code.h"
   4
   5 #define MIN_BLOCK_SIZE 256
   6
   7 static void reap(struct naPool* p);
   8 static void mark(naRef r);
   9
  10 struct Block {
  11     int   size;
  12     char* block;
  13     struct Block* next;
  14 };
  15
  16 // Must be called with the giant exclusive lock!
  17 static void freeDead()
  18 {
  19     int i;
  20     for(i=0; i<globals->ndead; i++)
  21         naFree(globals->deadBlocks[i]);
  22     globals->ndead = 0;
  23 }
  24
  25 static void marktemps(struct Context* c)
  26 {
  27     int i;
  28     naRef r = naNil();
  29     for(i=0; i<c->ntemps; i++) {
  30         r.ref.ptr.obj = c->temps[i];
  31         mark(r);
  32     }
  33 }
  34
  35 // Must be called with the big lock!
  36 static void garbageCollect()
  37 {
  38     int i;
  39     struct Context* c;
  40     globals->allocCount = 0;
  41     c = globals->allContexts;
  42     while(c) {
  43         for(i=0; i<NUM_NASAL_TYPES; i++)
  44             c->nfree[i] = 0;
  45         for(i=0; i < c->fTop; i++) {
  46             mark(c->fStack[i].func);
  47             mark(c->fStack[i].locals);
  48         }
  49         for(i=0; i < c->opTop; i++)
  50             mark(c->opStack[i]);
  51         mark(c->dieArg);
  52         marktemps(c);
  53         c = c->nextAll;
  54     }
  55
  56     mark(globals->save);
  57     mark(globals->symbols);
  58     mark(globals->meRef);
  59     mark(globals->argRef);
  60     mark(globals->parentsRef);
  61
  62     // Finally collect all the freed objects
  63     for(i=0; i<NUM_NASAL_TYPES; i++)
  64         reap(&(globals->pools[i]));
  65
  66     // Make enough space for the dead blocks we need to free during
  67     // execution.  This works out to 1 spot for every 2 live objects,
  68     // which should be limit the number of bottleneck operations
  69     // without imposing an undue burden of extra "freeable" memory.
  70     if(globals->deadsz < globals->allocCount) {
  71         globals->deadsz = globals->allocCount;
  72         if(globals->deadsz < 256) globals->deadsz = 256;
  73         naFree(globals->deadBlocks);
  74         globals->deadBlocks = naAlloc(sizeof(void*) * globals->deadsz);
  75     }
  76     globals->needGC = 0;
  77 }
  78
  79 void naModLock()
  80 {
  81     LOCK();
  82     globals->nThreads++;
  83     UNLOCK();
  84     naCheckBottleneck();
  85 }
  86
  87 void naModUnlock()
  88 {
  89     LOCK();
  90     globals->nThreads--;
  91     UNLOCK();
  92 }
  93
  94 // Must be called with the main lock.  Engages the "bottleneck", where
  95 // all threads will block so that one (the last one to call this
  96 // function) can run alone.  This is done for GC, and also to free the
  97 // list of "dead" blocks when it gets full (which is part of GC, if
  98 // you think about it).
  99 static void bottleneck()
 100 {
 101     struct Globals* g = globals;
 102     g->bottleneck = 1;
 103     while(g->bottleneck && g->waitCount < g->nThreads - 1) {
 104         g->waitCount++;
 105         UNLOCK(); naSemDown(g->sem); LOCK();
 106         g->waitCount--;
 107     }
 108     if(g->waitCount >= g->nThreads - 1) {
 109         freeDead();
 110         if(g->needGC) garbageCollect();
 111         if(g->waitCount) naSemUpAll(g->sem, g->waitCount);
 112         g->bottleneck = 0;
 113     }
 114 }
 115
 116 void naCheckBottleneck()
 117 {
 118     if(globals->bottleneck) { LOCK(); bottleneck(); UNLOCK(); }
 119 }
 120
 121 static void naCode_gcclean(struct naCode* o)
 122 {
 123     naFree(o->byteCode);   o->byteCode = 0;
 124     naFree(o->constants);  o->constants = 0;
 125     naFree(o->argSyms);    o->argSyms = 0;
 126     naFree(o->optArgSyms); o->optArgSyms = 0;
 127     naFree(o->optArgVals); o->optArgVals = 0;
 128     naFree(o->lineIps);    o->lineIps = 0;
 129 }
 130
 131 static void naGhost_gcclean(struct naGhost* g)
 132 {
 133     if(g->ptr) g->gtype->destroy(g->ptr);
 134     g->ptr = 0;
 135 }
 136
 137 static void freeelem(struct naPool* p, struct naObj* o)
 138 {
 139     // Free any intrinsic (i.e. non-garbage collected) storage the
 140     // object might have
 141     switch(p->type) {
 142     case T_STR:
 143         naStr_gcclean((struct naStr*)o);
 144         break;
 145     case T_VEC:
 146         naVec_gcclean((struct naVec*)o);
 147         break;
 148     case T_HASH:
 149         naHash_gcclean((struct naHash*)o);
 150         break;
 151     case T_CODE:
 152         naCode_gcclean((struct naCode*)o);
 153         break;
 154     case T_GHOST:
 155         naGhost_gcclean((struct naGhost*)o);
 156         break;
 157     }
 158
 159     // And add it to the free list
 160     p->free[p->nfree++] = o;
 161 }
 162
 163 static void newBlock(struct naPool* p, int need)
 164 {
 165     int i;
 166     struct Block* newb;
 167
 168     if(need < MIN_BLOCK_SIZE) need = MIN_BLOCK_SIZE;
 169
 170     newb = naAlloc(sizeof(struct Block));
 171     newb->block = naAlloc(need * p->elemsz);
 172     newb->size = need;
 173     newb->next = p->blocks;
 174     p->blocks = newb;
 175     naBZero(newb->block, need * p->elemsz);
 176
 177     if(need > p->freesz - p->freetop) need = p->freesz - p->freetop;
 178     p->nfree = 0;
 179     p->free = p->free0 + p->freetop;
 180     for(i=0; i < need; i++) {
 181         struct naObj* o = (struct naObj*)(newb->block + i*p->elemsz);
 182         o->mark = 0;
 183         p->free[p->nfree++] = o;
 184     }
 185     p->freetop += need;
 186 }
 187
 188 void naGC_init(struct naPool* p, int type)
 189 {
 190     p->type = type;
 191     p->elemsz = naTypeSize(type);
 192     p->blocks = 0;
 193
 194     p->free0 = p->free = 0;
 195     p->nfree = p->freesz = p->freetop = 0;
 196     reap(p);
 197 }
 198
 199 static int poolsize(struct naPool* p)
 200 {
 201     int total = 0;
 202     struct Block* b = p->blocks;
 203     while(b) { total += b->size; b = b->next; }
 204     return total;
 205 }
 206
 207 struct naObj** naGC_get(struct naPool* p, int n, int* nout)
 208 {
 209     struct naObj** result;
 210     naCheckBottleneck();
 211     LOCK();
 212     while(globals->allocCount < 0 || (p->nfree == 0 && p->freetop >= p->freesz)) {
 213         globals->needGC = 1;
 214         bottleneck();
 215     }
 216     if(p->nfree == 0)
 217         newBlock(p, poolsize(p)/8);
 218     n = p->nfree < n ? p->nfree : n;
 219     *nout = n;
 220     p->nfree -= n;
 221     globals->allocCount -= n;
 222     result = (struct naObj**)(p->free + p->nfree);
 223     UNLOCK();
 224     return result;
 225 }
 226
 227 static void markvec(naRef r)
 228 {
 229     int i;
 230     struct VecRec* vr = r.ref.ptr.vec->rec;
 231     if(!vr) return;
 232     for(i=0; i<vr->size; i++)
 233         mark(vr->array[i]);
 234 }
 235
 236 static void markhash(naRef r)
 237 {
 238     int i;
 239     struct HashRec* hr = r.ref.ptr.hash->rec;
 240     if(!hr) return;
 241     for(i=0; i < (1<<hr->lgalloced); i++) {
 242         struct HashNode* hn = hr->table[i];
 243         while(hn) {
 244             mark(hn->key);
 245             mark(hn->val);
 246             hn = hn->next;
 247         }
 248     }
 249 }
 250
 251 // Sets the reference bit on the object, and recursively on all
 252 // objects reachable from it.  Uses the processor stack for recursion...
 253 static void mark(naRef r)
 254 {
 255     int i;
 256
 257     if(IS_NUM(r) || IS_NIL(r))
 258         return;
 259
 260     if(r.ref.ptr.obj->mark == 1)
 261         return;
 262
 263     r.ref.ptr.obj->mark = 1;
 264     switch(r.ref.ptr.obj->type) {
 265     case T_VEC: markvec(r); break;
 266     case T_HASH: markhash(r); break;
 267     case T_CODE:
 268         mark(r.ref.ptr.code->srcFile);
 269         for(i=0; i<r.ref.ptr.code->nConstants; i++)
 270             mark(r.ref.ptr.code->constants[i]);
 271         break;
 272     case T_FUNC:
 273         mark(r.ref.ptr.func->code);
 274         mark(r.ref.ptr.func->namespace);
 275         mark(r.ref.ptr.func->next);
 276         break;
 277     }
 278 }
 279
 280 // Collects all the unreachable objects into a free list, and
 281 // allocates more space if needed.
 282 static void reap(struct naPool* p)
 283 {
 284     struct Block* b;
 285     int elem, freesz, total = poolsize(p);
 286     p->nfree = 0;
 287     freesz = total < MIN_BLOCK_SIZE ? MIN_BLOCK_SIZE : total;
 288     freesz = (3 * freesz / 2) + (globals->nThreads * OBJ_CACHE_SZ);
 289     if(p->freesz < freesz) {
 290         naFree(p->free0);
 291         p->freesz = freesz;
 292         p->free = p->free0 = naAlloc(sizeof(void*) * p->freesz);
 293     }
 294
 295     for(b = p->blocks; b; b = b->next)
 296         for(elem=0; elem < b->size; elem++) {
 297             struct naObj* o = (struct naObj*)(b->block + elem * p->elemsz);
 298             if(o->mark == 0)
 299                 freeelem(p, o);
 300             o->mark = 0;
 301         }
 302
 303     // allocs of this type until the next collection
 304     globals->allocCount += total/2;
 305
 306     // Allocate more if necessary (try to keep 25-50% of the objects
 307     // available)
 308     if(p->nfree < total/4) {
 309         int used = total - p->nfree;
 310         int avail = total - used;
 311         int need = used/2 - avail;
 312         if(need > 0)
 313             newBlock(p, need);
 314     }
 315     p->freetop = p->nfree;
 316 }
 317
 318 // Does the swap, returning the old value
 319 static void* doswap(void** target, void* val)
 320 {
 321     void* old = *target;
 322     *target = val;
 323     return old;
 324 }
 325
 326 // Atomically replaces target with a new pointer, and adds the old one
 327 // to the list of blocks to free the next time something holds the
 328 // giant lock.
 329 void naGC_swapfree(void** target, void* val)
 330 {
 331     void* old;
 332     LOCK();
 333     old = doswap(target, val);
 334     while(globals->ndead >= globals->deadsz)
 335         bottleneck();
 336     globals->deadBlocks[globals->ndead++] = old;
 337     UNLOCK();
 338 }