1/*
2 * Copyright (C) 2014-2019 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 "ButterflyInlines.h"
30#include "CodeBlockInlines.h"
31#include "HeapIterationScope.h"
32#include "JSCInlines.h"
33#include "JSObject.h"
34#include "MarkedSpaceInlines.h"
35#include "VMInspector.h"
36#include "ValueProfile.h"
37#include <wtf/ProcessID.h>
38
39namespace JSC {
40
41HeapVerifier::HeapVerifier(Heap* heap, unsigned numberOfGCCyclesToRecord)
42 : m_heap(heap)
43 , m_currentCycle(0)
44 , m_numberOfCycles(numberOfGCCyclesToRecord)
45{
46 RELEASE_ASSERT(m_numberOfCycles > 0);
47 m_cycles = makeUniqueArray<GCCycle>(m_numberOfCycles);
48}
49
50const char* HeapVerifier::phaseName(HeapVerifier::Phase phase)
51{
52 switch (phase) {
53 case Phase::BeforeGC:
54 return "BeforeGC";
55 case Phase::BeforeMarking:
56 return "BeforeMarking";
57 case Phase::AfterMarking:
58 return "AfterMarking";
59 case Phase::AfterGC:
60 return "AfterGC";
61 }
62 RELEASE_ASSERT_NOT_REACHED();
63 return nullptr; // Silencing a compiler warning.
64}
65
66void HeapVerifier::startGC()
67{
68 Heap* heap = m_heap;
69 incrementCycle();
70 currentCycle().reset();
71 currentCycle().scope = *heap->collectionScope();
72 currentCycle().timestamp = MonotonicTime::now();
73 ASSERT(!m_didPrintLogs);
74}
75
76void HeapVerifier::endGC()
77{
78 if (m_didPrintLogs) {
79 dataLog("END ");
80 printVerificationHeader();
81 dataLog("\n\n");
82 m_didPrintLogs = false;
83 }
84}
85
86void HeapVerifier::gatherLiveCells(HeapVerifier::Phase phase)
87{
88 Heap* heap = m_heap;
89 CellList& list = *cellListForGathering(phase);
90
91 list.reset();
92 heap->m_objectSpace.forEachLiveCell([&list] (HeapCell* cell, HeapCell::Kind kind) {
93 list.add({ cell, kind, CellProfile::Live });
94 return IterationStatus::Continue;
95 });
96}
97
98CellList* HeapVerifier::cellListForGathering(HeapVerifier::Phase phase)
99{
100 switch (phase) {
101 case Phase::BeforeMarking:
102 return &currentCycle().before;
103 case Phase::AfterMarking:
104 return &currentCycle().after;
105 case Phase::BeforeGC:
106 case Phase::AfterGC:
107 // We should not be gathering live cells during these phases.
108 break;
109 }
110 RELEASE_ASSERT_NOT_REACHED();
111 return nullptr; // Silencing a compiler warning.
112}
113
114static void trimDeadCellsFromList(CellList& knownLiveSet, CellList& list)
115{
116 if (!list.size())
117 return;
118
119 for (auto& cellProfile : list.cells()) {
120 if (cellProfile.isDead())
121 continue; // Don't "resurrect" known dead cells.
122 if (!knownLiveSet.find(cellProfile.cell())) {
123 cellProfile.setIsDead();
124 continue;
125 }
126 cellProfile.setIsLive();
127 }
128}
129
130void HeapVerifier::trimDeadCells()
131{
132 CellList& knownLiveSet = currentCycle().after;
133
134 trimDeadCellsFromList(knownLiveSet, currentCycle().before);
135
136 for (int i = -1; i > -m_numberOfCycles; i--) {
137 trimDeadCellsFromList(knownLiveSet, cycleForIndex(i).before);
138 trimDeadCellsFromList(knownLiveSet, cycleForIndex(i).after);
139 }
140}
141
142void HeapVerifier::printVerificationHeader()
143{
144 RELEASE_ASSERT(m_heap->collectionScope());
145 CollectionScope scope = currentCycle().scope;
146 MonotonicTime gcCycleTimestamp = currentCycle().timestamp;
147 dataLog("Verifying heap in [p", getCurrentProcessID(), ", ", Thread::current(), "] vm ",
148 RawPointer(&m_heap->vm()), " on ", scope, " GC @ ", gcCycleTimestamp, "\n");
149}
150
151bool HeapVerifier::verifyCellList(Phase phase, CellList& list)
152{
153 VM& vm = m_heap->vm();
154 auto& liveCells = list.cells();
155
156 bool listNamePrinted = false;
157 auto printHeaderIfNeeded = scopedLambda<void()>([&] () {
158 if (listNamePrinted)
159 return;
160
161 printVerificationHeader();
162 dataLog(" @ phase ", phaseName(phase), ": FAILED in cell list '", list.name(), "' (size ", liveCells.size(), ")\n");
163 listNamePrinted = true;
164 m_didPrintLogs = true;
165 });
166
167 bool success = true;
168 for (size_t i = 0; i < liveCells.size(); i++) {
169 CellProfile& profile = liveCells[i];
170 if (!profile.isLive())
171 continue;
172
173 if (!profile.isJSCell())
174 continue;
175
176 JSCell* cell = profile.jsCell();
177 success |= validateJSCell(&vm, cell, &profile, &list, printHeaderIfNeeded, " ");
178 }
179
180 return success;
181}
182
183bool HeapVerifier::validateCell(HeapCell* cell, VM* expectedVM)
184{
185 auto printNothing = scopedLambda<void()>([] () { });
186
187 if (cell->isZapped()) {
188 dataLog(" cell ", RawPointer(cell), " is ZAPPED\n");
189 return false;
190 }
191
192 if (!isJSCellKind(cell->cellKind()))
193 return true; // Nothing more to validate.
194
195 JSCell* jsCell = static_cast<JSCell*>(cell);
196 return validateJSCell(expectedVM, jsCell, nullptr, nullptr, printNothing);
197}
198
199bool HeapVerifier::validateJSCell(VM* expectedVM, JSCell* cell, CellProfile* profile, CellList* list, const ScopedLambda<void()>& printHeaderIfNeeded, const char* prefix)
200{
201 auto printHeaderAndCell = [cell, profile, &printHeaderIfNeeded, prefix] () {
202 printHeaderIfNeeded();
203 dataLog(prefix, "cell ", RawPointer(cell));
204 if (profile)
205 dataLog(" [", profile->className(), "]");
206 };
207
208 // 1. Validate the cell.
209
210 if (cell->isZapped()) {
211 printHeaderAndCell();
212 dataLog(" is zapped\n");
213 return false;
214 }
215
216 StructureID structureID = cell->structureID();
217 if (!structureID) {
218 printHeaderAndCell();
219 dataLog(" has NULL structureID\n");
220 return false;
221 }
222
223 if (expectedVM) {
224 VM& vm = *expectedVM;
225
226 VM* cellVM = &cell->vm();
227 if (cellVM != expectedVM) {
228 printHeaderAndCell();
229 dataLog(" is from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(cellVM), "\n");
230 return false;
231 }
232
233 // 2. Validate the cell's structure
234
235 Structure* structure = vm.getStructure(structureID);
236 if (!structure) {
237 printHeaderAndCell();
238#if USE(JSVALUE64)
239 uint32_t structureIDAsUint32 = structureID;
240#else
241 uint32_t structureIDAsUint32 = reinterpret_cast<uint32_t>(structureID);
242#endif
243 dataLog(" with structureID ", structureIDAsUint32, " maps to a NULL Structure pointer\n");
244 return false;
245 }
246
247 if (structure->isZapped()) {
248 printHeaderAndCell();
249 dataLog(" has ZAPPED structure ", RawPointer(structure), "\n");
250 return false;
251 }
252
253 if (!structure->structureID()) {
254 printHeaderAndCell();
255 dataLog(" has structure ", RawPointer(structure), " whose structureID is NULL\n");
256 return false;
257 }
258
259 VM* structureVM = &structure->vm();
260 if (structureVM != expectedVM) {
261 printHeaderAndCell();
262 dataLog(" has structure ", RawPointer(structure), " from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(structureVM), "\n");
263 return false;
264 }
265
266 if (list) {
267 auto* structureProfile = list->find(structure);
268 if (!structureProfile) {
269 printHeaderAndCell();
270 dataLog(" has structure ", RawPointer(structure), " NOT found in the live cell list\n");
271 return false;
272 }
273
274 if (!structureProfile->isLive()) {
275 printHeaderAndCell();
276 dataLog(" has DEAD structure ", RawPointer(structure), "\n");
277 return false;
278 }
279 }
280
281 StructureID structureStructureID = structure->structureID();
282 if (!structureStructureID) {
283 printHeaderAndCell();
284 dataLog(" has structure ", RawPointer(structure), " with a NULL structureID\n");
285 return false;
286 }
287
288 // 3. Validate the cell's structure's structure.
289
290 Structure* structureStructure = vm.getStructure(structureID);
291 if (!structureStructure) {
292 printHeaderAndCell();
293 dataLog(" has structure ", RawPointer(structure), " whose structure is NULL\n");
294 return false;
295 }
296
297 if (structureStructure->isZapped()) {
298 printHeaderAndCell();
299 dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is ZAPPED\n");
300 return false;
301 }
302
303 if (!structureStructure->structureID()) {
304 printHeaderAndCell();
305 dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " has a NULL structureID\n");
306 return false;
307 }
308
309 VM* structureStructureVM = &structureStructure->vm();
310 if (structureStructureVM != expectedVM) {
311 printHeaderAndCell();
312 dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is from a different VM: expected:", RawPointer(expectedVM), " actual:", RawPointer(structureStructureVM), "\n");
313 return false;
314 }
315
316 if (list) {
317 auto* structureStructureProfile = list->find(structureStructure);
318 if (!structureStructureProfile) {
319 printHeaderAndCell();
320 dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is NOT found in the live cell list\n");
321 return false;
322 }
323
324 if (!structureStructureProfile->isLive()) {
325 printHeaderAndCell();
326 dataLog(" has structure ", RawPointer(structure), " whose structure ", RawPointer(structureStructure), " is DEAD\n");
327 return false;
328 }
329 }
330
331 CodeBlock* codeBlock = jsDynamicCast<CodeBlock*>(vm, cell);
332 if (UNLIKELY(codeBlock)) {
333 bool success = true;
334 codeBlock->forEachValueProfile([&](ValueProfile& valueProfile, bool) {
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
358void 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
366void 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(vm);
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
408void HeapVerifier::checkIfRecorded(HeapCell* cell)
409{
410 bool found = false;
411 const char* const prefix = " ";
412 static constexpr 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
443void 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
468