X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/14957cd040308e3eeec43d26bae5d76da13fcd85..6fe7ccc865dc7d7541b93c5bcaf6368d2c98a174:/heap/MarkStack.cpp

diff --git a/heap/MarkStack.cpp b/heap/MarkStack.cpp
index d3adfdc..cf6e351 100644
--- a/heap/MarkStack.cpp
+++ b/heap/MarkStack.cpp
@@ -26,24 +26,266 @@
 #include "config.h"
 #include "MarkStack.h"
 
+#include "CopiedSpace.h"
+#include "CopiedSpaceInlineMethods.h"
 #include "ConservativeRoots.h"
 #include "Heap.h"
+#include "Options.h"
 #include "JSArray.h"
 #include "JSCell.h"
 #include "JSObject.h"
 #include "ScopeChain.h"
 #include "Structure.h"
+#include "WriteBarrier.h"
+#include <wtf/MainThread.h>
 
 namespace JSC {
 
-size_t MarkStack::s_pageSize = 0;
+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(Options::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, Options::gcMarkStackSegmentSize);
+    }
+}
+
+MarkStackArray::MarkStackArray(MarkStackSegmentAllocator& allocator)
+    : m_allocator(allocator)
+    , m_segmentCapacity(MarkStackSegment::capacityFromSize(Options::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()
+{
+    ASSERT(!m_topSegment->m_previous);
+    m_allocator.release(m_topSegment);
+}
+
+void MarkStackArray::expand()
+{
+    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 >= Options::maximumNumberOfSharedSegments)
+        return false;
+        
+    size_t numberOfCellsToKeep = Options::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 Options::minimumNumberOfCellsToKeep, whichever is bigger.
+    size_t numberOfCellsToSteal = std::max((size_t)Options::minimumNumberOfCellsToKeep, other.size() / Options::numberOfGCMarkers);
+    while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
+        append(other.removeLast());
+}
+
+#if ENABLE(PARALLEL_GC)
+void MarkStackThreadSharedData::markingThreadMain()
+{
+    WTF::registerGCThread();
+    SlotVisitor slotVisitor(*this);
+    ParallelModeEnabler enabler(slotVisitor);
+    slotVisitor.drainFromShared(SlotVisitor::SlaveDrain);
+}
+
+void MarkStackThreadSharedData::markingThreadStartFunc(void* shared)
+{
+    static_cast<MarkStackThreadSharedData*>(shared)->markingThreadMain();
+}
+#endif
+
+MarkStackThreadSharedData::MarkStackThreadSharedData(JSGlobalData* globalData)
+    : m_globalData(globalData)
+    , m_copiedSpace(&globalData->heap.m_storageSpace)
+    , m_sharedMarkStack(m_segmentAllocator)
+    , m_numberOfActiveParallelMarkers(0)
+    , m_parallelMarkersShouldExit(false)
+{
+#if ENABLE(PARALLEL_GC)
+    for (unsigned i = 1; i < Options::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]);
+#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
+    ASSERT(m_opaqueRoots.isEmpty());
+#endif
+    
+    m_weakReferenceHarvesters.removeAll();
+}
 
 void MarkStack::reset()
 {
-    ASSERT(s_pageSize);
-    m_values.shrinkAllocation(s_pageSize);
-    m_markSets.shrinkAllocation(s_pageSize);
+    m_visitCount = 0;
+    ASSERT(m_stack.isEmpty());
+#if ENABLE(PARALLEL_GC)
+    ASSERT(m_opaqueRoots.isEmpty()); // Should have merged by now.
+#else
     m_opaqueRoots.clear();
+#endif
 }
 
 void MarkStack::append(ConservativeRoots& conservativeRoots)
@@ -54,100 +296,243 @@ void MarkStack::append(ConservativeRoots& conservativeRoots)
         internalAppend(roots[i]);
 }
 
