Bug 686144 - eliminating gc::MarkingDelay. r=wmccloskey
authorIgor Bukanov <igor@mir2.org>
Mon, 12 Sep 2011 11:43:43 +0200
changeset 78472 104fb6df714f1a9f45b01cde35530ac60b28651b
parent 78471 1d5cdab249a9e37a464dd4cbf4ac8a5301164cf3
child 78473 9208ee94b0120e0c18ab370f1fb7cfb8a0698339
push id78
push userclegnitto@mozilla.com
push dateFri, 16 Dec 2011 17:32:24 +0000
treeherdermozilla-release@79d24e644fdd [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswmccloskey
bugs686144
milestone9.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 686144 - eliminating gc::MarkingDelay. r=wmccloskey
js/src/jsgc.cpp
js/src/jsgc.h
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -222,17 +222,17 @@ Arena::finalize(JSContext *cx, AllocKind
 {
     /* Enforce requirements on size of T. */
     JS_ASSERT(thingSize % Cell::CellSize == 0);
     JS_ASSERT(thingSize <= 255);
 
     JS_ASSERT(aheader.allocated());
     JS_ASSERT(thingKind == aheader.getAllocKind());
     JS_ASSERT(thingSize == aheader.getThingSize());
-    JS_ASSERT(!aheader.getMarkingDelay()->link);
+    JS_ASSERT(!aheader.hasDelayedMarking);
 
     uintptr_t thing = thingsStart(thingKind);
     uintptr_t lastByte = thingsEnd() - 1;
 
     FreeSpan nextFree(aheader.getFirstFreeSpan());
     nextFree.checkSpan();
 
     FreeSpan newListHead;
@@ -382,42 +382,37 @@ FinalizeArenas(JSContext *cx, ArenaLists
         break;
     }
 }
 
 } /* namespace gc */
 } /* namespace js */
 
 void
