X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/14957cd040308e3eeec43d26bae5d76da13fcd85..8b637bb680022adfddad653280734877951535a9:/heap/MarkStack.cpp diff --git a/heap/MarkStack.cpp b/heap/MarkStack.cpp index d3adfdc..39907c7 100644 --- a/heap/MarkStack.cpp +++ b/heap/MarkStack.cpp @@ -25,140 +25,146 @@ #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 +#include +#include 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())); + 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()); + 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