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

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.h (modified) (11 diffs)

trunk/Source/JavaScriptCore/heap/MarkStack.h

@@ -28 +28 @@
 
 #include "HandleTypes.h"
+#include "Heuristics.h"
 #include "JSValue.h"
 #include "Register.h"
@@ -44 +45 @@
     class JSGlobalData;
     class MarkStack;
+    class ParallelModeEnabler;
     class Register;
+    class SlotVisitor;
     template<typename T> class WriteBarrierBase;
     template<typename T> class JITWriteBarrier;
     
+    struct MarkStackSegment {
+        MarkStackSegment* m_previous;
+#if !ASSERT_DISABLED
+        size_t m_top;
+#endif
+        
+        const JSCell** data()
+        {
+            return bitwise_cast<const JSCell**>(this + 1);
+        }
+        
+        static size_t capacityFromSize(size_t size)
+        {
+            return (size - sizeof(MarkStackSegment)) / sizeof(const JSCell*);
+        }
+        
+        static size_t sizeFromCapacity(size_t capacity)
+        {
+            return sizeof(MarkStackSegment) + capacity * sizeof(const JSCell*);
+        }
+    };
+
+    class MarkStackSegmentAllocator {
+    public:
+        MarkStackSegmentAllocator();
+        ~MarkStackSegmentAllocator();
+        
+        MarkStackSegment* allocate();
+        void release(MarkStackSegment*);
+        
+        void shrinkReserve();
+        
+    private:
+        Mutex m_lock;
+        MarkStackSegment* m_nextFreeSegment;
+    };
+
     class MarkStackArray {
     public:
-        MarkStackArray();
+        MarkStackArray(MarkStackSegmentAllocator&);
         ~MarkStackArray();
 
+        void append(const JSCell*);
+
+        bool canRemoveLast();
+        const JSCell* removeLast();
+        bool refill();
+        
+        bool isEmpty();
+        
+        bool canDonateSomeCells(); // Returns false if you should definitely not call doanteSomeCellsTo().
+        bool donateSomeCellsTo(MarkStackArray& other); // Returns true if some cells were donated.
+        
+        void stealSomeCellsFrom(MarkStackArray& other);
+
+        size_t size();
+
+    private:
+        MarkStackSegment* m_topSegment;
+        
         void expand();
-        void append(const JSCell*);
-
-        const JSCell* removeLast();
-
-        bool isEmpty();
-
-        void shrinkAllocation(size_t);
-
+        
+        MarkStackSegmentAllocator& m_allocator;
+
+        size_t m_segmentCapacity;
+        size_t m_top;
+        size_t m_numberOfPreviousSegments;
+        
+        size_t postIncTop()
+        {
+            size_t result = m_top++;
+            ASSERT(result == m_topSegment->m_top++);
+            return result;
+        }
+        
+        size_t preDecTop()
+        {
+            size_t result = --m_top;
+            ASSERT(result == --m_topSegment->m_top);
+            return result;
+        }
+        
+        void setTopForFullSegment()
+        {
+            ASSERT(m_topSegment->m_top == m_segmentCapacity);
+            m_top = m_segmentCapacity;
+        }
+        
+        void setTopForEmptySegment()
+        {
+            ASSERT(!m_topSegment->m_top);
+            m_top = 0;
+        }
+        
+        size_t top()
+        {
+            ASSERT(m_top == m_topSegment->m_top);
+            return m_top;
+        }
+        
+#if ASSERT_DISABLED
+        void validatePrevious() { }
+#else
+        void validatePrevious()
+        {
+            unsigned count = 0;
+            for (MarkStackSegment* current = m_topSegment->m_previous; current; current = current->m_previous)
+                count++;
+            ASSERT(count == m_numberOfPreviousSegments);
+        }
+#endif
+    };
+
+    class MarkStackThreadSharedData {
+    public:
+        MarkStackThreadSharedData(JSGlobalData*);
+        ~MarkStackThreadSharedData();
+        
+        void reset();
+    
     private:
-        const JSCell** m_data;
-        size_t m_top;
-        size_t m_capacity;
-        size_t m_allocated;
+        friend class MarkStack;
+        friend class SlotVisitor;
+
+#if ENABLE(PARALLEL_GC)
+        void markingThreadMain();
+        static void* markingThreadStartFunc(void* heap);
+#endif
+
+        JSGlobalData* m_globalData;
+        
+        MarkStackSegmentAllocator m_segmentAllocator;
+        
+        Vector<ThreadIdentifier> m_markingThreads;
+        
+        Mutex m_markingLock;
+        ThreadCondition m_markingCondition;
+        MarkStackArray m_sharedMarkStack;
+        unsigned m_numberOfActiveParallelMarkers;
+        bool m_parallelMarkersShouldExit;
+
+        Mutex m_opaqueRootsLock;
+        HashSet<void*> m_opaqueRoots;
+
+        Mutex m_weakReferenceHarvesterLock;
+        WeakReferenceHarvester* m_firstWeakReferenceHarvester;
     };
 