-inline void MarkStack::visitChildren(JSCell* cell)
+ALWAYS_INLINE static void visitChildren(SlotVisitor& visitor, const JSCell* cell)
 {
+#if ENABLE(SIMPLE_HEAP_PROFILING)
+    m_visitedTypeCounts.count(cell);
+#endif
+
     ASSERT(Heap::isMarked(cell));
-    if (cell->structure()->typeInfo().type() < CompoundType) {
-        cell->JSCell::visitChildren(*this);
+    
+    if (isJSString(cell)) {
+        JSString::visitChildren(const_cast<JSCell*>(cell), visitor);
         return;
     }
 
-    if (!cell->structure()->typeInfo().overridesVisitChildren()) {
-        ASSERT(cell->isObject());
-#ifdef NDEBUG
-        asObject(cell)->visitChildrenDirect(*this);
-#else
-        ASSERT(!m_isCheckingForDefaultMarkViolation);
-        m_isCheckingForDefaultMarkViolation = true;
-        cell->visitChildren(*this);
-        ASSERT(m_isCheckingForDefaultMarkViolation);
-        m_isCheckingForDefaultMarkViolation = false;
-#endif
+    if (isJSFinalObject(cell)) {
+        JSObject::visitChildren(const_cast<JSCell*>(cell), visitor);
         return;
     }
-    if (cell->vptr() == m_jsArrayVPtr) {
-        asArray(cell)->visitChildrenDirect(*this);
+
+    if (isJSArray(cell)) {
+        JSArray::visitChildren(const_cast<JSCell*>(cell), visitor);
         return;
     }
-    cell->visitChildren(*this);
+
+    cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), visitor);
 }
 
-void MarkStack::drain()
+void SlotVisitor::donateSlow()
 {
-#if !ASSERT_DISABLED
-    ASSERT(!m_isDraining);
-    m_isDraining = true;
+    // 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() >= Options::sharedStackWakeupThreshold)
+            m_shared.m_markingCondition.broadcast();
+    }
+}
+
+void SlotVisitor::drain()
+{
+    ASSERT(m_isInParallelMode);
+   
+#if ENABLE(PARALLEL_GC)
+    if (Options::numberOfGCMarkers > 1) {
+        while (!m_stack.isEmpty()) {
+            m_stack.refill();
+            for (unsigned countdown = Options::minimumNumberOfScansBetweenRebalance; m_stack.canRemoveLast() && countdown--;)
+                visitChildren(*this, m_stack.removeLast());
+            donateKnownParallel();
+        }
+        
+        mergeOpaqueRootsIfNecessary();
+        return;
+    }
 #endif
-    while (!m_markSets.isEmpty() || !m_values.isEmpty()) {
-        while (!m_markSets.isEmpty() && m_values.size() < 50) {
-            ASSERT(!m_markSets.isEmpty());
-            MarkSet& current = m_markSets.last();
-            ASSERT(current.m_values);
-            JSValue* end = current.m_end;
-            ASSERT(current.m_values);
-            ASSERT(current.m_values != end);
-        findNextUnmarkedNullValue:
-            ASSERT(current.m_values != end);
-            JSValue value = *current.m_values;
-            current.m_values++;
-
-            JSCell* cell;
-            if (!value || !value.isCell() || Heap::testAndSetMarked(cell = value.asCell())) {
-                if (current.m_values == end) {
-                    m_markSets.removeLast();
-                    continue;
-                }
-                goto findNextUnmarkedNullValue;
-            }
+    
+    while (!m_stack.isEmpty()) {
+        m_stack.refill();
+        while (m_stack.canRemoveLast())
+            visitChildren(*this, m_stack.removeLast());
+    }
+}
 
-            if (cell->structure()->typeInfo().type() < CompoundType) {
-                cell->JSCell::visitChildren(*this);
-                if (current.m_values == end) {
-                    m_markSets.removeLast();
-                    continue;
-                }
-                goto findNextUnmarkedNullValue;
-            }
+void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
+{
+    ASSERT(m_isInParallelMode);
+    
+    ASSERT(Options::numberOfGCMarkers);
+    
+    bool shouldBeParallel;
 
-            if (current.m_values == end)
-                m_markSets.removeLast();
+#if ENABLE(PARALLEL_GC)
+    shouldBeParallel = Options::numberOfGCMarkers > 1;
+#else
+    ASSERT(Options::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--;
 
-            visitChildren(cell);
+            // 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()) {
+                        // Let any sleeping slaves know it's time for them to give their private CopiedBlocks back
+                        m_shared.m_markingCondition.broadcast();
+                        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) {
+                    if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty())
+                        doneCopying();
+                    m_shared.m_markingCondition.wait(m_shared.m_markingLock);
+                }
+                
+                // Is the VM exiting? If so, exit this thread.
+                if (m_shared.m_parallelMarkersShouldExit) {
+                    doneCopying();
+                    return;
+                }
+            }
+           
+            m_stack.stealSomeCellsFrom(m_shared.m_sharedMarkStack);
+            m_shared.m_numberOfActiveParallelMarkers++;
         }
