X-Git-Url: https://git.mxchange.org/?a=blobdiff_plain;f=simgear%2Fnasal%2Fgc.c;h=e9d9b7b8ba60587f9618eca6e25fab55a3a8a5f5;hb=85e58b4a49d3c3b74afed3c766b47b65a6a95a66;hp=60f6c4223785c1f476bed9733f5acfb6d0993fbe;hpb=83b4dcb55cea1ba30a1ccfd08b517926672a018b;p=simgear.git

diff --git a/simgear/nasal/gc.c b/simgear/nasal/gc.c
index 60f6c422..e9d9b7b8 100644
--- a/simgear/nasal/gc.c
+++ b/simgear/nasal/gc.c
@@ -1,214 +1,288 @@
 #include "nasal.h"
 #include "data.h"
+#include "code.h"
 
-#define MIN_BLOCK_SIZE 256
+#define MIN_BLOCK_SIZE 32
 
-// "type" for an object freed by the collector
-#define T_GCFREED 123 // DEBUG
+static void reap(struct naPool* p);
+static void mark(naRef r);
 
 struct Block {
     int   size;
     char* block;
+    struct Block* next;
 };
 
-// Decremented every allocation.  When it reaches zero, we do a
-// garbage collection.  The value is reset to 1/2 of the total object
-// count each collection, which is sane: it ensures that no more than
-// 50% growth can happen between collections, and ensures that garbage
-// collection work is constant with allocation work (i.e. that O(N)
-// work is done only every O(1/2N) allocations).
-static int GlobalAllocCount = 256;
-
-static void appendfree(struct naPool*p, struct naObj* o)
-{
-    // Need more space?
-    if(p->freesz <= p->nfree) {
-        int i, n = 1+((3*p->nfree)>>1);
-        void** newf = naAlloc(n * sizeof(void*));
-        for(i=0; i<p->nfree; i++)
-            newf[i] = p->free[i];
-        naFree(p->free);
-        p->free = newf;
-        p->freesz = n;
+// Must be called with the giant exclusive lock!
+static void freeDead()
+{
+    int i;
+    for(i=0; i<globals->ndead; i++)
+        naFree(globals->deadBlocks[i]);
+    globals->ndead = 0;
+}
+
+static void marktemps(struct Context* c)
+{
+    int i;
+    naRef r = naNil();
+    for(i=0; i<c->ntemps; i++) {
+        SETPTR(r, c->temps[i]);
+        mark(r);
     }
+}
 
-    p->free[p->nfree++] = o;
+// Must be called with the big lock!
+static void garbageCollect()
+{
+    int i;
+    struct Context* c;
+    globals->allocCount = 0;
+    c = globals->allContexts;
+    while(c) {
+        for(i=0; i<NUM_NASAL_TYPES; i++)
+            c->nfree[i] = 0;
+        for(i=0; i < c->fTop; i++) {
+            mark(c->fStack[i].func);
+            mark(c->fStack[i].locals);
+        }
+        for(i=0; i < c->opTop; i++)
+            mark(c->opStack[i]);
+        mark(c->dieArg);
+        marktemps(c);
+        c = c->nextAll;
+    }
+
+    mark(globals->save);
+    mark(globals->symbols);
+    mark(globals->meRef);
+    mark(globals->argRef);
+    mark(globals->parentsRef);
+
+    // Finally collect all the freed objects
+    for(i=0; i<NUM_NASAL_TYPES; i++)
+        reap(&(globals->pools[i]));
+
+    // Make enough space for the dead blocks we need to free during
+    // execution.  This works out to 1 spot for every 2 live objects,
+    // which should be limit the number of bottleneck operations
+    // without imposing an undue burden of extra "freeable" memory.
+    if(globals->deadsz < globals->allocCount) {
+        globals->deadsz = globals->allocCount;
+        if(globals->deadsz < 256) globals->deadsz = 256;
+        naFree(globals->deadBlocks);
+        globals->deadBlocks = naAlloc(sizeof(void*) * globals->deadsz);
+    }
+    globals->needGC = 0;
+}
+
+void naModLock()
+{
+    LOCK();
+    globals->nThreads++;
+    UNLOCK();
+    naCheckBottleneck();
+}
+
+void naModUnlock()
+{
+    LOCK();
+    globals->nThreads--;
+    // We might be the "last" thread needed for collection.  Since
+    // we're releasing our modlock to do something else for a while,
+    // wake someone else up to do it.
+    if(globals->waitCount == globals->nThreads)
+        naSemUp(globals->sem, 1);
+    UNLOCK();
+}
+
+// Must be called with the main lock.  Engages the "bottleneck", where
+// all threads will block so that one (the last one to call this
+// function) can run alone.  This is done for GC, and also to free the
+// list of "dead" blocks when it gets full (which is part of GC, if
+// you think about it).
+static void bottleneck()
+{
+    struct Globals* g = globals;
+    g->bottleneck = 1;
+    while(g->bottleneck && g->waitCount < g->nThreads - 1) {
+        g->waitCount++;
+        UNLOCK(); naSemDown(g->sem); LOCK();
+        g->waitCount--;
+    }
+    if(g->waitCount >= g->nThreads - 1) {
+        freeDead();
+        if(g->needGC) garbageCollect();
+        if(g->waitCount) naSemUp(g->sem, g->waitCount);
+        g->bottleneck = 0;
+    }
+}
+
+void naCheckBottleneck()
+{
+    if(globals->bottleneck) { LOCK(); bottleneck(); UNLOCK(); }
 }
 
 static void naCode_gcclean(struct naCode* o)
 {
-    naFree(o->byteCode);  o->byteCode = 0;
-    naFree(o->constants); o->constants = 0;
+    naFree(o->constants);  o->constants = 0;
 }
 
 static void naGhost_gcclean(struct naGhost* g)
 {
-    if(g->ptr) g->gtype->destroy(g->ptr);
+    if(g->ptr && g->gtype->destroy) g->gtype->destroy(g->ptr);
     g->ptr = 0;
 }
 
 static void freeelem(struct naPool* p, struct naObj* o)
 {
-    // Mark the object as "freed" for debugging purposes
-    o->type = T_GCFREED; // DEBUG
-
-    // Free any intrinsic (i.e. non-garbage collected) storage the
-    // object might have
+    // Clean up any intrinsic storage the object might have...
     switch(p->type) {
-    case T_STR:
-        naStr_gcclean((struct naStr*)o);
-        break;
-    case T_VEC:
-        naVec_gcclean((struct naVec*)o);
-        break;
-    case T_HASH:
-        naHash_gcclean((struct naHash*)o);
-        break;
-    case T_CODE:
-        naCode_gcclean((struct naCode*)o);
-        break;
-    case T_GHOST:
-        naGhost_gcclean((struct naGhost*)o);
-        break;
+    case T_STR:   naStr_gcclean  ((struct naStr*)  o); break;
+    case T_VEC:   naVec_gcclean  ((struct naVec*)  o); break;
+    case T_HASH:  naiGCHashClean ((struct naHash*) o); break;
+    case T_CODE:  naCode_gcclean ((struct naCode*) o); break;
+    case T_GHOST: naGhost_gcclean((struct naGhost*)o); break;
     }
-
-    // And add it to the free list
-    appendfree(p, o);
+    p->free[p->nfree++] = o;  // ...and add it to the free list
 }
 
 static void newBlock(struct naPool* p, int need)
 {
     int i;
-    char* buf;
-    struct Block* newblocks;
+    struct Block* newb;
 
-    if(need < MIN_BLOCK_SIZE)
-        need = MIN_BLOCK_SIZE;
-    
-    newblocks = naAlloc((p->nblocks+1) * sizeof(struct Block));
-    for(i=0; i<p->nblocks; i++) newblocks[i] = p->blocks[i];
-    naFree(p->blocks);
-    p->blocks = newblocks;
-    buf = naAlloc(need * p->elemsz);
-    naBZero(buf, need * p->elemsz);
-    p->blocks[p->nblocks].size = need;
-    p->blocks[p->nblocks].block = buf;
-    p->nblocks++;
+    if(need < MIN_BLOCK_SIZE) need = MIN_BLOCK_SIZE;
+
+    newb = naAlloc(sizeof(struct Block));
+    newb->block = naAlloc(need * p->elemsz);
+    newb->size = need;
+    newb->next = p->blocks;
+    p->blocks = newb;
+    naBZero(newb->block, need * p->elemsz);
     
-    for(i=0; i<need; i++) {
-        struct naObj* o = (struct naObj*)(buf + i*p->elemsz);
+    if(need > p->freesz - p->freetop) need = p->freesz - p->freetop;
+    p->nfree = 0;
+    p->free = p->free0 + p->freetop;
+    for(i=0; i < need; i++) {
+        struct naObj* o = (struct naObj*)(newb->block + i*p->elemsz);
         o->mark = 0;
-        o->type = p->type;
-        appendfree(p, o);
+        p->free[p->nfree++] = o;
     }
+    p->freetop += need;
 }
 
 void naGC_init(struct naPool* p, int type)
 {
     p->type = type;
     p->elemsz = naTypeSize(type);
-    p->nblocks = 0;
     p->blocks = 0;
-    p->nfree = 0;
-    p->freesz = 0;
-    p->free = 0;
-    naGC_reap(p);
+
+    p->free0 = p->free = 0;
+    p->nfree = p->freesz = p->freetop = 0;
+    reap(p);
 }
 
-int naGC_size(struct naPool* p)
+static int poolsize(struct naPool* p)
 {
-    int i, total=0;
-    for(i=0; i<p->nblocks; i++)
-        total += ((struct Block*)(p->blocks + i))->size;
+    int total = 0;
+    struct Block* b = p->blocks;
+    while(b) { total += b->size; b = b->next; }
     return total;
 }
 
-struct naObj* naGC_get(struct naPool* p)
+struct naObj** naGC_get(struct naPool* p, int n, int* nout)
 {
-    // Collect every GlobalAllocCount allocations.
-    // This gets set to ~50% of the total object count each
-    // collection (it's incremented in naGC_reap()).
-    if(--GlobalAllocCount < 0) {
-        GlobalAllocCount = 0;
-        naGarbageCollect();
+    struct naObj** result;
+    naCheckBottleneck();
+    LOCK();
+    while(globals->allocCount < 0 || (p->nfree == 0 && p->freetop >= p->freesz)) {
+        globals->needGC = 1;
+        bottleneck();
     }
-
-    // If we're out, then allocate an extra 12.5%
     if(p->nfree == 0)
-        newBlock(p, naGC_size(p)/8);
-    return p->free[--p->nfree];
+        newBlock(p, poolsize(p)/8);
+    n = p->nfree < n ? p->nfree : n;
+    *nout = n;
+    p->nfree -= n;
+    globals->allocCount -= n;
+    result = (struct naObj**)(p->free + p->nfree);
+    UNLOCK();
+    return result;
+}
+
+static void markvec(naRef r)
+{
+    int i;
+    struct VecRec* vr = PTR(r).vec->rec;
+    if(!vr) return;
+    for(i=0; i<vr->size; i++)
+        mark(vr->array[i]);
 }
 
 // Sets the reference bit on the object, and recursively on all
-// objects reachable from it.  Clumsy: uses C stack recursion, which
-// is slower than it need be and may cause problems on some platforms
-// due to the very large stack depths that result.
-void naGC_mark(naRef r)
+// objects reachable from it.  Uses the processor stack for recursion...
+static void mark(naRef r)
 {
     int i;
 
     if(IS_NUM(r) || IS_NIL(r))
         return;
 
-    if(r.ref.ptr.obj->mark == 1)
+    if(PTR(r).obj->mark == 1)
         return;
 
-    // Verify that the object hasn't been freed incorrectly:
-    if(r.ref.ptr.obj->type == T_GCFREED) *(int*)0=0; // DEBUG
-
-    r.ref.ptr.obj->mark = 1;
-    switch(r.ref.ptr.obj->type) {
-    case T_VEC:
-        for(i=0; i<r.ref.ptr.vec->size; i++)
-            naGC_mark(r.ref.ptr.vec->array[i]);
-        break;
-    case T_HASH:
-        if(r.ref.ptr.hash->table == 0)
-            break;
-        for(i=0; i < (1<<r.ref.ptr.hash->lgalloced); i++) {
-            struct HashNode* hn = r.ref.ptr.hash->table[i];
-            while(hn) {
-                naGC_mark(hn->key);
-                naGC_mark(hn->val);
-                hn = hn->next;
-            }
-        }
-        break;
+    PTR(r).obj->mark = 1;
+    switch(PTR(r).obj->type) {
+    case T_VEC: markvec(r); break;
+    case T_HASH: naiGCMarkHash(r); break;
     case T_CODE:
-        naGC_mark(r.ref.ptr.code->srcFile);
-        for(i=0; i<r.ref.ptr.code->nConstants; i++)
-            naGC_mark(r.ref.ptr.code->constants[i]);
-        break;
-    case T_CLOSURE:
-        naGC_mark(r.ref.ptr.closure->namespace);
-        naGC_mark(r.ref.ptr.closure->next);
+        mark(PTR(r).code->srcFile);
+        for(i=0; i<PTR(r).code->nConstants; i++)
+            mark(PTR(r).code->constants[i]);
         break;
     case T_FUNC:
-        naGC_mark(r.ref.ptr.func->code);
-        naGC_mark(r.ref.ptr.func->closure);
+        mark(PTR(r).func->code);
+        mark(PTR(r).func->namespace);
+        mark(PTR(r).func->next);
         break;
     }
 }
 
+void naiGCMark(naRef r)
+{
+    mark(r);
+}
+
 // Collects all the unreachable objects into a free list, and
 // allocates more space if needed.
-void naGC_reap(struct naPool* p)
+static void reap(struct naPool* p)
 {
-    int i, elem, total = 0;
+    struct Block* b;
+    int elem, freesz, total = poolsize(p);
+    freesz = total < MIN_BLOCK_SIZE ? MIN_BLOCK_SIZE : total;
+    freesz = (3 * freesz / 2) + (globals->nThreads * OBJ_CACHE_SZ);
+    if(p->freesz < freesz) {
+        naFree(p->free0);
+        p->freesz = freesz;
+        p->free = p->free0 = naAlloc(sizeof(void*) * p->freesz);
+    }
+
     p->nfree = 0;
-    for(i=0; i<p->nblocks; i++) {
-        struct Block* b = p->blocks + i;
-        total += b->size;
+    p->free = p->free0;
+
+    for(b = p->blocks; b; b = b->next)
         for(elem=0; elem < b->size; elem++) {
             struct naObj* o = (struct naObj*)(b->block + elem * p->elemsz);
             if(o->mark == 0)
                 freeelem(p, o);
             o->mark = 0;
         }
-    }
 
-    // Add 50% of our total to the global count
-    GlobalAllocCount += total/2;
+    p->freetop = p->nfree;
+
+    // allocs of this type until the next collection
+    globals->allocCount += total/2;
     
     // Allocate more if necessary (try to keep 25-50% of the objects
     // available)
@@ -221,3 +295,24 @@ void naGC_reap(struct naPool* p)
     }
 }
 
+// Does the swap, returning the old value
+static void* doswap(void** target, void* val)
+{
+    void* old = *target;
+    *target = val;
+    return old;
+}
+
+// Atomically replaces target with a new pointer, and adds the old one
+// to the list of blocks to free the next time something holds the
+// giant lock.
+void naGC_swapfree(void** target, void* val)
+{
+    void* old;
+    LOCK();
+    old = doswap(target, val);
+    while(globals->ndead >= globals->deadsz)
+        bottleneck();
+    globals->deadBlocks[globals->ndead++] = old;
+    UNLOCK();
+}