#include "config.h"
#include "MarkStack.h"
#include "CopiedSpace.h"
#include "CopiedSpaceInlineMethods.h"
#include "ConservativeRoots.h"
#include "Heap.h"
#include "Options.h"
#include "JSArray.h"
#include "JSCell.h"
#include "JSObject.h"
#include "ScopeChain.h"
#include "Structure.h"
#include "WriteBarrier.h"
#include <wtf/MainThread.h>
namespace JSC {
MarkStackSegmentAllocator::MarkStackSegmentAllocator()
: m_nextFreeSegment(0)
{
}
MarkStackSegmentAllocator::~MarkStackSegmentAllocator()
{
shrinkReserve();
}
MarkStackSegment* MarkStackSegmentAllocator::allocate()
{
{
MutexLocker locker(m_lock);
if (m_nextFreeSegment) {
MarkStackSegment* result = m_nextFreeSegment;
m_nextFreeSegment = result->m_previous;
return result;
}
}
return static_cast<MarkStackSegment*>(OSAllocator::reserveAndCommit(Options::gcMarkStackSegmentSize));
}
void MarkStackSegmentAllocator::release(MarkStackSegment* segment)
{
MutexLocker locker(m_lock);
segment->m_previous = m_nextFreeSegment;
m_nextFreeSegment = segment;
}
void MarkStackSegmentAllocator::shrinkReserve()
{
MarkStackSegment* segments;
{
MutexLocker locker(m_lock);
segments = m_nextFreeSegment;
m_nextFreeSegment = 0;
}
while (segments) {
MarkStackSegment* toFree = segments;
segments = segments->m_previous;
OSAllocator::decommitAndRelease(toFree, Options::gcMarkStackSegmentSize);
}
}
MarkStackArray::MarkStackArray(MarkStackSegmentAllocator& allocator)
: m_allocator(allocator)
, m_segmentCapacity(MarkStackSegment::capacityFromSize(Options::gcMarkStackSegmentSize))
, m_top(0)
, m_numberOfPreviousSegments(0)
{
m_topSegment = m_allocator.allocate();
#if !ASSERT_DISABLED
m_topSegment->m_top = 0;
#endif
m_topSegment->m_previous = 0;
}
MarkStackArray::~MarkStackArray()
{
ASSERT(!m_topSegment->m_previous);
m_allocator.release(m_topSegment);
}
void MarkStackArray::expand()
{
ASSERT(m_topSegment->m_top == m_segmentCapacity);
m_numberOfPreviousSegments++;
MarkStackSegment* nextSegment = m_allocator.allocate();
#if !ASSERT_DISABLED
nextSegment->m_top = 0;
#endif
nextSegment->m_previous = m_topSegment;
m_topSegment = nextSegment;
setTopForEmptySegment();
validatePrevious();
}
bool MarkStackArray::refill()
{
validatePrevious();
if (top())
return true;
MarkStackSegment* toFree = m_topSegment;
MarkStackSegment* previous = m_topSegment->m_previous;
if (!previous)
return false;
ASSERT(m_numberOfPreviousSegments);
m_numberOfPreviousSegments--;
m_topSegment = previous;
m_allocator.release(toFree);
setTopForFullSegment();
validatePrevious();
return true;
}
bool MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
{
ASSERT(m_segmentCapacity == other.m_segmentCapacity);
validatePrevious();
other.validatePrevious();
if (other.m_numberOfPreviousSegments + 1 >= Options::maximumNumberOfSharedSegments)
return false;
size_t numberOfCellsToKeep = Options::minimumNumberOfCellsToKeep;
ASSERT(m_top > numberOfCellsToKeep || m_topSegment->m_previous);
MarkStackSegment* previous = m_topSegment->m_previous;
while (previous) {
ASSERT(m_numberOfPreviousSegments);
MarkStackSegment* current = previous;
previous = current->m_previous;
current->m_previous = other.m_topSegment->m_previous;
other.m_topSegment->m_previous = current;
m_numberOfPreviousSegments--;
other.m_numberOfPreviousSegments++;
}
ASSERT(!m_numberOfPreviousSegments);
m_topSegment->m_previous = 0;
validatePrevious();
other.validatePrevious();
if (m_top > numberOfCellsToKeep * 2)
numberOfCellsToKeep = m_top / 2;
while (m_top > numberOfCellsToKeep)
other.append(removeLast());
return true;
}
void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other)
{
ASSERT(m_segmentCapacity == other.m_segmentCapacity);
validatePrevious();
other.validatePrevious();
if (other.m_topSegment->m_previous) {
ASSERT(other.m_topSegment->m_previous->m_top == m_segmentCapacity);
MarkStackSegment* current = other.m_topSegment->m_previous;
other.m_topSegment->m_previous = current->m_previous;
other.m_numberOfPreviousSegments--;
ASSERT(!!other.m_numberOfPreviousSegments == !!other.m_topSegment->m_previous);
current->m_previous = m_topSegment->m_previous;
m_topSegment->m_previous = current;
m_numberOfPreviousSegments++;
validatePrevious();
other.validatePrevious();
return;
}
size_t numberOfCellsToSteal = std::max((size_t)Options::minimumNumberOfCellsToKeep, other.size() / Options::numberOfGCMarkers);
while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
append(other.removeLast());
}
#if ENABLE(PARALLEL_GC)
void MarkStackThreadSharedData::markingThreadMain()
{
WTF::registerGCThread();
SlotVisitor slotVisitor(*this);
ParallelModeEnabler enabler(slotVisitor);
slotVisitor.drainFromShared(SlotVisitor::SlaveDrain);
}
void MarkStackThreadSharedData::markingThreadStartFunc(void* shared)
{
static_cast<MarkStackThreadSharedData*>(shared)->markingThreadMain();
}
#endif
MarkStackThreadSharedData::MarkStackThreadSharedData(JSGlobalData* globalData)
: m_globalData(globalData)
, m_copiedSpace(&globalData->heap.m_storageSpace)
, m_sharedMarkStack(m_segmentAllocator)
, m_numberOfActiveParallelMarkers(0)
, m_parallelMarkersShouldExit(false)
{
#if ENABLE(PARALLEL_GC)
for (unsigned i = 1; i < Options::numberOfGCMarkers; ++i) {
m_markingThreads.append(createThread(markingThreadStartFunc, this, "JavaScriptCore::Marking"));
ASSERT(m_markingThreads.last());
}
#endif
}
MarkStackThreadSharedData::~MarkStackThreadSharedData()
{
#if ENABLE(PARALLEL_GC)
{
MutexLocker locker(m_markingLock);
m_parallelMarkersShouldExit = true;
m_markingCondition.broadcast();
}
for (unsigned i = 0; i < m_markingThreads.size(); ++i)
waitForThreadCompletion(m_markingThreads[i]);
#endif
}
void MarkStackThreadSharedData::reset()
{
ASSERT(!m_numberOfActiveParallelMarkers);
ASSERT(!m_parallelMarkersShouldExit);
ASSERT(m_sharedMarkStack.isEmpty());
#if ENABLE(PARALLEL_GC)
m_segmentAllocator.shrinkReserve();
m_opaqueRoots.clear();
#else
ASSERT(m_opaqueRoots.isEmpty());
#endif
m_weakReferenceHarvesters.removeAll();
}
void MarkStack::reset()
{
m_visitCount = 0;
ASSERT(m_stack.isEmpty());
#if ENABLE(PARALLEL_GC)
ASSERT(m_opaqueRoots.isEmpty()); #else
m_opaqueRoots.clear();
#endif
}
void MarkStack::append(ConservativeRoots& conservativeRoots)
{
JSCell** roots = conservativeRoots.roots();
size_t size = conservativeRoots.size();
for (size_t i = 0; i < size; ++i)
internalAppend(roots[i]);
}
ALWAYS_INLINE static void visitChildren(SlotVisitor& visitor, const JSCell* cell)
{
#if ENABLE(SIMPLE_HEAP_PROFILING)
m_visitedTypeCounts.count(cell);
#endif
ASSERT(Heap::isMarked(cell));
if (isJSString(cell)) {
JSString::visitChildren(const_cast<JSCell*>(cell), visitor);
return;
}
if (isJSFinalObject(cell)) {
JSObject::visitChildren(const_cast<JSCell*>(cell), visitor);
return;
}
if (isJSArray(cell)) {
JSArray::visitChildren(const_cast<JSCell*>(cell), visitor);
return;
}
cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), visitor);
}
void SlotVisitor::donateSlow()
{
if (m_shared.m_sharedMarkStack.size() > m_stack.size())
return;
MutexLocker locker(m_shared.m_markingLock);
if (m_stack.donateSomeCellsTo(m_shared.m_sharedMarkStack)) {
if (m_shared.m_sharedMarkStack.size() >= Options::sharedStackWakeupThreshold)
m_shared.m_markingCondition.broadcast();
}
}
void SlotVisitor::drain()
{
ASSERT(m_isInParallelMode);
#if ENABLE(PARALLEL_GC)
if (Options::numberOfGCMarkers > 1) {
while (!m_stack.isEmpty()) {
m_stack.refill();
for (unsigned countdown = Options::minimumNumberOfScansBetweenRebalance; m_stack.canRemoveLast() && countdown--;)
visitChildren(*this, m_stack.removeLast());
donateKnownParallel();
}
mergeOpaqueRootsIfNecessary();
return;
}
#endif
while (!m_stack.isEmpty()) {
m_stack.refill();
while (m_stack.canRemoveLast())
visitChildren(*this, m_stack.removeLast());
}
}
void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
{
ASSERT(m_isInParallelMode);
ASSERT(Options::numberOfGCMarkers);
bool shouldBeParallel;
#if ENABLE(PARALLEL_GC)
shouldBeParallel = Options::numberOfGCMarkers > 1;
#else
ASSERT(Options::numberOfGCMarkers == 1);
shouldBeParallel = false;
#endif
if (!shouldBeParallel) {
ASSERT_UNUSED(sharedDrainMode, sharedDrainMode == MasterDrain);
ASSERT(m_stack.isEmpty());
ASSERT(m_shared.m_sharedMarkStack.isEmpty());
return;
}
#if ENABLE(PARALLEL_GC)
{
MutexLocker locker(m_shared.m_markingLock);
m_shared.m_numberOfActiveParallelMarkers++;
}
while (true) {
{
MutexLocker locker(m_shared.m_markingLock);
m_shared.m_numberOfActiveParallelMarkers--;
if (sharedDrainMode == MasterDrain) {
while (true) {
if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty()) {
m_shared.m_markingCondition.broadcast();
return;
}
if (!m_shared.m_sharedMarkStack.isEmpty())
break;
m_shared.m_markingCondition.wait(m_shared.m_markingLock);
}
} else {
ASSERT(sharedDrainMode == SlaveDrain);
if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty())
m_shared.m_markingCondition.broadcast();
while (m_shared.m_sharedMarkStack.isEmpty() && !m_shared.m_parallelMarkersShouldExit) {
if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty())
doneCopying();
m_shared.m_markingCondition.wait(m_shared.m_markingLock);
}
if (m_shared.m_parallelMarkersShouldExit) {
doneCopying();
return;
}
}
m_stack.stealSomeCellsFrom(m_shared.m_sharedMarkStack);
m_shared.m_numberOfActiveParallelMarkers++;
}
drain();
}
#endif
}
void MarkStack::mergeOpaqueRoots()
{
ASSERT(!m_opaqueRoots.isEmpty()); {
MutexLocker locker(m_shared.m_opaqueRootsLock);
HashSet<void*>::iterator begin = m_opaqueRoots.begin();
HashSet<void*>::iterator end = m_opaqueRoots.end();
for (HashSet<void*>::iterator iter = begin; iter != end; ++iter)
m_shared.m_opaqueRoots.add(*iter);
}
m_opaqueRoots.clear();
}
void SlotVisitor::startCopying()
{
ASSERT(!m_copyBlock);
if (!m_shared.m_copiedSpace->borrowBlock(&m_copyBlock))
CRASH();
}
void* SlotVisitor::allocateNewSpace(void* ptr, size_t bytes)
{
if (CopiedSpace::isOversize(bytes)) {
m_shared.m_copiedSpace->pin(CopiedSpace::oversizeBlockFor(ptr));
return 0;
}
if (m_shared.m_copiedSpace->isPinned(ptr))
return 0;
if (!m_copyBlock)
startCopying();
if (!CopiedSpace::fitsInBlock(m_copyBlock, bytes)) {
m_shared.m_copiedSpace->doneFillingBlock(m_copyBlock);
if (!m_shared.m_copiedSpace->borrowBlock(&m_copyBlock))
CRASH();
}
return CopiedSpace::allocateFromBlock(m_copyBlock, bytes);
}
void SlotVisitor::copyAndAppend(void** ptr, size_t bytes, JSValue* values, unsigned length)
{
void* oldPtr = *ptr;
void* newPtr = allocateNewSpace(oldPtr, bytes);
if (newPtr) {
size_t jsValuesOffset = static_cast<size_t>(reinterpret_cast<char*>(values) - static_cast<char*>(oldPtr));
JSValue* newValues = reinterpret_cast_ptr<JSValue*>(static_cast<char*>(newPtr) + jsValuesOffset);
for (unsigned i = 0; i < length; i++) {
JSValue& value = values[i];
newValues[i] = value;
if (!value)
continue;
internalAppend(value);
}
memcpy(newPtr, oldPtr, jsValuesOffset);
*ptr = newPtr;
} else
append(values, length);
}
void SlotVisitor::doneCopying()
{
if (!m_copyBlock)
return;
m_shared.m_copiedSpace->doneFillingBlock(m_copyBlock);
m_copyBlock = 0;
}
void SlotVisitor::harvestWeakReferences()
{
for (WeakReferenceHarvester* current = m_shared.m_weakReferenceHarvesters.head(); current; current = current->next())
current->visitWeakReferences(*this);
}
void SlotVisitor::finalizeUnconditionalFinalizers()
{
while (m_shared.m_unconditionalFinalizers.hasNext())
m_shared.m_unconditionalFinalizers.removeNext()->finalizeUnconditionally();
}
#if ENABLE(GC_VALIDATION)
void MarkStack::validate(JSCell* cell)
{
if (!cell)
CRASH();
if (!cell->structure())
CRASH();
if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo())
CRASH();
}
#else
void MarkStack::validate(JSCell*)
{
}
#endif
}