-
mhahnenberg@apple.com authored
https://bugs.webkit.org/show_bug.cgi?id=98792 Reviewed by Filip Pizlo. Currently our copying collection occurs simultaneously with the marking phase. We'd like to be able to reuse CopiedBlocks as soon as they become fully evacuated, but this is not currently possible because we don't know the liveness statistics of each old CopiedBlock until marking/copying has already finished. Instead, we have to allocate additional memory from the OS to use as our working set of CopiedBlocks while copying. We then return the fully evacuated old CopiedBlocks back to the block allocator, thus giving our copying phase an O(live bytes) overhead. To fix this, we should instead split the copying phase apart from the marking phase. This way we have full liveness data for each CopiedBlock during the copying phase so that we can reuse them the instant they become fully evacuated. With the additional liveness data that each CopiedBlock accumulates, we can add some additional heuristics to the collector. For example, we can calculate our global Heap fragmentation and only choose to do a copying phase if that fragmentation exceeds some limit. As another example, we can skip copying blocks that are already above a particular fragmentation limit, which allows older objects to coalesce into blocks that are rarely copied. * JavaScriptCore.xcodeproj/project.pbxproj: * heap/CopiedBlock.h: (CopiedBlock): (JSC::CopiedBlock::CopiedBlock): Added support for tracking live bytes in a CopiedBlock in a thread-safe fashion. (JSC::CopiedBlock::reportLiveBytes): Adds a number of live bytes to the block in a thread-safe fashion using compare and swap. (JSC): (JSC::CopiedBlock::didSurviveGC): Called when a block survives a single GC without being evacuated. This could be called for a couple reasons: (a) the block was pinned or (b) we decided not to do any copying. A block can become pinned for a few reasons: (1) a pointer into the block was found during the conservative scan. (2) the block was deemed full enough to not warrant any copying. (3) The block is oversize and was found to be live. (JSC::CopiedBlock::didEvacuateBytes): Called when some number of bytes are copied from this block. If the number of live bytes ever hits zero, the block will return itself to the BlockAllocator to be recycled. (JSC::CopiedBlock::canBeRecycled): Indicates that a block has no live bytes and can be immediately recycled. This is used for blocks that are found to have zero live bytes at the beginning of the copying phase. (JSC::CopiedBlock::shouldEvacuate): This function returns true if the current fragmentation of the block is above our fragmentation threshold, and false otherwise. (JSC::CopiedBlock::isPinned): Added an accessor for the pinned flag (JSC::CopiedBlock::liveBytes): * heap/CopiedSpace.cpp: (JSC::CopiedSpace::CopiedSpace): (JSC::CopiedSpace::doneFillingBlock): Changed so that we can exchange our filled block for a fresh block. This avoids the situation where a thread returns its borrowed block, it's the last borrowed block, so CopiedSpace thinks that copying has completed, and it starts doing all of the copying phase cleanup. In actuality, the thread wanted another block after returning the current block. So we allow the thread to atomically exchange its block for another block. (JSC::CopiedSpace::startedCopying): Added the calculation of global Heap fragmentation to determine if the copying phase should commence. We include the MarkedSpace in our fragmentation calculation by assuming that the MarkedSpace is 0% fragmented since we can reuse any currently free memory in it (i.e. we ignore any internal fragmentation in the MarkedSpace). While we're calculating the fragmentation of CopiedSpace, we also return any free blocks we find along the way (meaning liveBytes() == 0). (JSC): (JSC::CopiedSpace::doneCopying): We still have to iterate over all the blocks, regardless of whether the copying phase took place or not so that we can reset all of the live bytes counters and un-pin any pinned blocks. * heap/CopiedSpace.h: (CopiedSpace): (JSC::CopiedSpace::shouldDoCopyPhase): * heap/CopiedSpaceInlineMethods.h: (JSC::CopiedSpace::recycleEvacuatedBlock): This function is distinct from recycling a borrowed block because a borrowed block hasn't been added to the CopiedSpace yet, but an evacuated block is still currently in CopiedSpace, so we have to make sure we properly remove all traces of the block from CopiedSpace before returning it to BlockAllocator. (JSC::CopiedSpace::recycleBorrowedBlock): Renamed to indicate the distinction mentioned above. * heap/CopyVisitor.cpp: Added. (JSC): (JSC::CopyVisitor::CopyVisitor): (JSC::CopyVisitor::copyFromShared): Main function for any thread participating in the copying phase. Grabs chunks of MarkedBlocks from the shared list and copies the backing store of anybody who needs it until there are no more chunks to copy. * heap/CopyVisitor.h: Added. (JSC): (CopyVisitor): * heap/CopyVisitorInlineMethods.h: Added. (JSC): (GCCopyPhaseFunctor): (JSC::GCCopyPhaseFunctor::GCCopyPhaseFunctor): (JSC::GCCopyPhaseFunctor::operator()): (JSC::CopyVisitor::checkIfShouldCopy): We don't have to check shouldEvacuate() because all of those checks are done during the marking phase. (JSC::CopyVisitor::allocateNewSpace): (JSC::CopyVisitor::allocateNewSpaceSlow): (JSC::CopyVisitor::startCopying): Initialization function for a thread that is about to start copying. (JSC::CopyVisitor::doneCopying): (JSC::CopyVisitor::didCopy): This callback is called by an object that has just successfully copied its backing store. It indicates to the CopiedBlock that somebody has just finished evacuating some number of bytes from it, and, if the CopiedBlock now has no more live bytes, can be recycled immediately. * heap/GCThread.cpp: Added. (JSC): (JSC::GCThread::GCThread): This is a new class that encapsulates a single thread responsible for participating in a specific set of GC phases. Currently, that set of phases includes Mark, Copy, and Exit. Each thread monitors a shared variable in its associated GCThreadSharedData. The main thread updates this m_currentPhase variable as collection progresses through the various phases. Parallel marking still works exactly like it has. In other words, the "run loop" for each of the GC threads sits above any individual phase, thus keeping the separate phases of the collector orthogonal. (JSC::GCThread::threadID): (JSC::GCThread::initializeThreadID): (JSC::GCThread::slotVisitor): (JSC::GCThread::copyVisitor): (JSC::GCThread::waitForNextPhase): (JSC::GCThread::gcThreadMain): (JSC::GCThread::gcThreadStartFunc): * heap/GCThread.h: Added. (JSC): (GCThread): * heap/GCThreadSharedData.cpp: The GCThreadSharedData now has a list of GCThread objects rather than raw ThreadIdentifiers. (JSC::GCThreadSharedData::resetChildren): (JSC::GCThreadSharedData::childVisitCount): (JSC::GCThreadSharedData::GCThreadSharedData): (JSC::GCThreadSharedData::~GCThreadSharedData): (JSC::GCThreadSharedData::reset): (JSC::GCThreadSharedData::didStartMarking): Callback to let the GCThreadSharedData know that marking has started and updates the m_currentPhase variable and notifies the GCThreads accordingly. (JSC::GCThreadSharedData::didFinishMarking): Ditto for finishing marking. (JSC::GCThreadSharedData::didStartCopying): Ditto for starting the copying phase. (JSC::GCThreadSharedData::didFinishCopying): Ditto for finishing copying. * heap/GCThreadSharedData.h: (JSC): (GCThreadSharedData): (JSC::GCThreadSharedData::getNextBlocksToCopy): Atomically gets the next chunk of work for a copying thread. * heap/Heap.cpp: (JSC::Heap::Heap): (JSC::Heap::markRoots): (JSC): (JSC::Heap::copyBackingStores): Responsible for setting up the copying phase, notifying the copying threads, and doing any copying work if necessary. (JSC::Heap::collect): * heap/Heap.h: (Heap): (JSC): (JSC::CopyFunctor::CopyFunctor): (CopyFunctor): (JSC::CopyFunctor::operator()): * heap/IncrementalSweeper.cpp: Changed the incremental sweeper to have a reference to the list of MarkedBlocks that need sweeping, since this now resides in the Heap so that it can be easily shared by the GCThreads. (JSC::IncrementalSweeper::IncrementalSweeper): (JSC::IncrementalSweeper::startSweeping): * heap/IncrementalSweeper.h: (JSC): (IncrementalSweeper): * heap/SlotVisitor.cpp: (JSC::SlotVisitor::setup): (JSC::SlotVisitor::drainFromShared): We no longer do any copying-related work here. (JSC): * heap/SlotVisitor.h: (SlotVisitor): * heap/SlotVisitorInlineMethods.h: (JSC): (JSC::SlotVisitor::copyLater): Notifies the CopiedBlock that there are some live bytes that may need to be copied. * runtime/Butterfly.h: (JSC): (Butterfly): * runtime/ButterflyInlineMethods.h: (JSC::Butterfly::createUninitializedDuringCollection): Uses the new CopyVisitor. * runtime/ClassInfo.h: (MethodTable): Added new "virtual" function copyBackingStore to method table. (JSC): * runtime/JSCell.cpp: (JSC::JSCell::copyBackingStore): Default implementation that does nothing. (JSC): * runtime/JSCell.h: (JSC): (JSCell): * runtime/JSObject.cpp: (JSC::JSObject::copyButterfly): Does the actual copying of the butterfly. (JSC): (JSC::JSObject::visitButterfly): Calls copyLater for the butterfly. (JSC::JSObject::copyBackingStore): * runtime/JSObject.h: (JSObject): (JSC::JSCell::methodTable): (JSC::JSCell::inherits): * runtime/Options.h: Added two new constants, minHeapUtilization and minCopiedBlockUtilization, to govern the amount of fragmentation we allow before doing copying. (JSC): git-svn-id: http://svn.webkit.org/repository/webkit/trunk@131213 268f45cc-cd09-0410-ab3c-d52691b4dbfc
02e39c7e