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