[ubi::Node] should be able to find paths by which some objects refer to others

RESOLVED FIXED in Firefox 47

Status

()

defect
RESOLVED FIXED
6 years ago
4 years ago

People

(Reporter: jimb, Assigned: fitzgen)

Tracking

(Blocks 2 bugs)

unspecified
mozilla47
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox47 fixed)

Details

()

Attachments

(1 attachment, 2 obsolete attachments)

Debugger should be able to take a set of objects for which we'd like to find names, and then for each object report how it can be reached from a given set of globals.

Here are notes copied from: https://etherpad.mozilla.org/memory-tool

# Path Finding (BFS)

    Can pass in multiple objects and share work (alternatively, can we just maintain some state for each a snapshot so we don't need to pass in multiple at once to share work, but just share work across all calls to a specific snapshot by default/automatically?)

    On second iteration, we can add a cost to edges so that any non-JS edges are much more costly than plain JS references. This allows us to get JS expressions as the retained path in most cases.

    As a JS function, it would take a set of roots and an object (or set of objects?) and give us a representation of the path from the root to the given object.

## Path representation
An  array of path descriptors starting from a global and ending at this  object. Each path descriptor describes the type of node and its outgoing  edge. Path descriptors have the following form:
{
    type: NodeType,
    edge: {
        type: EdgeType,
        value: EdgeValue
    }
}
Where:
* NodeType describes the type of the node. It is one of:
  * "global"
  * "object"
  * "environment"
* EdgeType describes the type of the outgoing edge to the next node. It is one of:
  * "property": JS property or index access.
  * "variable": A reference to a variable.
  * "timeout": A reference to a function passed to setTimeout.
  * "interval": A reference to a function passed to setInterval.
* EdgeValue is the property name, index value, variable name, or ms interval/timeout.
FWIW, I have some scripts that do a similar thing for paths in CC and GC heaps logs (a fairly low-level view of memory), that we've used to fix a number of Gecko leaks, as well as a few Gaia ones.
  https://github.com/amccreight/heapgraph/blob/master/cc/find_roots.py
  https://github.com/amccreight/heapgraph/blob/master/g/find_roots.py
This is based on some earlier scripts by (I think) peterv, and it just does the simplest possible thing, and inverts the graph, then floods out from the rooting object, reporting paths as it goes.
No longer blocks: 960671
(In reply to Andrew McCreight [:mccr8] from comment #1)
> FWIW, I have some scripts that do a similar thing for paths in CC and GC
> heaps logs (a fairly low-level view of memory), that we've used to fix a
> number of Gecko leaks, as well as a few Gaia ones.
>   https://github.com/amccreight/heapgraph/blob/master/cc/find_roots.py
>   https://github.com/amccreight/heapgraph/blob/master/g/find_roots.py
> This is based on some earlier scripts by (I think) peterv, and it just does
> the simplest possible thing, and inverts the graph, then floods out from the
> rooting object, reporting paths as it goes.

Yes, these will be similar results, but with effort put into providing paths comprehensible to JS developers. We also want to be able to use this code to generate "names" for the objects in the "top N by retained size" lists, and similar enumerations.
Probably a lot of us have written this a couple times by now. :)
Duplicate of this bug: 646737
No longer blocks: 960776
Assignee: nobody → nfitzgerald
Status: NEW → ASSIGNED
Depends on: 1247412
Depends on: 1247413
This commit adds `JS::ubi::ShortestPaths` which can find the N shortest
retaining paths starting from some root for any number of target nodes.
Attachment #8718078 - Flags: review?(jimb)
This iteration halts the traversal if we have found every path we will ever
record for every target.
Attachment #8718083 - Flags: review?(jimb)
Attachment #8718078 - Attachment is obsolete: true
Attachment #8718078 - Flags: review?(jimb)
Summary: [jsdbg2] Debugger should be able to find paths by which some objects refer to others → [ubi::Node] should be able to find paths by which some objects refer to others
Comment on attachment 8718083 [details] [diff] [review]
Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs

Review of attachment 8718083 [details] [diff] [review]:
-----------------------------------------------------------------

Still reviewing, just publishing as I go...

::: js/public/UbiNodeShortestPaths.h
@@ +79,5 @@
> +{
> +  private:
> +    // Types, type aliases, and data members.
> +
> +    friend struct Handler;

Is this needed? I thought member types had access to everything in the parent types, even without being friended.

@@ +118,5 @@
> +            if (first && !back->init(origin, edge))
> +                return false;
> +
> +
> +            if (!shortestPaths.targets_.has(edge.referent))

Why two blank lines above this?

@@ +121,5 @@
> +
> +            if (!shortestPaths.targets_.has(edge.referent))
> +                return true;
> +
> +            auto ptr = shortestPaths.paths_.lookupForAdd(edge.referent);

At this point, either `edge` or `back` has the name we must use, depending on whether `first` is true or not. Using the wrong one would leave null UniquePtrs in surprising places. So I think it'd be worth commenting briefly that our source of names must always take `first` into account.

@@ +235,5 @@
> +     * responsibility to handle and report the OOM.
> +     */
> +    static mozilla::Maybe<ShortestPaths>
> +    Create(JSRuntime* rt, AutoCheckCannotGC& noGC, uint32_t maxNumPaths, const Node& root, NodeSet&& targets) {
> +        MOZ_ASSERT(targets.count() > 0);

You probably want to also assert that the number of paths requested per target is greater than zero.
Comment on attachment 8718083 [details] [diff] [review]
Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs

Review of attachment 8718083 [details] [diff] [review]:
-----------------------------------------------------------------

More in-progress comments...

::: js/public/UbiNodeShortestPaths.h
@@ +152,5 @@
> +        }
> +
> +    };
> +
> +    using Traversal = BreadthFirst<Handler>;

This declaration is identical to the one in Handler. Would it work to drop the one in Handler, and just let it see this one? (Perhaps put it up above, for clarity?)

::: js/src/builtin/TestingFunctions.cpp
@@ +2569,5 @@
> +    RootedNativeObject objs(cx, &args[1].toObject().as<ArrayObject>());
> +    if (objs->getDenseInitializedLength() == 0) {
> +        ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
> +                              JSDVG_SEARCH_STACK, args[1], nullptr,
> +                              "not a dense array object with one more elements", nullptr);

"one or more"

@@ +2597,5 @@
> +
> +    Rooted<GCVector<GCVector<GCVector<Value>>>> values(cx, GCVector<GCVector<GCVector<Value>>>(cx));
> +    Vector<Vector<Vector<JS::ubi::EdgeName>>> names(cx);
> +    {
> +        JS::AutoCheckCannotGC noGC(cx->runtime());

It might be worth a comment to mention why we have to copy everything out into a GC-stable form, within the scope of an AutoCheckCannotGC. Simply citing ShortestPaths' requirements is enough.

@@ +2607,5 @@
> +        }
> +
> +        for (size_t i = 0; i < length; i++) {
> +            RootedValue val(cx, objs->getDenseElement(i));
> +            JS::ubi::Node node(val);

I think there's actually no need for this: there's a deliberate implicit conversion between HandleValue and JS::ubi::Node.

@@ +2614,5 @@
> +                return false;
> +            }
> +        }
> +
> +        JS::ubi::Node root(args[0]);

