1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/shell/jsheaptools.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,575 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "shell/jsheaptools.h"
1.11 +
1.12 +#include "mozilla/Move.h"
1.13 +
1.14 +#include <string.h>
1.15 +
1.16 +#include "jsalloc.h"
1.17 +#include "jsapi.h"
1.18 +#include "jscntxt.h"
1.19 +#include "jscompartment.h"
1.20 +#include "jsobj.h"
1.21 +#include "jsprf.h"
1.22 +
1.23 +#include "jsobjinlines.h"
1.24 +
1.25 +using namespace js;
1.26 +
1.27 +using mozilla::Move;
1.28 +
1.29 +#ifdef DEBUG
1.30 +
1.31 +
1.32 +/*** class HeapReverser **************************************************************************/
1.33 +
1.34 +/*
1.35 + * A class for constructing a map of the JavaScript heap, with all
1.36 + * reference edges reversed.
1.37 + *
1.38 + * Unfortunately, it's not possible to build the results for findReferences
1.39 + * while visiting things solely in the order that JS_TraceRuntime and
1.40 + * JS_TraceChildren reaches them. For example, as you work outward from the
1.41 + * roots, suppose an edge from thing T reaches a "gray" thing G --- G being gray
1.42 + * because you're still in the midst of traversing its descendants. At this
1.43 + * point, you don't know yet whether G will be a referrer or not, and so you
1.44 + * can't tell whether T should be a referrer either. And you won't visit T
1.45 + * again.
1.46 + *
1.47 + * So we take a brute-force approach. We reverse the entire graph, and then walk
1.48 + * outward from |target| to the representable objects that refer to it, stopping
1.49 + * at such objects.
1.50 + */
1.51 +
1.52 +/*
1.53 + * A JSTracer that produces a map of the heap with edges reversed.
1.54 + *
1.55 + * HeapReversers must be allocated in a stack frame. (They are derived from
1.56 + * CustomAutoRooter, and those must be allocated and destroyed in a stack-like
1.57 + * order.)
1.58 + *
1.59 + * HeapReversers keep all the roots they find in their traversal alive until
1.60 + * they are destroyed. So you don't need to worry about nodes going away while
1.61 + * you're using them.
1.62 + */
1.63 +class HeapReverser : public JSTracer, public JS::CustomAutoRooter
1.64 +{
1.65 + public:
1.66 + struct Edge;
1.67 +
1.68 + /* Metadata for a given Cell we have visited. */
1.69 + class Node {
1.70 + public:
1.71 + Node() { }
1.72 + Node(JSGCTraceKind kind)
1.73 + : kind(kind), incoming(), marked(false) { }
1.74 +
1.75 + /*
1.76 + * Move constructor and move assignment. These allow us to store our
1.77 + * incoming edge Vector in the hash table: Vectors support moves, but
1.78 + * not assignments or copy construction.
1.79 + */
1.80 + Node(Node &&rhs)
1.81 + : kind(rhs.kind), incoming(Move(rhs.incoming)), marked(rhs.marked) { }
1.82 + Node &operator=(Node &&rhs) {
1.83 + MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
1.84 + this->~Node();
1.85 + new(this) Node(Move(rhs));
1.86 + return *this;
1.87 + }
1.88 +
1.89 + void trace(JSTracer *trc) {
1.90 + for (Edge *e = incoming.begin(); e != incoming.end(); e++)
1.91 + e->trace(trc);
1.92 + }
1.93 +
1.94 + /* What kind of Cell this is. */
1.95 + JSGCTraceKind kind;
1.96 +
1.97 + /*
1.98 + * A vector of this Cell's incoming edges.
1.99 + * This must use SystemAllocPolicy because HashMap requires its elements to
1.100 + * be constructible with no arguments.
1.101 + */
1.102 + Vector<Edge, 0, SystemAllocPolicy> incoming;
1.103 +
1.104 + /* A mark bit, for other traversals. */
1.105 + bool marked;
1.106 +
1.107 + private:
1.108 + Node(const Node &) MOZ_DELETE;
1.109 + Node &operator=(const Node &) MOZ_DELETE;
1.110 + };
1.111 +
1.112 + /* Metadata for a heap edge we have traversed. */
1.113 + struct Edge {
1.114 + public:
1.115 + Edge(char *name, void *origin) : name(name), origin(origin) { }
1.116 + ~Edge() { js_free(name); }
1.117 +
1.118 + /*
1.119 + * Move constructor and move assignment. These allow us to live in
1.120 + * Vectors without needing to copy our name string when the vector is
1.121 + * resized.
1.122 + */
1.123 + Edge(Edge &&rhs) : name(rhs.name), origin(rhs.origin) {
1.124 + rhs.name = nullptr;
1.125 + }
1.126 + Edge &operator=(Edge &&rhs) {
1.127 + MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
1.128 + this->~Edge();
1.129 + new(this) Edge(Move(rhs));
1.130 + return *this;
1.131 + }
1.132 +
1.133 + void trace(JSTracer *trc) {
1.134 + if (origin)
1.135 + gc::MarkGCThingRoot(trc, &origin, "HeapReverser::Edge");
1.136 + }
1.137 +
1.138 + /* The name of this heap edge. Owned by this Edge. */
1.139 + char *name;
1.140 +
1.141 + /*
1.142 + * The Cell from which this edge originates. nullptr means a root. This
1.143 + * is a cell address instead of a Node * because Nodes live in HashMap
1.144 + * table entries; if the HashMap reallocates its table, all pointers to
1.145 + * the Nodes it contains would become invalid. You should look up the
1.146 + * address here in |map| to find its Node.
1.147 + */
1.148 + void *origin;
1.149 + };
1.150 +
1.151 + /*
1.152 + * The result of a reversal is a map from Cells' addresses to Node
1.153 + * structures describing their incoming edges.
1.154 + */
1.155 + typedef HashMap<void *, Node, DefaultHasher<void *>, SystemAllocPolicy> Map;
1.156 + Map map;
1.157 +
1.158 + /* Construct a HeapReverser for |context|'s heap. */
1.159 + HeapReverser(JSContext *cx)
1.160 + : JSTracer(cx->runtime(), traverseEdgeWithThis),
1.161 + JS::CustomAutoRooter(cx),
1.162 + noggc(JS_GetRuntime(cx)),
1.163 + runtime(JS_GetRuntime(cx)),
1.164 + parent(nullptr)
1.165 + {
1.166 + }
1.167 +
1.168 + bool init() { return map.init(); }
1.169 +
1.170 + /* Build a reversed map of the heap in |map|. */
1.171 + bool reverseHeap();
1.172 +
1.173 + private:
1.174 + JS::AutoDisableGenerationalGC noggc;
1.175 +
1.176 + /* A runtime pointer for use by the destructor. */
1.177 + JSRuntime *runtime;
1.178 +
1.179 + /*
1.180 + * Return the name of the most recent edge this JSTracer has traversed. The
1.181 + * result is allocated with malloc; if we run out of memory, raise an error
1.182 + * in this HeapReverser's context and return nullptr.
1.183 + *
1.184 + * This may not be called after that edge's call to traverseEdge has
1.185 + * returned.
1.186 + */
1.187 + char *getEdgeDescription();
1.188 +
1.189 + /* Class for setting new parent, and then restoring the original. */
1.190 + class AutoParent {
1.191 + public:
1.192 + AutoParent(HeapReverser *reverser, void *newParent) : reverser(reverser) {
1.193 + savedParent = reverser->parent;
1.194 + reverser->parent = newParent;
1.195 + }
1.196 + ~AutoParent() {
1.197 + reverser->parent = savedParent;
1.198 + }
1.199 + private:
1.200 + HeapReverser *reverser;
1.201 + void *savedParent;
1.202 + };
1.203 +
1.204 + /* A work item in the stack of nodes whose children we need to traverse. */
1.205 + struct Child {
1.206 + Child(void *cell, JSGCTraceKind kind) : cell(cell), kind(kind) { }
1.207 + void *cell;
1.208 + JSGCTraceKind kind;
1.209 + };
1.210 +
1.211 + /*
1.212 + * A stack of work items. We represent the stack explicitly to avoid
1.213 + * overflowing the C++ stack when traversing long chains of objects.
1.214 + */
1.215 + Vector<Child, 0, SystemAllocPolicy> work;
1.216 +
1.217 + /* When traverseEdge is called, the Cell and kind at which the edge originated. */
1.218 + void *parent;
1.219 +
1.220 + /* Traverse an edge. */
1.221 + bool traverseEdge(void *cell, JSGCTraceKind kind);
1.222 +
1.223 + /*
1.224 + * JS_TraceRuntime and JS_TraceChildren don't propagate error returns,
1.225 + * and out-of-memory errors, by design, don't establish an exception in
1.226 + * |context|, so traverseEdgeWithThis uses this to communicate the
1.227 + * result of the traversal to reverseHeap.
1.228 + */
1.229 + bool traversalStatus;
1.230 +
1.231 + /* Static member function wrapping 'traverseEdge'. */
1.232 + static void traverseEdgeWithThis(JSTracer *tracer, void **thingp, JSGCTraceKind kind) {
1.233 + HeapReverser *reverser = static_cast<HeapReverser *>(tracer);
1.234 + if (!reverser->traverseEdge(*thingp, kind))
1.235 + reverser->traversalStatus = false;
1.236 + }
1.237 +
1.238 + /* Return a jsval representing a node, if possible; otherwise, return JSVAL_VOID. */
1.239 + jsval nodeToValue(void *cell, int kind) {
1.240 + if (kind != JSTRACE_OBJECT)
1.241 + return JSVAL_VOID;
1.242 + JSObject *object = static_cast<JSObject *>(cell);
1.243 + return OBJECT_TO_JSVAL(object);
1.244 + }
1.245 +
1.246 + /* Keep all tracked objects live across GC. */
1.247 + virtual void trace(JSTracer *trc) MOZ_OVERRIDE {
1.248 + if (!map.initialized())
1.249 + return;
1.250 + for (Map::Enum e(map); !e.empty(); e.popFront()) {
1.251 + gc::MarkGCThingRoot(trc, const_cast<void **>(&e.front().key()), "HeapReverser::map::key");
1.252 + e.front().value().trace(trc);
1.253 + }
1.254 + for (Child *c = work.begin(); c != work.end(); ++c)
1.255 + gc::MarkGCThingRoot(trc, &c->cell, "HeapReverser::Child");
1.256 + }
1.257 +};
1.258 +
1.259 +bool
1.260 +HeapReverser::traverseEdge(void *cell, JSGCTraceKind kind)
1.261 +{
1.262 + /* Capture this edge before the JSTracer members get overwritten. */
1.263 + char *edgeDescription = getEdgeDescription();
1.264 + if (!edgeDescription)
1.265 + return false;
1.266 + Edge e(edgeDescription, parent);
1.267 +
1.268 + Map::AddPtr a = map.lookupForAdd(cell);
1.269 + if (!a) {
1.270 + /*
1.271 + * We've never visited this cell before. Add it to the map (thus
1.272 + * marking it as visited), and put it on the work stack, to be
1.273 + * visited from the main loop.
1.274 + */
1.275 + Node n(kind);
1.276 + uint32_t generation = map.generation();
1.277 + if (!map.add(a, cell, Move(n)) ||
1.278 + !work.append(Child(cell, kind)))
1.279 + return false;
1.280 + /* If the map has been resized, re-check the pointer. */
1.281 + if (map.generation() != generation)
1.282 + a = map.lookupForAdd(cell);
1.283 + }
1.284 +
1.285 + /* Add this edge to the reversed map. */
1.286 + return a->value().incoming.append(Move(e));
1.287 +}
1.288 +
1.289 +bool
1.290 +HeapReverser::reverseHeap()
1.291 +{
1.292 + traversalStatus = true;
1.293 +
1.294 + /* Prime the work stack with the roots of collection. */
1.295 + JS_TraceRuntime(this);
1.296 + if (!traversalStatus)
1.297 + return false;
1.298 +
1.299 + /* Traverse children until the stack is empty. */
1.300 + while (!work.empty()) {
1.301 + const Child child = work.popCopy();
1.302 + AutoParent autoParent(this, child.cell);
1.303 + JS_TraceChildren(this, child.cell, child.kind);
1.304 + if (!traversalStatus)
1.305 + return false;
1.306 + }
1.307 +
1.308 + return true;
1.309 +}
1.310 +
1.311 +char *
1.312 +HeapReverser::getEdgeDescription()
1.313 +{
1.314 + if (!debugPrinter() && debugPrintIndex() == (size_t) -1) {
1.315 + const char *arg = static_cast<const char *>(debugPrintArg());
1.316 + char *name = js_pod_malloc<char>(strlen(arg) + 1);
1.317 + if (!name)
1.318 + return nullptr;
1.319 + strcpy(name, arg);
1.320 + return name;
1.321 + }
1.322 +
1.323 + /* Lovely; but a fixed size is required by JSTraceNamePrinter. */
1.324 + static const int nameSize = 200;
1.325 + char *name = js_pod_malloc<char>(nameSize);
1.326 + if (!name)
1.327 + return nullptr;
1.328 + if (debugPrinter())
1.329 + debugPrinter()(this, name, nameSize);
1.330 + else
1.331 + JS_snprintf(name, nameSize, "%s[%lu]",
1.332 + static_cast<const char *>(debugPrintArg()), debugPrintIndex());
1.333 +
1.334 + /* Shrink storage to fit. */
1.335 + return static_cast<char *>(js_realloc(name, strlen(name) + 1));
1.336 +}
1.337 +
1.338 +
1.339 +/*** class ReferenceFinder ***********************************************************************/
1.340 +
1.341 +/* A class for finding an object's referrers, given a reversed heap map. */
1.342 +class ReferenceFinder {
1.343 + public:
1.344 + ReferenceFinder(JSContext *cx, const HeapReverser &reverser)
1.345 + : context(cx), reverser(reverser), result(cx) { }
1.346 +
1.347 + /* Produce an object describing all references to |target|. */
1.348 + JSObject *findReferences(HandleObject target);
1.349 +
1.350 + private:
1.351 + /* The context in which to do allocation and error-handling. */
1.352 + JSContext *context;
1.353 +
1.354 + /* A reversed map of the current heap. */
1.355 + const HeapReverser &reverser;
1.356 +
1.357 + /* The results object we're currently building. */
1.358 + RootedObject result;
1.359 +
1.360 + /* A list of edges we've traversed to get to a certain point. */
1.361 + class Path {
1.362 + public:
1.363 + Path(const HeapReverser::Edge &edge, Path *next) : edge(edge), next(next) { }
1.364 +
1.365 + /*
1.366 + * Compute the full path represented by this Path. The result is
1.367 + * owned by the caller.
1.368 + */
1.369 + char *computeName(JSContext *cx);
1.370 +
1.371 + private:
1.372 + const HeapReverser::Edge &edge;
1.373 + Path *next;
1.374 + };
1.375 +
1.376 + struct AutoNodeMarker {
1.377 + AutoNodeMarker(HeapReverser::Node *node) : node(node) { node->marked = true; }
1.378 + ~AutoNodeMarker() { node->marked = false; }
1.379 + private:
1.380 + HeapReverser::Node *node;
1.381 + };
1.382 +
1.383 + /*
1.384 + * Given that we've reached |cell| via |path|, with all Nodes along that
1.385 + * path marked, add paths from all reportable objects reachable from cell
1.386 + * to |result|.
1.387 + */
1.388 + bool visit(void *cell, Path *path);
1.389 +
1.390 + /*
1.391 + * If |cell|, of |kind|, is representable as a JavaScript value, return that
1.392 + * value; otherwise, return JSVAL_VOID.
1.393 + */
1.394 + jsval representable(void *cell, int kind) {
1.395 + if (kind == JSTRACE_OBJECT) {
1.396 + JSObject *object = static_cast<JSObject *>(cell);
1.397 +
1.398 + /* Certain classes of object are for internal use only. */
1.399 + if (object->is<BlockObject>() ||
1.400 + object->is<CallObject>() ||
1.401 + object->is<StaticWithObject>() ||
1.402 + object->is<DynamicWithObject>() ||
1.403 + object->is<DeclEnvObject>()) {
1.404 + return JSVAL_VOID;
1.405 + }
1.406 +
1.407 + /* Internal function objects should also not be revealed. */
1.408 + if (JS_ObjectIsFunction(context, object) && IsInternalFunctionObject(object))
1.409 + return JSVAL_VOID;
1.410 +
1.411 + return OBJECT_TO_JSVAL(object);
1.412 + }
1.413 +
1.414 + return JSVAL_VOID;
1.415 + }
1.416 +
1.417 + /* Add |referrer| as something that refers to |target| via |path|. */
1.418 + bool addReferrer(jsval referrer, Path *path);
1.419 +};
1.420 +
1.421 +bool
1.422 +ReferenceFinder::visit(void *cell, Path *path)
1.423 +{
1.424 + /* In ReferenceFinder, paths will almost certainly fit on the C++ stack. */
1.425 + JS_CHECK_RECURSION(context, return false);
1.426 +
1.427 + /* Have we reached a root? Always report that. */
1.428 + if (!cell)
1.429 + return addReferrer(JSVAL_NULL, path);
1.430 +
1.431 + HeapReverser::Map::Ptr p = reverser.map.lookup(cell);
1.432 + JS_ASSERT(p);
1.433 + HeapReverser::Node *node = &p->value();
1.434 +
1.435 + /* Is |cell| a representable cell, reached via a non-empty path? */
1.436 + if (path != nullptr) {
1.437 + jsval representation = representable(cell, node->kind);
1.438 + if (!JSVAL_IS_VOID(representation))
1.439 + return addReferrer(representation, path);
1.440 + }
1.441 +
1.442 + /*
1.443 + * If we've made a cycle, don't traverse further. We *do* want to include
1.444 + * paths from the target to itself, so we don't want to do this check until
1.445 + * after we've possibly reported this cell as a referrer.
1.446 + */
1.447 + if (node->marked)
1.448 + return true;
1.449 + AutoNodeMarker marker(node);
1.450 +
1.451 + /* Visit the origins of all |cell|'s incoming edges. */
1.452 + for (size_t i = 0; i < node->incoming.length(); i++) {
1.453 + const HeapReverser::Edge &edge = node->incoming[i];
1.454 + Path extendedPath(edge, path);
1.455 + if (!visit(edge.origin, &extendedPath))
1.456 + return false;
1.457 + }
1.458 +
1.459 + return true;
1.460 +}
1.461 +
1.462 +char *
1.463 +ReferenceFinder::Path::computeName(JSContext *cx)
1.464 +{
1.465 + /* Walk the edge list and compute the total size of the path. */
1.466 + size_t size = 6;
1.467 + for (Path *l = this; l; l = l->next)
1.468 + size += strlen(l->edge.name) + (l->next ? 2 : 0);
1.469 + size += 1;
1.470 +
1.471 + char *path = cx->pod_malloc<char>(size);
1.472 + if (!path)
1.473 + return nullptr;
1.474 +
1.475 + /*
1.476 + * Walk the edge list again, and copy the edge names into place, with
1.477 + * appropriate separators. Note that we constructed the edge list from
1.478 + * target to referrer, which means that the list links point *towards* the
1.479 + * target, so we can walk the list and build the path from left to right.
1.480 + */
1.481 + strcpy(path, "edge: ");
1.482 + char *next = path + 6;
1.483 + for (Path *l = this; l; l = l->next) {
1.484 + strcpy(next, l->edge.name);
1.485 + next += strlen(next);
1.486 + if (l->next) {
1.487 + strcpy(next, "; ");
1.488 + next += 2;
1.489 + }
1.490 + }
1.491 + JS_ASSERT(next + 1 == path + size);
1.492 +
1.493 + return path;
1.494 +}
1.495 +
1.496 +bool
1.497 +ReferenceFinder::addReferrer(jsval referrerArg, Path *path)
1.498 +{
1.499 + RootedValue referrer(context, referrerArg);
1.500 +
1.501 + if (!context->compartment()->wrap(context, &referrer))
1.502 + return false;
1.503 +
1.504 + ScopedJSFreePtr<char> pathName(path->computeName(context));
1.505 + if (!pathName)
1.506 + return false;
1.507 +
1.508 + /* Find the property of the results object named |pathName|. */
1.509 + RootedValue v(context);
1.510 +
1.511 + if (!JS_GetProperty(context, result, pathName, &v))
1.512 + return false;
1.513 + if (v.isUndefined()) {
1.514 + /* Create an array to accumulate referents under this path. */
1.515 + JSObject *array = JS_NewArrayObject(context, referrer);
1.516 + if (!array)
1.517 + return false;
1.518 + v.setObject(*array);
1.519 + return !!JS_SetProperty(context, result, pathName, v);
1.520 + }
1.521 +
1.522 + /* The property's value had better be an array. */
1.523 + RootedObject array(context, &v.toObject());
1.524 + JS_ASSERT(JS_IsArrayObject(context, array));
1.525 +
1.526 + /* Append our referrer to this array. */
1.527 + uint32_t length;
1.528 + return JS_GetArrayLength(context, array, &length) &&
1.529 + JS_SetElement(context, array, length, referrer);
1.530 +}
1.531 +
1.532 +JSObject *
1.533 +ReferenceFinder::findReferences(HandleObject target)
1.534 +{
1.535 + result = JS_NewObject(context, nullptr, JS::NullPtr(), JS::NullPtr());
1.536 + if (!result)
1.537 + return nullptr;
1.538 + if (!visit(target, nullptr))
1.539 + return nullptr;
1.540 +
1.541 + return result;
1.542 +}
1.543 +
1.544 +/* See help(findReferences). */
1.545 +bool
1.546 +FindReferences(JSContext *cx, unsigned argc, jsval *vp)
1.547 +{
1.548 + CallArgs args = CallArgsFromVp(argc, vp);
1.549 + if (args.length() < 1) {
1.550 + JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_MORE_ARGS_NEEDED,
1.551 + "findReferences", "0", "s");
1.552 + return false;
1.553 + }
1.554 +
1.555 + RootedValue target(cx, args[0]);
1.556 + if (!target.isObject()) {
1.557 + JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_UNEXPECTED_TYPE,
1.558 + "argument", "not an object");
1.559 + return false;
1.560 + }
1.561 +
1.562 + /* Walk the JSRuntime, producing a reversed map of the heap. */
1.563 + HeapReverser reverser(cx);
1.564 + if (!reverser.init() || !reverser.reverseHeap())
1.565 + return false;
1.566 +
1.567 + /* Given the reversed map, find the referents of target. */
1.568 + ReferenceFinder finder(cx, reverser);
1.569 + Rooted<JSObject*> targetObj(cx, &target.toObject());
1.570 + JSObject *references = finder.findReferences(targetObj);
1.571 + if (!references)
1.572 + return false;
1.573 +
1.574 + args.rval().setObject(*references);
1.575 + return true;
1.576 +}
1.577 +
1.578 +#endif /* DEBUG */
