Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (92232 => 92233)
--- trunk/Source/_javascript_Core/ChangeLog 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/ChangeLog 2011-08-02 21:22:34 UTC (rev 92233)
@@ -1,3 +1,50 @@
+2011-08-02 Filip Pizlo <fpi...@apple.com>
+
+ JSC GC uses dummy cells to avoid having to remember which cells
+ it has already destroyed
+ https://bugs.webkit.org/show_bug.cgi?id=65556
+
+ Reviewed by Oliver Hunt.
+
+ This gets rid of dummy cells, and ensures that it's not necessary
+ to invoke a destructor on cells that have already been swept. In
+ the common case, a block knows that either all of its free cells
+ still need to have destructors called, or none of them do, which
+ minimizes the amount of branching that needs to happen per cell
+ when performing a sweep.
+
+ This is performance neutral on SunSpider and V8. It is meant as
+ a stepping stone to simplify the implementation of more
+ sophisticated sweeping algorithms.
+
+ * heap/Heap.cpp:
+ (JSC::CountFunctor::ClearMarks::operator()):
+ * heap/MarkedBlock.cpp:
+ (JSC::MarkedBlock::initForCellSize):
+ (JSC::MarkedBlock::callDestructor):
+ (JSC::MarkedBlock::specializedReset):
+ (JSC::MarkedBlock::reset):
+ (JSC::MarkedBlock::specializedSweep):
+ (JSC::MarkedBlock::sweep):
+ (JSC::MarkedBlock::produceFreeList):
+ (JSC::MarkedBlock::lazySweep):
+ (JSC::MarkedBlock::blessNewBlockForFastPath):
+ (JSC::MarkedBlock::blessNewBlockForSlowPath):
+ (JSC::MarkedBlock::canonicalizeBlock):
+ * heap/MarkedBlock.h:
+ (JSC::MarkedBlock::FreeCell::setNoObject):
+ (JSC::MarkedBlock::setDestructorState):
+ (JSC::MarkedBlock::destructorState):
+ (JSC::MarkedBlock::notifyMayHaveFreshFreeCells):
+ * runtime/JSCell.cpp:
+ * runtime/JSCell.h:
+ (JSC::JSCell::JSCell::JSCell):
+ * runtime/JSGlobalData.cpp:
+ (JSC::JSGlobalData::JSGlobalData):
+ (JSC::JSGlobalData::clearBuiltinStructures):
+ * runtime/JSGlobalData.h:
+ * runtime/Structure.h:
+
2011-08-01 Michael Saboff <msab...@apple.com>
Virtual copying of FastMalloc allocated memory causes madvise MADV_FREE_REUSABLE errors
Modified: trunk/Source/_javascript_Core/heap/Heap.cpp (92232 => 92233)
--- trunk/Source/_javascript_Core/heap/Heap.cpp 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/heap/Heap.cpp 2011-08-02 21:22:34 UTC (rev 92233)
@@ -108,6 +108,7 @@
inline void ClearMarks::operator()(MarkedBlock* block)
{
block->clearMarks();
+ block->notifyMayHaveFreshFreeCells();
}
struct Sweep : MarkedBlock::VoidFunctor {
Modified: trunk/Source/_javascript_Core/heap/MarkedBlock.cpp (92232 => 92233)
--- trunk/Source/_javascript_Core/heap/MarkedBlock.cpp 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/heap/MarkedBlock.cpp 2011-08-02 21:22:34 UTC (rev 92233)
@@ -57,29 +57,85 @@
{
m_atomsPerCell = (cellSize + atomSize - 1) / atomSize;
m_endAtom = atomsPerBlock - m_atomsPerCell + 1;
+ setDestructorState(SomeFreeCellsStillHaveObjects);
}
-void MarkedBlock::reset()
+template<MarkedBlock::DestructorState specializedDestructorState>
+void MarkedBlock::callDestructor(JSCell* cell, void* jsFinalObjectVPtr)
{
+ if (specializedDestructorState == FreeCellsDontHaveObjects)
+ return;
+ void* vptr = cell->vptr();
+ if (specializedDestructorState == AllFreeCellsHaveObjects || vptr) {
+ if (vptr == jsFinalObjectVPtr) {
+ JSFinalObject* object = reinterpret_cast<JSFinalObject*>(cell);
+ object->JSFinalObject::~JSFinalObject();
+ } else
+ cell->~JSCell();
+ }
+}
+
+template<MarkedBlock::DestructorState specializedDestructorState>
+void MarkedBlock::specializedReset()
+{
+ void* jsFinalObjectVPtr = m_heap->globalData()->jsFinalObjectVPtr;
+
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
- reinterpret_cast<JSCell*>(&atoms()[i])->~JSCell();
+ callDestructor<specializedDestructorState>(reinterpret_cast<JSCell*>(&atoms()[i]), jsFinalObjectVPtr);
}
-void MarkedBlock::sweep()
+void MarkedBlock::reset()
{
- Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
+ switch (destructorState()) {
+ case FreeCellsDontHaveObjects:
+ case SomeFreeCellsStillHaveObjects:
+ specializedReset<SomeFreeCellsStillHaveObjects>();
+ break;
+ default:
+ ASSERT(destructorState() == AllFreeCellsHaveObjects);
+ specializedReset<AllFreeCellsHaveObjects>();
+ break;
+ }
+}
- for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
- if (m_marks.get(i))
- continue;
+template<MarkedBlock::DestructorState specializedDestructorState>
+void MarkedBlock::specializedSweep()
+{
+ if (specializedDestructorState != FreeCellsDontHaveObjects) {
+ void* jsFinalObjectVPtr = m_heap->globalData()->jsFinalObjectVPtr;
+
+ for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
+ if (m_marks.get(i))
+ continue;
+
+ JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
+ callDestructor<specializedDestructorState>(cell, jsFinalObjectVPtr);
+ cell->setVPtr(0);
+ }
+
+ setDestructorState(FreeCellsDontHaveObjects);
+ }
+}
- JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
- cell->~JSCell();
- new (cell) JSCell(*m_heap->globalData(), dummyMarkableCellStructure);
+void MarkedBlock::sweep()
+{
+ HEAP_DEBUG_BLOCK(this);
+
+ switch (destructorState()) {
+ case FreeCellsDontHaveObjects:
+ break;
+ case SomeFreeCellsStillHaveObjects:
+ specializedSweep<SomeFreeCellsStillHaveObjects>();
+ break;
+ default:
+ ASSERT(destructorState() == AllFreeCellsHaveObjects);
+ specializedSweep<AllFreeCellsHaveObjects>();
+ break;
}
}
-MarkedBlock::FreeCell* MarkedBlock::lazySweep()
+template<MarkedBlock::DestructorState specializedDestructorState>
+ALWAYS_INLINE MarkedBlock::FreeCell* MarkedBlock::produceFreeList()
{
// This returns a free list that is ordered in reverse through the block.
// This is fine, since the allocation code makes no assumptions about the
@@ -92,25 +148,49 @@
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
if (!m_marks.testAndSet(i)) {
JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
- if (cell->vptr() == jsFinalObjectVPtr) {
- JSFinalObject* object = reinterpret_cast<JSFinalObject*>(cell);
- object->JSFinalObject::~JSFinalObject();
- } else
- cell->~JSCell();
+ if (specializedDestructorState != FreeCellsDontHaveObjects)
+ callDestructor<specializedDestructorState>(cell, jsFinalObjectVPtr);
FreeCell* freeCell = reinterpret_cast<FreeCell*>(cell);
freeCell->next = result;
result = freeCell;
}
}
+ // This is sneaky: if we're producing a free list then we intend to
+ // fill up the free cells in the block with objects, which means that
+ // if we have a new GC then all of the free stuff in this block will
+ // comprise objects rather than empty cells.
+ setDestructorState(AllFreeCellsHaveObjects);
+
return result;
}
+MarkedBlock::FreeCell* MarkedBlock::lazySweep()
+{
+ // This returns a free list that is ordered in reverse through the block.
+ // This is fine, since the allocation code makes no assumptions about the
+ // order of the free list.
+
+ HEAP_DEBUG_BLOCK(this);
+
+ switch (destructorState()) {
+ case FreeCellsDontHaveObjects:
+ return produceFreeList<FreeCellsDontHaveObjects>();
+ case SomeFreeCellsStillHaveObjects:
+ return produceFreeList<SomeFreeCellsStillHaveObjects>();
+ default:
+ ASSERT(destructorState() == AllFreeCellsHaveObjects);
+ return produceFreeList<AllFreeCellsHaveObjects>();
+ }
+}
+
MarkedBlock::FreeCell* MarkedBlock::blessNewBlockForFastPath()
{
// This returns a free list that is ordered in reverse through the block,
// as in lazySweep() above.
+ HEAP_DEBUG_BLOCK(this);
+
FreeCell* result = 0;
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
m_marks.set(i);
@@ -118,28 +198,45 @@
freeCell->next = result;
result = freeCell;
}
+
+ // See produceFreeList(). If we're here then we intend to fill the
+ // block with objects, so once a GC happens, all free cells will be
+ // occupied by objects.
+ setDestructorState(AllFreeCellsHaveObjects);
+
return result;
}
void MarkedBlock::blessNewBlockForSlowPath()
{
- Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
+ HEAP_DEBUG_BLOCK(this);
+
+ m_marks.clearAll();
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
- new (&atoms()[i]) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);
+ reinterpret_cast<FreeCell*>(&atoms()[i])->setNoObject();
+
+ setDestructorState(FreeCellsDontHaveObjects);
}
void MarkedBlock::canonicalizeBlock(FreeCell* firstFreeCell)
{
- Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
+ HEAP_DEBUG_BLOCK(this);
- for (FreeCell* current = firstFreeCell; current;) {
- FreeCell* next = current->next;
- size_t i = atomNumber(current);
+ ASSERT(destructorState() == AllFreeCellsHaveObjects);
+
+ if (firstFreeCell) {
+ for (FreeCell* current = firstFreeCell; current;) {
+ FreeCell* next = current->next;
+ size_t i = atomNumber(current);
+
+ m_marks.clear(i);
+
+ current->setNoObject();
+
+ current = next;
+ }
- m_marks.clear(i);
- new (static_cast<void*>(current)) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);
-
- current = next;
+ setDestructorState(SomeFreeCellsStillHaveObjects);
}
}
Modified: trunk/Source/_javascript_Core/heap/MarkedBlock.h (92232 => 92233)
--- trunk/Source/_javascript_Core/heap/MarkedBlock.h 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/heap/MarkedBlock.h 2011-08-02 21:22:34 UTC (rev 92233)
@@ -28,8 +28,20 @@
#include <wtf/PageAllocationAligned.h>
#include <wtf/StdLibExtras.h>
+// Set to log state transitions of blocks.
+#define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
+
+#if HEAP_LOG_BLOCK_STATE_TRANSITIONS
+#define HEAP_DEBUG_BLOCK(block) do { \
+ printf("%s:%d %s: block %s = %p\n", \
+ __FILE__, __LINE__, __FUNCTION__, #block, (block)); \
+ } while (false)
+#else
+#define HEAP_DEBUG_BLOCK(block) ((void)0)
+#endif
+
namespace JSC {
-
+
class Heap;
class JSCell;
@@ -37,7 +49,13 @@
static const size_t KB = 1024;
- void destructor(JSCell*); // Defined in JSCell.h.
+ // A marked block is a page-aligned container for heap-allocated objects.
+ // Objects are allocated within cells of the marked block. For a given
+ // marked block, all cells have the same size. Objects smaller than the
+ // cell size may be allocated in the marked block, in which case the
+ // allocation suffers from internal fragmentation: wasted space whose
+ // size is equal to the difference between the cell size and the object
+ // size.
class MarkedBlock : public DoublyLinkedListNode<MarkedBlock> {
friend class WTF::DoublyLinkedListNode<MarkedBlock>;
@@ -52,6 +70,13 @@
struct FreeCell {
FreeCell* next;
+
+ void setNoObject()
+ {
+ // This relies on FreeCell not having a vtable, and the next field
+ // falling exactly where a vtable would have been.
+ next = 0;
+ }
};
struct VoidFunctor {
@@ -96,6 +121,9 @@
// them, and returns a linked list of those cells.
FreeCell* lazySweep();
+ // Notify the block that destructors may have to be called again.
+ void notifyMayHaveFreshFreeCells();
+
void initForCellSize(size_t cellSize);
// These should be called immediately after a block is created.
@@ -132,6 +160,8 @@
private:
static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
static const size_t atomMask = ~(atomSize - 1); // atomSize must be a power of two.
+
+ enum DestructorState { FreeCellsDontHaveObjects, SomeFreeCellsStillHaveObjects, AllFreeCellsHaveObjects };
typedef char Atom[atomSize];
@@ -140,11 +170,34 @@
size_t atomNumber(const void*);
size_t ownerSetNumber(const JSCell*);
-
+
+ template<DestructorState destructorState>
+ static void callDestructor(JSCell*, void* jsFinalObjectVPtr);
+
+ template<DestructorState destructorState>
+ void specializedReset();
+
+ template<DestructorState destructorState>
+ void specializedSweep();
+
+ template<DestructorState destructorState>
+ MarkedBlock::FreeCell* produceFreeList();
+
+ void setDestructorState(DestructorState destructorState)
+ {
+ m_destructorState = static_cast<int8_t>(destructorState);
+ }
+
+ DestructorState destructorState()
+ {
+ return static_cast<DestructorState>(m_destructorState);
+ }
+
size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
size_t m_atomsPerCell;
WTF::Bitmap<blockSize / atomSize> m_marks;
bool m_inNewSpace;
+ int8_t m_destructorState; // use getters/setters for this, particularly since we may want to compact this (effectively log(3)/log(2)-bit) field into other fields
OwnerSet m_ownerSets[ownerSetsPerBlock];
PageAllocationAligned m_allocation;
Heap* m_heap;
@@ -186,6 +239,27 @@
{
m_inNewSpace = inNewSpace;
}
+
+ inline void MarkedBlock::notifyMayHaveFreshFreeCells()
+ {
+ HEAP_DEBUG_BLOCK(this);
+
+ // This is called at the beginning of GC. If this block is
+ // AllFreeCellsHaveObjects, then it means that we filled up
+ // the block in this collection. If it's in any other state,
+ // then this collection will potentially produce new free
+ // cells; new free cells always have objects. Hence if the
+ // state currently claims that there are no objects in free
+ // cells then we need to bump it over. Otherwise leave it be.
+ // This all crucially relies on the collector canonicalizing
+ // blocks before doing anything else, as canonicalizeBlocks
+ // will correctly set SomeFreeCellsStillHaveObjects for
+ // blocks that were only partially filled during this
+ // mutation cycle.
+
+ if (destructorState() == FreeCellsDontHaveObjects)
+ setDestructorState(SomeFreeCellsStillHaveObjects);
+ }
inline bool MarkedBlock::isEmpty()
{
Modified: trunk/Source/_javascript_Core/runtime/JSCell.cpp (92232 => 92233)
--- trunk/Source/_javascript_Core/runtime/JSCell.cpp 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/runtime/JSCell.cpp 2011-08-02 21:22:34 UTC (rev 92233)
@@ -30,8 +30,6 @@
namespace JSC {
-const ClassInfo JSCell::s_dummyCellInfo = { "DummyCell", 0, 0, 0 };
-
bool JSCell::getUInt32(uint32_t&) const
{
return false;
Modified: trunk/Source/_javascript_Core/runtime/JSCell.h (92232 => 92233)
--- trunk/Source/_javascript_Core/runtime/JSCell.h 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/runtime/JSCell.h 2011-08-02 21:22:34 UTC (rev 92233)
@@ -71,7 +71,6 @@
friend class Structure;
friend class StructureChain;
friend class RegExp;
- friend void destructor(JSCell*);
enum CreatingEarlyCellTag { CreatingEarlyCell };
@@ -83,11 +82,8 @@
JSCell(JSGlobalData&, Structure*);
JSCell(JSGlobalData&, Structure*, CreatingEarlyCellTag);
virtual ~JSCell();
- static const ClassInfo s_dummyCellInfo;
public:
- static Structure* createDummyStructure(JSGlobalData&);
-
// Querying the type.
bool isString() const;
bool isObject() const;
@@ -180,7 +176,7 @@
#endif
m_structure.setEarlyValue(globalData, this, structure);
// Very first set of allocations won't have a real structure.
- ASSERT(m_structure || !globalData.dummyMarkableCellStructure);
+ ASSERT(m_structure || !globalData.structureStructure);
}
inline JSCell::~JSCell()
@@ -350,11 +346,6 @@
return isCell() ? asCell()->toThisObject(exec) : toThisObjectSlowCase(exec);
}
- inline void destructor(JSCell* cell)
- {
- cell->~JSCell();
- }
-
template <typename T> void* allocateCell(Heap& heap)
{
return heap.allocate(sizeof(T));
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalData.cpp (92232 => 92233)
--- trunk/Source/_javascript_Core/runtime/JSGlobalData.cpp 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalData.cpp 2011-08-02 21:22:34 UTC (rev 92233)
@@ -227,7 +227,6 @@
evalExecutableStructure.set(*this, EvalExecutable::createStructure(*this, jsNull()));
programExecutableStructure.set(*this, ProgramExecutable::createStructure(*this, jsNull()));
functionExecutableStructure.set(*this, FunctionExecutable::createStructure(*this, jsNull()));
- dummyMarkableCellStructure.set(*this, JSCell::createDummyStructure(*this));
regExpStructure.set(*this, RegExp::createStructure(*this, jsNull()));
structureChainStructure.set(*this, StructureChain::createStructure(*this, jsNull()));
@@ -286,7 +285,6 @@
evalExecutableStructure.clear();
programExecutableStructure.clear();
functionExecutableStructure.clear();
- dummyMarkableCellStructure.clear();
regExpStructure.clear();
structureChainStructure.clear();
}
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalData.h (92232 => 92233)
--- trunk/Source/_javascript_Core/runtime/JSGlobalData.h 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalData.h 2011-08-02 21:22:34 UTC (rev 92233)
@@ -173,7 +173,6 @@
Strong<Structure> evalExecutableStructure;
Strong<Structure> programExecutableStructure;
Strong<Structure> functionExecutableStructure;
- Strong<Structure> dummyMarkableCellStructure;
Strong<Structure> regExpStructure;
Strong<Structure> structureChainStructure;
Modified: trunk/Source/_javascript_Core/runtime/Structure.h (92232 => 92233)
--- trunk/Source/_javascript_Core/runtime/Structure.h 2011-08-02 21:22:22 UTC (rev 92232)
+++ trunk/Source/_javascript_Core/runtime/Structure.h 2011-08-02 21:22:34 UTC (rev 92233)
@@ -284,11 +284,6 @@
#endif
}
- inline Structure* JSCell::createDummyStructure(JSGlobalData& globalData)
- {
- return Structure::create(globalData, jsNull(), TypeInfo(UnspecifiedType), AnonymousSlotCount, &s_dummyCellInfo);
- }
-
ALWAYS_INLINE void MarkStack::internalAppend(JSCell* cell)
{
ASSERT(!m_isCheckingForDefaultMarkViolation);
