Changeset 98937 in webkit for trunk/Source/JavaScriptCore/heap/MarkStack.cpp

Timestamp:

Oct 31, 2011, 11:43:37 PM (14 years ago)

Author:

[email protected]

Message:

The GC should be parallel
​https://bugs.webkit.org/show_bug.cgi?id=70995

Source/JavaScriptCore:

Reviewed by Geoff Garen.

Added parallel tracing to the GC. This works by having local mark
stacks per thread, and a global shared one. Threads sometimes
donate cells from the mark stack to the global one if the heuristics
tell them that it's affordable to do so. Threads that have depleted
their local mark stacks try to steal some from the shared one.

Marking is now done using an atomic weak relaxed CAS (compare-and-swap).

This is a 23% speed-up on V8-splay when I use 4 marking threads,
leading to a 3.5% speed-up on V8.

It also appears that this reduces GC pause times on real websites by
more than half.

• JavaScriptCore.exp:
• JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.def:
• heap/Heap.cpp:

(JSC::Heap::Heap):
(JSC::Heap::~Heap):
(JSC::Heap::markRoots):

• heap/Heap.h:
• heap/MarkStack.cpp:

(JSC::MarkStackSegmentAllocator::MarkStackSegmentAllocator):
(JSC::MarkStackSegmentAllocator::~MarkStackSegmentAllocator):
(JSC::MarkStackSegmentAllocator::allocate):
(JSC::MarkStackSegmentAllocator::release):
(JSC::MarkStackSegmentAllocator::shrinkReserve):
(JSC::MarkStackArray::MarkStackArray):
(JSC::MarkStackArray::~MarkStackArray):
(JSC::MarkStackArray::expand):
(JSC::MarkStackArray::refill):
(JSC::MarkStackArray::donateSomeCellsTo):
(JSC::MarkStackArray::stealSomeCellsFrom):
(JSC::MarkStackThreadSharedData::markingThreadMain):
(JSC::MarkStackThreadSharedData::markingThreadStartFunc):
(JSC::MarkStackThreadSharedData::MarkStackThreadSharedData):
(JSC::MarkStackThreadSharedData::~MarkStackThreadSharedData):
(JSC::MarkStackThreadSharedData::reset):
(JSC::MarkStack::reset):
(JSC::SlotVisitor::donateSlow):
(JSC::SlotVisitor::drain):
(JSC::SlotVisitor::drainFromShared):
(JSC::MarkStack::mergeOpaqueRoots):
(JSC::SlotVisitor::harvestWeakReferences):

• heap/MarkStack.h:

(JSC::MarkStackSegment::data):
(JSC::MarkStackSegment::capacityFromSize):
(JSC::MarkStackSegment::sizeFromCapacity):
(JSC::MarkStackArray::postIncTop):
(JSC::MarkStackArray::preDecTop):
(JSC::MarkStackArray::setTopForFullSegment):
(JSC::MarkStackArray::setTopForEmptySegment):
(JSC::MarkStackArray::top):
(JSC::MarkStackArray::validatePrevious):
(JSC::MarkStack::addWeakReferenceHarvester):
(JSC::MarkStack::mergeOpaqueRootsIfNecessary):
(JSC::MarkStack::mergeOpaqueRootsIfProfitable):
(JSC::MarkStack::MarkStack):
(JSC::MarkStack::addOpaqueRoot):
(JSC::MarkStack::containsOpaqueRoot):
(JSC::MarkStack::opaqueRootCount):
(JSC::MarkStackArray::append):
(JSC::MarkStackArray::canRemoveLast):
(JSC::MarkStackArray::removeLast):
(JSC::MarkStackArray::isEmpty):
(JSC::MarkStackArray::canDonateSomeCells):
(JSC::MarkStackArray::size):
(JSC::ParallelModeEnabler::ParallelModeEnabler):
(JSC::ParallelModeEnabler::~ParallelModeEnabler):

• heap/MarkedBlock.h:

(JSC::MarkedBlock::testAndSetMarked):

• heap/SlotVisitor.h:

(JSC::SlotVisitor::donate):
(JSC::SlotVisitor::donateAndDrain):
(JSC::SlotVisitor::donateKnownParallel):
(JSC::SlotVisitor::SlotVisitor):

• heap/WeakReferenceHarvester.h:
• runtime/Heuristics.cpp:

(JSC::Heuristics::initializeHeuristics):

• runtime/Heuristics.h:
• wtf/Atomics.h:

(WTF::weakCompareAndSwap):

• wtf/Bitmap.h:

