#pragma once
#include "AllocatorAttributes.h"
#include "DestructionMode.h"
#include "HeapCell.h"
#include "IterationStatus.h"
#include "WeakSet.h"
#include <wtf/Atomics.h>
#include <wtf/Bitmap.h>
#include <wtf/HashFunctions.h>
#include <wtf/StdLibExtras.h>
namespace JSC {
class FreeList;
class Heap;
class JSCell;
class MarkedAllocator;
class MarkedSpace;
class SlotVisitor;
class Subspace;
typedef uintptr_t Bits;
typedef uint32_t HeapVersion;
class MarkedBlock {
WTF_MAKE_NONCOPYABLE(MarkedBlock);
friend class LLIntOffsetsExtractor;
friend struct VerifyMarked;
public:
class Handle;
private:
friend class Handle;
public:
static const size_t atomSize = 16; static const size_t blockSize = 16 * KB;
static const size_t blockMask = ~(blockSize - 1);
static const size_t atomsPerBlock = blockSize / atomSize;
static_assert(!(MarkedBlock::atomSize & (MarkedBlock::atomSize - 1)), "MarkedBlock::atomSize must be a power of two.");
static_assert(!(MarkedBlock::blockSize & (MarkedBlock::blockSize - 1)), "MarkedBlock::blockSize must be a power of two.");
struct VoidFunctor {
typedef void ReturnType;
void returnValue() { }
};
class CountFunctor {
public:
typedef size_t ReturnType;
CountFunctor() : m_count(0) { }
void count(size_t count) const { m_count += count; }
ReturnType returnValue() const { return m_count; }
private:
mutable ReturnType m_count;
};
class Handle {
WTF_MAKE_NONCOPYABLE(Handle);
WTF_MAKE_FAST_ALLOCATED;
friend class LLIntOffsetsExtractor;
friend class MarkedBlock;
friend struct VerifyMarked;
public:
~Handle();
MarkedBlock& block();
void* cellAlign(void*);
bool isEmpty();
void lastChanceToFinalize();
MarkedAllocator* allocator() const;
Subspace* subspace() const;
Heap* heap() const;
inline MarkedSpace* space() const;
VM* vm() const;
WeakSet& weakSet();
enum SweepMode { SweepOnly, SweepToFreeList };
void sweep(FreeList*);
template<typename DestroyFunc>
void finishSweepKnowingSubspace(FreeList*, const DestroyFunc&);
void unsweepWithNoNewlyAllocated();
void zap(const FreeList&);
void shrink();
void visitWeakSet(SlotVisitor&);
void reapWeakSet();
void didConsumeFreeList(); void stopAllocating(const FreeList&);
void resumeAllocating(FreeList&);
size_t cellSize();
inline unsigned cellsPerBlock();
const AllocatorAttributes& attributes() const;
DestructionMode destruction() const;
bool needsDestruction() const;
HeapCell::Kind cellKind() const;
size_t markCount();
size_t size();
inline bool isLive(HeapVersion markingVersion, bool isMarking, const HeapCell*);
inline bool isLiveCell(HeapVersion markingVersion, bool isMarking, const void*);
bool isLive(const HeapCell*);
bool isLiveCell(const void*);
bool isFreeListedCell(const void* target) const;
bool isNewlyAllocated(const void*);
void setNewlyAllocated(const void*);
void clearNewlyAllocated(const void*);
HeapVersion newlyAllocatedVersion() const { return m_newlyAllocatedVersion; }
inline bool isNewlyAllocatedStale() const;
inline bool hasAnyNewlyAllocated();
void resetAllocated();
template <typename Functor> IterationStatus forEachCell(const Functor&);
template <typename Functor> inline IterationStatus forEachLiveCell(const Functor&);
template <typename Functor> inline IterationStatus forEachDeadCell(const Functor&);
template <typename Functor> inline IterationStatus forEachMarkedCell(const Functor&);
JS_EXPORT_PRIVATE bool areMarksStale();
void assertMarksNotStale();
bool isFreeListed() const { return m_isFreeListed; }
size_t index() const { return m_index; }
void removeFromAllocator();
void didAddToAllocator(MarkedAllocator*, size_t index);
void didRemoveFromAllocator();
void dumpState(PrintStream&);
private:
Handle(Heap&, void*);
enum SweepDestructionMode { BlockHasNoDestructors, BlockHasDestructors, BlockHasDestructorsAndCollectorIsRunning };
enum ScribbleMode { DontScribble, Scribble };
enum EmptyMode { IsEmpty, NotEmpty };
enum NewlyAllocatedMode { HasNewlyAllocated, DoesNotHaveNewlyAllocated };
enum MarksMode { MarksStale, MarksNotStale };
SweepDestructionMode sweepDestructionMode();
EmptyMode emptyMode();
ScribbleMode scribbleMode();
NewlyAllocatedMode newlyAllocatedMode();
MarksMode marksMode();
template<bool, EmptyMode, SweepMode, SweepDestructionMode, ScribbleMode, NewlyAllocatedMode, MarksMode, typename DestroyFunc>
void specializedSweep(FreeList*, EmptyMode, SweepMode, SweepDestructionMode, ScribbleMode, NewlyAllocatedMode, MarksMode, const DestroyFunc&);
void setIsFreeListed();
MarkedBlock::Handle* m_prev;
MarkedBlock::Handle* m_next;
size_t m_atomsPerCell { std::numeric_limits<size_t>::max() };
size_t m_endAtom { std::numeric_limits<size_t>::max() };
WTF::Bitmap<atomsPerBlock> m_newlyAllocated;
AllocatorAttributes m_attributes;
bool m_isFreeListed { false };
MarkedAllocator* m_allocator { nullptr };
size_t m_index { std::numeric_limits<size_t>::max() };
WeakSet m_weakSet;
HeapVersion m_newlyAllocatedVersion;
MarkedBlock* m_block { nullptr };
};
static MarkedBlock::Handle* tryCreate(Heap&);
Handle& handle();
VM* vm() const;
inline Heap* heap() const;
inline MarkedSpace* space() const;
static bool isAtomAligned(const void*);
static MarkedBlock* blockFor(const void*);
static size_t firstAtom();
size_t atomNumber(const void*);
size_t markCount();
bool isMarked(const void*);
bool isMarked(HeapVersion markingVersion, const void*);
bool isMarkedConcurrently(HeapVersion markingVersion, const void*);
bool isMarked(const void*, Dependency);
bool testAndSetMarked(const void*, Dependency);
bool isAtom(const void*);
void clearMarked(const void*);
size_t cellSize();
const AllocatorAttributes& attributes() const;
bool hasAnyMarked() const;
void noteMarked();
#if ASSERT_DISABLED
void assertValidCell(VM&, HeapCell*) const { }
#else
void assertValidCell(VM&, HeapCell*) const;
#endif
WeakSet& weakSet();
JS_EXPORT_PRIVATE bool areMarksStale();
bool areMarksStale(HeapVersion markingVersion);
DependencyWith<bool> areMarksStaleWithDependency(HeapVersion markingVersion);
Dependency aboutToMark(HeapVersion markingVersion);
#if ASSERT_DISABLED
void assertMarksNotStale() { }
#else
JS_EXPORT_PRIVATE void assertMarksNotStale();
#endif
bool needsDestruction() const { return m_needsDestruction; }
void updateNeedsDestruction();
void resetMarks();
bool isMarkedRaw(const void* p);
HeapVersion markingVersion() const { return m_markingVersion; }
private:
static const size_t atomAlignmentMask = atomSize - 1;
typedef char Atom[atomSize];
MarkedBlock(VM&, Handle&);
Atom* atoms();
JS_EXPORT_PRIVATE void aboutToMarkSlow(HeapVersion markingVersion);
void clearHasAnyMarked();
void noteMarkedSlow();
inline bool marksConveyLivenessDuringMarking(HeapVersion markingVersion);
WTF::Bitmap<atomsPerBlock> m_marks;
bool m_needsDestruction;
Lock m_lock;
int16_t m_biasedMarkCount;
int16_t m_markCountBias;
HeapVersion m_markingVersion;
Handle& m_handle;
VM* m_vm;
};
inline MarkedBlock::Handle& MarkedBlock::handle()
{
return m_handle;
}
inline MarkedBlock& MarkedBlock::Handle::block()
{
return *m_block;
}
inline size_t MarkedBlock::firstAtom()
{
return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
}
inline MarkedBlock::Atom* MarkedBlock::atoms()
{
return reinterpret_cast<Atom*>(this);
}
inline bool MarkedBlock::isAtomAligned(const void* p)
{
return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
}
inline void* MarkedBlock::Handle::cellAlign(void* p)
{
Bits base = reinterpret_cast<Bits>(block().atoms() + firstAtom());
Bits bits = reinterpret_cast<Bits>(p);
bits -= base;
bits -= bits % cellSize();
bits += base;
return reinterpret_cast<void*>(bits);
}
inline MarkedBlock* MarkedBlock::blockFor(const void* p)
{
return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
}
inline MarkedAllocator* MarkedBlock::Handle::allocator() const
{
return m_allocator;
}
inline Heap* MarkedBlock::Handle::heap() const
{
return m_weakSet.heap();
}
inline VM* MarkedBlock::Handle::vm() const
{
return m_weakSet.vm();
}
inline VM* MarkedBlock::vm() const
{
return m_vm;
}
inline WeakSet& MarkedBlock::Handle::weakSet()
{
return m_weakSet;
}
inline WeakSet& MarkedBlock::weakSet()
{
return m_handle.weakSet();
}
inline void MarkedBlock::Handle::shrink()
{
m_weakSet.shrink();
}
inline void MarkedBlock::Handle::visitWeakSet(SlotVisitor& visitor)
{
return m_weakSet.visit(visitor);
}
inline void MarkedBlock::Handle::reapWeakSet()
{
m_weakSet.reap();
}
inline size_t MarkedBlock::Handle::cellSize()
{
return m_atomsPerCell * atomSize;
}
inline size_t MarkedBlock::cellSize()
{
return m_handle.cellSize();
}
inline const AllocatorAttributes& MarkedBlock::Handle::attributes() const
{
return m_attributes;
}
inline const AllocatorAttributes& MarkedBlock::attributes() const
{
return m_handle.attributes();
}
inline bool MarkedBlock::Handle::needsDestruction() const
{
return m_attributes.destruction == NeedsDestruction;
}
inline DestructionMode MarkedBlock::Handle::destruction() const
{
return m_attributes.destruction;
}
inline HeapCell::Kind MarkedBlock::Handle::cellKind() const
{
return m_attributes.cellKind;
}
inline size_t MarkedBlock::Handle::markCount()
{
return m_block->markCount();
}
inline size_t MarkedBlock::Handle::size()
{
return markCount() * cellSize();
}
inline size_t MarkedBlock::atomNumber(const void* p)
{
return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
}
inline bool MarkedBlock::areMarksStale(HeapVersion markingVersion)
{
return markingVersion != m_markingVersion;
}
ALWAYS_INLINE DependencyWith<bool> MarkedBlock::areMarksStaleWithDependency(HeapVersion markingVersion)
{
HeapVersion version = m_markingVersion;
return dependencyWith(dependency(version), version != markingVersion);
}
inline Dependency MarkedBlock::aboutToMark(HeapVersion markingVersion)
{
auto result = areMarksStaleWithDependency(markingVersion);
if (UNLIKELY(result.value))
aboutToMarkSlow(markingVersion);
return result.dependency;
}
inline void MarkedBlock::Handle::assertMarksNotStale()
{
block().assertMarksNotStale();
}
inline bool MarkedBlock::isMarkedRaw(const void* p)
{
return m_marks.get(atomNumber(p));
}
inline bool MarkedBlock::isMarked(HeapVersion markingVersion, const void* p)
{
return areMarksStale(markingVersion) ? false : isMarkedRaw(p);
}
inline bool MarkedBlock::isMarkedConcurrently(HeapVersion markingVersion, const void* p)
{
auto result = areMarksStaleWithDependency(markingVersion);
if (result.value)
return false;
return m_marks.get(atomNumber(p), result.dependency);
}
inline bool MarkedBlock::isMarked(const void* p, Dependency dependency)
{
assertMarksNotStale();
return m_marks.get(atomNumber(p), dependency);
}
inline bool MarkedBlock::testAndSetMarked(const void* p, Dependency dependency)
{
assertMarksNotStale();
return m_marks.concurrentTestAndSet(atomNumber(p), dependency);
}
inline bool MarkedBlock::Handle::isNewlyAllocated(const void* p)
{
return m_newlyAllocated.get(m_block->atomNumber(p));
}
inline void MarkedBlock::Handle::setNewlyAllocated(const void* p)
{
m_newlyAllocated.set(m_block->atomNumber(p));
}
inline void MarkedBlock::Handle::clearNewlyAllocated(const void* p)
{
m_newlyAllocated.clear(m_block->atomNumber(p));
}
inline bool MarkedBlock::isAtom(const void* p)
{
ASSERT(MarkedBlock::isAtomAligned(p));
size_t atomNumber = this->atomNumber(p);
size_t firstAtom = MarkedBlock::firstAtom();
if (atomNumber < firstAtom) return false;
if ((atomNumber - firstAtom) % m_handle.m_atomsPerCell) return false;
if (atomNumber >= m_handle.m_endAtom) return false;
return true;
}
template <typename Functor>
inline IterationStatus MarkedBlock::Handle::forEachCell(const Functor& functor)
{
HeapCell::Kind kind = m_attributes.cellKind;
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
if (functor(cell, kind) == IterationStatus::Done)
return IterationStatus::Done;
}
return IterationStatus::Continue;
}
inline bool MarkedBlock::hasAnyMarked() const
{
return m_biasedMarkCount != m_markCountBias;
}
inline void MarkedBlock::noteMarked()
{
int16_t biasedMarkCount = m_biasedMarkCount;
++biasedMarkCount;
m_biasedMarkCount = biasedMarkCount;
if (UNLIKELY(!biasedMarkCount))
noteMarkedSlow();
}
}
namespace WTF {
struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
static unsigned hash(JSC::MarkedBlock* const& key)
{
return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
}
};
template<> struct DefaultHash<JSC::MarkedBlock*> {
typedef MarkedBlockHash Hash;
};
void printInternal(PrintStream& out, JSC::MarkedBlock::Handle::SweepMode);
}