Same here.

@@ +2617,5 @@
> +
> +        JS::ubi::Node root(args[0]);
> +        auto maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx->runtime(), noGC, maxNumPaths,
> +                                                                 root, mozilla::Move(targets));
> +        if (maybeShortestPaths.isNothing())

ShortestPaths::Create doesn't report OOMs, right? So don't we need to `ReportOutOfMemory` here?

@@ +2629,5 @@
> +                return false;
> +            }
> +
> +            RootedValue val(cx, objs->getDenseElement(i));
> +            JS::ubi::Node target(val);

Another unneeded explicit conversion.

@@ +2639,5 @@
> +                for (auto& part : path) {
> +                    if (!pathVals.append(part->predecessor().exposeToJS()) ||
> +                        !pathNames.append(mozilla::Move(part->name())))
> +                    {
> +                        return false;

Just checking: both `GCVector` and the `Vector` we're using here automatically report OOM on the context, right?
Comment on attachment 8718083 [details] [diff] [review]
Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs

Review of attachment 8718083 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great. r=me with comments addressed.
Attachment #8718083 - Flags: review?(jimb) → review+
Thanks for the speedy review!

(In reply to Jim Blandy :jimb from comment #10)
> ::: js/public/UbiNodeShortestPaths.h
> @@ +152,5 @@
> > +        }
> > +
> > +    };
> > +
> > +    using Traversal = BreadthFirst<Handler>;
> 
> This declaration is identical to the one in Handler. Would it work to drop
> the one in Handler, and just let it see this one? (Perhaps put it up above,
> for clarity?)

I thought that it might complain about Handler only being forward declared at that point in time, but I didn't actually try it out. I will see if I can do that.


> @@ +2607,5 @@
> > +        }
> > +
> > +        for (size_t i = 0; i < length; i++) {
> > +            RootedValue val(cx, objs->getDenseElement(i));
> > +            JS::ubi::Node node(val);
> 
> I think there's actually no need for this: there's a deliberate implicit
> conversion between HandleValue and JS::ubi::Node.

Unfortunately, there is no conversion for non-Handle, raw Value, and getDenseElement returns a raw Value, so the rooting is necessary. Blech.

> @@ +2617,5 @@
> > +
> > +        JS::ubi::Node root(args[0]);
> > +        auto maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx->runtime(), noGC, maxNumPaths,
> > +                                                                 root, mozilla::Move(targets));
> > +        if (maybeShortestPaths.isNothing())
> 
> ShortestPaths::Create doesn't report OOMs, right? So don't we need to
> `ReportOutOfMemory` here?