@@ -74 +204 @@
 
     public:
-        static void* allocateStack(size_t);
-        static void releaseStack(void*, size_t);
-
-        MarkStack(void* jsArrayVPtr, void* jsFinalObjectVPtr, void* jsStringVPtr);
+        MarkStack(MarkStackThreadSharedData&, void* jsArrayVPtr, void* jsFinalObjectVPtr, void* jsStringVPtr);
         ~MarkStack();
 
@@ -89 +216 @@
         void appendUnbarrieredPointer(T**);
         
-        bool addOpaqueRoot(void*);
+        void addOpaqueRoot(void*);
         bool containsOpaqueRoot(void*);
         int opaqueRootCount();
@@ -103 +230 @@
         void addWeakReferenceHarvester(WeakReferenceHarvester* weakReferenceHarvester)
         {
+            MutexLocker locker(m_shared.m_weakReferenceHarvesterLock);
             if (weakReferenceHarvester->m_nextAndFlag & 1)
                 return;
-            weakReferenceHarvester->m_nextAndFlag = reinterpret_cast<uintptr_t>(m_firstWeakReferenceHarvester) | 1;
-            m_firstWeakReferenceHarvester = weakReferenceHarvester;
+            weakReferenceHarvester->m_nextAndFlag = reinterpret_cast<uintptr_t>(m_shared.m_firstWeakReferenceHarvester) | 1;
+            m_shared.m_firstWeakReferenceHarvester = weakReferenceHarvester;
         }
 
@@ -118 +246 @@
         void internalAppend(JSCell*);
         void internalAppend(JSValue);
-
+        
+        void mergeOpaqueRoots();
+        
+        void mergeOpaqueRootsIfNecessary()
+        {
+            if (m_opaqueRoots.isEmpty())
+                return;
+            mergeOpaqueRoots();
+        }
+        
+        void mergeOpaqueRootsIfProfitable()
+        {
+            if (static_cast<unsigned>(m_opaqueRoots.size()) < Heuristics::opaqueRootMergeThreshold)
+                return;
+            mergeOpaqueRoots();
+        }
+        
         MarkStackArray m_stack;
         void* m_jsArrayVPtr;
@@ -124 +268 @@
         void* m_jsStringVPtr;
         HashSet<void*> m_opaqueRoots; // Handle-owning data structures not visible to the garbage collector.
-        WeakReferenceHarvester* m_firstWeakReferenceHarvester;
         
 #if !ASSERT_DISABLED
@@ -132 +275 @@
 #endif
     protected:
+        friend class ParallelModeEnabler;
+        
         size_t m_visitCount;
-    };
-
-    inline MarkStack::MarkStack(void* jsArrayVPtr, void* jsFinalObjectVPtr, void* jsStringVPtr)
-        : m_jsArrayVPtr(jsArrayVPtr)
+        bool m_isInParallelMode;
+        
+        MarkStackThreadSharedData& m_shared;
+    };
+
+    inline MarkStack::MarkStack(MarkStackThreadSharedData& shared, void* jsArrayVPtr, void* jsFinalObjectVPtr, void* jsStringVPtr)
+        : m_stack(shared.m_segmentAllocator)
+        , m_jsArrayVPtr(jsArrayVPtr)
         , m_jsFinalObjectVPtr(jsFinalObjectVPtr)
         , m_jsStringVPtr(jsStringVPtr)
-        , m_firstWeakReferenceHarvester(0)
 #if !ASSERT_DISABLED
         , m_isCheckingForDefaultMarkViolation(false)
