View source for Sfink/JS Stack Walking

= Walking the JS stack =

I'm writing this for a fairly general audience, including people who are not on
the JS team, so I'm going to lay out some basic information first.

== Stack Layout ==

SpiderMonkey currently maintains its stack on the heap, and this JS stack is
mostly independent of the native C/C++ stack. The full details on how the JS
stack is managed can be found in a comment at the top of js/src/vm/Stack.h.
This is due to change in IonMonkey, which will switch to using the native stack
for JS.

Some quick terminology: in SpiderMonkey, we talk about "scripts", which are
either JS functions, the toplevel code outside of any functions, or the code
compiled by an eval(). The data structure representing a script is JSScript.

A particular JS script may be executed in a variety of ways: in the
interpreter, JITted, or JITted but inlined into another "outer" script. (Until
recently, it was way more complicated: portions of a script would get JITted by
the trace JIT, possibly dynamically inlining all or portions of called
functions, and sometimes bailing out partway through to finish executing in the
interpreter. That craziness is gone now with the removal of the tracing JIT,
though it may return in some form for IonMonkey.) Regardless, the JS stack
contains a single frame for each invocation of a non-inlined script.

Native stack frames for JITted code also store a VMFrame struct, which represents the execution of some number of JITted scripts. Initially, the VMFrame is created for just the script you're invoking, but that script may call other JITted
scripts, and no new native frame is pushed for those. The VMFrame fields are updated to reflect the currently-executing state, as well as a pair of JS StackFrame pointers <entryfp,fp> representing the range of JS stack frames that
the JIT native frame is executing. Note that VMFrames are auxiliary data, and
are not needed just to walk the JS stack.

Each JSContext has its own JS stack, but all of those context-specific stacks
are interleaved together into a per-thread StackSpace data structure.

In the simplest case, you can simply iterate through the entire StackSpace
using an AllFramesIter iterator. For a given StackFrame, you can grab out the
JSScript it is executing, and from there get the URL and starting line number
of the script. Well, if you ignore inlined scripts, anyway.

Ridiculously oversimplified pseudocode:

  foreach jsframe in AllFramesIter(threadData):
    script = jsframe.script
    print(script.filename, script.lineno)

== Exact Line Number ==

Getting the exact line number is trickier. In general, you want to get the
pointer into the JS bytecode instruction being executed. We'll refer to that as
the PC. Then you can use the src notes -- metadata stored in the JSScript -- to
map the PC to the actual line number.

If the frame in question is running JITted and is the leaf (youngest/current)
frame, you may first need to map the native instruction pointer (IP) to the JS
bytecode pointer (PC) using a 'native map' stored in the JITScript data
structure. If the frame is JITted but not a leaf, it will have synced their PCs
into the VMFrame struct before invoking the next JS function, so no native map
games are necessary.

Note that by "leaf", I'm only referring to the JS stack. If you have a frame
for a JITted script on the native stack underneath some younger native frames,
you are not guaranteed that the PC in the VMFrame will be up to date. (Many
times it will; the terminology for these cases is "fallible VM calls". The
"infallible VM calls" are the tricky ones.)

StackFrames also store the PC of the previous (calling) frame. Think of it as
the JS bytecode return address. If you are using a StackIter, it will give you
access to the PC "belonging to" a given stack frame, so you do not need to
worry about the off-by-one. (iter.pc() returns the PC within the StackFrame
given by iter.fp(), not the PC of the caller that was saved in that frame.)

Pseudocode:
   for jsframe in StackIter(cx):
     if jsframe.isScript():
       pc = jsframe.pc()
       lineno = JS_PCToLineNumber(jsframe.fp().regs.script, pc)
     (else jsframe.isNativeCall())

