X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/14957cd040308e3eeec43d26bae5d76da13fcd85..81345200c95645a1b0d2635520f96ad55dfde63f:/heap/MarkStack.cpp?ds=inline

diff --git a/heap/MarkStack.cpp b/heap/MarkStack.cpp
index d3adfdc..66201f4 100644
--- a/heap/MarkStack.cpp
+++ b/heap/MarkStack.cpp
@@ -26,139 +26,90 @@
 #include "config.h"
 #include "MarkStack.h"
 
-#include "ConservativeRoots.h"
-#include "Heap.h"
-#include "JSArray.h"
-#include "JSCell.h"
-#include "JSObject.h"
-#include "ScopeChain.h"
-#include "Structure.h"
+#include "JSCInlines.h"
 
 namespace JSC {
 
-size_t MarkStack::s_pageSize = 0;
-
-void MarkStack::reset()
+MarkStackArray::MarkStackArray(BlockAllocator& blockAllocator)
+    : GCSegmentedArray<const JSCell*>(blockAllocator)
 {
-    ASSERT(s_pageSize);
-    m_values.shrinkAllocation(s_pageSize);
-    m_markSets.shrinkAllocation(s_pageSize);
-    m_opaqueRoots.clear();
 }
 
-void MarkStack::append(ConservativeRoots& conservativeRoots)
+void MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
 {
-    JSCell** roots = conservativeRoots.roots();
-    size_t size = conservativeRoots.size();
-    for (size_t i = 0; i < size; ++i)
-        internalAppend(roots[i]);
-}
+    // Try to donate about 1 / 2 of our cells. To reduce copying costs,
+    // we prefer donating whole segments over donating individual cells,
+    // even if this skews away from our 1 / 2 target.
 
-inline void MarkStack::visitChildren(JSCell* cell)
-{
-    ASSERT(Heap::isMarked(cell));
-    if (cell->structure()->typeInfo().type() < CompoundType) {
-        cell->JSCell::visitChildren(*this);
-        return;
-    }
+    size_t segmentsToDonate = m_numberOfSegments / 2; // If we only have one segment (our head) we don't donate any segments.
 
-    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
-        return;
-    }
-    if (cell->vptr() == m_jsArrayVPtr) {
-        asArray(cell)->visitChildrenDirect(*this);
+    if (!segmentsToDonate) {
+        size_t cellsToDonate = m_top / 2; // Round down to donate 0 / 1 cells.
+        while (cellsToDonate--) {
+            ASSERT(m_top);
+            other.append(removeLast());
+        }
         return;
     }
-    cell->visitChildren(*this);
-}
 
-void MarkStack::drain()
-{
-#if !ASSERT_DISABLED
-    ASSERT(!m_isDraining);
-    m_isDraining = true;
-#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;
-            }
-
-            if (cell->structure()->typeInfo().type() < CompoundType) {
-                cell->JSCell::visitChildren(*this);
-                if (current.m_values == end) {
-                    m_markSets.removeLast();
-                    continue;
-                }
-                goto findNextUnmarkedNullValue;
-            }
-
-            if (current.m_values == end)
-                m_markSets.removeLast();
-
-            visitChildren(cell);
-        }
-        while (!m_values.isEmpty())
-            visitChildren(m_values.removeLast());
+    validatePrevious();
+    other.validatePrevious();
+
+    // Remove our head and the head of the other list before we start moving segments around.
+    // We'll add them back on once we're done donating.
+    GCArraySegment<const JSCell*>* myHead = m_segments.removeHead();
+    GCArraySegment<const JSCell*>* otherHead = other.m_segments.removeHead();
+
+    while (segmentsToDonate--) {
+        GCArraySegment<const JSCell*>* current = m_segments.removeHead();
+        ASSERT(current);
+        ASSERT(m_numberOfSegments > 1);
+        other.m_segments.push(current);
+        m_numberOfSegments--;
+        other.m_numberOfSegments++;
     }
-#if !ASSERT_DISABLED
-    m_isDraining = false;
-#endif
-}
 
-#if ENABLE(GC_VALIDATION)
-void MarkStack::validateSet(JSValue* values, size_t count)
-{
-    for (size_t i = 0; i < count; i++) {
-        if (values[i])
-            validateValue(values[i]);
-    }
+    // Put the original heads back in their places.
+    m_segments.push(myHead);
+    other.m_segments.push(otherHead);
+
+    validatePrevious();
+    other.validatePrevious();
 }
 
-void MarkStack::validateValue(JSValue value)
+void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other, size_t idleThreadCount)
 {
-    if (!value)
-        CRASH();
-    if (!value.isCell())
+    // Try to steal 1 / Nth of the shared array, where N is the number of idle threads.
+    // To reduce copying costs, we prefer stealing a whole segment over stealing
+    // individual cells, even if this skews away from our 1 / N target.
+
+    validatePrevious();
+    other.validatePrevious();
+        
+    // If other has an entire segment, steal it and return.
+    if (other.m_numberOfSegments > 1) {
+        // Move the heads of the lists aside. We'll push them back on after.
+        GCArraySegment<const JSCell*>* otherHead = other.m_segments.removeHead();
+        GCArraySegment<const JSCell*>* myHead = m_segments.removeHead();
+
+        ASSERT(other.m_segments.head()->m_top == s_segmentCapacity);
+
+        m_segments.push(other.m_segments.removeHead());
+
+        m_numberOfSegments++;
+        other.m_numberOfSegments--;
+        
+        m_segments.push(myHead);
+        other.m_segments.push(otherHead);
+    
+        validatePrevious();
+        other.validatePrevious();
         return;
-    JSCell* cell = value.asCell();
-    if (!cell)
-        CRASH();
-
-    if (!cell->structure())
-        CRASH();
+    }
 
-    // Both the cell's structure, and the cell's structure's structure should be the Structure Structure.
-    // I hate this sentence.
-    if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo())
-        CRASH();
+    size_t numberOfCellsToSteal = (other.size() + idleThreadCount - 1) / idleThreadCount; // Round up to steal 1 / 1.
+    while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
+        append(other.removeLast());
 }
-#endif
 
 } // namespace JSC