[WTF] Use m_suspendCount instead of m_suspended flag in Thread
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkStack.cpp
index 6c46b28..871b301 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2009, 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2009-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 #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 "WriteBarrier.h"
+#include "GCSegmentedArrayInlines.h"
+#include "JSCInlines.h"
 
 namespace JSC {
 
 MarkStackArray::MarkStackArray()
-    : m_top(0)
-    , m_allocated(pageSize())
+    : GCSegmentedArray<const JSCell*>()
 {
-    m_data = static_cast<const JSCell**>(MarkStack::allocateStack(m_allocated));
-    m_capacity = m_allocated / sizeof(JSCell*);
 }
 
-MarkStackArray::~MarkStackArray()
+void MarkStackArray::transferTo(MarkStackArray& other)
 {
-    MarkStack::releaseStack(m_data, m_allocated);
-}
-
-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));
-#else
-    MarkStack::releaseStack(reinterpret_cast<char*>(m_data) + size, m_allocated - size);
-#endif
-    m_allocated = size;
-    m_capacity = m_allocated / sizeof(JSCell*);
-}
-
-void MarkStack::reset()
-{
-    m_visitCount = 0;
-    m_stack.shrinkAllocation(pageSize());
-    m_opaqueRoots.clear();
+    RELEASE_ASSERT(this != &other);
+    
+    // Remove our head and the head of the other list.
+    GCArraySegment<const JSCell*>* myHead = m_segments.removeHead();
+    GCArraySegment<const JSCell*>* otherHead = other.m_segments.removeHead();
+    m_numberOfSegments--;
+    other.m_numberOfSegments--;
+    
+    other.m_segments.append(m_segments);
+    
+    other.m_numberOfSegments += m_numberOfSegments;
+    m_numberOfSegments = 0;
+    
+    // Put the original heads back in their places.
+    m_segments.push(myHead);
+    other.m_segments.push(otherHead);
+    m_numberOfSegments++;
+    other.m_numberOfSegments++;
+    
+    while (!isEmpty()) {
+        refill();
+        while (canRemoveLast())
+            other.append(removeLast());
+    }
 }
 
-void MarkStack::append(ConservativeRoots& conservativeRoots)
+size_t MarkStackArray::transferTo(MarkStackArray& other, size_t limit)
 {
-    JSCell** roots = conservativeRoots.roots();
-    size_t size = conservativeRoots.size();
-    for (size_t i = 0; i < size; ++i)
-        internalAppend(roots[i]);
+    size_t count = 0;
+    while (count < limit && !isEmpty()) {
+        refill();
+        while (count < limit && canRemoveLast()) {
+            other.append(removeLast());
+            count++;
+        }
+    }
+    RELEASE_ASSERT(count <= limit);
+    return count;
 }
 
-ALWAYS_INLINE static void visitChildren(SlotVisitor& visitor, const JSCell* cell, void* jsFinalObjectVPtr, void* jsArrayVPtr, void* jsStringVPtr)
+void MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
 {
-#if ENABLE(SIMPLE_HEAP_PROFILING)
-    m_visitedTypeCounts.count(cell);
-#endif
-
-    ASSERT(Heap::isMarked(cell));
-
-    if (cell->vptr() == jsStringVPtr)
-        return;
-
-    if (cell->vptr() == jsFinalObjectVPtr) {
-        JSObject::visitChildren(const_cast<JSCell*>(cell), visitor);
+    // 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;
     }
 
-    if (cell->vptr() == jsArrayVPtr) {
-        JSArray::visitChildren(const_cast<JSCell*>(cell), visitor);
-        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.
+    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++;
     }
 
-    cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), visitor);
-}
+    // Put the original heads back in their places.
+    m_segments.push(myHead);
+    other.m_segments.push(otherHead);
 
-void SlotVisitor::drain()
-{
-    void* jsFinalObjectVPtr = m_jsFinalObjectVPtr;
-    void* jsArrayVPtr = m_jsArrayVPtr;
-    void* jsStringVPtr = m_jsStringVPtr;
-
-    while (!m_stack.isEmpty())
-        visitChildren(*this, m_stack.removeLast(), jsFinalObjectVPtr, jsArrayVPtr, jsStringVPtr);
+    validatePrevious();
+    other.validatePrevious();
 }
 
-void SlotVisitor::harvestWeakReferences()
+void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other, size_t idleThreadCount)
 {
-    while (m_firstWeakReferenceHarvester) {
-        WeakReferenceHarvester* current = m_firstWeakReferenceHarvester;
-        WeakReferenceHarvester* next = reinterpret_cast<WeakReferenceHarvester*>(current->m_nextAndFlag & ~1);
-        current->m_nextAndFlag = 0;
-        m_firstWeakReferenceHarvester = next;
-        current->visitWeakReferences(*this);
+    // 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;
     }
-}
-
-#if ENABLE(GC_VALIDATION)
-void MarkStack::validate(JSCell* cell)
-{
-    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();
-}
-#else
-void MarkStack::validate(JSCell*)
-{
+    // Steal ceil(other.size() / idleThreadCount) things.
+    size_t numberOfCellsToSteal = (other.size() + idleThreadCount - 1) / idleThreadCount;
+    while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
+        append(other.removeLast());
 }
-#endif
 
 } // namespace JSC