Log 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):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (219896 => 219897)
--- trunk/Source/_javascript_Core/ChangeLog 2017-07-26 01:03:29 UTC (rev 219896)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-07-26 01:19:23 UTC (rev 219897)
@@ -1,3 +1,68 @@
+2017-07-24 Filip Pizlo <fpi...@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 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):
+
2017-07-25 Keith Miller <keith_mil...@apple.com>
Remove Broken CompareEq constant folding phase.
Modified: trunk/Source/_javascript_Core/heap/MarkedAllocator.cpp (219896 => 219897)
--- trunk/Source/_javascript_Core/heap/MarkedAllocator.cpp 2017-07-26 01:03:29 UTC (rev 219896)
+++ trunk/Source/_javascript_Core/heap/MarkedAllocator.cpp 2017-07-26 01:19:23 UTC (rev 219897)
@@ -67,17 +67,8 @@
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 @@
return result;
}
- if (Options::stealEmptyBlocksFromOtherAllocators()
- && shouldStealEmptyBlocksFromOtherAllocators()) {
+ if (Options::stealEmptyBlocksFromOtherAllocators()) {
if (MarkedBlock::Handle* block = markedSpace().findEmptyBlockToSteal()) {
block->sweep(nullptr);
@@ -389,19 +379,17 @@
// know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ
// vectors.
+ m_empty = m_live & ~m_markingNotEmpty;
+ m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
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;
+ // 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;
}
- m_empty = m_live & ~m_markingNotEmpty;
- m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
-
if (false) {
dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n");
dumpBits(WTF::dataFile());
@@ -437,7 +425,7 @@
void MarkedAllocator::shrink()
{
- m_empty.forEachSetBit(
+ (m_empty & ~m_destructible).forEachSetBit(
[&] (size_t index) {
markedSpace().freeBlock(m_blocks[index]);
});
Modified: trunk/Source/_javascript_Core/heap/MarkedAllocator.h (219896 => 219897)
--- trunk/Source/_javascript_Core/heap/MarkedAllocator.h 2017-07-26 01:03:29 UTC (rev 219896)
+++ trunk/Source/_javascript_Core/heap/MarkedAllocator.h 2017-07-26 01:19:23 UTC (rev 219897)
@@ -41,9 +41,10 @@
#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 @@
// 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 @@
private:
friend class MarkedBlock;
- bool shouldStealEmptyBlocksFromOtherAllocators() const;
-
JS_EXPORT_PRIVATE void* allocateSlowCase(GCDeferralContext*);
JS_EXPORT_PRIVATE void* tryAllocateSlowCase(GCDeferralContext*);
void* allocateSlowCaseImpl(GCDeferralContext*, bool crashOnFailure);
Modified: trunk/Source/_javascript_Core/heap/MarkedBlock.cpp (219896 => 219897)
--- trunk/Source/_javascript_Core/heap/MarkedBlock.cpp 2017-07-26 01:03:29 UTC (rev 219896)
+++ trunk/Source/_javascript_Core/heap/MarkedBlock.cpp 2017-07-26 01:19:23 UTC (rev 219897)
@@ -152,6 +152,7 @@
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 +404,11 @@
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 +421,7 @@
if (space()->isMarking())
block().m_lock.lock();
- if (m_attributes.destruction == NeedsDestruction) {
+ if (needsDestruction) {
subspace()->finishSweep(*this, freeList);
return;
}
Modified: trunk/Source/_javascript_Core/heap/MarkedBlockInlines.h (219896 => 219897)
--- trunk/Source/_javascript_Core/heap/MarkedBlockInlines.h 2017-07-26 01:03:29 UTC (rev 219896)
+++ trunk/Source/_javascript_Core/heap/MarkedBlockInlines.h 2017-07-26 01:19:23 UTC (rev 219897)
@@ -161,6 +161,17 @@
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 @@
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 @@
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,8 +281,6 @@
MarksMode marksMode = this->marksMode();
auto trySpecialized = [&] () -> bool {
- if (sweepMode != SweepToFreeList)
- return false;
if (scribbleMode != DontScribble)
return false;
if (newlyAllocatedMode != DoesNotHaveNewlyAllocated)
@@ -281,16 +287,50 @@
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, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
+ return true;
+ case MarksStale:
+ specializedSweep<true, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
+ return true;
+ }
+ case SweepToFreeList:
+ switch (marksMode) {
+ case MarksNotStale:
+ specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
+ return true;
+ case MarksStale:
+ specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
+ return true;
+ }
+ }
}
return false;
@@ -320,8 +360,6 @@
// - 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;
}
_______________________________________________ webkit-changes mailing list webkit-changes@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-changes
