<div dir="ltr">Hi,<div><br></div><div>I worked on these 2 optimizations to libunwind:</div><div>- I replaced the global cache by a thread-local cache. This removes the need for some locking.</div><div>- Instead of restoring all registers for every stack frame, I restore only EBP, EIP and ESP.</div><div><br></div><div>The code is here:</div><div><a href="https://github.com/fdoray/libunwind/tree/minimal_regs" target="_blank">https://github.com/fdoray/libunwind/tree/minimal_regs</a><br></div><div>Warning: This version of the library is no longer signal-safe and has undefined behavior if more registers than EBP/EIP/ESP are required to unwind a stack frame (this never happened in the few tests that I made so far). These two limitations could easily be overcome in the future.</div><div><br></div><div>Performance results, on x86_64:</div><div><br></div><div>unw_backtrace(), original libunwind</div><div>Mean time per backtrace: 6130 ns / 80% of samples between 1479 and 13837 ns<br></div><div><br></div><div>unw_backtrace(), modified libunwind ***</div><div>Mean time per backtrace: 4255 ns / 80% of samples between 1526 and 5252 ns.</div><div><br></div><div>unw_step()/unw_get_reg() [1], original libuwndin</div><div>Mean time per backtrace: 43520 ns / 80% of samples between 13705 and 58782 ns.<br></div><div><br></div><div>unw_step()/unw_get_reg(), modified libunwind</div><div>Mean time per backtrace: 5804 ns / 80% of samples between 2844 and 11325 ns.</div><div><br></div><div>Francois</div><div><br></div><div>[1] As in the example presented here: <a href="http://www.nongnu.org/libunwind/man/libunwind(3).html">http://www.nongnu.org/libunwind/man/libunwind(3).html</a></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Mar 16, 2015 at 8:35 PM, Brian Robbins <span dir="ltr"><<a href="mailto:brianrob@microsoft.com" target="_blank">brianrob@microsoft.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Hi All,<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">This is great. Thank you very much for the information.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">-Brian<u></u><u></u></span></p>
<p class="MsoNormal"><a name="14c2529008d33d03__MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></a></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Francis Giraldeau [mailto:<a href="mailto:francis.giraldeau@gmail.com" target="_blank">francis.giraldeau@gmail.com</a>]
<br>
<b>Sent:</b> Thursday, March 12, 2015 11:34 AM<br>
<b>To:</b> Mathieu Desnoyers<br>
<b>Cc:</b> Brian Robbins; <a href="mailto:lttng-dev@lists.lttng.org" target="_blank">lttng-dev@lists.lttng.org</a><span class=""><br>
<b>Subject:</b> Re: [lttng-dev] Userspace Tracing and Backtraces<u></u><u></u></span></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<div>
<p class="MsoNormal">2015-03-10 21:47 GMT-04:00 Mathieu Desnoyers <<a href="mailto:mathieu.desnoyers@efficios.com" target="_blank">mathieu.desnoyers@efficios.com</a>>:<u></u><u></u></p><div><div class="h5">
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><span style="color:black">Francis: Did you define UNW_LOCAL_ONLY before including<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">the libunwind header in your benchmarks ? (see<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"><a href="http://www.nongnu.org/libunwind/man/libunwind%283%29.html" target="_blank">http://www.nongnu.org/libunwind/man/libunwind%283%29.html</a>)</span><span style="font-family:"Arial",sans-serif;color:#222222"> </span><span style="color:black"><u></u><u></u></span></p>
</div>
</div>
</blockquote>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><span style="color:black"><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">The seems to change performance dramatically according to the documentation.<u></u><u></u></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Yes, this is the case. Time to unwind is higher at the beginning (probably related to internal cache build), and also vary according to call-stack depth.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><span style="color:black">Agreed on having the backtrace as a context. The main question left is<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">to figure out if we want to call libunwind from within the traced application<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">execution context.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">Unfortunately, libunwind is not reentrant wrt signals. This is already<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">a good argument for not calling it from within a tracepoint. I wonder<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">if the authors of libunwind would be open to make it signal-reentrant<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">in the future (not by disabling signals, but rather by keeping a TLS<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">nesting counter, and returning an error if nested, for performance<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">considerations).<u></u><u></u></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The functions unw_init_local() and unw_step() are signal safe [1]. The critical sections are protected using lock_acquire() that blocks all signals before taking the mutex, which prevent the recursion.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<div>
<p class="MsoNormal">#define lock_acquire(l,m) \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">do { \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> SIGPROCMASK (SIG_SETMASK, &unwi_full_mask, &(m)); \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> mutex_lock (l); \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">} while (0)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">#define lock_release(l,m) \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">do { \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> mutex_unlock (l); \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> SIGPROCMASK (SIG_SETMASK, &(m), NULL); \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">} while (0)<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">To understand the implications, I did a small program to study nested signals [2], where a signal is sent from within a signal, or when segmentation fault occurs in a signal handler. Blocking a signal differs it when it is unblocked, while
ignored signals are discarded. Blocked signals that can't be ignored have their default behaviour. It prevents a possible deadlock, let's say if lock_acquire() was nesting with a custom SIGSEGV handler trying to get the same lock.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">So, let's say that instead of blocking signals, we have a per-thread mutex, that returns if try_lock() fails. It would be faster, but from the user's point of view, the backtrace will be dropped randomly. I would prefer it a bit slower,
but reliable.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">In addition, could it be possible that TLS is not signal safe [3]? <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<blockquote style="border:none;border-left:solid #1010ff 1.5pt;padding:0in 0in 0in 4.0pt;margin-left:3.75pt;margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">or using the perf capture mechanism that you describe below?</span><span style="color:black"><u></u><u></u></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="color:black">Perf is peeking at the userspace from kernel space, it's another story. I guess that libunwind was not ported to the kernel because it is a large chunk
of complicated code that performs a lot of I/O and computation, while copying a portion of the stack is really about KISS and low runtime overhead.<u></u><u></u></span></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="color:black">If using libunwind does not work out, another alternative I would consider<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">would be to copy the stack like perf is doing from the kernel. However,<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">in the spirit of compacting trace data, I would be tempted to do the following<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">if we go down that route: check each pointer-aligned address for its content.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">If it looks like a pointer to an executable memory area (library, executable, or<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">JIT'd code), we keep it. Else, we zero this information (not needed). We can<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">then do a RLE-alike compression on the zeroes, so we can keep the layout<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">of the stack after uncompression.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"><u></u> <u></u></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Interesting! For comparison, here is a perf event [4] that shows there is a lot of room for reducing the event size. We should check if discarding other saved register values on the stack impacts restoring the instruction pointer register.
Doing the unwind offline also solves signal safety, should be fast and scalable.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Francis<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">[1] <a href="http://www.nongnu.org/libunwind/man/unw_init_local(3).html" target="_blank">http://www.nongnu.org/libunwind/man/unw_init_local(3).html</a><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">[2] <a href="https://gist.github.com/giraldeau/98f08161e83a7ab800ea" target="_blank">https://gist.github.com/giraldeau/98f08161e83a7ab800ea</a><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">[3] <a href="https://sourceware.org/glibc/wiki/TLSandSignals" target="_blank">https://sourceware.org/glibc/wiki/TLSandSignals</a><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">[4] <a href="http://pastebin.com/sByfXXAQ" target="_blank">http://pastebin.com/sByfXXAQ</a><u></u><u></u></p>
</div>
</div></div></div>
</div>
</div>
</div>
</div>
<br>_______________________________________________<br>
lttng-dev mailing list<br>
<a href="mailto:lttng-dev@lists.lttng.org">lttng-dev@lists.lttng.org</a><br>
<a href="http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev" target="_blank">http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev</a><br>
<br></blockquote></div><br></div>