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