bug 673795 - part2, using lists of avaiulable chunks for faster chunk selection. r=wmccloskey
authorIgor Bukanov <igor@mir2.org>
Tue, 26 Jul 2011 09:55:23 +0200
changeset 74369 3210abdedf8ae17174a28b3120f9f69224a43d5d
parent 74368 8c36a72adee981550afeca616c7403a9b4248b78
child 74370 c8f38fb18c6a388a6ef4723fabcfd099ac51a78f
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
reviewerswmccloskey
bugs673795
milestone8.0a1
bug 673795 - part2, using lists of avaiulable chunks for faster chunk selection. r=wmccloskey
js/src/jsapi.cpp
js/src/jscntxt.h
js/src/jscompartment.cpp
js/src/jscompartment.h
js/src/jsgc.cpp
js/src/jsgc.h
--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -2715,17 +2715,17 @@ JS_GetGCParameter(JSRuntime *rt, JSGCPar
         return rt->gcEmptyArenaPoolLifespan;
       case JSGC_BYTES:
         return rt->gcBytes;
       case JSGC_MODE:
         return uint32(rt->gcMode);
       case JSGC_UNUSED_CHUNKS:
         return uint32(rt->gcEmptyChunkCount);
       case JSGC_TOTAL_CHUNKS:
-        return uint32(rt->gcUserChunkSet.count() + rt->gcSystemChunkSet.count() + rt->gcEmptyChunkCount);
+        return uint32(rt->gcChunkSet.count() + rt->gcEmptyChunkCount);
       default:
         JS_ASSERT(key == JSGC_NUMBER);
         return rt->gcNumber;
     }
 }
 
 JS_PUBLIC_API(void)
 JS_SetGCParameterForThread(JSContext *cx, JSGCParamKey key, uint32 value)
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -385,18 +385,39 @@ struct JSRuntime
      * See bug 492355 for more details.
      *
      * This comes early in JSRuntime to minimize the immediate format used by
      * trace-JITted code that reads it.
      */
     uint32              protoHazardShape;
 
     /* Garbage collector state, used by jsgc.c. */
-    js::GCChunkSet      gcUserChunkSet;
-    js::GCChunkSet      gcSystemChunkSet;
+
+    /*
+     * Set of all GC chunks with at least one allocated thing. The
+     * conservative GC uses it to quickly check if a possible GC thing points
+     * into an allocated chunk.
+     */
+    js::GCChunkSet      gcChunkSet;
+
+    /*
+     * Doubly-linked lists of chunks from user and system compartments. The GC
+     * allocates its arenas from the corresponding list and when all arenas
+     * in the list head are taken, then the chunk is removed from the list.
+     * During the GC when all arenas in a chunk become free, that chunk is
+     * removed from the list and scheduled for release.
+     */
+    js::gc::Chunk       *gcSystemAvailableChunkListHead;
+    js::gc::Chunk       *gcUserAvailableChunkListHead;
+
+    /*
+     * Singly-linked list of empty chunks and its length. We use the list not
+     * to release empty chunks immediately so they can be used for future
+     * allocations. This avoids very high overhead of chunk release/allocation.
+     */
     js::gc::Chunk       *gcEmptyChunkListHead;
     size_t              gcEmptyChunkCount;
 
     js::RootedValueMap  gcRootsHash;
     js::GCLocks         gcLocksHash;
     jsrefcount          gcKeepAtoms;
     uint32              gcBytes;
     uint32              gcTriggerBytes;
