[XRay][compiler-rt] Segmented Array: Simplify and Optimise

[dberris]

Summary

This is a follow-on to D49217 which simplifies and optimises the
implementation of the segmented array. In this patch we co-locate the
book-keeping for segments in the __xray::Array<T> with the data it's
managing. We take the chance in this patch to actually rename Chunk to
Segment to better align with the high-level description of the
segmented array.

With measurements using benchmarks landed in D48879, we've identified
that calls to pthread_getspecific started dominating the cycles, which
led us to revert the change made in D49217 to use C++ thread_local
initialisation instead (it reduces the cost by a huge margin, since we
save one PLT-based call to pthread functions in the hot path). In
particular, this is in __xray::getThreadLocalData().

We also took the opportunity to remove the least-common-multiple based
calculation and instead pack as much data into segments of the array.
This greatly simplifies the API of the container which hides as much of
the implementation details as possible. For instance, we calculate the
number of elements we need for the each segment internally in the Array
instead of making it part of the type.

With the changes here, we're able to get a measurable improvement on the
performance of profiling mode on top of what D48879 already provides.

Depends on D48879.

[dberris]

For reference, here's one run of this:

Run on (48 X 3500 MHz CPU s)
2018-07-16 16:52:42
---------------------------------------------------------------------------------------------
Benchmark                                                      Time           CPU Iterations
---------------------------------------------------------------------------------------------
BM_XRayProfilingDeepCallStack/1/real_time/threads:1          210 ns        210 ns    3308489
BM_XRayProfilingDeepCallStack/1/real_time/threads:2          178 ns        356 ns    5002350
BM_XRayProfilingDeepCallStack/1/real_time/threads:4          145 ns        580 ns    6354504
BM_XRayProfilingDeepCallStack/1/real_time/threads:8          104 ns        830 ns    9115392
BM_XRayProfilingDeepCallStack/1/real_time/threads:16         185 ns       2953 ns   11361168
BM_XRayProfilingDeepCallStack/1/real_time/threads:32         131 ns       4174 ns    3908320
BM_XRayProfilingDeepCallStack/2/real_time/threads:1          300 ns        300 ns    2346595
BM_XRayProfilingDeepCallStack/2/real_time/threads:2          214 ns        428 ns    3257884
BM_XRayProfilingDeepCallStack/2/real_time/threads:4          158 ns        634 ns    4000000
BM_XRayProfilingDeepCallStack/2/real_time/threads:8          111 ns        887 ns    8249424
BM_XRayProfilingDeepCallStack/2/real_time/threads:16         106 ns       1693 ns    9066288
BM_XRayProfilingDeepCallStack/2/real_time/threads:32         152 ns       4849 ns    5675424
BM_XRayProfilingDeepCallStack/4/real_time/threads:1          493 ns        493 ns    1364467
BM_XRayProfilingDeepCallStack/4/real_time/threads:2          319 ns        638 ns    2303518
BM_XRayProfilingDeepCallStack/4/real_time/threads:4          248 ns        990 ns    2819940
BM_XRayProfilingDeepCallStack/4/real_time/threads:8          205 ns       1641 ns    5950176
BM_XRayProfilingDeepCallStack/4/real_time/threads:16         136 ns       2173 ns    7368064
BM_XRayProfilingDeepCallStack/4/real_time/threads:32         164 ns       5236 ns    4473248
BM_XRayProfilingDeepCallStack/8/real_time/threads:1          844 ns        844 ns     801574
BM_XRayProfilingDeepCallStack/8/real_time/threads:2          499 ns        998 ns    1443832
BM_XRayProfilingDeepCallStack/8/real_time/threads:4          347 ns       1389 ns    2580568
BM_XRayProfilingDeepCallStack/8/real_time/threads:8          222 ns       1779 ns    4014088
BM_XRayProfilingDeepCallStack/8/real_time/threads:16         180 ns       2878 ns    5293888
BM_XRayProfilingDeepCallStack/8/real_time/threads:32         199 ns       6356 ns    3462080
BM_XRayProfilingDeepCallStack/16/real_time/threads:1        1616 ns       1616 ns     436321
BM_XRayProfilingDeepCallStack/16/real_time/threads:2         901 ns       1802 ns     785188
BM_XRayProfilingDeepCallStack/16/real_time/threads:4         537 ns       2146 ns    1450452
BM_XRayProfilingDeepCallStack/16/real_time/threads:8         324 ns       2589 ns    2484176
BM_XRayProfilingDeepCallStack/16/real_time/threads:16        265 ns       4239 ns    2503008
BM_XRayProfilingDeepCallStack/16/real_time/threads:32        232 ns       7386 ns    3167712
BM_XRayProfilingDeepCallStack/32/real_time/threads:1        3168 ns       3168 ns     222286
BM_XRayProfilingDeepCallStack/32/real_time/threads:2        1671 ns       3341 ns     422232
BM_XRayProfilingDeepCallStack/32/real_time/threads:4         941 ns       3764 ns     722448
BM_XRayProfilingDeepCallStack/32/real_time/threads:8         549 ns       4393 ns    1367408
BM_XRayProfilingDeepCallStack/32/real_time/threads:16        389 ns       6229 ns    1802800
BM_XRayProfilingDeepCallStack/32/real_time/threads:32        314 ns      10027 ns    2194848
BM_XRayProfilingDeepCallStack/64/real_time/threads:1        6237 ns       6236 ns     111448
BM_XRayProfilingDeepCallStack/64/real_time/threads:2        3251 ns       6501 ns     213690
BM_XRayProfilingDeepCallStack/64/real_time/threads:4        1752 ns       7009 ns     392108
BM_XRayProfilingDeepCallStack/64/real_time/threads:8         989 ns       7914 ns     742304
BM_XRayProfilingDeepCallStack/64/real_time/threads:16        653 ns      10454 ns    1098144
BM_XRayProfilingDeepCallStack/64/real_time/threads:32        451 ns      14443 ns    1472192