(WTF::::Bitmap):
(WTF::::get):
(WTF::::set):
(WTF::::testAndSet):
(WTF::::testAndClear):
(WTF::::concurrentTestAndSet):
(WTF::::concurrentTestAndClear):
(WTF::::clear):
(WTF::::clearAll):
(WTF::::nextPossiblyUnset):
(WTF::::findRunOfZeros):
(WTF::::count):
(WTF::::isEmpty):
(WTF::::isFull):

• wtf/MainThread.h:

(WTF::isMainThreadOrGCThread):

• wtf/Platform.h:
• wtf/ThreadSpecific.h:

(WTF::::isSet):

• wtf/mac/MainThreadMac.mm:

(WTF::initializeGCThreads):
(WTF::initializeMainThreadPlatform):
(WTF::initializeMainThreadToProcessMainThreadPlatform):
(WTF::registerGCThread):
(WTF::isMainThreadOrGCThread):

Source/WebCore:

Reviewed by Geoff Garen.

Added parallel tracing to the GC. This required loosening some assertions,
since some code may now be called from outside the main thread.

No new tests, since no behavior was changed.

• platform/TreeShared.h:

(WebCore::TreeShared::parent):

File:

• trunk/Source/JavaScriptCore/heap/MarkStack.cpp (modified) (4 diffs)

trunk/Source/JavaScriptCore/heap/MarkStack.cpp

@@ -29 +29 @@
 #include "ConservativeRoots.h"
 #include "Heap.h"
+#include "Heuristics.h"
 #include "JSArray.h"
 #include "JSCell.h"
@@ -35 +36 @@
 #include "Structure.h"
 #include "WriteBarrier.h"
