[XRay][profiler] Part 4: Profiler Mode Wiring

[dberris]

Summary

This is part of the larger XRay Profiling Mode effort.

This patch implements the wiring required to enable us to actually
select the xray-profiling mode, and install the handlers to start
measuring the time and frequency of the function calls in call stacks.
The current way to get the profile information is by working with the
XRay API to __xray_process_buffers(...).

In subsequent changes we'll implement profile saving to files, similar
to how the FDR and basic modes operate, as well as means for converting
this format into those that can be loaded/visualised as flame graphs. We
will also be extending the accounting tool in LLVM to support
stack-based function call accounting.

We also continue with the implementation to support building small
histograms of latencies for the FunctionCallTrie::Node type, to allow
us to actually approximate the distribution of latencies per function.

Depends on D45758 and D46998.

[dberris]

ping @echristo or @kpw?

[pelikan]

Sorry for the late review, and for destroying your diff.

What I think would also make interesting test cases:

• when the call sequence is A → B → C → setjmp(3) ↓ B ↓ A → D → longjmp(3), where an exit from A would be after N times the loop ran
• or (alternatively) strange situations involving C++ exceptions

compiler-rt/lib/xray/tests/unit/allocator_test.cc

37

ASSERT_EQ(A.Counter, 1);

40

ASSERT_EQ(A.Counter, 1);

compiler-rt/lib/xray/tests/unit/function_call_trie_test.cc

40–41

For readability, can we have the TSCs to be 100, 200, 300 etc.? Now the numbers look the same. (and I see a test below does that already)

compiler-rt/lib/xray/xray_allocator.h

13–14

I would at least add a TODO for adding support for replacing this allocator with any of the security-checking ones. (ubsan? efence? valgrind? I keep forgetting the names of them. compiler-rt IIRC has some "secure" allocator too.)

We don't want to become another OpenSSL.

67

static_assert(Size <= 16); to make sure we don't run out of bits when a CPU manufacturer goes crazy?

compiler-rt/lib/xray/xray_function_call_trie.h

25–28

I'd reword/reorder this slightly, to make it clearer what's actually being stored.

FunctionCallTrie represents stack traces of XRay instrumented functions that we've encountered, where a node corresponds to a function call and the path from the root to that node represents its stack trace.

85

IIUC, a comma before "then", or a new sentence.

91

New line not necessary?

117–118

Why are these not unsigned? There's no such thing as a negative count or negative time spent in a function. ShadowStackEntry has the time as u64.

(I'd make the function ID unsigned too.)

118

Please put something like "// TSC ticks" at the end of the line, or introduce u64 typedefs for TSC ticks/deltas to avoid someone mistaking it for nanoseconds or the like.

132

It's not clear to me why does this need FId when the Node pointer below has it as well. Please add a brief comment if it's really necessary.

153

Um, why is this line necessary? :-) Line 230 should work without Allocators:: too.

256–257

Why is the comment related to the function not above the function's first line? Same for exitFunction().

316–320

It's not clear to me from this comment that this function, unlike mergeInto, may create duplicate entries.

compiler-rt/lib/xray/xray_profile_collector.cc

32

I'm not sure a spinning lock is the best idea when deepCopying a huge tree, but have no data to prove anything.

130

Why not just "auto FId"?

135–139

Are you sure "static" is needed here? With just a local zero variable, the compiler may inline the memcpy and turn it into memset, whereas you're telling it to load a thing far away in memory.

That said, I reckon "internal_memset(NextPtr, 0, 4); NextPtr += 4;" would be both easier to read and faster.

152–155

Same here, memset(NextPtr, 0, 8); NextPtr += 8;

compiler-rt/lib/xray/xray_profile_collector.h

11

instruementation has an typoe in it -> instrumentation

Please fix other files as well.

32–33

Why is this a class with public static methods, when it doesn't have any data or subclasses and therefore should be a namespace?

compiler-rt/test/xray/TestCases/Posix/profiling-single-threaded.cc

16–17

These local macros don't make it that much shorter or more readable. Consider either removing "XRAY_" or dropping them.

[pelikan]

compiler-rt/lib/xray/tests/unit/function_call_trie_test.cc

92–93

f0 → f1 → setjmp ↓(f1→f0) longjmp ↓(f1↓f0) longjmp ↓(f1↓f0) should generate lots of exits but only one entry. Or when the profiling starts in a signal handler.

So it shouldn't be "impossible", just "infrequent" :-)

107–111

Test name says "MissingIntermediaryEntry" but this is missing an intermediary *exit*.

146–151

Same, please use multiplies of 100 for TSCs. I wonder whether we should test the TSC time series not being non-decreasing due to TSC mismatches when rescheduling among poorly synchronized CPU packages.

compiler-rt/lib/xray/tests/unit/profile_collector_test.cc

22

did you mean: "the only one we actually care about"?

If we "only care" about it, what more can we do about it? :-)

48

I would at least assert the buffer's size is within some reasonable bounds - has the trailing bit and a function list. Maybe also the zero sentinels in places.

78

Again, some assertions to make sure both threads are reflected in that buffer would be nice. Doesn't have to be too strict.

compiler-rt/lib/xray/tests/unit/segmented_array_test.cc

72

Please also test what happens when you do

Array <TestData> data;
auto it = data.begin();
it--;

Because I think you'll find Offset will be SIZE_MAX. Not sure we want that.

compiler-rt/lib/xray/xray_allocator.h

95

assume NewChain == nullptr. (or BackingStore for that matter)

compiler-rt/lib/xray/xray_profile_collector.cc

51

Why do we need the volatile? It's a global, there's very little optimization the compiler can do anyway... I'd like to see what I missed, thinking it'd be OK without it.

compiler-rt/lib/xray/xray_segmented_array.h

43

So, actually, I never liked linked lists where the prev/next pointers are in a separate region of memory, because that tends to worsen the cache miss rate when you walk through the list, and when the points at which these Chunk things are allocated are reasonably randomized along with the actual data allocations to confuse the CPU prefetcher. Which is why I've always been using LIST/TAILQ versions from queue(3) as they embed these to the structures they're listing. I'm not saying you should rewrite all of this now, but have you thought about putting the prev/next into the T somehow? Is that even possible to do with C++ templates?

45

Why is this necessary, and we can't just use N?

62

InternalAlloc can return nullptr.

154

I suppose these were your debugging statements which can go away (and below).

243

tautology

[dberris]

• fixup: Address comments

compiler-rt/lib/xray/tests/unit/allocator_test.cc

37

This is not a valid assertion, since Counter is not relevant to the allocator's observable properties.

40

Same.

compiler-rt/lib/xray/tests/unit/function_call_trie_test.cc

40–41

Can you explain better why using 100, 200, 300 as opposed to 1, 2, 3 is better?

92–93

Right, changed to "rare".

For now, we've not made special support for setjmp/longjmp instrumentation. While there's a possibility we can do that in the future, we're not counting on being able to differentiate that for now.

The signal handler case is precisely the one we're looking to support here, but that's just one case.

146–151

Good point. I'll leave a TODO for that. In particular we actually need to keep track of the CPU ID instead of just the TSC when we're building the shadow stack. That will let us track the migration of the thread(s).

It's still not clear to me why using multiples of 100 is important. These are just arbitrary numbers anyway, it shouldn't matter what order of magnitude they are.

compiler-rt/lib/xray/tests/unit/profile_collector_test.cc

22

I don't see the difference. English is hard.

"the only one we care about" == "the one we actually only care about"

There are other use-cases for this collection API, some of which we don't cover in this unit test (yet).

In particular, we could be collecting snapshots of the function call trie for a function every so often, and associating a timestamp to that, so we can show profiles over time instead of a single profile.

48

Some of these details aren't really relevant to the unit test. For example:

• The size of the block is dependent on how we've decided to serialise the data. Yes we can assert that the size is not zero (doing that now).
• The function list could be in any order. It's not a relevant feature of the API. What we care about is that we're able to get the data. The concern of parsing this data is not really at this level of the unit test (I'd rather we have an actual end-to-end test that would get this information).
• We're testing that we can get a buffer that's not the empty buffer, which tells us enough information to say that this API in particular is holding its promises based on the preconditions and postconditions.

compiler-rt/lib/xray/tests/unit/segmented_array_test.cc

72

That's technically testing for undefined behaviour -- i.e. outside of the contract of the container. :)

compiler-rt/lib/xray/xray_allocator.h

13–14

We already do that, because we're relying on the underlying allocator for sanitizer_common. There's already a way to provide alternate implementations of those in that regard. All the backing store we have is gotten from sanitizer_common as opposed to using our own calls to mmap directly.

compiler-rt/lib/xray/xray_function_call_trie.h

117–118

There are some potentially subtle issues with using unsigned in these variables. Some of them are:

• Forcing a value to be unsigned causes the compiler to implement modular arithmetic, even if we don't ever expect that values will wrap-around.
• Doing zero-sign extension is not cheap. We want to make these values as cheap as possible to update.

Also, we cannot make the function ID unsigned, because the value we're getting from XRay is a signed number (int32_t). The conversion will not be faithful, and we've avoided unsigned in those cases for similar reasons.

If we decide in the future that we can actually get away with unsigned values for function ids (which I think we can) then we can change all the XRay implementations to take unsigned values for the function id, etc. -- most of which is not really worth the cost.

132

This is an optimisation, so that we don't actually need to reach into the pointer just to get the function id of the function at the top of the stack.

153

This is necessary because users of this nested type need to access these exported types. In this case, because NodeRefAllocatorType is part of the FunctionCallTrie type, we're re-exporting this type through Allocators which is a public type.

256–257

Because the comment is an implementation detail, it's explaining what it's doing rather than what users need to expect (i.e. it's not documentation of the contract, it's documentation of the implementation detail).

316–320

Good point. Updated the comment and the implementation to make it clear that we're *not* destroying the state of the FunctionCallTrie in O.

compiler-rt/lib/xray/xray_profile_collector.cc

32

Note, the intent here is to use the GlobalMutex to lock operations on the ThreadTries vector. We shouldn't be holding a lock on the GlobalMutex while in the process of copying the FunctionCallTrie.

compiler-rt/lib/xray/xray_profile_collector.h

32–33

Good point. It started as a class that had member variables, until it evolved to a global implementation, which is better just as a namespace.

compiler-rt/lib/xray/xray_segmented_array.h

43

What you're talking about is intrusive lists. These work only if you're doing a linked list of elements, but in this case it's the chunks we're linking together. Each chunk will have a block, which is what we're managing. All the chunks come from the same region of memory.

45

Usability -- because you can do:

Chunk C;
assert(C.Size > 0);

compiler-rt/test/xray/TestCases/Posix/profiling-single-threaded.cc

16–17

Yeah, unfortunately without these clang-format gets confused. :D

[echristo]

Can this possibly be split up? It's way too long to easily review and seems to at least have two sets of functionality.

[dberris]

Split into smaller parts.

[dberris]

Retitled, and updated to reflect breakup into smaller parts.

[dberris]

Adding back llvm-commits.

[kpw]

This one is more straightforward than the previous in the change. The main ideas all fall into place nicely, but I have pointed out some details that could use some attention.

compiler-rt/lib/xray/xray_profiler.cc

42

Can you expand the initialism to thread-local data in a comment? I always think TopLevelDomain when I see this and after jumping to definition that would help refresh my memory.

52

Don't you need pthread_create first for ProfilingKey?

106

Seems to me this should be memory_order_acquire_release if we want mutual exclusion of profileCollectorService::reset() from another thread.

143–144

Maybe check verbosity and Report?

157–169

I think this should be wrapped in an "if (TLD.FCT)" block.

It's definitely an edge case, but If ProfileLogStatus is INITIALIZED, and if the atomic load happens and before the next statement a context switch and update to FINALIZING happens, then the TLD can be unitialized, but the status check won't know about the FINALIZING statement and we'll deference a null TLD.FCT.

I think there is a similar problem with moving the GetTLD() before the atomic_load for the transition from FINALIZED to INITIALIZING. You could solve it by having GetTLD return the TLD reference and status from the load.

It also might be worth documenting that InternalAlloc won't return null (as opposed to FCT allocator, so we're relying on that.

190–191

Not scoped to profiling mode: This stragegy still makes me uncomfortable for cases where not much is instrumented (e.g. event tracing), but I don't have a better solution fleshed out.

It kind of feels like a cooperative scheduling problem where threads should check periodically if they're cancelled. Maybe we could have an option to add sleds that just do a finalizing check without instrumenting so that sparse instrumentation is able to respect the grace period.

199

Is this protected from simultaneous calls to postCurrentThreadFCT if other threads take a while to see they're finalized.

211–214

Do you have that graph of valid state transitions? I though it was OK to go from FINALIZED back to INITIALIZED without going back to UNITIALIZED.

230–231

Can these error for bad/missing flags?

241

Ahh. Can you just make a comment near the pthread_set_specific that INITIALIZE is responsible for calling pthread_key_create.

compiler-rt/test/xray/TestCases/Posix/profiling-multi-threaded.cc

5–6

Is it xray-profiler or xray-profiling? Does the flag not match the mode string in code? You assert on xray-profiling and set the mode to that in code below.

9

Do you need a thing to exclude windows since you're calling readtsc()

30

Yes please. ;)

compiler-rt/test/xray/TestCases/Posix/profiling-single-threaded.cc

6

Similar flag confusion.

48

