Attachment 316351 Details for Bug 174811 – the patch

[patch] the patch

blah.patch (text/plain), 20.51 KB, created by Filip Pizlo on 2017-07-24 21:48:11 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2017-07-24 21:48:11 PDT

Size: 20.51 KB

patch

obsolete

>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 219858)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,66 @@
>+2017-07-24  Filip Pizlo  <fpizlo@apple.com>
>+
>+        GC should be fine with trading blocks between destructor and non-destructor blocks
>+        https://bugs.webkit.org/show_bug.cgi?id=174811
>+
>+        Reviewed by NOBODY (OOPS!).
>+        
>+        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).
>+        
>+        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):
>+
> 2017-07-24  Mark Lam  <mark.lam@apple.com>
> 
>         Gardening: fixed C Loop build after r219790.
>Index: Source/JavaScriptCore/heap/MarkedAllocator.cpp
>===================================================================
>--- Source/JavaScriptCore/heap/MarkedAllocator.cpp	(revision 219789)
>+++ Source/JavaScriptCore/heap/MarkedAllocator.cpp	(working copy)
>@@ -67,17 +67,8 @@ bool MarkedAllocator::isPagedOut(double 
>     return false;
> }
> 
>-bool MarkedAllocator::shouldStealEmptyBlocksFromOtherAllocators() const
>-{
>-    return !needsDestruction();
>-}
>-
> MarkedBlock::Handle* MarkedAllocator::findEmptyBlockToSteal()
> {
>-    // Don't allow others to steal from us, if we wouldn't steal from others.
>-    if (!shouldStealEmptyBlocksFromOtherAllocators())
>-        return nullptr;
>-    
>     m_emptyCursor = m_empty.findBit(m_emptyCursor, true);
>     if (m_emptyCursor >= m_blocks.size())
>         return nullptr;
>@@ -111,8 +102,7 @@ void* MarkedAllocator::tryAllocateWithou
>             return result;
>     }
>     
>-    if (Options::stealEmptyBlocksFromOtherAllocators()
>-        && shouldStealEmptyBlocksFromOtherAllocators()) {
>+    if (Options::stealEmptyBlocksFromOtherAllocators()) {
>         if (MarkedBlock::Handle* block = markedSpace().findEmptyBlockToSteal()) {
>             block->sweep(nullptr);
>             
>@@ -389,18 +379,16 @@ void MarkedAllocator::endMarking()
>     // know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ
>     // vectors.
>     
>-    if (needsDestruction()) {
>-        // If blocks need destruction then nothing is empty! This is a correct assertion but may
>-        // become wrong once we go full concurrent: when we create a new block, it will flicker
>-        // into the empty set for a tiny moment. On the other hand, this code is likely to be run
>-        // in stopTheWorld.
>-        ASSERT(m_empty.isEmpty());
>-        m_canAllocateButNotEmpty = m_live & ~m_markingRetired;
>-        return;
>-    }
>-    
>     m_empty = m_live & ~m_markingNotEmpty;
>     m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
>+    if (needsDestruction()) {
>+        // There are some blocks that we didn't allocate out of in the last cycle, but we swept them. This
>+        // will forget that we did that and we will end up sweeping them again and attempting to call their
>+        // destructors again. That's fine because of zapping. The only time when we cannot forget is when
>+        // we just allocate a block or when we move a block from one size class to another. That doesn't
>+        // happen here.
>+        m_destructible = m_live;
>+    }
>     
>     if (false) {
>         dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n");
>@@ -437,7 +425,7 @@ void MarkedAllocator::sweep()
> 
> void MarkedAllocator::shrink()
> {
>-    m_empty.forEachSetBit(
>+    (m_empty & ~m_destructible).forEachSetBit(
>         [&] (size_t index) {
>             markedSpace().freeBlock(m_blocks[index]);
>         });
>Index: Source/JavaScriptCore/heap/MarkedAllocator.h
>===================================================================
>--- Source/JavaScriptCore/heap/MarkedAllocator.h	(revision 219789)
>+++ Source/JavaScriptCore/heap/MarkedAllocator.h	(working copy)
>@@ -41,9 +41,10 @@ class LLIntOffsetsExtractor;
> 
> #define FOR_EACH_MARKED_ALLOCATOR_BIT(macro) \
>     macro(live, Live) /* The set of block indices that have actual blocks. */\
>-    macro(empty, Empty) /* The set of all blocks that have no live objects and nothing to destroy. */ \
>+    macro(empty, Empty) /* The set of all blocks that have no live objects. */ \
>     macro(allocated, Allocated) /* The set of all blocks that are full of live objects. */\
>     macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
>+    macro(destructible, Destructible) /* The set of all blocks that may have destructors to run. */\
>     macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
>     macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
>     \
>@@ -65,69 +66,6 @@ class LLIntOffsetsExtractor;
> // has to look at both bitvectors.
> // https://bugs.webkit.org/show_bug.cgi?id=162121
> 
>-// Note that this collector supports overlapping allocator state with marking state, since in a
>-// concurrent collector you allow allocation while marking is running. So it's best to visualize a
>-// full mutable->eden collect->mutate->full collect cycle and see how the bits above get affected.
>-// The example below tries to be exhaustive about what happens to the bits, but omits a lot of
>-// things that happen to other state.
>-//
>-// Create allocator
>-// - all bits are empty
>-// Start allocating in some block
>-// - allocate the block and set the live bit.
>-// - the empty bit for the block flickers on and then gets immediately cleared by sweeping.
>-// - set the eden bit.
>-// Finish allocating in that block
>-// - set the allocated bit.
>-// Do that to a lot of blocks and then start an eden collection.
>-// - beginMarking() has nothing to do.
>-// - by default we have cleared markingNotEmpty/markingRetired bits.
>-// - marking builds up markingNotEmpty/markingRetired bits.
>-// We do endMarking()
>-// - clear all allocated bits.
>-// - for destructor blocks: fragmented = live & ~markingRetired
>-// - for non-destructor blocks:
>-//       empty = live & ~markingNotEmpty
>-//       fragmented = live & markingNotEmpty & ~markingRetired
>-// Snapshotting.
>-// - unswept |= eden
>-// Prepare for allocation.
>-// - clear eden
>-// Finish collection.
>-// Allocate in some block that had some free and some live objects.
>-// - clear the canAllocateButNotEmpty bit
>-// - clear the unswept bit
>-// - set the eden bit
>-// Finish allocating (set the allocated bit).
>-// Allocate in some block that was completely empty.
>-// - clear the empty bit
>-// - clear the unswept bit
>-// - set the eden bit.
>-// Finish allocating (set the allocated bit).
>-// Allocate in some block that was completely empty in another allocator.
>-// - clear the empty bit
>-// - clear all bits in that allocator
>-// - set the live bit in another allocator and the empty bit.
>-// - clear the empty, unswept bits.
>-// - set the eden bit.
>-// Finish allocating (set the allocated bit).
>-// Start a full collection.
>-// - beginMarking() clears markingNotEmpty, markingRetired
>-// - the heap version is incremented
>-// - marking rebuilds markingNotEmpty/markingretired bits.
>-// We do endMarking()
>-// - clear all allocated bits.
>-// - set canAllocateButNotEmpty/empty the same way as in eden collection.
>-// Snapshotting.
>-// - unswept = live
>-// prepare for allocation.
>-// - clear eden.
>-// Finish collection.
>-//
>-// Notice how in this scheme, the empty/canAllocateButNotEmpty state stays separate from the
>-// markingNotEmpty/markingRetired state. This is one step towards having separated allocation and
>-// marking state.
>-
> class MarkedAllocator {
>     friend class LLIntOffsetsExtractor;
> 
>@@ -217,8 +155,6 @@ public:
> private:
>     friend class MarkedBlock;
>     
>-    bool shouldStealEmptyBlocksFromOtherAllocators() const;
>-    
>     JS_EXPORT_PRIVATE void* allocateSlowCase(GCDeferralContext*);
>     JS_EXPORT_PRIVATE void* tryAllocateSlowCase(GCDeferralContext*);
>     void* allocateSlowCaseImpl(GCDeferralContext*, bool crashOnFailure);
>Index: Source/JavaScriptCore/heap/MarkedBlock.cpp
>===================================================================
>--- Source/JavaScriptCore/heap/MarkedBlock.cpp	(revision 219789)
>+++ Source/JavaScriptCore/heap/MarkedBlock.cpp	(working copy)
>@@ -24,6 +24,26 @@
>  */
> 
> #include "config.h"
>+
>+#include <wtf/Assertions.h>
>+
>+namespace {
>+
>+NO_RETURN_DUE_TO_CRASH NEVER_INLINE void crash()
>+{
>+    CRASH();
>+}
>+
>+#undef RELEASE_ASSERT
>+#define RELEASE_ASSERT(assertion) do { \
>+    if (!(assertion)) { \
>+        WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
>+        crash(); \
>+    } \
>+} while (0)
>+
>+} // anonymous namespace
>+
> #include "MarkedBlock.h"
> 
> #include "FreeListInlines.h"
>@@ -152,6 +172,7 @@ void MarkedBlock::Handle::stopAllocating
> void MarkedBlock::Handle::lastChanceToFinalize()
> {
>     allocator()->setIsAllocated(NoLockingNecessary, this, false);
>+    allocator()->setIsDestructible(NoLockingNecessary, this, true);
>     m_block->m_marks.clearAll();
>     m_block->clearHasAnyMarked();
>     m_block->m_markingVersion = heap()->objectSpace().markingVersion();
>@@ -403,8 +424,11 @@ void MarkedBlock::Handle::sweep(FreeList
>     m_allocator->setIsUnswept(NoLockingNecessary, this, false);
>     
>     m_weakSet.sweep();
>+    
>+    bool needsDestruction = m_attributes.destruction == NeedsDestruction
>+        && m_allocator->isDestructible(NoLockingNecessary, this);
> 
>-    if (sweepMode == SweepOnly && m_attributes.destruction == DoesNotNeedDestruction)
>+    if (sweepMode == SweepOnly && !needsDestruction)
>         return;
> 
>     if (UNLIKELY(m_isFreeListed)) {
>@@ -417,7 +441,7 @@ void MarkedBlock::Handle::sweep(FreeList
>     if (space()->isMarking())
>         block().m_lock.lock();
>     
>-    if (m_attributes.destruction == NeedsDestruction) {
>+    if (needsDestruction) {
>         subspace()->finishSweep(*this, freeList);
>         return;
>     }
>Index: Source/JavaScriptCore/heap/MarkedBlockInlines.h
>===================================================================
>--- Source/JavaScriptCore/heap/MarkedBlockInlines.h	(revision 219789)
>+++ Source/JavaScriptCore/heap/MarkedBlockInlines.h	(working copy)
>@@ -161,6 +161,17 @@ void MarkedBlock::Handle::specializedSwe
>     
>     unsigned cellSize = this->cellSize();
>     
>+    VM& vm = *this->vm();
>+    auto destroy = [&] (void* cell) {
>+        JSCell* jsCell = static_cast<JSCell*>(cell);
>+        if (!jsCell->isZapped()) {
>+            destroyFunc(vm, jsCell);
>+            jsCell->zap();
>+        }
>+    };
>+    
>+    m_allocator->setIsDestructible(NoLockingNecessary, this, false);
>+    
>     if (Options::useBumpAllocator()
>         && emptyMode == IsEmpty
>         && newlyAllocatedMode == DoesNotHaveNewlyAllocated) {
>@@ -181,14 +192,17 @@ void MarkedBlock::Handle::specializedSwe
>         char* payloadEnd = startOfLastCell + cellSize;
>         RELEASE_ASSERT(payloadEnd - MarkedBlock::blockSize <= bitwise_cast<char*>(&block));
>         char* payloadBegin = bitwise_cast<char*>(block.atoms() + firstAtom());
>-        if (scribbleMode == Scribble)
>-            scribble(payloadBegin, payloadEnd - payloadBegin);
>+        
>         if (sweepMode == SweepToFreeList)
>             setIsFreeListed();
>-        else
>-            m_allocator->setIsEmpty(NoLockingNecessary, this, true);
>         if (space()->isMarking())
>             block.m_lock.unlock();
>+        if (destructionMode != BlockHasNoDestructors) {
>+            for (char* cell = payloadBegin; cell < payloadEnd; cell += cellSize)
>+                destroy(cell);
>+        }
>+        if (scribbleMode == Scribble)
>+            scribble(payloadBegin, payloadEnd - payloadBegin);
>         if (sweepMode == SweepToFreeList)
>             freeList->initializeBump(payloadEnd, payloadEnd - payloadBegin);
>         if (false)
>@@ -205,17 +219,11 @@ void MarkedBlock::Handle::specializedSwe
>     cryptographicallyRandomValues(&secret, sizeof(uintptr_t));
>     bool isEmpty = true;
>     Vector<size_t> deadCells;
>-    VM& vm = *this->vm();
>     auto handleDeadCell = [&] (size_t i) {
>         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&block.atoms()[i]);
> 
>-        if (destructionMode != BlockHasNoDestructors && emptyMode == NotEmpty) {
>-            JSCell* jsCell = static_cast<JSCell*>(cell);
>-            if (!jsCell->isZapped()) {
>-                destroyFunc(vm, jsCell);
>-                jsCell->zap();
>-            }
>-        }
>+        if (destructionMode != BlockHasNoDestructors && emptyMode == NotEmpty)
>+            destroy(cell);
> 
>         if (sweepMode == SweepToFreeList) {
>             FreeCell* freeCell = reinterpret_cast_ptr<FreeCell*>(cell);
>@@ -273,24 +281,56 @@ void MarkedBlock::Handle::finishSweepKno
>     MarksMode marksMode = this->marksMode();
> 
>     auto trySpecialized = [&] () -> bool {
>-        if (sweepMode != SweepToFreeList)
>-            return false;
>         if (scribbleMode != DontScribble)
>             return false;
>         if (newlyAllocatedMode != DoesNotHaveNewlyAllocated)
>             return false;
>         if (destructionMode != BlockHasDestructors)
>             return false;
>-        if (emptyMode == IsEmpty)
>-            return false;
>         
>-        switch (marksMode) {
>-        case MarksNotStale:
>-            specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
>-            return true;
>-        case MarksStale:
>-            specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
>-            return true;
>+        switch (emptyMode) {
>+        case IsEmpty:
>+            switch (sweepMode) {
>+            case SweepOnly:
>+                switch (marksMode) {
>+                case MarksNotStale:
>+                    specializedSweep<true, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
>+                    return true;
>+                case MarksStale:
>+                    specializedSweep<true, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
>+                    return true;
>+                }
>+            case SweepToFreeList:
>+                switch (marksMode) {
>+                case MarksNotStale:
>+                    specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
>+                    return true;
>+                case MarksStale:
>+                    specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
>+                    return true;
>+                }
>+            }
>+        case NotEmpty:
>+            switch (sweepMode) {
>+            case SweepOnly:
>+                switch (marksMode) {
>+                case MarksNotStale:
>+                    specializedSweep<true, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
>+                    return true;
>+                case MarksStale:
>+                    specializedSweep<true, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
>+                    return true;
>+                }
>+            case SweepToFreeList:
>+                switch (marksMode) {
>+                case MarksNotStale:
>+                    specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
>+                    return true;
>+                case MarksStale:
>+                    specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
>+                    return true;
>+                }
>+            }
>         }
>         
>         return false;
>@@ -320,8 +360,6 @@ inline MarkedBlock::Handle::EmptyMode Ma
>     // - It's true when the block is freshly allocated.
>     // - It's true if the block had been swept in the past, all destructors were called, and that
>     //   sweep proved that the block is empty.
>-    // - It's false if there are any destructors that need to be called, even if the block has no
>-    //   live objects.
>     return m_allocator->isEmpty(NoLockingNecessary, this) ? IsEmpty : NotEmpty;
> }
>

Flags:

mark.lam: review+

Actions: View | Formatted Diff | Diff

Attachments on bug 174811: 316350 | 316351