+#include <wtf/MainThread.h>
 
 namespace JSC {
 
-MarkStackArray::MarkStackArray()
-    : m_top(0)
-    , m_allocated(pageSize())
-{
-    m_data = static_cast<const JSCell**>(MarkStack::allocateStack(m_allocated));
-    m_capacity = m_allocated / sizeof(JSCell*);
+MarkStackSegmentAllocator::MarkStackSegmentAllocator()
+    : m_nextFreeSegment(0)
+{
+}
+
+MarkStackSegmentAllocator::~MarkStackSegmentAllocator()
+{
+    shrinkReserve();
+}
+
+MarkStackSegment* MarkStackSegmentAllocator::allocate()
+{
+    {
+        MutexLocker locker(m_lock);
+        if (m_nextFreeSegment) {
+            MarkStackSegment* result = m_nextFreeSegment;
+            m_nextFreeSegment = result->m_previous;
+            return result;
+        }
+    }
+
+    return static_cast<MarkStackSegment*>(OSAllocator::reserveAndCommit(Heuristics::gcMarkStackSegmentSize));
+}
+
+void MarkStackSegmentAllocator::release(MarkStackSegment* segment)
+{
+    MutexLocker locker(m_lock);
+    segment->m_previous = m_nextFreeSegment;
+    m_nextFreeSegment = segment;
+}
+
+void MarkStackSegmentAllocator::shrinkReserve()
+{
+    MarkStackSegment* segments;
+    {
+        MutexLocker locker(m_lock);
+        segments = m_nextFreeSegment;
+        m_nextFreeSegment = 0;
+    }
+    while (segments) {
+        MarkStackSegment* toFree = segments;
+        segments = segments->m_previous;
+        OSAllocator::decommitAndRelease(toFree, Heuristics::gcMarkStackSegmentSize);
+    }
+}
+
+MarkStackArray::MarkStackArray(MarkStackSegmentAllocator& allocator)
+    : m_allocator(allocator)
+    , m_segmentCapacity(MarkStackSegment::capacityFromSize(Heuristics::gcMarkStackSegmentSize))
+    , m_top(0)
+    , m_numberOfPreviousSegments(0)
+{
+    m_topSegment = m_allocator.allocate();
+#if !ASSERT_DISABLED
+    m_topSegment->m_top = 0;
+#endif
+    m_topSegment->m_previous = 0;
 }
 
 MarkStackArray::~MarkStackArray()
 {
-    MarkStack::releaseStack(m_data, m_allocated);
+    ASSERT(!m_topSegment->m_previous);
+    m_allocator.release(m_topSegment);
 }
 
 void MarkStackArray::expand()
 {
-    size_t oldAllocation = m_allocated;
-    m_allocated *= 2;
-    m_capacity = m_allocated / sizeof(JSCell*);
-    void* newData = MarkStack::allocateStack(m_allocated);
-    memcpy(newData, m_data, oldAllocation);
-    MarkStack::releaseStack(m_data, oldAllocation);
-    m_data = static_cast<const JSCell**>(newData);
-}
-
-void MarkStackArray::shrinkAllocation(size_t size)
-{
-    ASSERT(size <= m_allocated);
-    ASSERT(isPageAligned(size));
-    if (size == m_allocated)
-        return;
-#if OS(WINDOWS)
-    // We cannot release a part of a region with VirtualFree. To get around this,
-    // we'll release the entire region and reallocate the size that we want.
-    MarkStack::releaseStack(m_data, m_allocated);
-    m_data = static_cast<const JSCell**>(MarkStack::allocateStack(size));
+    ASSERT(m_topSegment->m_top == m_segmentCapacity);
+    
+    m_numberOfPreviousSegments++;
+    
+    MarkStackSegment* nextSegment = m_allocator.allocate();
+#if !ASSERT_DISABLED
+    nextSegment->m_top = 0;
+#endif
+    nextSegment->m_previous = m_topSegment;
+    m_topSegment = nextSegment;
+    setTopForEmptySegment();
+    validatePrevious();
+}
+
+bool MarkStackArray::refill()
+{
+    validatePrevious();
+    if (top())
+        return true;
+    MarkStackSegment* toFree = m_topSegment;
+    MarkStackSegment* previous = m_topSegment->m_previous;
+    if (!previous)
+        return false;
+    ASSERT(m_numberOfPreviousSegments);
+    m_numberOfPreviousSegments--;
+    m_topSegment = previous;
+    m_allocator.release(toFree);
+    setTopForFullSegment();
+    validatePrevious();
+    return true;
+}
+
+bool MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
+{
+    ASSERT(m_segmentCapacity == other.m_segmentCapacity);
+    validatePrevious();
+    other.validatePrevious();
+        
+    // Fast check: see if the other mark stack already has enough segments.
+    if (other.m_numberOfPreviousSegments + 1 >= Heuristics::maximumNumberOfSharedSegments)
+        return false;
+        
+    size_t numberOfCellsToKeep = Heuristics::minimumNumberOfCellsToKeep;
+    ASSERT(m_top > numberOfCellsToKeep || m_topSegment->m_previous);
+        
+    // Looks like we should donate! Give the other mark stack all of our
+    // previous segments, and then top it off.
+    MarkStackSegment* previous = m_topSegment->m_previous;
+    while (previous) {
+        ASSERT(m_numberOfPreviousSegments);
+
+        MarkStackSegment* current = previous;
+        previous = current->m_previous;
+            
+        current->m_previous = other.m_topSegment->m_previous;
+        other.m_topSegment->m_previous = current;
+            
+        m_numberOfPreviousSegments--;
+        other.m_numberOfPreviousSegments++;
+    }
+    ASSERT(!m_numberOfPreviousSegments);
+    m_topSegment->m_previous = 0;
+    validatePrevious();
+    other.validatePrevious();
+        
+    // Now top off. We want to keep at a minimum numberOfCellsToKeep, but if
+    // we really have a lot of work, we give up half.
+    if (m_top > numberOfCellsToKeep * 2)
+        numberOfCellsToKeep = m_top / 2;
+    while (m_top > numberOfCellsToKeep)
+        other.append(removeLast());
+        
+    return true;
+}
+
+void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other)
+{
+    ASSERT(m_segmentCapacity == other.m_segmentCapacity);
+    validatePrevious();
+    other.validatePrevious();
+        
+    // If other has an entire segment, steal it and return.
+    if (other.m_topSegment->m_previous) {
+        ASSERT(other.m_topSegment->m_previous->m_top == m_segmentCapacity);
+            
+        // First remove a segment from other.
+        MarkStackSegment* current = other.m_topSegment->m_previous;
+        other.m_topSegment->m_previous = current->m_previous;
+        other.m_numberOfPreviousSegments--;
+            
+        ASSERT(!!other.m_numberOfPreviousSegments == !!other.m_topSegment->m_previous);
+            
+        // Now add it to this.
+        current->m_previous = m_topSegment->m_previous;
+        m_topSegment->m_previous = current;
+        m_numberOfPreviousSegments++;
+            
+        validatePrevious();
+        other.validatePrevious();
+        return;
+    }
+        
+    // Otherwise drain 1/Nth of the shared array where N is the number of
+    // workers, or Heuristics::minimumNumberOfCellsToKeep, whichever is bigger.
+    size_t numberOfCellsToSteal = std::max((size_t)Heuristics::minimumNumberOfCellsToKeep, other.size() / Heuristics::numberOfGCMarkers);
+    while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
+        append(other.removeLast());
+}
+
+#if ENABLE(PARALLEL_GC)
+void MarkStackThreadSharedData::markingThreadMain()
+{
+    WTF::registerGCThread();
+    SlotVisitor slotVisitor(*this, m_globalData->jsArrayVPtr, m_globalData->jsFinalObjectVPtr, m_globalData->jsStringVPtr);
+    ParallelModeEnabler enabler(slotVisitor);
+    slotVisitor.drainFromShared(SlotVisitor::SlaveDrain);
+}
+
+void* MarkStackThreadSharedData::markingThreadStartFunc(void* shared)
+{
+    static_cast<MarkStackThreadSharedData*>(shared)->markingThreadMain();
+    return 0;
+}
+#endif
+
+MarkStackThreadSharedData::MarkStackThreadSharedData(JSGlobalData* globalData)
+    : m_globalData(globalData)
+    , m_sharedMarkStack(m_segmentAllocator)
+    , m_numberOfActiveParallelMarkers(0)
+    , m_parallelMarkersShouldExit(false)
+    , m_firstWeakReferenceHarvester(0)
+{
+#if ENABLE(PARALLEL_GC)
+    for (unsigned i = 1; i < Heuristics::numberOfGCMarkers; ++i) {
+        m_markingThreads.append(createThread(markingThreadStartFunc, this, "JavaScriptCore::Marking"));
+        ASSERT(m_markingThreads.last());
+    }
+#endif
+}
+
+MarkStackThreadSharedData::~MarkStackThreadSharedData()
+{
+#if ENABLE(PARALLEL_GC)    
+    // Destroy our marking threads.
+    {
+        MutexLocker locker(m_markingLock);
+        m_parallelMarkersShouldExit = true;
+        m_markingCondition.broadcast();
+    }
+    for (unsigned i = 0; i < m_markingThreads.size(); ++i)
+        waitForThreadCompletion(m_markingThreads[i], 0);
+#endif
+}
+    
+void MarkStackThreadSharedData::reset()
+{
+    ASSERT(!m_numberOfActiveParallelMarkers);
+    ASSERT(!m_parallelMarkersShouldExit);
+    ASSERT(m_sharedMarkStack.isEmpty());
+    
+#if ENABLE(PARALLEL_GC)
+    m_segmentAllocator.shrinkReserve();
+    m_opaqueRoots.clear();
 #else
-    MarkStack::releaseStack(reinterpret_cast<char*>(m_data) + size, m_allocated - size);
-#endif
-    m_allocated = size;
-    m_capacity = m_allocated / sizeof(JSCell*);
+    ASSERT(m_opaqueRoots.isEmpty());
+#endif
 }
 
@@ -83 +278 @@
 {
     m_visitCount = 0;
-    m_stack.shrinkAllocation(pageSize());
+    ASSERT(m_stack.isEmpty());
+#if ENABLE(PARALLEL_GC)
+    ASSERT(m_opaqueRoots.isEmpty()); // Should have merged by now.
+#else
     m_opaqueRoots.clear();
+#endif
 }
 
@@ -121 +320 @@
 }
 
