The Tor Browser / file revision

 /* -*- 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 <string.h>

 #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<Edge, 0, SystemAllocPolicy> 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<void *, Node, DefaultHasher<void *>, 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<Child, 0, SystemAllocPolicy> 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<HeapReverser *>(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<JSObject *>(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<void **>(&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<const char *>(debugPrintArg());

         char *name = js_pod_malloc<char>(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<char>(nameSize);

     if (!name)

         return nullptr;

     if (debugPrinter())

         debugPrinter()(this, name, nameSize);

     else

         JS_snprintf(name, nameSize, "%s[%lu]",

                     static_cast<const char *>(debugPrintArg()), debugPrintIndex());

     /* Shrink storage to fit. */

     return static_cast<char *>(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<JSObject *>(cell);

             /* Certain classes of object are for internal use only. */

             if (object->is<BlockObject>() ||

                 object->is<CallObject>() ||

                 object->is<StaticWithObject>() ||

                 object->is<DynamicWithObject>() ||

                 object->is<DeclEnvObject>()) {

                 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<char>(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<char> 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<JSObject*> targetObj(cx, &target.toObject());

     JSObject *references = finder.findReferences(targetObj);

     if (!references)

         return false;

     args.rval().setObject(*references);

     return true;

 }

 #endif /* DEBUG */