The Tor Browser: js/src/gc/Verifier.cpp@b8a032363ba2 (annotated)

js/src/gc/Verifier.cpp@b8a032363ba2 (annotated)

js/src/gc/Verifier.cpp

Thu, 22 Jan 2015 13:21:57 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Thu, 22 Jan 2015 13:21:57 +0100
branch: TOR_BUG_9701
changeset 15: b8a032363ba2
permissions: -rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 #ifdef MOZ_VALGRIND
 # include <valgrind/memcheck.h>
 #endif
 #include "jscntxt.h"
 #include "jsgc.h"
 #include "jsprf.h"
 #include "gc/GCInternals.h"
 #include "gc/Zone.h"
 #include "js/GCAPI.h"
 #include "js/HashTable.h"
 #include "jscntxtinlines.h"
 #include "jsgcinlines.h"
 using namespace js;
 using namespace js::gc;
 using namespace mozilla;
 #ifdef JS_GC_ZEAL
 /*
  * Write barrier verification
  *
  * The next few functions are for write barrier verification.
  *
  * The VerifyBarriers function is a shorthand. It checks if a verification phase
  * is currently running. If not, it starts one. Otherwise, it ends the current
  * phase and starts a new one.
  *
  * The user can adjust the frequency of verifications, which causes
  * VerifyBarriers to be a no-op all but one out of N calls. However, if the
  * |always| parameter is true, it starts a new phase no matter what.
  *
  * Pre-Barrier Verifier:
  *   When StartVerifyBarriers is called, a snapshot is taken of all objects in
  *   the GC heap and saved in an explicit graph data structure. Later,
  *   EndVerifyBarriers traverses the heap again. Any pointer values that were in
  *   the snapshot and are no longer found must be marked; otherwise an assertion
  *   triggers. Note that we must not GC in between starting and finishing a
  *   verification phase.
  *
  * Post-Barrier Verifier:
  *   When StartVerifyBarriers is called, we create a virtual "Nursery Set" which
  *   future allocations are recorded in and turn on the StoreBuffer. Later,
  *   EndVerifyBarriers traverses the heap and ensures that the set of cross-
  *   generational pointers we find is a subset of the pointers recorded in our
  *   StoreBuffer.
  */
 struct EdgeValue
 {
     void *thing;
     JSGCTraceKind kind;
     const char *label;
 };
 struct VerifyNode
 {
     void *thing;
     JSGCTraceKind kind;
     uint32_t count;
     EdgeValue edges[1];
 };
 typedef HashMap<void *, VerifyNode *, DefaultHasher<void *>, SystemAllocPolicy> NodeMap;
 /*
  * The verifier data structures are simple. The entire graph is stored in a
  * single block of memory. At the beginning is a VerifyNode for the root
  * node. It is followed by a sequence of EdgeValues--the exact number is given
  * in the node. After the edges come more nodes and their edges.
  *
  * The edgeptr and term fields are used to allocate out of the block of memory
  * for the graph. If we run out of memory (i.e., if edgeptr goes beyond term),
  * we just abandon the verification.
  *
  * The nodemap field is a hashtable that maps from the address of the GC thing
  * to the VerifyNode that represents it.
  */
 struct VerifyPreTracer : JSTracer
 {
     JS::AutoDisableGenerationalGC noggc;
     /* The gcNumber when the verification began. */
     uint64_t number;
     /* This counts up to gcZealFrequency to decide whether to verify. */
     int count;
     /* This graph represents the initial GC "snapshot". */
     VerifyNode *curnode;
     VerifyNode *root;
     char *edgeptr;
     char *term;
     NodeMap nodemap;
     VerifyPreTracer(JSRuntime *rt, JSTraceCallback callback)
       : JSTracer(rt, callback), noggc(rt), number(rt->gcNumber), count(0), root(nullptr)
     {}
     ~VerifyPreTracer() {
         js_free(root);
     }
 };
 /*
  * This function builds up the heap snapshot by adding edges to the current
  * node.
  */
 static void
 AccumulateEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
 {
     VerifyPreTracer *trc = (VerifyPreTracer *)jstrc;
     JS_ASSERT(!IsInsideNursery(trc->runtime(), *(uintptr_t **)thingp));
     trc->edgeptr += sizeof(EdgeValue);
     if (trc->edgeptr >= trc->term) {
         trc->edgeptr = trc->term;
         return;
     }
     VerifyNode *node = trc->curnode;
     uint32_t i = node->count;
     node->edges[i].thing = *thingp;
     node->edges[i].kind = kind;
     node->edges[i].label = trc->tracingName("<unknown>");
     node->count++;
 }
 static VerifyNode *
 MakeNode(VerifyPreTracer *trc, void *thing, JSGCTraceKind kind)
 {
     NodeMap::AddPtr p = trc->nodemap.lookupForAdd(thing);
     if (!p) {
         VerifyNode *node = (VerifyNode *)trc->edgeptr;
         trc->edgeptr += sizeof(VerifyNode) - sizeof(EdgeValue);
         if (trc->edgeptr >= trc->term) {
             trc->edgeptr = trc->term;
             return nullptr;
         }
         node->thing = thing;
         node->count = 0;
         node->kind = kind;
         trc->nodemap.add(p, thing, node);
         return node;
     }
     return nullptr;
 }
 static VerifyNode *
 NextNode(VerifyNode *node)
 {
     if (node->count == 0)
         return (VerifyNode *)((char *)node + sizeof(VerifyNode) - sizeof(EdgeValue));
     else
         return (VerifyNode *)((char *)node + sizeof(VerifyNode) +
                              sizeof(EdgeValue)*(node->count - 1));
 }
 void
 gc::StartVerifyPreBarriers(JSRuntime *rt)
 {
     if (rt->gcVerifyPreData || rt->gcIncrementalState != NO_INCREMENTAL)
         return;
     /*
      * The post barrier verifier requires the storebuffer to be enabled, but the
      * pre barrier verifier disables it as part of disabling GGC.  Don't allow
      * starting the pre barrier verifier if the post barrier verifier is already
      * running.
      */
     if (rt->gcVerifyPostData)
         return;
     MinorGC(rt, JS::gcreason::EVICT_NURSERY);
     AutoPrepareForTracing prep(rt, WithAtoms);
     if (!IsIncrementalGCSafe(rt))
         return;
     for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront())
         r.front()->bitmap.clear();
     rt->gcNumber++;
     VerifyPreTracer *trc = js_new<VerifyPreTracer>(rt, JSTraceCallback(nullptr));
     if (!trc)
         return;
     /*
      * Passing a function pointer directly to js_new trips a compiler bug in
      * MSVC. Work around by filling the pointer after allocating with nullptr.
      */
     trc->setTraceCallback(AccumulateEdge);
     const size_t size = 64 * 1024 * 1024;
     trc->root = (VerifyNode *)js_malloc(size);
     if (!trc->root)
         goto oom;
     trc->edgeptr = (char *)trc->root;
     trc->term = trc->edgeptr + size;
     if (!trc->nodemap.init())
         goto oom;
     /* Create the root node. */
     trc->curnode = MakeNode(trc, nullptr, JSGCTraceKind(0));
     /* We want MarkRuntime to save the roots to gcSavedRoots. */
     rt->gcIncrementalState = MARK_ROOTS;
     /* Make all the roots be edges emanating from the root node. */
     MarkRuntime(trc);
     VerifyNode *node;
     node = trc->curnode;
     if (trc->edgeptr == trc->term)
         goto oom;
     /* For each edge, make a node for it if one doesn't already exist. */
     while ((char *)node < trc->edgeptr) {
         for (uint32_t i = 0; i < node->count; i++) {
             EdgeValue &e = node->edges[i];
             VerifyNode *child = MakeNode(trc, e.thing, e.kind);
             if (child) {
                 trc->curnode = child;
                 JS_TraceChildren(trc, e.thing, e.kind);
             }
             if (trc->edgeptr == trc->term)
                 goto oom;
         }
         node = NextNode(node);
     }
     rt->gcVerifyPreData = trc;
     rt->gcIncrementalState = MARK;
     rt->gcMarker.start();
     rt->setNeedsBarrier(true);
     for (ZonesIter zone(rt, WithAtoms); !zone.done(); zone.next()) {
         PurgeJITCaches(zone);
         zone->setNeedsBarrier(true, Zone::UpdateIon);
         zone->allocator.arenas.purge();
     }
     return;
 oom:
     rt->gcIncrementalState = NO_INCREMENTAL;
     js_delete(trc);
     rt->gcVerifyPreData = nullptr;
 }
 static bool
 IsMarkedOrAllocated(Cell *cell)
 {
     return cell->isMarked() || cell->arenaHeader()->allocatedDuringIncremental;
 }
 static const uint32_t MAX_VERIFIER_EDGES = 1000;
 /*
  * This function is called by EndVerifyBarriers for every heap edge. If the edge
  * already existed in the original snapshot, we "cancel it out" by overwriting
  * it with nullptr. EndVerifyBarriers later asserts that the remaining
  * non-nullptr edges (i.e., the ones from the original snapshot that must have
  * been modified) must point to marked objects.
  */
 static void
 CheckEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
 {
     VerifyPreTracer *trc = (VerifyPreTracer *)jstrc;
     VerifyNode *node = trc->curnode;
     /* Avoid n^2 behavior. */
     if (node->count > MAX_VERIFIER_EDGES)
         return;
     for (uint32_t i = 0; i < node->count; i++) {
         if (node->edges[i].thing == *thingp) {
             JS_ASSERT(node->edges[i].kind == kind);
             node->edges[i].thing = nullptr;
             return;
         }
     }
 }
 static void
 AssertMarkedOrAllocated(const EdgeValue &edge)
 {
     if (!edge.thing || IsMarkedOrAllocated(static_cast<Cell *>(edge.thing)))
         return;
     // Permanent atoms aren't marked during graph traversal.
     if (edge.kind == JSTRACE_STRING && static_cast<JSString *>(edge.thing)->isPermanentAtom())
         return;
     char msgbuf[1024];
     const char *label = edge.label;
     JS_snprintf(msgbuf, sizeof(msgbuf), "[barrier verifier] Unmarked edge: %s", label);
     MOZ_ReportAssertionFailure(msgbuf, __FILE__, __LINE__);
     MOZ_CRASH();
 }
 void
 gc::EndVerifyPreBarriers(JSRuntime *rt)
 {
     JS_ASSERT(!JS::IsGenerationalGCEnabled(rt));
     AutoPrepareForTracing prep(rt, SkipAtoms);
     VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData;
     if (!trc)
         return;
     bool compartmentCreated = false;
     /* We need to disable barriers before tracing, which may invoke barriers. */
     for (ZonesIter zone(rt, WithAtoms); !zone.done(); zone.next()) {
         if (!zone->needsBarrier())
             compartmentCreated = true;
         zone->setNeedsBarrier(false, Zone::UpdateIon);
         PurgeJITCaches(zone);
     }
     rt->setNeedsBarrier(false);
     /*
      * We need to bump gcNumber so that the methodjit knows that jitcode has
      * been discarded.
      */
     JS_ASSERT(trc->number == rt->gcNumber);
     rt->gcNumber++;
     rt->gcVerifyPreData = nullptr;
     rt->gcIncrementalState = NO_INCREMENTAL;
     if (!compartmentCreated && IsIncrementalGCSafe(rt)) {
         trc->setTraceCallback(CheckEdge);
         /* Start after the roots. */
         VerifyNode *node = NextNode(trc->root);
         while ((char *)node < trc->edgeptr) {
             trc->curnode = node;
             JS_TraceChildren(trc, node->thing, node->kind);
             if (node->count <= MAX_VERIFIER_EDGES) {
                 for (uint32_t i = 0; i < node->count; i++)
                     AssertMarkedOrAllocated(node->edges[i]);
             }
             node = NextNode(node);
         }
     }
     rt->gcMarker.reset();
     rt->gcMarker.stop();
     js_delete(trc);
 }
 /*** Post-Barrier Verifyier ***/
 struct VerifyPostTracer : JSTracer
 {
     /* The gcNumber when the verification began. */
     uint64_t number;
     /* This counts up to gcZealFrequency to decide whether to verify. */
     int count;
     /* The set of edges in the StoreBuffer at the end of verification. */
     typedef HashSet<void **, PointerHasher<void **, 3>, SystemAllocPolicy> EdgeSet;
     EdgeSet *edges;
     VerifyPostTracer(JSRuntime *rt, JSTraceCallback callback)
       : JSTracer(rt, callback), number(rt->gcNumber), count(0)
     {}
 };
 /*
  * The post-barrier verifier runs the full store buffer and a fake nursery when
  * running and when it stops, walks the full heap to ensure that all the
  * important edges were inserted into the storebuffer.
  */
 void
 gc::StartVerifyPostBarriers(JSRuntime *rt)
 {
 #ifdef JSGC_GENERATIONAL
     if (rt->gcVerifyPostData ||
         rt->gcIncrementalState != NO_INCREMENTAL)
     {
         return;
     }
     MinorGC(rt, JS::gcreason::EVICT_NURSERY);
     rt->gcNumber++;
     VerifyPostTracer *trc = js_new<VerifyPostTracer>(rt, JSTraceCallback(nullptr));
     if (!trc)
         return;
     rt->gcVerifyPostData = trc;
 #endif
 }
 #ifdef JSGC_GENERATIONAL
 void
 PostVerifierCollectStoreBufferEdges(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
 {
     VerifyPostTracer *trc = (VerifyPostTracer *)jstrc;
     /* The nursery only stores objects. */
     if (kind != JSTRACE_OBJECT)
         return;
     /* The store buffer may store extra, non-cross-generational edges. */
     JSObject *dst = *reinterpret_cast<JSObject **>(thingp);
     if (trc->runtime()->gcNursery.isInside(thingp) || !trc->runtime()->gcNursery.isInside(dst))
         return;
     /*
      * Values will be unpacked to the stack before getting here. However, the
      * only things that enter this callback are marked by the store buffer. The
      * store buffer ensures that the real tracing location is set correctly.
      */
     void **loc = trc->tracingLocation(thingp);
     trc->edges->put(loc);
 }
 static void
 AssertStoreBufferContainsEdge(VerifyPostTracer::EdgeSet *edges, void **loc, JSObject *dst)
 {
     if (edges->has(loc))
         return;
     char msgbuf[1024];
     JS_snprintf(msgbuf, sizeof(msgbuf), "[post-barrier verifier] Missing edge @ %p to %p",
                 (void *)loc, (void *)dst);
     MOZ_ReportAssertionFailure(msgbuf, __FILE__, __LINE__);
     MOZ_CRASH();
 }
 void
 PostVerifierVisitEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind)
 {
     VerifyPostTracer *trc = (VerifyPostTracer *)jstrc;
     /* The nursery only stores objects. */
     if (kind != JSTRACE_OBJECT)
         return;
     /* Filter out non cross-generational edges. */
     JS_ASSERT(!trc->runtime()->gcNursery.isInside(thingp));
     JSObject *dst = *reinterpret_cast<JSObject **>(thingp);
     if (!trc->runtime()->gcNursery.isInside(dst))
         return;
     /*
      * Values will be unpacked to the stack before getting here. However, the
      * only things that enter this callback are marked by the JS_TraceChildren
      * below. Since ObjectImpl::markChildren handles this, the real trace
      * location will be set correctly in these cases.
      */
     void **loc = trc->tracingLocation(thingp);
     AssertStoreBufferContainsEdge(trc->edges, loc, dst);
 }
 #endif
 void
 js::gc::EndVerifyPostBarriers(JSRuntime *rt)
 {
 #ifdef JSGC_GENERATIONAL
     VerifyPostTracer::EdgeSet edges;
     AutoPrepareForTracing prep(rt, SkipAtoms);
     VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData;
     /* Visit every entry in the store buffer and put the edges in a hash set. */
     trc->setTraceCallback(PostVerifierCollectStoreBufferEdges);
     if (!edges.init())
         goto oom;
     trc->edges = &edges;
     rt->gcStoreBuffer.markAll(trc);
     /* Walk the heap to find any edges not the the |edges| set. */
     trc->setTraceCallback(PostVerifierVisitEdge);
     for (GCZoneGroupIter zone(rt); !zone.done(); zone.next()) {
         for (size_t kind = 0; kind < FINALIZE_LIMIT; ++kind) {
             for (CellIterUnderGC cells(zone, AllocKind(kind)); !cells.done(); cells.next()) {
                 Cell *src = cells.getCell();
                 JS_TraceChildren(trc, src, MapAllocToTraceKind(AllocKind(kind)));
             }
         }
     }
 oom:
     js_delete(trc);
     rt->gcVerifyPostData = nullptr;
 #endif
 }
 /*** Barrier Verifier Scheduling ***/
 static void
 VerifyPreBarriers(JSRuntime *rt)
 {
     if (rt->gcVerifyPreData)
         EndVerifyPreBarriers(rt);
     else
         StartVerifyPreBarriers(rt);
 }
 static void
 VerifyPostBarriers(JSRuntime *rt)
 {
     if (rt->gcVerifyPostData)
         EndVerifyPostBarriers(rt);
     else
         StartVerifyPostBarriers(rt);
 }
 void
 gc::VerifyBarriers(JSRuntime *rt, VerifierType type)
 {
     if (type == PreBarrierVerifier)
         VerifyPreBarriers(rt);
     else
         VerifyPostBarriers(rt);
 }
 static void
 MaybeVerifyPreBarriers(JSRuntime *rt, bool always)
 {
     if (rt->gcZeal() != ZealVerifierPreValue)
         return;
     if (rt->mainThread.suppressGC)
         return;
     if (VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData) {
         if (++trc->count < rt->gcZealFrequency && !always)
             return;
         EndVerifyPreBarriers(rt);
     }
     StartVerifyPreBarriers(rt);
 }
 static void
 MaybeVerifyPostBarriers(JSRuntime *rt, bool always)
 {
 #ifdef JSGC_GENERATIONAL
     if (rt->gcZeal() != ZealVerifierPostValue)
         return;
     if (rt->mainThread.suppressGC || !rt->gcStoreBuffer.isEnabled())
         return;
     if (VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData) {
         if (++trc->count < rt->gcZealFrequency && !always)
             return;
         EndVerifyPostBarriers(rt);
     }
     StartVerifyPostBarriers(rt);
 #endif
 }
 void
 js::gc::MaybeVerifyBarriers(JSContext *cx, bool always)
 {
     MaybeVerifyPreBarriers(cx->runtime(), always);
     MaybeVerifyPostBarriers(cx->runtime(), always);
 }
 void
 js::gc::FinishVerifier(JSRuntime *rt)
 {
     if (VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData) {
         js_delete(trc);
         rt->gcVerifyPreData = nullptr;
     }
 #ifdef JSGC_GENERATIONAL
     if (VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData) {
         js_delete(trc);
         rt->gcVerifyPostData = nullptr;
     }
 #endif
 }
 #endif /* JS_GC_ZEAL */

The Tor Browser / annotate

js/src/gc/Verifier.cpp@b8a032363ba2 (annotated)

js/src/gc/Verifier.cpp