Changeset 207263 in webkit

Timestamp:

Oct 12, 2016 4:56:34 PM (8 years ago)

Author:

fpizlo@apple.com

Message:

The blackening of CellState is a bad way of tracking if the object is being marked for the first time
​https://bugs.webkit.org/show_bug.cgi?id=163343

Reviewed by Mark Lam.

When I first added the concept of NewGrey/OldGrey, I had the SlotVisitor store the old cell
state in itself, so that it could use it to decide what to do for reportExtraMemoryVisited().

Then I changed it in a recent commit, because I wanted the freedom to have SlotVisitor visit
multiple objects in tandem. But I never ended up using this capability. Still, I liked the
new way better: instead of the SlotVisitor rembemering the state-before-blackening, we would
make the object's state reflect whether it was black for the first time or not. That seemed
convenient.

Unfortunately it's wrong. After we blacken the object, a concurrent barrier could instantly
grey it. Then we would forget that we are visiting this object for the first time.
Subsequent visits will think that they are not the first. So, we will fail to do the right
thing in reportExtraMemoryVisited().

So, this reverts that change. This is a little more than just a revert, though. I've changed
the terminology a bit. For example, I got tired of reading Black and having to remind myself
that it really means that the object has begun being visited, instead of the more strict
meaning that implies that it has already been visited. We want to say that it's Black or
currently being scanned. I'm going to adopt Siebert's term for this: Anthracite [1]. So, our
black CellState is now called AnthraciteOrBlack.

[1] ​https://pdfs.semanticscholar.org/7ae4/633265aead1f8835cf7966e179d02c2c8a4b.pdf

• heap/CellState.h:

(JSC::isBlack): Deleted.
(JSC::blacken): Deleted.

• heap/Heap.cpp:

(JSC::Heap::addToRememberedSet):
(JSC::Heap::writeBarrierSlowPath):

• heap/Heap.h:
• heap/HeapInlines.h:

(JSC::Heap::reportExtraMemoryVisited):
(JSC::Heap::reportExternalMemoryVisited):

• heap/SlotVisitor.cpp:

(JSC::SlotVisitor::appendToMarkStack):
(JSC::SlotVisitor::visitChildren):

• heap/SlotVisitor.h:
• heap/SlotVisitorInlines.h:

(JSC::SlotVisitor::reportExtraMemoryVisited):
(JSC::SlotVisitor::reportExternalMemoryVisited):

• llint/LLIntData.cpp:

(JSC::LLInt::Data::performAssertions):