-        while (!m_values.isEmpty())
-            visitChildren(m_values.removeLast());
+        
+        drain();
     }
-#if !ASSERT_DISABLED
-    m_isDraining = false;
 #endif
 }
 
-#if ENABLE(GC_VALIDATION)
-void MarkStack::validateSet(JSValue* values, size_t count)
+void MarkStack::mergeOpaqueRoots()
 {
-    for (size_t i = 0; i < count; i++) {
-        if (values[i])
-            validateValue(values[i]);
+    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 MarkStack::validateValue(JSValue value)
+void SlotVisitor::startCopying()
 {
-    if (!value)
+    ASSERT(!m_copyBlock);
+    if (!m_shared.m_copiedSpace->borrowBlock(&m_copyBlock))
         CRASH();
-    if (!value.isCell())
+}    
+
+void* SlotVisitor::allocateNewSpace(void* ptr, size_t bytes)
+{
+    if (CopiedSpace::isOversize(bytes)) {
+        m_shared.m_copiedSpace->pin(CopiedSpace::oversizeBlockFor(ptr));
+        return 0;
+    }
+
+    if (m_shared.m_copiedSpace->isPinned(ptr))
+        return 0;
+
+    // The only time it's possible to have a null copy block is if we have just started copying.
+    if (!m_copyBlock)
+        startCopying();
+
+    if (!CopiedSpace::fitsInBlock(m_copyBlock, bytes)) {
+        // We don't need to lock across these two calls because the master thread won't 
+        // call doneCopying() because this thread is considered active.
+        m_shared.m_copiedSpace->doneFillingBlock(m_copyBlock);
+        if (!m_shared.m_copiedSpace->borrowBlock(&m_copyBlock))
+            CRASH();
+    }
+    return CopiedSpace::allocateFromBlock(m_copyBlock, bytes);
+}
+
+void SlotVisitor::copyAndAppend(void** ptr, size_t bytes, JSValue* values, unsigned length)
+{
+    void* oldPtr = *ptr;
+    void* newPtr = allocateNewSpace(oldPtr, bytes);
+    if (newPtr) {
+        size_t jsValuesOffset = static_cast<size_t>(reinterpret_cast<char*>(values) - static_cast<char*>(oldPtr));
+
+        JSValue* newValues = reinterpret_cast_ptr<JSValue*>(static_cast<char*>(newPtr) + jsValuesOffset);
+        for (unsigned i = 0; i < length; i++) {
+            JSValue& value = values[i];
+            newValues[i] = value;
+            if (!value)
+                continue;
+            internalAppend(value);
+        }
+
+        memcpy(newPtr, oldPtr, jsValuesOffset);
+        *ptr = newPtr;
+    } else
+        append(values, length);
+}
+    
+void SlotVisitor::doneCopying()
+{
+    if (!m_copyBlock)
         return;
-    JSCell* cell = value.asCell();
+
+    m_shared.m_copiedSpace->doneFillingBlock(m_copyBlock);
+
+    m_copyBlock = 0;
+}
+
+void SlotVisitor::harvestWeakReferences()
+{
+    for (WeakReferenceHarvester* current = m_shared.m_weakReferenceHarvesters.head(); current; current = current->next())
+        current->visitWeakReferences(*this);
+}
+
+void SlotVisitor::finalizeUnconditionalFinalizers()
+{
+    while (m_shared.m_unconditionalFinalizers.hasNext())
+        m_shared.m_unconditionalFinalizers.removeNext()->finalizeUnconditionally();
+}
+
+#if ENABLE(GC_VALIDATION)
+void MarkStack::validate(JSCell* cell)
+{
     if (!cell)
         CRASH();
 
@@ -159,6 +544,10 @@ void MarkStack::validateValue(JSValue value)
     if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo())
         CRASH();
 }
+#else
+void MarkStack::validate(JSCell*)
+{
+}
 #endif
 
 } // namespace JSC