--- a/js/src/jscompartment.cpp
+++ b/js/src/jscompartment.cpp
@@ -122,17 +122,16 @@ JSCompartment::~JSCompartment()
     for (size_t i = 0; i != JS_ARRAY_LENGTH(scriptsToGC); ++i)
         JS_ASSERT(!scriptsToGC[i]);
 #endif
 }
 
 bool
 JSCompartment::init()
 {
-    chunk = NULL;
     for (unsigned i = 0; i < FINALIZE_LIMIT; i++)
         arenas[i].init();
     freeLists.init();
     if (!crossCompartmentWrappers.init())
         return false;
 
     if (!scriptFilenameTable.init())
         return false;
@@ -462,18 +461,16 @@ JSCompartment::markCrossCompartmentWrapp
 
     for (WrapperMap::Enum e(crossCompartmentWrappers); !e.empty(); e.popFront())
         MarkValue(trc, e.front().key, "cross-compartment wrapper");
 }
 
 void
 JSCompartment::sweep(JSContext *cx, uint32 releaseInterval)
 {
-    chunk = NULL;
-
     /* Remove dead wrappers from the table. */
     for (WrapperMap::Enum e(crossCompartmentWrappers); !e.empty(); e.popFront()) {
         JS_ASSERT_IF(IsAboutToBeFinalized(cx, e.front().key.toGCThing()) &&
                      !IsAboutToBeFinalized(cx, e.front().value.toGCThing()),
                      e.front().key.isString());
         if (IsAboutToBeFinalized(cx, e.front().key.toGCThing()) ||
             IsAboutToBeFinalized(cx, e.front().value.toGCThing())) {
             e.removeFront();
--- a/js/src/jscompartment.h
+++ b/js/src/jscompartment.h
@@ -385,17 +385,16 @@ typedef HashSet<ScriptFilenameEntry *,
                 ScriptFilenameHasher,
                 SystemAllocPolicy> ScriptFilenameTable;
 
 } /* namespace js */
 
 struct JS_FRIEND_API(JSCompartment) {
     JSRuntime                    *rt;
     JSPrincipals                 *principals;
-    js::gc::Chunk                *chunk;
 
     js::gc::ArenaList            arenas[js::gc::FINALIZE_LIMIT];
     js::gc::FreeLists            freeLists;
 
     uint32                       gcBytes;
     uint32                       gcTriggerBytes;
     size_t                       gcLastBytes;
 
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -332,50 +332,75 @@ Chunk::init(JSRuntime *rt)
         *prevp = &a->aheader;
         a->aheader.setAsNotAllocated();
         prevp = &a->aheader.next;
     }
     *prevp = NULL;
 
     for (size_t i = 0; i != JS_ARRAY_LENGTH(markingDelay); ++i)
         markingDelay[i].init();
+
+    /*
+     * The rest of info fields is initailzied in PickChunk. We do not clear
+     * the mark bitmap as that is done at the start of the next GC.
+     */
 }
 
-bool
-Chunk::unused()
+inline Chunk **
+GetAvailableChunkList(JSCompartment *comp)
 {
-    return info.numFree == ArenasPerChunk;
+    JSRuntime *rt = comp->rt;
+    return comp->isSystemCompartment
+           ? &rt->gcSystemAvailableChunkListHead
+           : &rt->gcUserAvailableChunkListHead;
 }
 
-bool
-Chunk::hasAvailableArenas()
+inline void
+Chunk::addToAvailableList(JSCompartment *comp)
 {
-    return info.numFree > 0;
+    Chunk **listHeadp = GetAvailableChunkList(comp);
+    JS_ASSERT(!info.prevp);
+    JS_ASSERT(!info.next);
+    info.prevp = listHeadp;
+    Chunk *head = *listHeadp;
+    if (head) {
+        JS_ASSERT(head->info.prevp == listHeadp);
+        head->info.prevp = &info.next;
+    }
+    info.next = head;
+    *listHeadp = this;
 }
 
-bool
-Chunk::withinArenasRange(Cell *cell)
+inline void
+Chunk::removeFromAvailableList()
 {
-    uintptr_t addr = uintptr_t(cell);
-    if (addr >= uintptr_t(&arenas[0]) && addr < uintptr_t(&arenas[ArenasPerChunk]))
-        return true;
-    return false;
+    JS_ASSERT(info.prevp);
+    *info.prevp = info.next;
+    if (info.next) {
+        JS_ASSERT(info.next->info.prevp == &info.next);
+        info.next->info.prevp = info.prevp;
+    }
+    info.prevp = NULL;
+    info.next = NULL;
 }
 
 template <size_t thingSize>
 ArenaHeader *
 Chunk::allocateArena(JSContext *cx, unsigned thingKind)
 {
     JSCompartment *comp = cx->compartment;
     JS_ASSERT(hasAvailableArenas());
     ArenaHeader *aheader = info.emptyArenaListHead;
     info.emptyArenaListHead = aheader->next;
     aheader->init(comp, thingKind, thingSize);
     --info.numFree;
 
+    if (!hasAvailableArenas())
+        removeFromAvailableList();
+
     JSRuntime *rt = info.runtime;
     Probes::resizeHeap(comp, rt->gcBytes, rt->gcBytes + ArenaSize);
     JS_ATOMIC_ADD(&rt->gcBytes, ArenaSize);
     JS_ATOMIC_ADD(&comp->gcBytes, ArenaSize);
     if (comp->gcBytes >= comp->gcTriggerBytes)
         TriggerCompartmentGC(comp);
 
     return aheader;
@@ -404,28 +429,34 @@ Chunk::releaseArena(ArenaHeader *aheader
 #endif
     JS_ATOMIC_ADD(&rt->gcBytes, -int32(ArenaSize));
     JS_ATOMIC_ADD(&comp->gcBytes, -int32(ArenaSize));
 
     aheader->setAsNotAllocated();
     aheader->next = info.emptyArenaListHead;
     info.emptyArenaListHead = aheader;
     ++info.numFree;
-    if (unused()) {
-        rt->gcUserChunkSet.remove(this);
-        rt->gcSystemChunkSet.remove(this);
+    if (info.numFree == 1) {
+        JS_ASSERT(!info.prevp);
+        JS_ASSERT(!info.next);
+        addToAvailableList(aheader->compartment);
+    } else if (!unused()) {
+        JS_ASSERT(info.prevp);
+    } else {
+        rt->gcChunkSet.remove(this);
+        removeFromAvailableList();
 
         /*
          * We keep empty chunks until we are done with finalization to allow
          * calling IsAboutToBeFinalized/Cell::isMarked for finalized GC things
          * in empty chunks. So we add the chunk to the empty set even during
          * GC_SHRINK.
          */
         info.age = 0;
-        info.link = rt->gcEmptyChunkListHead;
+        info.next = rt->gcEmptyChunkListHead;
         rt->gcEmptyChunkListHead = this;
         rt->gcEmptyChunkCount++;
     }
 }
 
 inline Chunk *
 AllocateGCChunk(JSRuntime *rt)
 {
@@ -445,103 +476,81 @@ ReleaseGCChunk(JSRuntime *rt, Chunk *p)
     JS_ATOMIC_INCREMENT(&destroyChunkCount);
 #endif
     rt->gcChunkAllocator->free_(p);
 }
 
 inline Chunk *
 PickChunk(JSContext *cx)
 {
-    Chunk *chunk = cx->compartment->chunk;
-    if (chunk && chunk->hasAvailableArenas())
+    JSCompartment *comp = cx->compartment;
+    JSRuntime *rt = comp->rt;
+    Chunk **listHeadp = GetAvailableChunkList(comp);
+    Chunk *chunk = *listHeadp;
+    if (chunk)
         return chunk;
 
-    JSRuntime *rt = cx->runtime;
-    bool isSystemCompartment = cx->compartment->isSystemCompartment;
-
     /*
-     * The chunk used for the last allocation is full, search all chunks for
-     * free arenas.
+     * We do not have available chunks, either get one from the empty set or
+     * allocate one.
      */
-    GCChunkSet *chunkSet = isSystemCompartment ? &rt->gcSystemChunkSet : &rt->gcUserChunkSet;
-    for (GCChunkSet::Range r(chunkSet->all()); !r.empty(); r.popFront()) {
-        chunk = r.front();
-        if (chunk->hasAvailableArenas()) {
-            cx->compartment->chunk = chunk;
-            return chunk;
-        }
-    }
-
-    /* Use an empty chunk when available or allocate a new one. */
     chunk = rt->gcEmptyChunkListHead;
     if (chunk) {
         JS_ASSERT(chunk->unused());
-        JS_ASSERT(!rt->gcUserChunkSet.has(chunk));
-        JS_ASSERT(!rt->gcSystemChunkSet.has(chunk));
+        JS_ASSERT(!rt->gcChunkSet.has(chunk));
         JS_ASSERT(rt->gcEmptyChunkCount >= 1);
-        rt->gcEmptyChunkListHead = chunk->info.link;
+        rt->gcEmptyChunkListHead = chunk->info.next;
         rt->gcEmptyChunkCount--;
     } else {
         chunk = AllocateGCChunk(rt);
         if (!chunk)
             return NULL;
 
         chunk->init(rt);
         rt->gcChunkAllocationSinceLastGC = true;
     }
 
     /*
      * FIXME bug 583732 - chunk is newly allocated and cannot be present in
      * the table so using ordinary lookupForAdd is suboptimal here.
      */
-    GCChunkSet::AddPtr p = chunkSet->lookupForAdd(chunk);
+    GCChunkSet::AddPtr p = rt->gcChunkSet.lookupForAdd(chunk);
     JS_ASSERT(!p);
-    if (!chunkSet->add(p, chunk)) {
+    if (!rt->gcChunkSet.add(p, chunk)) {
         ReleaseGCChunk(rt, chunk);
         return NULL;
     }
 
-    cx->compartment->chunk = chunk;
+    chunk->info.prevp = NULL;
+    chunk->info.next = NULL;
+    chunk->addToAvailableList(comp);
+
     return chunk;
 }
 
 static void
-ReleaseEmptyGCChunks(JSRuntime *rt)
-{
-    for (Chunk *chunk = rt->gcEmptyChunkListHead; chunk; ) {
-        Chunk *next = chunk->info.link;
-        ReleaseGCChunk(rt, chunk);
-        chunk = next;
-    }
-    rt->gcEmptyChunkListHead = NULL;
-    rt->gcEmptyChunkCount = 0;
-}
-
-static void
 ExpireGCChunks(JSRuntime *rt, JSGCInvocationKind gckind)
 {
     AutoLockGC lock(rt);
 
-    if (gckind == GC_SHRINK) {
-        ReleaseEmptyGCChunks(rt);
-    } else {
-        /* Return old empty chunks to the system. */
-        for (Chunk **chunkp = &rt->gcEmptyChunkListHead; *chunkp; ) {
-            JS_ASSERT(rt->gcEmptyChunkCount);
-            Chunk *chunk = *chunkp;
-            JS_ASSERT(chunk->info.age <= MAX_EMPTY_CHUNK_AGE);
-            if (chunk->info.age == MAX_EMPTY_CHUNK_AGE) {
-                *chunkp = chunk->info.link;
-                --rt->gcEmptyChunkCount;
-                ReleaseGCChunk(rt, chunk);
-            } else {
-                /* Keep the chunk but increase its age. */
-                ++chunk->info.age;
-                chunkp = &chunk->info.link;
-            }
+    /* Return old empty chunks to the system. */
+    for (Chunk **chunkp = &rt->gcEmptyChunkListHead; *chunkp; ) {
+        JS_ASSERT(rt->gcEmptyChunkCount);
+        Chunk *chunk = *chunkp;
+        JS_ASSERT(chunk->unused());
+        JS_ASSERT(!rt->gcChunkSet.has(chunk));
+        JS_ASSERT(chunk->info.age <= MAX_EMPTY_CHUNK_AGE);
+        if (gckind == GC_SHRINK || chunk->info.age == MAX_EMPTY_CHUNK_AGE) {
+            *chunkp = chunk->info.next;
+            --rt->gcEmptyChunkCount;
+            ReleaseGCChunk(rt, chunk);
+        } else {
+            /* Keep the chunk but increase its age. */
+            ++chunk->info.age;
+            chunkp = &chunk->info.next;
         }
     }
 }
 
 JS_FRIEND_API(bool)
 IsAboutToBeFinalized(JSContext *cx, const void *thing)
 {
     if (JSAtom::isStatic(thing))
@@ -571,24 +580,17 @@ js_GCThingIsMarked(void *thing, uintN co
  * JIT code is discarded in inactive compartments, regardless of how often that
  * code runs.
  */
 static const int64 JIT_SCRIPT_EIGHTH_LIFETIME = 120 * 1000 * 1000;
 
 JSBool
 js_InitGC(JSRuntime *rt, uint32 maxbytes)
 {
-    /*
-     * Make room for at least 16 chunks so the table would not grow before
-     * the browser starts up.
-     */
-    if (!rt->gcUserChunkSet.init(INITIAL_CHUNK_CAPACITY))
-        return false;
-
-    if (!rt->gcSystemChunkSet.init(INITIAL_CHUNK_CAPACITY))
+    if (!rt->gcChunkSet.init(INITIAL_CHUNK_CAPACITY))
         return false;
 
     if (!rt->gcRootsHash.init(256))
         return false;
 
     if (!rt->gcLocksHash.init(256))
         return false;
 
@@ -720,18 +722,17 @@ MarkIfGCThingWord(JSTracer *trc, jsuword
 #if JS_BITS_PER_WORD == 32
     jsuword addr = w & JSID_PAYLOAD_MASK;
 #elif JS_BITS_PER_WORD == 64
     jsuword addr = w & JSID_PAYLOAD_MASK & JSVAL_PAYLOAD_MASK;
 #endif
 
     Chunk *chunk = Chunk::fromAddress(addr);
 
-    if (!trc->context->runtime->gcUserChunkSet.has(chunk) &&
-        !trc->context->runtime->gcSystemChunkSet.has(chunk))
+    if (!trc->context->runtime->gcChunkSet.has(chunk))
         return CGCT_NOTCHUNK;
 
     /*
      * We query for pointers outside the arena array after checking for an
      * allocated chunk. Such pointers are rare and we want to reject them
      * after doing more likely rejections.
      */
     if (!Chunk::withinArenasRange(addr))
@@ -928,23 +929,28 @@ js_FinishGC(JSRuntime *rt)
     for (JSCompartment **c = rt->compartments.begin(); c != rt->compartments.end(); ++c) {
         JSCompartment *comp = *c;
         comp->finishArenaLists();
         Foreground::delete_(comp);
     }
     rt->compartments.clear();
     rt->atomsCompartment = NULL;
 
-    for (GCChunkSet::Range r(rt->gcUserChunkSet.all()); !r.empty(); r.popFront())
-        ReleaseGCChunk(rt, r.front());
-    for (GCChunkSet::Range r(rt->gcSystemChunkSet.all()); !r.empty(); r.popFront())
+    rt->gcSystemAvailableChunkListHead = NULL;
+    rt->gcUserAvailableChunkListHead = NULL;
+    for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront())
         ReleaseGCChunk(rt, r.front());
-    rt->gcUserChunkSet.clear();
-    rt->gcSystemChunkSet.clear();
-    ReleaseEmptyGCChunks(rt);
+    rt->gcChunkSet.clear();
+    for (Chunk *chunk = rt->gcEmptyChunkListHead; chunk; ) {
+        Chunk *next = chunk->info.next;
+        ReleaseGCChunk(rt, chunk);
+        chunk = next;
+    }
+    rt->gcEmptyChunkListHead = NULL;
+    rt->gcEmptyChunkCount = 0;
 
 #ifdef JS_THREADSAFE
     rt->gcHelperThread.finish(rt);
 #endif
 
 #ifdef DEBUG
     if (!rt->gcRootsHash.empty())
         CheckLeakedRoots(rt);
@@ -2260,20 +2266,17 @@ MarkAndSweep(JSContext *cx, JSCompartmen
      * Mark phase.
      */
     GCTIMESTAMP(startMark);
     GCMarker gcmarker(cx);
     JS_ASSERT(IS_GC_MARKING_TRACER(&gcmarker));
     JS_ASSERT(gcmarker.getMarkColor() == BLACK);
     rt->gcMarkingTracer = &gcmarker;
 
-    for (GCChunkSet::Range r(rt->gcUserChunkSet.all()); !r.empty(); r.popFront())
-        r.front()->bitmap.clear();
-
-    for (GCChunkSet::Range r(rt->gcSystemChunkSet.all()); !r.empty(); r.popFront())
+    for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront())
         r.front()->bitmap.clear();
 
     if (comp) {
         for (JSCompartment **c = rt->compartments.begin(); c != rt->compartments.end(); ++c)
             (*c)->markCrossCompartmentWrappers(&gcmarker);
     }
 
     MarkRuntime(&gcmarker);
--- a/js/src/jsgc.h
+++ b/js/src/jsgc.h
@@ -509,18 +509,19 @@ struct MarkingDelay {
      */
     static ArenaHeader *stackBottom() {
         return reinterpret_cast<ArenaHeader *>(ArenaSize);
     }
 };
 
 /* The chunk header (located at the end of the chunk to preserve arena alignment). */
 struct ChunkInfo {
-    Chunk           *link;
     JSRuntime       *runtime;
+    Chunk           *next;
+    Chunk           **prevp;
     ArenaHeader     *emptyArenaListHead;
     size_t          age;
     size_t          numFree;
 };
 
 const size_t BytesPerArena = ArenaSize + ArenaBitmapBytes + sizeof(MarkingDelay);
 const size_t ArenasPerChunk = (GC_CHUNK_SIZE - sizeof(ChunkInfo)) / BytesPerArena;
 
@@ -615,19 +616,27 @@ struct Chunk {
 
     uintptr_t address() const {
         uintptr_t addr = reinterpret_cast<uintptr_t>(this);
         JS_ASSERT(!(addr & GC_CHUNK_MASK));
         return addr;
     }
 
     void init(JSRuntime *rt);
-    bool unused();
-    bool hasAvailableArenas();
-    bool withinArenasRange(Cell *cell);
+
+    bool unused() const {
+        return info.numFree == ArenasPerChunk;
+    }
+
+    bool hasAvailableArenas() const {
+        return info.numFree > 0;
+    }
+
+    inline void addToAvailableList(JSCompartment *compartment);
+    inline void removeFromAvailableList();
 
     template <size_t thingSize>
     ArenaHeader *allocateArena(JSContext *cx, unsigned thingKind);
 
     void releaseArena(ArenaHeader *aheader);
 };
 
 JS_STATIC_ASSERT(sizeof(Chunk) <= GC_CHUNK_SIZE);