Make the HeapVerifier useful again.
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 14 Mar 2017 00:39:24 +0000 (00:39 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 14 Mar 2017 00:39:24 +0000 (00:39 +0000)
https://bugs.webkit.org/show_bug.cgi?id=161752

Reviewed by Filip Pizlo.

Resurrect the HeapVerifier.  Here's what the verifier now offers:

1. It captures the list of cells before and after GCs up to N GC cycles.
   N is set by JSC_numberOfGCCyclesToRecordForVerification.
   Currently, N defaults to 3.

   This is useful if we're debugging in lldb and want to check if a candidate
   cell pointer was observed by the GC during the last N GC cycles.  We can do
   this check buy calling HeapVerifier::checkIfRecorded() with the cell address.

   HeapVerifier::checkIfRecorded() is robust and can be used on bogus addresses.
   If the candidate cell was previously recorded by the HeapVerifier during a
   GC cycle, checkIfRecorded() will dump any useful info it has on that cell.

2. The HeapVerifier will verify that cells in its captured list after a GC are
   sane.  Some examples of cell insanity are:
   - the cell claims to belong to a different VM.
   - the cell has a NULL structureID.
   - the cell has a NULL structure.
   - the cell's structure has a NULL structureID.
   - the cell's structure has a NULL structure.
   - the cell's structure's structure has a NULL structureID.
   - the cell's structure's structure has a NULL structure.

   These are all signs of corruption or a GC bug.  The verifier will report any
   insanity it finds, and then crash with a RELEASE_ASSERT.

3. Since the HeapVerifier captures list of cells in the heap before and after GCs
   for the last N GCs, it will also automatically "trim" dead cells those list
   after the most recent GC.

   "trim" here means that the CellProfile in the HeapVerifier's lists will be
   updated to reflect that the cell is now dead.  It still keeps a record of the
   dead cell pointer and the meta data collected about it back when it was alive.
   As a result, checkIfRecorded() will also report if the candidate cell passed
   to it is a dead object from a previous GC cycle.

4. Each CellProfile captured by the HeapVerifier now track the following info:
   - the cell's HeapCell::Kind.
   - the cell's liveness.
   - if is JSCell, the cell's classInfo()->className.
   - an associated timestamp.
   - an associated stack trace.

   Currently, the timestamp is only used for the time when the cell was recorded
   by the HeapVerifier during GC.  The stack trace is currently unused.

   However, these fields are kept there so that we can instrument the VM (during
   a debugging session, which requires rebuilding the VM) and record interesting
   stack traces like that of the time of allocation of the cell.  Since
   capturing the stack traces for each cell is a very heavy weight operation,
   the HeapVerifier code does not do this by default.  Instead, we just leave
   the building blocks for doing so in place to ease future debugging efforts.

* heap/Heap.cpp:
(JSC::Heap::runBeginPhase):
(JSC::Heap::runEndPhase):
(JSC::Heap::didFinishCollection):
* heap/Heap.h:
(JSC::Heap::verifier):
* heap/MarkedAllocator.h:
(JSC::MarkedAllocator::takeLastActiveBlock): Deleted.
* heap/MarkedSpace.h:
* heap/MarkedSpaceInlines.h:
(JSC::MarkedSpace::forEachLiveCell):
* tools/CellList.cpp:
(JSC::CellList::find):
(JSC::CellList::reset):
(JSC::CellList::findCell): Deleted.
* tools/CellList.h:
(JSC::CellList::CellList):
(JSC::CellList::name):
(JSC::CellList::size):
(JSC::CellList::cells):
(JSC::CellList::add):
(JSC::CellList::reset): Deleted.
* tools/CellProfile.h:
(JSC::CellProfile::CellProfile):
(JSC::CellProfile::cell):
(JSC::CellProfile::jsCell):
(JSC::CellProfile::isJSCell):
(JSC::CellProfile::kind):
(JSC::CellProfile::isLive):
(JSC::CellProfile::isDead):
(JSC::CellProfile::setIsLive):
(JSC::CellProfile::setIsDead):
(JSC::CellProfile::timestamp):
(JSC::CellProfile::className):
(JSC::CellProfile::stackTrace):
(JSC::CellProfile::setStackTrace):
* tools/HeapVerifier.cpp:
(JSC::HeapVerifier::startGC):
(JSC::HeapVerifier::endGC):
(JSC::HeapVerifier::gatherLiveCells):
(JSC::trimDeadCellsFromList):
(JSC::HeapVerifier::trimDeadCells):
(JSC::HeapVerifier::printVerificationHeader):
(JSC::HeapVerifier::verifyCellList):
(JSC::HeapVerifier::validateCell):
(JSC::HeapVerifier::validateJSCell):
(JSC::HeapVerifier::verify):
(JSC::HeapVerifier::reportCell):
(JSC::HeapVerifier::checkIfRecorded):
(JSC::HeapVerifier::initializeGCCycle): Deleted.
(JSC::GatherCellFunctor::GatherCellFunctor): Deleted.
(JSC::GatherCellFunctor::visit): Deleted.
(JSC::GatherCellFunctor::operator()): Deleted.
(JSC::HeapVerifier::verifyButterflyIsInStorageSpace): Deleted.
* tools/HeapVerifier.h:
(JSC::HeapVerifier::GCCycle::reset):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@213883 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/heap/MarkedAllocator.h
Source/JavaScriptCore/heap/MarkedSpace.h
Source/JavaScriptCore/heap/MarkedSpaceInlines.h
Source/JavaScriptCore/tools/CellList.cpp
Source/JavaScriptCore/tools/CellList.h
Source/JavaScriptCore/tools/CellProfile.h
Source/JavaScriptCore/tools/HeapVerifier.cpp
Source/JavaScriptCore/tools/HeapVerifier.h

index 7ded4f0..642cd54 100644 (file)
@@ -1,3 +1,121 @@
+2017-03-13  Mark Lam  <mark.lam@apple.com>
+
+        Make the HeapVerifier useful again.
+        https://bugs.webkit.org/show_bug.cgi?id=161752
+
+        Reviewed by Filip Pizlo.
+
+        Resurrect the HeapVerifier.  Here's what the verifier now offers:
+
+        1. It captures the list of cells before and after GCs up to N GC cycles.
+           N is set by JSC_numberOfGCCyclesToRecordForVerification.
+           Currently, N defaults to 3.
+
+           This is useful if we're debugging in lldb and want to check if a candidate
+           cell pointer was observed by the GC during the last N GC cycles.  We can do
+           this check buy calling HeapVerifier::checkIfRecorded() with the cell address.
+
+           HeapVerifier::checkIfRecorded() is robust and can be used on bogus addresses.
+           If the candidate cell was previously recorded by the HeapVerifier during a
+           GC cycle, checkIfRecorded() will dump any useful info it has on that cell.
+
+        2. The HeapVerifier will verify that cells in its captured list after a GC are
+           sane.  Some examples of cell insanity are:
+           - the cell claims to belong to a different VM.
+           - the cell has a NULL structureID.
+           - the cell has a NULL structure.
+           - the cell's structure has a NULL structureID.
+           - the cell's structure has a NULL structure.
+           - the cell's structure's structure has a NULL structureID.
+           - the cell's structure's structure has a NULL structure.
+
+           These are all signs of corruption or a GC bug.  The verifier will report any
+           insanity it finds, and then crash with a RELEASE_ASSERT.
+
+        3. Since the HeapVerifier captures list of cells in the heap before and after GCs
+           for the last N GCs, it will also automatically "trim" dead cells those list
+           after the most recent GC.
+
+           "trim" here means that the CellProfile in the HeapVerifier's lists will be
+           updated to reflect that the cell is now dead.  It still keeps a record of the
+           dead cell pointer and the meta data collected about it back when it was alive.
+           As a result, checkIfRecorded() will also report if the candidate cell passed
+           to it is a dead object from a previous GC cycle. 
+
+        4. Each CellProfile captured by the HeapVerifier now track the following info:
+           - the cell's HeapCell::Kind.
+           - the cell's liveness.
+           - if is JSCell, the cell's classInfo()->className.
+           - an associated timestamp.
+           - an associated stack trace.
+
+           Currently, the timestamp is only used for the time when the cell was recorded
+           by the HeapVerifier during GC.  The stack trace is currently unused.
+
+           However, these fields are kept there so that we can instrument the VM (during
+           a debugging session, which requires rebuilding the VM) and record interesting
+           stack traces like that of the time of allocation of the cell.  Since
+           capturing the stack traces for each cell is a very heavy weight operation,
+           the HeapVerifier code does not do this by default.  Instead, we just leave
+           the building blocks for doing so in place to ease future debugging efforts.
+
+        * heap/Heap.cpp:
+        (JSC::Heap::runBeginPhase):
+        (JSC::Heap::runEndPhase):
+        (JSC::Heap::didFinishCollection):
+        * heap/Heap.h:
+        (JSC::Heap::verifier):
+        * heap/MarkedAllocator.h:
+        (JSC::MarkedAllocator::takeLastActiveBlock): Deleted.
+        * heap/MarkedSpace.h:
+        * heap/MarkedSpaceInlines.h:
+        (JSC::MarkedSpace::forEachLiveCell):
+        * tools/CellList.cpp:
+        (JSC::CellList::find):
+        (JSC::CellList::reset):
+        (JSC::CellList::findCell): Deleted.
+        * tools/CellList.h:
+        (JSC::CellList::CellList):
+        (JSC::CellList::name):
+        (JSC::CellList::size):
+        (JSC::CellList::cells):
+        (JSC::CellList::add):
+        (JSC::CellList::reset): Deleted.
+        * tools/CellProfile.h:
+        (JSC::CellProfile::CellProfile):
+        (JSC::CellProfile::cell):
+        (JSC::CellProfile::jsCell):
+        (JSC::CellProfile::isJSCell):
+        (JSC::CellProfile::kind):
+        (JSC::CellProfile::isLive):
+        (JSC::CellProfile::isDead):
+        (JSC::CellProfile::setIsLive):
+        (JSC::CellProfile::setIsDead):
+        (JSC::CellProfile::timestamp):
+        (JSC::CellProfile::className):
+        (JSC::CellProfile::stackTrace):
+        (JSC::CellProfile::setStackTrace):
+        * tools/HeapVerifier.cpp:
+        (JSC::HeapVerifier::startGC):
+        (JSC::HeapVerifier::endGC):
+        (JSC::HeapVerifier::gatherLiveCells):
+        (JSC::trimDeadCellsFromList):
+        (JSC::HeapVerifier::trimDeadCells):
+        (JSC::HeapVerifier::printVerificationHeader):
+        (JSC::HeapVerifier::verifyCellList):
+        (JSC::HeapVerifier::validateCell):
+        (JSC::HeapVerifier::validateJSCell):
+        (JSC::HeapVerifier::verify):
+        (JSC::HeapVerifier::reportCell):
+        (JSC::HeapVerifier::checkIfRecorded):
+        (JSC::HeapVerifier::initializeGCCycle): Deleted.
+        (JSC::GatherCellFunctor::GatherCellFunctor): Deleted.
+        (JSC::GatherCellFunctor::visit): Deleted.
+        (JSC::GatherCellFunctor::operator()): Deleted.
+        (JSC::HeapVerifier::verifyButterflyIsInStorageSpace): Deleted.
+        * tools/HeapVerifier.h:
+        (JSC::HeapVerifier::GCCycle::reset):
+
 2017-03-13  SKumarMetro  <s.kumar@metrological.com>
 
         JSC: fix compilation errors for MIPS
index 7483f11..05469a0 100644 (file)
@@ -1097,12 +1097,12 @@ NEVER_INLINE bool Heap::runBeginPhase(GCConductor conn)
         
     willStartCollection(scope);
         
-    if (m_verifier) {
+    if (UNLIKELY(m_verifier)) {
         // Verify that live objects from the last GC cycle haven't been corrupted by
         // mutators before we begin this new GC cycle.
         m_verifier->verify(HeapVerifier::Phase::BeforeGC);
             
-        m_verifier->initializeGCCycle();
+        m_verifier->startGC();
         m_verifier->gatherLiveCells(HeapVerifier::Phase::BeforeMarking);
     }
         
@@ -1332,7 +1332,7 @@ NEVER_INLINE bool Heap::runEndPhase(GCConductor conn)
     updateObjectCounts();
     endMarking();
         
-    if (m_verifier) {
+    if (UNLIKELY(m_verifier)) {
         m_verifier->gatherLiveCells(HeapVerifier::Phase::AfterMarking);
         m_verifier->verify(HeapVerifier::Phase::AfterMarking);
     }
@@ -1357,13 +1357,13 @@ NEVER_INLINE bool Heap::runEndPhase(GCConductor conn)
     m_objectSpace.prepareForAllocation();
     updateAllocationLimits();
 
-    didFinishCollection();
-    
-    if (m_verifier) {
+    if (UNLIKELY(m_verifier)) {
         m_verifier->trimDeadCells();
         m_verifier->verify(HeapVerifier::Phase::AfterGC);
     }
 
+    didFinishCollection();
+
     if (false) {
         dataLog("Heap state after GC:\n");
         m_objectSpace.dumpBits();
@@ -2162,6 +2162,9 @@ void Heap::didFinishCollection()
         removeDeadHeapSnapshotNodes(*heapProfiler);
     }
 
+    if (UNLIKELY(m_verifier))
+        m_verifier->endGC();
+
     RELEASE_ASSERT(m_collectionScope);
     m_lastCollectionScope = m_collectionScope;
     m_collectionScope = std::nullopt;
index 0632716..d065701 100644 (file)
@@ -351,7 +351,9 @@ public:
     CFRunLoopRef runLoop() const { return m_runLoop.get(); }
     JS_EXPORT_PRIVATE void setRunLoop(CFRunLoopRef);
 #endif // USE(CF)
-    
+
+    HeapVerifier* verifier() const { return m_verifier.get(); }
+
 private:
     friend class AllocatingScope;
     friend class CodeBlock;
index 09903e4..1c6402b 100644 (file)
@@ -42,7 +42,7 @@ 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(allocated, Allocated) /* The set of allblocks that are full of 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(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. */\
@@ -155,13 +155,7 @@ public:
     void* allocate(GCDeferralContext* = nullptr);
     void* tryAllocate(GCDeferralContext* = nullptr);
     Heap* heap() { return m_heap; }
-    MarkedBlock::Handle* takeLastActiveBlock()
-    {
-        MarkedBlock::Handle* block = m_lastActiveBlock;
-        m_lastActiveBlock = 0;
-        return block;
-    }
-    
+
     template<typename Functor> void forEachBlock(const Functor&);
     template<typename Functor> void forEachNotEmptyBlock(const Functor&);
     
index 26be5e3..5f0491e 100644 (file)
@@ -178,6 +178,10 @@ private:
     void* allocateSlow(Subspace&, GCDeferralContext*, size_t);
     void* tryAllocateSlow(Subspace&, GCDeferralContext*, size_t);
 
+    // Use this version when calling from within the GC where we know that the allocators
+    // have already been stopped.
+    template<typename Functor> void forEachLiveCell(const Functor&);
+
     static void initializeSizeClassForStepSize();
     
     void initializeSubspace(Subspace&);
@@ -212,6 +216,8 @@ private:
     MarkedAllocator* m_firstAllocator { nullptr };
     MarkedAllocator* m_lastAllocator { nullptr };
     MarkedAllocator* m_allocatorForEmptyAllocation { nullptr };
+
+    friend class HeapVerifier;
 };
 
 template <typename Functor> inline void MarkedSpace::forEachBlock(const Functor& functor)
index e629cb0..7fba86d 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -33,6 +33,11 @@ namespace JSC {
 template<typename Functor> inline void MarkedSpace::forEachLiveCell(HeapIterationScope&, const Functor& functor)
 {
     ASSERT(isIterating());
+    forEachLiveCell(functor);
+}
+
+template<typename Functor> inline void MarkedSpace::forEachLiveCell(const Functor& functor)
+{
     BlockIterator end = m_blocks.set().end();
     for (BlockIterator it = m_blocks.set().begin(); it != end; ++it) {
         if ((*it)->handle().forEachLiveCell(functor) == IterationStatus::Done)
index c49f7da..b4b845a 100644 (file)
 
 namespace JSC {
 
-CellProfile* CellList::findCell(JSCell* cell)
+CellProfile* CellList::find(HeapCell* cell)
 {
-    for (auto& profile : liveCells) {
-        if (cell == profile.cell)
-            return &profile;
+    if (!size())
+        return nullptr;
+
+    if (!m_mapIsUpToDate) {
+        m_map.clear();
+        for (auto& profile : m_cells)
+            m_map.add(profile.cell(), &profile);
+        m_mapIsUpToDate = true;
     }
-    return nullptr;
+    return m_map.get(cell);
+}
+
+void CellList::reset()
+{
+    m_cells.clear();
+    m_map.clear();
+    m_mapIsUpToDate = false;
 }
 
 } // namespace JSC
index 0e36762..0c88aaa 100644 (file)
 #pragma once
 
 #include "CellProfile.h"
-#include <wtf/Vector.h>
+#include <wtf/HashMap.h>
+#include <wtf/SegmentedVector.h>
 
 namespace JSC {
 
-struct CellList {
+class CellList {
+    WTF_MAKE_FAST_ALLOCATED;
+public:
     CellList(const char* name)
-        : name(name)
-        , hasLiveCells(true)
+        : m_name(name)
     {
     }
     
-    void reset()
+    const char* name() const { return m_name; }
+    size_t size() const { return m_cells.size(); }
+
+    typedef SegmentedVector<CellProfile, 64> CellProfileVector;
+    CellProfileVector& cells() { return m_cells; }
+
+    void add(CellProfile&& profile)
     {
-        liveCells.clear();
-        hasLiveCells = true; // Presume to have live objects until the list is trimmed.
+        m_cells.append(WTFMove(profile));
+        m_mapIsUpToDate = false;
     }
-    
-    CellProfile* findCell(JSCell*);
-    
-    const char* name;
-    Vector<CellProfile> liveCells;
-    bool hasLiveCells;
+
+    void reset();
+
+    CellProfile* find(HeapCell*);
+
+private:
+    const char* m_name;
+    CellProfileVector m_cells;
+
+    bool m_mapIsUpToDate { false };
+    HashMap<HeapCell*, CellProfile*> m_map;
 };
     
 } // namespace JSC
index 48720ed..07bb9a8 100644 (file)
 
 #pragma once
 
-namespace JSC {
+#include "JSCell.h"
+#include "StackTrace.h"
+#include "Structure.h"
+#include <wtf/MonotonicTime.h>
 
-class JSCell;
+namespace JSC {
 
 struct CellProfile {
-    CellProfile(JSCell* cell, bool isConfirmedDead = false)
-        : cell(cell)
-        , isConfirmedDead(isConfirmedDead)
+    enum Liveness {
+        Unknown,
+        Dead,
+        Live
+    };
+
+    CellProfile(HeapCell* cell, HeapCell::Kind kind, Liveness liveness)
+        : m_cell(cell)
+        , m_kind(kind)
+        , m_liveness(liveness)
+        , m_timestamp(MonotonicTime::now())
+    {
+        if (m_kind == HeapCell::JSCell && m_liveness != Dead)
+            m_className = jsCell()->structure()->classInfo()->className;
+    }
+
+    CellProfile(CellProfile&& other)
+        : m_cell(other.m_cell)
+        , m_kind(other.m_kind)
+        , m_liveness(other.m_liveness)
+        , m_timestamp(other.m_timestamp)
+        , m_className(other.m_className)
+        , m_stackTrace(WTFMove(other.m_stackTrace))
+    { }
+
+    HeapCell* cell() const { return m_cell; }
+    JSCell* jsCell() const
     {
+        ASSERT(isJSCell());
+        return static_cast<JSCell*>(m_cell);
     }
+
+    bool isJSCell() const { return m_kind == HeapCell::JSCell; }
     
-    JSCell* cell;
-    bool isConfirmedDead;
+    HeapCell::Kind kind() const { return m_kind; }
+
+    bool isLive() const { return m_liveness == Live; }
+    bool isDead() const { return m_liveness == Dead; }
+
+    void setIsLive() { m_liveness = Live; }
+    void setIsDead() { m_liveness = Dead; }
+
+    MonotonicTime timestamp() const { return m_timestamp; }
+
+    const char* className() const { return m_className; }
+
+    StackTrace* stackTrace() const { return m_stackTrace.get(); }
+    void setStackTrace(StackTrace* trace) { m_stackTrace = std::unique_ptr<StackTrace>(trace); }
+
+private:
+    HeapCell* m_cell;
+    HeapCell::Kind m_kind;
+    Liveness m_liveness { Unknown };
+    MonotonicTime m_timestamp;
+    const char* m_className { nullptr };
+    std::unique_ptr<StackTrace> m_stackTrace;
 };
 
 } // namespace JSC
index 3959e95..5426d98 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 #include "config.h"
 #include "HeapVerifier.h"
 
-#include "ButterflyInlines.h"
+#include "CodeBlock.h"
 #include "HeapIterationScope.h"
 #include "JSCInlines.h"
 #include "JSObject.h"
 #include "MarkedSpaceInlines.h"
+#include "VMInspector.h"
+#include "ValueProfile.h"
+#include <wtf/ProcessID.h>
 
 namespace JSC {
 
@@ -59,48 +62,36 @@ const char* HeapVerifier::phaseName(HeapVerifier::Phase phase)
     return nullptr; // Silencing a compiler warning.
 }
 
-void HeapVerifier::initializeGCCycle()
+void HeapVerifier::startGC()
 {
     Heap* heap = m_heap;
     incrementCycle();
+    currentCycle().reset();
     currentCycle().scope = *heap->collectionScope();
+    currentCycle().timestamp = MonotonicTime::now();
+    ASSERT(!m_didPrintLogs);
 }
 
-struct GatherCellFunctor : MarkedBlock::CountFunctor {
-    GatherCellFunctor(CellList& list)
-        : m_list(list)
-    {
-        ASSERT(!list.liveCells.size());
-    }
-
-    inline void visit(JSCell* cell)
-    {
-        CellProfile profile(cell);
-        m_list.liveCells.append(profile);
-    }
-
-    IterationStatus operator()(HeapCell* cell, HeapCell::Kind kind) const
-    {
-        if (kind == HeapCell::JSCell) {
-            // FIXME: This const_cast exists because this isn't a C++ lambda.
-            // https://bugs.webkit.org/show_bug.cgi?id=159644
-            const_cast<GatherCellFunctor*>(this)->visit(static_cast<JSCell*>(cell));
-        }
-        return IterationStatus::Continue;
+void HeapVerifier::endGC()
+{
+    if (m_didPrintLogs) {
+        dataLog("END ");
+        printVerificationHeader();
+        dataLog("\n\n");
+        m_didPrintLogs = false;
     }
-
-    CellList& m_list;
-};
+}
 
 void HeapVerifier::gatherLiveCells(HeapVerifier::Phase phase)
 {
     Heap* heap = m_heap;
     CellList& list = *cellListForGathering(phase);
 
-    HeapIterationScope iterationScope(*heap);
     list.reset();
-    GatherCellFunctor functor(list);
-    heap->m_objectSpace.forEachLiveCell(iterationScope, functor);
+    heap->m_objectSpace.forEachLiveCell([&list] (HeapCell* cell, HeapCell::Kind kind) {
+        list.add({ cell, kind, CellProfile::Live });
+        return IterationStatus::Continue;
+    });
 }
 
 CellList* HeapVerifier::cellListForGathering(HeapVerifier::Phase phase)
@@ -119,31 +110,25 @@ CellList* HeapVerifier::cellListForGathering(HeapVerifier::Phase phase)
     return nullptr; // Silencing a compiler warning.
 }
 
-static void trimDeadCellsFromList(HashSet<JSCell*>& knownLiveSet, CellList& list)
+static void trimDeadCellsFromList(CellList& knownLiveSet, CellList& list)
 {
-    if (!list.hasLiveCells)
+    if (!list.size())
         return;
 
-    size_t liveCellsFound = 0;
-    for (auto& cellProfile : list.liveCells) {
-        if (cellProfile.isConfirmedDead)
+    for (auto& cellProfile : list.cells()) {
+        if (cellProfile.isDead())
             continue; // Don't "resurrect" known dead cells.
-        if (!knownLiveSet.contains(cellProfile.cell)) {
-            cellProfile.isConfirmedDead = true;
+        if (!knownLiveSet.find(cellProfile.cell())) {
+            cellProfile.setIsDead();
             continue;
         }
-        liveCellsFound++;
+        cellProfile.setIsLive();
     }
-    list.hasLiveCells = !!liveCellsFound;
 }
 
 void HeapVerifier::trimDeadCells()
 {
-    HashSet<JSCell*> knownLiveSet;
-
-    CellList& after = currentCycle().after;
-    for (auto& cellProfile : after.liveCells)
-        knownLiveSet.add(cellProfile.cell);
+    CellList& knownLiveSet = currentCycle().after;
 
     trimDeadCellsFromList(knownLiveSet, currentCycle().before);
 
@@ -153,71 +138,330 @@ void HeapVerifier::trimDeadCells()
     }
 }
 
-bool HeapVerifier::verifyButterflyIsInStorageSpace(Phase, CellList&)
+void HeapVerifier::printVerificationHeader()
+{
+    RELEASE_ASSERT(m_heap->collectionScope());
+    CollectionScope scope = currentCycle().scope;
+    MonotonicTime gcCycleTimestamp = currentCycle().timestamp;
+    dataLog("Verifying heap in [p", getCurrentProcessID(), ", t", currentThread(), "] vm ",
+        RawPointer(m_heap->vm()), " on ", scope, " GC @ ", gcCycleTimestamp, "\n");
+}
+
+bool HeapVerifier::verifyCellList(Phase phase, CellList& list)
+{
+    VM& vm = *m_heap->vm();
+    auto& liveCells = list.cells();
+
+    bool listNamePrinted = false;
+    auto printHeaderIfNeeded = [&] () {
+        if (listNamePrinted)
+            return;
+        
+        printVerificationHeader();
+        dataLog(" @ phase ", phaseName(phase), ": FAILED in cell list '", list.name(), "' (size ", liveCells.size(), ")\n");
+        listNamePrinted = true;
+        m_didPrintLogs = true;
+    };
+    
+    bool success = true;
+    for (size_t i = 0; i < liveCells.size(); i++) {
+        CellProfile& profile = liveCells[i];
+        if (!profile.isLive())
+            continue;
+
+        if (!profile.isJSCell())
+            continue;
+
+        JSCell* cell = profile.jsCell();
+        success |= validateJSCell(&vm, cell, &profile, &list, printHeaderIfNeeded, "  ");
+    }
+
+    return success;
+}
+
+bool HeapVerifier::validateCell(HeapCell* cell, VM* expectedVM)
+{
+    auto printNothing = [] () { };
+
+    if (cell->isZapped()) {
+        dataLog("    cell ", RawPointer(cell), " is ZAPPED\n");
+        return false;
+    }
+
+    if (cell->cellKind() != HeapCell::JSCell)
+        return true; // Nothing more to validate.
+
+    JSCell* jsCell = static_cast<JSCell*>(cell);
+    return validateJSCell(expectedVM, jsCell, nullptr, nullptr, printNothing);
+}
+
+bool HeapVerifier::validateJSCell(VM* expectedVM, JSCell* cell, CellProfile* profile, CellList* list, std::function<void()> printHeaderIfNeeded, const char* prefix)
 {
-    // FIXME: Make this work again. https://bugs.webkit.org/show_bug.cgi?id=161752
+    auto printHeaderAndCell = [cell, profile, printHeaderIfNeeded, prefix] () {
+        printHeaderIfNeeded();
+        dataLog(prefix, "cell ", RawPointer(cell));
+        if (profile)
+            dataLog(" [", profile->className(), "]");
+    };
+
+    // 1. Validate the cell.
+
+    if (cell->isZapped()) {
+        printHeaderAndCell();
+        dataLog(" is zapped\n");
+        return false;
+    }
+
+    StructureID structureID = cell->structureID();
+    if (!structureID) {
+        printHeaderAndCell();
+        dataLog(" has NULL structureID\n");
+        return false;
+    }
+
+    if (expectedVM) {
+        VM& vm = *expectedVM;
+
+        VM* cellVM = cell->vm();
+        if (cellVM != expectedVM) {
+            printHeaderAndCell();
+            dataLog(" is from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(cellVM), "\n");
+            return false;
+        }
+
+        // 2. Validate the cell's structure
+
+        Structure* structure = vm.getStructure(structureID);
+        if (!structure) {
+            printHeaderAndCell();
+#if USE(JSVALUE64)
+            uint32_t structureIDAsUint32 = structureID;
+#else
+            uint32_t structureIDAsUint32 = reinterpret_cast<uint32_t>(structureID);
+#endif
+            dataLog(" with structureID ", structureIDAsUint32, " maps to a NULL Structure pointer\n");
+            return false;
+        }
+
+        if (structure->isZapped()) {
+            printHeaderAndCell();
+            dataLog(" has ZAPPED structure ", RawPointer(structure), "\n");
+            return false;
+        }
+
+        if (!structure->structureID()) {
+            printHeaderAndCell();
+            dataLog(" has structure ", RawPointer(structure), " whose structureID is NULL\n");
+            return false;
+        }
+
+        VM* structureVM = structure->vm();
+        if (structureVM != expectedVM) {
+            printHeaderAndCell();
+            dataLog(" has structure ", RawPointer(structure), " from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(structureVM), "\n");
+            return false;
+        }
+
+        if (list) {
+            auto* structureProfile = list->find(structure);
+            if (!structureProfile) {
+                printHeaderAndCell();
+                dataLog(" has structure ", RawPointer(structure), " NOT found in the live cell list\n");
+                return false;
+            }
+
+            if (!structureProfile->isLive()) {
+                printHeaderAndCell();
+                dataLog(" has DEAD structure ", RawPointer(structure), "\n");
+                return false;
+            }
+        }
+
+        StructureID structureStructureID = structure->structureID();
+        if (!structureStructureID) {
+            printHeaderAndCell();
+            dataLog(" has structure ", RawPointer(structure), " with a NULL structureID\n");
+            return false;
+        }
+
+        // 3. Validate the cell's structure's structure.
+        
+        Structure* structureStructure = vm.getStructure(structureID);
+        if (!structureStructure) {
+            printHeaderAndCell();
+            dataLog(" has structure ", RawPointer(structure), " whose structure is NULL\n");
+            return false;
+        }
+        
+        if (structureStructure->isZapped()) {
+            printHeaderAndCell();
+            dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is ZAPPED\n");
+            return false;
+        }
+        
+        if (!structureStructure->structureID()) {
+            printHeaderAndCell();
+            dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " has a NULL structureID\n");
+            return false;
+        }
+        
+        VM* structureStructureVM = structureStructure->vm();
+        if (structureStructureVM != expectedVM) {
+            printHeaderAndCell();
+            dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(structureStructureVM), "\n");
+            return false;
+        }
+        
+        if (list) {
+            auto* structureStructureProfile = list->find(structureStructure);
+            if (!structureStructureProfile) {
+                printHeaderAndCell();
+                dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is NOT found in the live cell list\n");
+                return false;
+            }
+            
+            if (!structureStructureProfile->isLive()) {
+                printHeaderAndCell();
+                dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is DEAD\n");
+                return false;
+            }
+        }
+        
+        CodeBlock* codeBlock = jsDynamicCast<CodeBlock*>(vm, cell);
+        if (UNLIKELY(codeBlock)) {
+            bool success = true;
+            for (unsigned i = 0; i < codeBlock->totalNumberOfValueProfiles(); ++i) {
+                ValueProfile* valueProfile = codeBlock->getFromAllValueProfiles(i);
+                for (unsigned i = 0; i < ValueProfile::totalNumberOfBuckets; ++i) {
+                    JSValue value = JSValue::decode(valueProfile->m_buckets[i]);
+                    if (!value)
+                        continue;
+                    if (!value.isCell())
+                        continue;
+                    JSCell* valueCell = value.asCell();
+                    if (valueCell->isZapped()) {
+                        printHeaderIfNeeded();
+                        dataLog(prefix, "CodeBlock ", RawPointer(codeBlock), " has ZAPPED ValueProfile cell ", RawPointer(valueCell), "\n");
+                        success = false;
+                        continue;
+                    }
+                }
+            }
+            if (!success)
+                return false;
+        }
+    }
+
     return true;
 }
 
 void HeapVerifier::verify(HeapVerifier::Phase phase)
 {
-    bool beforeVerified = verifyButterflyIsInStorageSpace(phase, currentCycle().before);
-    bool afterVerified = verifyButterflyIsInStorageSpace(phase, currentCycle().after);
-    RELEASE_ASSERT(beforeVerified && afterVerified);
+    if (phase == Phase::AfterGC) {
+        bool verified = verifyCellList(phase, currentCycle().after);
+        RELEASE_ASSERT(verified);
+    }
 }
 
-void HeapVerifier::reportCell(CellProfile& cellProfile, int cycleIndex, HeapVerifier::GCCycle& cycle, CellList& list)
+void HeapVerifier::reportCell(CellProfile& profile, int cycleIndex, HeapVerifier::GCCycle& cycle, CellList& list, const char* prefix)
 {
-    JSCell* cell = cellProfile.cell;
+    HeapCell* cell = profile.cell();
+    VM* vm = m_heap->vm();
 
-    if (cellProfile.isConfirmedDead) {
-        dataLogF("FOUND dead cell %p in GC[%d] %s list '%s'\n",
-            cell, cycleIndex, collectionScopeName(cycle.scope), list.name);
-        return;
-    }
+    if (prefix)
+        dataLog(prefix);
 
-    if (cell->isObject()) {
-        JSObject* object = static_cast<JSObject*>(cell);
-        Structure* structure = object->structure();
-        Butterfly* butterfly = object->butterfly();
-        void* butterflyBase = butterfly->base(structure);
-
-        dataLogF("FOUND object %p type '%s' butterfly %p (base %p) in GC[%d] %s list '%s'\n",
-            object, structure->classInfo()->className,
-            butterfly, butterflyBase,
-            cycleIndex, collectionScopeName(cycle.scope), list.name);
-    } else {
-        Structure* structure = cell->structure();
-        dataLogF("FOUND cell %p type '%s' in GC[%d] %s list '%s'\n",
-            cell, structure->classInfo()->className,
-            cycleIndex, collectionScopeName(cycle.scope), list.name);
+    dataLog("FOUND");
+    if (profile.isLive())
+        dataLog(" LIVE");
+    else if (profile.isDead())
+        dataLog(" DEAD");
+
+    if (!profile.isJSCell())
+        dataLog(" HeapCell ");
+    else
+        dataLog(" JSCell ");
+    dataLog(RawPointer(cell));
+
+    if (profile.className())
+        dataLog(" [", profile.className(), "]");
+
+    if (profile.isLive() && profile.isJSCell()) {
+        JSCell* jsCell = profile.jsCell();
+        Structure* structure = jsCell->structure();
+        dataLog(" structure:", RawPointer(structure));
+        if (jsCell->isObject()) {
+            JSObject* obj = static_cast<JSObject*>(cell);
+            Butterfly* butterfly = obj->butterfly();
+            void* butterflyBase = butterfly->base(structure);
+            
+            dataLog(" butterfly:", RawPointer(butterfly), " (base:", RawPointer(butterflyBase), ")");
+        }
     }
+
+    dataLog(" in ", cycle.scope, " GC[", cycleIndex, "] in '", list.name(), "' list in VM ",
+        RawPointer(vm), " recorded at time ", profile.timestamp(), "\n");
+    if (profile.stackTrace())
+        dataLog(*profile.stackTrace());
 }
 
-void HeapVerifier::checkIfRecorded(JSCell* cell)
+void HeapVerifier::checkIfRecorded(HeapCell* cell)
 {
     bool found = false;
+    const char* const prefix = "  ";
+    static const bool verbose = true;
 
     for (int cycleIndex = 0; cycleIndex > -m_numberOfCycles; cycleIndex--) {
         GCCycle& cycle = cycleForIndex(cycleIndex);
-        CellList& beforeList = cycle.before;
-        CellList& afterList = cycle.after;
+        CellList* lists[] = { &cycle.before, &cycle.after };
 
-        CellProfile* profile;
-        profile = beforeList.findCell(cell);
-        if (profile) {
-            reportCell(*profile, cycleIndex, cycle, beforeList);
-            found = true;
-        }
-        profile = afterList.findCell(cell);
-        if (profile) {
-            reportCell(*profile, cycleIndex, cycle, afterList);
-            found = true;
+        if (verbose)
+            dataLog("Checking ", cycle.scope, " GC<", cycle.timestamp, ">, cycle [", cycleIndex, "]:\n");
+        
+        const char* resultPrefix = "    ";
+        for (auto* list : lists) {
+            if (verbose)
+                dataLog(prefix, "Cycle [", cycleIndex, "] '", list->name(), "' list: ");
+
+            CellProfile* profile = list->find(cell);
+            if (profile) {
+                reportCell(*profile, cycleIndex, cycle, *list, resultPrefix);
+                found = true;
+            } else if (verbose)
+                dataLog(resultPrefix, "cell NOT found\n");
         }
     }
 
     if (!found)
-        dataLogF("cell %p NOT FOUND\n", cell);
+        dataLog(prefix, "cell ", RawPointer(cell), " NOT FOUND\n");
+}
+
+// The following are slower but more robust versions of the corresponding functions of the same name.
+// These robust versions are designed so that we can call them interactively from a C++ debugger
+// to query if a candidate is recorded cell.
+
+void HeapVerifier::checkIfRecorded(uintptr_t candidateCell)
+{
+    HeapCell* candidateHeapCell = reinterpret_cast<HeapCell*>(candidateCell);
+    
+    VMInspector& inspector = VMInspector::instance();
+    auto expectedLocker = inspector.lock(Seconds(2));
+    if (!expectedLocker) {
+        ASSERT(expectedLocker.error() == VMInspector::Error::TimedOut);
+        dataLog("ERROR: Timed out while waiting to iterate VMs.");
+        return;
+    }
+
+    auto& locker = expectedLocker.value();
+    inspector.iterate(locker, [&] (VM& vm) {
+        if (!vm.heap.m_verifier)
+            return VMInspector::FunctorStatus::Continue;
+        
+        auto* verifier = vm.heap.m_verifier.get();
+        dataLog("Search for cell ", RawPointer(candidateHeapCell), " in VM ", RawPointer(&vm), ":\n");
+        verifier->checkIfRecorded(candidateHeapCell);
+        return VMInspector::FunctorStatus::Continue;
+    });
 }
 
 } // namespace JSC
index 35f243e..4824b1c 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -27,6 +27,7 @@
 
 #include "CellList.h"
 #include "Heap.h"
+#include <wtf/MonotonicTime.h>
 
 namespace JSC {
 
@@ -45,16 +46,21 @@ public:
 
     HeapVerifier(Heap*, unsigned numberOfGCCyclesToRecord);
 
-    void initializeGCCycle();
+    void startGC();
+    void endGC();
+
     void gatherLiveCells(Phase);
     void trimDeadCells();
     void verify(Phase);
 
+    static const char* phaseName(Phase);
+    
     // Scans all previously recorded CellLists and checks if the specified
     // cell was in any of those lists.
-    JS_EXPORT_PRIVATE void checkIfRecorded(JSCell*);
+    JS_EXPORT_PRIVATE static void checkIfRecorded(uintptr_t maybeCell);
 
-    static const char* phaseName(Phase);
+    // Returns false if anything is found to be inconsistent/incorrect about the specified cell.
+    JS_EXPORT_PRIVATE static bool validateCell(HeapCell*, VM* expectedVM = nullptr);
 
 private:
     struct GCCycle {
@@ -64,7 +70,14 @@ private:
         {
         }
 
+        void reset()
+        {
+            before.reset();
+            after.reset();
+        }
+
         CollectionScope scope;
+        MonotonicTime timestamp;
         CellList before;
         CellList after;
     };
@@ -82,13 +95,18 @@ private:
     }
 
     CellList* cellListForGathering(Phase);
-    bool verifyButterflyIsInStorageSpace(Phase, CellList&);
+    bool verifyCellList(Phase, CellList&);
+    static bool validateJSCell(VM* expectedVM, JSCell*, CellProfile*, CellList*, std::function<void()> printHeaderIfNeeded, const char* prefix = "");
+
+    void printVerificationHeader();
 
-    static void reportCell(CellProfile&, int cycleIndex, HeapVerifier::GCCycle&, CellList&);
+    void checkIfRecorded(HeapCell* maybeHeapCell);
+    void reportCell(CellProfile&, int cycleIndex, HeapVerifier::GCCycle&, CellList&, const char* prefix = nullptr);
 
     Heap* m_heap;
     int m_currentCycle;
     int m_numberOfCycles;
+    bool m_didPrintLogs { false };
     std::unique_ptr<GCCycle[]> m_cycles;
 };