simgear/nasal/gc.c

   1 #include "nasal.h"
   2 #include "data.h"
   3 #include "code.h"
   4
   5 #define MIN_BLOCK_SIZE 32
   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         SETPTR(r, 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->save_hash);
  58     mark(globals->symbols);
  59     mark(globals->meRef);
  60     mark(globals->argRef);
  61     mark(globals->parentsRef);
  62
  63     // Finally collect all the freed objects
  64     for(i=0; i<NUM_NASAL_TYPES; i++)
  65         reap(&(globals->pools[i]));
  66
  67     // Make enough space for the dead blocks we need to free during
  68     // execution.  This works out to 1 spot for every 2 live objects,
  69     // which should be limit the number of bottleneck operations
  70     // without imposing an undue burden of extra "freeable" memory.
  71     if(globals->deadsz < globals->allocCount) {
  72         globals->deadsz = globals->allocCount;
  73         if(globals->deadsz < 256) globals->deadsz = 256;
  74         naFree(globals->deadBlocks);
  75         globals->deadBlocks = naAlloc(sizeof(void*) * globals->deadsz);
  76     }
  77     globals->needGC = 0;
  78 }
  79
  80 void naModLock()
  81 {
  82     LOCK();
  83     globals->nThreads++;
  84     UNLOCK();
  85     naCheckBottleneck();
  86 }
  87
  88 void naModUnlock()
  89 {
  90     LOCK();
  91     globals->nThreads--;
  92     // We might be the "last" thread needed for collection.  Since
  93     // we're releasing our modlock to do something else for a while,
  94     // wake someone else up to do it.
  95     if(globals->waitCount == globals->nThreads)
  96         naSemUp(globals->sem, 1);
  97     UNLOCK();
  98 }
  99
 100 // Must be called with the main lock.  Engages the "bottleneck", where
 101 // all threads will block so that one (the last one to call this
 102 // function) can run alone.  This is done for GC, and also to free the
 103 // list of "dead" blocks when it gets full (which is part of GC, if
 104 // you think about it).
 105 static void bottleneck()
 106 {
 107     struct Globals* g = globals;
 108     g->bottleneck = 1;
 109     while(g->bottleneck && g->waitCount < g->nThreads - 1) {
 110         g->waitCount++;
 111         UNLOCK(); naSemDown(g->sem); LOCK();
 112         g->waitCount--;
 113     }
 114     if(g->waitCount >= g->nThreads - 1) {
 115         freeDead();
 116         if(g->needGC) garbageCollect();
 117         if(g->waitCount) naSemUp(g->sem, g->waitCount);
 118         g->bottleneck = 0;
 119     }
 120 }
 121
 122 void naGC()
 123 {
 124     LOCK();
 125     globals->needGC = 1;
 126     bottleneck();
 127     UNLOCK();
 128     naCheckBottleneck();
 129 }
 130
 131 void naCheckBottleneck()
 132 {
 133     if(globals->bottleneck) { LOCK(); bottleneck(); UNLOCK(); }
 134 }
 135
 136 static void naCode_gcclean(struct naCode* o)
 137 {
 138     naFree(o->constants);  o->constants = 0;
 139 }
 140
 141 static void naCCode_gcclean(struct naCCode* c)
 142 {
 143     if(c->fptru && c->user_data && c->destroy) c->destroy(c->user_data);
 144     c->user_data = 0;
 145 }
 146
 147 static void naGhost_gcclean(struct naGhost* g)
 148 {
 149     if(g->ptr && g->gtype->destroy) g->gtype->destroy(g->ptr);
 150     g->ptr = 0;
 151 }
 152
 153 static void freeelem(struct naPool* p, struct naObj* o)
 154 {
 155     // Clean up any intrinsic storage the object might have...
 156     switch(p->type) {
 157     case T_STR:   naStr_gcclean  ((struct naStr*)  o); break;
 158     case T_VEC:   naVec_gcclean  ((struct naVec*)  o); break;
 159     case T_HASH:  naiGCHashClean ((struct naHash*) o); break;
 160     case T_CODE:  naCode_gcclean ((struct naCode*) o); break;
 161     case T_CCODE: naCCode_gcclean((struct naCCode*)o); break;
 162     case T_GHOST: naGhost_gcclean((struct naGhost*)o); break;
 163     }
 164     p->free[p->nfree++] = o;  // ...and add it to the free list
 165 }
 166
 167 static void newBlock(struct naPool* p, int need)
 168 {
 169     int i;
 170     struct Block* newb;
 171
 172     if(need < MIN_BLOCK_SIZE) need = MIN_BLOCK_SIZE;
 173
 174     newb = naAlloc(sizeof(struct Block));
 175     newb->block = naAlloc(need * p->elemsz);
 176     newb->size = need;
 177     newb->next = p->blocks;
 178     p->blocks = newb;
 179     naBZero(newb->block, need * p->elemsz);
 180
 181     if(need > p->freesz - p->freetop) need = p->freesz - p->freetop;
 182     p->nfree = 0;
 183     p->free = p->free0 + p->freetop;
 184     for(i=0; i < need; i++) {
 185         struct naObj* o = (struct naObj*)(newb->block + i*p->elemsz);
 186         o->mark = 0;
 187         p->free[p->nfree++] = o;
 188     }
 189     p->freetop += need;
 190 }
 191
 192 void naGC_init(struct naPool* p, int type)
 193 {
 194     p->type = type;
 195     p->elemsz = naTypeSize(type);
 196     p->blocks = 0;
 197
 198     p->free0 = p->free = 0;
 199     p->nfree = p->freesz = p->freetop = 0;
 200     reap(p);
 201 }
 202
 203 static int poolsize(struct naPool* p)
 204 {
 205     int total = 0;
 206     struct Block* b = p->blocks;
 207     while(b) { total += b->size; b = b->next; }
 208     return total;
 209 }
 210
 211 struct naObj** naGC_get(struct naPool* p, int n, int* nout)
 212 {
 213     struct naObj** result;
 214     naCheckBottleneck();
 215     LOCK();
 216     while(globals->allocCount < 0 || (p->nfree == 0 && p->freetop >= p->freesz)) {
 217         globals->needGC = 1;
 218         bottleneck();
 219     }
 220     if(p->nfree == 0)
 221         newBlock(p, poolsize(p)/8);
 222     n = p->nfree < n ? p->nfree : n;
 223     *nout = n;
 224     p->nfree -= n;
 225     globals->allocCount -= n;
 226     result = (struct naObj**)(p->free + p->nfree);
 227     UNLOCK();
 228     return result;
 229 }
 230
 231 static void markvec(naRef r)
 232 {
 233     int i;
 234     struct VecRec* vr = PTR(r).vec->rec;
 235     if(!vr) return;
 236     for(i=0; i<vr->size; i++)
 237         mark(vr->array[i]);
 238 }
 239
 240 // Sets the reference bit on the object, and recursively on all
 241 // objects reachable from it.  Uses the processor stack for recursion...
 242 static void mark(naRef r)
 243 {
 244     int i;
 245
 246     if(IS_NUM(r) || IS_NIL(r))
 247         return;
 248
 249     if(PTR(r).obj->mark == 1)
 250         return;
 251
 252     PTR(r).obj->mark = 1;
 253     switch(PTR(r).obj->type) {
 254     case T_VEC: markvec(r); break;
 255     case T_HASH: naiGCMarkHash(r); break;
 256     case T_CODE:
 257         mark(PTR(r).code->srcFile);
 258         for(i=0; i<PTR(r).code->nConstants; i++)
 259             mark(PTR(r).code->constants[i]);
 260         break;
 261     case T_FUNC:
 262         mark(PTR(r).func->code);
 263         mark(PTR(r).func->namespace);
 264         mark(PTR(r).func->next);
 265         break;
 266     case T_GHOST:
 267         mark(PTR(r).ghost->data);
 268         break;
 269     }
 270 }
 271
 272 void naiGCMark(naRef r)
 273 {
 274     mark(r);
 275 }
 276
 277 // Collects all the unreachable objects into a free list, and
 278 // allocates more space if needed.
 279 static void reap(struct naPool* p)
 280 {
 281     struct Block* b;
 282     int elem, freesz, total = poolsize(p);
 283     freesz = total < MIN_BLOCK_SIZE ? MIN_BLOCK_SIZE : total;
 284     freesz = (3 * freesz / 2) + (globals->nThreads * OBJ_CACHE_SZ);
 285     if(p->freesz < freesz) {
 286         naFree(p->free0);
 287         p->freesz = freesz;
 288         p->free = p->free0 = naAlloc(sizeof(void*) * p->freesz);
 289     }
 290
 291     p->nfree = 0;
 292     p->free = p->free0;
 293
 294     for(b = p->blocks; b; b = b->next)
 295         for(elem=0; elem < b->size; elem++) {
 296             struct naObj* o = (struct naObj*)(b->block + elem * p->elemsz);
 297             if(o->mark == 0)
 298                 freeelem(p, o);
 299             o->mark = 0;
 300         }
 301
 302     p->freetop = p->nfree;
 303
 304     // allocs of this type until the next collection
 305     globals->allocCount += total/2;
 306
 307     // Allocate more if necessary (try to keep 25-50% of the objects
 308     // available)
 309     if(p->nfree < total/4) {
 310         int used = total - p->nfree;
 311         int avail = total - used;
 312         int need = used/2 - avail;
 313         if(need > 0)
 314             newBlock(p, need);
 315     }
 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 }