Unfortunately, for general stack unwinding you cannot use StackIter because it
modifies the stack (eg instantiating inline frames for simplicity) and it
requires a JSContext. (FIXME: We can change things to be able to hand it a
JSContext, though we don't want to, since we want frames for all contexts.) If
you are not using StackIter but instead using AllFramesIter, then things are a
lot hairier. There is no easy pc() accessor. Inlined frames will not be
expanded for you, so a given frame may actually represent an outer script plus
a set of inlined (nested, even) scripts. The PC will point into the innermost
(currently active) script, not to the outer script. (FIXME; I haven't fully
implemented handling of inlined frames yet.)

== Intermediate State ==

Accessing the JS stack during a signal handler (or while stopped by another
thread, as in OSX and Windows) is considerably more complicated. The basic
problem is that data structures referring to the JS stack may be in a state of
flux, so it is unsafe to even dereference arbitrary StackFrame* pointers. The
state stored within StackFrames, VMFrames, and StackSpaces could also be in
flux.

This difficulty is not just for getting exact line numbers. The straightforward
way of getting the stack of scripts relies on unsafe accesses. (In other words:
it's harder to get a stack of call sites than just a stack of functions, but
the concurrent mutation problem makes even the former difficult.)

=== Flagging Mutation ===

One approach to handle this is for the stackwalking code to know when things
are in flux and drop samples (or return partial information) in those cases.
Options: (1) atomically increment a global variable around mutation (it's a
flag for multiple threads); (2) set a per-thread flag; and/or (3) do nothing
during normal operation, but when walking the native stack, detect when the IP
is in the machine code address range of code that modifies needed state.

Two problems with this approach are complexity and speed. Example sites of
mutation:

* JITted code that updates the VMFrame (the "in flux" state can even cross call sites of "infallible" C++ functions)
* ContextStack::popInvokeArgs (simple case)
* PopActiveVMFrame() called by JIT trampolines, unsafe until repointRegs called from inside the regular C++ method EnterMethodJIT()

There are probably others, and identifying all of these cases requires detailed
knowledge of the engine and is fairly brittle.

There are some other odd cases, like where js::Interpret maintains the set of
registers (including the PC) in a local variable and repoints JSContext->regs
there instead of pointing somewhere within the JS stack. Then the PC is mutated
within that register struct ("mostly" safely; you might get a pointer to a
previous bytecode.)

Previously, imacros also introduced headaches, but they're dead now.

=== Validating Data ===

Another approach would be to withstand mutation by validating all data before accessing/dereferencing it, and if anything doesn't look right, bailing out and dropping that sample.

From the ThreadData we can find the youngest stack frame. (Well, the youngest
or its immediate caller, at least.) This can be validated against the address
range corresponding to the currently live stack; if it is inside it, then at
least it is safe to dereference. (You might have a stale fp that was popped and
then another frame was pushed over the top of it, so the data it points to may
be garbage, but at least you can dereference it.)

The JSScript* can be pulled out of the StackFrame and checked against a global
table of valid scripts. Anything in there is guaranteed to still be live, so
can be used freely. It could possibly the *wrong* script (if the fp was bogus),
but for expected users (sampling profilers) it's acceptable to get the
wrong answer occasionally as long it happens rarely.

The valid stack region can be determined from the StackSpace in the ThreadData.

To find the PC for a JITted frame, you need to get the VMFrame. This requires
first knowing that an IP corresponds to JITted code rather than C/C++ code.
Then you need the address of the VMFrame itself. The "correct" solution to this
is to walk the stack and get out the CFA ("Call Frame Address" in DWARF
terminology; it's roughly the value of the stack pointer just before a function
is called, and is used to find the saved return address as well as all other
values on the native stack.) The VMFrame is a local variable in JITted code,
and so will always be found at a fixed offset from the CFA. This requires a
stack unwinding tool that gives both return addresses and CFA info. (For
example, glibc's backtrace() function only provides the return addresses.)
libunwind can do this on Linux and OSX, but only for frames for which it has CFI
(call frame information). It has a dynamic CFI registration mechanism, but
it was only ever implemented for ia64. It appears that it would be relatively
easy to modify libunwind to accept standard DWARF debug info, and I have a
patch to generate such info (used for providing gdb with the JIT code
information.) I'm not sure what the performance cost is of generating that
info. I do know that generating the full DWARF info plus embedding it into an
ELF file and queueing it up for GDB to consume is very slow, but I don't know
how much of that is the DWARF generation itself.

The easier solution is to look one frame deeper/older, because JaegerMonkey
arranges things so that the VMFrame will be passed as the first parameter to
any called functions. So assuming the deeper frame is not itself JITted,
libunwind can give you the stack pointer saved for a given frame and the
VMFrame pointer can be read off the top of the stack. libunwind will give
*some* value for the stack pointer even if it gets confused by JIT frames, so
with some validation against the native stack and full validation on anything
pulled out of the VMFrame, it can still be used optimistically even without
implementing dynamic JIT registration for libunwind.

But to get the PC itself, you need to call maybeScript() on each JS frame,
which could potentially access fp->fun()->isInterpreted() -- which means the
fp->fun() must point to a valid memory region. This is detectable using the conservative GC machinery, with careful handling to avoid seeing intermediate state of the bookkeeping.

The PC can be validated against the script's bytecode range.

To retrieve the PCs for the JS frames,

  cx = threadData.currentContext()
  foreach jsframe in AllFramesIter(threadData):
    if ! validStackPointer(cx, jsframe):
      bail

== Delayed Analysis ==

Another source of pain is that stack snapshotting should be fast. You don't
want to interfere with regular timing any more than necessary. That means that
during a signal handler you mainly just want to walk the C and JS stacks,
record everything you need into fixed-size buffers (no memory allocation,
remember!), and continue. A separate thread can walk along and do any necessary
detailed analysis.

When saving out the JS stack, you want to copy out as little information as
possible, because of the cost in both time and space. Unfortunately, by the
time the profiler thread gets to a sample, any pointers to data structures that
you captured when taking the sample may have expired.

So for each type of data involved, there are a couple of choices: (1) copy
anything needed; (2) detect that the data has expired and drop the sample; (3)
don't copy initially, but when the datum expires check whether it might be
needed by a sample and copy out whatever is needed at that time.

Data structures in question:
* JSScript - used to get filename and lineno, and map a PC to a line number
* Script filename (they have a different lifetime than JSScript)
* JITScript - used to map IPs to PCs

=== JSScript ===

During the signal handler, all scripts are checked against the global table of
valid scripts, so the script is known to be fully valid and all fields can be
used freely.

During the delayed sample processing, scripts may have died. A callback on
script destruction queues up a "PendingDeadScript", which keeps a copy of the
script's filename, line number range, source notes, and other data that will be
needed later. Then the script is released to be destroyed. (Note that script
destruction happens during GC, and by the time the profiler knows that a script
is to be destroyed, it's too late to re-root it to save it.) Periodically, the
pending dead script queue will be updated to discard script corpses that are
old enough to not be needed.

This is not a great solution, because it means saving info for *all* dying
scripts, not just ones that were active or hit by a sample.

Perhaps a better approach would be to make the global table of live scripts
keep a counter of how many times each script was hit by a sample. I haven't
thought too hard about this, but I think it might require taking a lock from
the signal handler, which is always messy.

Another alternative would be to discard samples that include dead scripts,
because scripts only die during GC anyway. That's not great from the point of
view of a sampling profiler, because "heavy" scripts both execute frequently
and allocate lots of memory, and so they would be under-represented in the
profile. But perhaps the percentage loss is low enough.

Finally, the signal handler could construct a set of all scripts that were
sampled, and root them for the GC. This feels somewhat hairy from the locking
perspective (the signal handler would need to lock against reads from the
profiler thread and the profiled thread), but it might be reasonable.

=== Script Filenames ===

Many scripts share the same filename, so the lifetimes of script filenames is
independent from scripts'. Right now, I'm keeping a separate table of
filenames, but I never delete from it, so let's just say that I haven't thought
too deeply about this one.

=== Native Address to JIT Code Mappings ===

When handling an IP taken at time T0, the table only tells me if the script is
still alive at time T1 (when the sample is being processed.) So I also maintain
a "history log" which records every script creation/destruction event and when
it happens (with respect to the sample counter). Conceptually, you could first
look up a script in the global table, then walk through the history log in
reverse time order to modify whatever was found. In practice, you scan the log
in forward time order: skip over all entries that happened before T1. Then the
next entry found is the first event relevant to that IP that happened *after*
that IP was sampled. If it is a creation, then the IP could not have been in
the table before that point. If it is a deletion, then the IP *was* in the
table, but is no longer valid. If the IP is not found in the history log, then
the global table is valid for both T0 and T1.

If the IP was found in the global table, then we can use it freely.

If the IP was not found at all, or a creation event for it was found in the
history log, then the IP does not belong to JIT code.

If the IP was found in a deletion event in the history log, then it belongs to
a JITScript that has been deleted. To handle these, a callback on JITScript
deletion scans through the queue of pending samples looking for matching IPs.
If any are found, the IP -> PC mapping is done and written into a side table,
then the JITScript is allowed to die. When the sample is processed, it checks
in that table for IP -> PC mappings of the appropriate age.

The the history log is regularly pruned to discard events that are old enough
that no sample could possibly use them. Note that this must consider *all*
active profilers, since the history log is global.

== Interleaved Stacks ==

The native stack and the JS stack are somewhat independent, but it is useful to
treat them as interleaved: a JIT frame on the native stack might correspond to
a contiguous subsequence of the JS stack, as would js::Interpret frames.

  (C)  main() calls
  (C)  js::RunScript() calls
  (C)  js::Interpret() executes
  (JS) http://www.ducklips.com/defenestrate.js:17 calls
  (JS) http://www.ducklips.com/defenestrate.js:234 calls
  (JS) http://cdn.net/jquery-7.2.js:33 calls
  (C)  nsXPConnect::doStuff() calls
  (C)  nsDOMWhack::match() calls
  (C)  nsXPConnect::invokeGetter() calls
  (C)  js::mjit::InvokeMethodJIT() executes
  (JS) http://cdn.net/jquery-7.2.js:182 calls
  (JS) http://cdn.net/jquery-7.2.js:79 calls
  (C) js::math::Cosine()

[any resemblance to actual C++ or JS function names is purely coincidental]

Interleaving the stacks is (relatively) straightforward: JIT frames contain the
VMFrame data structure, which contains both a (possibly stale) current fp and
the fp at which the JIT was first invoked (the 'entryfp'). The truly current fp
is kept in a known register, so we can know the exact start and end fps.

It's almost the same with js::Interpret: the current fp is maintained in a
FrameRegs struct stored in a local variable. The entryfp is passed in as a
parameter. So if js::Interpret is somewhere on the stack, we can use the CFI
(Call Frame Information) from the stack unwinding to find the address
corresponding to js::Interpret's activation frame, and from that look up the
relevant local variables. (If the innermost frame of our native stack *is*
js::Interpret, then this won't necessarily work since the most up-to-date value
might be in a register. But the JS stack frame pointer is only modified when JS
scripts are invoked, which requires nontrivial C function calls, which means
they'll be saved across those calls. So we'll usually get the right answer just
by looking at the saved locals, and we can accept a little bit of staleness in
our stack reconstruction procedure.)

What is required for this is the native address range of js::Interpret (so we
can recognize native stack frames corresponding to js::Interpret), and the
offsets of those local variables. To figure out the address range, I insert
registration calls at the beginning and end of js::Interpret. Within those
calls, I use libunwind to walk up the stack one frame, and record those return
addresses. The resulting address range doesn't cover the whole of
js::Interpret, but it doesn't really need to either. (Anything outside of that
region is before or after interpreting any JS code, so no JS frames really
"belong" to that invocation of js::Interpret anyway.)

To get the save locations of the locals, I pass their addresses into one of the
registration routines. libunwind tells me the CFA (Call Frame Address, the
stack pointer corresponding to the js::Interpret activation), so I just compute
the offset from the CFA to each of the locals' addresses.

The rest is just data twiddling. Using the full JS stack, and the set of native
stack frames that "own" JS stack frame subsequences, weave them together into
one data structure based on the <fp,entryfp> ranges for JIT and js::Interpret
frames.

== Native Stack Walking ==

Note that all of this depends on being able to walk the native stack. So far, I
have relied on having debug symbols available, and have only used 64-bit Linux.
I've found libunwind to be surprisingly robust, even managing to see through
JIT stack frames to the C++ frames underneath them, which is more than I can
say for GDB. To have this generally useful, we'd want to be able to walk stacks
in production builds on all OSes and architectures. Here's my handwavey
thinking about how to achieve this:

First, consider Linux. I think libunwind is a good solutioni here. The quick
fix is to enable the frame pointer (and make sure that libunwind relies on it;
given the amd64 ABI, an unwinder could legitimately ignore it.) That kind of
sucks, so the next fallback would be compiling with .eh_frame sections that
give the necessary unwind info. This shouldn't cost anything in runtime
performance (assuming it doesn't get read off of disk unnecessarily, but I'll
ignore that for now), though it does cost space. I'm hoping that just the
.eh_frame sections are small enough to be tolerable, but if not, we could
compress them by discarded the portions of the unwind tables that give unneeded
registers. I think we could probably just keep the CFA, return address, stack
pointer, whatever register maintains the current JS StackFrame for JIT code,
and whatever registers are needed to compute those values (if any; an example
might be the frame pointer when it's being used for that purpose.) And
technically, we really only need the JS frame register for functions that might
be directly called from JIT code.

The main idea is that we don't need debug info; we just need the same info used
to unwind the stack for C++ exception handling. (Namely, the .eh_frame section,
though if we don't want it to be mapped into memory we could use .debug_frame
instead.)

I'm not very familiar with OSX, so I'll pretend that it's identical to Linux.
Though apparently it isn't; you need some "dlsym" thing for regular debug info.

I'm totally unfamiliar with Windows. Full debug info is in PDBs, I guess. But
it seems like (1) the general idea that we need way, way less than full debug
info holds; and (2) Windows still needs to be able to unwind stacks for
exception handling, so there should be some analog of .eh_frame.

== IonMonkey ==

IonMonkey is going to switch to a unified stack, so the native stack will
contain one frame for each JS frame, embedded at the right spot, using the same
conventions as the native C/C++ code. This should remove much of the
complexity, because only a single stackwalk is required, and it doesn't depend
on all kinds of data that might be in flux at the time of observation. You
would still need to know what type of frame each native frame is, in order to
know how to unwind it and look up the local variables that would give the
source location info.

== Status and Future ==

=== Tests ===

This is brittle code that relies on unstable code. Without tests it will break
frequently.

=== Platform support ===

I have only been developing on amd64 Linux with frame pointers and debug
symbols. The JS stack walker is mostly useless without support for OSX,
Windows, and Android.

amd64: libunwind should work fine on x86 and ARM, though I think I have some
minor register naming stuff to fix to make it properly portable.

Linux: libunwind should work on OSX, but I haven't tested it. (Remember that I
am using more from libunwind than just the return address stack.) libunwind
does not and never will work on Windows. The Windows API has a StackWalk64 that
contains a stack pointer, which should be good enough for our purposes.

Frame pointers and debug symbols: this is the tough part. It's no use relying
on frame pointers, because (1) our release builds won't have them and (2) the
amd64 ABI doesn't promise they'll work anyway.

For libunwind, the next step would be to look at the size of the minimum debug
information required to walk the stack and access the locals we care about, and
implement a way to download just that much when profiling is turned on.
Alternatively, we could look at the cost of compiling in .eh_frame sections to
see if it would be feasible to just have the information there all of the time.

For Windows, Ehsan is looking into this. His current plan is to use a tool to
strip down the PDB files to produce much smaller ones. WinAPI's StackWalk64
accepts function pointers for accessing debug info, so we just need to write a
version that handles our variant. Sounds great to me! An alternative would be
to use (cached) symbol server lookups.

=== SPS Integration ===

SPS (Simple Profiler System) is a separate profiler that currently only has
native stack walking, but which would like to incorporate JS stacks. Probably
the easiest version of JS stacks to integrate would be the interleaved C++/JS
stacks, to avoid pushing the complexity of two independent stacks into all
profile info consumers. (Though much of that complexity is already present in
anything that handles multiple threads with independent stacks.)

=== Stackwalking support ===

JS stack walking unfortunately depends on native stack walking. I have been
using libunwind on x64 Linux with debug symbols. To make this usable in a
production browser, every one of those conditionals needs to be relaxed.

x64: libunwind should handle x86 and ARM

Linux: libunwind *should* work on OSX, though I haven't tested it.

=== JSFunction validity checking ===

To check for the validity of JSFunctions, I am currently doing a generic test
for an addressible address range. This is incorrect, since it could trigger
side effects. I have already discussed the options above, but some way to make
use of the conservative GC address tester seems necessary.

=== Inlined Frames ===

The support for inlined frames is partial. As mentioned above, StackIter
materializes inline frames before doing its iteration, but that's unsuitable
for signal handler use because it writes to memory. A profiler also probably
would rather reflect the unmodified state anyway. AllFramesIter does not
materialize frames, but the support for describing and traversing them is
incomplete. (It may even be broken with inlined frames currently, eg throwing
out any stack with an inlined frame. I haven't tested.)

=== Thread safety and multiple runtimes ===

I have tried hard to get the thread safety right, but there is approximately a
0% chance that it is completely correct -- *especially* if you want to use this
on more than one thread at a time.

One particularly shaky area is that I recently changed which threads access
which CodeMap-related data structures, and I need to audit the
locking/flag-checking code. (Whenever the signal handler starts accessing
things that might be locked by the main thread, it gets messy.)

=== Performance ===

The one truly horrible performance problem I currently know of is that I'm
using a simple unsorted vector for the native address lookup table. This really
ought to be a tree lookup.

I also suspect that the validity checking needs to be optimized.

The current implementation also has too much overhead when the profiler is off.
A specific example: since the table of valid JSScripts must be 100% accurate at
all times, I maintain the table even before the profiler is enabled for any
thread. This overhead could be eliminated by scanning through all scripts in
all compartments in all runtimes when turning on profiling for the first time
(and discarding the table when profiling is turned off.) There are a few others
that need to be dealt with as well. Some of them will degrade the functionality
a bit, but we can live with those losses.

I haven't measured the overall overhead yet, so there are undoubtably other
areas that need to be fixed to use this in a real production setting.

The profiler uses too much memory for script filenames, and leaks that memory.

=== Output ===

So far I'm not doing a whole lot with the profile data being collected. I need
to look at SPS to see if has the frontend functionality we want, and whether
it's usable in a way that doesn't require the full browser.

I'd also like to produce basic gprof-style textual reports and kcachegrind
input.

== Landing ==

To get a minimally useful version running on a single platform and
configuration:

* Augment the current JIT registration API
* Fix the script filename memory leak
* Fix the perf overhead when profiling is off
* Land the deque implementation I am using (or figure out how to eliminate its use)
* Land a small patch to add a line numbering src note to the beginning of all scripts (it is currently omitted because it is redundant with script->lineno, but the stack walker sometimes needs it when the script is dead.) Or eliminate the necessity for it.
* Land js_MapPCToLineNumber, an API that is usable when the original script is dead but a copy of the src notes is still available.
* Land configure.in changes to link in libunwind
* Fix the compile on currently-unsupported platforms
* Land shell integration (implemented, but it may be excessive -- it includes yet another embedded options parser)
* Profile the overhead of the RAII-style "activity" markers that I've added to most JM stub calls to see if it's acceptable to land with them in.