Good catch!

> @@ +2639,5 @@
> > +                for (auto& part : path) {
> > +                    if (!pathVals.append(part->predecessor().exposeToJS()) ||
> > +                        !pathNames.append(mozilla::Move(part->name())))
> > +                    {
> > +                        return false;
> 
> Just checking: both `GCVector` and the `Vector` we're using here
> automatically report OOM on the context, right?

Yes, the default alloc policy takes a cx on construction, which they report OOMs on.
Attachment #8718083 - Attachment is obsolete: true
(In reply to Carsten Book [:Tomcat] from comment #15)
> backed out for bustage like
> https://treeherder.mozilla.org/logviewer.html#?job_id=21615859&repo=mozilla-
> inbound

This is because the dependent bugs which were also marked checkin-needed were not landed first. Should I not mark multiple bugs checkin-needed when there are ordering dependencies between them?
Flags: needinfo?(nfitzgerald) → needinfo?(cbook)
(In reply to Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] from comment #17)
> (In reply to Carsten Book [:Tomcat] from comment #15)
> > backed out for bustage like
> > https://treeherder.mozilla.org/logviewer.html#?job_id=21615859&repo=mozilla-
> > inbound
> 
> This is because the dependent bugs which were also marked checkin-needed
> were not landed first. Should I not mark multiple bugs checkin-needed when
> there are ordering dependencies between them?

oh a note like checkin bug x first (or a order in which they need checked in would be awesome).
Flags: needinfo?(cbook)
Ah ok, I thought that the "depends on" field already described that, but I suppose it is good to highlight.

Well, the dependencies have been checked into m-i now, so re-adding checkin-needed.
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/e4c61fe8518b
Status: ASSIGNED → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla47
Depends on: 1249107
Depends on: 1249938
Depends on: 1252912
Depends on: 1254105
You need to log in before you can comment on or make changes to this bug.