Source/JavaScriptCore/heap/MarkedAllocator.cpp - third_party/webkit - Git at Google

 /*
  * Copyright (C) 2012, 2013, 2016 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 "AllocationScope.h"
 #include "GCActivityCallback.h"
 #include "Heap.h"
 #include "IncrementalSweeper.h"
 #include "JSCInlines.h"
 #include "MarkedBlockInlines.h"
 #include "SuperSampler.h"
 #include "VM.h"
 #include <wtf/CurrentTime.h>

 namespace JSC {

 MarkedAllocator::MarkedAllocator(Heap* heap, MarkedSpace* markedSpace, size_t cellSize, const AllocatorAttributes& attributes)
     : m_currentBlock(0)
     , m_lastActiveBlock(0)
     , m_cellSize(static_cast<unsigned>(cellSize))
     , m_attributes(attributes)
     , m_heap(heap)
     , m_markedSpace(markedSpace)
 {
 }

 bool MarkedAllocator::isPagedOut(double deadline)
 {
     unsigned itersSinceLastTimeCheck = 0;
     for (size_t index = 0; index < m_blocks.size(); ++index) {
         MarkedBlock::Handle* block = m_blocks[index];
         if (block) {
             // Forces us to touch the memory of the block, but has no semantic effect.
             if (block->areMarksStale())
                 block->block().resetMarkingVersion();
         }
         ++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(m_allocationCursor, false);

         if (void* result = tryAllocateIn(m_blocks[m_allocationCursor]))
             return result;
     }

     if (Options::stealEmptyBlocksFromOtherAllocators()
         && shouldStealEmptyBlocksFromOtherAllocators()) {
         if (MarkedBlock::Handle* block = m_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->hasAnyNewlyAllocated());
     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(block));
         ASSERT(!isCanAllocateButNotEmpty(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(m_currentBlock, true);
     m_markedSpace->didAllocateInBlock(m_currentBlock);
     return result;
 }

 ALWAYS_INLINE void MarkedAllocator::doTestCollectionsIfNeeded()
 {
     if (!Options::slowPathAllocsBetweenGCs())
         return;

     static unsigned allocationCount = 0;
     if (!allocationCount) {
         if (!m_heap->isDeferred())
             m_heap->collectAllGarbage();
         ASSERT(m_heap->m_operationInProgress == NoOperation);
     }
     if (++allocationCount >= Options::slowPathAllocsBetweenGCs())
         allocationCount = 0;
 }

 void* MarkedAllocator::allocateSlowCase()
 {
     bool crashOnFailure = true;
     return allocateSlowCaseImpl(crashOnFailure);
 }

 void* MarkedAllocator::tryAllocateSlowCase()
 {
     bool crashOnFailure = false;
     return allocateSlowCaseImpl(crashOnFailure);
 }

 void* MarkedAllocator::allocateSlowCaseImpl(bool crashOnFailure)
 {
     SuperSamplerScope superSamplerScope(false);
     ASSERT(m_heap->vm()->currentThreadIsHoldingAPILock());
     doTestCollectionsIfNeeded();

     ASSERT(!m_markedSpace->isIterating());
     m_heap->didAllocate(m_freeList.originalSize);

     didConsumeFreeList();

     m_heap->collectIfNecessaryOrDefer();

     AllocationScope allocationScope(*m_heap);

     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;

     m_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(
                 [&] (FastBitVector& vector) {
                     ASSERT_UNUSED(vector, vector.numBits() == oldCapacity);
                 });

             ASSERT(m_blocks.capacity() > oldCapacity);

             forEachBitVector(
                 [&] (FastBitVector& vector) {
                     vector.resize(m_blocks.capacity());
                 });
         }
     } else {
         index = m_freeBlockIndices.takeLast();
         ASSERT(!m_blocks[index]);
         m_blocks[index] = block;
     }

     forEachBitVector(
         [&] (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(index, true);
     setIsEmpty(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(
         [&] (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) {
             m_blocks[index]->sweep();
         });
 }

 void MarkedAllocator::shrink()
 {
     m_empty.forEachSetBit(
         [&] (size_t index) {
             m_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(
         [&] (FastBitVector&, const char* name) {
             unsigned length = strlen(name);
             maxNameLength = std::max(maxNameLength, length);
         });

     forEachBitVectorWithName(
         [&] (FastBitVector& vector, const char* name) {
             out.print("    ", name, ": ");
             for (unsigned i = maxNameLength - strlen(name); i--;)
                 out.print(" ");
             out.print(vector, "\n");
         });
 }

 } // namespace JSC
	/*
	* Copyright (C) 2012, 2013, 2016 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 "AllocationScope.h"
	#include "GCActivityCallback.h"
	#include "Heap.h"
	#include "IncrementalSweeper.h"
	#include "JSCInlines.h"
	#include "MarkedBlockInlines.h"
	#include "SuperSampler.h"
	#include "VM.h"
	#include <wtf/CurrentTime.h>

	namespace JSC {

	MarkedAllocator::MarkedAllocator(Heap* heap, MarkedSpace* markedSpace, size_t cellSize, const AllocatorAttributes& attributes)
	: m_currentBlock(0)
	, m_lastActiveBlock(0)
	, m_cellSize(static_cast<unsigned>(cellSize))
	, m_attributes(attributes)
	, m_heap(heap)
	, m_markedSpace(markedSpace)
	{
	}

	bool MarkedAllocator::isPagedOut(double deadline)
	{
	unsigned itersSinceLastTimeCheck = 0;
	for (size_t index = 0; index < m_blocks.size(); ++index) {
	MarkedBlock::Handle* block = m_blocks[index];
	if (block) {
	// Forces us to touch the memory of the block, but has no semantic effect.
	if (block->areMarksStale())
	block->block().resetMarkingVersion();
	}
	++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(m_allocationCursor, false);

	if (void* result = tryAllocateIn(m_blocks[m_allocationCursor]))
	return result;
	}

	if (Options::stealEmptyBlocksFromOtherAllocators()
	&& shouldStealEmptyBlocksFromOtherAllocators()) {
	if (MarkedBlock::Handle* block = m_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->hasAnyNewlyAllocated());
	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(block));
	ASSERT(!isCanAllocateButNotEmpty(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(m_currentBlock, true);
	m_markedSpace->didAllocateInBlock(m_currentBlock);
	return result;
	}

	ALWAYS_INLINE void MarkedAllocator::doTestCollectionsIfNeeded()
	{
	if (!Options::slowPathAllocsBetweenGCs())
	return;

	static unsigned allocationCount = 0;
	if (!allocationCount) {
	if (!m_heap->isDeferred())
	m_heap->collectAllGarbage();
	ASSERT(m_heap->m_operationInProgress == NoOperation);
	}
	if (++allocationCount >= Options::slowPathAllocsBetweenGCs())
	allocationCount = 0;
	}

	void* MarkedAllocator::allocateSlowCase()
	{
	bool crashOnFailure = true;
	return allocateSlowCaseImpl(crashOnFailure);
	}

	void* MarkedAllocator::tryAllocateSlowCase()
	{
	bool crashOnFailure = false;
	return allocateSlowCaseImpl(crashOnFailure);
	}

	void* MarkedAllocator::allocateSlowCaseImpl(bool crashOnFailure)
	{
	SuperSamplerScope superSamplerScope(false);
	ASSERT(m_heap->vm()->currentThreadIsHoldingAPILock());
	doTestCollectionsIfNeeded();

	ASSERT(!m_markedSpace->isIterating());
	m_heap->didAllocate(m_freeList.originalSize);

	didConsumeFreeList();

	m_heap->collectIfNecessaryOrDefer();

	AllocationScope allocationScope(*m_heap);

	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;

	m_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(
	[&] (FastBitVector& vector) {
	ASSERT_UNUSED(vector, vector.numBits() == oldCapacity);
	});

	ASSERT(m_blocks.capacity() > oldCapacity);

	forEachBitVector(
	[&] (FastBitVector& vector) {
	vector.resize(m_blocks.capacity());
	});
	}
	} else {
	index = m_freeBlockIndices.takeLast();
	ASSERT(!m_blocks[index]);
	m_blocks[index] = block;
	}

	forEachBitVector(
	[&] (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(index, true);
	setIsEmpty(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(
	[&] (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) {
	m_blocks[index]->sweep();
	});
	}

	void MarkedAllocator::shrink()
	{
	m_empty.forEachSetBit(
	[&] (size_t index) {
	m_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(
	[&] (FastBitVector&, const char* name) {
	unsigned length = strlen(name);
	maxNameLength = std::max(maxNameLength, length);
	});

	forEachBitVectorWithName(
	[&] (FastBitVector& vector, const char* name) {
	out.print(" ", name, ": ");
	for (unsigned i = maxNameLength - strlen(name); i--;)
	out.print(" ");
	out.print(vector, "\n");
	});
	}

	} // namespace JSC