#ifndef MarkedBlock_h
#define MarkedBlock_h
#include "CardSet.h"
#include <wtf/Bitmap.h>
#include <wtf/DoublyLinkedList.h>
#include <wtf/HashFunctions.h>
#include <wtf/PageAllocationAligned.h>
#include <wtf/StdLibExtras.h>
#include <wtf/Vector.h>
#define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
#if HEAP_LOG_BLOCK_STATE_TRANSITIONS
#define HEAP_LOG_BLOCK_STATE_TRANSITION(block) do { \
printf("%s:%d %s: block %s = %p, %d\n", \
__FILE__, __LINE__, __FUNCTION__, #block, (block), (block)->m_state); \
} while (false)
#else
#define HEAP_LOG_BLOCK_STATE_TRANSITION(block) ((void)0)
#endif
namespace JSC {
class Heap;
class JSCell;
typedef uintptr_t Bits;
static const size_t KB = 1024;
static const size_t MB = 1024 * 1024;
bool isZapped(const JSCell*);
class MarkedBlock : public DoublyLinkedListNode<MarkedBlock> {
friend class WTF::DoublyLinkedListNode<MarkedBlock>;
public:
static const size_t atomSize = 4 * sizeof(void*);
static const size_t atomShift = 5;
static const size_t blockSize = 16 * KB;
static const size_t blockMask = ~(blockSize - 1);
static const size_t atomsPerBlock = blockSize / atomSize; static const size_t atomMask = atomsPerBlock - 1;
static const int cardShift = 8; static const size_t bytesPerCard = 1 << cardShift;
static const int cardCount = blockSize / bytesPerCard;
static const int cardMask = cardCount - 1;
struct FreeCell {
FreeCell* next;
};
struct VoidFunctor {
typedef void ReturnType;
void returnValue() { }
};
static MarkedBlock* create(Heap*, size_t cellSize);
static MarkedBlock* recycle(MarkedBlock*, size_t cellSize);
static void destroy(MarkedBlock*);
static bool isAtomAligned(const void*);
static MarkedBlock* blockFor(const void*);
static size_t firstAtom();
Heap* heap() const;
void* allocate();
enum SweepMode { SweepOnly, SweepToFreeList };
FreeCell* sweep(SweepMode = SweepOnly);
void didConsumeFreeList(); void zapFreeList(FreeCell* firstFreeCell);
void clearMarks();
size_t markCount();
bool markCountIsZero();
size_t cellSize();
size_t size();
size_t capacity();
bool isMarked(const void*);
bool testAndSetMarked(const void*);
bool isLive(const JSCell*);
bool isLiveCell(const void*);
void setMarked(const void*);
#if ENABLE(GGC)
void setDirtyObject(const void* atom)
{
ASSERT(MarkedBlock::blockFor(atom) == this);
m_cards.markCardForAtom(atom);
}
uint8_t* addressOfCardFor(const void* atom)
{
ASSERT(MarkedBlock::blockFor(atom) == this);
return &m_cards.cardForAtom(atom);
}
static inline size_t offsetOfCards()
{
return OBJECT_OFFSETOF(MarkedBlock, m_cards);
}
static inline size_t offsetOfMarks()
{
return OBJECT_OFFSETOF(MarkedBlock, m_marks);
}
typedef Vector<JSCell*, 32> DirtyCellVector;
inline void gatherDirtyCells(DirtyCellVector&);
template <int size> inline void gatherDirtyCellsWithSize(DirtyCellVector&);
#endif
template <typename Functor> void forEachCell(Functor&);
private:
static const size_t atomAlignmentMask = atomSize - 1;
enum BlockState { New, FreeListed, Allocated, Marked, Zapped };
typedef char Atom[atomSize];
MarkedBlock(const PageAllocationAligned&, Heap*, size_t cellSize);
Atom* atoms();
size_t atomNumber(const void*);
void callDestructor(JSCell*, void* jsFinalObjectVPtr);
template<BlockState, SweepMode> FreeCell* specializedSweep();
#if ENABLE(GGC)
CardSet<bytesPerCard, blockSize> m_cards;
#endif
size_t m_atomsPerCell;
size_t m_endAtom; #if ENABLE(PARALLEL_GC)
WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic> m_marks;
#else
WTF::Bitmap<atomsPerBlock, WTF::BitmapNotAtomic> m_marks;
#endif
BlockState m_state;
PageAllocationAligned m_allocation;
Heap* m_heap;
MarkedBlock* m_prev;
MarkedBlock* m_next;
};
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 MarkedBlock* MarkedBlock::blockFor(const void* p)
{
return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
}
inline Heap* MarkedBlock::heap() const
{
return m_heap;
}
inline void MarkedBlock::didConsumeFreeList()
{
HEAP_LOG_BLOCK_STATE_TRANSITION(this);
ASSERT(m_state == FreeListed);
m_state = Allocated;
}
inline void MarkedBlock::clearMarks()
{
HEAP_LOG_BLOCK_STATE_TRANSITION(this);
ASSERT(m_state != New && m_state != FreeListed);
m_marks.clearAll();
m_state = Marked;
}
inline size_t MarkedBlock::markCount()
{
return m_marks.count();
}
inline bool MarkedBlock::markCountIsZero()
{
return m_marks.isEmpty();
}
inline size_t MarkedBlock::cellSize()
{
return m_atomsPerCell * atomSize;
}
inline size_t MarkedBlock::size()
{
return markCount() * cellSize();
}
inline size_t MarkedBlock::capacity()
{
return m_allocation.size();
}
inline size_t MarkedBlock::atomNumber(const void* p)
{
return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
}
inline bool MarkedBlock::isMarked(const void* p)
{
return m_marks.get(atomNumber(p));
}
inline bool MarkedBlock::testAndSetMarked(const void* p)
{
return m_marks.concurrentTestAndSet(atomNumber(p));
}
inline void MarkedBlock::setMarked(const void* p)
{
m_marks.set(atomNumber(p));
}
inline bool MarkedBlock::isLive(const JSCell* cell)
{
switch (m_state) {
case Allocated:
return true;
case Zapped:
if (isZapped(cell)) {
ASSERT(!m_marks.get(atomNumber(cell)));
return false;
}
return true;
case Marked:
return m_marks.get(atomNumber(cell));
case New:
case FreeListed:
ASSERT_NOT_REACHED();
return false;
}
ASSERT_NOT_REACHED();
return false;
}
inline bool MarkedBlock::isLiveCell(const void* p)
{
ASSERT(MarkedBlock::isAtomAligned(p));
size_t atomNumber = this->atomNumber(p);
size_t firstAtom = this->firstAtom();
if (atomNumber < firstAtom) return false;
if ((atomNumber - firstAtom) % m_atomsPerCell) return false;
return isLive(static_cast<const JSCell*>(p));
}
template <typename Functor> inline void MarkedBlock::forEachCell(Functor& functor)
{
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
if (!isLive(cell))
continue;
functor(cell);
}
}
#if ENABLE(GGC)
template <int _cellSize> void MarkedBlock::gatherDirtyCellsWithSize(DirtyCellVector& dirtyCells)
{
if (m_cards.testAndClear(0)) {
char* ptr = reinterpret_cast<char*>(&atoms()[firstAtom()]);
const char* end = reinterpret_cast<char*>(this) + bytesPerCard;
while (ptr < end) {
JSCell* cell = reinterpret_cast<JSCell*>(ptr);
if (isMarked(cell))
dirtyCells.append(cell);
ptr += _cellSize;
}
}
const size_t cellOffset = firstAtom() * atomSize % _cellSize;
for (size_t i = 1; i < m_cards.cardCount; i++) {
if (!m_cards.testAndClear(i))
continue;
char* ptr = reinterpret_cast<char*>(this) + i * bytesPerCard + cellOffset;
char* end = reinterpret_cast<char*>(this) + (i + 1) * bytesPerCard;
while (ptr < end) {
JSCell* cell = reinterpret_cast<JSCell*>(ptr);
if (isMarked(cell))
dirtyCells.append(cell);
ptr += _cellSize;
}
}
}
void MarkedBlock::gatherDirtyCells(DirtyCellVector& dirtyCells)
{
COMPILE_ASSERT((int)m_cards.cardCount == (int)cardCount, MarkedBlockCardCountsMatch);
ASSERT(m_state != New && m_state != FreeListed);
m_state = Marked;
if (markCountIsZero())
return;
size_t cellSize = this->cellSize();
if (cellSize == 32) {
gatherDirtyCellsWithSize<32>(dirtyCells);
return;
}
if (cellSize == 64) {
gatherDirtyCellsWithSize<64>(dirtyCells);
return;
}
const size_t firstCellOffset = firstAtom() * atomSize % cellSize;
if (m_cards.testAndClear(0)) {
char* ptr = reinterpret_cast<char*>(this) + firstAtom() * atomSize;
char* end = reinterpret_cast<char*>(this) + bytesPerCard;
while (ptr < end) {
JSCell* cell = reinterpret_cast<JSCell*>(ptr);
if (isMarked(cell))
dirtyCells.append(cell);
ptr += cellSize;
}
}
for (size_t i = 1; i < m_cards.cardCount; i++) {
if (!m_cards.testAndClear(i))
continue;
char* ptr = reinterpret_cast<char*>(this) + firstCellOffset + cellSize * ((i * bytesPerCard + cellSize - 1 - firstCellOffset) / cellSize);
char* end = reinterpret_cast<char*>(this) + std::min((i + 1) * bytesPerCard, m_endAtom * atomSize);
while (ptr < end) {
JSCell* cell = reinterpret_cast<JSCell*>(ptr);
if (isMarked(cell))
dirtyCells.append(cell);
ptr += cellSize;
}
}
}
#endif
}
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;
};
}
#endif // MarkedBlock_h