Source/JavaScriptCore/heap/PreciseAllocation.cpp - WebKit - Git at Google

 /*
  * Copyright (C) 2016-2021 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 "PreciseAllocation.h"

 #include "AlignedMemoryAllocator.h"
 #include "IsoCellSetInlines.h"
 #include "JSCInlines.h"
 #include "Scribble.h"
 #include "SubspaceInlines.h"

 namespace JSC {

 static inline bool isAlignedForPreciseAllocation(void* memory)
 {
     uintptr_t allocatedPointer = bitwise_cast<uintptr_t>(memory);
     return !(allocatedPointer & (PreciseAllocation::alignment - 1));
 }

 PreciseAllocation* PreciseAllocation::tryCreate(Heap& heap, size_t size, Subspace* subspace, unsigned indexInSpace)
 {
     if constexpr (validateDFGDoesGC)
         heap.verifyCanGC();

     size_t adjustedAlignmentAllocationSize = headerSize() + size + halfAlignment;
     static_assert(halfAlignment == 8, "We assume that memory returned by malloc has alignment >= 8.");

     // We must use tryAllocateMemory instead of tryAllocateAlignedMemory since we want to use "realloc" feature.
     void* space = subspace->alignedMemoryAllocator()->tryAllocateMemory(adjustedAlignmentAllocationSize);
     if (!space)
         return nullptr;

     bool adjustedAlignment = false;
     if (!isAlignedForPreciseAllocation(space)) {
         space = bitwise_cast<void*>(bitwise_cast<uintptr_t>(space) + halfAlignment);
         adjustedAlignment = true;
         ASSERT(isAlignedForPreciseAllocation(space));
     }

     if (scribbleFreeCells())
         scribble(space, size);
     return new (NotNull, space) PreciseAllocation(heap, size, subspace, indexInSpace, adjustedAlignment);
 }

 PreciseAllocation* PreciseAllocation::tryReallocate(size_t size, Subspace* subspace)
 {
     ASSERT(!isLowerTier());
     size_t adjustedAlignmentAllocationSize = headerSize() + size + halfAlignment;
     static_assert(halfAlignment == 8, "We assume that memory returned by malloc has alignment >= 8.");

     ASSERT(subspace == m_subspace);

     unsigned oldCellSize = m_cellSize;
     bool oldAdjustedAlignment = m_adjustedAlignment;
     void* oldBasePointer = basePointer();

     void* newBasePointer = subspace->alignedMemoryAllocator()->tryReallocateMemory(oldBasePointer, adjustedAlignmentAllocationSize);
     if (!newBasePointer)
         return nullptr;

     PreciseAllocation* newAllocation = bitwise_cast<PreciseAllocation*>(newBasePointer);
     bool newAdjustedAlignment = false;
     if (!isAlignedForPreciseAllocation(newBasePointer)) {
         newAdjustedAlignment = true;
         newAllocation = bitwise_cast<PreciseAllocation*>(bitwise_cast<uintptr_t>(newBasePointer) + halfAlignment);
         ASSERT(isAlignedForPreciseAllocation(static_cast<void*>(newAllocation)));
     }

     // We have 4 patterns.
     // oldAdjustedAlignment = true  newAdjustedAlignment = true  => Do nothing.
     // oldAdjustedAlignment = true  newAdjustedAlignment = false => Shift forward by halfAlignment
     // oldAdjustedAlignment = false newAdjustedAlignment = true  => Shift backward by halfAlignment
     // oldAdjustedAlignment = false newAdjustedAlignment = false => Do nothing.

     if (oldAdjustedAlignment != newAdjustedAlignment) {
         if (oldAdjustedAlignment) {
             ASSERT(!newAdjustedAlignment);
             ASSERT(newAllocation == newBasePointer);
             // Old   [ 8 ][  content  ]
             // Now   [   ][  content  ]
             // New   [  content  ]...
             memmove(newBasePointer, bitwise_cast<char*>(newBasePointer) + halfAlignment, oldCellSize + PreciseAllocation::headerSize());
         } else {
             ASSERT(newAdjustedAlignment);
             ASSERT(newAllocation != newBasePointer);
             ASSERT(newAllocation == bitwise_cast<void*>(bitwise_cast<char*>(newBasePointer) + halfAlignment));
             // Old   [  content  ]
             // Now   [  content  ][   ]
             // New   [ 8 ][  content  ]
             memmove(bitwise_cast<char*>(newBasePointer) + halfAlignment, newBasePointer, oldCellSize + PreciseAllocation::headerSize());
         }
     }

     newAllocation->m_cellSize = size;
     newAllocation->m_adjustedAlignment = newAdjustedAlignment;
     return newAllocation;
 }


 PreciseAllocation* PreciseAllocation::createForLowerTier(Heap& heap, size_t size, Subspace* subspace, uint8_t lowerTierIndex)
 {
     if constexpr (validateDFGDoesGC)
         heap.verifyCanGC();

     size_t adjustedAlignmentAllocationSize = headerSize() + size + halfAlignment;
     static_assert(halfAlignment == 8, "We assume that memory returned by malloc has alignment >= 8.");

     void* space = subspace->alignedMemoryAllocator()->tryAllocateMemory(adjustedAlignmentAllocationSize);
     RELEASE_ASSERT(space);

     bool adjustedAlignment = false;
     if (!isAlignedForPreciseAllocation(space)) {
         space = bitwise_cast<void*>(bitwise_cast<uintptr_t>(space) + halfAlignment);
         adjustedAlignment = true;
         ASSERT(isAlignedForPreciseAllocation(space));
     }

     if (scribbleFreeCells())
         scribble(space, size);
     PreciseAllocation* preciseAllocation = new (NotNull, space) PreciseAllocation(heap, size, subspace, 0, adjustedAlignment);
     preciseAllocation->m_lowerTierIndex = lowerTierIndex;
     return preciseAllocation;
 }

 PreciseAllocation* PreciseAllocation::reuseForLowerTier()
 {
     Heap& heap = *this->heap();
     size_t size = m_cellSize;
     Subspace* subspace = m_subspace;
     bool adjustedAlignment = m_adjustedAlignment;
     uint8_t lowerTierIndex = m_lowerTierIndex;
     void* basePointer = this->basePointer();

     this->~PreciseAllocation();

     void* space = basePointer;
     ASSERT((!isAlignedForPreciseAllocation(basePointer)) == adjustedAlignment);
     if (adjustedAlignment)
         space = bitwise_cast<void*>(bitwise_cast<uintptr_t>(basePointer) + halfAlignment);

     PreciseAllocation* preciseAllocation = new (NotNull, space) PreciseAllocation(heap, size, subspace, 0, adjustedAlignment);
     preciseAllocation->m_lowerTierIndex = lowerTierIndex;
     preciseAllocation->m_hasValidCell = false;
     return preciseAllocation;
 }

 PreciseAllocation::PreciseAllocation(Heap& heap, size_t size, Subspace* subspace, unsigned indexInSpace, bool adjustedAlignment)
     : m_indexInSpace(indexInSpace)
     , m_cellSize(size)
     , m_isNewlyAllocated(true)
     , m_hasValidCell(true)
     , m_adjustedAlignment(adjustedAlignment)
     , m_attributes(subspace->attributes())
     , m_subspace(subspace)
     , m_weakSet(heap.vm())
 {
     m_isMarked.store(0);
     ASSERT(cell()->isPreciseAllocation());
 }

 PreciseAllocation::~PreciseAllocation()
 {
     if (isOnList())
         remove();
 }

 void PreciseAllocation::lastChanceToFinalize()
 {
     m_weakSet.lastChanceToFinalize();
     clearMarked();
     clearNewlyAllocated();
     sweep();
 }

 void PreciseAllocation::flip()
 {
     ASSERT(heap()->collectionScope() == CollectionScope::Full);
     // Propagate the last time's mark bit to m_isNewlyAllocated so that `isLive` will say "yes" until this GC cycle finishes.
     // After that, m_isNewlyAllocated is cleared again. So only previously marked or actually newly created objects survive.
     // We do not need to care about concurrency here since marking thread is stopped right now. This is equivalent to the logic
     // of MarkedBlock::aboutToMarkSlow.
     // We invoke this function only when this is full collection. This ensures that at the end of upcoming cycle, we will
     // clear NewlyAllocated bits of all objects. So this works correctly.
     //
     //                                      N: NewlyAllocated, M: Marked
     //                                                 after this         at the end        When cycle
     //                                            N M  function    N M     of cycle    N M  is finished   N M
     // The live object survives the last cycle    0 1      =>      1 0        =>       1 1       =>       0 1    => live
     // The dead object in the last cycle          0 0      =>      0 0        =>       0 0       =>       0 0    => dead
     // The live object newly created after this            =>      1 0        =>       1 1       =>       0 1    => live
     // The dead object newly created after this            =>      1 0        =>       1 0       =>       0 0    => dead
     // The live object newly created before this  1 0      =>      1 0        =>       1 1       =>       0 1    => live
     // The dead object newly created before this  1 0      =>      1 0        =>       1 0       =>       0 0    => dead
     //                                                                                                    ^
     //                                                              This is ensured since this function is used only for full GC.
     m_isNewlyAllocated |= isMarked();
     m_isMarked.store(false, std::memory_order_relaxed);
 }

 bool PreciseAllocation::isEmpty()
 {
     return !isMarked() && m_weakSet.isEmpty() && !isNewlyAllocated();
 }

 void PreciseAllocation::sweep()
 {
     m_weakSet.sweep();

     if (m_hasValidCell && !isLive()) {
         if (m_attributes.destruction == NeedsDestruction)
             m_subspace->destroy(vm(), static_cast<JSCell*>(cell()));
         // We should clear IsoCellSet's bit before actually destroying PreciseAllocation
         // since PreciseAllocation's destruction can be delayed until its WeakSet is cleared.
         if (isLowerTier())
             static_cast<IsoSubspace*>(m_subspace)->clearIsoCellSetBit(this);
         m_hasValidCell = false;
     }
 }

 void PreciseAllocation::destroy()
 {
     AlignedMemoryAllocator* allocator = m_subspace->alignedMemoryAllocator();
     void* basePointer = this->basePointer();
     this->~PreciseAllocation();
     allocator->freeMemory(basePointer);
 }

 void PreciseAllocation::dump(PrintStream& out) const
 {
     out.print(RawPointer(this), ":(cell at ", RawPointer(cell()), " with size ", m_cellSize, " and attributes ", m_attributes, ")");
 }

 #if ASSERT_ENABLED
 void PreciseAllocation::assertValidCell(VM& vm, HeapCell* cell) const
 {
     ASSERT(&vm == &this->vm());
     ASSERT(cell == this->cell());
     ASSERT(m_hasValidCell);
 }
 #endif

 } // namespace JSC
	/*
	* Copyright (C) 2016-2021 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 "PreciseAllocation.h"

	#include "AlignedMemoryAllocator.h"
	#include "IsoCellSetInlines.h"
	#include "JSCInlines.h"
	#include "Scribble.h"
	#include "SubspaceInlines.h"

	namespace JSC {

	static inline bool isAlignedForPreciseAllocation(void* memory)
	{
	uintptr_t allocatedPointer = bitwise_cast<uintptr_t>(memory);
	return !(allocatedPointer & (PreciseAllocation::alignment - 1));
	}

	PreciseAllocation* PreciseAllocation::tryCreate(Heap& heap, size_t size, Subspace* subspace, unsigned indexInSpace)
	{
	if constexpr (validateDFGDoesGC)
	heap.verifyCanGC();

	size_t adjustedAlignmentAllocationSize = headerSize() + size + halfAlignment;
	static_assert(halfAlignment == 8, "We assume that memory returned by malloc has alignment >= 8.");

	// We must use tryAllocateMemory instead of tryAllocateAlignedMemory since we want to use "realloc" feature.
	void* space = subspace->alignedMemoryAllocator()->tryAllocateMemory(adjustedAlignmentAllocationSize);
	if (!space)
	return nullptr;

	bool adjustedAlignment = false;
	if (!isAlignedForPreciseAllocation(space)) {
	space = bitwise_cast<void*>(bitwise_cast<uintptr_t>(space) + halfAlignment);
	adjustedAlignment = true;
	ASSERT(isAlignedForPreciseAllocation(space));
	}

	if (scribbleFreeCells())
	scribble(space, size);
	return new (NotNull, space) PreciseAllocation(heap, size, subspace, indexInSpace, adjustedAlignment);
	}

	PreciseAllocation* PreciseAllocation::tryReallocate(size_t size, Subspace* subspace)
	{
	ASSERT(!isLowerTier());
	size_t adjustedAlignmentAllocationSize = headerSize() + size + halfAlignment;
	static_assert(halfAlignment == 8, "We assume that memory returned by malloc has alignment >= 8.");

	ASSERT(subspace == m_subspace);

	unsigned oldCellSize = m_cellSize;
	bool oldAdjustedAlignment = m_adjustedAlignment;
	void* oldBasePointer = basePointer();

	void* newBasePointer = subspace->alignedMemoryAllocator()->tryReallocateMemory(oldBasePointer, adjustedAlignmentAllocationSize);
	if (!newBasePointer)
	return nullptr;

	PreciseAllocation* newAllocation = bitwise_cast<PreciseAllocation*>(newBasePointer);
	bool newAdjustedAlignment = false;
	if (!isAlignedForPreciseAllocation(newBasePointer)) {
	newAdjustedAlignment = true;
	newAllocation = bitwise_cast<PreciseAllocation*>(bitwise_cast<uintptr_t>(newBasePointer) + halfAlignment);
	ASSERT(isAlignedForPreciseAllocation(static_cast<void*>(newAllocation)));
	}

	// We have 4 patterns.
	// oldAdjustedAlignment = true newAdjustedAlignment = true => Do nothing.
	// oldAdjustedAlignment = true newAdjustedAlignment = false => Shift forward by halfAlignment
	// oldAdjustedAlignment = false newAdjustedAlignment = true => Shift backward by halfAlignment
	// oldAdjustedAlignment = false newAdjustedAlignment = false => Do nothing.

	if (oldAdjustedAlignment != newAdjustedAlignment) {
	if (oldAdjustedAlignment) {
	ASSERT(!newAdjustedAlignment);
	ASSERT(newAllocation == newBasePointer);
	// Old [ 8 ][ content ]
	// Now [ ][ content ]
	// New [ content ]...
	memmove(newBasePointer, bitwise_cast<char*>(newBasePointer) + halfAlignment, oldCellSize + PreciseAllocation::headerSize());
	} else {
	ASSERT(newAdjustedAlignment);
	ASSERT(newAllocation != newBasePointer);
	ASSERT(newAllocation == bitwise_cast<void>(bitwise_cast<char>(newBasePointer) + halfAlignment));
	// Old [ content ]
	// Now [ content ][ ]
	// New [ 8 ][ content ]
	memmove(bitwise_cast<char*>(newBasePointer) + halfAlignment, newBasePointer, oldCellSize + PreciseAllocation::headerSize());
	}
	}

	newAllocation->m_cellSize = size;
	newAllocation->m_adjustedAlignment = newAdjustedAlignment;
	return newAllocation;
	}


	PreciseAllocation* PreciseAllocation::createForLowerTier(Heap& heap, size_t size, Subspace* subspace, uint8_t lowerTierIndex)
	{
	if constexpr (validateDFGDoesGC)
	heap.verifyCanGC();

	size_t adjustedAlignmentAllocationSize = headerSize() + size + halfAlignment;
	static_assert(halfAlignment == 8, "We assume that memory returned by malloc has alignment >= 8.");

	void* space = subspace->alignedMemoryAllocator()->tryAllocateMemory(adjustedAlignmentAllocationSize);
	RELEASE_ASSERT(space);

	bool adjustedAlignment = false;
	if (!isAlignedForPreciseAllocation(space)) {
	space = bitwise_cast<void*>(bitwise_cast<uintptr_t>(space) + halfAlignment);
	adjustedAlignment = true;
	ASSERT(isAlignedForPreciseAllocation(space));
	}

	if (scribbleFreeCells())
	scribble(space, size);
	PreciseAllocation* preciseAllocation = new (NotNull, space) PreciseAllocation(heap, size, subspace, 0, adjustedAlignment);
	preciseAllocation->m_lowerTierIndex = lowerTierIndex;
	return preciseAllocation;
	}

	PreciseAllocation* PreciseAllocation::reuseForLowerTier()
	{
	Heap& heap = *this->heap();
	size_t size = m_cellSize;
	Subspace* subspace = m_subspace;
	bool adjustedAlignment = m_adjustedAlignment;
	uint8_t lowerTierIndex = m_lowerTierIndex;
	void* basePointer = this->basePointer();

	this->~PreciseAllocation();

	void* space = basePointer;
	ASSERT((!isAlignedForPreciseAllocation(basePointer)) == adjustedAlignment);
	if (adjustedAlignment)
	space = bitwise_cast<void*>(bitwise_cast<uintptr_t>(basePointer) + halfAlignment);

	PreciseAllocation* preciseAllocation = new (NotNull, space) PreciseAllocation(heap, size, subspace, 0, adjustedAlignment);
	preciseAllocation->m_lowerTierIndex = lowerTierIndex;
	preciseAllocation->m_hasValidCell = false;
	return preciseAllocation;
	}

	PreciseAllocation::PreciseAllocation(Heap& heap, size_t size, Subspace* subspace, unsigned indexInSpace, bool adjustedAlignment)
	: m_indexInSpace(indexInSpace)
	, m_cellSize(size)
	, m_isNewlyAllocated(true)
	, m_hasValidCell(true)
	, m_adjustedAlignment(adjustedAlignment)
	, m_attributes(subspace->attributes())
	, m_subspace(subspace)
	, m_weakSet(heap.vm())
	{
	m_isMarked.store(0);
	ASSERT(cell()->isPreciseAllocation());
	}

	PreciseAllocation::~PreciseAllocation()
	{
	if (isOnList())
	remove();
	}

	void PreciseAllocation::lastChanceToFinalize()
	{
	m_weakSet.lastChanceToFinalize();
	clearMarked();
	clearNewlyAllocated();
	sweep();
	}

	void PreciseAllocation::flip()
	{
	ASSERT(heap()->collectionScope() == CollectionScope::Full);
	// Propagate the last time's mark bit to m_isNewlyAllocated so that `isLive` will say "yes" until this GC cycle finishes.
	// After that, m_isNewlyAllocated is cleared again. So only previously marked or actually newly created objects survive.
	// We do not need to care about concurrency here since marking thread is stopped right now. This is equivalent to the logic
	// of MarkedBlock::aboutToMarkSlow.
	// We invoke this function only when this is full collection. This ensures that at the end of upcoming cycle, we will
	// clear NewlyAllocated bits of all objects. So this works correctly.
	//
	// N: NewlyAllocated, M: Marked
	// after this at the end When cycle
	// N M function N M of cycle N M is finished N M
	// The live object survives the last cycle 0 1 => 1 0 => 1 1 => 0 1 => live
	// The dead object in the last cycle 0 0 => 0 0 => 0 0 => 0 0 => dead
	// The live object newly created after this => 1 0 => 1 1 => 0 1 => live
	// The dead object newly created after this => 1 0 => 1 0 => 0 0 => dead
	// The live object newly created before this 1 0 => 1 0 => 1 1 => 0 1 => live
	// The dead object newly created before this 1 0 => 1 0 => 1 0 => 0 0 => dead
	// ^
	// This is ensured since this function is used only for full GC.
	m_isNewlyAllocated \|= isMarked();
	m_isMarked.store(false, std::memory_order_relaxed);
	}

	bool PreciseAllocation::isEmpty()
	{
	return !isMarked() && m_weakSet.isEmpty() && !isNewlyAllocated();
	}

	void PreciseAllocation::sweep()
	{
	m_weakSet.sweep();

	if (m_hasValidCell && !isLive()) {
	if (m_attributes.destruction == NeedsDestruction)
	m_subspace->destroy(vm(), static_cast<JSCell*>(cell()));
	// We should clear IsoCellSet's bit before actually destroying PreciseAllocation
	// since PreciseAllocation's destruction can be delayed until its WeakSet is cleared.
	if (isLowerTier())
	static_cast<IsoSubspace*>(m_subspace)->clearIsoCellSetBit(this);
	m_hasValidCell = false;
	}
	}

	void PreciseAllocation::destroy()
	{
	AlignedMemoryAllocator* allocator = m_subspace->alignedMemoryAllocator();
	void* basePointer = this->basePointer();
	this->~PreciseAllocation();
	allocator->freeMemory(basePointer);
	}

	void PreciseAllocation::dump(PrintStream& out) const
	{
	out.print(RawPointer(this), ":(cell at ", RawPointer(cell()), " with size ", m_cellSize, " and attributes ", m_attributes, ")");
	}

	#if ASSERT_ENABLED
	void PreciseAllocation::assertValidCell(VM& vm, HeapCell* cell) const
	{
	ASSERT(&vm == &this->vm());
	ASSERT(cell == this->cell());
	ASSERT(m_hasValidCell);
	}
	#endif

	} // namespace JSC