Changeset 92233 in webkit


Ignore:
Timestamp:
Aug 2, 2011 2:22:34 PM (13 years ago)
Author:
fpizlo@apple.com
Message:

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:
Location:
trunk/Source/JavaScriptCore
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r92231 r92233  
     12011-08-02  Filip Pizlo  <fpizlo@apple.com>
     2
     3        JSC GC uses dummy cells to avoid having to remember which cells
     4        it has already destroyed
     5        https://bugs.webkit.org/show_bug.cgi?id=65556
     6
     7        Reviewed by Oliver Hunt.
     8       
     9        This gets rid of dummy cells, and ensures that it's not necessary
     10        to invoke a destructor on cells that have already been swept.  In
     11        the common case, a block knows that either all of its free cells
     12        still need to have destructors called, or none of them do, which
     13        minimizes the amount of branching that needs to happen per cell
     14        when performing a sweep.
     15       
     16        This is performance neutral on SunSpider and V8.  It is meant as
     17        a stepping stone to simplify the implementation of more
     18        sophisticated sweeping algorithms.
     19
     20        * heap/Heap.cpp:
     21        (JSC::CountFunctor::ClearMarks::operator()):
     22        * heap/MarkedBlock.cpp:
     23        (JSC::MarkedBlock::initForCellSize):
     24        (JSC::MarkedBlock::callDestructor):
     25        (JSC::MarkedBlock::specializedReset):
     26        (JSC::MarkedBlock::reset):
     27        (JSC::MarkedBlock::specializedSweep):
     28        (JSC::MarkedBlock::sweep):
     29        (JSC::MarkedBlock::produceFreeList):
     30        (JSC::MarkedBlock::lazySweep):
     31        (JSC::MarkedBlock::blessNewBlockForFastPath):
     32        (JSC::MarkedBlock::blessNewBlockForSlowPath):
     33        (JSC::MarkedBlock::canonicalizeBlock):
     34        * heap/MarkedBlock.h:
     35        (JSC::MarkedBlock::FreeCell::setNoObject):
     36        (JSC::MarkedBlock::setDestructorState):
     37        (JSC::MarkedBlock::destructorState):
     38        (JSC::MarkedBlock::notifyMayHaveFreshFreeCells):
     39        * runtime/JSCell.cpp:
     40        * runtime/JSCell.h:
     41        (JSC::JSCell::JSCell::JSCell):
     42        * runtime/JSGlobalData.cpp:
     43        (JSC::JSGlobalData::JSGlobalData):
     44        (JSC::JSGlobalData::clearBuiltinStructures):
     45        * runtime/JSGlobalData.h:
     46        * runtime/Structure.h:
     47
    1482011-08-01  Michael Saboff  <msaboff@apple.com>
    249

  • trunk/Source/JavaScriptCore/heap/Heap.cpp

    r92224 r92233  
    109109{
    110110    block->clearMarks();
     111    block->notifyMayHaveFreshFreeCells();
    111112}
    112113

  • trunk/Source/JavaScriptCore/heap/MarkedBlock.cpp

    r92084 r92233  
    5858    m_atomsPerCell = (cellSize + atomSize - 1) / atomSize;
    5959    m_endAtom = atomsPerBlock - m_atomsPerCell + 1;
     60    setDestructorState(SomeFreeCellsStillHaveObjects);
     61}
     62
     63template<MarkedBlock::DestructorState specializedDestructorState>
     64void MarkedBlock::callDestructor(JSCell* cell, void* jsFinalObjectVPtr)
     65{
     66    if (specializedDestructorState == FreeCellsDontHaveObjects)
     67        return;
     68    void* vptr = cell->vptr();
     69    if (specializedDestructorState == AllFreeCellsHaveObjects || vptr) {
     70        if (vptr == jsFinalObjectVPtr) {
     71            JSFinalObject* object = reinterpret_cast<JSFinalObject*>(cell);
     72            object->JSFinalObject::~JSFinalObject();
     73        } else
     74            cell->~JSCell();
     75    }
     76}
     77
     78template<MarkedBlock::DestructorState specializedDestructorState>
     79void MarkedBlock::specializedReset()
     80{
     81    void* jsFinalObjectVPtr = m_heap->globalData()->jsFinalObjectVPtr;
     82
     83    for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
     84        callDestructor<specializedDestructorState>(reinterpret_cast<JSCell*>(&atoms()[i]), jsFinalObjectVPtr);
    6085}
    6186
    6287void MarkedBlock::reset()
    6388{
    64     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
    65         reinterpret_cast<JSCell*>(&atoms()[i])->~JSCell();
     89    switch (destructorState()) {
     90    case FreeCellsDontHaveObjects:
     91    case SomeFreeCellsStillHaveObjects:
     92        specializedReset<SomeFreeCellsStillHaveObjects>();
     93        break;
     94    default:
     95        ASSERT(destructorState() == AllFreeCellsHaveObjects);
     96        specializedReset<AllFreeCellsHaveObjects>();
     97        break;
     98    }
     99}
     100
     101template<MarkedBlock::DestructorState specializedDestructorState>
     102void MarkedBlock::specializedSweep()
     103{
     104    if (specializedDestructorState != FreeCellsDontHaveObjects) {
     105        void* jsFinalObjectVPtr = m_heap->globalData()->jsFinalObjectVPtr;
     106       
     107        for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
     108            if (m_marks.get(i))
     109                continue;
     110           
     111            JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
     112            callDestructor<specializedDestructorState>(cell, jsFinalObjectVPtr);
     113            cell->setVPtr(0);
     114        }
     115       
     116        setDestructorState(FreeCellsDontHaveObjects);
     117    }
    66118}
    67119
    68120void MarkedBlock::sweep()
    69121{
    70     Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
    71 
    72     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
    73         if (m_marks.get(i))
    74             continue;
    75 
    76         JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
    77         cell->~JSCell();
    78         new (cell) JSCell(*m_heap->globalData(), dummyMarkableCellStructure);
    79     }
    80 }
    81 
    82 MarkedBlock::FreeCell* MarkedBlock::lazySweep()
     122    HEAP_DEBUG_BLOCK(this);
     123   
     124    switch (destructorState()) {
     125    case FreeCellsDontHaveObjects:
     126        break;
     127    case SomeFreeCellsStillHaveObjects:
     128        specializedSweep<SomeFreeCellsStillHaveObjects>();
     129        break;
     130    default:
     131        ASSERT(destructorState() == AllFreeCellsHaveObjects);
     132        specializedSweep<AllFreeCellsHaveObjects>();
     133        break;
     134    }
     135}
     136
     137template<MarkedBlock::DestructorState specializedDestructorState>
     138ALWAYS_INLINE MarkedBlock::FreeCell* MarkedBlock::produceFreeList()
    83139{
    84140    // This returns a free list that is ordered in reverse through the block.
    … …  
    93149        if (!m_marks.testAndSet(i)) {
    94150            JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
    95             if (cell->vptr() == jsFinalObjectVPtr) {
    96                 JSFinalObject* object = reinterpret_cast<JSFinalObject*>(cell);
    97                 object->JSFinalObject::~JSFinalObject();
    98             } else
    99                 cell->~JSCell();
     151            if (specializedDestructorState != FreeCellsDontHaveObjects)
     152                callDestructor<specializedDestructorState>(cell, jsFinalObjectVPtr);
    100153            FreeCell* freeCell = reinterpret_cast<FreeCell*>(cell);
    101154            freeCell->next = result;
    … …  
    104157    }
    105158   
     159    // This is sneaky: if we're producing a free list then we intend to
     160    // fill up the free cells in the block with objects, which means that
     161    // if we have a new GC then all of the free stuff in this block will
     162    // comprise objects rather than empty cells.
     163    setDestructorState(AllFreeCellsHaveObjects);
     164
    106165    return result;
     166}
     167
     168MarkedBlock::FreeCell* MarkedBlock::lazySweep()
     169{
     170    // This returns a free list that is ordered in reverse through the block.
     171    // This is fine, since the allocation code makes no assumptions about the
     172    // order of the free list.
     173   
     174    HEAP_DEBUG_BLOCK(this);
     175   
     176    switch (destructorState()) {
     177    case FreeCellsDontHaveObjects:
     178        return produceFreeList<FreeCellsDontHaveObjects>();
     179    case SomeFreeCellsStillHaveObjects:
     180        return produceFreeList<SomeFreeCellsStillHaveObjects>();
     181    default:
     182        ASSERT(destructorState() == AllFreeCellsHaveObjects);
     183        return produceFreeList<AllFreeCellsHaveObjects>();
     184    }
    107185}
    108186
    … …  
    112190    // as in lazySweep() above.
    113191   
     192    HEAP_DEBUG_BLOCK(this);
     193
    114194    FreeCell* result = 0;
    115195    for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
    … …  
    119199        result = freeCell;
    120200    }
     201   
     202    // See produceFreeList(). If we're here then we intend to fill the
     203    // block with objects, so once a GC happens, all free cells will be
     204    // occupied by objects.
     205    setDestructorState(AllFreeCellsHaveObjects);
     206
    121207    return result;
    122208}
    … …  
    124210void MarkedBlock::blessNewBlockForSlowPath()
    125211{
    126     Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
     212    HEAP_DEBUG_BLOCK(this);
     213
     214    m_marks.clearAll();
    127215    for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
    128         new (&atoms()[i]) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);
     216        reinterpret_cast<FreeCell*>(&atoms()[i])->setNoObject();
     217   
     218    setDestructorState(FreeCellsDontHaveObjects);
    129219}
    130220
    131221void MarkedBlock::canonicalizeBlock(FreeCell* firstFreeCell)
    132222{
    133     Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
    134    
    135     for (FreeCell* current = firstFreeCell; current;) {
    136         FreeCell* next = current->next;
    137         size_t i = atomNumber(current);
     223    HEAP_DEBUG_BLOCK(this);
     224   
     225    ASSERT(destructorState() == AllFreeCellsHaveObjects);
     226   
     227    if (firstFreeCell) {
     228        for (FreeCell* current = firstFreeCell; current;) {
     229            FreeCell* next = current->next;
     230            size_t i = atomNumber(current);
     231           
     232            m_marks.clear(i);
     233           
     234            current->setNoObject();
     235           
     236            current = next;
     237        }
    138238       
    139         m_marks.clear(i);
    140         new (static_cast<void*>(current)) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);
    141 
    142         current = next;
     239        setDestructorState(SomeFreeCellsStillHaveObjects);
    143240    }
    144241}

  • trunk/Source/JavaScriptCore/heap/MarkedBlock.h

    r92092 r92233  
    2929#include <wtf/StdLibExtras.h>
    3030
     31// Set to log state transitions of blocks.
     32#define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
     33
     34#if HEAP_LOG_BLOCK_STATE_TRANSITIONS
     35#define HEAP_DEBUG_BLOCK(block) do {                                    \
     36        printf("%s:%d %s: block %s = %p\n",                             \
     37               __FILE__, __LINE__, __FUNCTION__, #block, (block));      \
     38    } while (false)
     39#else
     40#define HEAP_DEBUG_BLOCK(block) ((void)0)
     41#endif
     42
    3143namespace JSC {
    32 
     44   
    3345    class Heap;
    3446    class JSCell;
    … …  
    3850    static const size_t KB = 1024;
    3951   
    40     void destructor(JSCell*); // Defined in JSCell.h.
     52    // A marked block is a page-aligned container for heap-allocated objects.
     53    // Objects are allocated within cells of the marked block. For a given
     54    // marked block, all cells have the same size. Objects smaller than the
     55    // cell size may be allocated in the marked block, in which case the
     56    // allocation suffers from internal fragmentation: wasted space whose
     57    // size is equal to the difference between the cell size and the object
     58    // size.
    4159
    4260    class MarkedBlock : public DoublyLinkedListNode<MarkedBlock> {
    … …  
    5371        struct FreeCell {
    5472            FreeCell* next;
     73           
     74            void setNoObject()
     75            {
     76                // This relies on FreeCell not having a vtable, and the next field
     77                // falling exactly where a vtable would have been.
     78                next = 0;
     79            }
    5580        };
    5681       
    … …  
    97122        FreeCell* lazySweep();
    98123       
     124        // Notify the block that destructors may have to be called again.
     125        void notifyMayHaveFreshFreeCells();
     126       
    99127        void initForCellSize(size_t cellSize);
    100128       
    … …  
    133161        static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
    134162        static const size_t atomMask = ~(atomSize - 1); // atomSize must be a power of two.
     163       
     164        enum DestructorState { FreeCellsDontHaveObjects, SomeFreeCellsStillHaveObjects, AllFreeCellsHaveObjects };
    135165
    136166        typedef char Atom[atomSize];
    … …  
    141171        size_t atomNumber(const void*);
    142172        size_t ownerSetNumber(const JSCell*);
    143 
     173       
     174        template<DestructorState destructorState>
     175        static void callDestructor(JSCell*, void* jsFinalObjectVPtr);
     176       
     177        template<DestructorState destructorState>
     178        void specializedReset();
     179       
     180        template<DestructorState destructorState>
     181        void specializedSweep();
     182       
     183        template<DestructorState destructorState>
     184        MarkedBlock::FreeCell* produceFreeList();
     185       
     186        void setDestructorState(DestructorState destructorState)
     187        {
     188            m_destructorState = static_cast<int8_t>(destructorState);
     189        }
     190       
     191        DestructorState destructorState()
     192        {
     193            return static_cast<DestructorState>(m_destructorState);
     194        }
     195       
    144196        size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
    145197        size_t m_atomsPerCell;
    146198        WTF::Bitmap<blockSize / atomSize> m_marks;
    147199        bool m_inNewSpace;
     200        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
    148201        OwnerSet m_ownerSets[ownerSetsPerBlock];
    149202        PageAllocationAligned m_allocation;
    … …  
    186239    {
    187240        m_inNewSpace = inNewSpace;
     241    }
     242   
     243    inline void MarkedBlock::notifyMayHaveFreshFreeCells()
     244    {
     245        HEAP_DEBUG_BLOCK(this);
     246       
     247        // This is called at the beginning of GC. If this block is
     248        // AllFreeCellsHaveObjects, then it means that we filled up
     249        // the block in this collection. If it's in any other state,
     250        // then this collection will potentially produce new free
     251        // cells; new free cells always have objects. Hence if the
     252        // state currently claims that there are no objects in free
     253        // cells then we need to bump it over. Otherwise leave it be.
     254        // This all crucially relies on the collector canonicalizing
     255        // blocks before doing anything else, as canonicalizeBlocks
     256        // will correctly set SomeFreeCellsStillHaveObjects for
     257        // blocks that were only partially filled during this
     258        // mutation cycle.
     259       
     260        if (destructorState() == FreeCellsDontHaveObjects)
     261            setDestructorState(SomeFreeCellsStillHaveObjects);
    188262    }
    189263

  • trunk/Source/JavaScriptCore/runtime/JSCell.cpp

    r92046 r92233  
    3030
    3131namespace JSC {
    32 
    33 const ClassInfo JSCell::s_dummyCellInfo = { "DummyCell", 0, 0, 0 };
    3432
    3533bool JSCell::getUInt32(uint32_t&) const

  • trunk/Source/JavaScriptCore/runtime/JSCell.h

    r92046 r92233  
    7272        friend class StructureChain;
    7373        friend class RegExp;
    74         friend void destructor(JSCell*);
    7574
    7675        enum CreatingEarlyCellTag { CreatingEarlyCell };
    … …  
    8483        JSCell(JSGlobalData&, Structure*, CreatingEarlyCellTag);
    8584        virtual ~JSCell();
    86         static const ClassInfo s_dummyCellInfo;
    8785
    8886    public:
    89         static Structure* createDummyStructure(JSGlobalData&);
    90 
    9187        // Querying the type.
    9288        bool isString() const;
    … …  
    181177            m_structure.setEarlyValue(globalData, this, structure);
    182178        // Very first set of allocations won't have a real structure.
    183         ASSERT(m_structure || !globalData.dummyMarkableCellStructure);
     179        ASSERT(m_structure || !globalData.structureStructure);
    184180    }
    185181
    … …  
    351347    }
    352348
    353     inline void destructor(JSCell* cell)
    354     {
    355         cell->~JSCell();
    356     }
    357 
    358349    template <typename T> void* allocateCell(Heap& heap)
    359350    {

  • trunk/Source/JavaScriptCore/runtime/JSGlobalData.cpp

    r92224 r92233  
    228228    programExecutableStructure.set(*this, ProgramExecutable::createStructure(*this, jsNull()));
    229229    functionExecutableStructure.set(*this, FunctionExecutable::createStructure(*this, jsNull()));
    230     dummyMarkableCellStructure.set(*this, JSCell::createDummyStructure(*this));
    231230    regExpStructure.set(*this, RegExp::createStructure(*this, jsNull()));
    232231    structureChainStructure.set(*this, StructureChain::createStructure(*this, jsNull()));
    … …  
    287286    programExecutableStructure.clear();
    288287    functionExecutableStructure.clear();
    289     dummyMarkableCellStructure.clear();
    290288    regExpStructure.clear();
    291289    structureChainStructure.clear();

  • trunk/Source/JavaScriptCore/runtime/JSGlobalData.h

    r92224 r92233  
    174174        Strong<Structure> programExecutableStructure;
    175175        Strong<Structure> functionExecutableStructure;
    176         Strong<Structure> dummyMarkableCellStructure;
    177176        Strong<Structure> regExpStructure;
    178177        Strong<Structure> structureChainStructure;

  • trunk/Source/JavaScriptCore/runtime/Structure.h

    r91194 r92233  
    285285    }
    286286
    287     inline Structure* JSCell::createDummyStructure(JSGlobalData& globalData)
    288     {
    289         return Structure::create(globalData, jsNull(), TypeInfo(UnspecifiedType), AnonymousSlotCount, &s_dummyCellInfo);
    290     }
    291 
    292287    ALWAYS_INLINE void MarkStack::internalAppend(JSCell* cell)
    293288    {
Note: See TracChangeset for help on using the changeset viewer.