The developer tools will soon have a mode that records the JS call stack at which each object allocation occurs. This mode needs a compact representation for captured call stacks. A tree in which younger frames are ancestors of older frames --- sharing the old ends of the stacks, in effect --- seems like a good first cut. The optimizations discussed here would apply nicely to such a representation: https://groups.google.com/forum/#!msg/mozilla.dev.tech.js-engine.internals/crDZ1vU7hkY/uYg3xxD552oJ

In the process of splitting up my patch from bug 961288. This is what I had from that patch with the allocation specific stuff removed (which included all the tests). Will write a TestingFunctions.cpp function to capture a stack and then write tests around that (as opposed to the saved stacks for allocations).

This patch ports over the tests I had from the last patch to use the new `saveStack()` testing function instead of enabling tracking allocations, allocating an object, and then getting its metadata. Still need to write tests for: * principals * generator frames * eval frames (direct and indirect) * self hosted functions (forEach/map/filter/reduce etc) * native functions (such as someString.replace(pattern, function)) * getter and setter frames * proxy handlers

https://tbpl.mozilla.org/?tree=Try&rev=b9cb937ce355 I think this is ready!

Well, that was a rather unhappy try push :-/ Leaving review flag in the hopes that I can either fix this before it ends up on the top of your queue or at least get some feedback if I don't fix the issues in time :)

