| /* |
| * Copyright (C) 2012-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 |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "MarkedAllocator.h" |
| |
| #include "AllocatingScope.h" |
| #include "GCActivityCallback.h" |
| #include "Heap.h" |
| #include "IncrementalSweeper.h" |
| #include "JSCInlines.h" |
| #include "MarkedAllocatorInlines.h" |
| #include "MarkedBlockInlines.h" |
| #include "SuperSampler.h" |
| #include "VM.h" |
| #include <wtf/CurrentTime.h> |
| |
| namespace JSC { |
| |
| MarkedAllocator::MarkedAllocator(Heap* heap, Subspace* subspace, size_t cellSize) |
| : m_currentBlock(0) |
| , m_lastActiveBlock(0) |
| , m_cellSize(static_cast<unsigned>(cellSize)) |
| , m_attributes(subspace->attributes()) |
| , m_heap(heap) |
| , m_subspace(subspace) |
| { |
| } |
| |
| bool MarkedAllocator::isPagedOut(double deadline) |
| { |
| unsigned itersSinceLastTimeCheck = 0; |
| for (auto* block : m_blocks) { |
| if (block) |
| block->block().updateNeedsDestruction(); |
| ++itersSinceLastTimeCheck; |
| if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) { |
| double currentTime = WTF::monotonicallyIncreasingTime(); |
| if (currentTime > deadline) |
| return true; |
| itersSinceLastTimeCheck = 0; |
| } |
| } |
| return false; |
| } |
| |
| bool MarkedAllocator::shouldStealEmptyBlocksFromOtherAllocators() const |
| { |
| return !needsDestruction(); |
| } |
| |
| MarkedBlock::Handle* MarkedAllocator::findEmptyBlockToSteal() |
| { |
| // Don't allow others to steal from us, if we wouldn't steal from others. |
| if (!shouldStealEmptyBlocksFromOtherAllocators()) |
| return nullptr; |
| |
| m_emptyCursor = m_empty.findBit(m_emptyCursor, true); |
| if (m_emptyCursor >= m_blocks.size()) |
| return nullptr; |
| return m_blocks[m_emptyCursor]; |
| } |
| |
| void MarkedAllocator::didConsumeFreeList() |
| { |
| if (m_currentBlock) |
| m_currentBlock->didConsumeFreeList(); |
| |
| setFreeList(FreeList()); |
| m_currentBlock = nullptr; |
| } |
| |
| void* MarkedAllocator::tryAllocateWithoutCollecting() |
| { |
| SuperSamplerScope superSamplerScope(false); |
| |
| ASSERT(!m_currentBlock); |
| ASSERT(!m_freeList); |
| |
| for (;;) { |
| m_allocationCursor = (m_canAllocateButNotEmpty | m_empty).findBit(m_allocationCursor, true); |
| if (m_allocationCursor >= m_blocks.size()) |
| break; |
| |
| setIsCanAllocateButNotEmpty(NoLockingNecessary, m_allocationCursor, false); |
| |
| if (void* result = tryAllocateIn(m_blocks[m_allocationCursor])) |
| return result; |
| } |
| |
| if (Options::stealEmptyBlocksFromOtherAllocators() |
| && shouldStealEmptyBlocksFromOtherAllocators()) { |
| if (MarkedBlock::Handle* block = markedSpace().findEmptyBlockToSteal()) { |
| block->sweep(); |
| |
| // It's good that this clears canAllocateButNotEmpty as well as all other bits, |
| // because there is a remote chance that a block may have both canAllocateButNotEmpty |
| // and empty set at the same time. |
| block->removeFromAllocator(); |
| addBlock(block); |
| return allocateIn(block); |
| } |
| } |
| |
| return nullptr; |
| } |
| |
| void* MarkedAllocator::allocateIn(MarkedBlock::Handle* block) |
| { |
| void* result = tryAllocateIn(block); |
| RELEASE_ASSERT(result); |
| return result; |
| } |
| |
| void* MarkedAllocator::tryAllocateIn(MarkedBlock::Handle* block) |
| { |
| ASSERT(block); |
| ASSERT(!block->isFreeListed()); |
| |
| FreeList freeList = block->sweep(MarkedBlock::Handle::SweepToFreeList); |
| |
| // It's possible to stumble on a completely full block. Marking tries to retire these, but |
| // that algorithm is racy and may forget to do it sometimes. |
| if (freeList.allocationWillFail()) { |
| ASSERT(block->isFreeListed()); |
| block->unsweepWithNoNewlyAllocated(); |
| ASSERT(!block->isFreeListed()); |
| ASSERT(!isEmpty(NoLockingNecessary, block)); |
| ASSERT(!isCanAllocateButNotEmpty(NoLockingNecessary, block)); |
| return nullptr; |
| } |
| |
| m_currentBlock = block; |
| setFreeList(freeList); |
| |
| void* result; |
| if (m_freeList.remaining) { |
| unsigned cellSize = m_cellSize; |
| m_freeList.remaining -= cellSize; |
| result = m_freeList.payloadEnd - m_freeList.remaining - cellSize; |
| } else { |
| FreeCell* head = m_freeList.head; |
| m_freeList.head = head->next; |
| result = head; |
| } |
| RELEASE_ASSERT(result); |
| setIsEden(NoLockingNecessary, m_currentBlock, true); |
| markedSpace().didAllocateInBlock(m_currentBlock); |
| return result; |
| } |
| |
| ALWAYS_INLINE void MarkedAllocator::doTestCollectionsIfNeeded(GCDeferralContext* deferralContext) |
| { |
| if (!Options::slowPathAllocsBetweenGCs()) |
| return; |
| |
| static unsigned allocationCount = 0; |
| if (!allocationCount) { |
| if (!m_heap->isDeferred()) { |
| if (deferralContext) |
| deferralContext->m_shouldGC = true; |
| else |
| m_heap->collectAllGarbage(); |
| } |
| } |
| if (++allocationCount >= Options::slowPathAllocsBetweenGCs()) |
| allocationCount = 0; |
| } |
| |
| void* MarkedAllocator::allocateSlowCase(GCDeferralContext* deferralContext) |
| { |
| bool crashOnFailure = true; |
| return allocateSlowCaseImpl(deferralContext, crashOnFailure); |
| } |
| |
| void* MarkedAllocator::tryAllocateSlowCase(GCDeferralContext* deferralContext) |
| { |
| bool crashOnFailure = false; |
| return allocateSlowCaseImpl(deferralContext, crashOnFailure); |
| } |
| |
| void* MarkedAllocator::allocateSlowCaseImpl(GCDeferralContext* deferralContext, bool crashOnFailure) |
| { |
| SuperSamplerScope superSamplerScope(false); |
| ASSERT(m_heap->vm()->currentThreadIsHoldingAPILock()); |
| doTestCollectionsIfNeeded(deferralContext); |
| |
| ASSERT(!markedSpace().isIterating()); |
| m_heap->didAllocate(m_freeList.originalSize); |
| |
| didConsumeFreeList(); |
| |
| AllocatingScope helpingHeap(*m_heap); |
| |
| m_heap->collectIfNecessaryOrDefer(deferralContext); |
| |
| // Goofy corner case: the GC called a callback and now this allocator has a currentBlock. This only |
| // happens when running WebKit tests, which inject a callback into the GC's finalization. |
| if (UNLIKELY(m_currentBlock)) { |
| if (crashOnFailure) |
| return allocate(deferralContext); |
| return tryAllocate(deferralContext); |
| } |
| |
| void* result = tryAllocateWithoutCollecting(); |
| |
| if (LIKELY(result != 0)) |
| return result; |
| |
| MarkedBlock::Handle* block = tryAllocateBlock(); |
| if (!block) { |
| if (crashOnFailure) |
| RELEASE_ASSERT_NOT_REACHED(); |
| else |
| return nullptr; |
| } |
| addBlock(block); |
| result = allocateIn(block); |
| ASSERT(result); |
| return result; |
| } |
| |
| static size_t blockHeaderSize() |
| { |
| return WTF::roundUpToMultipleOf<MarkedBlock::atomSize>(sizeof(MarkedBlock)); |
| } |
| |
| size_t MarkedAllocator::blockSizeForBytes(size_t bytes) |
| { |
| size_t minBlockSize = MarkedBlock::blockSize; |
| size_t minAllocationSize = blockHeaderSize() + WTF::roundUpToMultipleOf<MarkedBlock::atomSize>(bytes); |
| minAllocationSize = WTF::roundUpToMultipleOf(WTF::pageSize(), minAllocationSize); |
| return std::max(minBlockSize, minAllocationSize); |
| } |
| |
| MarkedBlock::Handle* MarkedAllocator::tryAllocateBlock() |
| { |
| SuperSamplerScope superSamplerScope(false); |
| |
| MarkedBlock::Handle* handle = MarkedBlock::tryCreate(*m_heap); |
| if (!handle) |
| return nullptr; |
| |
| markedSpace().didAddBlock(handle); |
| |
| return handle; |
| } |
| |
| void MarkedAllocator::addBlock(MarkedBlock::Handle* block) |
| { |
| size_t index; |
| if (m_freeBlockIndices.isEmpty()) { |
| index = m_blocks.size(); |
| |
| size_t oldCapacity = m_blocks.capacity(); |
| m_blocks.append(block); |
| if (m_blocks.capacity() != oldCapacity) { |
| forEachBitVector( |
| NoLockingNecessary, |
| [&] (FastBitVector& vector) { |
| ASSERT_UNUSED(vector, vector.numBits() == oldCapacity); |
| }); |
| |
| ASSERT(m_blocks.capacity() > oldCapacity); |
| |
| LockHolder locker(m_bitvectorLock); |
| forEachBitVector( |
| locker, |
| [&] (FastBitVector& vector) { |
| vector.resize(m_blocks.capacity()); |
| }); |
| } |
| } else { |
| index = m_freeBlockIndices.takeLast(); |
| ASSERT(!m_blocks[index]); |
| m_blocks[index] = block; |
| } |
| |
| forEachBitVector( |
| NoLockingNecessary, |
| [&] (FastBitVector& vector) { |
| ASSERT_UNUSED(vector, !vector[index]); |
| }); |
| |
| // This is the point at which the block learns of its cellSize() and attributes(). |
| block->didAddToAllocator(this, index); |
| |
| setIsLive(NoLockingNecessary, index, true); |
| setIsEmpty(NoLockingNecessary, index, true); |
| } |
| |
| void MarkedAllocator::removeBlock(MarkedBlock::Handle* block) |
| { |
| ASSERT(block->allocator() == this); |
| ASSERT(m_blocks[block->index()] == block); |
| |
| m_blocks[block->index()] = nullptr; |
| m_freeBlockIndices.append(block->index()); |
| |
| forEachBitVector( |
| holdLock(m_bitvectorLock), |
| [&] (FastBitVector& vector) { |
| vector[block->index()] = false; |
| }); |
| |
| block->didRemoveFromAllocator(); |
| } |
| |
| void MarkedAllocator::stopAllocating() |
| { |
| if (false) |
| dataLog(RawPointer(this), ": MarkedAllocator::stopAllocating!\n"); |
| ASSERT(!m_lastActiveBlock); |
| if (!m_currentBlock) { |
| ASSERT(!m_freeList); |
| return; |
| } |
| |
| m_currentBlock->stopAllocating(m_freeList); |
| m_lastActiveBlock = m_currentBlock; |
| m_currentBlock = 0; |
| m_freeList = FreeList(); |
| } |
| |
| void MarkedAllocator::prepareForAllocation() |
| { |
| m_lastActiveBlock = nullptr; |
| m_currentBlock = nullptr; |
| setFreeList(FreeList()); |
| |
| m_allocationCursor = 0; |
| m_emptyCursor = 0; |
| m_unsweptCursor = 0; |
| |
| m_eden.clearAll(); |
| |
| if (UNLIKELY(Options::useImmortalObjects())) { |
| // FIXME: Make this work again. |
| // https://bugs.webkit.org/show_bug.cgi?id=162296 |
| RELEASE_ASSERT_NOT_REACHED(); |
| } |
| } |
| |
| void MarkedAllocator::lastChanceToFinalize() |
| { |
| forEachBlock( |
| [&] (MarkedBlock::Handle* block) { |
| block->lastChanceToFinalize(); |
| }); |
| } |
| |
| void MarkedAllocator::setFreeList(const FreeList& freeList) |
| { |
| m_freeList = freeList; |
| } |
| |
| void MarkedAllocator::resumeAllocating() |
| { |
| if (!m_lastActiveBlock) |
| return; |
| |
| m_freeList = m_lastActiveBlock->resumeAllocating(); |
| m_currentBlock = m_lastActiveBlock; |
| m_lastActiveBlock = nullptr; |
| } |
| |
| void MarkedAllocator::beginMarkingForFullCollection() |
| { |
| // Mark bits are sticky and so is our summary of mark bits. We only clear these during full |
| // collections, so if you survived the last collection you will survive the next one so long |
| // as the next one is eden. |
| m_markingNotEmpty.clearAll(); |
| m_markingRetired.clearAll(); |
| } |
| |
| void MarkedAllocator::endMarking() |
| { |
| m_allocated.clearAll(); |
| |
| // It's surprising and frustrating to comprehend, but the end-of-marking flip does not need to |
| // know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ |
| // vectors. |
| |
| if (needsDestruction()) { |
| // If blocks need destruction then nothing is empty! This is a correct assertion but may |
| // become wrong once we go full concurrent: when we create a new block, it will flicker |
| // into the empty set for a tiny moment. On the other hand, this code is likely to be run |
| // in stopTheWorld. |
| ASSERT(m_empty.isEmpty()); |
| m_canAllocateButNotEmpty = m_live & ~m_markingRetired; |
| return; |
| } |
| |
| m_empty = m_live & ~m_markingNotEmpty; |
| m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired; |
| |
| if (false) { |
| dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n"); |
| dumpBits(WTF::dataFile()); |
| } |
| } |
| |
| void MarkedAllocator::snapshotUnsweptForEdenCollection() |
| { |
| m_unswept |= m_eden; |
| } |
| |
| void MarkedAllocator::snapshotUnsweptForFullCollection() |
| { |
| m_unswept = m_live; |
| } |
| |
| MarkedBlock::Handle* MarkedAllocator::findBlockToSweep() |
| { |
| m_unsweptCursor = m_unswept.findBit(m_unsweptCursor, true); |
| if (m_unsweptCursor >= m_blocks.size()) |
| return nullptr; |
| return m_blocks[m_unsweptCursor]; |
| } |
| |
| void MarkedAllocator::sweep() |
| { |
| m_unswept.forEachSetBit( |
| [&] (size_t index) { |
| MarkedBlock::Handle* block = m_blocks[index]; |
| block->sweep(); |
| }); |
| } |
| |
| void MarkedAllocator::shrink() |
| { |
| m_empty.forEachSetBit( |
| [&] (size_t index) { |
| markedSpace().freeBlock(m_blocks[index]); |
| }); |
| } |
| |
| void MarkedAllocator::assertNoUnswept() |
| { |
| if (ASSERT_DISABLED) |
| return; |
| |
| if (m_unswept.isEmpty()) |
| return; |
| |
| dataLog("Assertion failed: unswept not empty in ", *this, ".\n"); |
| dumpBits(); |
| ASSERT_NOT_REACHED(); |
| } |
| |
| void MarkedAllocator::dump(PrintStream& out) const |
| { |
| out.print(RawPointer(this), ":", m_cellSize, "/", m_attributes); |
| } |
| |
| void MarkedAllocator::dumpBits(PrintStream& out) |
| { |
| unsigned maxNameLength = 0; |
| forEachBitVectorWithName( |
| NoLockingNecessary, |
| [&] (FastBitVector&, const char* name) { |
| unsigned length = strlen(name); |
| maxNameLength = std::max(maxNameLength, length); |
| }); |
| |
| forEachBitVectorWithName( |
| NoLockingNecessary, |
| [&] (FastBitVector& vector, const char* name) { |
| out.print(" ", name, ": "); |
| for (unsigned i = maxNameLength - strlen(name); i--;) |
| out.print(" "); |
| out.print(vector, "\n"); |
| }); |
| } |
| |
| MarkedSpace& MarkedAllocator::markedSpace() const |
| { |
| return m_subspace->space(); |
| } |
| |
| } // namespace JSC |
| |