Comparing against a run without this change but with D49217:

Run on (48 X 3500 MHz CPU s)                                                                
2018-07-12 17:01:35                                                                         
---------------------------------------------------------------------------------------------
Benchmark                                                      Time           CPU Iterations
---------------------------------------------------------------------------------------------
BM_XRayProfilingDeepCallStack/1/real_time/threads:1          202 ns        202 ns    3477313
BM_XRayProfilingDeepCallStack/1/real_time/threads:2          179 ns        357 ns    4581178
BM_XRayProfilingDeepCallStack/1/real_time/threads:4          144 ns        577 ns    5875828
BM_XRayProfilingDeepCallStack/1/real_time/threads:8          125 ns       1003 ns    8311456                               
BM_XRayProfilingDeepCallStack/1/real_time/threads:16         174 ns       2792 ns    9522368
BM_XRayProfilingDeepCallStack/1/real_time/threads:32         146 ns       4687 ns    6358400
BM_XRayProfilingDeepCallStack/2/real_time/threads:1          295 ns        295 ns    2359216
BM_XRayProfilingDeepCallStack/2/real_time/threads:2          239 ns        478 ns    2888910
BM_XRayProfilingDeepCallStack/2/real_time/threads:4          160 ns        638 ns    5410336
BM_XRayProfilingDeepCallStack/2/real_time/threads:8          125 ns        999 ns    7721696
BM_XRayProfilingDeepCallStack/2/real_time/threads:16         103 ns       1647 ns    5126384
BM_XRayProfilingDeepCallStack/2/real_time/threads:32         131 ns       4153 ns    5427136
BM_XRayProfilingDeepCallStack/4/real_time/threads:1          490 ns        490 ns    1326060
BM_XRayProfilingDeepCallStack/4/real_time/threads:2          367 ns        734 ns    2276550                                          
BM_XRayProfilingDeepCallStack/4/real_time/threads:4          249 ns        994 ns    3981604                   
BM_XRayProfilingDeepCallStack/4/real_time/threads:8          174 ns       1394 ns    5467368
BM_XRayProfilingDeepCallStack/4/real_time/threads:16         129 ns       2057 ns    4399568
BM_XRayProfilingDeepCallStack/4/real_time/threads:32         148 ns       4718 ns    4695104
BM_XRayProfilingDeepCallStack/8/real_time/threads:1          873 ns        873 ns     788744
BM_XRayProfilingDeepCallStack/8/real_time/threads:2          535 ns       1071 ns    1177912
BM_XRayProfilingDeepCallStack/8/real_time/threads:4          339 ns       1354 ns    2235540
BM_XRayProfilingDeepCallStack/8/real_time/threads:8          256 ns       2051 ns    3818424                             
BM_XRayProfilingDeepCallStack/8/real_time/threads:16         208 ns       3323 ns    4687040
BM_XRayProfilingDeepCallStack/8/real_time/threads:32         211 ns       6751 ns    3579136
BM_XRayProfilingDeepCallStack/16/real_time/threads:1        1652 ns       1652 ns     414737
BM_XRayProfilingDeepCallStack/16/real_time/threads:2         975 ns       1950 ns     785698
BM_XRayProfilingDeepCallStack/16/real_time/threads:4         601 ns       2402 ns    1400136
BM_XRayProfilingDeepCallStack/16/real_time/threads:8         365 ns       2918 ns    2308440
BM_XRayProfilingDeepCallStack/16/real_time/threads:16        313 ns       5003 ns    1600000
BM_XRayProfilingDeepCallStack/16/real_time/threads:32        256 ns       8177 ns    3033056
BM_XRayProfilingDeepCallStack/32/real_time/threads:1        3419 ns       3418 ns     209959
BM_XRayProfilingDeepCallStack/32/real_time/threads:2        1858 ns       3716 ns     405304
BM_XRayProfilingDeepCallStack/32/real_time/threads:4        1051 ns       4204 ns     690604
BM_XRayProfilingDeepCallStack/32/real_time/threads:8         611 ns       4890 ns    1233168
BM_XRayProfilingDeepCallStack/32/real_time/threads:16        425 ns       6798 ns    1634992
BM_XRayProfilingDeepCallStack/32/real_time/threads:32        336 ns      10737 ns    1958368
BM_XRayProfilingDeepCallStack/64/real_time/threads:1        6438 ns       6438 ns     105337                    
BM_XRayProfilingDeepCallStack/64/real_time/threads:2        3432 ns       6864 ns     197488
BM_XRayProfilingDeepCallStack/64/real_time/threads:4        2477 ns       9906 ns     376460
BM_XRayProfilingDeepCallStack/64/real_time/threads:8        1069 ns       8547 ns     578224
BM_XRayProfilingDeepCallStack/64/real_time/threads:16        684 ns      10949 ns    1079040
BM_XRayProfilingDeepCallStack/64/real_time/threads:32        482 ns      15417 ns    1298176

[grandinj]

compiler-rt/lib/xray/xray_segmented_array.h

34

Parameter N seems to be dead?

[dberris]

• fixup: remove static assert on size and remove outdated comment

[dberris]

compiler-rt/lib/xray/xray_segmented_array.h

34

Good catch, thanks!

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

struct TestData {
 
   // 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);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> Data(A, CA);
+  Array<TestData> Data(A);
   (void)Data;
 }
 
 TEST(SegmentedArrayTest, ConstructAndPopulate) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  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);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  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);
