vendor/compiler-rt/compiler-rt-trunk-r338150

7 files changed, 728 insertions, 12 deletions

diff --git a/lib/xray/tests/unit/CMakeLists.txt b/lib/xray/tests/unit/CMakeLists.txt
index 62d01f239581..b42eb50d0790 100644
--- a/lib/xray/tests/unit/CMakeLists.txt
+++ b/lib/xray/tests/unit/CMakeLists.txt
@@ -2,3 +2,11 @@ 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)
diff --git a/lib/xray/tests/unit/allocator_test.cc b/lib/xray/tests/unit/allocator_test.cc
new file mode 100644
index 000000000000..be404160e417
--- /dev/null
+++ b/lib/xray/tests/unit/allocator_test.cc
@@ -0,0 +1,42 @@
+//===-- 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); }
+
+TEST(AllocatorTest, Allocate) {
+  Allocator<sizeof(TestData)> A(2 << 11);
+  auto B = A.Allocate();
+  ASSERT_NE(B.Data, nullptr);
+}
+
+TEST(AllocatorTest, OverAllocate) {
+  Allocator<sizeof(TestData)> A(sizeof(TestData));
+  auto B1 = A.Allocate();
+  (void)B1;
+  auto B2 = A.Allocate();
+  ASSERT_EQ(B2.Data, nullptr);
+}
+
+} // namespace
+} // namespace __xray
diff --git a/lib/xray/tests/unit/buffer_queue_test.cc b/lib/xray/tests/unit/buffer_queue_test.cc
index 1ec7469ce187..c0d4ccb268d6 100644
--- a/lib/xray/tests/unit/buffer_queue_test.cc
+++ b/lib/xray/tests/unit/buffer_queue_test.cc
@@ -32,9 +32,9 @@ TEST(BufferQueueTest, GetAndRelease) {
   ASSERT_TRUE(Success);
   BufferQueue::Buffer Buf;
   ASSERT_EQ(Buffers.getBuffer(Buf), BufferQueue::ErrorCode::Ok);
-  ASSERT_NE(nullptr, Buf.Buffer);
+  ASSERT_NE(nullptr, Buf.Data);
   ASSERT_EQ(Buffers.releaseBuffer(Buf), BufferQueue::ErrorCode::Ok);
-  ASSERT_EQ(nullptr, Buf.Buffer);
+  ASSERT_EQ(nullptr, Buf.Data);
 }
 
 TEST(BufferQueueTest, GetUntilFailed) {
@@ -53,7 +53,7 @@ TEST(BufferQueueTest, ReleaseUnknown) {
   BufferQueue Buffers(kSize, 1, Success);
   ASSERT_TRUE(Success);
   BufferQueue::Buffer Buf;
-  Buf.Buffer = reinterpret_cast<void *>(0xdeadbeef);
+  Buf.Data = reinterpret_cast<void *>(0xdeadbeef);
   Buf.Size = kSize;
   EXPECT_EQ(BufferQueue::ErrorCode::UnrecognizedBuffer,
             Buffers.releaseBuffer(Buf));
@@ -65,7 +65,7 @@ TEST(BufferQueueTest, ErrorsWhenFinalising) {
   ASSERT_TRUE(Success);
   BufferQueue::Buffer Buf;
   ASSERT_EQ(Buffers.getBuffer(Buf), BufferQueue::ErrorCode::Ok);
-  ASSERT_NE(nullptr, Buf.Buffer);
+  ASSERT_NE(nullptr, Buf.Data);
   ASSERT_EQ(Buffers.finalize(), BufferQueue::ErrorCode::Ok);
   BufferQueue::Buffer OtherBuf;
   ASSERT_EQ(BufferQueue::ErrorCode::QueueFinalizing,
diff --git a/lib/xray/tests/unit/fdr_logging_test.cc b/lib/xray/tests/unit/fdr_logging_test.cc
index 76738ea4dff3..b6961efbc351 100644
--- a/lib/xray/tests/unit/fdr_logging_test.cc
+++ b/lib/xray/tests/unit/fdr_logging_test.cc
@@ -10,6 +10,7 @@
 // This file is a part of XRay, a function call tracing system.
 //
 //===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_common.h"
 #include "xray_fdr_logging.h"
 #include "gtest/gtest.h"
 
@@ -86,7 +87,7 @@ TEST(FDRLoggingTest, Simple) {
 
   XRayFileHeader H;
   memcpy(&H, Contents, sizeof(XRayFileHeader));
-  ASSERT_EQ(H.Version, 2);
+  ASSERT_EQ(H.Version, 3);
   ASSERT_EQ(H.Type, FileTypes::FDR_LOG);
 
   // We require one buffer at least to have the "extents" metadata record,
@@ -131,7 +132,7 @@ TEST(FDRLoggingTest, Multiple) {
 
   XRayFileHeader H;
   memcpy(&H, Contents, sizeof(XRayFileHeader));
-  ASSERT_EQ(H.Version, 2);
+  ASSERT_EQ(H.Version, 3);
   ASSERT_EQ(H.Type, FileTypes::FDR_LOG);
 
   MetadataRecord MDR0, MDR1;
@@ -154,12 +155,12 @@ TEST(FDRLoggingTest, MultiThreadedCycling) {
   // Now we want to create one thread, do some logging, then create another one,
   // in succession and making sure that we're able to get thread records from
   // the latest thread (effectively being able to recycle buffers).
-  std::array<pid_t, 2> Threads;
+  std::array<tid_t, 2> Threads;
   for (uint64_t I = 0; I < 2; ++I) {
     std::thread t{[I, &Threads] {
       fdrLoggingHandleArg0(I + 1, XRayEntryType::ENTRY);
       fdrLoggingHandleArg0(I + 1, XRayEntryType::EXIT);
-      Threads[I] = syscall(SYS_gettid);
+      Threads[I] = GetTid();
     }};
     t.join();
   }
@@ -182,7 +183,7 @@ TEST(FDRLoggingTest, MultiThreadedCycling) {
 
   XRayFileHeader H;
   memcpy(&H, Contents, sizeof(XRayFileHeader));
-  ASSERT_EQ(H.Version, 2);
+  ASSERT_EQ(H.Version, 3);
   ASSERT_EQ(H.Type, FileTypes::FDR_LOG);
 
   MetadataRecord MDR0, MDR1;
@@ -192,9 +193,9 @@ TEST(FDRLoggingTest, MultiThreadedCycling) {
   ASSERT_EQ(MDR0.RecordKind,
             uint8_t(MetadataRecord::RecordKinds::BufferExtents));
   ASSERT_EQ(MDR1.RecordKind, uint8_t(MetadataRecord::RecordKinds::NewBuffer));
-  pid_t Latest = 0;
-  memcpy(&Latest, MDR1.Data, sizeof(pid_t));
-  ASSERT_EQ(Latest, Threads[1]);
+  int32_t Latest = 0;
+  memcpy(&Latest, MDR1.Data, sizeof(int32_t));
+  ASSERT_EQ(Latest, static_cast<int32_t>(Threads[1]));
 }
 
 } // namespace
diff --git a/lib/xray/tests/unit/function_call_trie_test.cc b/lib/xray/tests/unit/function_call_trie_test.cc
new file mode 100644
index 000000000000..049ecfb07e01
--- /dev/null
+++ b/lib/xray/tests/unit/function_call_trie_test.cc
@@ -0,0 +1,286 @@
+//===-- 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 "gtest/gtest.h"
+
+#include "xray_function_call_trie.h"
+
+namespace __xray {
+
+namespace {
+
+TEST(FunctionCallTrieTest, ConstructWithTLSAllocators) {
+  profilingFlags()->setDefaults();
+  FunctionCallTrie::Allocators Allocators = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(Allocators);
+}
+
+TEST(FunctionCallTrieTest, EnterAndExitFunction) {
+  profilingFlags()->setDefaults();
+  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) {
+  profilingFlags()->setDefaults();
+  auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+  Trie.exitFunction(1, 1);
+  const auto &R = Trie.getRoots();
+
+  ASSERT_TRUE(R.empty());
+}
+
+TEST(FunctionCallTrieTest, NoMatchingEntersForExit) {
+  profilingFlags()->setDefaults();
+  auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+  Trie.enterFunction(2, 1);
+  Trie.enterFunction(3, 3);
+  Trie.exitFunction(1, 5);
+  const auto &R = Trie.getRoots();
+
+  ASSERT_FALSE(R.empty());
+  EXPECT_EQ(R.size(), size_t{1});
+}
+
+TEST(FunctionCallTrieTest, MissingFunctionExit) {
+  profilingFlags()->setDefaults();
+  auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+  Trie.enterFunction(1, 1);
+  const auto &R = Trie.getRoots();
+
+  ASSERT_FALSE(R.empty());
+  EXPECT_EQ(R.size(), size_t{1});
+}
+
+TEST(FunctionCallTrieTest, MultipleRoots) {
+  profilingFlags()->setDefaults();
+  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);
+
+  // Make sure the roots have different IDs.
+  const auto R0 = R[0];
+  const auto R1 = R[1];
+  ASSERT_NE(R0->FId, R1->FId);
+
+  // Inspect the roots that they have the right data.
+  ASSERT_NE(R0, nullptr);
+  EXPECT_EQ(R0->CallCount, 1u);
+  EXPECT_EQ(R0->CumulativeLocalTime, 1u);
+
+  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) {
+  profilingFlags()->setDefaults();
+  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);
+}
+
+TEST(FunctionCallTrieTest, DeepCallStack) {
+  // Simulate a relatively deep call stack (32 levels) and ensure that we can
+  // properly pop all the way up the stack.
+  profilingFlags()->setDefaults();
+  auto A = FunctionCallTrie::InitAllocators();
+  FunctionCallTrie Trie(A);
+  for (int i = 0; i < 32; ++i)
+    Trie.enterFunction(i + 1, i);
+  Trie.exitFunction(1, 33);
+
+  // Here, validate that we have a 32-level deep function call path from the
+  // root (1) down to the leaf (33).
+  const auto &R = Trie.getRoots();
+  ASSERT_EQ(R.size(), 1u);
+  auto F = R[0];
+  for (int i = 0; i < 32; ++i) {
+    EXPECT_EQ(F->FId, i + 1);
+    EXPECT_EQ(F->CallCount, 1);
+    if (F->Callees.empty() && i != 31)
+      FAIL() << "Empty callees for FId " << F->FId;
+    if (i != 31)
+      F = F->Callees[0].NodePtr;
+  }
+}
+
+// TODO: Test that we can handle cross-CPU migrations, where TSCs are not
+// guaranteed to be synchronised.
+TEST(FunctionCallTrieTest, DeepCopy) {
+  profilingFlags()->setDefaults();
+  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::NodeIdPair &R) { return R.FId == 2; })
+           ->NodePtr;
+  const auto &F1Copy =
+      *R0Copy.Callees
+           .find_element(
+               [](const FunctionCallTrie::NodeIdPair &R) { return R.FId == 2; })
+           ->NodePtr;
+  EXPECT_EQ(&R0Orig, F1Orig.Parent);
+  EXPECT_EQ(&R0Copy, F1Copy.Parent);
+}
+
+TEST(FunctionCallTrieTest, MergeInto) {
+  profilingFlags()->setDefaults();
+  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);
+
+  // We use a different allocator here to make sure that we're able to transfer
+  // data into a FunctionCallTrie which uses a different allocator. This
+  // reflects the inteded usage scenario for when we're collecting profiles that
+  // aggregate across threads.
+  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);
+  EXPECT_EQ(R0.Callees.size(), 1u);
+
+  const auto &F1 = *R0.Callees[0].NodePtr;
+  EXPECT_EQ(F1.FId, 2);
+  EXPECT_EQ(F1.CallCount, 2);
+  EXPECT_EQ(F1.CumulativeLocalTime, 6);
+  EXPECT_EQ(F1.Callees.size(), 1u);
+
+  const auto &F2 = *F1.Callees[0].NodePtr;
+  EXPECT_EQ(F2.FId, 3);
+  EXPECT_EQ(F2.CallCount, 2);
+  EXPECT_EQ(F2.CumulativeLocalTime, 2);
+  EXPECT_EQ(F2.Callees.size(), 0u);
+}
+
+} // namespace
+
+} // namespace __xray
diff --git a/lib/xray/tests/unit/profile_collector_test.cc b/lib/xray/tests/unit/profile_collector_test.cc
new file mode 100644
index 000000000000..b7dbe567312a
--- /dev/null
+++ b/lib/xray/tests/unit/profile_collector_test.cc
@@ -0,0 +1,179 @@
+//===-- profile_collector_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 "gtest/gtest.h"
+
+#include "xray_profile_collector.h"
+#include "xray_profiling_flags.h"
+#include <cstdint>
+#include <thread>
+#include <utility>
+#include <vector>
+
+namespace __xray {
+namespace {
+
+static constexpr auto kHeaderSize = 16u;
+
+void ValidateBlock(XRayBuffer B) {
+  profilingFlags()->setDefaults();
+  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] = {};
+  internal_memcpy(LocalBuffer, B.Data, kHeaderSize);
+  u32 BlockSize = 0;
+  u32 BlockNumber = 0;
+  u64 ThreadId = 0;
+  internal_memcpy(&BlockSize, LocalBuffer, sizeof(u32));
+  internal_memcpy(&BlockNumber, LocalBuffer + sizeof(u32), sizeof(u32));
+  internal_memcpy(&ThreadId, LocalBuffer + (2 * sizeof(u32)), sizeof(u64));
+  ASSERT_NE(BlockSize, 0u);
+  ASSERT_GE(BlockNumber, 0u);
+  ASSERT_NE(ThreadId, 0u);
+}
+
+std::tuple<u32, u32, u64> ParseBlockHeader(XRayBuffer B) {
+  char LocalBuffer[kHeaderSize] = {};
+  internal_memcpy(LocalBuffer, B.Data, kHeaderSize);
+  u32 BlockSize = 0;
+  u32 BlockNumber = 0;
+  u64 ThreadId = 0;
+  internal_memcpy(&BlockSize, LocalBuffer, sizeof(u32));
+  internal_memcpy(&BlockNumber, LocalBuffer + sizeof(u32), sizeof(u32));
+  internal_memcpy(&ThreadId, LocalBuffer + (2 * sizeof(u32)), sizeof(u64));
+  return std::make_tuple(BlockSize, BlockNumber, ThreadId);
+}
+
+struct Profile {
+  int64_t CallCount;
+  int64_t CumulativeLocalTime;
+  std::vector<int32_t> Path;
+};
+
+std::tuple<Profile, const char *> ParseProfile(const char *P) {
+  Profile Result;
+  // Read the path first, until we find a sentinel 0.
+  int32_t F;
+  do {
+    internal_memcpy(&F, P, sizeof(int32_t));
+    P += sizeof(int32_t);
+    Result.Path.push_back(F);
+  } while (F != 0);
+
+  // Then read the CallCount.
+  internal_memcpy(&Result.CallCount, P, sizeof(int64_t));
+  P += sizeof(int64_t);
+
+  // Then read the CumulativeLocalTime.
+  internal_memcpy(&Result.CumulativeLocalTime, P, sizeof(int64_t));
+  P += sizeof(int64_t);
+  return std::make_tuple(std::move(Result), P);
+}
+
+TEST(profileCollectorServiceTest, PostSerializeCollect) {
+  profilingFlags()->setDefaults();
+  // 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 T(Allocators);
+
+  // Then, we populate the trie with some data.
+  T.enterFunction(1, 1);
+  T.enterFunction(2, 2);
+  T.exitFunction(2, 3);
+  T.exitFunction(1, 4);
+
+  // Then we post the data to the global profile collector service.
+  profileCollectorService::post(T, 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);
+  u32 BlockSize;
+  u32 BlockNum;
+  u64 ThreadId;
+  std::tie(BlockSize, BlockNum, ThreadId) = ParseBlockHeader(B);
+
+  // We look at the serialized buffer to see whether the Trie we're expecting
+  // to see is there.
+  auto DStart = static_cast<const char *>(B.Data) + kHeaderSize;
+  std::vector<char> D(DStart, DStart + BlockSize);
+  B = profileCollectorService::nextBuffer(B);
+  ASSERT_EQ(B.Data, nullptr);
+  ASSERT_EQ(B.Size, 0u);
+
+  Profile Profile1, Profile2;
+  auto P = static_cast<const char *>(D.data());
+  std::tie(Profile1, P) = ParseProfile(P);
+  std::tie(Profile2, P) = ParseProfile(P);
+
+  ASSERT_NE(Profile1.Path.size(), Profile2.Path.size());
+  auto &P1 = Profile1.Path.size() < Profile2.Path.size() ? Profile2 : Profile1;
+  auto &P2 = Profile1.Path.size() < Profile2.Path.size() ? Profile1 : Profile2;
+  std::vector<int32_t> P1Expected = {2, 1, 0};
+  std::vector<int32_t> P2Expected = {1, 0};
+  ASSERT_EQ(P1.Path.size(), P1Expected.size());
+  ASSERT_EQ(P2.Path.size(), P2Expected.size());
+  ASSERT_EQ(P1.Path, P1Expected);
+  ASSERT_EQ(P2.Path, P2Expected);
+}
+
+// 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 T(Allocators);
+
+  T.enterFunction(1, 1);
+  T.enterFunction(2, 2);
+  T.exitFunction(2, 3);
+  T.exitFunction(1, 4);
+
+  profileCollectorService::post(T, GetTid());
+}
+
+TEST(profileCollectorServiceTest, PostSerializeCollectMultipleThread) {
+  profilingFlags()->setDefaults();
+  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
diff --git a/lib/xray/tests/unit/segmented_array_test.cc b/lib/xray/tests/unit/segmented_array_test.cc
new file mode 100644
index 000000000000..035674ccfaf5
--- /dev/null
+++ b/lib/xray/tests/unit/segmented_array_test.cc
@@ -0,0 +1,200 @@
+#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, ConstructWithAllocators) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4);
+  Array<TestData> Data(A);
+  (void)Data;
+}
+
+TEST(SegmentedArrayTest, ConstructAndPopulate) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4);
+  Array<TestData> data(A);
+  ASSERT_NE(data.Append(TestData{0, 0}), nullptr);
+  ASSERT_NE(data.Append(TestData{1, 1}), nullptr);
+  ASSERT_EQ(data.size(), 2u);
+}
+
+TEST(SegmentedArrayTest, ConstructPopulateAndLookup) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4);
+  Array<TestData> data(A);
+  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) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 24);
+  Array<TestData> data(A);
+  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) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4);
+  Array<TestData> data(A);
+  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
+  ASSERT_EQ(data[0].First, 1);
+  ASSERT_EQ(data[0].Second, 1);
+}
+
+TEST(SegmentedArrayTest, AppendAndTrim) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4);
+  Array<TestData> data(A);
+  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, IteratorAdvance) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4);
+  Array<TestData> data(A);
+  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);
+}
+
+TEST(SegmentedArrayTest, IteratorRetreat) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 4);
+  Array<TestData> data(A);
+  ASSERT_TRUE(data.empty());
+  ASSERT_EQ(data.begin(), data.end());
+  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);
+
+  auto I0 = data.end();
+  ASSERT_EQ(I0--, data.end());
+  ASSERT_NE(I0, data.end());
+  ASSERT_EQ(I0, data.begin());
+  ASSERT_EQ(I0->First, 1);
+  ASSERT_EQ(I0->Second, 1);
+}
+
+TEST(SegmentedArrayTest, IteratorTrimBehaviour) {
+  using AllocatorType = typename Array<TestData>::AllocatorType;
+  AllocatorType A(1 << 20);
+  Array<TestData> Data(A);
+  ASSERT_TRUE(Data.empty());
+  auto I0Begin = Data.begin(), I0End = Data.end();
+  // Add enough elements in Data to have more than one chunk.
+  constexpr auto Segment = Array<TestData>::SegmentSize;
+  constexpr auto SegmentX2 = Segment * 2;
+  for (auto i = SegmentX2; i > 0u; --i) {
+    Data.AppendEmplace(static_cast<s64>(i), static_cast<s64>(i));
+  }
+  ASSERT_EQ(Data.size(), SegmentX2);
+  {
+    auto &Back = Data.back();
+    ASSERT_EQ(Back.First, 1);
+    ASSERT_EQ(Back.Second, 1);
+  }
+
+  // Trim one chunk's elements worth.
+  Data.trim(Segment);
+  ASSERT_EQ(Data.size(), Segment);
+
+  // Check that we are still able to access 'back' properly.
+  {
+    auto &Back = Data.back();
+    ASSERT_EQ(Back.First, static_cast<s64>(Segment + 1));
+    ASSERT_EQ(Back.Second, static_cast<s64>(Segment + 1));
+  }
+
+  // Then trim until it's empty.
+  Data.trim(Segment);
+  ASSERT_TRUE(Data.empty());
+
+  // Here our iterators should be the same.
+  auto I1Begin = Data.begin(), I1End = Data.end();
+  EXPECT_EQ(I0Begin, I1Begin);
+  EXPECT_EQ(I0End, I1End);
+
+  // Then we ensure that adding elements back works just fine.
+  for (auto i = SegmentX2; i > 0u; --i) {
+    Data.AppendEmplace(static_cast<s64>(i), static_cast<s64>(i));
+  }
+  EXPECT_EQ(Data.size(), SegmentX2);
+}
+
+struct ShadowStackEntry {
+  uint64_t EntryTSC = 0;
+  uint64_t *NodePtr = nullptr;
+  ShadowStackEntry(uint64_t T, uint64_t *N) : EntryTSC(T), NodePtr(N) {}
+};
+
+TEST(SegmentedArrayTest, SimulateStackBehaviour) {
+  using AllocatorType = typename Array<ShadowStackEntry>::AllocatorType;
+  AllocatorType A(1 << 10);
+  Array<ShadowStackEntry> Data(A);
+  static uint64_t Dummy = 0;
+  constexpr uint64_t Max = 9;
+
+  for (uint64_t i = 0; i < Max; ++i) {
+    auto P = Data.Append({i, &Dummy});
+    ASSERT_NE(P, nullptr);
+    ASSERT_EQ(P->NodePtr, &Dummy);
+    auto &Back = Data.back();
+    ASSERT_EQ(Back.NodePtr, &Dummy);
+    ASSERT_EQ(Back.EntryTSC, i);
+  }
+
+  // Simulate a stack by checking the data from the end as we're trimming.
+  auto Counter = Max;
+  ASSERT_EQ(Data.size(), size_t(Max));
+  while (!Data.empty()) {
+    const auto &Top = Data.back();
+    uint64_t *TopNode = Top.NodePtr;
+    EXPECT_EQ(TopNode, &Dummy) << "Counter = " << Counter;
+    Data.trim(1);
+    --Counter;
+    ASSERT_EQ(Data.size(), size_t(Counter));
+  }
+}
+
+} // namespace
+} // namespace __xray