961288 - Optionally track allocation sites

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

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

We should be able to optionally track the site of every JS allocation.

We should store stacks in a suffix tree so that we share the oldest frames across many stacks.

When our allocation tracking mode is enabled, we should hook into shape creation via SetObjectMetaDataHook[0] and return a meta data object that has a property that points to a (JS shadow object of a) node in the stack tree: the youngest frame in this allocation's captured stack. In order to avoid fragmenting shapes, we must keep the meta data object in a HashSet and return the exact same object for every allocation at the same location.

The stack tree's nodes should be reference counted and as we allocate objects we increment the count of their stack tree nodes, and in the JS shadow stack tree node's js::Class::finalize hook we decrement the stack tree nodes' counts.

For initial testing, we should expose a pair of functions in js/src/builtin/TestingFunctions.cpp. One that enables tracking allocation sites and another that disables it. Jim tells me there is already a function to get an object's meta data, so we can use that function to test that an object's allocation site's captured stack is correct.

[0] http://dxr.mozilla.org/mozilla-central/source/js/src/jsfriendapi.h#1733

Comment 1

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

Shu suggests making the stack tree nodes GC things.

Comment 2

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

Attachment: WIP

Work in progress patch.

* Need to figure out why the test crashes (I think it has to do with the ScriptFrameIter stuff in SavedStacks::insertFrames, but I haven't investigated yet)

* SavedFrame needs a prototype w/ getters so that we can actually test the metadata objects that we create.

* Need to integrate with GC stuff and remove SavedFrames from SavedStack::frames when they are no longer reachable.

* Probably more stuff, that I'm not thinking of right now.

Comment 3

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

Attachment: WIP

Another WIP patch. It works! And there is a nice toString method so SavedFrame instances just look like stringified call stacks. Woo!

TODO:

* Differentiate SavedFrame.prototype from SavedFrame instances in SavedFrame::checkThis.

* Custom GC stuff for SavedStacks.

* Save JSPrincipals in SavedFrame and only expose frames whose principal is subsumed by the current context's principal.

* Really fill out the unit tests and get all corner cases.

Comment 4

[Jim Blandy :jimb]

Fantastic! That was quick work!

Comment 5

[Jim Blandy :jimb]

I filed bug 969273 with a patch that defines some principal testing functions for the JS shell.

Comment 6

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

(Jim, was there a reason you changed this back from ASSIGNED to NEW? Does the JS Engine component do things differently?)

Comment 7

[Steve Fink [:sfink] [:s:]]

(In reply to Nick Fitzgerald [:fitzgen] [Ðoge:D6jomNp59N9TVfgc538HU3RswwmwZwcrd7] from comment #0)
> We should store stacks in a suffix tree so that we share the oldest frames
> across many stacks.

Can you expand on this? Why a full suffix tree just to share prefixes? Or do you need to share general substacks?

For prefixes, I'd think you'd just need a basic tree. Or trie, if you want to walk from the root. Or dag, if you want to share suffixes too.

Suffix trees are slow (worse than O(n)) or complicated (eg Ukkonen's) to build. Moreso since you'd want to build incrementally.

Comment 8

[Jim Blandy :jimb]

(In reply to Nick Fitzgerald [:fitzgen] [Ðoge:D6jomNp59N9TVfgc538HU3RswwmwZwcrd7] from comment #6)
> (Jim, was there a reason you changed this back from ASSIGNED to NEW? Does
> the JS Engine component do things differently?)

D'oh!!

Comment 9

[David Bruant]

Re depending on bug 972045, is the full stack really required? I have the feeling that for a first iteration, file/line/column (~last stack frame) can be enough information. For sure, it's already more than you can find on Chrome and IE11 tools last time I checked and is already useful for lots of circumstances.

Comment 10

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

Whole stacks is already implemented, just splitting the patch up.

Comment 11

[Nicholas Nethercote [inactive]]

> We should be able to optionally track the site of every JS allocation.
> We should store stacks in a suffix tree so that we share the oldest frames
> across many stacks.

For my pdf.js profiling, just having a 1-deep stack trace is sufficient in maybe 90--95% of the cases.

Comment 12

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

Attachment: WIP

This is rebased on top of the patches for bug 972045 (which contain all the SavedStack and SavedFrame stuff now).

Need to write some tests for allocation sites specifically.

Comment 13

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

Attachment: track-allocation-sites.patch

No try push at the moment because I think we are having infrastructure issues again.

This patch just defines a simple object metadata callback which saves the allocation site as a |SavedFrame| in the object's metadata.

Comment 14

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

Try push finally succeeded: https://tbpl.mozilla.org/?tree=Try&rev=672d0f865435

Comment 15

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

Comment on attachment 8412893 [details] [diff] [review]
track-allocation-sites.patch

Clearing review until I get a good try push.

Comment 16

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

Attachment: track-allocation-sites.patch

https://tbpl.mozilla.org/?tree=Try&rev=d99a27e20236

Comment 17

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

Attachment: track-allocation-sites.patch

Sigh... One more time.

https://tbpl.mozilla.org/?tree=Try&rev=60a0f3c9ea28

Comment 18

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

Comment on attachment 8414527 [details] [diff] [review]
track-allocation-sites.patch

Ok that try push was good.

Eddy, this should hopefully be a pretty quick review; it's a pretty small patch :)

Comment 19

[Eddy Bruel [:ejpbruel]]

Comment on attachment 8414527 [details] [diff] [review]
track-allocation-sites.patch

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

Overall patch looks good to me. r+ with a few comments.

::: js/src/builtin/TestingFunctions.cpp
@@ +871,5 @@
>  }
> +static bool
> +EnableTrackAllocations(JSContext *cx, unsigned argc, jsval *vp)
> +{
> +    SetObjectMetadataCallback(cx, SavedStacksMetadataCallback);

What if something else already set the metadata callback? Then enabling track allocations could have some unexpected side effects. Shouldn't we guard against that?

::: js/src/vm/SavedStacks.cpp
@@ +509,5 @@
> +bool
> +SavedStacksMetadataCallback(JSContext *cx, JSObject **pmetadata)
> +{
> +    Rooted<SavedFrame *> frame(cx);
> +    if (!cx->compartment()->savedStacks().saveCurrentStack(cx, &frame))

Storing a copy of the entire call stack as metadata with each object sounds prohibitively expensive. However, I've looked at the implementation of SavedStack, and it looks like it tries to reuse the same objects whenever it can, so it might be ok.

Have you done any actual performance measurements for this? I'm not going to r- the patch for this since it's an optional feature and it's not exposed to the web, but I'd be interested to see how this performs in practice.

Comment 20

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

Attachment: track-allocation-sites.patch

Talked with Eddy on IRC, just documenting the fact that |enableTrackingAllocations| overrides the metadata callback because it is only used in other testing functions right now. Will get perf impact data once bug 993085 lands and it is easier to test. Jim sent a message to the list about possible follow ups for perf improvement here: https://lists.mozilla.org/pipermail/dev-tech-js-engine-internals/2014-January/001555.html

Comment 21

[Nicholas Nethercote [inactive]]

> Storing a copy of the entire call stack as metadata with each object sounds
> prohibitively expensive.

FWIW, I've done some very hacky profiling involving object allocation sites, just getting the top entry of the stack (i.e. the actual source location of the allocation). That alone has been extremely useful, and it's been rare that I've wished having deeper stacks.

Comment 22

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

(In reply to Nicholas Nethercote [:njn] from comment #21)
> > Storing a copy of the entire call stack as metadata with each object sounds
> > prohibitively expensive.
> 
> FWIW, I've done some very hacky profiling involving object allocation sites,
> just getting the top entry of the stack (i.e. the actual source location of
> the allocation). That alone has been extremely useful, and it's been rare
> that I've wished having deeper stacks.

We might want to have full stack vs youngest frame toggle-able in the future. However, one of the things we want to do in devtools is to create flame graphs of allocations. For that, we will need the whole stack. See also bug 1004110 for an optimization to make it easier to keep full stacks.

Comment 23

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/887b927cce10

Comment 24

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/887b927cce10