Changeset 219897 in webkit


Ignore:
Timestamp:
Jul 25, 2017, 6:19:23 PM (8 years ago)
Author:
fpizlo@apple.com
Message:

GC should be fine with trading blocks between destructor and non-destructor blocks
​https://bugs.webkit.org/show_bug.cgi?id=174811

Reviewed by Mark Lam.

Our GC has the ability to trade blocks between MarkedAllocators. A MarkedAllocator is a
size-class-within-a-Subspace. The ability to trade helps reduce memory wastage due to
fragmentation. Prior to this change, this only worked between blocks that did not have destructors.
This was partly a policy decision. But mostly, it was fallout from the way we use the empty block
set.

Here's how empty used to work. If a block is empty, we don't run destructors. We say that a block
is empty if:

A) It has no live objects and its a non-destructor block, or
B) We just allocated it (so it has no destructors even if it's a destructor block), or
C) We just stole it from another allocator (so it also has no destructors), or
D) We just swept the block and ran all destructors.

Case (A) is for trading blocks. That's how a different MarkedAllocator would know that this is a
block that could be stolen.

Cases (B) and (C) need to be detected for correctness, since otherwise we might try to run
destructors in blocks that have garbage bits. In that case, the isZapped check won't detect that
cells don't need destruction, so without having the empty bit we would try to destruct garbage
and crash. Currently, we know that we have cases (B) and (C) when the block is empty.

Case (D) is necessary for detecting which blocks can be removed when we shrink the heap.

If we tried to enable trading of blocks between allocators without making any changes to how
empty works, then it just would not work. We have to set the empty bits of blocks that have no
live objects in order for those bits to be candidates for trading. But if we do that, then our
logic for cases (B-D) will think that the block has no destructible objects. That's bad, since then
our destructors won't run and we'll leak memory.

This change fixes this issue by decoupling the "do I have destructors" question from the "do I have
live objects" question by introducing a new destructible bitvector. The GC flags all live blocks
as being destructible at the end. We clear the destructible bit in cases (B-D). Cases (B-C) are
handled entirely by the new destrictible bit, while case (D) is detected by looking for blocks that
are (empty & ~destructible).

Then we can simply remove all destructor-oriented special-casing of the empty bit. And we can
remove destructor-oriented special-casing of block trading.

This is a perf-neutral change. We expect most free memory to be in non-destructor blocks anyway,
so this change is more about clean-up than perf. But, this could reduce memory usage in some
pathological cases.

  • heap/MarkedAllocator.cpp:

(JSC::MarkedAllocator::findEmptyBlockToSteal):
(JSC::MarkedAllocator::tryAllocateWithoutCollecting):
(JSC::MarkedAllocator::endMarking):
(JSC::MarkedAllocator::shrink):
(JSC::MarkedAllocator::shouldStealEmptyBlocksFromOtherAllocators): Deleted.

  • heap/MarkedAllocator.h:
  • heap/MarkedBlock.cpp:

(JSC::MarkedBlock::Handle::lastChanceToFinalize):
(JSC::MarkedBlock::Handle::sweep):

  • heap/MarkedBlockInlines.h:

(JSC::MarkedBlock::Handle::specializedSweep):
(JSC::MarkedBlock::Handle::finishSweepKnowingSubspace):
(JSC::MarkedBlock::Handle::emptyMode):

