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

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jim Blandy :jimb]

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.

Comment 1

[Andrew McCreight [:mccr8]]

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.

Comment 2

[Jim Blandy :jimb]

(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.

Comment 3

[Jason Orendorff [:jorendorff]]

Probably a lot of us have written this a couple times by now. :)

Comment 5

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs

This commit adds `JS::ubi::ShortestPaths` which can find the N shortest
retaining paths starting from some root for any number of target nodes.

Comment 6

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=b747423002a5

Comment 7

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs

This iteration halts the traversal if we have found every path we will ever
record for every target.

Comment 8

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

New try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=1e758f485247

Comment 9

[Jim Blandy :jimb]

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 10

[Jim Blandy :jimb]

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 11

[Jim Blandy :jimb]

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.

Comment 12

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

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.

Comment 13

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs

Updated per review.

New try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=4831d2ffa20c

Comment 14

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/09836ef7b0f6

Comment 15

[Carsten Book [:Tomcat]]

backed out for bustage like https://treeherder.mozilla.org/logviewer.html#?job_id=21615859&repo=mozilla-inbound

Comment 16

[Pulsebot]

Backout:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ea6f3bbe55c1

Comment 17

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

(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?

Comment 18

[Carsten Book [:Tomcat]]

(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).

Comment 19

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

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.

Comment 20

[Pulsebot]

https://hg.mozilla.org/integration/fx-team/rev/e4c61fe8518b

Comment 21

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/e4c61fe8518b