<div dir="ltr"><span id="docs-internal-guid-28843a28-6028-98d0-ae63-422ac74f7c10"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">TL;DR: At Google we use a call tracing system called XRay which inserts patchable instrumentation points into function entries and exits. If the community is interested, we'd like to contribute this system to the LLVM project. Many more details are contained in the whitepaper at: <a href="https://storage.googleapis.com/xray-downloads/whitepaper/XRayAFunctionCallTracingSystem.pdf">https://storage.googleapis.com/xray-downloads/whitepaper/XRayAFunctionCallTracingSystem.pdf</a></span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Who's "we": <a href="mailto:dberris@google.com">dberris@google.com</a>, <a href="mailto:echristo@google.com">echristo@google.com</a></span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Overview</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">At Google we use XRay to build binaries that have "nop sleds" at function call entry and exits that we can patch at runtime to insert instrumentation calls. We use this to generate sufficiently accurate function call timings to help track down the source of production service latency. Alternate uses include getting function call statistics (histogram of function timings), and generating function call traces (sample of call stacks) to analyse call graphs (for example, analysing calls to malloc()/free()).</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">We have also developed analysis tools for this data, and are continuing to build on top of them with the intent of making them available outside of Google in the long term.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The key features of this system are:</span></p><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Enable/disable the instrumentation at runtime.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Control which functions get the instrumentation points at compile time. We do this through some configurable heuristics (i.e. only functions with >N instructions or that have loop constructs) and whitelists/blacklists (i.e. always instrument functions X, Y, Z and never instrument functions A, B, C).</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Source-level annotations (__attribute__(...), [[...]]) to specify whether or not a function should be instrumentable at a fine-grained level.</span></p></li></ul><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Currently this works on x86-64, but we are going to make this work on a few other platforms as well.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Proposal</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The approach involves the following:</span></p><br><ol style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">*Clang+LLVM:* Add support for a C++ function attribute ( `[[clang::function-instrument=xray-{always,never}]]`) to indicate whether a function should either always or never be instrumentable. The intent is to propagate this attribute as text attributes on LLVM functions until we can consolidate the function instrumentation implementations to use this attribute too.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">*Clang:* Add flags (`-fxray-instrument=`) to enable and control this behaviour. Further configuration flags will enable users to specify functions to always/never instrument, and add thresholds for some heuristics.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">*LLVM:* Add new LLVM pseudo instructions for indicating where the instrumentation sleds should be placed, and what kind of sleds these are. For entry sleds, we can use the `PATCHABLE_OP` instruction, and a new instruction for patching exits (`PATCHABLE_RET`?) that get handled by the assembly printer per platform. Currently only implemented for x86_64.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">*LLVM:* Use a separate section to map the instrumentation sled locations. This will work even in non-debug builds and the sections will be merged by the linker.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">*compiler-rt:* Implement a few functions in compiler-rt under either profiling or under a new library (we'd like to call it "xray") that look like the following:</span><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><br class="kix-line-break"></span><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">`__xray_patch(...)` <- takes a function pointer, installs some code at runtime in the instrumentation points; the provided function will be user-provided.</span><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><br class="kix-line-break"></span><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">`__xray_cleanup()` <- removes the instrumentation code and turns them back into the "nop sleds".</span><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><br class="kix-line-break"></span><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">`__xray_dump_table(...)` <- provides a means of inspecting the mapping between instrumentation points and function names, useful for post-processing.</span></p></li></ol><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">As a proof of concept usage of this, we're contributing a tool to do function call accounting for a binary. It will use the XRay compiler-rt library to install function call logging to an in-memory circular buffer, and dump out the log to a file at program completion (or triggered with a signal handler) in a simple trace format. There’s also a command-line tool for interpreting this data to generate useful statistics.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">We're committed to bringing more of the runtime library into LLVM with consultation and collaboration with the larger community. This includes things like:</span></p><br><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Support for adding context-specific annotations (e.g. for RPCs, memory allocation/deallocation tracing, etc.)</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Accurate function call logging and heuristics around this to handle programs that do a lot of work.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">A data analysis framework for dealing with a trace format.</span></p></li></ul><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">As an initial step, the high level idea is to build the infrastructure (steps 1-5) into LLVM first to allow us and the community at large to build upon this (bring this to other platforms, make it more efficient, add features that matter when debugging performance issues with C++ binaries, etc.). The next step is potentially to create a project in LLVM dedicated to the tooling around XRay -- this will contain a library for function call logging/tracing, documentation, and libraries for reading/manipulating the trace format that XRay can generate.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Key questions:</span></p><br><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Is this something the LLVM community is interested in having?</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Do you have feedback on the proposed approach?</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:14.6667px;font-family:Arial;vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Do you see any large complications/blockers to getting this supported as part of LLVM?</span></p></li></ul><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Alternatives/Related Art</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">We also looked at other tools that do things similar to what's being proposed here, and we'd like to say a few words about the differences:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Pintools: This works at too low a level (binaries, machine code) which usually doesn't provide as much information or control to the programmer doing the debugging. There are also significant overheads involved in making this work in a production environment.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Intel PT: Although very powerful, the level of detail it provides is very different (and is actually complementary) to doing strictly function call tracing. It also requires hardware and kernel support. XRay is purely in userland.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">dtrace: It requires kernel support to get going, as opposed to a purely userland solution. Although what's being proposed is purely a subset of the functionality available to dtrace, we find that the idea itself (function call tracing) has merit and would like to cite the existence of dtrace as "proof of validity" to the overall approach. :)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Valgrind: There are similarities for what Valgrind does with XRay without needing the instrumentation points to be inserted. Dynamic code rewriting is certainly one possible approach to solving this problem. When we measure the costs of using Valgrind compared to XRay we've found that the targeted nature of XRay's instrumentation (and logging) tended to perform better and more tolerable in production.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">DynamoRIO: DR does much of what Valgrind does in a very flexible and configurable manner. We think XRay can be implemented as a purely runtime-dynamic rewriting approach but the costs of maintaining alternate versions of the code in memory and the effects on indirect function calls makes this less efficient than the combination of static instrumentation points and targeted runtime patching.</span></p><br></span></div>