Add Heap verification infrastructure.
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 20 Nov 2014 23:28:41 +0000 (23:28 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 20 Nov 2014 23:28:41 +0000 (23:28 +0000)
<https://webkit.org/b/138851>

Reviewed by Geoffrey Garen.

The verification infrastructure code is always built in but disabled by
default.  When disabled, the cost is minimal:
1. Heap has a m_verifier field.
2. GC does a few "if (m_verifier)" checks that should fail.
3. HeapVerifier takes up code space though not used.

When enabled:
1. The HeapVerifier will keep N number of GC cycle data.
   Each GC cycle will contain a "before marking" and "after marking" live
   object list.
   The GC cycles is a circular buffer.  Only data for the last N GC cycles
   will be retained.
2. During GC, the current GC cycle's live objects lists will be populated
   before and after marking.
3. The current GC cycle's live object lists will be validated before GC,
   after marking, and after GC.

Currently, the only validation being done is to verify that object
butterflies are allocated from valid blocks in the Storage (aka Copied)
space.

* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters:
* JavaScriptCore.xcodeproj/project.pbxproj:
* heap/Heap.cpp:
(JSC::Heap::Heap):
(JSC::Heap::collect):
* heap/Heap.h:
* heap/HeapVerifier.cpp: Added.
(JSC::LiveObjectList::findObject):
(JSC::HeapVerifier::HeapVerifier):
(JSC::HeapVerifier::collectionTypeName):
(JSC::HeapVerifier::phaseName):
(JSC::getButterflyDetails):
(JSC::HeapVerifier::initializeGCCycle):
(JSC::GatherLiveObjFunctor::GatherLiveObjFunctor):
(JSC::GatherLiveObjFunctor::operator()):
(JSC::HeapVerifier::gatherLiveObjects):
(JSC::HeapVerifier::liveObjectListForGathering):
(JSC::trimDeadObjectsFromList):
(JSC::HeapVerifier::trimDeadObjects):
(JSC::HeapVerifier::verifyButterflyIsInStorageSpace):
(JSC::HeapVerifier::verify):
(JSC::HeapVerifier::reportObject):
(JSC::HeapVerifier::checkIfRecorded):
* heap/HeapVerifier.h: Added.
(JSC::LiveObjectData::LiveObjectData):
(JSC::LiveObjectList::LiveObjectList):
(JSC::LiveObjectList::reset):
(JSC::HeapVerifier::GCCycle::GCCycle):
(JSC::HeapVerifier::GCCycle::collectionTypeName):
(JSC::HeapVerifier::incrementCycle):
(JSC::HeapVerifier::currentCycle):
(JSC::HeapVerifier::cycleForIndex):
* runtime/Options.h:

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

Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/heap/HeapVerifier.cpp [new file with mode: 0644]
Source/JavaScriptCore/heap/HeapVerifier.h [new file with mode: 0644]
Source/JavaScriptCore/runtime/Options.h

index e03c8fe..fbd63f0 100644 (file)
@@ -265,6 +265,7 @@ set(JavaScriptCore_SOURCES
     heap/Heap.cpp
     heap/HeapStatistics.cpp
     heap/HeapTimer.cpp
+    heap/HeapVerifier.cpp
     heap/IncrementalSweeper.cpp
     heap/JITStubRoutineSet.cpp
     heap/MachineStackMarker.cpp
index 06babdc..5d85624 100644 (file)
@@ -1,3 +1,67 @@
+2014-11-20  Mark Lam  <mark.lam@apple.com>
+
+        Add Heap verification infrastructure.
+        <https://webkit.org/b/138851>
+
+        Reviewed by Geoffrey Garen.
+
+        The verification infrastructure code is always built in but disabled by
+        default.  When disabled, the cost is minimal:
+        1. Heap has a m_verifier field.
+        2. GC does a few "if (m_verifier)" checks that should fail.
+        3. HeapVerifier takes up code space though not used.
+
+        When enabled:
+        1. The HeapVerifier will keep N number of GC cycle data.
+           Each GC cycle will contain a "before marking" and "after marking" live
+           object list.
+           The GC cycles is a circular buffer.  Only data for the last N GC cycles
+           will be retained.
+        2. During GC, the current GC cycle's live objects lists will be populated
+           before and after marking.
+        3. The current GC cycle's live object lists will be validated before GC,
+           after marking, and after GC.
+
+        Currently, the only validation being done is to verify that object
+        butterflies are allocated from valid blocks in the Storage (aka Copied)
+        space.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+        * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * heap/Heap.cpp:
+        (JSC::Heap::Heap):
+        (JSC::Heap::collect):
+        * heap/Heap.h:
+        * heap/HeapVerifier.cpp: Added.
+        (JSC::LiveObjectList::findObject):
+        (JSC::HeapVerifier::HeapVerifier):
+        (JSC::HeapVerifier::collectionTypeName):
+        (JSC::HeapVerifier::phaseName):
+        (JSC::getButterflyDetails):
+        (JSC::HeapVerifier::initializeGCCycle):
+        (JSC::GatherLiveObjFunctor::GatherLiveObjFunctor):
+        (JSC::GatherLiveObjFunctor::operator()):
+        (JSC::HeapVerifier::gatherLiveObjects):
+        (JSC::HeapVerifier::liveObjectListForGathering):
+        (JSC::trimDeadObjectsFromList):
+        (JSC::HeapVerifier::trimDeadObjects):
+        (JSC::HeapVerifier::verifyButterflyIsInStorageSpace):
+        (JSC::HeapVerifier::verify):
+        (JSC::HeapVerifier::reportObject):
+        (JSC::HeapVerifier::checkIfRecorded):
+        * heap/HeapVerifier.h: Added.
+        (JSC::LiveObjectData::LiveObjectData):
+        (JSC::LiveObjectList::LiveObjectList):
+        (JSC::LiveObjectList::reset):
+        (JSC::HeapVerifier::GCCycle::GCCycle):
+        (JSC::HeapVerifier::GCCycle::collectionTypeName):
+        (JSC::HeapVerifier::incrementCycle):
+        (JSC::HeapVerifier::currentCycle):
+        (JSC::HeapVerifier::cycleForIndex):
+        * runtime/Options.h:
+
 2014-11-20  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         Rename String.prototype.contains to String.prototype.includes
index 9df752a..f2948a3 100644 (file)
     <ClCompile Include="..\heap\Heap.cpp" />
     <ClCompile Include="..\heap\HeapStatistics.cpp" />
     <ClCompile Include="..\heap\HeapTimer.cpp" />
+    <ClCompile Include="..\heap\HeapVerifier.cpp" />
     <ClCompile Include="..\heap\IncrementalSweeper.cpp" />
     <ClCompile Include="..\heap\JITStubRoutineSet.cpp" />
     <ClCompile Include="..\heap\MachineStackMarker.cpp" />
     <ClInclude Include="..\heap\HeapRootVisitor.h" />
     <ClInclude Include="..\heap\HeapStatistics.h" />
     <ClInclude Include="..\heap\HeapTimer.h" />
+    <ClInclude Include="..\heap\HeapVerifier.h" />
     <ClInclude Include="..\heap\IncrementalSweeper.h" />
     <ClInclude Include="..\heap\JITStubRoutineSet.h" />
     <ClInclude Include="..\heap\ListableHandler.h" />
index 52f0f20..0544756 100644 (file)
     <ClCompile Include="..\heap\HeapTimer.cpp">
       <Filter>heap</Filter>
     </ClCompile>
+    <ClCompile Include="..\heap\HeapVerifier.cpp">
+      <Filter>heap</Filter>
+    </ClCompile>
     <ClCompile Include="..\heap\IncrementalSweeper.cpp">
       <Filter>heap</Filter>
     </ClCompile>
     <ClInclude Include="..\heap\HeapTimer.h">
       <Filter>heap</Filter>
     </ClInclude>
+    <ClInclude Include="..\heap\HeapVerifier.h">
+      <Filter>heap</Filter>
+    </ClInclude>
     <ClInclude Include="..\heap\IncrementalSweeper.h">
       <Filter>heap</Filter>
     </ClInclude>
index 6cc937e..fe8441b 100644 (file)
                FE5248F9191442D900B7FDE4 /* VariableWatchpointSetInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = FE5248F8191442D900B7FDE4 /* VariableWatchpointSetInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
                FE5932A7183C5A2600A1ECCC /* VMEntryScope.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE5932A5183C5A2600A1ECCC /* VMEntryScope.cpp */; };
                FE5932A8183C5A2600A1ECCC /* VMEntryScope.h in Headers */ = {isa = PBXBuildFile; fileRef = FE5932A6183C5A2600A1ECCC /* VMEntryScope.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               FE7BA60F1A1A7CEC00F1F7B4 /* HeapVerifier.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7BA60D1A1A7CEC00F1F7B4 /* HeapVerifier.cpp */; };
+               FE7BA6101A1A7CEC00F1F7B4 /* HeapVerifier.h in Headers */ = {isa = PBXBuildFile; fileRef = FE7BA60E1A1A7CEC00F1F7B4 /* HeapVerifier.h */; settings = {ATTRIBUTES = (Private, ); }; };
                FEA08620182B7A0400F6D851 /* Breakpoint.h in Headers */ = {isa = PBXBuildFile; fileRef = FEA0861E182B7A0400F6D851 /* Breakpoint.h */; settings = {ATTRIBUTES = (Private, ); }; };
                FEA08621182B7A0400F6D851 /* DebuggerPrimitives.h in Headers */ = {isa = PBXBuildFile; fileRef = FEA0861F182B7A0400F6D851 /* DebuggerPrimitives.h */; settings = {ATTRIBUTES = (Private, ); }; };
                FEB58C14187B8B160098EF0B /* ErrorHandlingScope.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEB58C12187B8B160098EF0B /* ErrorHandlingScope.cpp */; };
                FE5248F8191442D900B7FDE4 /* VariableWatchpointSetInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VariableWatchpointSetInlines.h; sourceTree = "<group>"; };
                FE5932A5183C5A2600A1ECCC /* VMEntryScope.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = VMEntryScope.cpp; sourceTree = "<group>"; };
                FE5932A6183C5A2600A1ECCC /* VMEntryScope.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VMEntryScope.h; sourceTree = "<group>"; };
+               FE7BA60D1A1A7CEC00F1F7B4 /* HeapVerifier.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HeapVerifier.cpp; sourceTree = "<group>"; };
+               FE7BA60E1A1A7CEC00F1F7B4 /* HeapVerifier.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HeapVerifier.h; sourceTree = "<group>"; };
                FEA0861E182B7A0400F6D851 /* Breakpoint.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Breakpoint.h; sourceTree = "<group>"; };
                FEA0861F182B7A0400F6D851 /* DebuggerPrimitives.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DebuggerPrimitives.h; sourceTree = "<group>"; };
                FEB58C12187B8B160098EF0B /* ErrorHandlingScope.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ErrorHandlingScope.cpp; sourceTree = "<group>"; };
                142E312A134FF0A600AFADB5 /* heap */ = {
                        isa = PBXGroup;
                        children = (
+                               FE7BA60D1A1A7CEC00F1F7B4 /* HeapVerifier.cpp */,
+                               FE7BA60E1A1A7CEC00F1F7B4 /* HeapVerifier.h */,
                                C2DA778218E259990066FCB6 /* HeapInlines.h */,
                                ADDB1F6218D77DB7009B58A8 /* OpaqueRootSet.h */,
                                2AACE63A18CA5A0300ED0191 /* GCActivityCallback.cpp */,
                                A584032018BFFBE1005A0811 /* InspectorAgent.h in Headers */,
                                2AABCDE718EF294200002096 /* GCLogging.h in Headers */,
                                FE5248F9191442D900B7FDE4 /* VariableWatchpointSetInlines.h in Headers */,
+                               FE7BA6101A1A7CEC00F1F7B4 /* HeapVerifier.h in Headers */,
                                A5EF9B141A1D43F600702E90 /* generate_cpp_backend_dispatcher_header.py in Headers */,
                                C2DA778318E259990066FCB6 /* HeapInlines.h in Headers */,
                                C4F4B6F41A05C944005CAB76 /* cpp_generator.py in Headers */,
                                A513E5CA185F9624007E95AD /* InjectedScriptManager.cpp in Sources */,
                                A5840E20187B7B8600843B10 /* InjectedScriptModule.cpp in Sources */,
                                0F24E55517F0B71C00ABB217 /* InlineCallFrameSet.cpp in Sources */,
+                               FE7BA60F1A1A7CEC00F1F7B4 /* HeapVerifier.cpp in Sources */,
                                A5CEEE14187F3BAD00E55C99 /* InspectorAgent.cpp in Sources */,
                                A593CF86184038CA00BFCE27 /* InspectorAgentRegistry.cpp in Sources */,
                                0F2B9CF619D0BAC100B1D1B5 /* FTLExitTimeObjectMaterialization.cpp in Sources */,
index aed6b70..6e95291 100644 (file)
@@ -35,6 +35,7 @@
 #include "HeapIterationScope.h"
 #include "HeapRootVisitor.h"
 #include "HeapStatistics.h"
+#include "HeapVerifier.h"
 #include "IncrementalSweeper.h"
 #include "Interpreter.h"
 #include "JSGlobalObject.h"
@@ -339,6 +340,8 @@ Heap::Heap(VM* vm, HeapType heapType)
     , m_deferralDepth(0)
 {
     m_storageSpace.init();
+    if (Options::verifyHeap())
+        m_verifier = std::make_unique<HeapVerifier>(this, Options::numberOfGCCyclesToRecordForVerification());
 }
 
 Heap::~Heap()
@@ -1004,6 +1007,14 @@ void Heap::collect(HeapOperation collectionType)
     GCPHASE(Collect);
 
     double gcStartTime = WTF::monotonicallyIncreasingTime();
+    if (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->gatherLiveObjects(HeapVerifier::Phase::BeforeMarking);
+    }
 
     deleteOldCode(gcStartTime);
     flushOldStructureIDTables();
@@ -1012,6 +1023,10 @@ void Heap::collect(HeapOperation collectionType)
 
     markRoots(gcStartTime);
 
+    if (m_verifier) {
+        m_verifier->gatherLiveObjects(HeapVerifier::Phase::AfterMarking);
+        m_verifier->verify(HeapVerifier::Phase::AfterMarking);
+    }
     JAVASCRIPTCORE_GC_MARKED();
 
     if (vm()->typeProfiler())
@@ -1035,6 +1050,11 @@ void Heap::collect(HeapOperation collectionType)
     didFinishCollection(gcStartTime);
     resumeCompilerThreads();
 
+    if (m_verifier) {
+        m_verifier->trimDeadObjects();
+        m_verifier->verify(HeapVerifier::Phase::AfterGC);
+    }
+
     if (Options::logGC()) {
         double after = currentTimeMS();
         dataLog(after - before, " ms]\n");
index 348d4ec..2dd8154 100644 (file)
@@ -57,6 +57,7 @@ class GCAwareJITStubRoutine;
 class GlobalCodeBlock;
 class Heap;
 class HeapRootVisitor;
+class HeapVerifier;
 class IncrementalSweeper;
 class JITStubRoutine;
 class JSCell;
@@ -234,6 +235,7 @@ private:
     friend class GCAwareJITStubRoutine;
     friend class GCLogging;
     friend class HandleSet;
+    friend class HeapVerifier;
     friend class JITStubRoutine;
     friend class LLIntOffsetsExtractor;
     friend class MarkedSpace;
@@ -383,6 +385,8 @@ private:
     
     unsigned m_deferralDepth;
     Vector<DFG::Worklist*> m_suspendedCompilerWorklists;
+
+    std::unique_ptr<HeapVerifier> m_verifier;
 };
 
 } // namespace JSC
diff --git a/Source/JavaScriptCore/heap/HeapVerifier.cpp b/Source/JavaScriptCore/heap/HeapVerifier.cpp
new file mode 100644 (file)
index 0000000..c25524c
--- /dev/null
@@ -0,0 +1,294 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "HeapVerifier.h"
+
+#include "ButterflyInlines.h"
+#include "CopiedSpaceInlines.h"
+#include "HeapIterationScope.h"
+#include "JSCInlines.h"
+#include "JSObject.h"
+
+namespace JSC {
+
+LiveObjectData* LiveObjectList::findObject(JSObject* obj)
+{
+    for (size_t i = 0; i < liveObjects.size(); i++) {
+        LiveObjectData& data = liveObjects[i];
+        if (obj == data.obj)
+            return &data;
+    }
+    return nullptr;
+}
+
+HeapVerifier::HeapVerifier(Heap* heap, unsigned numberOfGCCyclesToRecord)
+    : m_heap(heap)
+    , m_currentCycle(0)
+    , m_numberOfCycles(numberOfGCCyclesToRecord)
+{
+    RELEASE_ASSERT(m_numberOfCycles > 0);
+    m_cycles = std::make_unique<GCCycle[]>(m_numberOfCycles);
+}
+
+const char* HeapVerifier::collectionTypeName(HeapOperation type)
+{
+    switch (type) {
+    case NoOperation:
+        return "NoOperation";
+    case AnyCollection:
+        return "AnyCollection";
+    case Allocation:
+        return "Allocation";
+    case EdenCollection:
+        return "EdenCollection";
+    case FullCollection:
+        return "FullCollection";
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+    return nullptr; // Silencing a compiler warning.
+}
+
+const char* HeapVerifier::phaseName(HeapVerifier::Phase phase)
+{
+    switch (phase) {
+    case Phase::BeforeGC:
+        return "BeforeGC";
+    case Phase::BeforeMarking:
+        return "BeforeMarking";
+    case Phase::AfterMarking:
+        return "AfterMarking";
+    case Phase::AfterGC:
+        return "AfterGC";
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+    return nullptr; // Silencing a compiler warning.
+}
+
+static void getButterflyDetails(JSObject* obj, void*& butterflyBase, size_t& butterflyCapacityInBytes, CopiedBlock*& butterflyBlock)
+{
+    Structure* structure = obj->structure();
+    Butterfly* butterfly = obj->butterfly();
+    butterflyBase = butterfly->base(structure);
+    butterflyBlock = CopiedSpace::blockFor(butterflyBase);
+
+    size_t propertyCapacity = structure->outOfLineCapacity();
+    size_t preCapacity;
+    size_t indexingPayloadSizeInBytes;
+    bool hasIndexingHeader = obj->hasIndexingHeader();
+    if (UNLIKELY(hasIndexingHeader)) {
+        preCapacity = butterfly->indexingHeader()->preCapacity(structure);
+        indexingPayloadSizeInBytes = butterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
+    } else {
+        preCapacity = 0;
+        indexingPayloadSizeInBytes = 0;
+    }
+    butterflyCapacityInBytes = Butterfly::totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
+}
+
+void HeapVerifier::initializeGCCycle()
+{
+    Heap* heap = m_heap;
+    incrementCycle();
+    currentCycle().collectionType = heap->operationInProgress();
+}
+
+struct GatherLiveObjFunctor : MarkedBlock::CountFunctor {
+    GatherLiveObjFunctor(LiveObjectList& list)
+        : m_list(list)
+    {
+        ASSERT(!list.liveObjects.size());
+    }
+
+    void operator()(JSCell* cell)
+    {
+        if (!cell->isObject())
+            return;        
+        LiveObjectData data(asObject(cell));
+        m_list.liveObjects.append(data);
+    }
+
+    LiveObjectList& m_list;
+};
+
+void HeapVerifier::gatherLiveObjects(HeapVerifier::Phase phase)
+{
+    Heap* heap = m_heap;
+    LiveObjectList& list = *liveObjectListForGathering(phase);
+
+    HeapIterationScope iterationScope(*heap);
+    list.reset();
+    GatherLiveObjFunctor functor(list);
+    heap->m_objectSpace.forEachLiveCell(iterationScope, functor);
+}
+
+LiveObjectList* HeapVerifier::liveObjectListForGathering(HeapVerifier::Phase phase)
+{
+    switch (phase) {
+    case Phase::BeforeMarking:
+        return &currentCycle().before;
+    case Phase::AfterMarking:
+        return &currentCycle().after;
+    case Phase::BeforeGC:
+    case Phase::AfterGC:
+        // We should not be gathering live objects during these phases.
+        break;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+    return nullptr; // Silencing a compiler warning.
+}
+
+static void trimDeadObjectsFromList(HashSet<JSObject*>& knownLiveSet, LiveObjectList& list)
+{
+    if (!list.hasLiveObjects)
+        return;
+
+    size_t liveObjectsFound = 0;
+    for (size_t i = 0; i < list.liveObjects.size(); i++) {
+        LiveObjectData& objData = list.liveObjects[i];
+        if (objData.isConfirmedDead)
+            continue; // Don't "resurrect" known dead objects.
+        if (!knownLiveSet.contains(objData.obj)) {
+            objData.isConfirmedDead = true;
+            continue;
+        }
+        liveObjectsFound++;
+    }
+    list.hasLiveObjects = !!liveObjectsFound;
+}
+
+void HeapVerifier::trimDeadObjects()
+{
+    HashSet<JSObject*> knownLiveSet;
+
+    LiveObjectList& after = currentCycle().after;
+    for (size_t i = 0; i < after.liveObjects.size(); i++) {
+        LiveObjectData& objData = after.liveObjects[i];
+        knownLiveSet.add(objData.obj);
+    }
+
+    trimDeadObjectsFromList(knownLiveSet, currentCycle().before);
+
+    for (int i = -1; i > -m_numberOfCycles; i--) {
+        trimDeadObjectsFromList(knownLiveSet, cycleForIndex(i).before);
+        trimDeadObjectsFromList(knownLiveSet, cycleForIndex(i).after);
+    }
+}
+
+bool HeapVerifier::verifyButterflyIsInStorageSpace(Phase phase, LiveObjectList& list)
+{
+    auto& liveObjects = list.liveObjects;
+
+    CopiedSpace& storageSpace = m_heap->m_storageSpace;
+    bool listNamePrinted = false;
+    bool success = true;
+    for (size_t i = 0; i < liveObjects.size(); i++) {
+        LiveObjectData& objectData = liveObjects[i];
+        if (objectData.isConfirmedDead)
+            continue;
+
+        JSObject* obj = objectData.obj;
+        Butterfly* butterfly = obj->butterfly();
+        if (butterfly) {
+            void* butterflyBase;
+            size_t butterflyCapacityInBytes;
+            CopiedBlock* butterflyBlock;
+            getButterflyDetails(obj, butterflyBase, butterflyCapacityInBytes, butterflyBlock);
+
+            if (!storageSpace.contains(butterflyBlock)) {
+                if (!listNamePrinted) {
+                    dataLogF("Verification @ phase %s FAILED in object list '%s' (size %zu)\n",
+                        phaseName(phase), list.name, liveObjects.size());
+                    listNamePrinted = true;
+                }
+
+                Structure* structure = obj->structure();
+                const char* structureClassName = structure->classInfo()->className;
+                dataLogF("    butterfly %p (base %p size %zu block %p) NOT in StorageSpace | obj %p type '%s'\n",
+                    butterfly, butterflyBase, butterflyCapacityInBytes, butterflyBlock, obj, structureClassName);
+                success = false;
+            }
+        }
+    }
+    return success;
+}
+
+void HeapVerifier::verify(HeapVerifier::Phase phase)
+{
+    bool beforeVerified = verifyButterflyIsInStorageSpace(phase, currentCycle().before);
+    bool afterVerified = verifyButterflyIsInStorageSpace(phase, currentCycle().after);
+    RELEASE_ASSERT(beforeVerified && afterVerified);
+}
+
+void HeapVerifier::reportObject(LiveObjectData& objData, int cycleIndex, HeapVerifier::GCCycle& cycle, LiveObjectList& list)
+{
+    JSObject* obj = objData.obj;
+
+    if (objData.isConfirmedDead) {
+        dataLogF("FOUND dead obj %p in GC[%d] %s list '%s'\n",
+            obj, cycleIndex, cycle.collectionTypeName(), list.name);
+        return;
+    }
+
+    Structure* structure = obj->structure();
+    Butterfly* butterfly = obj->butterfly();
+    void* butterflyBase;
+    size_t butterflyCapacityInBytes;
+    CopiedBlock* butterflyBlock;
+    getButterflyDetails(obj, butterflyBase, butterflyCapacityInBytes, butterflyBlock);
+
+    dataLogF("FOUND obj %p type '%s' butterfly %p (base %p size %zu block %p) in GC[%d] %s list '%s'\n",
+        obj, structure->classInfo()->className,
+        butterfly, butterflyBase, butterflyCapacityInBytes, butterflyBlock,
+        cycleIndex, cycle.collectionTypeName(), list.name);
+}
+
+void HeapVerifier::checkIfRecorded(JSObject* obj)
+{
+    bool found = false;
+
+    for (int cycleIndex = 0; cycleIndex > -m_numberOfCycles; cycleIndex--) {
+        GCCycle& cycle = cycleForIndex(cycleIndex);
+        LiveObjectList& beforeList = cycle.before; 
+        LiveObjectList& afterList = cycle.after; 
+
+        LiveObjectData* objData;
+        objData = beforeList.findObject(obj);
+        if (objData) {
+            reportObject(*objData, cycleIndex, cycle, beforeList);
+            found = true;
+        }
+        objData = afterList.findObject(obj);
+        if (objData) {
+            reportObject(*objData, cycleIndex, cycle, afterList);
+            found = true;
+        }
+    }
+
+    if (!found)
+        dataLogF("obj %p NOT FOUND\n", obj);
+}
+
+} // namespace JSC
diff --git a/Source/JavaScriptCore/heap/HeapVerifier.h b/Source/JavaScriptCore/heap/HeapVerifier.h
new file mode 100644 (file)
index 0000000..f6ec1d9
--- /dev/null
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef HeapVerifier_h
+#define HeapVerifier_h
+
+#include "Heap.h"
+#include <wtf/Vector.h>
+
+namespace JSC {
+
+class JSObject;
+class MarkedBlock;
+
+struct LiveObjectData {
+    LiveObjectData(JSObject* obj, bool isConfirmedDead = false)
+        : obj(obj)
+        , isConfirmedDead(isConfirmedDead)
+    {
+    }
+
+    JSObject* obj;
+    bool isConfirmedDead;
+};
+
+struct LiveObjectList {
+    LiveObjectList(const char* name)
+        : name(name)
+        , hasLiveObjects(true)
+    {
+    }
+
+    void reset()
+    {
+        liveObjects.clear();
+        hasLiveObjects = true; // Presume to have live objects until the list is trimmed.
+    }
+
+    LiveObjectData* findObject(JSObject*);
+
+    const char* name;
+    Vector<LiveObjectData> liveObjects;
+    bool hasLiveObjects;
+};
+
+class HeapVerifier {
+public:
+    enum class Phase {
+        BeforeGC,
+        BeforeMarking,
+        AfterMarking,
+        AfterGC
+    };
+
+    HeapVerifier(Heap*, unsigned numberOfGCCyclesToRecord);
+
+    void initializeGCCycle();
+    void gatherLiveObjects(Phase);
+    void trimDeadObjects();
+    void verify(Phase);
+
+    // Scans all previously recorded LiveObjectLists and checks if the specified
+    // object was in any of those lists.
+    JS_EXPORT_PRIVATE void checkIfRecorded(JSObject*);
+
+    static const char* collectionTypeName(HeapOperation);
+    static const char* phaseName(Phase);
+
+private:
+    struct GCCycle {
+        GCCycle()
+            : before("Before Marking")
+            , after("After Marking")
+        {
+        }
+
+        HeapOperation collectionType;
+        LiveObjectList before;
+        LiveObjectList after;
+
+        const char* collectionTypeName() const
+        {
+            return HeapVerifier::collectionTypeName(collectionType);
+        }
+    };
+
+    void incrementCycle() { m_currentCycle = (m_currentCycle + 1) % m_numberOfCycles; }
+    GCCycle& currentCycle() { return m_cycles[m_currentCycle]; }
+    GCCycle& cycleForIndex(int cycleIndex)
+    {
+        ASSERT(cycleIndex <= 0 && cycleIndex > -m_numberOfCycles);
+        cycleIndex += m_currentCycle;
+        if (cycleIndex < 0)
+            cycleIndex += m_numberOfCycles;
+        ASSERT(cycleIndex < m_numberOfCycles);
+        return m_cycles[cycleIndex];
+    }
+
+    LiveObjectList* liveObjectListForGathering(Phase);
+    bool verifyButterflyIsInStorageSpace(Phase, LiveObjectList&);
+
+    static void reportObject(LiveObjectData&, int cycleIndex, HeapVerifier::GCCycle&, LiveObjectList&);
+
+    Heap* m_heap;
+    int m_currentCycle;
+    int m_numberOfCycles;
+    std::unique_ptr<GCCycle[]> m_cycles;
+};
+
+} // namespace JSC
+
+#endif // HeapVerifier
index 9c4d925..f05cea6 100644 (file)
@@ -287,6 +287,9 @@ typedef const char* optionString;
     v(bool, logHeapStatisticsAtExit, false) \
     v(bool, enableTypeProfiler, false) \
     \
+    v(bool, verifyHeap, true) \
+    v(unsigned, numberOfGCCyclesToRecordForVerification, 3) \
+    \
     v(bool, enableExceptionFuzz, false) \
     v(unsigned, fireExceptionFuzzAt, 0)