@@ -145 +293 @@
 #endif
         , m_visitCount(0)
+        , m_isInParallelMode(false)
+        , m_shared(shared)
     {
     }
@@ -153 +303 @@
     }
 
-    inline bool MarkStack::addOpaqueRoot(void* root)
-    {
-        return m_opaqueRoots.add(root).second;
+    inline void MarkStack::addOpaqueRoot(void* root)
+    {
+#if ENABLE(PARALLEL_GC)
+        if (Heuristics::numberOfGCMarkers == 1) {
+            // Put directly into the shared HashSet.
+            m_shared.m_opaqueRoots.add(root);
+            return;
+        }
+        // Put into the local set, but merge with the shared one every once in
+        // a while to make sure that the local sets don't grow too large.
+        mergeOpaqueRootsIfProfitable();
+        m_opaqueRoots.add(root);
+#else
+        m_opaqueRoots.add(root);
+#endif
     }
 
     inline bool MarkStack::containsOpaqueRoot(void* root)
     {
+        ASSERT(!m_isInParallelMode);
+#if ENABLE(PARALLEL_GC)
+        ASSERT(m_opaqueRoots.isEmpty());
+        return m_shared.m_opaqueRoots.contains(root);
+#else
         return m_opaqueRoots.contains(root);
+#endif
     }
 
     inline int MarkStack::opaqueRootCount()
     {
+        ASSERT(!m_isInParallelMode);
+#if ENABLE(PARALLEL_GC)
+        ASSERT(m_opaqueRoots.isEmpty());
+        return m_shared.m_opaqueRoots.size();
+#else
         return m_opaqueRoots.size();
-    }
-
-    inline void* MarkStack::allocateStack(size_t size)
-    {
-        return OSAllocator::reserveAndCommit(size);
-    }
-
-    inline void MarkStack::releaseStack(void* addr, size_t size)
-    {
-        OSAllocator::decommitAndRelease(addr, size);
+#endif
     }
 
     inline void MarkStackArray::append(const JSCell* cell)
     {
-        if (m_top == m_capacity)
+        if (m_top == m_segmentCapacity)
             expand();
-        m_data[m_top++] = cell;
+        m_topSegment->data()[postIncTop()] = cell;
+    }
+
+    inline bool MarkStackArray::canRemoveLast()
+    {
+        return !!m_top;
     }
 
     inline const JSCell* MarkStackArray::removeLast()
     {
-        ASSERT(m_top);
-        return m_data[--m_top];
-    }
-    
+        return m_topSegment->data()[preDecTop()];
+    }
+
     inline bool MarkStackArray::isEmpty()
     {
-        return !m_top;
+        if (m_top)
+            return false;
+        if (m_topSegment->m_previous) {
+            ASSERT(m_topSegment->m_previous->m_top == m_segmentCapacity);
+            return false;
+        }
+        return true;
+    }
+
+    inline bool MarkStackArray::canDonateSomeCells()
+    {
+        size_t numberOfCellsToKeep = Heuristics::minimumNumberOfCellsToKeep;
+        // Another check: see if we have enough cells to warrant donation.
+        if (m_top <= numberOfCellsToKeep) {
+            // This indicates that we might not want to donate anything; check if we have
+            // another full segment. If not, then don't donate.
+            if (!m_topSegment->m_previous)
+                return false;
+            
+            ASSERT(m_topSegment->m_previous->m_top == m_segmentCapacity);
+        }
+        
+        return true;
+    }
+
+    inline size_t MarkStackArray::size()
+    {
+        return m_top + m_segmentCapacity * m_numberOfPreviousSegments;
     }
 
@@ -235 +430 @@
     }
 
-    class SlotVisitor;
+    class ParallelModeEnabler {
+    public:
+        ParallelModeEnabler(MarkStack& stack)
+            : m_stack(stack)
+        {
+            ASSERT(!m_stack.m_isInParallelMode);
+            m_stack.m_isInParallelMode = true;
+        }
+        
+        ~ParallelModeEnabler()
+        {
+            ASSERT(m_stack.m_isInParallelMode);
+            m_stack.m_isInParallelMode = false;
+        }
+        
+    private:
+        MarkStack& m_stack;
+    };
 
 } // namespace JSC