-Chunk::init(JSRuntime *rt)
+Chunk::init()
 {
-    info.runtime = rt;
-    info.age = 0;
-    info.numFree = ArenasPerChunk;
+    JS_POISON(this, JS_FREE_PATTERN, GC_CHUNK_SIZE);
 
     /* Assemble all arenas into a linked list and mark them as not allocated. */
     ArenaHeader **prevp = &info.emptyArenaListHead;
     Arena *end = &arenas[JS_ARRAY_LENGTH(arenas)];
     for (Arena *a = &arenas[0]; a != end; ++a) {
-#ifdef DEBUG
-        memset(a, ArenaSize, JS_FREE_PATTERN);
-#endif
         *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();
-
     /* We clear the bitmap to guard against xpc_IsGrayGCThing being called on
        uninitialized data, which would happen before the first GC cycle. */
     bitmap.clear();
 
+    info.age = 0;
+    info.numFree = ArenasPerChunk;
+
     /* The rest of info fields are initialized in PickChunk. */
 }
 
 inline Chunk **
 GetAvailableChunkList(JSCompartment *comp)
 {
     JSRuntime *rt = comp->rt;
     return comp->isSystemCompartment
@@ -462,37 +457,38 @@ Chunk::allocateArena(JSContext *cx, Allo
     ArenaHeader *aheader = info.emptyArenaListHead;
     info.emptyArenaListHead = aheader->next;
     aheader->init(comp, thingKind);
     --info.numFree;
 
     if (!hasAvailableArenas())
         removeFromAvailableList();
 
-    JSRuntime *rt = info.runtime;
+    JSRuntime *rt = comp->rt;
     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;
 }
 
 void
 Chunk::releaseArena(ArenaHeader *aheader)
 {
     JS_ASSERT(aheader->allocated());
-    JSRuntime *rt = info.runtime;
+    JS_ASSERT(!aheader->hasDelayedMarking);
+    JSCompartment *comp = aheader->compartment;
+    JSRuntime *rt = comp->rt;
 #ifdef JS_THREADSAFE
     AutoLockGC maybeLock;
     if (rt->gcHelperThread.sweeping)
-        maybeLock.lock(info.runtime);
+        maybeLock.lock(rt);
 #endif
-    JSCompartment *comp = aheader->compartment;
 
     Probes::resizeHeap(comp, rt->gcBytes, rt->gcBytes - ArenaSize);
     JS_ASSERT(size_t(rt->gcBytes) >= ArenaSize);
     JS_ASSERT(size_t(comp->gcBytes) >= ArenaSize);
 #ifdef JS_THREADSAFE
     if (rt->gcHelperThread.sweeping) {
         rt->reduceGCTriggerBytes(GC_HEAP_GROWTH_FACTOR * ArenaSize);
         comp->reduceGCTriggerBytes(GC_HEAP_GROWTH_FACTOR * ArenaSize);
@@ -571,17 +567,17 @@ PickChunk(JSContext *cx)
         JS_ASSERT(rt->gcEmptyChunkCount >= 1);
         rt->gcEmptyChunkListHead = chunk->info.next;
         rt->gcEmptyChunkCount--;
     } else {
         chunk = AllocateGCChunk(rt);
         if (!chunk)
             return NULL;
 
-        chunk->init(rt);
+        chunk->init();
         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 = rt->gcChunkSet.lookupForAdd(chunk);
@@ -1541,17 +1537,17 @@ namespace js {
  * into a stack list with the pointer to stack top in
  * GCMarker::unmarkedArenaStackTop. delayMarkingChildren adds
  * arenas to the stack as necessary while markDelayedChildren pops the arenas
  * from the stack until it empties.
  */
 
 GCMarker::GCMarker(JSContext *cx)
   : color(0),
-    unmarkedArenaStackTop(MarkingDelay::stackBottom()),
+    unmarkedArenaStackTop(NULL),
     objStack(cx->runtime->gcMarkStackObjs, sizeof(cx->runtime->gcMarkStackObjs)),
     ropeStack(cx->runtime->gcMarkStackRopes, sizeof(cx->runtime->gcMarkStackRopes)),
     typeStack(cx->runtime->gcMarkStackTypes, sizeof(cx->runtime->gcMarkStackTypes)),
     xmlStack(cx->runtime->gcMarkStackXMLs, sizeof(cx->runtime->gcMarkStackXMLs)),
     largeStack(cx->runtime->gcMarkStackLarges, sizeof(cx->runtime->gcMarkStackLarges))
 {
     JS_TRACER_INIT(this, cx, NULL);
     markLaterArenas = 0;
@@ -1568,56 +1564,55 @@ GCMarker::~GCMarker()
 #endif
 }
 
 void
 GCMarker::delayMarkingChildren(const void *thing)
 {
     const Cell *cell = reinterpret_cast<const Cell *>(thing);
     ArenaHeader *aheader = cell->arenaHeader();
-    if (aheader->getMarkingDelay()->link) {
+    if (aheader->hasDelayedMarking) {
         /* Arena already scheduled to be marked later */
         return;
     }
-    aheader->getMarkingDelay()->link = unmarkedArenaStackTop;
-    unmarkedArenaStackTop = aheader;
+    aheader->setNextDelayedMarking(unmarkedArenaStackTop);
+    unmarkedArenaStackTop = aheader->getArena();
     markLaterArenas++;
 }
 
 static void
-MarkDelayedChildren(JSTracer *trc, ArenaHeader *aheader)
+MarkDelayedChildren(JSTracer *trc, Arena *a)
 {
-    AllocKind thingKind = aheader->getAllocKind();
-    JSGCTraceKind traceKind = MapAllocToTraceKind(thingKind);
-    size_t thingSize = aheader->getThingSize();
-    Arena *a = aheader->getArena();
+    AllocKind allocKind = a->aheader.getAllocKind();
+    JSGCTraceKind traceKind = MapAllocToTraceKind(allocKind);
+    size_t thingSize = Arena::thingSize(allocKind);
     uintptr_t end = a->thingsEnd();
-    for (uintptr_t thing = a->thingsStart(thingKind); thing != end; thing += thingSize) {
+    for (uintptr_t thing = a->thingsStart(allocKind); thing != end; thing += thingSize) {
         Cell *t = reinterpret_cast<Cell *>(thing);
         if (t->isMarked())
             JS_TraceChildren(trc, t, traceKind);
     }
 }
 
 void
 GCMarker::markDelayedChildren()
 {
-    while (unmarkedArenaStackTop != MarkingDelay::stackBottom()) {
+    while (unmarkedArenaStackTop) {
         /*
          * If marking gets delayed at the same arena again, we must repeat
          * marking of its things. For that we pop arena from the stack and
-         * clear its nextDelayedMarking before we begin the marking.
+         * clear its hasDelayedMarking flag before we begin the marking.
          */
-        ArenaHeader *aheader = unmarkedArenaStackTop;
-        unmarkedArenaStackTop = aheader->getMarkingDelay()->link;
-        JS_ASSERT(unmarkedArenaStackTop);
-        aheader->getMarkingDelay()->link = NULL;
+        Arena *a = unmarkedArenaStackTop;
+        JS_ASSERT(a->aheader.hasDelayedMarking);
         JS_ASSERT(markLaterArenas);
+        unmarkedArenaStackTop = a->aheader.getNextDelayedMarking();
+        a->aheader.hasDelayedMarking = 0;
         markLaterArenas--;
-        MarkDelayedChildren(this, aheader);
+        MarkDelayedChildren(this, a);
     }
     JS_ASSERT(!markLaterArenas);
 }
 
 } /* namespace js */
 
 #ifdef DEBUG
 static void
--- a/js/src/jsgc.h
+++ b/js/src/jsgc.h
@@ -73,17 +73,16 @@ js_TraceXML(JSTracer *trc, JSXML* thing)
 namespace js {
 
 class GCHelperThread;
 struct Shape;
 
 namespace gc {
 
 struct Arena;
-struct MarkingDelay;
 
 /*
  * This must be an upper bound, but we do not need the least upper bound, so
  * we just exclude non-background objects.
  */
 const size_t MAX_BACKGROUND_FINALIZE_KINDS = FINALIZE_LIMIT - (FINALIZE_OBJECT_LAST + 1) / 2;
 
 const size_t ArenaShift = 12;
@@ -352,16 +351,18 @@ struct FreeSpan {
         }
 #endif
     }
 
 };
 
 /* Every arena has a header. */
 struct ArenaHeader {
+    friend struct FreeLists;
+
     JSCompartment   *compartment;
     ArenaHeader     *next;
 
   private:
     /*
      * The first span of free things in the arena. We encode it as the start
      * and end offsets within the arena, not as FreeSpan structure, to
      * minimize the header size.
@@ -370,31 +371,58 @@ struct ArenaHeader {
 
     /*
      * One of AllocKind constants or FINALIZE_LIMIT when the arena does not
      * contain any GC things and is on the list of empty arenas in the GC
      * chunk. The latter allows to quickly check if the arena is allocated
      * during the conservative GC scanning without searching the arena in the
      * list.
      */
-    unsigned        allocKind;
+    size_t       allocKind          : 8;
 
-    friend struct FreeLists;
+    /*
+     * When recursive marking uses too much stack the marking is delayed and
+     * the corresponding arenas are put into a stack using the following field
+     * as a linkage. To distinguish the bottom of the stack from the arenas
+     * not present in the stack we use an extra flag to tag arenas on the
+     * stack.
+     *
+     * To minimize the ArenaHeader size we record the next delayed marking
+     * linkage as arenaAddress() >> ArenaShift and pack it with the allocKind
+     * field and hasDelayedMarking flag. We use 8 bits for the allocKind, not
+     * ArenaShift - 1, so the compiler can use byte-level memory instructions
+     * to access it.
+     */
+  public:
+    size_t       hasDelayedMarking  : 1;
+    size_t       nextDelayedMarking : JS_BITS_PER_WORD - 8 - 1;
 
-  public:
+    static void staticAsserts() {
+        /* We must be able to fit the allockind into uint8. */
+        JS_STATIC_ASSERT(FINALIZE_LIMIT <= 255);
+
+        /*
+         * nextDelayedMarkingpacking assumes that ArenaShift has enough bits
+         * to cover allocKind and hasDelayedMarking.
+         */
+        JS_STATIC_ASSERT(ArenaShift >= 8 + 1);
+    }
+
     inline uintptr_t address() const;
     inline Chunk *chunk() const;
 
     void setAsNotAllocated() {
-        allocKind = FINALIZE_LIMIT;
+        allocKind = size_t(FINALIZE_LIMIT);
+        hasDelayedMarking = 0;
+        nextDelayedMarking = 0;
     }
 
     bool allocated() const {
-        JS_ASSERT(allocKind <= FINALIZE_LIMIT);
-        return allocKind < FINALIZE_LIMIT;
+        JS_ASSERT(allocKind <= size_t(FINALIZE_LIMIT));
+        return allocKind < size_t(FINALIZE_LIMIT);
     }
 
     inline void init(JSCompartment *comp, AllocKind kind);
 
     uintptr_t arenaAddress() const {
         return address();
     }
 
@@ -426,21 +454,22 @@ struct ArenaHeader {
         return FreeSpan::decodeOffsets(arenaAddress(), firstFreeSpanOffsets);
     }
 
     void setFirstFreeSpan(const FreeSpan *span) {
         JS_ASSERT(span->isWithinArena(arenaAddress()));
         firstFreeSpanOffsets = span->encodeAsOffsets();
     }
 
-    inline MarkingDelay *getMarkingDelay() const;
-
 #ifdef DEBUG
     void checkSynchronizedWithFreeList() const;
 #endif
+
+    inline Arena *getNextDelayedMarking() const;
+    inline void setNextDelayedMarking(Arena *arena);
 };
 
 struct Arena {
     /*
      * Layout of an arena:
      * An arena is 4K in size and 4K-aligned. It starts with the ArenaHeader
      * descriptor followed by some pad bytes. The remainder of the arena is
      * filled with the array of T things. The pad bytes ensure that the thing
@@ -501,50 +530,26 @@ struct Arena {
     uintptr_t thingsEnd() {
         return address() + ArenaSize;
     }
 
     template <typename T>
     bool finalize(JSContext *cx, AllocKind thingKind, size_t thingSize);
 };
 
-/*
- * When recursive marking uses too much stack the marking is delayed and
- * the corresponding arenas are put into a stack using a linked via the
- * following per arena structure.
- */
-struct MarkingDelay {
-    ArenaHeader *link;
-
-    void init() {
-        link = NULL;
-    }
-
-    /*
-     * To separate arenas without things to mark later from the arena at the
-     * marked delay stack bottom we use for the latter a special sentinel
-     * value. We set it to the header for the second arena in the chunk
-     * starting at the 0 address.
-     */
-    static ArenaHeader *stackBottom() {
-        return reinterpret_cast<ArenaHeader *>(ArenaSize);
-    }
-};
-
 /* The chunk header (located at the end of the chunk to preserve arena alignment). */
 struct ChunkInfo {
-    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 BytesPerArena = ArenaSize + ArenaBitmapBytes;
 const size_t ArenasPerChunk = (GC_CHUNK_SIZE - sizeof(ChunkInfo)) / BytesPerArena;
 
 /* A chunk bitmap contains enough mark bits for all the cells in a chunk. */
 struct ChunkBitmap {
     uintptr_t bitmap[ArenaBitmapWords * ArenasPerChunk];
 
     JS_ALWAYS_INLINE void getMarkWordAndMask(const Cell *cell, uint32 color,
                                              uintptr_t **wordp, uintptr_t *maskp);
@@ -608,17 +613,16 @@ JS_STATIC_ASSERT(ArenaBitmapBytes * Aren
 
 /*
  * Chunks contain arenas and associated data structures (mark bitmap, delayed
  * marking state).
  */
 struct Chunk {
     Arena           arenas[ArenasPerChunk];
     ChunkBitmap     bitmap;
-    MarkingDelay    markingDelay[ArenasPerChunk];
     ChunkInfo       info;
 
     static Chunk *fromAddress(uintptr_t addr) {
         addr &= ~GC_CHUNK_MASK;
         return reinterpret_cast<Chunk *>(addr);
     }
 
     static bool withinArenasRange(uintptr_t addr) {
@@ -632,17 +636,17 @@ 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);
+    void init();
 
     bool unused() const {
         return info.numFree == ArenasPerChunk;
     }
 
     bool hasAvailableArenas() const {
         return info.numFree > 0;
     }
@@ -697,19 +701,21 @@ Cell::isAligned() const
     return Arena::isAligned(address(), arenaHeader()->getThingSize());
 }
 #endif
 
 inline void
 ArenaHeader::init(JSCompartment *comp, AllocKind kind)
 {
     JS_ASSERT(!allocated());
-    JS_ASSERT(!getMarkingDelay()->link);
+    JS_ASSERT(!hasDelayedMarking);
     compartment = comp;
-    allocKind = kind;
+
+    JS_STATIC_ASSERT(FINALIZE_LIMIT <= 255);
+    allocKind = size_t(kind);
 
     /* See comments in FreeSpan::allocateFromNewArena. */
     firstFreeSpanOffsets = FreeSpan::FullArenaOffsets;
 }
 
 inline uintptr_t
 ArenaHeader::address() const
 {
@@ -736,33 +742,41 @@ ArenaHeader::isEmpty() const
 
 inline size_t
 ArenaHeader::getThingSize() const
 {
     JS_ASSERT(allocated());
     return Arena::thingSize(getAllocKind());
 }
 
+inline Arena *
+ArenaHeader::getNextDelayedMarking() const
+{
+    return reinterpret_cast<Arena *>(nextDelayedMarking << ArenaShift);
+}
+
+inline void
+ArenaHeader::setNextDelayedMarking(Arena *arena)
+{
+    JS_ASSERT(!hasDelayedMarking);
+    hasDelayedMarking = 1;
+    nextDelayedMarking = arena->address() >> ArenaShift;
+}
+
 JS_ALWAYS_INLINE void
 ChunkBitmap::getMarkWordAndMask(const Cell *cell, uint32 color,
                                 uintptr_t **wordp, uintptr_t *maskp)
 {
     JS_ASSERT(cell->chunk() == Chunk::fromAddress(reinterpret_cast<uintptr_t>(this)));
     size_t bit = (cell->address() & GC_CHUNK_MASK) / Cell::CellSize + color;
     JS_ASSERT(bit < ArenaBitmapBits * ArenasPerChunk);
     *maskp = uintptr_t(1) << (bit % JS_BITS_PER_WORD);
     *wordp = &bitmap[bit / JS_BITS_PER_WORD];
 }
 
-inline MarkingDelay *
-ArenaHeader::getMarkingDelay() const
-{
-    return &chunk()->markingDelay[Chunk::arenaIndex(address())];
-}
-
 static void
 AssertValidColor(const void *thing, uint32 color)
 {
 #ifdef DEBUG
     ArenaHeader *aheader = reinterpret_cast<const js::gc::Cell *>(thing)->arenaHeader();
     JS_ASSERT_IF(color, color < aheader->getThingSize() / Cell::CellSize);
 #endif
 }
@@ -838,22 +852,16 @@ MapAllocToTraceKind(AllocKind thingKind)
         JSTRACE_STRING,     /* FINALIZE_EXTERNAL_STRING */
     };
     return map[thingKind];
 }
 
 inline JSGCTraceKind
 GetGCThingTraceKind(const void *thing);
 
-static inline JSRuntime *
-GetGCThingRuntime(void *thing)
-{
-    return reinterpret_cast<Cell *>(thing)->chunk()->info.runtime;
-}
-
 struct ArenaLists {
 
     /*
      * ArenaList::head points to the start of the list. Normally cursor points
      * to the first arena in the list with some free things and all arenas
      * before cursor are fully allocated. However, as the arena currently being
      * allocated from is considered full while its list of free spans is moved
      * into the freeList, during the GC or cell enumeration, when an
@@ -1476,17 +1484,17 @@ static const size_t LARGE_MARK_STACK_SIZ
 
 struct GCMarker : public JSTracer {
   private:
     /* The color is only applied to objects, functions and xml. */
     uint32 color;
 
   public:
     /* Pointer to the top of the stack of arenas we are delaying marking on. */
-    js::gc::ArenaHeader *unmarkedArenaStackTop;
+    js::gc::Arena *unmarkedArenaStackTop;
     /* Count of arenas that are currently in the stack. */
     DebugOnly<size_t> markLaterArenas;
 
 #ifdef JS_DUMP_CONSERVATIVE_GC_ROOTS
     js::gc::ConservativeGCStats conservativeStats;
     Vector<void *, 0, SystemAllocPolicy> conservativeRoots;
     const char *conservativeDumpFileName;
     void dumpConservativeRoots();