JavaScriptCore-1218.0.1.tar.gz

[apple/javascriptcore.git] / heap / MarkStack.cpp

diff --git a/heap/MarkStack.cpp b/heap/MarkStack.cpp
index d3adfdceb0becb2dcf47ffb178780c43ef1cdc41..39907c715edc56c928a9cc51157cda93224482ca 100644 (file)
--- a/heap/MarkStack.cpp
+++ b/heap/MarkStack.cpp
@@ -25,140 +25,146 @@
 
 #include "config.h"
 #include "MarkStack.h"
 
 #include "config.h"
 #include "MarkStack.h"

+#include "MarkStackInlines.h"

 
 #include "ConservativeRoots.h"
 
 #include "ConservativeRoots.h"

+#include "CopiedSpace.h"
+#include "CopiedSpaceInlines.h"

 #include "Heap.h"
 #include "JSArray.h"
 #include "JSCell.h"
 #include "JSObject.h"
 #include "Heap.h"
 #include "JSArray.h"
 #include "JSCell.h"
 #include "JSObject.h"

-#include "ScopeChain.h"
+
+#include "SlotVisitorInlines.h"

 #include "Structure.h"
 #include "Structure.h"

+#include "WriteBarrier.h"
+#include <wtf/Atomics.h>
+#include <wtf/DataLog.h>
+#include <wtf/MainThread.h>

 
 namespace JSC {
 
 
 namespace JSC {
 

-size_t MarkStack::s_pageSize = 0;
+COMPILE_ASSERT(MarkStackSegment::blockSize == WeakBlock::blockSize, blockSizeMatch);

 
 

-void MarkStack::reset()
+MarkStackArray::MarkStackArray(BlockAllocator& blockAllocator)
+    : m_blockAllocator(blockAllocator)
+    , m_top(0)
+    , m_numberOfSegments(0)

 {
 {

-    ASSERT(s_pageSize);
-    m_values.shrinkAllocation(s_pageSize);
-    m_markSets.shrinkAllocation(s_pageSize);
-    m_opaqueRoots.clear();
+    m_segments.push(MarkStackSegment::create(m_blockAllocator.allocate<MarkStackSegment>()));
+    m_numberOfSegments++;

 }
 
 }
 

-void MarkStack::append(ConservativeRoots& conservativeRoots)
+MarkStackArray::~MarkStackArray()

 {
 {

-    JSCell** roots = conservativeRoots.roots();
-    size_t size = conservativeRoots.size();
-    for (size_t i = 0; i < size; ++i)
-        internalAppend(roots[i]);
+    ASSERT(m_numberOfSegments == 1 && m_segments.size() == 1);
+    m_blockAllocator.deallocate(MarkStackSegment::destroy(m_segments.removeHead()));

 }
 
 }
 

-inline void MarkStack::visitChildren(JSCell* cell)
+void MarkStackArray::expand()

 {
 {

-    ASSERT(Heap::isMarked(cell));
-    if (cell->structure()->typeInfo().type() < CompoundType) {
-        cell->JSCell::visitChildren(*this);
-        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;
+    ASSERT(m_segments.head()->m_top == s_segmentCapacity);
+    
+    MarkStackSegment* nextSegment = MarkStackSegment::create(m_blockAllocator.allocate<MarkStackSegment>());
+    m_numberOfSegments++;
+    
+#if !ASSERT_DISABLED
+    nextSegment->m_top = 0;

 #endif
 #endif

-        return;
-    }
-    if (cell->vptr() == m_jsArrayVPtr) {
-        asArray(cell)->visitChildrenDirect(*this);
-        return;
-    }
-    cell->visitChildren(*this);
+
+    m_segments.push(nextSegment);
+    setTopForEmptySegment();
+    validatePrevious();

 }
 
 }
 

-void MarkStack::drain()
+bool MarkStackArray::refill()

 {
 {

-#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());
-    }
-#if !ASSERT_DISABLED
-    m_isDraining = false;
-#endif
+    validatePrevious();
+    if (top())
+        return true;
+    m_blockAllocator.deallocate(MarkStackSegment::destroy(m_segments.removeHead()));
+    ASSERT(m_numberOfSegments > 1);
+    m_numberOfSegments--;
+    setTopForFullSegment();
+    validatePrevious();
+    return true;

 }
 
 }
 

-#if ENABLE(GC_VALIDATION)
-void MarkStack::validateSet(JSValue* values, size_t count)
+void MarkStackArray::donateSomeCellsTo(MarkStackArray& other)

 {
 {

-    for (size_t i = 0; i < count; i++) {
-        if (values[i])
-            validateValue(values[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.
+
+    size_t segmentsToDonate = m_numberOfSegments / 2; // If we only have one segment (our head) we don't donate any segments.
+
+    if (!segmentsToDonate) {
+        size_t cellsToDonate = m_top / 2; // Round down to donate 0 / 1 cells.
+        while (cellsToDonate--) {
+            ASSERT(m_top);
+            other.append(removeLast());
+        }
+        return;

     }
     }

+
+    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.
+    MarkStackSegment* myHead = m_segments.removeHead();
+    MarkStackSegment* otherHead = other.m_segments.removeHead();
+
+    while (segmentsToDonate--) {
+        MarkStackSegment* current = m_segments.removeHead();
+        ASSERT(current);
+        ASSERT(m_numberOfSegments > 1);
+        other.m_segments.push(current);
+        m_numberOfSegments--;
+        other.m_numberOfSegments++;
+    }
+
+    // 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.
+        MarkStackSegment* otherHead = other.m_segments.removeHead();
+        MarkStackSegment* 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;
         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
 
 } // namespace JSC