• llint/LowLevelInterpreter.asm:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• heap/CellState.h (modified) (2 diffs)
• heap/Heap.cpp (modified) (2 diffs)
• heap/Heap.h (modified) (1 diff)
• heap/HeapInlines.h (modified) (2 diffs)
• heap/SlotVisitor.cpp (modified) (3 diffs)
• heap/SlotVisitor.h (modified) (1 diff)
• heap/SlotVisitorInlines.h (modified) (2 diffs)
• llint/LLIntData.cpp (modified) (1 diff)
• llint/LowLevelInterpreter.asm (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2016-10-12  Filip Pizlo  <fpizlo@apple.com>
+
+        The blackening of CellState is a bad way of tracking if the object is being marked for the first time
+        https://bugs.webkit.org/show_bug.cgi?id=163343
+
+        Reviewed by Mark Lam.
+        
+        When I first added the concept of NewGrey/OldGrey, I had the SlotVisitor store the old cell
+        state in itself, so that it could use it to decide what to do for reportExtraMemoryVisited().
+        
+        Then I changed it in a recent commit, because I wanted the freedom to have SlotVisitor visit
+        multiple objects in tandem. But I never ended up using this capability. Still, I liked the
+        new way better: instead of the SlotVisitor rembemering the state-before-blackening, we would
+        make the object's state reflect whether it was black for the first time or not. That seemed
+        convenient.
+        
+        Unfortunately it's wrong. After we blacken the object, a concurrent barrier could instantly
+        grey it. Then we would forget that we are visiting this object for the first time.
+        Subsequent visits will think that they are not the first. So, we will fail to do the right
+        thing in reportExtraMemoryVisited().
+        
+        So, this reverts that change. This is a little more than just a revert, though. I've changed
+        the terminology a bit. For example, I got tired of reading Black and having to remind myself
+        that it really means that the object has begun being visited, instead of the more strict
+        meaning that implies that it has already been visited. We want to say that it's Black or
+        currently being scanned. I'm going to adopt Siebert's term for this: Anthracite [1]. So, our
+        black CellState is now called AnthraciteOrBlack.
+        
+        [1] https://pdfs.semanticscholar.org/7ae4/633265aead1f8835cf7966e179d02c2c8a4b.pdf
+
+        * heap/CellState.h:
+        (JSC::isBlack): Deleted.
+        (JSC::blacken): Deleted.
+        * heap/Heap.cpp:
+        (JSC::Heap::addToRememberedSet):
+        (JSC::Heap::writeBarrierSlowPath):
+        * heap/Heap.h:
+        * heap/HeapInlines.h:
+        (JSC::Heap::reportExtraMemoryVisited):
+        (JSC::Heap::reportExternalMemoryVisited):
+        * heap/SlotVisitor.cpp:
+        (JSC::SlotVisitor::appendToMarkStack):
+        (JSC::SlotVisitor::visitChildren):
+        * heap/SlotVisitor.h:
+        * heap/SlotVisitorInlines.h:
+        (JSC::SlotVisitor::reportExtraMemoryVisited):
+        (JSC::SlotVisitor::reportExternalMemoryVisited):
+        * llint/LLIntData.cpp:
+        (JSC::LLInt::Data::performAssertions):
+        * llint/LowLevelInterpreter.asm:
+
 2016-10-12  Mark Lam  <mark.lam@apple.com>
 

trunk/Source/JavaScriptCore/heap/CellState.h

@@ -31 +31 @@
 
 enum class CellState : uint8_t {
-    // The object is black for the first time during this GC.
-    NewBlack = 0,
-    
-    // The object is black for the Nth time during this full GC cycle (N > 1). An object may get to
-    // this state if it transitions from black back to grey during a concurrent GC, or because it
-    // wound up in the remembered set because of a generational barrier.
-    OldBlack = 1,
+    // The object is either currently being scanned (anthracite) or it has finished being scanned
+    // (black). It could be scanned for the first time this GC, or the Nth time - if it's anthracite
+    // then the SlotVisitor knows. We explicitly say "anthracite or black" to emphasize the fact that
+    // this is no guarantee that we have finished scanning the object, unless you also know that all
+    // SlotVisitors are done.
+    AnthraciteOrBlack = 0,
     
     // The object is in eden. During GC, this means that the object has not been marked yet.
-    NewWhite = 2,
+    NewWhite = 1,
 
     // The object is grey - i.e. it will be scanned - and this is the first time in this GC that we are
     // going to scan it. If this is an eden GC, this also means that the object is in eden.
-    NewGrey = 3,
+    NewGrey = 2,
 
     // The object is grey - i.e. it will be scanned - but it either belongs to old gen (if this is eden
     // GC) or it is grey a second time in this current GC (because a concurrent store barrier requested
     // re-greying).
-    OldGrey = 4
+    OldGrey = 3
 };
 
-static const unsigned blackThreshold = 1; // x <= blackThreshold means x is black.
+static const unsigned blackThreshold = 0; // x <= blackThreshold means x is AnthraciteOrBlack.
 static const unsigned tautologicalThreshold = 100; // x <= tautologicalThreshold is always true.
 
@@ -60 +59 @@
 }
 
-inline bool isBlack(CellState cellState)
-{
-    return isWithinThreshold(cellState, blackThreshold);
-}
-
-inline CellState blacken(CellState cellState)
-{
-    if (cellState == CellState::NewGrey)
-        return CellState::NewBlack;
-    ASSERT(cellState == CellState::NewBlack || cellState == CellState::OldBlack || cellState == CellState::OldGrey);
-    return CellState::OldBlack;
-}
-
 } // namespace JSC

trunk/Source/JavaScriptCore/heap/Heap.cpp

@@ -917 +917 @@
     ASSERT(cell);
     ASSERT(!Options::useConcurrentJIT() || !isCompilationThread());
-    ASSERT(isBlack(cell->cellState()));
+    ASSERT(cell->cellState() == CellState::AnthraciteOrBlack);
     // Indicate that this object is grey and that it's one of the following:
     // - A re-greyed object during a concurrent collection.
@@ -1553 +1553 @@
         // not black. But we can't know for sure until we fire off a fence.
         WTF::storeLoadFence();
-        if (!isBlack(from->cellState()))
+        if (from->cellState() != CellState::AnthraciteOrBlack)
             return;
     }

trunk/Source/JavaScriptCore/heap/Heap.h

@@ -182 +182 @@
     // memory growth.
     void reportExtraMemoryAllocated(size_t);
