This is a long post.\u00a0 Here’s a summary.<\/p>\n
Valgrind unwinds CFI typically 30 times faster than Breakpad.\u00a0 Bad though that sounds, it’s really encouraging.\u00a0 If we can get even half that speedup — that is, 15 times faster than at present — CFI\/EXIDX unwinding in SPS will be a lot more useful than it currently is.<\/p>\n
There are a number of reasons for the discrepancy, which the post discusses in detail.<\/p>\n
For some time now, we’ve been producing nightlies that have the ability to time-profile themselves using the built-in SPS profiler.\u00a0 SPS is a statistical sample-based profiler that samples specified (C++) threads by unwinding their stacks using a variety of mechanisms.<\/p>\n
In the past couple of months, Fennec and Linux nightlies have acquired the ability to take samples by unwinding the stacks using the same “native” unwind information that would be used for diagnosing a crash with (for example) GDB.\u00a0 On Linux that information is Dwarf2 CFI, and on ARM\/Fennec we use the ARM-specific EXIDX format.\u00a0 The unwinding is done using the Google Breakpad library that lives in our tree.<\/p>\n
Breakpad works well in the sense that it unwinds reliably through both libxul, system libraries and, apparently, JIT-produced code.\u00a0 But it’s slow.\u00a0 After considerable efforts at speeding it up, including some as-yet uncommitted changes (bug 893542<\/a> plus other hacks), Breakpad can unwind at a cost of about 6,600 instructions per frame for x86_64\/Linux, and probably a bit worse for ARM\/Android.<\/p>\n That’s expensive — for a typical 18 frame unwind that comes to around 120,000 instructions.\u00a0 On a desktop processor that can sustain perhaps 2000 million instructions\/second, that means we’d saturate one core at about 16,500 unwinds\/second.\u00a0 Supposing we’d like 90% of the CPU to be used for real work, not unwinding.\u00a0 Then we have budget for only 1650 unwinds\/second, which is pretty hopeless considering we want to sample multiple threads at a 1 KHz rate.\u00a0 On a low end phone, the problem is an order of magnitude worse.<\/p>\n I spent quite some time profiling Breakpad’s core CFI unwind loop on x86_64\/Linux.\u00a0 One thing that becomes very clear from this is that Breakpad is designed for generality, flexibility and correctness, but it is not designed for fast in-process unwinding.<\/p>\n Valgrind also does CFI based unwinding, and has been highly tuned over the years, particularly to support Helgrind, which is very unwind-intensive.\u00a0 I wondered how it compared, so I profiled it — a bit of a tricky exercise, running a big test app on an inner Valgrind (which does a lot of unwinding) on an outer Valgrind, running Callgrind, to get profile data.<\/p>\n The numbers really surprised me.\u00a0 Valgrind’s unwinder achieves about 220 instructions\/frame.\u00a0 That’s 30 times faster than my best Breakpad results so far.\u00a0 Why the huge difference?\u00a0 Surely some mistake?\u00a0 I started digging.\u00a0 First, though, a look at the algorithm.<\/p>\n The core algorithm is simple to understand.\u00a0 We start off with registers taken from the innermost frame — as a minimum, three: the program counter, the stack pointer and the frame pointer.\u00a0 The CFI data provides, for each possible instruction, a set of rules which say how recover the register values in the calling frame.\u00a0 So we apply those rules to our three registers, and repeat.\u00a0 The stack trace we’re after is then the sequence of PC values resulting.<\/p>\n One thing to note is that, although we only want the program counter values, we need to compute values for multiple registers, including at the very least the stack pointer.\u00a0 That’s because return addresses — hence, previous program counter values — are typically in memory at some SP offset, and so we need to know the SP values.<\/p>\n Diehard CFI-heads will recognise that the above description omits a lot of details.\u00a0 Nonetheless it encapsulates what the unwinder needs to be fast at.\u00a0 Viz:<\/p>\n The rule for each register is usually simple, having one of the following two forms:<\/p>\n For example, it might well be the case that, at some point<\/p>\n if we know that the return address is 64 bytes back up the stack.<\/p>\n With that in mind, the differences between the Breakpad and Valgrind implementations are as follows:<\/p>\n Valgrind maintains a 509-entry direct mapped cache containing previously used rule-sets.\u00a0 If we are doing a lot of unwinds, most of them will involve the same few hundred instructions, because the outer parts of the traces are identical or very similar.\u00a0 It achieves a near 100% hit rate in practice.\u00a0 Hence finding the entry comes down to computing “PC % 509”, a couple of loads and a conditional branch to check we’ve got the right entry.<\/p>\n Breakpad has no such cache.\u00a0 When bug 893542 lands it will have at a std::map-based cache.\u00a0 That’s a big improvement on no cache, but it’s still not anywhere near as good as a direct-mapped cache, since any lookup in the cache involves a std::map.find(), which means a red-black tree lookup,\u00a0 costing several hundred instructions.<\/p>\n Breakpad has another disadvantage: its architecture forces the cache test to be placed later than is optimal.\u00a0 Valgrind loads the unwind rules for all shared objects at process startup.\u00a0 Breakpad only reads debuginfo for an object at the first visit of the object.\u00a0 Hence Breakpad’s unwind loop must first, inefficiently, check each PC value to find out whether it needs to read debuginfo for the containing shared object.\u00a0 This alone adds a couple of hundred instructions per frame.<\/p>\n Breakpad is nothing if not flexible.\u00a0 The set of registers it is prepared to unwind is not fixed.\u00a0 Instead it depends on whatever registers the compiler-generated CFI provides unwind rules for. Hence Breakpad produces, at each unwind step, new values for all the integer registers that have a CFI unwind rule available at that location.<\/p>\n Valgrind, on the other hand, just unwinds a fixed set of registers which are known to be important in practice.\u00a0 On x86_64-linux, the set is %rip, %rsp and %rbp.\u00a0 On arm-linux: r15, r14, r13, r12, r11 and r7.\u00a0 If unwinding needs the value of some other register it’s just too bad — unwinding stops and it’s Game Over.\u00a0 But this never appears to be a problem in practice.<\/p>\n This disadvantages Breakpad in two ways.<\/p>\n Firstly, Breakpad unwinds more registers than Valgrind does, because the in-file CFI typically gives unwind rules for more registers.\u00a0 On x86_64-linux, for example, the CFI rules often give unwind info for %r15, %r14, %r13, %r12 and %r11, which Valgrind simply ignores.<\/p>\n Secondly, Valgrind’s use of a fixed register set makes its data structures much more efficient.\u00a0 Breakpad’s unwind loop has to maintain a std::map of register names to register values for all the currently tracked registers, and a similar map for register names to recovery rules.\u00a0 Hence it spends much time iterating over, and looking up in, these mappings.\u00a0 Despite efforts to make these lookups efficient, they can’t come close to Valgrind’s compiled-in (C-style) structs for register and rule sets, that require no lookups or iteration.<\/p>\n Valgrind unwinds with no dynamic memory allocation and dumps the resulting PC values in a known-to-be-large-enough caller-supplied array.<\/p>\n Breakpad constructs a std::vector of StackFrame objects.\u00a0 Each frame therefore requires a heap allocation — and, eventually, deallocation, which just by themselves come to more than Valgrind’s total per-frame cost.\u00a0 The 6,600 insn\/frame cost is after<\/em> I did some experimental restructuring to avoid these allocations.<\/p>\n Valgrind shortcuts in two ways, which makes the comparison slightly unfair.<\/p>\n As described above, Breakpad unwinds all integer registers for which CFI rules are available.\u00a0 Valgrind unwinds a fixed and generally smaller subset.\u00a0 This doesn’t appear to make any difference in practice.<\/p>\n Breakpad tracks the validity state of each register.\u00a0 This helps make unwinding more reliable and is needed to support transitioning between different frame recovery methods (CFI unwind, frame-pointer following, stack scanning) on a per-frame basis.\u00a0 Really, Valgrind ought to do that too.\u00a0 It will give some extra overhead, but not a lot — perhaps increasing the per-frame cost by 50%.<\/p>\n","protected":false},"excerpt":{"rendered":" This is a long post.\u00a0 Here’s a summary. Valgrind unwinds CFI typically 30 times faster than Breakpad.\u00a0 Bad though that sounds, it’s really encouraging.\u00a0 If we can get even half that speedup — that is, 15 times faster than at … Continue reading<\/a><\/p>\n","protected":false},"author":240,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts\/243"}],"collection":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/users\/240"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/comments?post=243"}],"version-history":[{"count":0,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts\/243\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/media?parent=243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/categories?post=243"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/tags?post=243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}The core CFI unwinding algorithm<\/h2>\n
(PC, SP, FP) = <values taken from CPU registers at start of unwind>\r\n\r\n repeat\r\n output_array[index++] = PC\r\n current_ruleset = Lookup_in_huge_table(PC)\r\n new_PC = evaluate_rule(current_ruleset.rule_for_PC,\u00a0 PC, SP, FP)\r\n new_SP = evaluate_rule(current_ruleset.rule_for_SP,\u00a0 PC, SP, FP)\r\n new_FP = evaluate_rule(current_ruleset.rule_for_FP,\u00a0 PC, SP, FP)\r\n PC = new_PC ; SP = new_SP; FP = new_FP;\r\n until\r\n end of stack reached, or we have enough frames<\/pre>\n
new_REG = old_PC (or old_SP or old_FP) + constant\r\n new_REG = read-memory-at( old_PC (or old_SP or old_FP) + constant )<\/pre>\n
new_PC = read-memory-at( old_SP + 64 )<\/pre>\n
Implementation differences<\/h2>\n
\n
Lookup_in_huge_table(PC)<\/pre>\n<\/li>\n<\/ul>\n
\n
\n
\n