WTF shouldn't have both Thread and ThreadIdentifier
[WebKit.git] / Source / JavaScriptCore / tools / HeapVerifier.cpp
1 /*
2  * Copyright (C) 2014-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "HeapVerifier.h"
28
29 #include "CodeBlock.h"
30 #include "HeapIterationScope.h"
31 #include "JSCInlines.h"
32 #include "JSObject.h"
33 #include "MarkedSpaceInlines.h"
34 #include "VMInspector.h"
35 #include "ValueProfile.h"
36 #include <wtf/ProcessID.h>
37
38 namespace JSC {
39
40 HeapVerifier::HeapVerifier(Heap* heap, unsigned numberOfGCCyclesToRecord)
41     : m_heap(heap)
42     , m_currentCycle(0)
43     , m_numberOfCycles(numberOfGCCyclesToRecord)
44 {
45     RELEASE_ASSERT(m_numberOfCycles > 0);
46     m_cycles = std::make_unique<GCCycle[]>(m_numberOfCycles);
47 }
48
49 const char* HeapVerifier::phaseName(HeapVerifier::Phase phase)
50 {
51     switch (phase) {
52     case Phase::BeforeGC:
53         return "BeforeGC";
54     case Phase::BeforeMarking:
55         return "BeforeMarking";
56     case Phase::AfterMarking:
57         return "AfterMarking";
58     case Phase::AfterGC:
59         return "AfterGC";
60     }
61     RELEASE_ASSERT_NOT_REACHED();
62     return nullptr; // Silencing a compiler warning.
63 }
64
65 void HeapVerifier::startGC()
66 {
67     Heap* heap = m_heap;
68     incrementCycle();
69     currentCycle().reset();
70     currentCycle().scope = *heap->collectionScope();
71     currentCycle().timestamp = MonotonicTime::now();
72     ASSERT(!m_didPrintLogs);
73 }
74
75 void HeapVerifier::endGC()
76 {
77     if (m_didPrintLogs) {
78         dataLog("END ");
79         printVerificationHeader();
80         dataLog("\n\n");
81         m_didPrintLogs = false;
82     }
83 }
84
85 void HeapVerifier::gatherLiveCells(HeapVerifier::Phase phase)
86 {
87     Heap* heap = m_heap;
88     CellList& list = *cellListForGathering(phase);
89
90     list.reset();
91     heap->m_objectSpace.forEachLiveCell([&list] (HeapCell* cell, HeapCell::Kind kind) {
92         list.add({ cell, kind, CellProfile::Live });
93         return IterationStatus::Continue;
94     });
95 }
96
97 CellList* HeapVerifier::cellListForGathering(HeapVerifier::Phase phase)
98 {
99     switch (phase) {
100     case Phase::BeforeMarking:
101         return &currentCycle().before;
102     case Phase::AfterMarking:
103         return &currentCycle().after;
104     case Phase::BeforeGC:
105     case Phase::AfterGC:
106         // We should not be gathering live cells during these phases.
107         break;
108     }
109     RELEASE_ASSERT_NOT_REACHED();
110     return nullptr; // Silencing a compiler warning.
111 }
112
113 static void trimDeadCellsFromList(CellList& knownLiveSet, CellList& list)
114 {
115     if (!list.size())
116         return;
117
118     for (auto& cellProfile : list.cells()) {
119         if (cellProfile.isDead())
120             continue; // Don't "resurrect" known dead cells.
121         if (!knownLiveSet.find(cellProfile.cell())) {
122             cellProfile.setIsDead();
123             continue;
124         }
125         cellProfile.setIsLive();
126     }
127 }
128
129 void HeapVerifier::trimDeadCells()
130 {
131     CellList& knownLiveSet = currentCycle().after;
132
133     trimDeadCellsFromList(knownLiveSet, currentCycle().before);
134
135     for (int i = -1; i > -m_numberOfCycles; i--) {
136         trimDeadCellsFromList(knownLiveSet, cycleForIndex(i).before);
137         trimDeadCellsFromList(knownLiveSet, cycleForIndex(i).after);
138     }
139 }
140
141 void HeapVerifier::printVerificationHeader()
142 {
143     RELEASE_ASSERT(m_heap->collectionScope());
144     CollectionScope scope = currentCycle().scope;
145     MonotonicTime gcCycleTimestamp = currentCycle().timestamp;
146     dataLog("Verifying heap in [p", getCurrentProcessID(), ", ", Thread::current(), "] vm ",
147         RawPointer(m_heap->vm()), " on ", scope, " GC @ ", gcCycleTimestamp, "\n");
148 }
149
150 bool HeapVerifier::verifyCellList(Phase phase, CellList& list)
151 {
152     VM& vm = *m_heap->vm();
153     auto& liveCells = list.cells();
154
155     bool listNamePrinted = false;
156     auto printHeaderIfNeeded = [&] () {
157         if (listNamePrinted)
158             return;
159         
160         printVerificationHeader();
161         dataLog(" @ phase ", phaseName(phase), ": FAILED in cell list '", list.name(), "' (size ", liveCells.size(), ")\n");
162         listNamePrinted = true;
163         m_didPrintLogs = true;
164     };
165     
166     bool success = true;
167     for (size_t i = 0; i < liveCells.size(); i++) {
168         CellProfile& profile = liveCells[i];
169         if (!profile.isLive())
170             continue;
171
172         if (!profile.isJSCell())
173             continue;
174
175         JSCell* cell = profile.jsCell();
176         success |= validateJSCell(&vm, cell, &profile, &list, printHeaderIfNeeded, "  ");
177     }
178
179     return success;
180 }
181
182 bool HeapVerifier::validateCell(HeapCell* cell, VM* expectedVM)
183 {
184     auto printNothing = [] () { };
185
186     if (cell->isZapped()) {
187         dataLog("    cell ", RawPointer(cell), " is ZAPPED\n");
188         return false;
189     }
190
191     if (cell->cellKind() != HeapCell::JSCell)
192         return true; // Nothing more to validate.
193
194     JSCell* jsCell = static_cast<JSCell*>(cell);
195     return validateJSCell(expectedVM, jsCell, nullptr, nullptr, printNothing);
196 }
197
198 bool HeapVerifier::validateJSCell(VM* expectedVM, JSCell* cell, CellProfile* profile, CellList* list, std::function<void()> printHeaderIfNeeded, const char* prefix)
199 {
200     auto printHeaderAndCell = [cell, profile, printHeaderIfNeeded, prefix] () {
201         printHeaderIfNeeded();
202         dataLog(prefix, "cell ", RawPointer(cell));
203         if (profile)
204             dataLog(" [", profile->className(), "]");
205     };
206
207     // 1. Validate the cell.
208
209     if (cell->isZapped()) {
210         printHeaderAndCell();
211         dataLog(" is zapped\n");
212         return false;
213     }
214
215     StructureID structureID = cell->structureID();
216     if (!structureID) {
217         printHeaderAndCell();
218         dataLog(" has NULL structureID\n");
219         return false;
220     }
221
222     if (expectedVM) {
223         VM& vm = *expectedVM;
224
225         VM* cellVM = cell->vm();
226         if (cellVM != expectedVM) {
227             printHeaderAndCell();
228             dataLog(" is from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(cellVM), "\n");
229             return false;
230         }
231
232         // 2. Validate the cell's structure
233
234         Structure* structure = vm.getStructure(structureID);
235         if (!structure) {
236             printHeaderAndCell();
237 #if USE(JSVALUE64)
238             uint32_t structureIDAsUint32 = structureID;
239 #else
240             uint32_t structureIDAsUint32 = reinterpret_cast<uint32_t>(structureID);
241 #endif
242             dataLog(" with structureID ", structureIDAsUint32, " maps to a NULL Structure pointer\n");
243             return false;
244         }
245
246         if (structure->isZapped()) {
247             printHeaderAndCell();
248             dataLog(" has ZAPPED structure ", RawPointer(structure), "\n");
249             return false;
250         }
251
252         if (!structure->structureID()) {
253             printHeaderAndCell();
254             dataLog(" has structure ", RawPointer(structure), " whose structureID is NULL\n");
255             return false;
256         }
257
258         VM* structureVM = structure->vm();
259         if (structureVM != expectedVM) {
260             printHeaderAndCell();
261             dataLog(" has structure ", RawPointer(structure), " from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(structureVM), "\n");
262             return false;
263         }
264
265         if (list) {
266             auto* structureProfile = list->find(structure);
267             if (!structureProfile) {
268                 printHeaderAndCell();
269                 dataLog(" has structure ", RawPointer(structure), " NOT found in the live cell list\n");
270                 return false;
271             }
272
273             if (!structureProfile->isLive()) {
274                 printHeaderAndCell();
275                 dataLog(" has DEAD structure ", RawPointer(structure), "\n");
276                 return false;
277             }
278         }
279
280         StructureID structureStructureID = structure->structureID();
281         if (!structureStructureID) {
282             printHeaderAndCell();
283             dataLog(" has structure ", RawPointer(structure), " with a NULL structureID\n");
284             return false;
285         }
286
287         // 3. Validate the cell's structure's structure.
288         
289         Structure* structureStructure = vm.getStructure(structureID);
290         if (!structureStructure) {
291             printHeaderAndCell();
292             dataLog(" has structure ", RawPointer(structure), " whose structure is NULL\n");
293             return false;
294         }
295         
296         if (structureStructure->isZapped()) {
297             printHeaderAndCell();
298             dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is ZAPPED\n");
299             return false;
300         }
301         
302         if (!structureStructure->structureID()) {
303             printHeaderAndCell();
304             dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " has a NULL structureID\n");
305             return false;
306         }
307         
308         VM* structureStructureVM = structureStructure->vm();
309         if (structureStructureVM != expectedVM) {
310             printHeaderAndCell();
311             dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(structureStructureVM), "\n");
312             return false;
313         }
314         
315         if (list) {
316             auto* structureStructureProfile = list->find(structureStructure);
317             if (!structureStructureProfile) {
318                 printHeaderAndCell();
319                 dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is NOT found in the live cell list\n");
320                 return false;
321             }
322             
323             if (!structureStructureProfile->isLive()) {
324                 printHeaderAndCell();
325                 dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is DEAD\n");
326                 return false;
327             }
328         }
329         
330         CodeBlock* codeBlock = jsDynamicCast<CodeBlock*>(vm, cell);
331         if (UNLIKELY(codeBlock)) {
332             bool success = true;
333             for (unsigned i = 0; i < codeBlock->totalNumberOfValueProfiles(); ++i) {
334                 ValueProfile& valueProfile = codeBlock->getFromAllValueProfiles(i);
335                 for (unsigned i = 0; i < ValueProfile::totalNumberOfBuckets; ++i) {
336                     JSValue value = JSValue::decode(valueProfile.m_buckets[i]);
337                     if (!value)
338                         continue;
339                     if (!value.isCell())
340                         continue;
341                     JSCell* valueCell = value.asCell();
342                     if (valueCell->isZapped()) {
343                         printHeaderIfNeeded();
344                         dataLog(prefix, "CodeBlock ", RawPointer(codeBlock), " has ZAPPED ValueProfile cell ", RawPointer(valueCell), "\n");
345                         success = false;
346                         continue;
347                     }
348                 }
349             }
350             if (!success)
351                 return false;
352         }
353     }
354
355     return true;
356 }
357
358 void HeapVerifier::verify(HeapVerifier::Phase phase)
359 {
360     if (phase == Phase::AfterGC) {
361         bool verified = verifyCellList(phase, currentCycle().after);
362         RELEASE_ASSERT(verified);
363     }
364 }
365
366 void HeapVerifier::reportCell(CellProfile& profile, int cycleIndex, HeapVerifier::GCCycle& cycle, CellList& list, const char* prefix)
367 {
368     HeapCell* cell = profile.cell();
369     VM* vm = m_heap->vm();
370
371     if (prefix)
372         dataLog(prefix);
373
374     dataLog("FOUND");
375     if (profile.isLive())
376         dataLog(" LIVE");
377     else if (profile.isDead())
378         dataLog(" DEAD");
379
380     if (!profile.isJSCell())
381         dataLog(" HeapCell ");
382     else
383         dataLog(" JSCell ");
384     dataLog(RawPointer(cell));
385
386     if (profile.className())
387         dataLog(" [", profile.className(), "]");
388
389     if (profile.isLive() && profile.isJSCell()) {
390         JSCell* jsCell = profile.jsCell();
391         Structure* structure = jsCell->structure();
392         dataLog(" structure:", RawPointer(structure));
393         if (jsCell->isObject()) {
394             JSObject* obj = static_cast<JSObject*>(cell);
395             Butterfly* butterfly = obj->butterfly();
396             void* butterflyBase = butterfly->base(structure);
397             
398             dataLog(" butterfly:", RawPointer(butterfly), " (base:", RawPointer(butterflyBase), ")");
399         }
400     }
401
402     dataLog(" in ", cycle.scope, " GC[", cycleIndex, "] in '", list.name(), "' list in VM ",
403         RawPointer(vm), " recorded at time ", profile.timestamp(), "\n");
404     if (profile.stackTrace())
405         dataLog(*profile.stackTrace());
406 }
407
408 void HeapVerifier::checkIfRecorded(HeapCell* cell)
409 {
410     bool found = false;
411     const char* const prefix = "  ";
412     static const bool verbose = true;
413
414     for (int cycleIndex = 0; cycleIndex > -m_numberOfCycles; cycleIndex--) {
415         GCCycle& cycle = cycleForIndex(cycleIndex);
416         CellList* lists[] = { &cycle.before, &cycle.after };
417
418         if (verbose)
419             dataLog("Checking ", cycle.scope, " GC<", cycle.timestamp, ">, cycle [", cycleIndex, "]:\n");
420         
421         const char* resultPrefix = "    ";
422         for (auto* list : lists) {
423             if (verbose)
424                 dataLog(prefix, "Cycle [", cycleIndex, "] '", list->name(), "' list: ");
425
426             CellProfile* profile = list->find(cell);
427             if (profile) {
428                 reportCell(*profile, cycleIndex, cycle, *list, resultPrefix);
429                 found = true;
430             } else if (verbose)
431                 dataLog(resultPrefix, "cell NOT found\n");
432         }
433     }
434
435     if (!found)
436         dataLog(prefix, "cell ", RawPointer(cell), " NOT FOUND\n");
437 }
438
439 // The following are slower but more robust versions of the corresponding functions of the same name.
440 // These robust versions are designed so that we can call them interactively from a C++ debugger
441 // to query if a candidate is recorded cell.
442
443 void HeapVerifier::checkIfRecorded(uintptr_t candidateCell)
444 {
445     HeapCell* candidateHeapCell = reinterpret_cast<HeapCell*>(candidateCell);
446     
447     VMInspector& inspector = VMInspector::instance();
448     auto expectedLocker = inspector.lock(Seconds(2));
449     if (!expectedLocker) {
450         ASSERT(expectedLocker.error() == VMInspector::Error::TimedOut);
451         dataLog("ERROR: Timed out while waiting to iterate VMs.");
452         return;
453     }
454
455     auto& locker = expectedLocker.value();
456     inspector.iterate(locker, [&] (VM& vm) {
457         if (!vm.heap.m_verifier)
458             return VMInspector::FunctorStatus::Continue;
459         
460         auto* verifier = vm.heap.m_verifier.get();
461         dataLog("Search for cell ", RawPointer(candidateHeapCell), " in VM ", RawPointer(&vm), ":\n");
462         verifier->checkIfRecorded(candidateHeapCell);
463         return VMInspector::FunctorStatus::Continue;
464     });
465 }
466
467 } // namespace JSC