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 "CodeBlockInlines.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
38namespace JSC {
39
40HeapVerifier::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 = makeUniqueArray<GCCycle>(m_numberOfCycles);
47}
48
49const 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
65void 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
75void HeapVerifier::endGC()
76{
77 if (m_didPrintLogs) {
78 dataLog("END ");
79 printVerificationHeader();
80 dataLog("\n\n");
81 m_didPrintLogs = false;
82 }
83}
84
85void 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
97CellList* 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
113static 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
129void 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
141void 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
150bool 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 = scopedLambda<void()>([&] () {
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
182bool HeapVerifier::validateCell(HeapCell* cell, VM* expectedVM)
183{
184 auto printNothing = scopedLambda<void()>([] () { });
185
186 if (cell->isZapped()) {
187 dataLog(" cell ", RawPointer(cell), " is ZAPPED\n");
188 return false;
189 }
190
191 if (!isJSCellKind(cell->cellKind()))
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
198bool HeapVerifier::validateJSCell(VM* expectedVM, JSCell* cell, CellProfile* profile, CellList* list, const ScopedLambda<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 codeBlock->forEachValueProfile([&](ValueProfile& valueProfile) {
334 for (unsigned i = 0; i < ValueProfile::totalNumberOfBuckets; ++i) {
335 JSValue value = JSValue::decode(valueProfile.m_buckets[i]);
336 if (!value)
337 continue;
338 if (!value.isCell())
339 continue;
340 JSCell* valueCell = value.asCell();
341 if (valueCell->isZapped()) {
342 printHeaderIfNeeded();
343 dataLog(prefix, "CodeBlock ", RawPointer(codeBlock), " has ZAPPED ValueProfile cell ", RawPointer(valueCell), "\n");
344 success = false;
345 continue;
346 }
347 }
348 });
349 if (!success)
350 return false;
351 }
352 }
353
354 return true;
355}
356
357void HeapVerifier::verify(HeapVerifier::Phase phase)
358{
359 if (phase == Phase::AfterGC) {
360 bool verified = verifyCellList(phase, currentCycle().after);
361 RELEASE_ASSERT(verified);
362 }
363}
364
365void HeapVerifier::reportCell(CellProfile& profile, int cycleIndex, HeapVerifier::GCCycle& cycle, CellList& list, const char* prefix)
366{
367 HeapCell* cell = profile.cell();
368 VM* vm = m_heap->vm();
369
370 if (prefix)
371 dataLog(prefix);
372
373 dataLog("FOUND");
374 if (profile.isLive())
375 dataLog(" LIVE");
376 else if (profile.isDead())
377 dataLog(" DEAD");
378
379 if (!profile.isJSCell())
380 dataLog(" HeapCell ");
381 else
382 dataLog(" JSCell ");
383 dataLog(RawPointer(cell));
384
385 if (profile.className())
386 dataLog(" [", profile.className(), "]");
387
388 if (profile.isLive() && profile.isJSCell()) {
389 JSCell* jsCell = profile.jsCell();
390 Structure* structure = jsCell->structure(*vm);
391 dataLog(" structure:", RawPointer(structure));
392 if (jsCell->isObject()) {
393 JSObject* obj = static_cast<JSObject*>(cell);
394 Butterfly* butterfly = obj->butterfly();
395 void* butterflyBase = butterfly->base(structure);
396
397 dataLog(" butterfly:", RawPointer(butterfly), " (base:", RawPointer(butterflyBase), ")");
398 }
399 }
400
401 dataLog(" in ", cycle.scope, " GC[", cycleIndex, "] in '", list.name(), "' list in VM ",
402 RawPointer(vm), " recorded at time ", profile.timestamp(), "\n");
403 if (profile.stackTrace())
404 dataLog(*profile.stackTrace());
405}
406
407void HeapVerifier::checkIfRecorded(HeapCell* cell)
408{
409 bool found = false;
410 const char* const prefix = " ";
411 static const bool verbose = true;
412
413 for (int cycleIndex = 0; cycleIndex > -m_numberOfCycles; cycleIndex--) {
414 GCCycle& cycle = cycleForIndex(cycleIndex);
415 CellList* lists[] = { &cycle.before, &cycle.after };
416
417 if (verbose)
418 dataLog("Checking ", cycle.scope, " GC<", cycle.timestamp, ">, cycle [", cycleIndex, "]:\n");
419
420 const char* resultPrefix = " ";
421 for (auto* list : lists) {
422 if (verbose)
423 dataLog(prefix, "Cycle [", cycleIndex, "] '", list->name(), "' list: ");
424
425 CellProfile* profile = list->find(cell);
426 if (profile) {
427 reportCell(*profile, cycleIndex, cycle, *list, resultPrefix);
428 found = true;
429 } else if (verbose)
430 dataLog(resultPrefix, "cell NOT found\n");
431 }
432 }
433
434 if (!found)
435 dataLog(prefix, "cell ", RawPointer(cell), " NOT FOUND\n");
436}
437
438// The following are slower but more robust versions of the corresponding functions of the same name.
439// These robust versions are designed so that we can call them interactively from a C++ debugger
440// to query if a candidate is recorded cell.
441
442void HeapVerifier::checkIfRecorded(uintptr_t candidateCell)
443{
444 HeapCell* candidateHeapCell = reinterpret_cast<HeapCell*>(candidateCell);
445
446 VMInspector& inspector = VMInspector::instance();
447 auto expectedLocker = inspector.lock(Seconds(2));
448 if (!expectedLocker) {
449 ASSERT(expectedLocker.error() == VMInspector::Error::TimedOut);
450 dataLog("ERROR: Timed out while waiting to iterate VMs.");
451 return;
452 }
453
454 auto& locker = expectedLocker.value();
455 inspector.iterate(locker, [&] (VM& vm) {
456 if (!vm.heap.m_verifier)
457 return VMInspector::FunctorStatus::Continue;
458
459 auto* verifier = vm.heap.m_verifier.get();
460 dataLog("Search for cell ", RawPointer(candidateHeapCell), " in VM ", RawPointer(&vm), ":\n");
461 verifier->checkIfRecorded(candidateHeapCell);
462 return VMInspector::FunctorStatus::Continue;
463 });
464}
465
466} // namespace JSC
467