diff -r 000000000000 -r 6474c204b198 js/src/gc/Verifier.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/gc/Verifier.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,611 @@ +/* -*- 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 +#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, 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(""); + 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(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(edge.thing))) + return; + + // Permanent atoms aren't marked during graph traversal. + if (edge.kind == JSTRACE_STRING && static_cast(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, 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(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(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(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 */