Could be illustrative and increase coverage to have a test case that verifies that profiling mode can turn back on after a "round."

[kpw]

in the chain* I meant.

[dberris]

• fixup: Use updated name for flags
• fixup: address comments by kpw@, rename to use profiling instead of profiler

[dberris]

compiler-rt/lib/xray/xray_profiler.cc

42

Renamed to ProfilingData instead.

143–144

Yeah, we'll need to refactor this to instead use the same reentrance guard across all the implementations (FDR and Basic). I'll add a dependency to the C++ ABI changes which has those changes.

190–191

Yep, we talked about this offline and we'll need to fix this across the implementations anyway. Let's fix that later.

199

serialize() has internal synchronisation, so we're relying on that synchronisation to do the right thing.

211–214

Yeah, unfortunately it seems that we're going to need to make it so that once an implementation has flushed, it should go back to UNINITIALIZED. Either that, or we're going to have to be a bit more clever about this.

230–231

Yes, but we're really just ignoring them here -- the parser will already report if the verbosity is high enough.

compiler-rt/test/xray/TestCases/Posix/profiling-multi-threaded.cc

5–6

There's two parts here -- there's the mode, which in this case is a name for the implementation. We're using "profiler" to be consistent with "flight data recorder" and "basic". We could just make this "xray-profiling" all throughout, which I think would make it much simpler -- and pretend that "FDR" is "flight data recording" instead. ;)

9

Good point. Yes, need to require Linux for now.

compiler-rt/test/xray/TestCases/Posix/profiling-single-threaded.cc

48

Good call, let me do that in the next round.

[dberris]

Rebase after removing ABI reliance and refactoring of RecursionGuard.

• fixup: s/__sanitizer:://g + clang-format
• fixup: use the common recursion guard
• fixup: remove C++ ABI dependency
• fixup: do two rounds of profiling

[dberris]

This is now ready for a look @kpw.

[kpw]

I'm going to have to download the renamed files to diff locally. Is there a way to do this in Differential that I'm missing?

compiler-rt/test/xray/TestCases/Posix/profiling-multi-threaded.cc

9

I think this still must be done before you submit.

[dberris]

In D44620#1127115, @kpw wrote:

I'm going to have to download the renamed files to diff locally. Is there a way to do this in Differential that I'm missing?

I'm not sure, but it looks like Differential already sees the rename/merge -- is there something else you're looking for?

compiler-rt/test/xray/TestCases/Posix/profiling-multi-threaded.cc

9

I looked into this and we already only enable all the tests for Linux from the lit configurations.

compiler-rt/lib/xray/CMakeLists.txt

 # Build for all components of the XRay runtime support library.
 
 # XRay runtime library implementation files.
 set(XRAY_SOURCES
     xray_init.cc
     xray_flags.cc
     xray_interface.cc
     xray_log_interface.cc
     xray_utils.cc)
 
 # Implementation files for all XRay modes.
 set(XRAY_FDR_MODE_SOURCES
     xray_buffer_queue.cc
     xray_fdr_logging.cc)
 
 set(XRAY_BASIC_MODE_SOURCES
     xray_inmemory_log.cc)
 
+set(XRAY_PROFILER_MODE_SOURCES
+    xray_profiler.cc
+    xray_profile_collector.cc)
+
 # Implementation files for all XRay architectures.
-set(aarch64_SOURCES xray_AArch64.cc xray_trampoline_AArch64.S)
-set(arm_SOURCES xray_arm.cc xray_trampoline_arm.S)
-set(armhf_SOURCES ${arm_SOURCES})
-set(mips_SOURCES xray_mips.cc xray_trampoline_mips.S)
-set(mipsel_SOURCES xray_mips.cc xray_trampoline_mips.S)
-set(mips64_SOURCES xray_mips64.cc xray_trampoline_mips64.S)
-set(mips64el_SOURCES xray_mips64.cc xray_trampoline_mips64.S)
+set(x86_64_SOURCES
+    xray_x86_64.cc
+    xray_trampoline_x86_64.S)
+
+set(arm_SOURCES
+    xray_arm.cc
+    xray_trampoline_arm.S)
+
+set(armhf_SOURCES
+    ${arm_SOURCES})
+
+set(aarch64_SOURCES
+    xray_AArch64.cc
+    xray_trampoline_AArch64.S)
+
+set(mips_SOURCES
+    xray_mips.cc
+    xray_trampoline_mips.S)
+
+set(mipsel_SOURCES
+    xray_mips.cc
+    xray_trampoline_mips.S)
+
+set(mips64_SOURCES
+    xray_mips64.cc
+    xray_trampoline_mips64.S)
+
+set(mips64el_SOURCES
+    xray_mips64.cc
+    xray_trampoline_mips64.S)
+
 set(powerpc64le_SOURCES
     xray_powerpc64.cc
     xray_trampoline_powerpc64.cc
     xray_trampoline_powerpc64_asm.S)