Added a bunch of header includes that were missing (but somehow wasn't a problem on my system only) and fixed up a few errors that should have also been compiler errors locally but weren't for whatever reason. Higher hopes for this push. https://tbpl.mozilla.org/?tree=Try&rev=e0a7cfd1a5b1

Eddy pointed out to me that I had a circular dependency >.< This patch just moves an include from SavedStacks.h to SavedStacks.cpp to resolve the problem. Yet another try push: https://tbpl.mozilla.org/?tree=Try&rev=a05f7154de8b

*sigh* Fixing more header include issues. Many thanks to Eddy for helping me out. https://tbpl.mozilla.org/?tree=Try&rev=568b8e1e3202

https://tbpl.mozilla.org/?tree=Try&rev=f35f5d131582 Now with proper refcounting for JSPrincipals! Hopefully this takes care of the failures on try...

https://tbpl.mozilla.org/?tree=Try&rev=f1016d962e6b This one should fix the issues with principals-01.js. It makes sure that the stack is being extracted in each global so that CCWs don't mess with the results we expect. principals-02.js doesn't have that problem so I am a bit more confused as to why it is apparently failing.

https://tbpl.mozilla.org/?tree=Try&rev=94ee00f4430d * Fixes some header ordering reported by |make check-style| * Rewrites the way that the principals-02.js parses the stack string, part of which has been failing. Hopefully this is much more clear now and if it is still failing, it should be more obvious where and why.

Aaaaaaaannnnnd I realized I haven't been including Jim's shell principals patches in my try pushes >_< https://tbpl.mozilla.org/?tree=Try&rev=c7749695ca64 This should finally give me a green try push. Fingers crossed. Feeling ashamed.

Ok getting an assertion failure in basic/bug908915.js. Am able to reproduce locally, but I don't really know what is going on in this code. Need to dive in deeper. Here is the backtrace: > #0 js::jit::IonFrameIterator::ionScript (this=0x7fff5fbfc370) at IonFrames.cpp:1517 > #1 0x000000010037dd2b in js::jit::SnapshotIterator::SnapshotIterator (this=0x7fff5fbfb668, iter=@0x7fff5fbfc370) at IonFrames.cpp:1306 > #2 0x000000010037a22d in js::jit::SnapshotIterator::SnapshotIterator (this=0x7fff5fbfb668, iter=@0x7fff5fbfc370) at IonFrames.cpp:1312 > #3 0x0000000100912106 in js::jit::InlineFrameIteratorMaybeGC<(js::AllowGC)1>::InlineFrameIteratorMaybeGC (this=0x7fff5fbfba88, cx=0x103800a90, iter=0x7fff5fbfc3a8) at IonFrameIterator.h:371 > #4 0x00000001008d7a15 in js::jit::InlineFrameIteratorMaybeGC<(js::AllowGC)1>::InlineFrameIteratorMaybeGC (this=0x7fff5fbfba88, cx=0x103800a90, iter=0x7fff5fbfc3a8) at IonFrameIterator.h:377 > #5 0x000000010086ce80 in js::ScriptFrameIter::ScriptFrameIter (this=0x7fff5fbfb9f0, other=@0x7fff5fbfc310) at Stack.cpp:675 > #6 0x000000010086cdcd in js::ScriptFrameIter::ScriptFrameIter (this=0x7fff5fbfb9f0, other=@0x7fff5fbfc310) at Stack.cpp:678 > #7 0x00000001007e6020 in js::SavedStacks::insertFrames (this=0x10a00ce80, cx=0x103800a90, iter=@0x7fff5fbfc310, frame=0x7fff5fbfbf18) at SavedStacks.cpp:421 > #8 0x00000001007e6051 in js::SavedStacks::insertFrames (this=0x10a00ce80, cx=0x103800a90, iter=@0x7fff5fbfc310, frame=0x7fff5fbfc6e0) at SavedStacks.cpp:423 > #9 0x00000001007e5f90 in js::SavedStacks::insert (this=0x10a00ce80, cx=0x103800a90, frame=0x7fff5fbfc6e0) at SavedStacks.cpp:376 > #10 0x000000010013f9da in SaveStack (cx=0x103800a90, argc=0, vp=0x7fff5fbfcd70) at TestingFunctions.cpp:842 > #11 0x00000001007fae95 in js::CallJSNative (cx=0x103800a90, native=0x10013f990 <SaveStack(JSContext*, unsigned int, JS::Value*)>, args=@0x7fff5fbfcc40) at jscntxtinlines.h:230 > #12 0x00000001007c391c in js::Invoke (cx=0x103800a90, args={<JS::detail::CallArgsBase<0>> = {<JS::CallReceiver> = {<JS::detail::CallReceiverBase<0>> = {<JS::detail::UsedRvalBase<IncludeUsedRval>> = {usedRval_ = false}, argv_ = 0x7fff5fbfcd80}, <No data fields>}, argc_ = 0}, <No data fields>}, construct=js::NO_CONSTRUCT) at Interpreter.cpp:476 > #13 0x00000001007c422d in js::Invoke (cx=0x103800a90, thisv=@0x7fff5fbfd7d8, fval=@0x7fff5fbfce88, argc=0, argv=0x7fff5fbfd7e0, rval={<js::MutableHandleBase<JS::Value>> = {<js::MutableValueOperations<JS::MutableHandle<JS::Value> >> = {<js::ValueOperations<JS::MutableHandle<JS::Value> >> = {<No data fields>}, <No data fields>}, <No data fields>}, ptr = 0x7fff5fbfd7d0}) at Interpreter.cpp:532 > #14 0x000000010063298c in js::DirectProxyHandler::call (this=0x1018b0758, cx=0x103800a90, proxy={<js::HandleBase<JSObject *>> = {<No data fields>}, ptr = 0x7fff5fbfd140}, args=@0x7fff5fbfd150) at jsproxy.cpp:465 > #15 0x000000010072ce8c in js::CrossCompartmentWrapper::call (this=0x1018b0758, cx=0x103800a90, wrapper={<js::HandleBase<JSObject *>> = {<No data fields>}, ptr = 0x7fff5fbfd140}, args=@0x7fff5fbfd150) at jswrapper.cpp:465 > #16 0x000000010063d040 in js::Proxy::call (cx=0x103800a90, proxy={<js::HandleBase<JSObject *>> = {<No data fields>}, ptr = 0x7fff5fbfd140}, args=@0x7fff5fbfd150) at jsproxy.cpp:2637 > #17 0x000000010063fa83 in js::proxy_Call (cx=0x103800a90, argc=0, vp=0x7fff5fbfd7d0) at jsproxy.cpp:3079 > #18 0x00000001007fae95 in js::CallJSNative (cx=0x103800a90, native=0x10063f990 <js::proxy_Call(JSContext*, unsigned int, JS::Value*)>, args=@0x7fff5fbfd6a0) at jscntxtinlines.h:230 > #19 0x00000001007c3840 in js::Invoke (cx=0x103800a90, args={<JS::detail::CallArgsBase<0>> = {<JS::CallReceiver> = {<JS::detail::CallReceiverBase<0>> = {<JS::detail::UsedRvalBase<IncludeUsedRval>> = {usedRval_ = false}, argv_ = 0x7fff5fbfd7e0}, <No data fields>}, argc_ = 0}, <No data fields>}, construct=js::NO_CONSTRUCT) at Interpreter.cpp:469 > #20 0x00000001007c422d in js::Invoke (cx=0x103800a90, thisv=@0x7fff5fbfd990, fval=@0x7fff5fbfd950, argc=0, argv=0x7fff5fbfdad0, rval={<js::MutableHandleBase<JS::Value>> = {<js::MutableValueOperations<JS::MutableHandle<JS::Value> >> = {<js::ValueOperations<JS::MutableHandle<JS::Value> >> = {<No data fields>}, <No data fields>}, <No data fields>}, ptr = 0x7fff5fbfd978}) at Interpreter.cpp:532 > #21 0x00000001004c6351 in js::jit::InvokeFunction (cx=0x103800a90, obj0={<js::HandleBase<JSObject *>> = {<No data fields>}, ptr = 0x7fff5fbfdab0}, argc=0, argv=0x7fff5fbfdac8, rval=0x7fff5fbfda88) at VMFunctions.cpp:88 > #22 0x00000001039f011f in ?? () > #23 0x0000000105600600 in ?? ()

From IRC with Jim: 17:27 < jimb> fitzgen: That looks really bogus. You're absolutely right that the '.isScripted()' check is simply not an adequate guard for the ionInlineFrames_ constructor. In Stack.cpp:675, we are getting a IonFrame_BaselineJS frame and passing it to what eventually becomes an IonFrameIterator. I think we need a better check in the ScriptFrameIter copy constructor, but I'm not sure exactly what is up...

Hannes, I'm pretty sure the ScriptFrameIter copy constructor is broken with regards to the |isScripted| call not being a good enough check. Can you help out and/or provide advice/insight? I can rewrite my code to work around this, but it seems like this is something that should probably be fixed...

This is a holdover from the days when IonFrameIterator only iterated Ion frames. |isScripted()| should be |isOptimizedJS()|. In fact, it seems fixed for the |const Data &data| ctor right below the copy ctor. r=me if you want to add that change to your patch as a rider. I suspect Nick is right in that nobody really uses the copy constructor for ScriptFrameIter, and so this never showed up before now.

r=shu on s/isScripted/isOptimizedJS/ New try push with this patch included: https://tbpl.mozilla.org/?tree=Try&rev=f6ea5ca53ffc

(In reply to Nick Fitzgerald [:fitzgen] from comment #14) > Hannes, I'm pretty sure the ScriptFrameIter copy constructor is broken with > regards to the |isScripted| call not being a good enough check. Can you help > out and/or provide advice/insight? Sorry about the delay. (Was on PTO). But I see shu already answered and is right on the money ;).

Comment on attachment 8383418 [details] [diff] [review] saved-stacks.patch Review of attachment 8383418 [details] [diff] [review]: ----------------------------------------------------------------- Some dumb initial comments. Still reviewing. ::: js/src/vm/SavedStacks.h @@ +15,5 @@ > +namespace js { > + > +class SavedFrame; > + > +struct SavedFrameLookup { What would you say to putting these all in SavedFrame? That is, SavedFrame::Lookup, SavedFrame::HashPolicy, SavedFrame::Map, etc. It might make things terser. Note that you can still *define* the classes outside the containing class: class SavedFrame { struct Lookup; }; struct SavedFrame::Lookup { ... blah blah ... }; @@ +54,5 @@ > + SavedFrameHashPolicy, > + SystemAllocPolicy> SavedFrameMap; > + > +enum { > + // The reserved slots in the SavedFrame class. This should definitely be local to SavedFrame. See, for example: https://hg.mozilla.org/mozilla-central/file/25aeb2bc79f2/js/src/vm/ScopeObject.h#l391 @@ +114,5 @@ > + mozilla::DebugOnly<bool> initialized; > + SavedFrameMap frames; > + JSObject *savedFrameProto; > + > + bool insertFrames(JSContext *cx, ScriptFrameIter &iter, SavedFrame **frame); Would it be better to use '... MutableHandle<SavedFrame> frame', here and in SavedStacks::insert?

Comment on attachment 8383418 [details] [diff] [review] saved-stacks.patch Review of attachment 8383418 [details] [diff] [review]: ----------------------------------------------------------------- Some more comments; review ongoing. ::: js/src/jscompartment.h @@ +200,5 @@ > > private: > js::ObjectMetadataCallback objectMetadataCallback; > > + js::SavedStacks savedStacks_; You should mention this in JSCompartment::addSizeOfIncludingThis, too. You should assert that savedStacks_ is storing nothing of interest in JSCompartment::clearTables. ::: js/src/vm/Debugger.cpp @@ +5908,5 @@ > > envProto = js_InitClass(cx, debugCtor, objProto, &DebuggerEnv_class, > + DebuggerEnv_construct, 0, > + DebuggerEnv_properties, DebuggerEnv_methods, > + nullptr, nullptr); Just whitespace, right? Thanks! ::: js/src/vm/SavedStacks.cpp @@ +52,5 @@ > + JSAtom *source = existing->getSource(); > + if (source->length() != lookup.source->length()) > + return false; > + if (0 != CompareAtoms(source, lookup.source)) > + return false; You shouldn't use CompareAtoms here; that's for generating < == > values, not just comparing for equality. The whole point of JSAtom is that there is at most one JSAtom instance for a given piece of text, so if you want to compare them for equality or hash them, then the pointer is all you need to look at. So you should use pointer hashing and comparison on both source and functionDisplayName. @@ +92,5 @@ > + nullptr, // finalize > + nullptr, // call > + nullptr, // hasInstance > + nullptr, // construct > + nullptr // trace You can just end the Class initializer after 'convert', and all of these will be automatically left null for you. ::: js/src/vm/SavedStacks.h @@ +112,5 @@ > + > + private: > + mozilla::DebugOnly<bool> initialized; > + SavedFrameMap frames; > + JSObject *savedFrameProto; This needs to be traced somehow, perhaps from JSCompartment::trace. An alternative would be to clear it in SavedStacks::sweep if its referent is "about to be finalized" --- that is, make savedFrameProto member a weak pointer. If everyone uses getOrCreateSavedFramePrototype, it'll just get regenerated as necessary.

Comment on attachment 8383418 [details] [diff] [review] saved-stacks.patch Review of attachment 8383418 [details] [diff] [review]: ----------------------------------------------------------------- More review-in-progress comments: Once we start using this on each object allocation, we should see whether making all those setters and getters inline wins us any perf. ::: js/src/vm/SavedStacks.cpp @@ +102,5 @@ > + const Value &v = getReservedSlot(JSSLOT_SAVEDFRAME_SOURCE); > + JS_ASSERT(v.isString()); > + JSString *s = v.toString(); > + JS_ASSERT(s->isAtom()); > + return &s->asAtom(); Actually, Value::toString and JSString::asAtom both assert what you're asserting here, so you can just omit the assertions; I think it turns into a nice one-liner. @@ +138,5 @@ > +SavedFrame::getParent() > +{ > + const Value &v = getReservedSlot(JSSLOT_SAVEDFRAME_PARENT); > + JS_ASSERT(v.isObjectOrNull()); > + return v.isObject() ? &v.toObject().as<SavedFrame>() : nullptr; I think all this is equivalent to Value::toObjectOrNull. @@ +343,5 @@ > + return false; > + if (!NumberValueToStringBuffer(cx, NumberValue(frame->getColumn()), sb)) > + return false; > + if (!sb.append('\n')) > + return false; Wouldn't this make a nice '||' chain? @@ +386,5 @@ > + > + if (IsObjectAboutToBeFinalized(&obj)) { > + JSPrincipals *p = obj->as<SavedFrame>().getPrincipals(); > + if (p) > + JS_DropPrincipals(rt, p); Would it make sense to actually give SavedFrame a 'finalize' method, and let that drop the principal? I grant that everything *should* go through here, so it's not a correctness issue. @@ +390,5 @@ > + JS_DropPrincipals(rt, p); > + e.removeFront(); > + } else if (obj != temp) { > + SavedFrame *frame = &obj->as<SavedFrame>(); > + e.rekeyFront(SavedFrameLookup(frame->getSource(), It would be a little neater to overload the SavedFrameLookup constructor with a variant that takes a SavedFrame *. More seriously, I think you'll need to re-key entries if the parent is relocated, too. That is, I think there's a bug here with the relocating GC. If that's correct, we should try to get a regression test that catches it, before we fix it. @@ +418,5 @@ > + return true; > + } > + > + ScriptFrameIter thisFrame(iter); > + SavedFrame *parentFrame; I'm kind of amazed the rooting analysis doesn't complain about this. Atomize can certainly allocate, and cause a GC, so this parentFrame should be a Rooted<SavedFrame>. @@ +453,5 @@ > + Rooted<SavedFrame *> frame(cx, createFrameFromLookup(cx, lookup)); > + if (!frame) > + return nullptr; > + > + if (!frames.add(p, frame)) I think you need to re-hash, because createFrameFromLookup may have caused a GC which relocates the parent, which changes the hash table location for this entry. ::: js/src/vm/SavedStacks.h @@ +32,5 @@ > + JSAtom *source; > + size_t line; > + size_t column; > + JSAtom *functionDisplayName; > + SavedFrame *parent; I think this needs to be a Handle<SavedFrame>, initialized from the same. When building a new entry, the allocation of the new frame could cause the parent frame to be relocated. If SavedFrameLookup::parent were a handle referring to a Rooted<SavedFrame>, then it would still be right. @@ +54,5 @@ > + SavedFrameHashPolicy, > + SystemAllocPolicy> SavedFrameMap; > + > +enum { > + // The reserved slots in the SavedFrame class. Oh, and once it is local to SavedFrame, we can drop all the _SAVEDFRAME_ name components (ahhh!) and perhaps even the JSSLOT_ prefix, if you feel comfortable with that. @@ +105,5 @@ > + public: > + SavedStacks() : initialized(false), frames(), savedFrameProto(nullptr) { } > + > + bool init(); > + bool insert(JSContext *cx, SavedFrame **frame); This isn't a very suggestive name. How about 'saveStack' or 'saveCurrentStack'?

Comment on attachment 8383418 [details] [diff] [review] saved-stacks.patch Review of attachment 8383418 [details] [diff] [review]: ----------------------------------------------------------------- This is great code. Many comments, and a few bugs, but so nice to read. Much symmetry. What simple. Would it make sense for all the SavedStacks methods that take a JSContext * to assert that 'this' is the context's current compartment's SavedStacks? That would make some of the assertions in createFrameFromLookup redundant. Instead of having the big list of SavedFrame::setBleah methods, couldn't we have a single 'initFromLookup' method? They're immutable fields anyway, right? ::: js/src/vm/SavedStacks.cpp @@ +498,5 @@ > + if (!frameObj) > + return nullptr; > + > + SavedFrame &f = frameObj->as<SavedFrame>(); > + JS_ASSERT(lookup.source); You assert this in SavedFrame::setSource, too, so you could drop this.

https://tbpl.mozilla.org/?tree=Try&rev=6f73e6641425 Changes in this patch revision: * replaced SavedFrame::setX methods with SavedFrame::initFromLookup * rename SavedStacks::insert to SavedStacks::saveCurrentStack * make SavedFrame::Lookup take a Handle<SavedFrame*> instead of just a SavedFrame* * use an || chain instead of multiple if statements when appending to the string buffer in SavedFrame::toStringMethod * make savedFrameProto a weak pointer and clear it in SavedStacks::sweep if it is about to be finalized * remove unnecessary nullptr slots from SavedFrame::class_ literal * move SavedFrame{Lookup,HashPolicy} to SavedFrame::{Lookup,HashPolicy} * use pointer comparison and hashing for JSAtoms in SavedFrame::Lookup and SavedFrame::HashPolicy * clear savedStacks in JSCompartment::clearTables * add savedStacks to JSCompartment::sizeOfExcludingThis * move the JSSLOT_SAVEDFRAME_X enum into SavedFrame and remove the _SAVEDFRAME_ part of its members * move the dropping of principals to the SavedFrame finalizer * make sure to rekey if gc relocated anything after createFrameFromLookup inside SavedStacks::sweep * use MutableHandle<SavedFrame *> instead of SavedFrame** for all of the out parameters

(In reply to Jim Blandy :jimb from comment #21) > Would it make sense for all the SavedStacks methods that take a JSContext * > to assert that 'this' is the context's current compartment's SavedStacks? > That would make some of the assertions in createFrameFromLookup redundant. I already do this in SavedStacks::saveCurrentStack, was there somewhere else you wanted to see this?

The Hf failures in the try push results linked to in comment 22 are significant. The log isn't helpful, but if you look at the lower right box, there's a link to the uploaded analysis results directory; the hazards.txt.gz file there says: Time: Mon Apr 21 2014 15:00:12 GMT-0400 (EDT) Function '_ZN2js10SavedFrame14parentPropertyEP9JSContextjPN2JS5ValueE|uint8 js::SavedFrame::parentProperty(JSContext*, uint32, JS::Value*)' has unrooted 'frame' of type 'js::SavedFrame*' live across GC call *subsumes at js/src/vm/SavedStacks.cpp:295 js/src/vm/SavedStacks.cpp:295: Call(15,16, __temp_5 := subsumes*(principals*,__temp_6*)) js/src/vm/SavedStacks.cpp:295: Assume(16,18, !__temp_5*, false) js/src/vm/SavedStacks.cpp:293: Assign(18,19, __temp_4 := 0) js/src/vm/SavedStacks.cpp:293: Assume(19,20, __temp_4*, false) js/src/vm/SavedStacks.cpp:297: Call(20,21, __temp_7 := args.field:0.field:0.field:0.rval()) js/src/vm/SavedStacks.cpp:297: Call(21,22, __temp_7.setObjectOrNull(frame*.field:0)) Function '_ZN2js10SavedFrame14toStringMethodEP9JSContextjPN2JS5ValueE|uint8 js::SavedFrame::toStringMethod(JSContext*, uint32, JS::Value*)' has unrooted 'frame' of type 'js::SavedFrame*' live across GC call *subsumes at js/src/vm/SavedStacks.cpp:319 js/src/vm/SavedStacks.cpp:319: Call(3,4, __temp_5 := subsumes*(principals*,__temp_6*)) js/src/vm/SavedStacks.cpp:319: Assume(4,6, !__temp_5*, false) js/src/vm/SavedStacks.cpp:319: Assign(6,7, __temp_4 := 0) js/src/vm/SavedStacks.cpp:319: Assume(7,8, __temp_4*, false) js/src/vm/SavedStacks.cpp:321: Call(8,9, __temp_7 := frame*.isSelfHosted()) What's at issue here is that the principals 'subsumes' function can do anything, including causing a GC, so the 'frame' local declared by the THIS_SAVEDFRAME macro is unrooted across a GC call. That should become a Rooted<SavedFrame *>, I guess.

This should fix the rooting failure on the last patch's try push. https://tbpl.mozilla.org/?tree=Try&rev=dcaf3939a2d7

That's (In reply to Nick Fitzgerald [:fitzgen] from comment #25) > This should fix the rooting failure on the last patch's try push. That's a nice green push. I'll look this over as soon as I'm done with shu's tests.

Comment on attachment 8411296 [details] [diff] [review] saved-stacks.patch Review of attachment 8411296 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/vm/SavedStacks.h @@ +65,5 @@ > + // The total number of reserved slots in the SavedFrame class. > + JSSLOT_COUNT > + }; > + > + // Because we hash the parent pointer, we need to rekey this a saved frame "this a"?

Rebased and fixed comment. Carrying over r+.

Backed out for mochitest asserts/crashes. https://hg.mozilla.org/integration/mozilla-inbound/rev/9688e85bd87c https://tbpl.mozilla.org/php/getParsedLog.php?id=38425326&tree=Mozilla-Inbound

Hmm I can't reproduce those failures locally... Doing a try push to see if maybe it wasn't my fault: https://tbpl.mozilla.org/?tree=Try&rev=44a6c3dd0d81

Was able to reproduce eventually. Turns out that the saved stacks set should actually be |NotLiveGCThing| in |CompartmentStats|. https://tbpl.mozilla.org/?tree=Try&rev=1abc9d37a726

Looks like that did it :)