-  ChunkAllocator CA(1 << 20);
-  Array<TestData> data(A, CA);
+  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);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  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);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  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);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  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);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  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);
-  ChunkAllocator CA(1 << 10);
-  Array<TestData> Data(A, CA);
+  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 Chunk = Array<TestData>::ChunkSize;
-  constexpr auto ChunkX2 = Chunk * 2;
-  for (auto i = ChunkX2; i > 0u; --i) {
+  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(), ChunkX2);
+  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(Chunk);
-  ASSERT_EQ(Data.size(), Chunk);
+  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>(Chunk + 1));
-    ASSERT_EQ(Back.Second, static_cast<s64>(Chunk + 1));
+    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(Chunk);
+  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 = ChunkX2; i > 0u; --i) {
+  for (auto i = SegmentX2; i > 0u; --i) {
     Data.AppendEmplace(static_cast<s64>(i), static_cast<s64>(i));
   }
-  EXPECT_EQ(Data.size(), ChunkX2);
+  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);
-  ChunkAllocator CA(1 << 10);
-  Array<ShadowStackEntry> Data(A, CA);
+  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();

compiler-rt/lib/xray/xray_function_call_trie.h

struct Node {
     Node *Parent;
     NodeIdPairArray 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, NodeIdPairAllocatorType &A, ChunkAllocator &CA, int64_t CC,
-         int64_t CLT, int32_t F)
-        : Parent(P), Callees(A, CA), CallCount(CC), CumulativeLocalTime(CLT),
+    Node(Node *P, NodeIdPairAllocatorType &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 {
     uint64_t EntryTSC;
struct Allocators {
     using NodeAllocatorType = NodeArray::AllocatorType;
     using RootAllocatorType = RootArray::AllocatorType;
     using ShadowStackAllocatorType = ShadowStackArray::AllocatorType;
 
     NodeAllocatorType *NodeAllocator = nullptr;
     RootAllocatorType *RootAllocator = nullptr;
     ShadowStackAllocatorType *ShadowStackAllocator = nullptr;
     NodeIdPairAllocatorType *NodeIdPairAllocator = nullptr;
-    ChunkAllocator *ChunkAlloc = nullptr;
 
     Allocators() {}
     Allocators(const Allocators &) = delete;
     Allocators &operator=(const Allocators &) = delete;
 
     Allocators(Allocators &&O)
         : NodeAllocator(O.NodeAllocator), RootAllocator(O.RootAllocator),
           ShadowStackAllocator(O.ShadowStackAllocator),
-          NodeIdPairAllocator(O.NodeIdPairAllocator), ChunkAlloc(O.ChunkAlloc) {
+          NodeIdPairAllocator(O.NodeIdPairAllocator) {
       O.NodeAllocator = nullptr;
       O.RootAllocator = nullptr;
       O.ShadowStackAllocator = nullptr;
       O.NodeIdPairAllocator = nullptr;
-      O.ChunkAlloc = 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.NodeIdPairAllocator;
         O.NodeIdPairAllocator = this->NodeIdPairAllocator;
         this->NodeIdPairAllocator = Tmp;
       }
-      {
-        auto Tmp = O.ChunkAlloc;
-        O.ChunkAlloc = this->ChunkAlloc;
-        this->ChunkAlloc = 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) {
~Allocators() {
         InternalFree(ShadowStackAllocator);
         ShadowStackAllocator = nullptr;
       }
       if (NodeIdPairAllocator != nullptr) {
         NodeIdPairAllocator->~NodeIdPairAllocatorType();
         InternalFree(NodeIdPairAllocator);
         NodeIdPairAllocator = nullptr;
       }
-      if (ChunkAlloc != nullptr) {
-        ChunkAlloc->~ChunkAllocator();
-        InternalFree(ChunkAlloc);
-        ChunkAlloc = nullptr;
-      }
     }
   };
 
   // TODO: Support configuration of options through the arguments.
   static Allocators InitAllocators() {
     return InitAllocatorsCustom(profilingFlags()->per_thread_allocator_max);
   }
 
auto ShadowStackAllocator =
             InternalAlloc(sizeof(Allocators::ShadowStackAllocatorType)));
     new (ShadowStackAllocator) Allocators::ShadowStackAllocatorType(Max);
     A.ShadowStackAllocator = ShadowStackAllocator;
 
     auto NodeIdPairAllocator = reinterpret_cast<NodeIdPairAllocatorType *>(
         InternalAlloc(sizeof(NodeIdPairAllocatorType)));
     new (NodeIdPairAllocator) NodeIdPairAllocatorType(Max);
     A.NodeIdPairAllocator = NodeIdPairAllocator;
-
-    auto ChunkAlloc = reinterpret_cast<ChunkAllocator *>(
-        InternalAlloc(sizeof(ChunkAllocator)));
-    new (ChunkAlloc) ChunkAllocator(Max);
-    A.ChunkAlloc = ChunkAlloc;
     return A;
   }
 
 private:
   NodeArray Nodes;
   RootArray Roots;
   ShadowStackArray ShadowStack;
   NodeIdPairAllocatorType *NodeIdPairAllocator = nullptr;
-  ChunkAllocator *ChunkAlloc = nullptr;
 
 public:
   explicit FunctionCallTrie(const Allocators &A)
-      : Nodes(*A.NodeAllocator, *A.ChunkAlloc),
-        Roots(*A.RootAllocator, *A.ChunkAlloc),
-        ShadowStack(*A.ShadowStackAllocator, *A.ChunkAlloc),
-        NodeIdPairAllocator(A.NodeIdPairAllocator), ChunkAlloc(A.ChunkAlloc) {}
+      : Nodes(*A.NodeAllocator), Roots(*A.RootAllocator),
+        ShadowStack(*A.ShadowStackAllocator),
+        NodeIdPairAllocator(A.NodeIdPairAllocator) {}
 
   void enterFunction(const int32_t FId, uint64_t TSC) {
     DCHECK_NE(FId, 0);
     // 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, *NodeIdPairAllocator,
-                                         *ChunkAlloc, 0, 0, FId);
+      auto NewRoot =
+          Nodes.AppendEmplace(nullptr, *NodeIdPairAllocator, 0, 0, FId);
       if (UNLIKELY(NewRoot == nullptr))
         return;
       Roots.Append(NewRoot);
       ShadowStack.AppendEmplace(TSC, NewRoot);
       return;
     }
 
     auto &Top = ShadowStack.back();
     auto TopNode = Top.NodePtr;
     DCHECK_NE(TopNode, nullptr);
 
     // 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 NodeIdPair &NR) { return NR.FId == FId; });
     if (Callee != nullptr) {
       CHECK_NE(Callee->NodePtr, nullptr);
       ShadowStack.AppendEmplace(TSC, Callee->NodePtr);
       return;
     }
 
     // This means we've never seen this stack before, create a new node here.