+void SlotVisitor::donateSlow()
+{
+    // Refuse to donate if shared has more entries than I do.
+    if (m_shared.m_sharedMarkStack.size() > m_stack.size())
+        return;
+    MutexLocker locker(m_shared.m_markingLock);
+    if (m_stack.donateSomeCellsTo(m_shared.m_sharedMarkStack)) {
+        // Only wake up threads if the shared stack is big enough; otherwise assume that
+        // it's more profitable for us to just scan this ourselves later.
+        if (m_shared.m_sharedMarkStack.size() >= Heuristics::sharedStackWakeupThreshold)
+            m_shared.m_markingCondition.broadcast();
+    }
+}
+
 void SlotVisitor::drain()
 {
+    ASSERT(m_isInParallelMode);
+    
     void* jsFinalObjectVPtr = m_jsFinalObjectVPtr;
     void* jsArrayVPtr = m_jsArrayVPtr;
     void* jsStringVPtr = m_jsStringVPtr;
 
-    while (!m_stack.isEmpty())
-        visitChildren(*this, m_stack.removeLast(), jsFinalObjectVPtr, jsArrayVPtr, jsStringVPtr);
+#if ENABLE(PARALLEL_GC)
+    if (Heuristics::numberOfGCMarkers > 1) {
+        while (!m_stack.isEmpty()) {
+            m_stack.refill();
+            for (unsigned countdown = Heuristics::minimumNumberOfScansBetweenRebalance; m_stack.canRemoveLast() && countdown--;)
+                visitChildren(*this, m_stack.removeLast(), jsFinalObjectVPtr, jsArrayVPtr, jsStringVPtr);
+            donateKnownParallel();
+        }
+        
+        mergeOpaqueRootsIfNecessary();
+        return;
+    }
+#endif
+    
+    while (!m_stack.isEmpty()) {
+        m_stack.refill();
+        while (m_stack.canRemoveLast())
+            visitChildren(*this, m_stack.removeLast(), jsFinalObjectVPtr, jsArrayVPtr, jsStringVPtr);
+    }
+}
+
+void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
+{
+    ASSERT(m_isInParallelMode);
+    
+    ASSERT(Heuristics::numberOfGCMarkers);
+    
+    bool shouldBeParallel;
+
+#if ENABLE(PARALLEL_GC)
+    shouldBeParallel = Heuristics::numberOfGCMarkers > 1;
+#else
+    ASSERT(Heuristics::numberOfGCMarkers == 1);
+    shouldBeParallel = false;
+#endif
+    
+    if (!shouldBeParallel) {
+        // This call should be a no-op.
+        ASSERT_UNUSED(sharedDrainMode, sharedDrainMode == MasterDrain);
+        ASSERT(m_stack.isEmpty());
+        ASSERT(m_shared.m_sharedMarkStack.isEmpty());
+        return;
+    }
+    
+#if ENABLE(PARALLEL_GC)
+    {
+        MutexLocker locker(m_shared.m_markingLock);
+        m_shared.m_numberOfActiveParallelMarkers++;
+    }
+    while (true) {
+        {
+            MutexLocker locker(m_shared.m_markingLock);
+            m_shared.m_numberOfActiveParallelMarkers--;
+
+            // How we wait differs depending on drain mode.
+            if (sharedDrainMode == MasterDrain) {
+                // Wait until either termination is reached, or until there is some work
+                // for us to do.
+                while (true) {
+                    // Did we reach termination?
+                    if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty())
+                        return;
+                    
+                    // Is there work to be done?
+                    if (!m_shared.m_sharedMarkStack.isEmpty())
+                        break;
+                    
+                    // Otherwise wait.
+                    m_shared.m_markingCondition.wait(m_shared.m_markingLock);
+                }
+            } else {
+                ASSERT(sharedDrainMode == SlaveDrain);
+                
+                // Did we detect termination? If so, let the master know.
+                if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty())
+                    m_shared.m_markingCondition.broadcast();
+                
+                while (m_shared.m_sharedMarkStack.isEmpty() && !m_shared.m_parallelMarkersShouldExit)
+                    m_shared.m_markingCondition.wait(m_shared.m_markingLock);
+                
+                // Is the VM exiting? If so, exit this thread.
+                if (m_shared.m_parallelMarkersShouldExit)
+                    return;
+            }
+            
+            m_stack.stealSomeCellsFrom(m_shared.m_sharedMarkStack);
+            m_shared.m_numberOfActiveParallelMarkers++;
+        }
+        
+        drain();
+    }
+#endif
+}
+
+void MarkStack::mergeOpaqueRoots()
+{
+    ASSERT(!m_opaqueRoots.isEmpty()); // Should only be called when opaque roots are non-empty.
+    {
+        MutexLocker locker(m_shared.m_opaqueRootsLock);
+        HashSet<void*>::iterator begin = m_opaqueRoots.begin();
+        HashSet<void*>::iterator end = m_opaqueRoots.end();
+        for (HashSet<void*>::iterator iter = begin; iter != end; ++iter)
+            m_shared.m_opaqueRoots.add(*iter);
+    }
+    m_opaqueRoots.clear();
 }
 
 void SlotVisitor::harvestWeakReferences()
 {
-    while (m_firstWeakReferenceHarvester) {
-        WeakReferenceHarvester* current = m_firstWeakReferenceHarvester;
+    while (m_shared.m_firstWeakReferenceHarvester) {
+        WeakReferenceHarvester* current = m_shared.m_firstWeakReferenceHarvester;
         WeakReferenceHarvester* next = reinterpret_cast<WeakReferenceHarvester*>(current->m_nextAndFlag & ~1);
         current->m_nextAndFlag = 0;
-        m_firstWeakReferenceHarvester = next;
+        m_shared.m_firstWeakReferenceHarvester = next;
         current->visitWeakReferences(*this);
     }