-set(x86_64_SOURCES xray_x86_64.cc xray_trampoline_x86_64.S)
 
 # Now put it all together...
 include_directories(..)
 include_directories(../../include)
 
 set(XRAY_CFLAGS ${SANITIZER_COMMON_CFLAGS})
 set(XRAY_COMMON_DEFINITIONS XRAY_HAS_EXCEPTIONS=1)
 append_list_if(
add_compiler_rt_object_libraries(RTXrayFDR
     CFLAGS ${XRAY_CFLAGS}
     DEFS ${XRAY_COMMON_DEFINITIONS})
   add_compiler_rt_object_libraries(RTXrayBASIC
     OS ${XRAY_SUPPORTED_OS}
     ARCHS ${XRAY_SUPPORTED_ARCH}
     SOURCES ${XRAY_BASIC_MODE_SOURCES}
     CFLAGS ${XRAY_CFLAGS}
     DEFS ${XRAY_COMMON_DEFINITIONS})
+  add_compiler_rt_object_libraries(RTXrayPROFILER
+    OS ${XRAY_SUPPORTED_OS}
+    ARCHS ${XRAY_SUPPORTED_ARCH}
+    SOURCES ${XRAY_PROFILER_MODE_SOURCES}
+    CFLAGS ${XRAY_CFLAGS}
+    DEFS ${XRAY_COMMON_DEFINITIONS})
 
   # We only support running on osx for now.
   add_compiler_rt_runtime(clang_rt.xray
     STATIC
     OS ${XRAY_SUPPORTED_OS}
     ARCHS ${XRAY_SUPPORTED_ARCH}
     OBJECT_LIBS RTXray
                 RTSanitizerCommon
add_compiler_rt_runtime(clang_rt.xray-basic
     OS ${XRAY_SUPPORTED_OS}
     ARCHS ${XRAY_SUPPORTED_ARCH}
     OBJECT_LIBS RTXrayBASIC
     CFLAGS ${XRAY_CFLAGS}
     DEFS ${XRAY_COMMON_DEFINITIONS}
     LINK_FLAGS ${SANITIZER_COMMON_LINK_FLAGS} ${WEAK_SYMBOL_LINK_FLAGS}
     LINK_LIBS ${XRAY_LINK_LIBS}
     PARENT_TARGET xray)
+  add_compiler_rt_runtime(clang_rt.xray-profiler
+    STATIC
+    OS ${XRAY_SUPPORTED_OS}
+    ARCHS ${XRAY_SUPPORTED_ARCH}
+    OBJECT_LIBS RTXrayBASIC
+    CFLAGS ${XRAY_CFLAGS}
+    DEFS ${XRAY_COMMON_DEFINITIONS}
+    LINK_FLAGS ${SANITIZER_COMMON_LINK_FLAGS} ${WEAK_SYMBOL_LINK_FLAGS}
+    LINK_LIBS ${XRAY_LINK_LIBS}
+    PARENT_TARGET xray)
 else() # not Apple
   foreach(arch ${XRAY_SUPPORTED_ARCH})
     if(NOT CAN_TARGET_${arch})
       continue()
     endif()
     add_compiler_rt_object_libraries(RTXray
       ARCHS ${arch}
       SOURCES ${XRAY_SOURCES} ${${arch}_SOURCES} CFLAGS ${XRAY_CFLAGS}
       DEFS ${XRAY_COMMON_DEFINITIONS})
     add_compiler_rt_object_libraries(RTXrayFDR
       ARCHS ${arch}
       SOURCES ${XRAY_FDR_MODE_SOURCES} CFLAGS ${XRAY_CFLAGS}
       DEFS ${XRAY_COMMON_DEFINITIONS})
     add_compiler_rt_object_libraries(RTXrayBASIC
       ARCHS ${arch}
       SOURCES ${XRAY_BASIC_MODE_SOURCES} CFLAGS ${XRAY_CFLAGS}
       DEFS ${XRAY_COMMON_DEFINITIONS})
+    add_compiler_rt_object_libraries(RTXrayPROFILER
+      ARCHS ${arch}
+      SOURCES ${XRAY_PROFILER_MODE_SOURCES} CFLAGS ${XRAY_CFLAGS}
+      DEFS ${XRAY_COMMON_DEFINITIONS})
 
     # Common XRay archive for instrumented binaries.
     add_compiler_rt_runtime(clang_rt.xray
      STATIC
      ARCHS ${arch}
      CFLAGS ${XRAY_CFLAGS}
      DEFS ${XRAY_COMMON_DEFINITIONS}
      OBJECT_LIBS ${XRAY_COMMON_RUNTIME_OBJECT_LIBS} RTXray
foreach(arch ${XRAY_SUPPORTED_ARCH})
     # Basic mode runtime archive (addon for clang_rt.xray)
     add_compiler_rt_runtime(clang_rt.xray-basic
       STATIC
       ARCHS ${arch}
       CFLAGS ${XRAY_CFLAGS}
       DEFS ${XRAY_COMMON_DEFINITIONS}
       OBJECT_LIBS RTXrayBASIC
       PARENT_TARGET xray)
+   # Profiler Mode runtime
+   add_compiler_rt_runtime(clang_rt.xray-profiler
+     STATIC
+     ARCHS ${arch}
+     CFLAGS ${XRAY_CFLAGS}
+     DEFS ${XRAY_COMMON_DEFINITIONS}
+     OBJECT_LIBS RTXrayPROFILER
+     PARENT_TARGET xray)
   endforeach()
 endif() # not Apple
 
 if(COMPILER_RT_INCLUDE_TESTS)
   add_subdirectory(tests)
 endif()

compiler-rt/lib/xray/tests/CMakeLists.txt

macro(add_xray_unittest testname)
   endif()
 endmacro()
 
 if(COMPILER_RT_CAN_EXECUTE_TESTS)
   if (APPLE)
     add_xray_lib("RTXRay.test.osx"
       $<TARGET_OBJECTS:RTXray.osx>
       $<TARGET_OBJECTS:RTXrayFDR.osx>
+      $<TARGET_OBJECTS:RTXrayPROFILER.osx>
       $<TARGET_OBJECTS:RTSanitizerCommon.osx>
       $<TARGET_OBJECTS:RTSanitizerCommonLibc.osx>)
   else()
   foreach(arch ${XRAY_SUPPORTED_ARCH})
     add_xray_lib("RTXRay.test.${arch}"
       $<TARGET_OBJECTS:RTXray.${arch}>
       $<TARGET_OBJECTS:RTXrayFDR.${arch}>
+      $<TARGET_OBJECTS:RTXrayPROFILER.${arch}>
       $<TARGET_OBJECTS:RTSanitizerCommon.${arch}>
       $<TARGET_OBJECTS:RTSanitizerCommonLibc.${arch}>)
   endforeach()
   endif()
   add_subdirectory(unit)
 endif()

compiler-rt/lib/xray/tests/unit/CMakeLists.txt

 add_xray_unittest(XRayBufferQueueTest SOURCES
   buffer_queue_test.cc xray_unit_test_main.cc)
 add_xray_unittest(XRayFDRLoggingTest SOURCES
   fdr_logging_test.cc xray_unit_test_main.cc)
+add_xray_unittest(XRayAllocatorTest SOURCES
+  allocator_test.cc xray_unit_test_main.cc)
+add_xray_unittest(XRaySegmentedArrayTest SOURCES
+  segmented_array_test.cc xray_unit_test_main.cc)
+add_xray_unittest(XRayFunctionCallTrieTest SOURCES
+  function_call_trie_test.cc xray_unit_test_main.cc)
+add_xray_unittest(XRayProfileCollectorTest SOURCES
+  profile_collector_test.cc xray_unit_test_main.cc)

compiler-rt/lib/xray/tests/unit/allocator_test.cc

+//===-- allocator_test.cc -------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a function call tracing system.
+//
+//===----------------------------------------------------------------------===//
+
+#include "xray_allocator.h"
+#include "gtest/gtest.h"
+
+namespace __xray {
+namespace {
+
+struct TestData {
+  s64 First;
+  s64 Second;
+};
+
+TEST(AllocatorTest, Construction) { Allocator<sizeof(TestData)> A(2 << 11, 0); }
+
+TEST(AllocatorTest, Allocate) {
+  Allocator<sizeof(TestData)> A(2 << 11, 0);
+  auto B = A.Allocate();
+  (void)B;
+}
+
+TEST(AllocatorTest, OverAllocate) {
+  Allocator<sizeof(TestData)> A(sizeof(TestData), 0);
+  auto B1 = A.Allocate();
+  (void)B1;
+  auto B2 = A.Allocate();
+  ASSERT_EQ(B2.Data, nullptr);
+}
+
+} // namespace
+} // namespace __xray

compiler-rt/lib/xray/tests/unit/function_call_trie_test.cc

+//===-- function_call_trie_test.cc ----------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a function call tracing system.
+//
+//===----------------------------------------------------------------------===//
+
+#include "xray_function_call_trie.h"
+#include "gtest/gtest.h"
+
+namespace __xray {
+
+namespace {
+
+TEST(FunctionCallTrieTest, Construction) {
+  // We want to make sure that we can create one of these without the set of
+  // allocators we need. This will by default use the global allocators.
+  FunctionCallTrie Trie;
+}
+
+TEST(FunctionCallTrieTest, ConstructWithTLSAllocators) {
+  // FIXME: Support passing in configuration for allocators in the allocator
+  // constructors.
+  thread_local FunctionCallTrie::Allocators Allocators =
+      FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(Allocators);
+}
+
+TEST(FunctionCallTrieTest, EnterAndExitFunction) {
+  thread_local auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+
+  Trie.enterFunction(1, 1);
+  Trie.exitFunction(1, 2);
+
+  // We need a way to pull the data out. At this point, until we get a data
+  // collection service implemented, we're going to export the data as a list of
+  // roots, and manually walk through the structure ourselves.
+
+  const auto &R = Trie.getRoots();
+
+  ASSERT_EQ(R.size(), 1u);
+  ASSERT_EQ(R.front()->FId, 1);
+  ASSERT_EQ(R.front()->CallCount, 1);
+  ASSERT_EQ(R.front()->CumulativeLocalTime, 1u);
+}
+
+TEST(FunctionCallTrieTest, MissingFunctionEntry) {
+  thread_local auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+  Trie.exitFunction(1, 1);
+  const auto &R = Trie.getRoots();
+
+  ASSERT_TRUE(R.empty());
+}
+
+TEST(FunctionCallTrieTest, MultipleRoots) {
+  thread_local auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+
+  // Enter and exit FId = 1.
+  Trie.enterFunction(1, 1);
+  Trie.exitFunction(1, 2);
+
+  // Enter and exit FId = 2.
+  Trie.enterFunction(2, 3);
+  Trie.exitFunction(2, 4);
+
+  const auto &R = Trie.getRoots();
+  ASSERT_FALSE(R.empty());
+  ASSERT_EQ(R.size(), 2u);
+
+  // Inspect the roots that they have the right data.
+  const auto R0 = R[0];
+  ASSERT_NE(R0, nullptr);
+  EXPECT_EQ(R0->CallCount, 1u);
+  EXPECT_EQ(R0->CumulativeLocalTime, 1u);
+
+  const auto R1 = R[1];
+  ASSERT_NE(R1, nullptr);
+  EXPECT_EQ(R1->CallCount, 1u);
+  EXPECT_EQ(R1->CumulativeLocalTime, 1u);
+}
+
+// While missing an intermediary entry may be rare in practice, we still enforce
+// that we can handle the case where we've missed the entry event somehow, in
+// between call entry/exits. To illustrate, imagine the following shadow call
+// stack:
+//
+//   f0@t0 -> f1@t1 -> f2@t2
+//
+// If for whatever reason we see an exit for `f2` @ t3, followed by an exit for
+// `f0` @ t4 (i.e. no `f1` exit in between) then we need to handle the case of
+// accounting local time to `f2` from d = (t3 - t2), then local time to `f1`
+// as d' = (t3 - t1) - d, and then local time to `f0` as d'' = (t3 - t0) - d'.
+TEST(FunctionCallTrieTest, MissingIntermediaryExit) {
+  thread_local auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+
+  Trie.enterFunction(1, 0);
+  Trie.enterFunction(2, 100);
+  Trie.enterFunction(3, 200);
+  Trie.exitFunction(3, 300);
+  Trie.exitFunction(1, 400);
+
+  // What we should see at this point is all the functions in the trie in a
+  // specific order (1 -> 2 -> 3) with the appropriate count(s) and local
+  // latencies.
+  const auto &R = Trie.getRoots();
+  ASSERT_FALSE(R.empty());
+  ASSERT_EQ(R.size(), 1u);
+
+  const auto &F1 = *R[0];
+  ASSERT_EQ(F1.FId, 1);
+  ASSERT_FALSE(F1.Callees.empty());
+
+  const auto &F2 = *F1.Callees[0].NodePtr;
+  ASSERT_EQ(F2.FId, 2);
+  ASSERT_FALSE(F2.Callees.empty());
+
+  const auto &F3 = *F2.Callees[0].NodePtr;
+  ASSERT_EQ(F3.FId, 3);
+  ASSERT_TRUE(F3.Callees.empty());
+
+  // Now that we've established the preconditions, we check for specific aspects
+  // of the nodes.
+  EXPECT_EQ(F3.CallCount, 1);
+  EXPECT_EQ(F2.CallCount, 1);
+  EXPECT_EQ(F1.CallCount, 1);
+  EXPECT_EQ(F3.CumulativeLocalTime, 100);
+  EXPECT_EQ(F2.CumulativeLocalTime, 300);
+  EXPECT_EQ(F1.CumulativeLocalTime, 100);
+}
+
+// TODO: Test that we can handle cross-CPU migrations, where TSCs are not
+// guaranteed to be synchronised.
+TEST(FunctionCallTrieTest, DeepCopy) {
+  auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+
+  Trie.enterFunction(1, 0);
+  Trie.enterFunction(2, 1);
+  Trie.exitFunction(2, 2);
+  Trie.enterFunction(3, 3);
+  Trie.exitFunction(3, 4);
+  Trie.exitFunction(1, 5);
+
+  // We want to make a deep copy and compare notes.
+  auto B = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Copy(B);
+  Trie.deepCopyInto(Copy);
+
+  ASSERT_NE(Trie.getRoots().size(), 0u);
+  ASSERT_EQ(Trie.getRoots().size(), Copy.getRoots().size());
+  const auto &R0Orig = *Trie.getRoots()[0];
+  const auto &R0Copy = *Copy.getRoots()[0];
+  EXPECT_EQ(R0Orig.FId, 1);
+  EXPECT_EQ(R0Orig.FId, R0Copy.FId);
+
+  ASSERT_EQ(R0Orig.Callees.size(), 2u);
+  ASSERT_EQ(R0Copy.Callees.size(), 2u);
+
+  const auto &F1Orig =
+      *R0Orig.Callees
+           .find_element(
+               [](const FunctionCallTrie::NodeRef &R) { return R.FId == 2; })
+           ->NodePtr;
+  const auto &F1Copy =
+      *R0Copy.Callees
+           .find_element(
+               [](const FunctionCallTrie::NodeRef &R) { return R.FId == 2; })
+           ->NodePtr;
+  EXPECT_EQ(&R0Orig, F1Orig.Parent);
+  EXPECT_EQ(&R0Copy, F1Copy.Parent);
+}
+
+TEST(FunctionCallTrieTest, MergeInto) {
+  auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie T0(A);
+  FunctionCallTrie T1(A);
+
+  // 1 -> 2 -> 3
+  T0.enterFunction(1, 0);
+  T0.enterFunction(2, 1);
+  T0.enterFunction(3, 2);
+  T0.exitFunction(3, 3);
+  T0.exitFunction(2, 4);
+  T0.exitFunction(1, 5);
+
+  // 1 -> 2 -> 3
+  T1.enterFunction(1, 0);
+  T1.enterFunction(2, 1);
+  T1.enterFunction(3, 2);
+  T1.exitFunction(3, 3);
+  T1.exitFunction(2, 4);
+  T1.exitFunction(1, 5);
+
+  auto B = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Merged(B);
+
+  T0.mergeInto(Merged);
+  T1.mergeInto(Merged);
+
+  ASSERT_EQ(Merged.getRoots().size(), 1u);
+  const auto &R0 = *Merged.getRoots()[0];
+  EXPECT_EQ(R0.FId, 1);
+  EXPECT_EQ(R0.CallCount, 2);
+  EXPECT_EQ(R0.CumulativeLocalTime, 10);
+}
+
+} // namespace
+
+} // namespace __xray

compiler-rt/lib/xray/tests/unit/profile_collector_test.cc

+//===-- function_call_trie_test.cc ----------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a function call tracing system.
+//
+//===----------------------------------------------------------------------===//
+#include "xray_profile_collector.h"
+#include "gtest/gtest.h"
+#include <thread>
+
+namespace __xray {
+namespace {
+
+static constexpr auto kHeaderSize = 16u;
+
+void ValidateBlock(XRayBuffer B) {
+  ASSERT_NE(static_cast<const void *>(B.Data), nullptr);
+  ASSERT_NE(B.Size, 0u);
+  ASSERT_GE(B.Size, kHeaderSize);
+  // We look at the block size, the block number, and the thread ID to ensure
+  // that none of them are zero (or that the header data is laid out as we
+  // expect).
+  char LocalBuffer[kHeaderSize] = {};
+  memcpy(LocalBuffer, B.Data, kHeaderSize);
+  u32 BlockSize = 0;
+  u32 BlockNumber = 0;
+  u64 ThreadId = 0;
+  memcpy(&BlockSize, LocalBuffer, sizeof(u32));
+  memcpy(&BlockNumber, LocalBuffer + sizeof(u32), sizeof(u32));
+  memcpy(&ThreadId, LocalBuffer + (2 * sizeof(u32)), sizeof(u64));
+  EXPECT_NE(BlockSize, 0u);
+  EXPECT_GE(BlockNumber, 0u);
+  EXPECT_NE(ThreadId, 0u);
+}
+
+TEST(profileCollectorServiceTest, PostSerializeCollect) {
+  // The most basic use-case (the one we actually only care about) is the one
+  // where we ensure that we can post FunctionCallTrie instances, which are then
+  // destroyed but serialized properly.
+  //
+  // First, we initialise a set of allocators in the local scope. This ensures
+  // that we're able to copy the contents of the FunctionCallTrie that uses
+  // the local allocators.
+  auto Allocators = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(Allocators);
+
+  // Then, we populate the trie with some data.
+  Trie.enterFunction(1, 1);
+  Trie.enterFunction(2, 2);
+  Trie.exitFunction(2, 3);
+  Trie.exitFunction(1, 4);
+
+  // Then we post the data to the global profile collector service.
+  profileCollectorService::post(Trie, 1);
+
+  // Then we serialize the data.
+  profileCollectorService::serialize();
+
+  // Then we go through a single buffer to see whether we're getting the data we
+  // expect.
+  auto B = profileCollectorService::nextBuffer({nullptr, 0});
+  ValidateBlock(B);
+}
+
+// We break out a function that will be run in multiple threads, one that will
+// use a thread local allocator, and will post the FunctionCallTrie to the
+// profileCollectorService. This simulates what the threads being profiled would
+// be doing anyway, but through the XRay logging implementation.
+void threadProcessing() {
+  thread_local auto Allocators = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(Allocators);
+
+  Trie.enterFunction(1, 1);
+  Trie.enterFunction(2, 2);
+  Trie.exitFunction(2, 3);
+  Trie.exitFunction(1, 4);
+
+  profileCollectorService::post(Trie, __sanitizer::GetTid());
+}
+
+TEST(profileCollectorServiceTest, PostSerializeCollectMultipleThread) {
+  std::thread t1(threadProcessing);
+  std::thread t2(threadProcessing);
+
+  t1.join();
+  t2.join();
+
+  // At this point, t1 and t2 are already done with what they were doing.
+  profileCollectorService::serialize();
+
+  // Ensure that we see two buffers.
+  auto B = profileCollectorService::nextBuffer({nullptr, 0});
+  ValidateBlock(B);
+
+  B = profileCollectorService::nextBuffer(B);
+  ValidateBlock(B);
+}
+
+} // namespace
+} // namespace __xray

compiler-rt/lib/xray/tests/unit/segmented_array_test.cc

+#include "xray_segmented_array.h"
+#include "gtest/gtest.h"
+
+namespace __xray {
+namespace {
+
+struct TestData {
+  s64 First;
+  s64 Second;
+
+  // Need a constructor for emplace operations.
+  TestData(s64 F, s64 S) : First(F), Second(S) {}
+};
+
+TEST(SegmentedArrayTest, Construction) {
+  Array<TestData> Data;
+  (void)Data;
+}
+
+TEST(SegmentedArrayTest, ConstructWithAllocator) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4, 0);
+  Array<TestData> Data(A);
+  (void)Data;
+}
+
+TEST(SegmentedArrayTest, ConstructAndPopulate) {
+  Array<TestData> data;
+  ASSERT_NE(data.Append(TestData{0, 0}), nullptr);
+  ASSERT_NE(data.Append(TestData{1, 1}), nullptr);
+  ASSERT_EQ(data.size(), 2u);
+}
+
+TEST(SegmentedArrayTest, ConstructPopulateAndLookup) {
+  Array<TestData> data;
+  ASSERT_NE(data.Append(TestData{0, 1}), nullptr);
+  ASSERT_EQ(data.size(), 1u);
+  ASSERT_EQ(data[0].First, 0);
+  ASSERT_EQ(data[0].Second, 1);
+}
+
+TEST(SegmentedArrayTest, PopulateWithMoreElements) {
+  Array<TestData> data;
+  static const auto kMaxElements = 100u;
+  for (auto I = 0u; I < kMaxElements; ++I) {
+    ASSERT_NE(data.Append(TestData{I, I + 1}), nullptr);
+  }
+  ASSERT_EQ(data.size(), kMaxElements);
+  for (auto I = 0u; I < kMaxElements; ++I) {
+    ASSERT_EQ(data[I].First, I);
+    ASSERT_EQ(data[I].Second, I + 1);
+  }
+}
+
+TEST(SegmentedArrayTest, AppendEmplace) {
+  Array<TestData> data;
+  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
+  ASSERT_EQ(data[0].First, 1);
+  ASSERT_EQ(data[0].Second, 1);
+}
+
+TEST(SegmentedArrayTest, AppendAndTrim) {
+  Array<TestData> data;
+  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
+  ASSERT_EQ(data.size(), 1u);
+  data.trim(1);
+  ASSERT_EQ(data.size(), 0u);
+  ASSERT_TRUE(data.empty());
+}
+
+TEST(SegmentedArrayTest, Iterators) {
+  Array<TestData> data;
+  ASSERT_TRUE(data.empty());
+  ASSERT_EQ(data.begin(), data.end());
+  auto I0 = data.begin();
+  ASSERT_EQ(I0++, data.begin());
+  ASSERT_NE(I0, data.begin());
+  for (const auto &D : data) {
+    (void)D;
+    FAIL();
+  }
+  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
+  ASSERT_EQ(data.size(), 1u);
+  ASSERT_NE(data.begin(), data.end());
+  auto &D0 = *data.begin();
+  ASSERT_EQ(D0.First, 1);
+  ASSERT_EQ(D0.Second, 1);
+}
+
+} // namespace
+} // namespace __xray

compiler-rt/lib/xray/xray_allocator.h

+//===-- xray_allocator.h ---------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// Defines the allocator interface for an arena allocator, used primarily for
+// the profiling runtime.
+//
+//===----------------------------------------------------------------------===//
+#ifndef XRAY_ALLOCATOR_H
+#define XRAY_ALLOCATOR_H
+
+#include "sanitizer_common/sanitizer_allocator_internal.h"
+#include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_common/sanitizer_mutex.h"
+#include <cstddef>
+#include <cstdint>
+
+#include "sanitizer_common/sanitizer_internal_defs.h"
+
+namespace __xray {
+
+/// The Allocator type hands out fixed-sized chunks of memory that are
+/// cache-line aligned and sized. This is useful for placement of
+/// performance-sensitive data in memory that's frequently accessed. The
+/// allocator also self-limits the peak memory usage to a dynamically defined
+/// maximum.
+///
+template <size_t N> struct Allocator {
+  // Each Block will have a fixed size, dependent on N. The allocator will hand
+  // out individual blocks identified by the Data pointer, which is associated
+  // with a block.
+  struct Block {
+    /// Compute the minimum cache-line size multiple that is >= N.
+    static constexpr auto Size =
+        kCacheLineSize * ((N / kCacheLineSize) + (N % kCacheLineSize ? 1 : 0));
+    void *Data = nullptr;
+  };
+
+private:
+  // A BlockChain will contain a fixed number of blocks, each with an identifier
+  // to specify whether it's been handed out or not. We keep track of BlockChain
+  // iterators, which are basically a pointer to the chain and an offset into
+  // the fixed set of blocks associated with a link. The iterators are
+  // bidirectional.
+  struct BlockChain {
+    static_assert(kCacheLineSize % sizeof(void *) == 0,
+                  "Cache line size is not divisible by size of void*; none of "
+                  "the assumptions of the BlockChain will hold.");
+
+    // This size represents the most number of pointers we can fit in a cache
+    // line, along with the next and previous pointers, and the bitmap to
+    // indicate which blocks have been handed out, and which ones are available.
+    // This structure corresponds to the following layout:
+    //
+    //   Blocks [ 0, 1, 2, .., Size - 1]
+    //
+    // Using a 16-bit bitmap will allow us to cover a really big cache line that
+    // might store up to 16 pointers.
+    static constexpr auto Size = (kCacheLineSize / sizeof(Block)) - 3;
+    static_assert(Size <= 16, "Need to support larger than 16 ");
+
+    // FIXME: Align this to cache-line address boundaries
+    Block Blocks[Size]{};
+    BlockChain *Prev = nullptr;
+    BlockChain *Next = nullptr;
+    u16 UsedBits = 0;
+  };
+
+  static_assert(sizeof(BlockChain) == kCacheLineSize,
+                "BlockChain instances must be cache-line-sized.");
+
+  static BlockChain NullLink;
+
+  // FIXME: Implement a freelist, in case we actually do intend to return memory
+  // to the allocator, as opposed to just de-allocating everything in one go.
+
+  size_t MaxMemory;
+  SpinMutex Mutex{};
+  BlockChain *Chain = &NullLink;
+  size_t Counter = 0;
+
+  BlockChain *NewChainLink() {
+    auto NewChain = reinterpret_cast<BlockChain *>(
+        InternalAlloc(sizeof(BlockChain), nullptr, kCacheLineSize));
+    auto BackingStore = reinterpret_cast<char *>(
+        InternalAlloc(BlockChain::Size * Block::Size, nullptr, kCacheLineSize));
+    size_t Offset = 0;
+    DCHECK_NE(NewChain, nullptr);
+    DCHECK_NE(BackingStore, nullptr);
+    for (auto &B : NewChain->Blocks) {
+      B.Data = BackingStore + Offset;
+      Offset += Block::Size;
+    }
+    NewChain->Prev = Chain;
+    NewChain->Next = &NullLink;
+    return NewChain;
+  }
+
+public:
+  Allocator(size_t M, size_t PreAllocate) : MaxMemory(M) {
+    // FIXME: Implement PreAllocate support!
+  }
+
+  Block Allocate() {
+    SpinMutexLock Lock(&Mutex);
+    // Check whether we're over quota.
+    if (Counter * Block::Size >= MaxMemory)
+      return {};
+
+    size_t ChainOffset = Counter % BlockChain::Size;
+    u16 BitMask = 1 << ChainOffset;
+
+    if (UNLIKELY(Chain == &NullLink)) {
+      // FIXME: Maybe pre-allocate some BlockChain instances in the same page
+      // as the Block objects.
+      auto NewChain = NewChainLink();
+
+      // Mark the first block in the newly crated link to "used".
+      NewChain->UsedBits |= BitMask;
+
+      // Prepare to return the first block.
+      auto B = NewChain->Blocks[ChainOffset];
+      Chain->Next = NewChain;
+      Chain = NewChain;
+      ++Counter;
+      return B;
+    }
+
+    // We need to see whether we can get one of the blocks already in the chain
+    // link can be used.
+    if ((Chain->UsedBits | BitMask) == 0) {
+      auto B = Chain->Blocks[ChainOffset];
+      Chain->UsedBits |= BitMask;
+      ++Counter;
+      return B;
+    }
+
+    // At this point we know that we've wrapped around, and the current chain no
+    // longer has free blocks. We then allocate a new chain and make that the
+    // current chain.
+    auto NewChain = NewChainLink();
+    NewChain->UsedBits |= BitMask;
+    auto B = NewChain->Blocks[ChainOffset];
+    Chain->Next = NewChain;
+    Chain = NewChain;
+    ++Counter;
+    return B;
+  }
+
+  ~Allocator() NOEXCEPT {
+    // We need to deallocate all the blocks, including the chain links.
+    for (auto C = Chain; C != &NullLink;) {
+      // We know that the data block is a large contiguous page, we deallocate
+      // that at once.
+      InternalFree(C->Blocks[0].Data);
+      auto Prev = C->Prev;
+      InternalFree(C);
+      C = Prev;
+    }
+  }
+};
+
+// Storage for the NullLink sentinel.
+template <size_t N> typename Allocator<N>::BlockChain Allocator<N>::NullLink;
+
+} // namespace __xray
+
+#endif // XRAY_ALLOCATOR_H

compiler-rt/lib/xray/xray_function_call_trie.h

+//===-- xray_function_call_trie.h ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// This file defines the interface for a function call trie.
+//
+//===----------------------------------------------------------------------===//
+#ifndef XRAY_FUNCTION_CALL_TRIE_H
+#define XRAY_FUNCTION_CALL_TRIE_H
+
+#include "xray_profiler_flags.h"
+#include "xray_segmented_array.h"
+#include <utility>
+
+namespace __xray {
+
+/// A FunctionCallTrie represents the stack traces of XRay instrumented
+/// functions that we've encountered, where a node corresponds to a function and
+/// the path from the root to the node its stack trace. Each node in the trie
+/// will contain some useful values, including:
+///
+///   * The cumulative amount of time spent in this particular node/stack.
+///   * The number of times this stack has appeared.
+///   * A histogram of latencies for that particular node.
+///
+/// Each node in the trie will also contain a list of callees, represented using
+/// a Array<NodeRef> -- each NodeRef instance will contain the function
+/// ID of the callee, and a pointer to the node.
+///
+/// If we visulaise this data structure, we'll find the following potential
+/// representation:
+///
+///   [function id node] -> [callees] [cumulative time]
+///                         [call counter] [latency histogram]
+///
+/// As an example, when we have a function in this pseudocode:
+///
+///   func f(N) {
+///     g()
+///     h()
+///     for i := 1..N { j() }
+///   }
+///
+/// We may end up with a trie of the following form:
+///
+///   f -> [ g, h, j ] [...] [1] [...]
+///   g -> [ ... ] [...] [1] [...]
+///   h -> [ ... ] [...] [1] [...]
+///   j -> [ ... ] [...] [N] [...]
+///
+/// If for instance the function g() called j() like so:
+///
+///   func g() {
+///     for i := 1..10 { j() }
+///   }
+///
+/// We'll find the following updated trie:
+///
+///   f -> [ g, h, j ] [...] [1] [...]
+///   g -> [ j' ] [...] [1] [...]
+///   h -> [ ... ] [...] [1] [...]
+///   j -> [ ... ] [...] [N] [...]
+///   j' -> [ ... ] [...] [10] [...]
+///
+/// Note that we'll have a new node representing the path `f -> g -> j'` with
+/// isolated data. This isolation gives us a means of representing the stack
+/// traces as a path, as opposed to a key in a table. The alternative
+/// implementation here would be to use a separate table for the path, and use
+/// hashes of the path as an identifier to accumuate the information. We've
+/// moved away from this approach as it takes a lot of time to compute the hash
+/// every time we need to update a function's call information as we're handling
+/// the entry and exit events.
+///
+/// This approach allows us to maintain a shadow stack, which represents the
+/// currently executing path, and on function exits quickly compute the amount
+/// of time elapsed from the entry, then update the counters for the node
+/// already represented in the trie. This necessitates an efficient
+/// representation of the various data structures (the list of callees must be
+/// cache-aware and efficient to look up, and the histogram must be compact and
+/// quick to update) to enable us to keep the overheads of this implementation
+/// to the minimum.
+class FunctionCallTrie {
+public:
+  struct Node;
+
+  // We use a NodeRef type instead of a std::pair<...> to not rely on the
+  // standard library types in this header.
+  struct NodeRef {
+    Node *NodePtr;
+    int32_t FId;
+
+    // Constructor for inplace-construction.
+    NodeRef(Node *N, int32_t F) : NodePtr(N), FId(F) {}
+  };
+
+  using NodeRefArray = Array<NodeRef>;
+  using NodeRefAllocatorType = NodeRefArray::AllocatorType;
+
+  // A Node in the FunctionCallTrie gives us a list of callees, the cumulative
+  // number of times this node actually appeared, the cumulative amount of time
+  // for this particular node including its children call times, and just the
+  // local time spent on this node. Each Node will have the ID of the XRay
+  // instrumented function that it is associated to.
+  struct Node {
+    Node *Parent;
+    NodeRefArray Callees;
+    int64_t CallCount;
+    int64_t CumulativeLocalTime;  // Typically in TSC deltas, not wall-time.
+    int32_t FId;
+
+    // We add a constructor here to allow us to inplace-construct through
+    // Array<...>'s AppendEmplace.
+    Node(Node *P, NodeRefAllocatorType &A, int64_t CC, int64_t CLT, int32_t F)
+        : Parent(P), Callees(A), CallCount(CC), CumulativeLocalTime(CLT),
+          FId(F) {}
+
+    // TODO: Include the compact histogram.
+  };
+
+private:
+  struct ShadowStackEntry {
+    int32_t FId; // We're copying the function ID into the stack to avoid having
+                 // to reach into the node just to get the function ID.
+    uint64_t EntryTSC;
+    Node *NodePtr;
+
+    // We add a constructor here to allow us to inplace-construct through
+    // Array<...>'s AppendEmplace.
+    ShadowStackEntry(int32_t F, uint64_t T, Node *N)
+        : FId(F), EntryTSC(T), NodePtr(N) {}
+  };
+
+  using NodeArray = Array<Node>;
+  using RootArray = Array<Node *>;
+  using ShadowStackArray = Array<ShadowStackEntry>;
+
+public:
+  // We collate the allocators we need into a single struct, as a convenience to
+  // allow us to initialize these as a group.
+  struct Allocators {
+    using NodeAllocatorType = NodeArray::AllocatorType;
+    using RootAllocatorType = RootArray::AllocatorType;
+    using ShadowStackAllocatorType = ShadowStackArray::AllocatorType;
+    using NodeRefAllocatorType = NodeRefAllocatorType;
+
+    NodeAllocatorType *NodeAllocator = nullptr;
+    RootAllocatorType *RootAllocator = nullptr;
+    ShadowStackAllocatorType *ShadowStackAllocator = nullptr;
+    NodeRefAllocatorType *NodeRefAllocator = nullptr;
+
+    Allocators() {}
+    Allocators(const Allocators &) = delete;
+    Allocators &operator=(const Allocators &) = delete;
+
+    Allocators(Allocators &&O)
+        : NodeAllocator(O.NodeAllocator), RootAllocator(O.RootAllocator),
+          ShadowStackAllocator(O.ShadowStackAllocator),
+          NodeRefAllocator(O.NodeRefAllocator) {
+      O.NodeAllocator = nullptr;
+      O.RootAllocator = nullptr;
+      O.ShadowStackAllocator = nullptr;
+      O.NodeRefAllocator = nullptr;
+    }
+
+    Allocators &operator=(Allocators &&O) {
+      {
+        auto Tmp = O.NodeAllocator;
+        O.NodeAllocator = this->NodeAllocator;
+        this->NodeAllocator = Tmp;
+      }
+      {
+        auto Tmp = O.RootAllocator;
+        O.RootAllocator = this->RootAllocator;
+        this->RootAllocator = Tmp;
+      }
+      {
+        auto Tmp = O.ShadowStackAllocator;
+        O.ShadowStackAllocator = this->ShadowStackAllocator;
+        this->ShadowStackAllocator = Tmp;
+      }
+      {
+        auto Tmp = O.NodeRefAllocator;
+        O.NodeRefAllocator = this->NodeRefAllocator;
+        this->NodeRefAllocator = Tmp;
+      }
+      return *this;
+    }
+
+    ~Allocators() {
+      // Note that we cannot use delete on these pointers, as they need to be
+      // returned to the sanitizer_common library's internal memory tracking
+      // system.
+      if (NodeAllocator != nullptr) {
+        NodeAllocator->~NodeAllocatorType();
+        InternalFree(NodeAllocator);
+      }
+      if (RootAllocator != nullptr) {
+        RootAllocator->~RootAllocatorType();
+        InternalFree(RootAllocator);
+      }
+      if (ShadowStackAllocator != nullptr) {
+        ShadowStackAllocator->~ShadowStackAllocatorType();
+        InternalFree(ShadowStackAllocator);
+      }
+      if (NodeRefAllocator != nullptr) {
+        NodeRefAllocator->~NodeRefAllocatorType();
+        InternalFree(NodeRefAllocator);
+      }
+    }
+  }; // namespace __xray
+
+  // TODO: Support configuration of options through the arguments.
+  static Allocators InitAllocators() {
+    Allocators A;
+    A.NodeAllocator = new (INTERNAL_ALLOC) Allocators::NodeAllocatorType(
+        profilerFlags()->xray_profiling_per_thread_allocator_max, 0);
+    A.RootAllocator = new (INTERNAL_ALLOC) Allocators::RootAllocatorType(
+        profilerFlags()->xray_profiling_per_thread_allocator_max, 0);
+    A.ShadowStackAllocator =
+        new (INTERNAL_ALLOC) Allocators::ShadowStackAllocatorType(
+            profilerFlags()->xray_profiling_per_thread_allocator_max, 0);
+    A.NodeRefAllocator = new (INTERNAL_ALLOC) Allocators::NodeRefAllocatorType(
+        profilerFlags()->xray_profiling_per_thread_allocator_max, 0);
+    return A;
+  }
+
+private:
+  NodeArray Nodes;
+  RootArray Roots;
+  ShadowStackArray ShadowStack;
+  NodeRefAllocatorType *NodeRefAllocator = nullptr;
+
+  const Allocators &GetGlobalAllocators() {
+    static const Allocators A = [] { return InitAllocators(); }();
+    return A;
+  }
+
+public:
+  explicit FunctionCallTrie(const Allocators &A)
+      : Nodes(*A.NodeAllocator), Roots(*A.RootAllocator),
+        ShadowStack(*A.ShadowStackAllocator),
+        NodeRefAllocator(A.NodeRefAllocator) {}
+
+  FunctionCallTrie() : FunctionCallTrie(GetGlobalAllocators()) {}
+
+  void enterFunction(int32_t FId, uint64_t TSC) {
+    // This function primarily deals with ensuring that the ShadowStack is
+    // consistent and ready for when an exit event is encountered.
+    if (UNLIKELY(ShadowStack.empty())) {
+      auto NewRoot = Nodes.AppendEmplace(nullptr, *NodeRefAllocator, 0, 0, FId);
+      if (UNLIKELY(NewRoot == nullptr))
+        return;
+      Roots.Append(NewRoot);
+      ShadowStack.AppendEmplace(FId, TSC, NewRoot);
+      return;
+    }
+
+    auto &Top = ShadowStack.back();
+    auto TopNode = Top.NodePtr;
+
+    // If we've seen this callee before, then we just access that node and place
+    // that on the top of the stack.
+    auto Callee = TopNode->Callees.find_element(
+        [FId](const NodeRef &NR) { return NR.FId == FId; });
+    if (Callee != nullptr) {
+      CHECK_NE(Callee->NodePtr, nullptr);
+      ShadowStack.AppendEmplace(FId, TSC, Callee->NodePtr);
+      return;
+    }
+
+    // This means we've never seen this stack before, create a new node here.
+    auto NewNode = Nodes.AppendEmplace(TopNode, *NodeRefAllocator, 0, 0, FId);
+    if (UNLIKELY(NewNode == nullptr))
+      return;
+    TopNode->Callees.AppendEmplace(NewNode, FId);
+    ShadowStack.AppendEmplace(FId, TSC, NewNode);
+    return;
+  }
+
+  void exitFunction(int32_t FId, uint64_t TSC) {
+    // When we exit a function, we look up the ShadowStack to see whether we've
+    // entered this function before. We do as little processing here as we can,
+    // since most of the hard work would have already been done at function
+    // entry.
+    if (UNLIKELY(ShadowStack.empty()))
+      return;
+
+    uint64_t CumulativeTreeTime = 0;
+    while (!ShadowStack.empty()) {
+      auto &Top = ShadowStack.back();
+      auto TopNode = Top.NodePtr;
+      auto TopFId = TopNode->FId;
+      auto LocalTime = TSC - Top.EntryTSC;
+      TopNode->CallCount++;
+      TopNode->CumulativeLocalTime += LocalTime - CumulativeTreeTime;
+      CumulativeTreeTime += LocalTime;
+      ShadowStack.trim(1);
+
+      // TODO: Update the histogram for the node.
+      if (TopFId == FId)
+        break;
+    }
+  }
+
+  const RootArray &getRoots() const { return Roots; }
+
+  // The deepCopyInto operation will update the provided FunctionCallTrie by
+  // re-creating the contents of this particular FunctionCallTrie in the other
+  // FunctionCallTrie. It will do this using a Depth First Traversal from the
+  // roots, and while doing so recreating the traversal in the provided
+  // FunctionCallTrie.
+  //
+  // This operation will *not* destroy the state in `O`, and thus may cause some
+  // duplicate entries in `O` if it is not empty.
+  void deepCopyInto(FunctionCallTrie &O) const {
+    for (const auto Root : getRoots()) {
+      // Add a node in O for this root.
+      auto NewRoot =
+          O.Nodes.AppendEmplace(nullptr, *O.NodeRefAllocator, Root->CallCount,
+                                Root->CumulativeLocalTime, Root->FId);
+      O.Roots.Append(NewRoot);
+
+      // We then push the root into a stack, to use as the parent marker for new
+      // nodes we push in as we're traversing depth-first down the call tree.
+      struct NodeAndParent {
+        FunctionCallTrie::Node *Node;
+        FunctionCallTrie::Node *NewNode;
+      };
+      using Stack = Array<NodeAndParent>;
+
+      typename Stack::AllocatorType StackAllocator(
+          profilerFlags()->xray_profiling_stack_allocator_max, 0);
+      Stack DFSStack(StackAllocator);
+      DFSStack.Append(NodeAndParent{Root, NewRoot});
+      while (!DFSStack.empty()) {
+        NodeAndParent NP = DFSStack.back();
+        DCHECK_NE(NP.Node, nullptr);
+        DCHECK_NE(NP.NewNode, nullptr);
+        DFSStack.trim(1);
+        for (const auto Callee : NP.Node->Callees) {
+          auto NewNode = O.Nodes.AppendEmplace(
+              NP.NewNode, *O.NodeRefAllocator, Callee.NodePtr->CallCount,
+              Callee.NodePtr->CumulativeLocalTime, Callee.FId);
+          DCHECK_NE(NewNode, nullptr);
+          NP.NewNode->Callees.AppendEmplace(NewNode, Callee.FId);
+          DFSStack.Append(NodeAndParent{Callee.NodePtr, NewNode});
+        }
+      }
+    }
+  }
+
+  // The mergeInto operation will update the provided FunctionCallTrie by
+  // traversing the current trie's roots and updating (i.e. merging) the data in
+  // the nodes with the data in the target's nodes. If the node doesn't exist in
+  // the provided trie, we add a new one in the right position, and inherit the
+  // data from the original (current) trie, along with all its callees.
+  void mergeInto(FunctionCallTrie &O) const {
+    for (const auto Root : getRoots()) {
+      Node *TargetRoot = nullptr;
+      auto R = O.Roots.find_element(
+          [&](const Node *Node) { return Node->FId == Root->FId; });
+      if (R == nullptr) {
+        TargetRoot = O.Nodes.AppendEmplace(nullptr, *O.NodeRefAllocator, 0, 0,
+                                           Root->FId);
+        O.Roots.Append(TargetRoot);
+      } else {
+        TargetRoot = *R;
+      }
+
+      struct NodeAndTarget {
+        FunctionCallTrie::Node *OrigNode;
+        FunctionCallTrie::Node *TargetNode;
+      };
+      using Stack = Array<NodeAndTarget>;
+
+      typename Stack::AllocatorType StackAllocator(
+          profilerFlags()->xray_profiling_stack_allocator_max, 0);
+      Stack DFSStack(StackAllocator);
+      DFSStack.Append(NodeAndTarget{Root, TargetRoot});
+      while (!DFSStack.empty()) {
+        NodeAndTarget NT = DFSStack.back();
+        DCHECK_NE(NT.OrigNode, nullptr);
+        DCHECK_NE(NT.TargetNode, nullptr);
+        DFSStack.trim(1);
+        NT.TargetNode->CallCount += NT.OrigNode->CallCount;
+        NT.TargetNode->CumulativeLocalTime += NT.OrigNode->CumulativeLocalTime;
+        for (const auto Callee : NT.OrigNode->Callees) {
+          auto TargetCallee = NT.TargetNode->Callees.find_element(
+              [&](const FunctionCallTrie::NodeRef &C) {
+                return C.FId == Callee.FId;
+              });
+          if (TargetCallee == nullptr) {
+            auto NewTargetNode = O.Nodes.AppendEmplace(
+                NT.TargetNode, *O.NodeRefAllocator, 0, 0, Callee.FId);
+            TargetCallee =
+                NT.TargetNode->Callees.AppendEmplace(NewTargetNode, Callee.FId);
+          }
+          DFSStack.Append(NodeAndTarget{Callee.NodePtr, TargetCallee->NodePtr});
+        }
+      }
+    }
+  }
+
+}; // namespace __xray
+
+} // namespace __xray
+
+#endif // XRAY_FUNCTION_CALL_TRIE_H

compiler-rt/lib/xray/xray_profile_collector.h

+//===-- xray_profile_collector.h -------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// This file defines the interface for a data collection service, for XRay
+// profiling. What we implement here is an in-process service where
+// FunctionCallTrie instances can be handed off by threads, to be
+// consolidated/collected.
+//
+//===----------------------------------------------------------------------===//
+#ifndef XRAY_XRAY_PROFILE_COLLECTOR_H
+#define XRAY_XRAY_PROFILE_COLLECTOR_H
+
+#include "xray_function_call_trie.h"
+
+#include "xray/xray_log_interface.h"
+
+namespace __xray {
+
+/// The ProfileCollectorService implements a centralised mechanism for
+/// collecting FunctionCallTrie instances, indexed by thread ID. On demand, the
+/// ProfileCollectorService can be queried for the most recent state of the
+/// data, in a form that allows traversal.
+namespace profileCollectorService {
+
+/// Posts the FunctionCallTrie assocaited with a specific Thread ID. This
+/// will:
+///
+///   - Make a copy of the FunctionCallTrie and store that against the Thread
+///     ID. This will use the global allocator for the service-managed
+///     FunctionCallTrie instances.
+///   - Queue up a pointer to the FunctionCallTrie.
+///   - If the queue is long enough (longer than some arbitrary threshold) we
+///     then pre-calculate a single FunctionCallTrie for the whole process.
+///
+///
+/// We are making a copy of the FunctionCallTrie because the intent is to have
+/// this function be called at thread exit, or soon after the profiling
+/// handler is finalized through the XRay APIs. By letting threads each
+/// process their own thread-local FunctionCallTrie instances, we're removing
+/// the need for synchronisation across threads while we're profiling.
+/// However, once we're done profiling, we can then collect copies of these
+/// FunctionCallTrie instances and pay the cost of the copy.
+///
+/// NOTE: In the future, if this turns out to be more costly than "moving" the
+/// FunctionCallTrie instances from the owning thread to the collector
+/// service, then we can change the implementation to do it this way (moving)
+/// instead.
+void post(const FunctionCallTrie &T, tid_t TId);
+
+/// The serialize will process all FunctionCallTrie instances in memory, and
+/// turn those into specifically formatted blocks, each describing the
+/// function call trie's contents in a compact form. In memory, this looks
+/// like the following layout:
+///
+///   - block size (32 bits)
+///   - block number (32 bits)
+///   - thread id (64 bits)
+///   - list of records:
+///     - function ids in reverse call order, from leaf to root, terminated by
+///       0 (32 bits per function id)
+///     - call count (64 bit)
+///     - cumulative local time (64 bit)
+///     - record delimiter (64 bit, 0x0)
+///
+void serialize();
+
+/// The reset function will clear out any internal memory held by the
+/// service. The intent is to have the resetting be done in calls to the
+/// initialization routine, or explicitly through the flush log API.
+void reset();
+
+/// This nextBuffer function is meant to implement the iterator functionality,
+/// provided in the XRay API.
+XRayBuffer nextBuffer(XRayBuffer B);
+
+}; // namespace profileCollectorService
+
+} // namespace __xray
+
+#endif // XRAY_XRAY_PROFILE_COLLECTOR_H

compiler-rt/lib/xray/xray_profile_collector.cc

+//===-- xray_profile_collector.cc ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// This implements the interface for the profileCollectorService.
+//
+//===----------------------------------------------------------------------===//
+#include "xray_profile_collector.h"
+#include "xray_profiler_flags.h"
+
+#include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_common/sanitizer_vector.h"
+
+#include <memory>
+#include <utility>
+
+namespace __xray {
+namespace profileCollectorService {
+
+namespace {
+
+SpinMutex GlobalMutex;
+struct ThreadTrie {
+  tid_t TId;
+  FunctionCallTrie *Trie;
+};
+Vector<ThreadTrie> ThreadTries;
+
+struct ProfileBuffer {
+  void *Data;
+  size_t Size;
+};
+Vector<ProfileBuffer> ProfileBuffers;
+
+struct BlockHeader {
+  u32 BlockSize;
+  u32 BlockNum;
+  u64 ThreadId;
+};
+
+FunctionCallTrie::Allocators *GlobalAllocators = nullptr;
+
+} // namespace
+
+void post(const FunctionCallTrie &T, tid_t TId) {
+  static const bool UNUSED Once = [] {
+    SpinMutexLock Lock(&GlobalMutex);
+    GlobalAllocators = new (INTERNAL_ALLOC) FunctionCallTrie::Allocators();
+    *GlobalAllocators = FunctionCallTrie::InitAllocators();
+    return false;
+  }();
+  DCHECK_NE(GlobalAllocators, nullptr);
+
+  ThreadTrie *Item = nullptr;
+  {
+    SpinMutexLock Lock(&GlobalMutex);
+    if (GlobalAllocators == nullptr)
+      return;
+
+    Item = ThreadTries.PushBack();
+    Item->TId = TId;
+    Item->Trie = new (INTERNAL_ALLOC) FunctionCallTrie(*GlobalAllocators);
+    DCHECK_NE(Item->Trie, nullptr);
+  }
+  DCHECK_NE(Item, nullptr);
+
+  T.deepCopyInto(*Item->Trie);
+}
+
+using PathArray = Array<int32_t>;
+
+struct ProfileRecord {
+  using PathAllocator = typename PathArray::AllocatorType;
+
+  // The Path in this record is in reverse order.
+  PathArray *Path = nullptr;
+  const FunctionCallTrie::Node *Node = nullptr;
+
+  // Constructor for in-place construction.
+  ProfileRecord(PathAllocator &A, const FunctionCallTrie::Node *N)
+      : Path(new (INTERNAL_ALLOC) PathArray(A)), Node(N) {}
+};
+
+namespace {
+
+using ProfileRecordArray = Array<ProfileRecord>;
+
+// We go through a FunctionCallTrie and traverse from the root, in DFS fashion,
+// to generate the path(s) and output the data.
+void populateRecords(ProfileRecordArray &PRs, ProfileRecord::PathAllocator &PA,
+                     const FunctionCallTrie &Trie) {
+  for (const auto R : Trie.getRoots()) {
+    using StackArray = Array<const FunctionCallTrie::Node *>;
+    using StackAllocator = typename StackArray::AllocatorType;
+    StackAllocator StackAlloc(
+        profilerFlags()->xray_profiling_stack_allocator_max, 0);
+    StackArray DFSStack(StackAlloc);
+    DFSStack.Append(R);
+    while (!DFSStack.empty()) {
+      auto Node = DFSStack.back();
+      DFSStack.trim(1);
+      auto Record = PRs.AppendEmplace(PA, Node);
+      DCHECK_NE(Record, nullptr);
+
+      // Traverse the Node's parents and as we're doing so, get the FIds in
+      // the order they appear.
+      for (auto N = Node; N != nullptr; N = N->Parent)
+        Record->Path->Append(N->FId);
+      DCHECK(!Record->Path->empty());
+
+      for (const auto C : Node->Callees)
+        DFSStack.Append(C.NodePtr);
+    }
+  }
+}
+
+void serializeRecords(ProfileBuffer *Buffer, const BlockHeader &Header,
+                      const ProfileRecordArray &ProfileRecords) {
+  auto NextPtr = static_cast<char *>(
+                     internal_memcpy(Buffer->Data, &Header, sizeof(Header))) +
+                 sizeof(Header);
+  for (const auto &Record : ProfileRecords) {
+    // List of IDs follow:
+    for (const auto FId : *Record.Path)
+      NextPtr =
+          static_cast<char *>(internal_memcpy(NextPtr, &FId, sizeof(FId))) +
+          sizeof(FId);
+
+    // Add the sentinel here.
+    constexpr int32_t SentinelFId = 0;
+    NextPtr = static_cast<char *>(
+                  internal_memset(NextPtr, SentinelFId, sizeof(SentinelFId))) +
+              sizeof(SentinelFId);
+
+    // Add the node data here.
+    NextPtr =
+        static_cast<char *>(internal_memcpy(NextPtr, &Record.Node->CallCount,
+                                            sizeof(Record.Node->CallCount))) +
+        sizeof(Record.Node->CallCount);
+    NextPtr = static_cast<char *>(
+                  internal_memcpy(NextPtr, &Record.Node->CumulativeLocalTime,
+                                  sizeof(Record.Node->CumulativeLocalTime))) +
+              sizeof(Record.Node->CumulativeLocalTime);
+
+    // Add an end of record sentinel here.
+    constexpr uint64_t EndOfRecord = 0x0;
+    NextPtr = static_cast<char *>(
+                  internal_memset(NextPtr, EndOfRecord, sizeof(EndOfRecord))) +
+              sizeof(EndOfRecord);
+  }
+
+  DCHECK_EQ(NextPtr - static_cast<char *>(Buffer->Data), Buffer->Size);
+}
+
+} // namespace
+
+void serialize() {
+  SpinMutexLock Lock(&GlobalMutex);
+
+  // Clear out the global ProfileBuffers.
+  for (uptr I = 0; I < ProfileBuffers.Size(); ++I)
+    InternalFree(ProfileBuffers[I].Data);
+  ProfileBuffers.Reset();
+
+  if (ThreadTries.Size() == 0)
+    return;
+
+  // Then repopulate the global ProfileBuffers.
+  for (u32 I = 0; I < ThreadTries.Size(); ++I) {
+    using ProfileRecordAllocator = typename ProfileRecordArray::AllocatorType;
+    ProfileRecordAllocator PRAlloc(
+        profilerFlags()->xray_profiling_global_allocator_max, 0);
+    ProfileRecord::PathAllocator PathAlloc(
+        profilerFlags()->xray_profiling_global_allocator_max, 0);
+    ProfileRecordArray ProfileRecords(PRAlloc);
+
+    // First, we want to compute the amount of space we're going to need. We'll
+    // use a local allocator and an __xray::Array<...> to store the intermediary
+    // data, then compute the size as we're going along. Then we'll allocate the
+    // contiguous space to contain the thread buffer data.
+    const auto &Trie = *ThreadTries[I].Trie;
+    if (Trie.getRoots().empty())
+      continue;
+    populateRecords(ProfileRecords, PathAlloc, Trie);
+    DCHECK(!Trie.getRoots().empty());
+    DCHECK(!ProfileRecords.empty());
+
+    // Go through each record, to compute the sizes.
+    //
+    // header size = block size (4 bytes)
+    //   + block number (4 bytes)
+    //   + thread id (8 bytes)
+    // record size = path ids (4 bytes * number of ids + sentinel 4 bytes)
+    //   + call count (8 bytes)
+    //   + local time (8 bytes)
+    //   + end of record (8 bytes)
+    u32 CumulativeSizes = 0;
+    for (const auto &Record : ProfileRecords)
+      CumulativeSizes += 28 + (4 * Record.Path->size());
+
+    BlockHeader Header{16 + CumulativeSizes, I, ThreadTries[I].TId};
+    auto Buffer = ProfileBuffers.PushBack();
+    Buffer->Size = sizeof(Header) + CumulativeSizes;
+    Buffer->Data = InternalAlloc(Buffer->Size, nullptr, 64);
+    DCHECK_NE(Buffer->Data, nullptr);
+    serializeRecords(Buffer, Header, ProfileRecords);
+
+    // Now clean up the ProfileRecords array, one at a time.
+    for (auto &Record : ProfileRecords) {
+      Record.Path->~PathArray();
+      InternalFree(Record.Path);
+    }
+  }
+}
+
+void reset() {
+  SpinMutexLock Lock(&GlobalMutex);
+  // Clear out the profile buffers that have been serialized.
+  for (uptr I = 0; I < ProfileBuffers.Size(); ++I)
+    InternalFree(ProfileBuffers[I].Data);
+  ProfileBuffers.Reset();
+
+  // Clear out the function call tries per thread.
+  for (uptr I = 0; I < ThreadTries.Size(); ++I) {
+    auto &T = ThreadTries[I];
+    T.Trie->~FunctionCallTrie();
+    InternalFree(T.Trie);
+  }
+  ThreadTries.Reset();
+
+  // Reset the global allocators.
+  if (GlobalAllocators != nullptr) {
+    GlobalAllocators->~Allocators();
+    InternalFree(GlobalAllocators);
+    GlobalAllocators = nullptr;
+  }
+  GlobalAllocators = new (INTERNAL_ALLOC) FunctionCallTrie::Allocators();
+  *GlobalAllocators = FunctionCallTrie::InitAllocators();
+}
+
+XRayBuffer nextBuffer(XRayBuffer B) {
+  // FIXME: Find a way to identify the buffers, somehow, from within this
+  // function.
+  SpinMutexLock Lock(&GlobalMutex);
+  if (B.Data == nullptr && ProfileBuffers.Size())
+    return {ProfileBuffers[0].Data, ProfileBuffers[0].Size};
+
+  BlockHeader Header;
+  internal_memcpy(&Header, B.Data, sizeof(BlockHeader));
+  auto NextBlock = Header.BlockNum + 1;
+  if (NextBlock < ProfileBuffers.Size())
+    return {ProfileBuffers[NextBlock].Data, ProfileBuffers[NextBlock].Size};
+  return {nullptr, 0};
+}
+
+} // namespace profileCollectorService
+} // namespace __xray

compiler-rt/lib/xray/xray_profiler.cc

+//===-- xray_profiling.cc --------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// This is the implementation of a profiling handler.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_atomic.h"
+#include "sanitizer_common/sanitizer_flags.h"
+#include "xray/xray_interface.h"
+#include "xray/xray_log_interface.h"
+
+#include "xray_flags.h"
+#include "xray_profile_collector.h"
+#include "xray_profiler_flags.h"
+#include "xray_tsc.h"
+#include "xray_utils.h"
+#include <memory>
+#include <pthread.h>
+
+namespace __xray {
+
+namespace {
+
+__sanitizer::atomic_sint32_t ProfilerLogFlushStatus = {
+    XRayLogFlushStatus::XRAY_LOG_NOT_FLUSHING};
+
+__sanitizer::atomic_sint32_t ProfilerLogStatus = {
+    XRayLogInitStatus::XRAY_LOG_UNINITIALIZED};
+
+__sanitizer::SpinMutex ProfilerOptionsMutex;
+
+struct alignas(64) ProfilingTLD {
+  FunctionCallTrie::Allocators *Allocators = nullptr;
+  FunctionCallTrie *FCT = nullptr;
+};
+
+static pthread_key_t ProfilingKey;
+
+ProfilingTLD &getThreadLocalData() XRAY_NEVER_INSTRUMENT {
+  thread_local ProfilingTLD TLD;
+  thread_local bool UNUSED Once = [] {
+    pthread_setspecific(ProfilingKey, &TLD);
+    return false;
+  }();
+
+  // We need to check whether the global flag to finalizing/finalized has been
+  // switched. If it is, then we ought to not actually initialise the data.
+  auto Status = __sanitizer::atomic_load(&ProfilerLogStatus,
+                                         __sanitizer::memory_order_acquire);
+  if (Status == XRayLogInitStatus::XRAY_LOG_FINALIZING ||
+      Status == XRayLogInitStatus::XRAY_LOG_FINALIZED)
+    return TLD;
+
+  // If we're live, then we re-initialize TLD if the pointers are not null.
+  if (UNLIKELY(TLD.Allocators == nullptr && TLD.FCT == nullptr)) {
+    TLD.Allocators = new (INTERNAL_ALLOC) FunctionCallTrie::Allocators();
+    *TLD.Allocators = FunctionCallTrie::InitAllocators();
+    TLD.FCT = new (INTERNAL_ALLOC) FunctionCallTrie(*TLD.Allocators);
+  }
+
+  return TLD;
+}
+
+} // namespace
+
+ProfilerFlags xray_profiler_flags_dont_use_directly; // use via profilerFlags().
+
+void registerProfilerFlags(FlagParser *P,
+                           ProfilerFlags *F) XRAY_NEVER_INSTRUMENT {
+#define XRAY_FLAG(Type, Name, DefaultValue, Description)                       \
+  RegisterFlag(P, #Name, Description, &F->Name);
+#include "xray_profiler_flags.inc"
+#undef XRAY_FLAG
+}
+
+const char *profilerCompilerDefinedFlags() XRAY_NEVER_INSTRUMENT {
+#ifdef XRAY_PROFILER_DEFAULT_OPTIONS
+  return SANITIZER_STRINGIFY(XRAY_PROFILER_DEFAULT_OPTIONS);
+#else
+  return "";
+#endif
+}
+
+void ProfilerFlags::setDefaults() XRAY_NEVER_INSTRUMENT {
+#define XRAY_FLAG(Type, Name, DefaultValue, Description) Name = DefaultValue;
+#include "xray_profiler_flags.inc"
+#undef XRAY_FLAG
+}
+
+__sanitizer::atomic_sint32_t ProfileFlushStatus = {
+    XRayLogFlushStatus::XRAY_LOG_NOT_FLUSHING};
+
+XRayLogFlushStatus profilingFlush() XRAY_NEVER_INSTRUMENT {
+  // When flushing, all we really do is reset the global state, and only when
+  // the log has already been finalized.
+  if (__sanitizer::atomic_load(&ProfilerLogStatus,
+                               __sanitizer::memory_order_acquire) !=
+      XRayLogInitStatus::XRAY_LOG_FINALIZED) {
+    if (__sanitizer::Verbosity())
+      Report("Not flushing profiles, profiler not been finalized.\n");
+    return XRayLogFlushStatus::XRAY_LOG_NOT_FLUSHING;
+  }
+
+  s32 Result = XRayLogFlushStatus::XRAY_LOG_NOT_FLUSHING;
+  if (!__sanitizer::atomic_compare_exchange_strong(
+          &ProfilerLogFlushStatus, &Result,
+          XRayLogFlushStatus::XRAY_LOG_FLUSHING,
+          __sanitizer::memory_order_release)) {
+    if (__sanitizer::Verbosity())
+      Report("Not flushing profiles, implementation still finalizing.\n");
+  }
+
+  profileCollectorService::reset();
+
+  __sanitizer::atomic_store(&ProfilerLogStatus,
+                            XRayLogFlushStatus::XRAY_LOG_FLUSHED,
+                            __sanitizer::memory_order_release);
+
+  return XRayLogFlushStatus::XRAY_LOG_FLUSHED;
+}
+
+namespace {
+
+thread_local volatile bool ReentranceGuard = false;
+
+void postCurrentThreadFCT(ProfilingTLD &TLD) {
+  if (TLD.Allocators == nullptr || TLD.FCT == nullptr)
+    return;
+
+  profileCollectorService::post(*TLD.FCT, GetTid());
+  TLD.FCT->~FunctionCallTrie();
+  TLD.Allocators->~Allocators();
+  InternalFree(TLD.FCT);
+  InternalFree(TLD.Allocators);
+  TLD.FCT = nullptr;
+  TLD.Allocators = nullptr;
+}
+
+} // namespace
+
+void profilingHandleArg0(int32_t FuncId,
+                         XRayEntryType Entry) XRAY_NEVER_INSTRUMENT {
+  unsigned char CPU;
+  auto TSC = readTSC(CPU);
+  if (ReentranceGuard)
+    return;
+  ReentranceGuard = true;
+
+  auto Status = __sanitizer::atomic_load(&ProfilerLogStatus,
+                                         __sanitizer::memory_order_acquire);
+  auto &TLD = getThreadLocalData();
+  if (UNLIKELY(Status == XRayLogInitStatus::XRAY_LOG_FINALIZED ||
+               Status == XRayLogInitStatus::XRAY_LOG_FINALIZING)) {
+    postCurrentThreadFCT(TLD);
+    ReentranceGuard = false;
+    return;
+  }
+
+  switch (Entry) {
+  case XRayEntryType::ENTRY:
+  case XRayEntryType::LOG_ARGS_ENTRY:
+    TLD.FCT->enterFunction(FuncId, TSC);
+    break;
+  case XRayEntryType::EXIT:
+  case XRayEntryType::TAIL:
+    TLD.FCT->exitFunction(FuncId, TSC);
+    break;
+  default:
+    // FIXME: Handle bugs.
+    break;
+  }
+
+  ReentranceGuard = false;
+}
+
+void profilingHandleArg1(int32_t FuncId, XRayEntryType Entry,
+                         uint64_t) XRAY_NEVER_INSTRUMENT {
+  return profilingHandleArg0(FuncId, Entry);
+}
+
+XRayLogInitStatus profilingFinalize() XRAY_NEVER_INSTRUMENT {
+  s32 CurrentStatus = XRayLogInitStatus::XRAY_LOG_INITIALIZED;
+  if (!__sanitizer::atomic_compare_exchange_strong(
+          &ProfilerLogStatus, &CurrentStatus,
+          XRayLogInitStatus::XRAY_LOG_FINALIZING,
+          __sanitizer::memory_order_release)) {
+    if (__sanitizer::Verbosity())
+      Report("Cannot finalize profile, the profiler is not initialized.\n");
+    return static_cast<XRayLogInitStatus>(CurrentStatus);
+  }
+
+  // Wait a grace period to allow threads to see that we're finalizing.
+  __sanitizer::SleepForMillis(profilerFlags()->xray_profiling_grace_period_ms);
+
+  // We also want to make sure that the current thread's data is cleaned up, if
+  // we have any.
+  auto &TLD = getThreadLocalData();
+  postCurrentThreadFCT(TLD);
+
+  // Then we force serialize the log data.
+  profileCollectorService::serialize();
+
+  __sanitizer::atomic_store(&ProfilerLogStatus,
+                            XRayLogInitStatus::XRAY_LOG_FINALIZED,
+                            __sanitizer::memory_order_release);
+  return XRayLogInitStatus::XRAY_LOG_FINALIZED;
+}
+
+XRayLogInitStatus
+profilingLoggingInit(size_t BufferSize, size_t BufferMax, void *Options,
+                     size_t OptionsSize) XRAY_NEVER_INSTRUMENT {
+  s32 CurrentStatus = XRayLogInitStatus::XRAY_LOG_UNINITIALIZED;
+  if (!__sanitizer::atomic_compare_exchange_strong(
+          &ProfilerLogStatus, &CurrentStatus,
+          XRayLogInitStatus::XRAY_LOG_INITIALIZING,
+          __sanitizer::memory_order_release)) {
+    if (__sanitizer::Verbosity())
+      Report(
+          "Cannot initialize already initialised profiling implementation.\n");
+    return static_cast<XRayLogInitStatus>(CurrentStatus);
+  }
+
+  // Here we use the sanitizer flag parsing mechanism. When PR36790 is fixed,
+  // migrate to using a different API for configuration.
+  {
+    SpinMutexLock Lock(&ProfilerOptionsMutex);
+    FlagParser ConfigParser;
+    auto *F = profilerFlags();
+    F->setDefaults();
+    registerProfilerFlags(&ConfigParser, F);
+    const char *ProfilerCompileFlags = profilerCompilerDefinedFlags();
+    ConfigParser.ParseString(ProfilerCompileFlags);
+    ConfigParser.ParseString(static_cast<const char *>(Options));
+    if (Verbosity())
+      ReportUnrecognizedFlags();
+  }
+
+  // We need to reset the profile data collection implementation now.
+  profileCollectorService::reset();
+
+  // We need to set up the at-thread-exit handler.
+  static bool UNUSED Once = [] {
+    pthread_key_create(&ProfilingKey, +[](void *) {
+      // This is the thread-exit handler.
+      auto &TLD = getThreadLocalData();
+      if (TLD.Allocators == nullptr && TLD.FCT == nullptr)
+        return;
+
+      postCurrentThreadFCT(TLD);
+    });
+    return false;
+  }();
+
+  __xray_log_set_buffer_iterator(profileCollectorService::nextBuffer);
+  __xray_set_handler(profilingHandleArg0);
+  __xray_set_handler_arg1(profilingHandleArg1);
+
+  __sanitizer::atomic_store(&ProfilerLogStatus,
+                            XRayLogInitStatus::XRAY_LOG_INITIALIZED,
+                            __sanitizer::memory_order_release);
+  if (__sanitizer::Verbosity())
+    Report("XRay Profiling init successful.\n");
+
+  return XRayLogInitStatus::XRAY_LOG_INITIALIZED;
+}
+
+bool profilingDynamicInitializer() XRAY_NEVER_INSTRUMENT {
+  // Set up the flag defaults from the static defaults and the compiler-provided
+  // defaults.
+  {
+    SpinMutexLock Lock(&ProfilerOptionsMutex);
+    auto *F = profilerFlags();
+    F->setDefaults();
+    FlagParser ProfilingParser;
+    registerProfilerFlags(&ProfilingParser, F);
+    const char *ProfilerCompileFlags = profilerCompilerDefinedFlags();
+    ProfilingParser.ParseString(ProfilerCompileFlags);
+  }
+
+  XRayLogImpl Impl{
+      profilingLoggingInit,
+      profilingFinalize,
+      profilingHandleArg0,
+      profilingFlush,
+  };
+  auto RegistrationResult = __xray_log_register_mode("xray-profiling", Impl);
+  if (RegistrationResult != XRayLogRegisterStatus::XRAY_REGISTRATION_OK &&
+      __sanitizer::Verbosity())
+    Report(
+        "Cannot register XRay Profiling mode to 'xray-profiling'; error = %d\n",
+        RegistrationResult);
+  if (!__sanitizer::internal_strcmp(flags()->xray_mode, "xray-profiling"))
+    __xray_set_log_impl(Impl);
+  return true;
+}
+
+} // namespace __xray
+
+static auto UNUSED Unused = __xray::profilingDynamicInitializer();

compiler-rt/lib/xray/xray_profiler_flags.h

+//===-- xray_profiler_flags.h ----------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// XRay profiler runtime flags.
+//===----------------------------------------------------------------------===//
+
+#ifndef XRAY_PROFILER_FLAGS_H
+#define XRAY_PROFILER_FLAGS_H
+
+#include "sanitizer_common/sanitizer_flag_parser.h"
+#include "sanitizer_common/sanitizer_internal_defs.h"
+
+namespace __xray {
+
+struct ProfilerFlags {
+#define XRAY_FLAG(Type, Name, DefaultValue, Description) Type Name;
+#include "xray_profiler_flags.inc"
+#undef XRAY_FLAG
+
+  void setDefaults();
+};
+
+extern ProfilerFlags xray_profiler_flags_dont_use_directly;
+inline ProfilerFlags *profilerFlags() {
+  return &xray_profiler_flags_dont_use_directly;
+}
+
+} // namespace __xray
+
+#endif // XRAY_PROFILER_FLAGS_H

compiler-rt/lib/xray/xray_profiler_flags.inc

+//===-- xray_flags.inc ------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// XRay profiling runtime flags.
+//
+//===----------------------------------------------------------------------===//
+#ifndef XRAY_FLAG
+#error "Define XRAY_FLAG prior to including this file!"
+#endif
+
+XRAY_FLAG(uptr, xray_profiling_per_thread_allocator_max, 2 << 20,
+          "Maximum size of any single per-thread allocator.")
+XRAY_FLAG(uptr, xray_profiling_global_allocator_max, 2 << 24,
+          "Maximum size of the global allocator for profile storage.")
+XRAY_FLAG(uptr, xray_profiling_stack_allocator_max, 2 << 24,
+          "Maximum size of the traversal stack allocator.")
+XRAY_FLAG(int, xray_profiling_grace_period_ms, 100,
+          "Profile collection will wait this much time in milliseconds before "
+          "resetting the global state. This gives a chance to threads to "
+          "notice that the profiler has been finalized and clean up.")

compiler-rt/lib/xray/xray_segmented_array.h

+//===-- xray_segmented_array.h ---------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// Defines the implementation of a segmented array, with fixed-size chunks
+// backing the segments.
+//
+//===----------------------------------------------------------------------===//
+#ifndef XRAY_SEGMENTED_ARRAY_H
+#define XRAY_SEGMENTED_ARRAY_H
+
+#include "xray_allocator.h"
+#include <type_traits>
+#include <utility>
+
+namespace __xray {
+
+/// The Array type provides an interface similar to std::vector<...> but does
+/// not shrink in size. Once constructed, elements can be appended but cannot be
+/// removed. The implementation is heavily dependent on the contract provided by
+/// the Allocator type, in that all memory will be released when the Allocator
+/// is destroyed. When an Array is destroyed, it will destroy elements in the
+/// backing store but will not free the memory. The parameter N defines how many
+/// elements of T there should be in a single block. By default we compute this
+/// number from packing as many T's as possible in a single cache line.
+template <class T, size_t N = (kCacheLineSize / sizeof(T)) +
+                              (kCacheLineSize % sizeof(T) ? 1 : 0)>
+struct Array {
+  static constexpr size_t AllocatorChunkSize = sizeof(T) * N;
+  using AllocatorType = Allocator<AllocatorChunkSize>;
+  static_assert(std::is_trivially_destructible<T>::value,
+                "T must be trivially destructible.");
+
+private:
+  struct Chunk {
+    typename AllocatorType::Block Block;
+    static constexpr size_t Size = N;
+    Chunk *Prev = nullptr;
+    Chunk *Next = nullptr;
+  };
+
+  static Chunk SentinelChunk;
+
+  AllocatorType *Allocator;
+  Chunk *Head = &SentinelChunk;
+  Chunk *Tail = &SentinelChunk;
+  size_t Size = 0;
+
+  Chunk *NewChunk() {
+    auto Block = Allocator->Allocate();
+    if (Block.Data == nullptr)
+      return nullptr;
+    // TODO: Maybe use a separate managed allocator for Chunk instances?
+    auto C = reinterpret_cast<Chunk *>(InternalAlloc(sizeof(Chunk)));
+    if (C == nullptr)
+      return nullptr;
+    C->Block = Block;
+    return C;
+  }
+
+  static AllocatorType &GetGlobalAllocator() {
+    static AllocatorType *const GlobalAllocator =
+        new (INTERNAL_ALLOC) AllocatorType(2 << 10, 0);
+    return *GlobalAllocator;
+  }
+
+  Chunk *InitHeadAndTail() {
+    DCHECK_EQ(Head, &SentinelChunk);
+    DCHECK_EQ(Tail, &SentinelChunk);
+    auto Chunk = NewChunk();
+    if (Chunk == nullptr)
+      return nullptr;
+    Chunk->Prev = &SentinelChunk;
+    Chunk->Next = &SentinelChunk;
+    Head = Chunk;
+    Tail = Chunk;
+    return Chunk;
+  }
+
+  Chunk *AppendNewChunk() {
+    auto Chunk = NewChunk();
+    if (Chunk == nullptr)
+      return nullptr;
+    Tail->Next = Chunk;
+    Chunk->Prev = Tail;
+    Chunk->Next = &SentinelChunk;
+    Tail = Chunk;
+    return Chunk;
+  }
+
+  class Iterator {
+    Chunk *C = nullptr;
+    size_t Offset = 0;
+
+  public:
+    Iterator(Chunk *IC, size_t O) : C(IC), Offset(O) {}
+
+    Iterator &operator++() {
+      DCHECK_NE(C, nullptr);
+      if (++Offset % N)
+        return *this;
+
+      // At this point, we know that Offset % N == 0, so we must advance the
+      // chunk pointer.
+      DCHECK_EQ(Offset % N, 0);
+      C = C->Next;
+      return *this;
+    }
+
+    Iterator &operator--() {
+      DCHECK_NE(C, nullptr);
+      if (--Offset % N) {
+        return *this;
+      }
+
+      // At this point, we know that Offset % N == 0, so we must retreat the
+      // chunk pointer.
+      DCHECK_EQ(Offset % N, 0);
+      C = C->Prev;
+      return *this;
+    }
+
+    Iterator operator++(int) {
+      Iterator Copy(*this);
+      if (++Offset % N == 0)
+        C = C->Next;
+      DCHECK_NE(Copy.Offset, this->Offset);
+      return Copy;
+    }
+
+    Iterator operator--(int) {
+      Iterator Copy(*this);
+      if (--Offset % N == 0)
+        C = C->Prev;
+      DCHECK_NE(Copy.Offset, this->Offset);
+      return Copy;
+    }
+
+    friend bool operator==(const Iterator &L, const Iterator &R) {
+      return L.C == R.C && L.Offset == R.Offset;
+    }
+
+    friend bool operator!=(const Iterator &L, const Iterator &R) {
+      return !(L == R);
+    }
+
+    const T &operator*() const {
+      DCHECK_NE(C, &SentinelChunk);
+      return reinterpret_cast<const T *>(C->Block.Data)[Offset % N];
+    }
+
+    T &operator*() {
+      DCHECK_NE(C, &SentinelChunk);
+      return reinterpret_cast<T *>(C->Block.Data)[Offset % N];
+    }
+  };
+
+public:
+  explicit Array(AllocatorType &A) : Allocator(&A) {}
+  Array() : Array(GetGlobalAllocator()) {}
+
+  Array(const Array &) = delete;
+  Array(Array &&O) NOEXCEPT : Allocator(O.Allocator),
+                              Head(O.Head),
+                              Tail(O.Tail),
+                              Size(O.Size) {
+    O.Head = &SentinelChunk;
+    O.Tail = &SentinelChunk;
+    O.Size = 0;
+  }
+
+  bool empty() const { return Size == 0; }
+
+  AllocatorType &allocator() const {
+    DCHECK_NE(Allocator, nullptr);
+    return *Allocator;
+  }
+
+  size_t size() const { return Size; }
+
+  T *Append(const T &E) {
+    if (UNLIKELY(Head == &SentinelChunk))
+      if (InitHeadAndTail() == nullptr)
+        return nullptr;
+
+    auto Offset = Size % N;
+    if (UNLIKELY(Size != 0 && Offset == 0))
+      if (AppendNewChunk() == nullptr)
+        return nullptr;
+
+    auto Position = reinterpret_cast<T *>(Tail->Block.Data) + Offset;
+    *Position = E;
+    ++Size;
+    return Position;
+  }
+
+  template <class... Args> T *AppendEmplace(Args &&... args) {
+    if (UNLIKELY(Head == &SentinelChunk))
+      if (InitHeadAndTail() == nullptr)
+        return nullptr;
+
+    auto Offset = Size % N;
+    if (UNLIKELY(Size != 0 && Offset == 0))
+      if (AppendNewChunk() == nullptr)
+        return nullptr;
+
+    auto Position = reinterpret_cast<T *>(Tail->Block.Data) + Offset;
+    // In-place construct at Position.
+    new (Position) T(std::forward<Args>(args)...);
+    ++Size;
+    return Position;
+  }
+
+  T &operator[](size_t Offset) const {
+    DCHECK_LE(Offset, Size);
+    // We need to traverse the array enough times to find the element at Offset.
+    auto C = Head;
+    while (Offset >= N) {
+      C = C->Next;
+      Offset -= N;
+      DCHECK_NE(C, &SentinelChunk);
+    }
+    auto Position = reinterpret_cast<T *>(C->Block.Data) + Offset;
+    return *Position;
+  }
+
+  T &front() const {
+    DCHECK_NE(Head, &SentinelChunk);
+    DCHECK_NE(Size, 0u);
+    return *reinterpret_cast<T *>(Head->Block.Data);
+  }
+
+  T &back() const {
+    DCHECK_NE(Tail, &SentinelChunk);
+    auto Offset = (Size - 1) % N;
+    return *(reinterpret_cast<T *>(Tail->Block.Data) + Offset);
+  }
+
+  template <class Predicate> T *find_element(Predicate P) const {
+    if (empty())
+      return nullptr;
+
+    auto C = Head;
+    auto E = Size;
+    while (E != 0) {
+      DCHECK(C != &SentinelChunk);
+      auto LE = N < E ? N : E;
+      auto end = reinterpret_cast<T *>(C->Block.Data) + LE;
+      for (auto It = reinterpret_cast<T *>(C->Block.Data); It != end; ++It)
+        if (P(*It))
+          return It;
+      C = C->Next;
+      E -= LE;
+    }
+    return nullptr;
+  }
+
+  /// Remove N Elements from the end.
+  void trim(size_t Elements) {
+    // TODO: Figure out whether we need to actually destroy the objects that are
+    // going to be trimmed -- determine whether assuming that trivially
+    // destructible objects are OK to discard, from the XRay implementation.
+    DCHECK_LE(Elements, Size);
+    Size -= Elements;
+  }
+
+  // Provide iterators.
+  Iterator begin() const { return Iterator(Head, 0); }
+  Iterator end() const { return Iterator(Tail, Size); }
+  Iterator cbegin() const { return Iterator(Head, 0); }
+  Iterator cend() const { return Iterator(Tail, Size); }
+};
+
+template <class T, size_t N>
+typename Array<T, N>::Chunk Array<T, N>::SentinelChunk;
+
+} // namespace __xray
+
+#endif // XRAY_SEGMENTED_ARRAY_H

compiler-rt/test/xray/TestCases/Posix/profiling-multi-threaded.cc

+// Check that we can get a profile from a single-threaded application, on
+// demand through the XRay logging implementation API.
+//
+// FIXME: Make -fxray-modes=xray-profiling part of the default?
+// RUN: %clangxx_xray -std=c++11 %s -o %t -fxray-modes=xray-profiler
+// RUN: %run %t
+//
+// UNSUPPORTED: target-is-mips64,target-is-mips64el
+
+#include "xray/xray_interface.h"
+#include "xray/xray_log_interface.h"
+#include <cassert>
+#include <cstdio>
+#include <string>
+#include <thread>
+
+#define XRAY_ALWAYS_INSTRUMENT [[clang::xray_always_instrument]]
+#define XRAY_NEVER_INSTRUMENT [[clang::xray_never_instrument]]
+
+XRAY_ALWAYS_INSTRUMENT void f2() { return; }
+XRAY_ALWAYS_INSTRUMENT void f1() { f2(); }
+XRAY_ALWAYS_INSTRUMENT void f0() { f1(); }
+
+using namespace std;
+
+volatile int buffer_counter = 0;
+
+XRAY_NEVER_INSTRUMENT void process_buffer(const char *, XRayBuffer) {
+  // FIXME: Actually assert the contents of the buffer.
+  ++buffer_counter;
+}
+
+XRAY_ALWAYS_INSTRUMENT int main(int, char **) {
+  assert(__xray_log_select_mode("xray-profiling") ==
+         XRayLogRegisterStatus::XRAY_REGISTRATION_OK);
+  assert(__xray_log_get_current_mode() != nullptr);
+  std::string current_mode = __xray_log_get_current_mode();
+  assert(current_mode == "xray-profiling");
+  assert(__xray_patch() == XRayPatchingStatus::SUCCESS);
+  assert(__xray_log_init(0, 0, nullptr, 0) ==
+         XRayLogInitStatus::XRAY_LOG_INITIALIZED);
+  std::thread t0([] { f0(); });
+  std::thread t1([] { f0(); });
+  f0();
+  t0.join();
+  t1.join();
+  assert(__xray_log_finalize() == XRayLogInitStatus::XRAY_LOG_FINALIZED);
+  assert(__xray_log_process_buffers(process_buffer) ==
+         XRayLogFlushStatus::XRAY_LOG_FLUSHED);
+  // We're running three threds, so we expect three buffers.
+  assert(buffer_counter == 3);
+  assert(__xray_log_flushLog() == XRayLogFlushStatus::XRAY_LOG_FLUSHED);
+}

compiler-rt/test/xray/TestCases/Posix/profiling-single-threaded.cc

+// Check that we can get a profile from a single-threaded application, on
+// demand through the XRay logging implementation API.
+//
+// FIXME: Make -fxray-modes=xray-profiling part of the default?
+// RUN: %clangxx_xray -std=c++11 %s -o %t -fxray-modes=xray-profiler
+// RUN: %run %t
+//
+// UNSUPPORTED: target-is-mips64,target-is-mips64el
+
+#include "xray/xray_interface.h"
+#include "xray/xray_log_interface.h"
+#include <cassert>
+#include <cstdio>
+#include <string>
+
+#define ALWAYS_INSTRUMENT [[clang::xray_always_instrument]]
+#define NEVER_INSTRUMENT [[clang::xray_never_instrument]]
+
+ALWAYS_INSTRUMENT void f2() { return; }
+ALWAYS_INSTRUMENT void f1() { f2(); }
+ALWAYS_INSTRUMENT void f0() { f1(); }
+
+using namespace std;
+
+volatile int buffer_counter = 0;
+
+NEVER_INSTRUMENT void process_buffer(const char *, XRayBuffer) {
+  // FIXME: Actually assert the contents of the buffer.
+  ++buffer_counter;
+}
+
+ALWAYS_INSTRUMENT int main(int, char **) {
+  assert(__xray_log_select_mode("xray-profiling") ==
+         XRayLogRegisterStatus::XRAY_REGISTRATION_OK);
+  assert(__xray_log_get_current_mode() != nullptr);
+  std::string current_mode = __xray_log_get_current_mode();
+  assert(current_mode == "xray-profiling");
+  assert(__xray_patch() == XRayPatchingStatus::SUCCESS);
+  assert(__xray_log_init(0, 0, nullptr, 0) ==
+         XRayLogInitStatus::XRAY_LOG_INITIALIZED);
+  f0();
+  assert(__xray_log_finalize() == XRayLogInitStatus::XRAY_LOG_FINALIZED);
+  f0();
+  assert(__xray_log_process_buffers(process_buffer) ==
+         XRayLogFlushStatus::XRAY_LOG_FLUSHED);
+  assert(buffer_counter == 1);
+  assert(__xray_log_flushLog() == XRayLogFlushStatus::XRAY_LOG_FLUSHED);
+}