Location:
trunk/Source/JavaScriptCore
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r219895 r219897  
     12017-07-24  Filip Pizlo  <fpizlo@apple.com>
     2
     3        GC should be fine with trading blocks between destructor and non-destructor blocks
     4        https://bugs.webkit.org/show_bug.cgi?id=174811
     5
     6        Reviewed by Mark Lam.
     7       
     8        Our GC has the ability to trade blocks between MarkedAllocators. A MarkedAllocator is a
     9        size-class-within-a-Subspace. The ability to trade helps reduce memory wastage due to
     10        fragmentation. Prior to this change, this only worked between blocks that did not have destructors.
     11        This was partly a policy decision. But mostly, it was fallout from the way we use the `empty` block
     12        set.
     13       
     14        Here's how `empty` used to work. If a block is empty, we don't run destructors. We say that a block
     15        is empty if:
     16       
     17        A) It has no live objects and its a non-destructor block, or
     18        B) We just allocated it (so it has no destructors even if it's a destructor block), or
     19        C) We just stole it from another allocator (so it also has no destructors), or
     20        D) We just swept the block and ran all destructors.
     21       
     22        Case (A) is for trading blocks. That's how a different MarkedAllocator would know that this is a
     23        block that could be stolen.
     24
     25        Cases (B) and (C) need to be detected for correctness, since otherwise we might try to run
     26        destructors in blocks that have garbage bits. In that case, the isZapped check won't detect that
     27        cells don't need destruction, so without having the `empty` bit we would try to destruct garbage
     28        and crash. Currently, we know that we have cases (B) and (C) when the block is empty.
     29       
     30        Case (D) is necessary for detecting which blocks can be removed when we `shrink` the heap.
     31       
     32        If we tried to enable trading of blocks between allocators without making any changes to how
     33        `empty` works, then it just would not work. We have to set the `empty` bits of blocks that have no
     34        live objects in order for those bits to be candidates for trading. But if we do that, then our
     35        logic for cases (B-D) will think that the block has no destructible objects. That's bad, since then
     36        our destructors won't run and we'll leak memory.
     37       
     38        This change fixes this issue by decoupling the "do I have destructors" question from the "do I have
     39        live objects" question by introducing a new `destructible` bitvector. The GC flags all live blocks
     40        as being destructible at the end. We clear the destructible bit in cases (B-D). Cases (B-C) are
     41        handled entirely by the new destrictible bit, while case (D) is detected by looking for blocks that
     42        are (empty & ~destructible).
     43       
     44        Then we can simply remove all destructor-oriented special-casing of the `empty` bit. And we can
     45        remove destructor-oriented special-casing of block trading.
     46
     47        This is a perf-neutral change. We expect most free memory to be in non-destructor blocks anyway,
     48        so this change is more about clean-up than perf. But, this could reduce memory usage in some
     49        pathological cases.
     50       
     51        * heap/MarkedAllocator.cpp:
     52        (JSC::MarkedAllocator::findEmptyBlockToSteal):
     53        (JSC::MarkedAllocator::tryAllocateWithoutCollecting):
     54        (JSC::MarkedAllocator::endMarking):
     55        (JSC::MarkedAllocator::shrink):
     56        (JSC::MarkedAllocator::shouldStealEmptyBlocksFromOtherAllocators): Deleted.
     57        * heap/MarkedAllocator.h:
     58        * heap/MarkedBlock.cpp:
     59        (JSC::MarkedBlock::Handle::lastChanceToFinalize):
     60        (JSC::MarkedBlock::Handle::sweep):
     61        * heap/MarkedBlockInlines.h:
     62        (JSC::MarkedBlock::Handle::specializedSweep):
     63        (JSC::MarkedBlock::Handle::finishSweepKnowingSubspace):
     64        (JSC::MarkedBlock::Handle::emptyMode):
     65
    1662017-07-25  Keith Miller  <keith_miller@apple.com>
    267

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

    r217711 r219897  
    6868}
    6969
    70 bool MarkedAllocator::shouldStealEmptyBlocksFromOtherAllocators() const
    71 {
    72     return !needsDestruction();
    73 }
    74 
    7570MarkedBlock::Handle* MarkedAllocator::findEmptyBlockToSteal()
    7671{
    77     // Don't allow others to steal from us, if we wouldn't steal from others.
    78     if (!shouldStealEmptyBlocksFromOtherAllocators())
    79         return nullptr;
    80    
    8172    m_emptyCursor = m_empty.findBit(m_emptyCursor, true);
    8273    if (m_emptyCursor >= m_blocks.size())
    … …  
    112103    }
    113104   
    114     if (Options::stealEmptyBlocksFromOtherAllocators()
    115         && shouldStealEmptyBlocksFromOtherAllocators()) {
     105    if (Options::stealEmptyBlocksFromOtherAllocators()) {
    116106        if (MarkedBlock::Handle* block = markedSpace().findEmptyBlockToSteal()) {
    117107            block->sweep(nullptr);
    … …  
    390380    // vectors.
    391381   
    392     if (needsDestruction()) {
    393         // If blocks need destruction then nothing is empty! This is a correct assertion but may
    394         // become wrong once we go full concurrent: when we create a new block, it will flicker
    395         // into the empty set for a tiny moment. On the other hand, this code is likely to be run
    396         // in stopTheWorld.
    397         ASSERT(m_empty.isEmpty());
    398         m_canAllocateButNotEmpty = m_live & ~m_markingRetired;
    399         return;
    400     }
    401    
    402382    m_empty = m_live & ~m_markingNotEmpty;
    403383    m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
     384    if (needsDestruction()) {
     385        // There are some blocks that we didn't allocate out of in the last cycle, but we swept them. This
     386        // will forget that we did that and we will end up sweeping them again and attempting to call their
     387        // destructors again. That's fine because of zapping. The only time when we cannot forget is when
     388        // we just allocate a block or when we move a block from one size class to another. That doesn't
     389        // happen here.
     390        m_destructible = m_live;
     391    }
    404392   
    405393    if (false) {
    … …  
    438426void MarkedAllocator::shrink()
    439427{
    440     m_empty.forEachSetBit(
     428    (m_empty & ~m_destructible).forEachSetBit(
    441429        [&] (size_t index) {
    442430            markedSpace().freeBlock(m_blocks[index]);

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

    r218794 r219897  
    4242#define FOR_EACH_MARKED_ALLOCATOR_BIT(macro) \
    4343    macro(live, Live) /* The set of block indices that have actual blocks. */\
    44     macro(empty, Empty) /* The set of all blocks that have no live objects and nothing to destroy. */ \
     44    macro(empty, Empty) /* The set of all blocks that have no live objects. */ \
    4545    macro(allocated, Allocated) /* The set of all blocks that are full of live objects. */\
    4646    macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
     47    macro(destructible, Destructible) /* The set of all blocks that may have destructors to run. */\
    4748    macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
    4849    macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
    … …  
    6566// has to look at both bitvectors.
    6667// https://bugs.webkit.org/show_bug.cgi?id=162121
    67 
    68 // Note that this collector supports overlapping allocator state with marking state, since in a
    69 // concurrent collector you allow allocation while marking is running. So it's best to visualize a
    70 // full mutable->eden collect->mutate->full collect cycle and see how the bits above get affected.
    71 // The example below tries to be exhaustive about what happens to the bits, but omits a lot of
    72 // things that happen to other state.
    73 //
    74 // Create allocator
    75 // - all bits are empty
    76 // Start allocating in some block
    77 // - allocate the block and set the live bit.
    78 // - the empty bit for the block flickers on and then gets immediately cleared by sweeping.
    79 // - set the eden bit.
    80 // Finish allocating in that block
    81 // - set the allocated bit.
    82 // Do that to a lot of blocks and then start an eden collection.
    83 // - beginMarking() has nothing to do.
    84 // - by default we have cleared markingNotEmpty/markingRetired bits.
    85 // - marking builds up markingNotEmpty/markingRetired bits.
    86 // We do endMarking()
    87 // - clear all allocated bits.
    88 // - for destructor blocks: fragmented = live & ~markingRetired
    89 // - for non-destructor blocks:
    90 //       empty = live & ~markingNotEmpty
    91 //       fragmented = live & markingNotEmpty & ~markingRetired
    92 // Snapshotting.
    93 // - unswept |= eden
    94 // Prepare for allocation.
    95 // - clear eden
    96 // Finish collection.
    97 // Allocate in some block that had some free and some live objects.
    98 // - clear the canAllocateButNotEmpty bit
    99 // - clear the unswept bit
    100 // - set the eden bit
    101 // Finish allocating (set the allocated bit).
    102 // Allocate in some block that was completely empty.
    103 // - clear the empty bit
    104 // - clear the unswept bit
    105 // - set the eden bit.
    106 // Finish allocating (set the allocated bit).
    107 // Allocate in some block that was completely empty in another allocator.
    108 // - clear the empty bit
    109 // - clear all bits in that allocator
    110 // - set the live bit in another allocator and the empty bit.
    111 // - clear the empty, unswept bits.
    112 // - set the eden bit.
    113 // Finish allocating (set the allocated bit).
    114 // Start a full collection.
    115 // - beginMarking() clears markingNotEmpty, markingRetired
    116 // - the heap version is incremented
    117 // - marking rebuilds markingNotEmpty/markingretired bits.
    118 // We do endMarking()
    119 // - clear all allocated bits.
    120 // - set canAllocateButNotEmpty/empty the same way as in eden collection.
    121 // Snapshotting.
    122 // - unswept = live
    123 // prepare for allocation.
    124 // - clear eden.
    125 // Finish collection.
    126 //
    127 // Notice how in this scheme, the empty/canAllocateButNotEmpty state stays separate from the
    128 // markingNotEmpty/markingRetired state. This is one step towards having separated allocation and
    129 // marking state.
    13068
    13169class MarkedAllocator {
    … …  
    218156    friend class MarkedBlock;
    219157   
    220     bool shouldStealEmptyBlocksFromOtherAllocators() const;
    221    
    222158    JS_EXPORT_PRIVATE void* allocateSlowCase(GCDeferralContext*);
    223159    JS_EXPORT_PRIVATE void* tryAllocateSlowCase(GCDeferralContext*);

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

    r218794 r219897  
    153153{
    154154    allocator()->setIsAllocated(NoLockingNecessary, this, false);
     155    allocator()->setIsDestructible(NoLockingNecessary, this, true);
    155156    m_block->m_marks.clearAll();
    156157    m_block->clearHasAnyMarked();
    … …  
    404405   
    405406    m_weakSet.sweep();
    406 
    407     if (sweepMode == SweepOnly && m_attributes.destruction == DoesNotNeedDestruction)
     407   
     408    bool needsDestruction = m_attributes.destruction == NeedsDestruction
     409        && m_allocator->isDestructible(NoLockingNecessary, this);
     410
     411    if (sweepMode == SweepOnly && !needsDestruction)
    408412        return;
    409413
    … …  
    418422        block().m_lock.lock();
    419423   
    420     if (m_attributes.destruction == NeedsDestruction) {
     424    if (needsDestruction) {
    421425        subspace()->finishSweep(*this, freeList);
    422426        return;

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

    r217711 r219897  
    162162    unsigned cellSize = this->cellSize();
    163163   
     164    VM& vm = *this->vm();
     165    auto destroy = [&] (void* cell) {
     166        JSCell* jsCell = static_cast<JSCell*>(cell);
     167        if (!jsCell->isZapped()) {
     168            destroyFunc(vm, jsCell);
     169            jsCell->zap();
     170        }
     171    };
     172   
     173    m_allocator->setIsDestructible(NoLockingNecessary, this, false);
     174   
    164175    if (Options::useBumpAllocator()
    165176        && emptyMode == IsEmpty
    … …  
    182193        RELEASE_ASSERT(payloadEnd - MarkedBlock::blockSize <= bitwise_cast<char*>(&block));
    183194        char* payloadBegin = bitwise_cast<char*>(block.atoms() + firstAtom());
     195       
     196        if (sweepMode == SweepToFreeList)
     197            setIsFreeListed();
     198        if (space()->isMarking())
     199            block.m_lock.unlock();
     200        if (destructionMode != BlockHasNoDestructors) {
     201            for (char* cell = payloadBegin; cell < payloadEnd; cell += cellSize)
     202                destroy(cell);
     203        }
    184204        if (scribbleMode == Scribble)
    185205            scribble(payloadBegin, payloadEnd - payloadBegin);
    186         if (sweepMode == SweepToFreeList)
    187             setIsFreeListed();
    188         else
    189             m_allocator->setIsEmpty(NoLockingNecessary, this, true);
    190         if (space()->isMarking())
    191             block.m_lock.unlock();
    192206        if (sweepMode == SweepToFreeList)
    193207            freeList->initializeBump(payloadEnd, payloadEnd - payloadBegin);
    … …  
    206220    bool isEmpty = true;
    207221    Vector<size_t> deadCells;
    208     VM& vm = *this->vm();
    209222    auto handleDeadCell = [&] (size_t i) {
    210223        HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&block.atoms()[i]);
    211224
    212         if (destructionMode != BlockHasNoDestructors && emptyMode == NotEmpty) {
    213             JSCell* jsCell = static_cast<JSCell*>(cell);
    214             if (!jsCell->isZapped()) {
    215                 destroyFunc(vm, jsCell);
    216                 jsCell->zap();
    217             }
    218         }
     225        if (destructionMode != BlockHasNoDestructors && emptyMode == NotEmpty)
     226            destroy(cell);
    219227
    220228        if (sweepMode == SweepToFreeList) {
    … …  
    274282
    275283    auto trySpecialized = [&] () -> bool {
    276         if (sweepMode != SweepToFreeList)
    277             return false;
    278284        if (scribbleMode != DontScribble)
    279285            return false;
    … …  
    282288        if (destructionMode != BlockHasDestructors)
    283289            return false;
    284         if (emptyMode == IsEmpty)
    285             return false;
    286        
    287         switch (marksMode) {
    288         case MarksNotStale:
    289             specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
    290             return true;
    291         case MarksStale:
    292             specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
    293             return true;
     290       
     291        switch (emptyMode) {
     292        case IsEmpty:
     293            switch (sweepMode) {
     294            case SweepOnly:
     295                switch (marksMode) {
     296                case MarksNotStale:
     297                    specializedSweep<true, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
     298                    return true;
     299                case MarksStale:
     300                    specializedSweep<true, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
     301                    return true;
     302                }
     303            case SweepToFreeList:
     304                switch (marksMode) {
     305                case MarksNotStale:
     306                    specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
     307                    return true;
     308                case MarksStale:
     309                    specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
     310                    return true;
     311                }
     312            }
     313        case NotEmpty:
     314            switch (sweepMode) {
     315            case SweepOnly:
     316                switch (marksMode) {
     317                case MarksNotStale:
     318                    specializedSweep<true, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
     319                    return true;
     320                case MarksStale:
     321                    specializedSweep<true, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
     322                    return true;
     323                }
     324            case SweepToFreeList:
     325                switch (marksMode) {
     326                case MarksNotStale:
     327                    specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
     328                    return true;
     329                case MarksStale:
     330                    specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
     331                    return true;
     332                }
     333            }
    294334        }
    295335       
    … …  
    321361    // - It's true if the block had been swept in the past, all destructors were called, and that
    322362    //   sweep proved that the block is empty.
    323     // - It's false if there are any destructors that need to be called, even if the block has no
    324     //   live objects.
    325363    return m_allocator->isEmpty(NoLockingNecessary, this) ? IsEmpty : NotEmpty;
    326364}
Note: See TracChangeset for help on using the changeset viewer.