#include "config.h"
#include "MarkStack.h"
+#include "MarkStackInlines.h"
#include "ConservativeRoots.h"
+#include "CopiedSpace.h"
+#include "CopiedSpaceInlines.h"
#include "Heap.h"
#include "JSArray.h"
#include "JSCell.h"
#include "JSObject.h"
-#include "ScopeChain.h"
+
+#include "SlotVisitorInlines.h"
#include "Structure.h"
+#include "WriteBarrier.h"
+#include <wtf/Atomics.h>
+#include <wtf/DataLog.h>
+#include <wtf/MainThread.h>
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
- 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;
- 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
projects / apple / javascriptcore.git / blobdiff