-    auto NewNode = Nodes.AppendEmplace(TopNode, *NodeIdPairAllocator,
-                                       *ChunkAlloc, 0, 0, FId);
+    auto NewNode =
+        Nodes.AppendEmplace(TopNode, *NodeIdPairAllocator, 0, 0, FId);
     if (UNLIKELY(NewNode == nullptr))
       return;
     DCHECK_NE(NewNode, nullptr);
     TopNode->Callees.AppendEmplace(NewNode, FId);
     ShadowStack.AppendEmplace(TSC, NewNode);
     DCHECK_NE(ShadowStack.back().NodePtr, nullptr);
     return;
   }
void deepCopyInto(FunctionCallTrie &O) const {
     struct NodeAndParent {
       FunctionCallTrie::Node *Node;
       FunctionCallTrie::Node *NewNode;
     };
     using Stack = Array<NodeAndParent>;
 
     typename Stack::AllocatorType StackAllocator(
         profilingFlags()->stack_allocator_max);
-    ChunkAllocator StackChunkAllocator(profilingFlags()->stack_allocator_max);
-    Stack DFSStack(StackAllocator, StackChunkAllocator);
+    Stack DFSStack(StackAllocator);
 
     for (const auto Root : getRoots()) {
       // Add a node in O for this root.
       auto NewRoot = O.Nodes.AppendEmplace(
-          nullptr, *O.NodeIdPairAllocator, *O.ChunkAlloc, Root->CallCount,
+          nullptr, *O.NodeIdPairAllocator, Root->CallCount,
           Root->CumulativeLocalTime, Root->FId);
 
       // Because we cannot allocate more memory we should bail out right away.
       if (UNLIKELY(NewRoot == nullptr))
         return;
 
       O.Roots.Append(NewRoot);
 
       // TODO: Figure out what to do if we fail to allocate any more stack
       // space. Maybe warn or report once?
       DFSStack.AppendEmplace(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.NodeIdPairAllocator, *O.ChunkAlloc,
-              Callee.NodePtr->CallCount, Callee.NodePtr->CumulativeLocalTime,
-              Callee.FId);
+              NP.NewNode, *O.NodeIdPairAllocator, Callee.NodePtr->CallCount,
+              Callee.NodePtr->CumulativeLocalTime, Callee.FId);
           if (UNLIKELY(NewNode == nullptr))
             return;
           NP.NewNode->Callees.AppendEmplace(NewNode, Callee.FId);
           DFSStack.AppendEmplace(Callee.NodePtr, NewNode);
         }
       }
     }
   }
public:
   void mergeInto(FunctionCallTrie &O) const {
     struct NodeAndTarget {
       FunctionCallTrie::Node *OrigNode;
       FunctionCallTrie::Node *TargetNode;
     };
     using Stack = Array<NodeAndTarget>;
     typename Stack::AllocatorType StackAllocator(
         profilingFlags()->stack_allocator_max);
-    ChunkAllocator CA(profilingFlags()->stack_allocator_max);
-    Stack DFSStack(StackAllocator, CA);
+    Stack DFSStack(StackAllocator);
 
     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.NodeIdPairAllocator,
-                                           *O.ChunkAlloc, 0, 0, Root->FId);
+        TargetRoot = O.Nodes.AppendEmplace(nullptr, *O.NodeIdPairAllocator, 0,
+                                           0, Root->FId);
         if (UNLIKELY(TargetRoot == nullptr))
           return;
 
         O.Roots.Append(TargetRoot);
       } else {
         TargetRoot = *R;
       }
 
       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);
         // TODO: Update the histogram as well when we have it ready.
         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::NodeIdPair &C) {
                 return C.FId == Callee.FId;
               });
           if (TargetCallee == nullptr) {
-            auto NewTargetNode =
-                O.Nodes.AppendEmplace(NT.TargetNode, *O.NodeIdPairAllocator,
-                                      *O.ChunkAlloc, 0, 0, Callee.FId);
+            auto NewTargetNode = O.Nodes.AppendEmplace(
+                NT.TargetNode, *O.NodeIdPairAllocator, 0, 0, Callee.FId);
 
             if (UNLIKELY(NewTargetNode == nullptr))
               return;
 
             TargetCallee =
                 NT.TargetNode->Callees.AppendEmplace(NewTargetNode, Callee.FId);
           }
           DFSStack.AppendEmplace(Callee.NodePtr, TargetCallee->NodePtr);

compiler-rt/lib/xray/xray_profile_collector.cc

struct ProfileRecord {
   using PathAllocator = typename PathArray::AllocatorType;
 
   // The Path in this record is the function id's from the leaf to the root of
   // the function call stack as represented from a FunctionCallTrie.
   PathArray *Path = nullptr;
   const FunctionCallTrie::Node *Node = nullptr;
 
