diff -r 000000000000 -r 6474c204b198 js/src/shell/jsheaptools.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/shell/jsheaptools.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,575 @@ +/* -*- 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/. */ + +#include "shell/jsheaptools.h" + +#include "mozilla/Move.h" + +#include + +#include "jsalloc.h" +#include "jsapi.h" +#include "jscntxt.h" +#include "jscompartment.h" +#include "jsobj.h" +#include "jsprf.h" + +#include "jsobjinlines.h" + +using namespace js; + +using mozilla::Move; + +#ifdef DEBUG + + +/*** class HeapReverser **************************************************************************/ + +/* + * A class for constructing a map of the JavaScript heap, with all + * reference edges reversed. + * + * Unfortunately, it's not possible to build the results for findReferences + * while visiting things solely in the order that JS_TraceRuntime and + * JS_TraceChildren reaches them. For example, as you work outward from the + * roots, suppose an edge from thing T reaches a "gray" thing G --- G being gray + * because you're still in the midst of traversing its descendants. At this + * point, you don't know yet whether G will be a referrer or not, and so you + * can't tell whether T should be a referrer either. And you won't visit T + * again. + * + * So we take a brute-force approach. We reverse the entire graph, and then walk + * outward from |target| to the representable objects that refer to it, stopping + * at such objects. + */ + +/* + * A JSTracer that produces a map of the heap with edges reversed. + * + * HeapReversers must be allocated in a stack frame. (They are derived from + * CustomAutoRooter, and those must be allocated and destroyed in a stack-like + * order.) + * + * HeapReversers keep all the roots they find in their traversal alive until + * they are destroyed. So you don't need to worry about nodes going away while + * you're using them. + */ +class HeapReverser : public JSTracer, public JS::CustomAutoRooter +{ + public: + struct Edge; + + /* Metadata for a given Cell we have visited. */ + class Node { + public: + Node() { } + Node(JSGCTraceKind kind) + : kind(kind), incoming(), marked(false) { } + + /* + * Move constructor and move assignment. These allow us to store our + * incoming edge Vector in the hash table: Vectors support moves, but + * not assignments or copy construction. + */ + Node(Node &&rhs) + : kind(rhs.kind), incoming(Move(rhs.incoming)), marked(rhs.marked) { } + Node &operator=(Node &&rhs) { + MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited"); + this->~Node(); + new(this) Node(Move(rhs)); + return *this; + } + + void trace(JSTracer *trc) { + for (Edge *e = incoming.begin(); e != incoming.end(); e++) + e->trace(trc); + } + + /* What kind of Cell this is. */ + JSGCTraceKind kind; + + /* + * A vector of this Cell's incoming edges. + * This must use SystemAllocPolicy because HashMap requires its elements to + * be constructible with no arguments. + */ + Vector incoming; + + /* A mark bit, for other traversals. */ + bool marked; + + private: + Node(const Node &) MOZ_DELETE; + Node &operator=(const Node &) MOZ_DELETE; + }; + + /* Metadata for a heap edge we have traversed. */ + struct Edge { + public: + Edge(char *name, void *origin) : name(name), origin(origin) { } + ~Edge() { js_free(name); } + + /* + * Move constructor and move assignment. These allow us to live in + * Vectors without needing to copy our name string when the vector is + * resized. + */ + Edge(Edge &&rhs) : name(rhs.name), origin(rhs.origin) { + rhs.name = nullptr; + } + Edge &operator=(Edge &&rhs) { + MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited"); + this->~Edge(); + new(this) Edge(Move(rhs)); + return *this; + } + + void trace(JSTracer *trc) { + if (origin) + gc::MarkGCThingRoot(trc, &origin, "HeapReverser::Edge"); + } + + /* The name of this heap edge. Owned by this Edge. */ + char *name; + + /* + * The Cell from which this edge originates. nullptr means a root. This + * is a cell address instead of a Node * because Nodes live in HashMap + * table entries; if the HashMap reallocates its table, all pointers to + * the Nodes it contains would become invalid. You should look up the + * address here in |map| to find its Node. + */ + void *origin; + }; + + /* + * The result of a reversal is a map from Cells' addresses to Node + * structures describing their incoming edges. + */ + typedef HashMap, SystemAllocPolicy> Map; + Map map; + + /* Construct a HeapReverser for |context|'s heap. */ + HeapReverser(JSContext *cx) + : JSTracer(cx->runtime(), traverseEdgeWithThis), + JS::CustomAutoRooter(cx), + noggc(JS_GetRuntime(cx)), + runtime(JS_GetRuntime(cx)), + parent(nullptr) + { + } + + bool init() { return map.init(); } + + /* Build a reversed map of the heap in |map|. */ + bool reverseHeap(); + + private: + JS::AutoDisableGenerationalGC noggc; + + /* A runtime pointer for use by the destructor. */ + JSRuntime *runtime; + + /* + * Return the name of the most recent edge this JSTracer has traversed. The + * result is allocated with malloc; if we run out of memory, raise an error + * in this HeapReverser's context and return nullptr. + * + * This may not be called after that edge's call to traverseEdge has + * returned. + */ + char *getEdgeDescription(); + + /* Class for setting new parent, and then restoring the original. */ + class AutoParent { + public: + AutoParent(HeapReverser *reverser, void *newParent) : reverser(reverser) { + savedParent = reverser->parent; + reverser->parent = newParent; + } + ~AutoParent() { + reverser->parent = savedParent; + } + private: + HeapReverser *reverser; + void *savedParent; + }; + + /* A work item in the stack of nodes whose children we need to traverse. */ + struct Child { + Child(void *cell, JSGCTraceKind kind) : cell(cell), kind(kind) { } + void *cell; + JSGCTraceKind kind; + }; + + /* + * A stack of work items. We represent the stack explicitly to avoid + * overflowing the C++ stack when traversing long chains of objects. + */ + Vector work; + + /* When traverseEdge is called, the Cell and kind at which the edge originated. */ + void *parent; + + /* Traverse an edge. */ + bool traverseEdge(void *cell, JSGCTraceKind kind); + + /* + * JS_TraceRuntime and JS_TraceChildren don't propagate error returns, + * and out-of-memory errors, by design, don't establish an exception in + * |context|, so traverseEdgeWithThis uses this to communicate the + * result of the traversal to reverseHeap. + */ + bool traversalStatus; + + /* Static member function wrapping 'traverseEdge'. */ + static void traverseEdgeWithThis(JSTracer *tracer, void **thingp, JSGCTraceKind kind) { + HeapReverser *reverser = static_cast(tracer); + if (!reverser->traverseEdge(*thingp, kind)) + reverser->traversalStatus = false; + } + + /* Return a jsval representing a node, if possible; otherwise, return JSVAL_VOID. */ + jsval nodeToValue(void *cell, int kind) { + if (kind != JSTRACE_OBJECT) + return JSVAL_VOID; + JSObject *object = static_cast(cell); + return OBJECT_TO_JSVAL(object); + } + + /* Keep all tracked objects live across GC. */ + virtual void trace(JSTracer *trc) MOZ_OVERRIDE { + if (!map.initialized()) + return; + for (Map::Enum e(map); !e.empty(); e.popFront()) { + gc::MarkGCThingRoot(trc, const_cast(&e.front().key()), "HeapReverser::map::key"); + e.front().value().trace(trc); + } + for (Child *c = work.begin(); c != work.end(); ++c) + gc::MarkGCThingRoot(trc, &c->cell, "HeapReverser::Child"); + } +}; + +bool +HeapReverser::traverseEdge(void *cell, JSGCTraceKind kind) +{ + /* Capture this edge before the JSTracer members get overwritten. */ + char *edgeDescription = getEdgeDescription(); + if (!edgeDescription) + return false; + Edge e(edgeDescription, parent); + + Map::AddPtr a = map.lookupForAdd(cell); + if (!a) { + /* + * We've never visited this cell before. Add it to the map (thus + * marking it as visited), and put it on the work stack, to be + * visited from the main loop. + */ + Node n(kind); + uint32_t generation = map.generation(); + if (!map.add(a, cell, Move(n)) || + !work.append(Child(cell, kind))) + return false; + /* If the map has been resized, re-check the pointer. */ + if (map.generation() != generation) + a = map.lookupForAdd(cell); + } + + /* Add this edge to the reversed map. */ + return a->value().incoming.append(Move(e)); +} + +bool +HeapReverser::reverseHeap() +{ + traversalStatus = true; + + /* Prime the work stack with the roots of collection. */ + JS_TraceRuntime(this); + if (!traversalStatus) + return false; + + /* Traverse children until the stack is empty. */ + while (!work.empty()) { + const Child child = work.popCopy(); + AutoParent autoParent(this, child.cell); + JS_TraceChildren(this, child.cell, child.kind); + if (!traversalStatus) + return false; + } + + return true; +} + +char * +HeapReverser::getEdgeDescription() +{ + if (!debugPrinter() && debugPrintIndex() == (size_t) -1) { + const char *arg = static_cast(debugPrintArg()); + char *name = js_pod_malloc(strlen(arg) + 1); + if (!name) + return nullptr; + strcpy(name, arg); + return name; + } + + /* Lovely; but a fixed size is required by JSTraceNamePrinter. */ + static const int nameSize = 200; + char *name = js_pod_malloc(nameSize); + if (!name) + return nullptr; + if (debugPrinter()) + debugPrinter()(this, name, nameSize); + else + JS_snprintf(name, nameSize, "%s[%lu]", + static_cast(debugPrintArg()), debugPrintIndex()); + + /* Shrink storage to fit. */ + return static_cast(js_realloc(name, strlen(name) + 1)); +} + + +/*** class ReferenceFinder ***********************************************************************/ + +/* A class for finding an object's referrers, given a reversed heap map. */ +class ReferenceFinder { + public: + ReferenceFinder(JSContext *cx, const HeapReverser &reverser) + : context(cx), reverser(reverser), result(cx) { } + + /* Produce an object describing all references to |target|. */ + JSObject *findReferences(HandleObject target); + + private: + /* The context in which to do allocation and error-handling. */ + JSContext *context; + + /* A reversed map of the current heap. */ + const HeapReverser &reverser; + + /* The results object we're currently building. */ + RootedObject result; + + /* A list of edges we've traversed to get to a certain point. */ + class Path { + public: + Path(const HeapReverser::Edge &edge, Path *next) : edge(edge), next(next) { } + + /* + * Compute the full path represented by this Path. The result is + * owned by the caller. + */ + char *computeName(JSContext *cx); + + private: + const HeapReverser::Edge &edge; + Path *next; + }; + + struct AutoNodeMarker { + AutoNodeMarker(HeapReverser::Node *node) : node(node) { node->marked = true; } + ~AutoNodeMarker() { node->marked = false; } + private: + HeapReverser::Node *node; + }; + + /* + * Given that we've reached |cell| via |path|, with all Nodes along that + * path marked, add paths from all reportable objects reachable from cell + * to |result|. + */ + bool visit(void *cell, Path *path); + + /* + * If |cell|, of |kind|, is representable as a JavaScript value, return that + * value; otherwise, return JSVAL_VOID. + */ + jsval representable(void *cell, int kind) { + if (kind == JSTRACE_OBJECT) { + JSObject *object = static_cast(cell); + + /* Certain classes of object are for internal use only. */ + if (object->is() || + object->is() || + object->is() || + object->is() || + object->is()) { + return JSVAL_VOID; + } + + /* Internal function objects should also not be revealed. */ + if (JS_ObjectIsFunction(context, object) && IsInternalFunctionObject(object)) + return JSVAL_VOID; + + return OBJECT_TO_JSVAL(object); + } + + return JSVAL_VOID; + } + + /* Add |referrer| as something that refers to |target| via |path|. */ + bool addReferrer(jsval referrer, Path *path); +}; + +bool +ReferenceFinder::visit(void *cell, Path *path) +{ + /* In ReferenceFinder, paths will almost certainly fit on the C++ stack. */ + JS_CHECK_RECURSION(context, return false); + + /* Have we reached a root? Always report that. */ + if (!cell) + return addReferrer(JSVAL_NULL, path); + + HeapReverser::Map::Ptr p = reverser.map.lookup(cell); + JS_ASSERT(p); + HeapReverser::Node *node = &p->value(); + + /* Is |cell| a representable cell, reached via a non-empty path? */ + if (path != nullptr) { + jsval representation = representable(cell, node->kind); + if (!JSVAL_IS_VOID(representation)) + return addReferrer(representation, path); + } + + /* + * If we've made a cycle, don't traverse further. We *do* want to include + * paths from the target to itself, so we don't want to do this check until + * after we've possibly reported this cell as a referrer. + */ + if (node->marked) + return true; + AutoNodeMarker marker(node); + + /* Visit the origins of all |cell|'s incoming edges. */ + for (size_t i = 0; i < node->incoming.length(); i++) { + const HeapReverser::Edge &edge = node->incoming[i]; + Path extendedPath(edge, path); + if (!visit(edge.origin, &extendedPath)) + return false; + } + + return true; +} + +char * +ReferenceFinder::Path::computeName(JSContext *cx) +{ + /* Walk the edge list and compute the total size of the path. */ + size_t size = 6; + for (Path *l = this; l; l = l->next) + size += strlen(l->edge.name) + (l->next ? 2 : 0); + size += 1; + + char *path = cx->pod_malloc(size); + if (!path) + return nullptr; + + /* + * Walk the edge list again, and copy the edge names into place, with + * appropriate separators. Note that we constructed the edge list from + * target to referrer, which means that the list links point *towards* the + * target, so we can walk the list and build the path from left to right. + */ + strcpy(path, "edge: "); + char *next = path + 6; + for (Path *l = this; l; l = l->next) { + strcpy(next, l->edge.name); + next += strlen(next); + if (l->next) { + strcpy(next, "; "); + next += 2; + } + } + JS_ASSERT(next + 1 == path + size); + + return path; +} + +bool +ReferenceFinder::addReferrer(jsval referrerArg, Path *path) +{ + RootedValue referrer(context, referrerArg); + + if (!context->compartment()->wrap(context, &referrer)) + return false; + + ScopedJSFreePtr pathName(path->computeName(context)); + if (!pathName) + return false; + + /* Find the property of the results object named |pathName|. */ + RootedValue v(context); + + if (!JS_GetProperty(context, result, pathName, &v)) + return false; + if (v.isUndefined()) { + /* Create an array to accumulate referents under this path. */ + JSObject *array = JS_NewArrayObject(context, referrer); + if (!array) + return false; + v.setObject(*array); + return !!JS_SetProperty(context, result, pathName, v); + } + + /* The property's value had better be an array. */ + RootedObject array(context, &v.toObject()); + JS_ASSERT(JS_IsArrayObject(context, array)); + + /* Append our referrer to this array. */ + uint32_t length; + return JS_GetArrayLength(context, array, &length) && + JS_SetElement(context, array, length, referrer); +} + +JSObject * +ReferenceFinder::findReferences(HandleObject target) +{ + result = JS_NewObject(context, nullptr, JS::NullPtr(), JS::NullPtr()); + if (!result) + return nullptr; + if (!visit(target, nullptr)) + return nullptr; + + return result; +} + +/* See help(findReferences). */ +bool +FindReferences(JSContext *cx, unsigned argc, jsval *vp) +{ + CallArgs args = CallArgsFromVp(argc, vp); + if (args.length() < 1) { + JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_MORE_ARGS_NEEDED, + "findReferences", "0", "s"); + return false; + } + + RootedValue target(cx, args[0]); + if (!target.isObject()) { + JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_UNEXPECTED_TYPE, + "argument", "not an object"); + return false; + } + + /* Walk the JSRuntime, producing a reversed map of the heap. */ + HeapReverser reverser(cx); + if (!reverser.init() || !reverser.reverseHeap()) + return false; + + /* Given the reversed map, find the referents of target. */ + ReferenceFinder finder(cx, reverser); + Rooted targetObj(cx, &target.toObject()); + JSObject *references = finder.findReferences(targetObj); + if (!references) + return false; + + args.rval().setObject(*references); + return true; +} + +#endif /* DEBUG */