The Tor Browser / file comparison

comparison: js/src/gc/Verifier.cpp

js/src/gc/Verifier.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:810714e10c8e
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifdef MOZ_VALGRIND
8 # include <valgrind/memcheck.h>
9 #endif
10
11 #include "jscntxt.h"
12 #include "jsgc.h"
13 #include "jsprf.h"
14
15 #include "gc/GCInternals.h"
16 #include "gc/Zone.h"
17 #include "js/GCAPI.h"
18 #include "js/HashTable.h"
19
20 #include "jscntxtinlines.h"
21 #include "jsgcinlines.h"
22
23 using namespace js;
24 using namespace js::gc;
25 using namespace mozilla;
26
27 #ifdef JS_GC_ZEAL
28
29 /*
30 * Write barrier verification
31 *
32 * The next few functions are for write barrier verification.
33 *
34 * The VerifyBarriers function is a shorthand. It checks if a verification phase
35 * is currently running. If not, it starts one. Otherwise, it ends the current
36 * phase and starts a new one.
37 *
38 * The user can adjust the frequency of verifications, which causes
39 * VerifyBarriers to be a no-op all but one out of N calls. However, if the
40 * |always| parameter is true, it starts a new phase no matter what.
41 *
42 * Pre-Barrier Verifier:
43 * When StartVerifyBarriers is called, a snapshot is taken of all objects in
44 * the GC heap and saved in an explicit graph data structure. Later,
45 * EndVerifyBarriers traverses the heap again. Any pointer values that were in
46 * the snapshot and are no longer found must be marked; otherwise an assertion
47 * triggers. Note that we must not GC in between starting and finishing a
48 * verification phase.
49 *
50 * Post-Barrier Verifier:
51 * When StartVerifyBarriers is called, we create a virtual "Nursery Set" which
52 * future allocations are recorded in and turn on the StoreBuffer. Later,
53 * EndVerifyBarriers traverses the heap and ensures that the set of cross-
54 * generational pointers we find is a subset of the pointers recorded in our
55 * StoreBuffer.
56 */
57
58 struct EdgeValue
59 {
60 void *thing;
61 JSGCTraceKind kind;
62 const char *label;
63 };
64
65 struct VerifyNode
66 {
67 void *thing;
68 JSGCTraceKind kind;
69 uint32_t count;
70 EdgeValue edges[1];
71 };
72
73 typedef HashMap<void *, VerifyNode *, DefaultHasher<void *>, SystemAllocPolicy> NodeMap;
74
75 /*
76 * The verifier data structures are simple. The entire graph is stored in a
77 * single block of memory. At the beginning is a VerifyNode for the root
78 * node. It is followed by a sequence of EdgeValues--the exact number is given
79 * in the node. After the edges come more nodes and their edges.
80 *
81 * The edgeptr and term fields are used to allocate out of the block of memory
82 * for the graph. If we run out of memory (i.e., if edgeptr goes beyond term),
83 * we just abandon the verification.
84 *
85 * The nodemap field is a hashtable that maps from the address of the GC thing
86 * to the VerifyNode that represents it.
87 */
88 struct VerifyPreTracer : JSTracer
89 {
90 JS::AutoDisableGenerationalGC noggc;
91
92 /* The gcNumber when the verification began. */
93 uint64_t number;
94
95 /* This counts up to gcZealFrequency to decide whether to verify. */
96 int count;
97
98 /* This graph represents the initial GC "snapshot". */
99 VerifyNode *curnode;
100 VerifyNode *root;
101 char *edgeptr;
102 char *term;
103 NodeMap nodemap;
104
105 VerifyPreTracer(JSRuntime *rt, JSTraceCallback callback)
106 : JSTracer(rt, callback), noggc(rt), number(rt->gcNumber), count(0), root(nullptr)
107 {}
108
109 ~VerifyPreTracer() {
110 js_free(root);
111 }
112 };
113
114 /*
115 * This function builds up the heap snapshot by adding edges to the current
116 * node.
117 */
118 static void
119 AccumulateEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
120 {
121 VerifyPreTracer *trc = (VerifyPreTracer *)jstrc;
122
123 JS_ASSERT(!IsInsideNursery(trc->runtime(), *(uintptr_t **)thingp));
124
125 trc->edgeptr += sizeof(EdgeValue);
126 if (trc->edgeptr >= trc->term) {
127 trc->edgeptr = trc->term;
128 return;
129 }
130
131 VerifyNode *node = trc->curnode;
132 uint32_t i = node->count;
133
134 node->edges[i].thing = *thingp;
135 node->edges[i].kind = kind;
136 node->edges[i].label = trc->tracingName("<unknown>");
137 node->count++;
138 }
139
140 static VerifyNode *
141 MakeNode(VerifyPreTracer *trc, void *thing, JSGCTraceKind kind)
142 {
143 NodeMap::AddPtr p = trc->nodemap.lookupForAdd(thing);
144 if (!p) {
145 VerifyNode *node = (VerifyNode *)trc->edgeptr;
146 trc->edgeptr += sizeof(VerifyNode) - sizeof(EdgeValue);
147 if (trc->edgeptr >= trc->term) {
148 trc->edgeptr = trc->term;
149 return nullptr;
150 }
151
152 node->thing = thing;
153 node->count = 0;
154 node->kind = kind;
155 trc->nodemap.add(p, thing, node);
156 return node;
157 }
158 return nullptr;
159 }
160
161 static VerifyNode *
162 NextNode(VerifyNode *node)
163 {
164 if (node->count == 0)
165 return (VerifyNode *)((char *)node + sizeof(VerifyNode) - sizeof(EdgeValue));
166 else
167 return (VerifyNode *)((char *)node + sizeof(VerifyNode) +
168 sizeof(EdgeValue)*(node->count - 1));
169 }
170
171 void
172 gc::StartVerifyPreBarriers(JSRuntime *rt)
173 {
174 if (rt->gcVerifyPreData || rt->gcIncrementalState != NO_INCREMENTAL)
175 return;
176
177 /*
178 * The post barrier verifier requires the storebuffer to be enabled, but the
179 * pre barrier verifier disables it as part of disabling GGC. Don't allow
180 * starting the pre barrier verifier if the post barrier verifier is already
181 * running.
182 */
183 if (rt->gcVerifyPostData)
184 return;
185
186 MinorGC(rt, JS::gcreason::EVICT_NURSERY);
187
188 AutoPrepareForTracing prep(rt, WithAtoms);
189
190 if (!IsIncrementalGCSafe(rt))
191 return;
192
193 for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront())
194 r.front()->bitmap.clear();
195
196 rt->gcNumber++;
197
198 VerifyPreTracer *trc = js_new<VerifyPreTracer>(rt, JSTraceCallback(nullptr));
199 if (!trc)
200 return;
201
202 /*
203 * Passing a function pointer directly to js_new trips a compiler bug in
204 * MSVC. Work around by filling the pointer after allocating with nullptr.
205 */
206 trc->setTraceCallback(AccumulateEdge);
207
208 const size_t size = 64 * 1024 * 1024;
209 trc->root = (VerifyNode *)js_malloc(size);
210 if (!trc->root)
211 goto oom;
212 trc->edgeptr = (char *)trc->root;
213 trc->term = trc->edgeptr + size;
214
215 if (!trc->nodemap.init())
216 goto oom;
217
218 /* Create the root node. */
219 trc->curnode = MakeNode(trc, nullptr, JSGCTraceKind(0));
220
221 /* We want MarkRuntime to save the roots to gcSavedRoots. */
222 rt->gcIncrementalState = MARK_ROOTS;
223
224 /* Make all the roots be edges emanating from the root node. */
225 MarkRuntime(trc);
226
227 VerifyNode *node;
228 node = trc->curnode;
229 if (trc->edgeptr == trc->term)
230 goto oom;
231
232 /* For each edge, make a node for it if one doesn't already exist. */
233 while ((char *)node < trc->edgeptr) {
234 for (uint32_t i = 0; i < node->count; i++) {
235 EdgeValue &e = node->edges[i];
236 VerifyNode *child = MakeNode(trc, e.thing, e.kind);
237 if (child) {
238 trc->curnode = child;
239 JS_TraceChildren(trc, e.thing, e.kind);
240 }
241 if (trc->edgeptr == trc->term)
242 goto oom;
243 }
244
245 node = NextNode(node);
246 }
247
248 rt->gcVerifyPreData = trc;
249 rt->gcIncrementalState = MARK;
250 rt->gcMarker.start();
251
252 rt->setNeedsBarrier(true);
253 for (ZonesIter zone(rt, WithAtoms); !zone.done(); zone.next()) {
254 PurgeJITCaches(zone);
255 zone->setNeedsBarrier(true, Zone::UpdateIon);
256 zone->allocator.arenas.purge();
257 }
258
259 return;
260
261 oom:
262 rt->gcIncrementalState = NO_INCREMENTAL;
263 js_delete(trc);
264 rt->gcVerifyPreData = nullptr;
265 }
266
267 static bool
268 IsMarkedOrAllocated(Cell *cell)
269 {
270 return cell->isMarked() || cell->arenaHeader()->allocatedDuringIncremental;
271 }
272
273 static const uint32_t MAX_VERIFIER_EDGES = 1000;
274
275 /*
276 * This function is called by EndVerifyBarriers for every heap edge. If the edge
277 * already existed in the original snapshot, we "cancel it out" by overwriting
278 * it with nullptr. EndVerifyBarriers later asserts that the remaining
279 * non-nullptr edges (i.e., the ones from the original snapshot that must have
280 * been modified) must point to marked objects.
281 */
282 static void
283 CheckEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
284 {
285 VerifyPreTracer *trc = (VerifyPreTracer *)jstrc;
286 VerifyNode *node = trc->curnode;
287
288 /* Avoid n^2 behavior. */
289 if (node->count > MAX_VERIFIER_EDGES)
290 return;
291
292 for (uint32_t i = 0; i < node->count; i++) {
293 if (node->edges[i].thing == *thingp) {
294 JS_ASSERT(node->edges[i].kind == kind);
295 node->edges[i].thing = nullptr;
296 return;
297 }
298 }
299 }
300
301 static void
302 AssertMarkedOrAllocated(const EdgeValue &edge)
303 {
304 if (!edge.thing || IsMarkedOrAllocated(static_cast<Cell *>(edge.thing)))
305 return;
306
307 // Permanent atoms aren't marked during graph traversal.
308 if (edge.kind == JSTRACE_STRING && static_cast<JSString *>(edge.thing)->isPermanentAtom())
309 return;
310
311 char msgbuf[1024];
312 const char *label = edge.label;
313
314 JS_snprintf(msgbuf, sizeof(msgbuf), "[barrier verifier] Unmarked edge: %s", label);
315 MOZ_ReportAssertionFailure(msgbuf, __FILE__, __LINE__);
316 MOZ_CRASH();
317 }
318
319 void
320 gc::EndVerifyPreBarriers(JSRuntime *rt)
321 {
322 JS_ASSERT(!JS::IsGenerationalGCEnabled(rt));
323
324 AutoPrepareForTracing prep(rt, SkipAtoms);
325
326 VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData;
327
328 if (!trc)
329 return;
330
331 bool compartmentCreated = false;
332
333 /* We need to disable barriers before tracing, which may invoke barriers. */
334 for (ZonesIter zone(rt, WithAtoms); !zone.done(); zone.next()) {
335 if (!zone->needsBarrier())
336 compartmentCreated = true;
337
338 zone->setNeedsBarrier(false, Zone::UpdateIon);
339 PurgeJITCaches(zone);
340 }
341 rt->setNeedsBarrier(false);
342
343 /*
344 * We need to bump gcNumber so that the methodjit knows that jitcode has
345 * been discarded.
346 */
347 JS_ASSERT(trc->number == rt->gcNumber);
348 rt->gcNumber++;
349
350 rt->gcVerifyPreData = nullptr;
351 rt->gcIncrementalState = NO_INCREMENTAL;
352
353 if (!compartmentCreated && IsIncrementalGCSafe(rt)) {
354 trc->setTraceCallback(CheckEdge);
355
356 /* Start after the roots. */
357 VerifyNode *node = NextNode(trc->root);
358 while ((char *)node < trc->edgeptr) {
359 trc->curnode = node;
360 JS_TraceChildren(trc, node->thing, node->kind);
361
362 if (node->count <= MAX_VERIFIER_EDGES) {
363 for (uint32_t i = 0; i < node->count; i++)
364 AssertMarkedOrAllocated(node->edges[i]);
365 }
366
367 node = NextNode(node);
368 }
369 }
370
371 rt->gcMarker.reset();
372 rt->gcMarker.stop();
373
374 js_delete(trc);
375 }
376
377 /*** Post-Barrier Verifyier ***/
378
379 struct VerifyPostTracer : JSTracer
380 {
381 /* The gcNumber when the verification began. */
382 uint64_t number;
383
384 /* This counts up to gcZealFrequency to decide whether to verify. */
385 int count;
386
387 /* The set of edges in the StoreBuffer at the end of verification. */
388 typedef HashSet<void **, PointerHasher<void **, 3>, SystemAllocPolicy> EdgeSet;
389 EdgeSet *edges;
390
391 VerifyPostTracer(JSRuntime *rt, JSTraceCallback callback)
392 : JSTracer(rt, callback), number(rt->gcNumber), count(0)
393 {}
394 };
395
396 /*
397 * The post-barrier verifier runs the full store buffer and a fake nursery when
398 * running and when it stops, walks the full heap to ensure that all the
399 * important edges were inserted into the storebuffer.
400 */
401 void
402 gc::StartVerifyPostBarriers(JSRuntime *rt)
403 {
404 #ifdef JSGC_GENERATIONAL
405 if (rt->gcVerifyPostData ||
406 rt->gcIncrementalState != NO_INCREMENTAL)
407 {
408 return;
409 }
410
411 MinorGC(rt, JS::gcreason::EVICT_NURSERY);
412
413 rt->gcNumber++;
414
415 VerifyPostTracer *trc = js_new<VerifyPostTracer>(rt, JSTraceCallback(nullptr));
416 if (!trc)
417 return;
418
419 rt->gcVerifyPostData = trc;
420 #endif
421 }
422
423 #ifdef JSGC_GENERATIONAL
424 void
425 PostVerifierCollectStoreBufferEdges(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
426 {
427 VerifyPostTracer *trc = (VerifyPostTracer *)jstrc;
428
429 /* The nursery only stores objects. */
430 if (kind != JSTRACE_OBJECT)
431 return;
432
433 /* The store buffer may store extra, non-cross-generational edges. */
434 JSObject *dst = *reinterpret_cast<JSObject **>(thingp);
435 if (trc->runtime()->gcNursery.isInside(thingp) || !trc->runtime()->gcNursery.isInside(dst))
436 return;
437
438 /*
439 * Values will be unpacked to the stack before getting here. However, the
440 * only things that enter this callback are marked by the store buffer. The
441 * store buffer ensures that the real tracing location is set correctly.
442 */
443 void **loc = trc->tracingLocation(thingp);
444
445 trc->edges->put(loc);
446 }
447
448 static void
449 AssertStoreBufferContainsEdge(VerifyPostTracer::EdgeSet *edges, void **loc, JSObject *dst)
450 {
451 if (edges->has(loc))
452 return;
453
454 char msgbuf[1024];
455 JS_snprintf(msgbuf, sizeof(msgbuf), "[post-barrier verifier] Missing edge @ %p to %p",
456 (void *)loc, (void *)dst);
457 MOZ_ReportAssertionFailure(msgbuf, __FILE__, __LINE__);
458 MOZ_CRASH();
459 }
460
461 void
462 PostVerifierVisitEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
463 {
464 VerifyPostTracer *trc = (VerifyPostTracer *)jstrc;
465
466 /* The nursery only stores objects. */
467 if (kind != JSTRACE_OBJECT)
468 return;
469
470 /* Filter out non cross-generational edges. */
471 JS_ASSERT(!trc->runtime()->gcNursery.isInside(thingp));
472 JSObject *dst = *reinterpret_cast<JSObject **>(thingp);
473 if (!trc->runtime()->gcNursery.isInside(dst))
474 return;
475
476 /*
477 * Values will be unpacked to the stack before getting here. However, the
478 * only things that enter this callback are marked by the JS_TraceChildren
479 * below. Since ObjectImpl::markChildren handles this, the real trace
480 * location will be set correctly in these cases.
481 */
482 void **loc = trc->tracingLocation(thingp);
483
484 AssertStoreBufferContainsEdge(trc->edges, loc, dst);
485 }
486 #endif
487
488 void
489 js::gc::EndVerifyPostBarriers(JSRuntime *rt)
490 {
491 #ifdef JSGC_GENERATIONAL
492 VerifyPostTracer::EdgeSet edges;
493 AutoPrepareForTracing prep(rt, SkipAtoms);
494
495 VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData;
496
497 /* Visit every entry in the store buffer and put the edges in a hash set. */
498 trc->setTraceCallback(PostVerifierCollectStoreBufferEdges);
499 if (!edges.init())
500 goto oom;
501 trc->edges = &edges;
502 rt->gcStoreBuffer.markAll(trc);
503
504 /* Walk the heap to find any edges not the the |edges| set. */
505 trc->setTraceCallback(PostVerifierVisitEdge);
506 for (GCZoneGroupIter zone(rt); !zone.done(); zone.next()) {
507 for (size_t kind = 0; kind < FINALIZE_LIMIT; ++kind) {
508 for (CellIterUnderGC cells(zone, AllocKind(kind)); !cells.done(); cells.next()) {
509 Cell *src = cells.getCell();
510 JS_TraceChildren(trc, src, MapAllocToTraceKind(AllocKind(kind)));
511 }
512 }
513 }
514
515 oom:
516 js_delete(trc);
517 rt->gcVerifyPostData = nullptr;
518 #endif
519 }
520
521 /*** Barrier Verifier Scheduling ***/
522
523 static void
524 VerifyPreBarriers(JSRuntime *rt)
525 {
526 if (rt->gcVerifyPreData)
527 EndVerifyPreBarriers(rt);
528 else
529 StartVerifyPreBarriers(rt);
530 }
531
532 static void
533 VerifyPostBarriers(JSRuntime *rt)
534 {
535 if (rt->gcVerifyPostData)
536 EndVerifyPostBarriers(rt);
537 else
538 StartVerifyPostBarriers(rt);
539 }
540
541 void
542 gc::VerifyBarriers(JSRuntime *rt, VerifierType type)
543 {
544 if (type == PreBarrierVerifier)
545 VerifyPreBarriers(rt);
546 else
547 VerifyPostBarriers(rt);
548 }
549
550 static void
551 MaybeVerifyPreBarriers(JSRuntime *rt, bool always)
552 {
553 if (rt->gcZeal() != ZealVerifierPreValue)
554 return;
555
556 if (rt->mainThread.suppressGC)
557 return;
558
559 if (VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData) {
560 if (++trc->count < rt->gcZealFrequency && !always)
561 return;
562
563 EndVerifyPreBarriers(rt);
564 }
565
566 StartVerifyPreBarriers(rt);
567 }
568
569 static void
570 MaybeVerifyPostBarriers(JSRuntime *rt, bool always)
571 {
572 #ifdef JSGC_GENERATIONAL
573 if (rt->gcZeal() != ZealVerifierPostValue)
574 return;
575
576 if (rt->mainThread.suppressGC || !rt->gcStoreBuffer.isEnabled())
577 return;
578
579 if (VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData) {
580 if (++trc->count < rt->gcZealFrequency && !always)
581 return;
582
583 EndVerifyPostBarriers(rt);
584 }
585 StartVerifyPostBarriers(rt);
586 #endif
587 }
588
589 void
590 js::gc::MaybeVerifyBarriers(JSContext *cx, bool always)
591 {
592 MaybeVerifyPreBarriers(cx->runtime(), always);
593 MaybeVerifyPostBarriers(cx->runtime(), always);
594 }
595
596 void
597 js::gc::FinishVerifier(JSRuntime *rt)
598 {
599 if (VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData) {
600 js_delete(trc);
601 rt->gcVerifyPreData = nullptr;
602 }
603 #ifdef JSGC_GENERATIONAL
604 if (VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData) {
605 js_delete(trc);
606 rt->gcVerifyPostData = nullptr;
607 }
608 #endif
609 }
610
611 #endif /* JS_GC_ZEAL */

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial