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