Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Description • 11 years ago

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

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 1 • 11 years ago

Shu suggests making the stack tree nodes GC things.

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 2 • 11 years ago

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.

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 3 • 11 years ago

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.

	Jim Blandy :jimb
	Comment 4 • 11 years ago

Fantastic! That was quick work!

	Jim Blandy :jimb
	Comment 5 • 11 years ago

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

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 6 • 11 years ago

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

	Steve Fink [:sfink] [:s:]
	Comment 7 • 11 years ago

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

	Jim Blandy :jimb
	Comment 8 • 11 years ago

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

	David Bruant
	Comment 9 • 11 years ago

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.

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 10 • 11 years ago

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

	Nicholas Nethercote [inactive]
	Comment 11 • 11 years ago

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

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 12 • 11 years ago

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.

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 13 • 10 years ago

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.

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 14 • 10 years ago

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

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 15 • 10 years ago

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

Clearing review until I get a good try push.

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 16 • 10 years ago

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

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 17 • 10 years ago

Sigh... One more time.

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

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 18 • 10 years ago

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 :)

	Eddy Bruel [:ejpbruel]
	Comment 19 • 10 years ago

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.

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 20 • 10 years ago

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

	Nicholas Nethercote [inactive]
	Comment 21 • 10 years ago

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

	Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] Assignee
	Comment 22 • 10 years ago

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

	Ryan VanderMeulen [:RyanVM]
	Comment 23 • 10 years ago

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

	Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)
	Comment 24 • 10 years ago

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