   // Constructor for in-place construction.
-  ProfileRecord(PathAllocator &A, ChunkAllocator &CA,
-                const FunctionCallTrie::Node *N)
+  ProfileRecord(PathAllocator &A, const FunctionCallTrie::Node *N)
       : Path([&] {
           auto P =
               reinterpret_cast<PathArray *>(InternalAlloc(sizeof(PathArray)));
-          new (P) PathArray(A, CA);
+          new (P) PathArray(A);
           return P;
         }()),
         Node(N) {}
 };
 
 namespace {
 
 using ProfileRecordArray = Array<ProfileRecord>;
 
 // Walk a depth-first traversal of each root of the FunctionCallTrie to generate
 // the path(s) and the data associated with the path.
 static void populateRecords(ProfileRecordArray &PRs,
                             ProfileRecord::PathAllocator &PA,
-                            ChunkAllocator &CA, const FunctionCallTrie &Trie) {
+                            const FunctionCallTrie &Trie) {
   using StackArray = Array<const FunctionCallTrie::Node *>;
   using StackAllocator = typename StackArray::AllocatorType;
   StackAllocator StackAlloc(profilingFlags()->stack_allocator_max);
-  ChunkAllocator StackChunkAlloc(profilingFlags()->stack_allocator_max);
-  StackArray DFSStack(StackAlloc, StackChunkAlloc);
+  StackArray DFSStack(StackAlloc);
   for (const auto R : Trie.getRoots()) {
     DFSStack.Append(R);
     while (!DFSStack.empty()) {
       auto Node = DFSStack.back();
       DFSStack.trim(1);
-      auto Record = PRs.AppendEmplace(PA, CA, Node);
+      auto Record = PRs.AppendEmplace(PA, Node);
       if (Record == nullptr)
         return;
       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);
void serialize() {
 
   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(profilingFlags()->global_allocator_max);
-    ChunkAllocator CA(profilingFlags()->global_allocator_max);
     ProfileRecord::PathAllocator PathAlloc(
         profilingFlags()->global_allocator_max);
-    ProfileRecordArray ProfileRecords(PRAlloc, CA);
+    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, CA, Trie);
+    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)

compiler-rt/lib/xray/xray_profiling.cc

 struct alignas(64) ProfilingData {
   FunctionCallTrie::Allocators *Allocators = nullptr;
   FunctionCallTrie *FCT = nullptr;
 };
 
 static pthread_key_t ProfilingKey;
 
 thread_local std::aligned_storage<sizeof(ProfilingData)>::type ThreadStorage{};
-
 static ProfilingData &getThreadLocalData() XRAY_NEVER_INSTRUMENT {
-  if (pthread_getspecific(ProfilingKey) == NULL) {
+  thread_local auto ThreadOnce = [] {
     new (&ThreadStorage) ProfilingData{};
     pthread_setspecific(ProfilingKey, &ThreadStorage);
-  }
+    return false;
+  }();
+  (void)ThreadOnce;
 
   auto &TLD = *reinterpret_cast<ProfilingData *>(&ThreadStorage);
 
   // 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 = atomic_load(&ProfilerLogStatus, memory_order_acquire);
   if (Status == XRayLogInitStatus::XRAY_LOG_FINALIZING ||
       Status == XRayLogInitStatus::XRAY_LOG_FINALIZED)

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
+// Defines the implementation of a segmented array, with fixed-size segments
 // backing the segments.
 //
 //===----------------------------------------------------------------------===//
 #ifndef XRAY_SEGMENTED_ARRAY_H
 #define XRAY_SEGMENTED_ARRAY_H
 
 #include "sanitizer_common/sanitizer_allocator.h"
 #include "xray_allocator.h"
 #include "xray_utils.h"
 #include <cassert>
 #include <type_traits>
 #include <utility>
 
 namespace __xray {
-struct Chunk {
-  void *Data;
-  Chunk *Prev;
-  Chunk *Next;
-};
-
-using ChunkAllocator = Allocator<next_pow2(sizeof(Chunk)) * 8>;
 
 /// 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.
-///
-/// We compute the least common multiple of the size of T and the cache line
-/// size, to allow us to maximise the number of T objects we can place in
-/// cache-line multiple sized blocks. To get back the number of T's, we divide
-/// this least common multiple by the size of T.
-template <class T,
-          size_t N = lcm(next_pow2(sizeof(T)), kCacheLineSize) / sizeof(T)>
-struct Array {
-  static constexpr size_t ChunkSize = N;
-  static constexpr size_t ElementStorageSize = next_pow2(sizeof(T));
-  static constexpr size_t AllocatorChunkSize = ElementStorageSize * ChunkSize;
-  using AllocatorType = Allocator<AllocatorChunkSize>;
-  static_assert(std::is_trivially_destructible<T>::value,
-                "T must be trivially destructible.");
+/// elements of T there should be in a single segment of the array.
+template <class T> class Array {
+  struct SegmentBase {
+    SegmentBase *Prev;
+    SegmentBase *Next;
+  };
 
-private:
-  // TODO: Consider co-locating the chunk information with the data in the
-  // Block, as in an intrusive list -- i.e. putting the next and previous
-  // pointer values inside the Block storage.
-  static Chunk SentinelChunk;
+  // We want each segment of the array to be cache-line aligned, and elements of
+  // the array be offset from the beginning of the segment.
+  struct Segment : SegmentBase {
+    char Data[];
+  };
+
+  static_assert(sizeof(Segment) == 16, "");
+
+public:
+  // Each segment of the array will be laid out with the following assumptions:
+  //
+  //   - Each segment will be on a cache-line address boundary (kCacheLineSize
+  //     aligned).
+  //
+  //   - The elements will be accessed through an aligned pointer, dependent on
+  //     the alignment of T.
+  //
+  //   - Each element is at least two-pointers worth from the beginning of the
+  //     Segment, aligned properly, and the rest of the elements are accessed
+  //     through appropriate alignment.
+  //
+  // We then compute the size of the segment to follow this logic:
+  //
+  //   - Compute the number of elements that can fit within
+  //     kCacheLineSize-multiple segments, minus the size of two pointers.
+  //
+  //   - Request cacheline-multiple sized elements from the allocator.
+  static constexpr size_t AlignedElementStorageSize =
+      sizeof(typename std::aligned_storage<sizeof(T), alignof(T)>::type);
+
+  static constexpr size_t SegmentSize =
+      nearest_boundary(sizeof(Segment) + next_pow2(sizeof(T)), kCacheLineSize);
+
+  using AllocatorType = Allocator<SegmentSize>;
+
+  static constexpr size_t ElementsPerSegment =
+      (SegmentSize - sizeof(Segment)) / next_pow2(sizeof(T));
 
+  static_assert(ElementsPerSegment > 0,
+                "Must have at least 1 element per segment.");
+
+  static SegmentBase SentinelSegment;
+
+private:
   AllocatorType *Alloc;
-  ChunkAllocator *ChunkAlloc;
-  Chunk *Head = &SentinelChunk;
-  Chunk *Tail = &SentinelChunk;
+  SegmentBase *Head = &SentinelSegment;
+  SegmentBase *Tail = &SentinelSegment;
   size_t Size = 0;
 
-  // Here we keep track of chunks in the freelist, to allow us to re-use chunks
-  // when elements are trimmed off the end.
-  Chunk *Freelist = &SentinelChunk;
+  // Here we keep track of segments in the freelist, to allow us to re-use
+  // segments when elements are trimmed off the end.
+  SegmentBase *Freelist = &SentinelSegment;
 
-  Chunk *NewChunk() {
+  Segment *NewSegment() {
     // We need to handle the case in which enough elements have been trimmed to
-    // allow us to re-use chunks we've allocated before. For this we look into
+    // allow us to re-use segments we've allocated before. For this we look into
     // the Freelist, to see whether we need to actually allocate new blocks or
     // just re-use blocks we've already seen before.
-    if (Freelist != &SentinelChunk) {
-      auto *FreeChunk = Freelist;
-      Freelist = FreeChunk->Next;
-      FreeChunk->Next = &SentinelChunk;
-      Freelist->Prev = &SentinelChunk;
-      return FreeChunk;
+    if (Freelist != &SentinelSegment) {
+      auto *FreeSegment = Freelist;
+      Freelist = FreeSegment->Next;
+      FreeSegment->Next = &SentinelSegment;
+      Freelist->Prev = &SentinelSegment;
+      return static_cast<Segment *>(FreeSegment);
     }
 
-    auto Block = Alloc->Allocate();
-    if (Block.Data == nullptr)
+    auto SegmentBlock = Alloc->Allocate();
+    if (SegmentBlock.Data == nullptr)
       return nullptr;
 
-    auto ChunkElement = ChunkAlloc->Allocate();
-    if (ChunkElement.Data == nullptr)
-      return nullptr;
-
-    // Placement-new the Chunk element at the appropriate location.
-    auto C = reinterpret_cast<Chunk *>(ChunkElement.Data);
-    Chunk LocalC{Block.Data, &SentinelChunk, &SentinelChunk};
-    internal_memcpy(C, &LocalC, sizeof(LocalC));
-    return C;
+    // Placement-new the Segment element at the beginning of the SegmentBlock.
+    auto S = reinterpret_cast<Segment *>(SegmentBlock.Data);
+    new (S) SegmentBase{&SentinelSegment, &SentinelSegment};
+    return S;
   }
 
-  Chunk *InitHeadAndTail() {
-    DCHECK_EQ(Head, &SentinelChunk);
-    DCHECK_EQ(Tail, &SentinelChunk);
-    auto Chunk = NewChunk();
-    if (Chunk == nullptr)
+  Segment *InitHeadAndTail() {
+    DCHECK_EQ(Head, &SentinelSegment);
+    DCHECK_EQ(Tail, &SentinelSegment);
+    auto Segment = NewSegment();
+    if (Segment == nullptr)
       return nullptr;
-    DCHECK_EQ(Chunk->Next, &SentinelChunk);
-    DCHECK_EQ(Chunk->Prev, &SentinelChunk);
-    return Head = Tail = Chunk;
+    DCHECK_EQ(Segment->Next, &SentinelSegment);
+    DCHECK_EQ(Segment->Prev, &SentinelSegment);
+    Head = Tail = static_cast<SegmentBase *>(Segment);
+    return Segment;
   }
 
-  Chunk *AppendNewChunk() {
-    auto Chunk = NewChunk();
-    if (Chunk == nullptr)
+  Segment *AppendNewSegment() {
+    auto S = NewSegment();
+    if (S == nullptr)
       return nullptr;
-    DCHECK_NE(Tail, &SentinelChunk);
-    DCHECK_EQ(Tail->Next, &SentinelChunk);
-    DCHECK_EQ(Chunk->Prev, &SentinelChunk);
-    DCHECK_EQ(Chunk->Next, &SentinelChunk);
-    Tail->Next = Chunk;
-    Chunk->Prev = Tail;
-    Tail = Chunk;
-    return Tail;
+    DCHECK_NE(Tail, &SentinelSegment);
+    DCHECK_EQ(Tail->Next, &SentinelSegment);
+    DCHECK_EQ(S->Prev, &SentinelSegment);
+    DCHECK_EQ(S->Next, &SentinelSegment);
+    Tail->Next = S;
+    S->Prev = Tail;
+    Tail = S;
+    return static_cast<Segment *>(Tail);
   }
 
   // This Iterator models a BidirectionalIterator.
   template <class U> class Iterator {
-    Chunk *C = &SentinelChunk;
+    SegmentBase *S = &SentinelSegment;
     size_t Offset = 0;
     size_t Size = 0;
 
   public:
-    Iterator(Chunk *IC, size_t Off, size_t S) : C(IC), Offset(Off), Size(S) {}
+    Iterator(SegmentBase *IS, size_t Off, size_t S)
+        : S(IS), Offset(Off), Size(S) {}
     Iterator(const Iterator &) noexcept = default;
     Iterator() noexcept = default;
     Iterator(Iterator &&) noexcept = default;
     Iterator &operator=(const Iterator &) = default;
     Iterator &operator=(Iterator &&) = default;
     ~Iterator() = default;
 
     Iterator &operator++() {
-      if (++Offset % N || Offset == Size)
+      if (++Offset % ElementsPerSegment || Offset == Size)
         return *this;
 
       // At this point, we know that Offset % N == 0, so we must advance the
-      // chunk pointer.
-      DCHECK_EQ(Offset % N, 0);
+      // segment pointer.
+      DCHECK_EQ(Offset % ElementsPerSegment, 0);
       DCHECK_NE(Offset, Size);
-      DCHECK_NE(C, &SentinelChunk);
-      DCHECK_NE(C->Next, &SentinelChunk);
-      C = C->Next;
-      DCHECK_NE(C, &SentinelChunk);
+      DCHECK_NE(S, &SentinelSegment);
+      DCHECK_NE(S->Next, &SentinelSegment);
+      S = S->Next;
+      DCHECK_NE(S, &SentinelSegment);
       return *this;
     }
 
     Iterator &operator--() {
-      DCHECK_NE(C, &SentinelChunk);
+      DCHECK_NE(S, &SentinelSegment);
       DCHECK_GT(Offset, 0);
 
       auto PreviousOffset = Offset--;
-      if (PreviousOffset != Size && PreviousOffset % N == 0) {
-        DCHECK_NE(C->Prev, &SentinelChunk);
-        C = C->Prev;
+      if (PreviousOffset != Size && PreviousOffset % ElementsPerSegment == 0) {
+        DCHECK_NE(S->Prev, &SentinelSegment);
+        S = S->Prev;
       }
 
       return *this;
     }
 
     Iterator operator++(int) {
       Iterator Copy(*this);
       ++(*this);
       return Copy;
     }
 
     Iterator operator--(int) {
       Iterator Copy(*this);
       --(*this);
       return Copy;
     }
 
     template <class V, class W>
     friend bool operator==(const Iterator<V> &L, const Iterator<W> &R) {
-      return L.C == R.C && L.Offset == R.Offset;
+      return L.S == R.S && L.Offset == R.Offset;
     }
 
     template <class V, class W>
     friend bool operator!=(const Iterator<V> &L, const Iterator<W> &R) {
       return !(L == R);
     }
 
     U &operator*() const {
-      DCHECK_NE(C, &SentinelChunk);
-      auto RelOff = Offset % N;
-      return *reinterpret_cast<U *>(reinterpret_cast<char *>(C->Data) +
-                                    (RelOff * ElementStorageSize));
-    }
+      DCHECK_NE(S, &SentinelSegment);
+      auto RelOff = Offset % ElementsPerSegment;
 
-    U *operator->() const {
-      DCHECK_NE(C, &SentinelChunk);
-      auto RelOff = Offset % N;
-      return reinterpret_cast<U *>(reinterpret_cast<char *>(C->Data) +
-                                   (RelOff * ElementStorageSize));
+      // We need to compute the character-aligned pointer, offset from the
+      // segment's Data location to get the element in the position of Offset.
+      auto Base = static_cast<Segment *>(S)->Data;
+      auto AlignedOffset = Base + (RelOff * AlignedElementStorageSize);
+      return *reinterpret_cast<U *>(AlignedOffset);
     }
+
+    U *operator->() const { return &(**this); }
   };
 
 public:
-  explicit Array(AllocatorType &A, ChunkAllocator &CA)
-      : Alloc(&A), ChunkAlloc(&CA) {}
+  explicit Array(AllocatorType &A) : Alloc(&A) {}
 
   Array(const Array &) = delete;
   Array(Array &&O) NOEXCEPT : Alloc(O.Alloc),
                               Head(O.Head),
                               Tail(O.Tail),
                               Size(O.Size) {
-    O.Head = &SentinelChunk;
-    O.Tail = &SentinelChunk;
+    O.Head = &SentinelSegment;
+    O.Tail = &SentinelSegment;
     O.Size = 0;
   }
 
   bool empty() const { return Size == 0; }
 
   AllocatorType &allocator() const {
     DCHECK_NE(Alloc, nullptr);
     return *Alloc;
   }
 
   size_t size() const { return Size; }
 
   T *Append(const T &E) {
-    if (UNLIKELY(Head == &SentinelChunk))
+    if (UNLIKELY(Head == &SentinelSegment))
       if (InitHeadAndTail() == nullptr)
         return nullptr;
 
-    auto Offset = Size % N;
+    auto Offset = Size % ElementsPerSegment;
     if (UNLIKELY(Size != 0 && Offset == 0))
-      if (AppendNewChunk() == nullptr)
+      if (AppendNewSegment() == nullptr)
         return nullptr;
 
-    auto Position = reinterpret_cast<T *>(reinterpret_cast<char *>(Tail->Data) +
-                                          (Offset * ElementStorageSize));
+    auto Base = static_cast<Segment *>(Tail)->Data;
+    auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
+    auto Position = reinterpret_cast<T *>(AlignedOffset);
     *Position = E;
     ++Size;
     return Position;
   }
 
   template <class... Args> T *AppendEmplace(Args &&... args) {
-    if (UNLIKELY(Head == &SentinelChunk))
+    if (UNLIKELY(Head == &SentinelSegment))
       if (InitHeadAndTail() == nullptr)
         return nullptr;
 
-    auto Offset = Size % N;
-    auto *LatestChunk = Tail;
+    auto Offset = Size % ElementsPerSegment;
+    auto *LatestSegment = Tail;
     if (UNLIKELY(Size != 0 && Offset == 0)) {
-      LatestChunk = AppendNewChunk();
-      if (LatestChunk == nullptr)
+      LatestSegment = AppendNewSegment();
+      if (LatestSegment == nullptr)
         return nullptr;
     }
 
-    DCHECK_NE(Tail, &SentinelChunk);
-    auto Position = reinterpret_cast<char *>(LatestChunk->Data) +
-                    (Offset * ElementStorageSize);
-    DCHECK_EQ(reinterpret_cast<uintptr_t>(Position) % ElementStorageSize, 0);
+    DCHECK_NE(Tail, &SentinelSegment);
+    auto Base = static_cast<Segment *>(LatestSegment)->Data;
+    auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
+    auto Position = reinterpret_cast<T *>(AlignedOffset);
+
     // In-place construct at Position.
     new (Position) T{std::forward<Args>(args)...};
     ++Size;
     return reinterpret_cast<T *>(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);
-    }
-    return *reinterpret_cast<T *>(reinterpret_cast<char *>(C->Data) +
-                                  (Offset * ElementStorageSize));
+    auto S = Head;
+    while (Offset >= ElementsPerSegment) {
+      S = S->Next;
+      Offset -= ElementsPerSegment;
+      DCHECK_NE(S, &SentinelSegment);
+    }
+    auto Base = static_cast<Segment *>(S)->Data;
+    auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
+    auto Position = reinterpret_cast<T *>(AlignedOffset);
+    return *reinterpret_cast<T *>(Position);
   }
 
   T &front() const {
-    DCHECK_NE(Head, &SentinelChunk);
+    DCHECK_NE(Head, &SentinelSegment);
     DCHECK_NE(Size, 0u);
     return *begin();
   }
 
   T &back() const {
-    DCHECK_NE(Tail, &SentinelChunk);
+    DCHECK_NE(Tail, &SentinelSegment);
     DCHECK_NE(Size, 0u);
     auto It = end();
     --It;
     return *It;
   }
 
   template <class Predicate> T *find_element(Predicate P) const {
     if (empty())
public:
   /// Remove N Elements from the end. This leaves the blocks behind, and not
   /// require allocation of new blocks for new elements added after trimming.
   void trim(size_t Elements) {
     DCHECK_LE(Elements, Size);
     DCHECK_GT(Size, 0);
     auto OldSize = Size;
     Size -= Elements;
 
-    DCHECK_NE(Head, &SentinelChunk);
-    DCHECK_NE(Tail, &SentinelChunk);
+    DCHECK_NE(Head, &SentinelSegment);
+    DCHECK_NE(Tail, &SentinelSegment);
 
-    for (auto ChunksToTrim =
-             (nearest_boundary(OldSize, N) - nearest_boundary(Size, N)) / N;
-         ChunksToTrim > 0; --ChunksToTrim) {
-      DCHECK_NE(Head, &SentinelChunk);
-      DCHECK_NE(Tail, &SentinelChunk);
+    for (auto SegmentsToTrim = (nearest_boundary(OldSize, ElementsPerSegment) -
+                                nearest_boundary(Size, ElementsPerSegment)) /
+                               ElementsPerSegment;
+         SegmentsToTrim > 0; --SegmentsToTrim) {
+      DCHECK_NE(Head, &SentinelSegment);
+      DCHECK_NE(Tail, &SentinelSegment);
       // Put the tail into the Freelist.
-      auto *FreeChunk = Tail;
+      auto *FreeSegment = Tail;
       Tail = Tail->Prev;
-      if (Tail == &SentinelChunk)
+      if (Tail == &SentinelSegment)
         Head = Tail;
       else
-        Tail->Next = &SentinelChunk;
+        Tail->Next = &SentinelSegment;
 
-      DCHECK_EQ(Tail->Next, &SentinelChunk);
-      FreeChunk->Next = Freelist;
-      FreeChunk->Prev = &SentinelChunk;
-      if (Freelist != &SentinelChunk)
-        Freelist->Prev = FreeChunk;
-      Freelist = FreeChunk;
+      DCHECK_EQ(Tail->Next, &SentinelSegment);
+      FreeSegment->Next = Freelist;
+      FreeSegment->Prev = &SentinelSegment;
+      if (Freelist != &SentinelSegment)
+        Freelist->Prev = FreeSegment;
+      Freelist = FreeSegment;
     }
   }
 
   // Provide iterators.
   Iterator<T> begin() const { return Iterator<T>(Head, 0, Size); }
   Iterator<T> end() const { return Iterator<T>(Tail, Size, Size); }
   Iterator<const T> cbegin() const { return Iterator<const T>(Head, 0, Size); }
   Iterator<const T> cend() const { return Iterator<const T>(Tail, Size, Size); }
 };
 
 // We need to have this storage definition out-of-line so that the compiler can
-// ensure that storage for the SentinelChunk is defined and has a single
+// ensure that storage for the SentinelSegment is defined and has a single
 // address.
-template <class T, size_t N>
-Chunk Array<T, N>::SentinelChunk{nullptr, &Array<T, N>::SentinelChunk,
-                                 &Array<T, N>::SentinelChunk};
+template <class T>
+typename Array<T>::SegmentBase Array<T>::SentinelSegment{
+    &Array<T>::SentinelSegment, &Array<T>::SentinelSegment};
 
 } // namespace __xray
 
 #endif // XRAY_SEGMENTED_ARRAY_H