-    void reportExtraMemoryVisited(JSCell*, size_t);
+    void reportExtraMemoryVisited(CellState oldState, size_t);
 
 #if ENABLE(RESOURCE_USAGE)
     // Use this API to report the subset of extra memory that lives outside this process.
-    void reportExternalMemoryVisited(JSCell*, size_t);
+    void reportExternalMemoryVisited(CellState oldState, size_t);
     size_t externalMemorySize() { return m_externalMemorySize; }
 #endif

trunk/Source/JavaScriptCore/heap/HeapInlines.h

@@ -159 +159 @@
 }
 
-inline void Heap::reportExtraMemoryVisited(JSCell* cell, size_t size)
+inline void Heap::reportExtraMemoryVisited(CellState oldState, size_t size)
 {
     // We don't want to double-count the extra memory that was reported in previous collections.
-    if (operationInProgress() == EdenCollection && cell->cellState() == CellState::OldBlack)
+    if (operationInProgress() == EdenCollection && oldState == CellState::OldGrey)
         return;
 
@@ -175 +175 @@
 
 #if ENABLE(RESOURCE_USAGE)
-inline void Heap::reportExternalMemoryVisited(JSCell* cell, size_t size)
+inline void Heap::reportExternalMemoryVisited(CellState oldState, size_t size)
 {
     // We don't want to double-count the external memory that was reported in previous collections.
-    if (operationInProgress() == EdenCollection && cell->cellState() == CellState::OldBlack)
+    if (operationInProgress() == EdenCollection && oldState == CellState::OldGrey)
         return;
 

trunk/Source/JavaScriptCore/heap/SlotVisitor.cpp

@@ -229 +229 @@
     ASSERT(Heap::isMarkedConcurrently(cell));
     ASSERT(!cell->isZapped());
+    ASSERT(cell->cellState() == CellState::NewGrey || cell->cellState() == CellState::OldGrey);
     
     container.noteMarked();
@@ -294 +295 @@
     SetCurrentCellScope currentCellScope(*this, cell);
     
-    cell->setCellState(blacken(cell->cellState()));
+    m_oldCellState = cell->cellState();
+    
+    // There is no race here - the cell state cannot change right now. Grey objects can only be
+    // visited by one marking thread. Neither the barrier nor marking will change the state of an
+    // object that is already grey.
+    ASSERT(m_oldCellState == CellState::OldGrey || m_oldCellState == CellState::NewGrey);
+    
+    cell->setCellState(CellState::AnthraciteOrBlack);
     
     WTF::storeLoadFence();
@@ -319 +327 @@
     
     if (UNLIKELY(m_heapSnapshotBuilder)) {
-        if (cell->cellState() != CellState::OldBlack)
+        if (m_oldCellState == CellState::NewGrey)
             m_heapSnapshotBuilder->appendNode(const_cast<JSCell*>(cell));
     }

trunk/Source/JavaScriptCore/heap/SlotVisitor.h

@@ -166 +166 @@
     HeapSnapshotBuilder* m_heapSnapshotBuilder { nullptr };
     JSCell* m_currentCell { nullptr };
+    CellState m_oldCellState;
 
 public:

trunk/Source/JavaScriptCore/heap/SlotVisitorInlines.h

@@ -106 +106 @@
 inline void SlotVisitor::reportExtraMemoryVisited(size_t size)
 {
-    heap()->reportExtraMemoryVisited(m_currentCell, size);
+    heap()->reportExtraMemoryVisited(m_oldCellState, size);
 }
 
@@ -112 +112 @@
 inline void SlotVisitor::reportExternalMemoryVisited(size_t size)
 {
-    heap()->reportExternalMemoryVisited(m_currentCell, size);
+    heap()->reportExternalMemoryVisited(m_oldCellState, size);
 }
 #endif

trunk/Source/JavaScriptCore/llint/LLIntData.cpp

@@ -215 +215 @@
 
     STATIC_ASSERT(MarkedBlock::blockSize == 16 * 1024);
-    STATIC_ASSERT(blackThreshold == 1);
+    STATIC_ASSERT(blackThreshold == 0);
 
     ASSERT(bitwise_cast<uintptr_t>(ShadowChicken::Packet::tailMarker()) == static_cast<uintptr_t>(0x7a11));

trunk/Source/JavaScriptCore/llint/LowLevelInterpreter.asm

@@ -410 +410 @@
 const MarkedBlockMask = ~(MarkedBlockSize - 1)
 
-const BlackThreshold = 1
+const BlackThreshold = 0
 
 # Allocation constants