1 files changed, 430 insertions, 154 deletions

diff --git a/contrib/compiler-rt/lib/xray/xray_segmented_array.h b/contrib/compiler-rt/lib/xray/xray_segmented_array.h
index 11dd794fa520..bc7e9379f63b 100644
--- a/contrib/compiler-rt/lib/xray/xray_segmented_array.h
+++ b/contrib/compiler-rt/lib/xray/xray_segmented_array.h
@@ -32,14 +32,9 @@ namespace __xray {
 /// is destroyed. When an Array is destroyed, it will destroy elements in the
 /// backing store but will not free the memory.
 template <class T> class Array {
-  struct SegmentBase {
-    SegmentBase *Prev;
-    SegmentBase *Next;
-  };
-
-  // 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 {
+  struct Segment {
+    Segment *Prev;
+    Segment *Next;
     char Data[1];
   };
 
@@ -62,98 +57,46 @@ public:
   //     kCacheLineSize-multiple segments, minus the size of two pointers.
   //
   //   - Request cacheline-multiple sized elements from the allocator.
-  static constexpr size_t AlignedElementStorageSize =
+  static constexpr uint64_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);
+  static constexpr uint64_t SegmentControlBlockSize = sizeof(Segment *) * 2;
+
+  static constexpr uint64_t SegmentSize = nearest_boundary(
+      SegmentControlBlockSize + next_pow2(sizeof(T)), kCacheLineSize);
 
   using AllocatorType = Allocator<SegmentSize>;
 
-  static constexpr size_t ElementsPerSegment =
-      (SegmentSize - sizeof(Segment)) / next_pow2(sizeof(T));
+  static constexpr uint64_t ElementsPerSegment =
+      (SegmentSize - SegmentControlBlockSize) / next_pow2(sizeof(T));
 
   static_assert(ElementsPerSegment > 0,
                 "Must have at least 1 element per segment.");
 
-  static SegmentBase SentinelSegment;
-
-private:
-  AllocatorType *Alloc;
-  SegmentBase *Head = &SentinelSegment;
-  SegmentBase *Tail = &SentinelSegment;
-  size_t Size = 0;
-
-  // 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;
-
-  Segment *NewSegment() {
-    // We need to handle the case in which enough elements have been trimmed to
-    // 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 != &SentinelSegment) {
-      auto *FreeSegment = Freelist;
-      Freelist = FreeSegment->Next;
-      FreeSegment->Next = &SentinelSegment;
-      Freelist->Prev = &SentinelSegment;
-      return static_cast<Segment *>(FreeSegment);
-    }
-
-    auto SegmentBlock = Alloc->Allocate();
-    if (SegmentBlock.Data == nullptr)
-      return nullptr;
-
-    // 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;
-  }
-
-  Segment *InitHeadAndTail() {
-    DCHECK_EQ(Head, &SentinelSegment);
-    DCHECK_EQ(Tail, &SentinelSegment);
-    auto Segment = NewSegment();
-    if (Segment == nullptr)
-      return nullptr;
-    DCHECK_EQ(Segment->Next, &SentinelSegment);
-    DCHECK_EQ(Segment->Prev, &SentinelSegment);
-    Head = Tail = static_cast<SegmentBase *>(Segment);
-    return Segment;
-  }
+  static Segment SentinelSegment;
 
-  Segment *AppendNewSegment() {
-    auto S = NewSegment();
-    if (S == nullptr)
-      return nullptr;
-    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);
-  }
+  using size_type = uint64_t;
 
+private:
   // This Iterator models a BidirectionalIterator.
   template <class U> class Iterator {
-    SegmentBase *S = &SentinelSegment;
-    size_t Offset = 0;
-    size_t Size = 0;
+    Segment *S = &SentinelSegment;
+    uint64_t Offset = 0;
+    uint64_t Size = 0;
 
   public:
-    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++() {
+    Iterator(Segment *IS, uint64_t Off, uint64_t S) XRAY_NEVER_INSTRUMENT
+        : S(IS),
+          Offset(Off),
+          Size(S) {}
+    Iterator(const Iterator &) NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
+    Iterator() NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
+    Iterator(Iterator &&) NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
+    Iterator &operator=(const Iterator &) XRAY_NEVER_INSTRUMENT = default;
+    Iterator &operator=(Iterator &&) XRAY_NEVER_INSTRUMENT = default;
+    ~Iterator() XRAY_NEVER_INSTRUMENT = default;
+
+    Iterator &operator++() XRAY_NEVER_INSTRUMENT {
       if (++Offset % ElementsPerSegment || Offset == Size)
         return *this;
 
@@ -168,7 +111,7 @@ private:
       return *this;
     }
 
-    Iterator &operator--() {
+    Iterator &operator--() XRAY_NEVER_INSTRUMENT {
       DCHECK_NE(S, &SentinelSegment);
       DCHECK_GT(Offset, 0);
 
@@ -181,107 +124,295 @@ private:
       return *this;
     }
 
-    Iterator operator++(int) {
+    Iterator operator++(int) XRAY_NEVER_INSTRUMENT {
       Iterator Copy(*this);
       ++(*this);
       return Copy;
     }
 
-    Iterator operator--(int) {
+    Iterator operator--(int) XRAY_NEVER_INSTRUMENT {
       Iterator Copy(*this);
       --(*this);
       return Copy;
     }
 
     template <class V, class W>
-    friend bool operator==(const Iterator<V> &L, const Iterator<W> &R) {
+    friend bool operator==(const Iterator<V> &L,
+                           const Iterator<W> &R) XRAY_NEVER_INSTRUMENT {
       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) {
+    friend bool operator!=(const Iterator<V> &L,
+                           const Iterator<W> &R) XRAY_NEVER_INSTRUMENT {
       return !(L == R);
     }
 
-    U &operator*() const {
+    U &operator*() const XRAY_NEVER_INSTRUMENT {
       DCHECK_NE(S, &SentinelSegment);
       auto RelOff = Offset % ElementsPerSegment;
 
       // 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 Base = &S->Data;
       auto AlignedOffset = Base + (RelOff * AlignedElementStorageSize);
       return *reinterpret_cast<U *>(AlignedOffset);
     }
 
-    U *operator->() const { return &(**this); }
+    U *operator->() const XRAY_NEVER_INSTRUMENT { return &(**this); }
   };
 
+  AllocatorType *Alloc;
+  Segment *Head;
+  Segment *Tail;
+
+  // Here we keep track of segments in the freelist, to allow us to re-use
+  // segments when elements are trimmed off the end.
+  Segment *Freelist;
+  uint64_t Size;
+
+  // ===============================
+  // In the following implementation, we work through the algorithms and the
+  // list operations using the following notation:
+  //
+  //   - pred(s) is the predecessor (previous node accessor) and succ(s) is
+  //     the successor (next node accessor).
+  //
+  //   - S is a sentinel segment, which has the following property:
+  //
+  //         pred(S) == succ(S) == S
+  //
+  //   - @ is a loop operator, which can imply pred(s) == s if it appears on
+  //     the left of s, or succ(s) == S if it appears on the right of s.
+  //
+  //   - sL <-> sR : means a bidirectional relation between sL and sR, which
+  //     means:
+  //
+  //         succ(sL) == sR && pred(SR) == sL
+  //
+  //   - sL -> sR : implies a unidirectional relation between sL and SR,
+  //     with the following properties:
+  //
+  //         succ(sL) == sR
+  //
+  //     sL <- sR : implies a unidirectional relation between sR and sL,
+  //     with the following properties:
+  //
+  //         pred(sR) == sL
+  //
+  // ===============================
+
+  Segment *NewSegment() XRAY_NEVER_INSTRUMENT {
+    // We need to handle the case in which enough elements have been trimmed to
+    // 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 != &SentinelSegment) {
+      // The current state of lists resemble something like this at this point:
+      //
+      //   Freelist: @S@<-f0->...<->fN->@S@
+      //                  ^ Freelist
+      //
+      // We want to perform a splice of `f0` from Freelist to a temporary list,
+      // which looks like:
+      //
+      //   Templist: @S@<-f0->@S@
+      //                  ^ FreeSegment
+      //
+      // Our algorithm preconditions are:
+      DCHECK_EQ(Freelist->Prev, &SentinelSegment);
+
+      // Then the algorithm we implement is:
+      //
+      //   SFS = Freelist
+      //   Freelist = succ(Freelist)
+      //   if (Freelist != S)
+      //     pred(Freelist) = S
+      //   succ(SFS) = S
+      //   pred(SFS) = S
+      //
+      auto *FreeSegment = Freelist;
+      Freelist = Freelist->Next;
+
+      // Note that we need to handle the case where Freelist is now pointing to
+      // S, which we don't want to be overwriting.
+      // TODO: Determine whether the cost of the branch is higher than the cost
+      // of the blind assignment.
+      if (Freelist != &SentinelSegment)
+        Freelist->Prev = &SentinelSegment;
+
+      FreeSegment->Next = &SentinelSegment;
+      FreeSegment->Prev = &SentinelSegment;
+
+      // Our postconditions are:
+      DCHECK_EQ(Freelist->Prev, &SentinelSegment);
+      DCHECK_NE(FreeSegment, &SentinelSegment);
+      return FreeSegment;
+    }
+
+    auto SegmentBlock = Alloc->Allocate();
+    if (SegmentBlock.Data == nullptr)
+      return nullptr;
+
+    // Placement-new the Segment element at the beginning of the SegmentBlock.
+    new (SegmentBlock.Data) Segment{&SentinelSegment, &SentinelSegment, {0}};
+    auto SB = reinterpret_cast<Segment *>(SegmentBlock.Data);
+    return SB;
+  }
+
+  Segment *InitHeadAndTail() XRAY_NEVER_INSTRUMENT {
+    DCHECK_EQ(Head, &SentinelSegment);
+    DCHECK_EQ(Tail, &SentinelSegment);
+    auto S = NewSegment();
+    if (S == nullptr)
+      return nullptr;
+    DCHECK_EQ(S->Next, &SentinelSegment);
+    DCHECK_EQ(S->Prev, &SentinelSegment);
+    DCHECK_NE(S, &SentinelSegment);
+    Head = S;
+    Tail = S;
+    DCHECK_EQ(Head, Tail);
+    DCHECK_EQ(Tail->Next, &SentinelSegment);
+    DCHECK_EQ(Tail->Prev, &SentinelSegment);
+    return S;
+  }
+
+  Segment *AppendNewSegment() XRAY_NEVER_INSTRUMENT {
+    auto S = NewSegment();
+    if (S == nullptr)
+      return nullptr;
+    DCHECK_NE(Tail, &SentinelSegment);
+    DCHECK_EQ(Tail->Next, &SentinelSegment);
+    DCHECK_EQ(S->Prev, &SentinelSegment);
+    DCHECK_EQ(S->Next, &SentinelSegment);
+    S->Prev = Tail;
+    Tail->Next = S;
+    Tail = S;
+    DCHECK_EQ(S, S->Prev->Next);
+    DCHECK_EQ(Tail->Next, &SentinelSegment);
+    return S;
+  }
+
 public:
-  explicit Array(AllocatorType &A) : Alloc(&A) {}
+  explicit Array(AllocatorType &A) XRAY_NEVER_INSTRUMENT
+      : Alloc(&A),
+        Head(&SentinelSegment),
+        Tail(&SentinelSegment),
+        Freelist(&SentinelSegment),
+        Size(0) {}
+
+  Array() XRAY_NEVER_INSTRUMENT : Alloc(nullptr),
+                                  Head(&SentinelSegment),
+                                  Tail(&SentinelSegment),
+                                  Freelist(&SentinelSegment),
+                                  Size(0) {}
 
   Array(const Array &) = delete;
-  Array(Array &&O) NOEXCEPT : Alloc(O.Alloc),
-                              Head(O.Head),
-                              Tail(O.Tail),
-                              Size(O.Size) {
+  Array &operator=(const Array &) = delete;
+
+  Array(Array &&O) XRAY_NEVER_INSTRUMENT : Alloc(O.Alloc),
+                                           Head(O.Head),
+                                           Tail(O.Tail),
+                                           Freelist(O.Freelist),
+                                           Size(O.Size) {
+    O.Alloc = nullptr;
     O.Head = &SentinelSegment;
     O.Tail = &SentinelSegment;
     O.Size = 0;
+    O.Freelist = &SentinelSegment;
   }
 
-  bool empty() const { return Size == 0; }
+  Array &operator=(Array &&O) XRAY_NEVER_INSTRUMENT {
+    Alloc = O.Alloc;
+    O.Alloc = nullptr;
+    Head = O.Head;
+    O.Head = &SentinelSegment;
+    Tail = O.Tail;
+    O.Tail = &SentinelSegment;
+    Freelist = O.Freelist;
+    O.Freelist = &SentinelSegment;
+    Size = O.Size;
+    O.Size = 0;
+    return *this;
+  }
+
+  ~Array() XRAY_NEVER_INSTRUMENT {
+    for (auto &E : *this)
+      (&E)->~T();
+  }
 
-  AllocatorType &allocator() const {
+  bool empty() const XRAY_NEVER_INSTRUMENT { return Size == 0; }
+
+  AllocatorType &allocator() const XRAY_NEVER_INSTRUMENT {
     DCHECK_NE(Alloc, nullptr);
     return *Alloc;
   }
 
-  size_t size() const { return Size; }
+  uint64_t size() const XRAY_NEVER_INSTRUMENT { return Size; }
 
-  T *Append(const T &E) {
-    if (UNLIKELY(Head == &SentinelSegment))
-      if (InitHeadAndTail() == nullptr)
+  template <class... Args>
+  T *AppendEmplace(Args &&... args) XRAY_NEVER_INSTRUMENT {
+    DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) ||
+           (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
+    if (UNLIKELY(Head == &SentinelSegment)) {
+      auto R = InitHeadAndTail();
+      if (R == nullptr)
         return nullptr;
+    }
+
+    DCHECK_NE(Head, &SentinelSegment);
+    DCHECK_NE(Tail, &SentinelSegment);
 
     auto Offset = Size % ElementsPerSegment;
     if (UNLIKELY(Size != 0 && Offset == 0))
       if (AppendNewSegment() == nullptr)
         return nullptr;
 
-    auto Base = static_cast<Segment *>(Tail)->Data;
+    DCHECK_NE(Tail, &SentinelSegment);
+    auto Base = &Tail->Data;
     auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
-    auto Position = reinterpret_cast<T *>(AlignedOffset);
-    *Position = E;
+    DCHECK_LE(AlignedOffset + sizeof(T),
+              reinterpret_cast<unsigned char *>(Base) + SegmentSize);
+
+    // In-place construct at Position.
+    new (AlignedOffset) T{std::forward<Args>(args)...};
     ++Size;
-    return Position;
+    return reinterpret_cast<T *>(AlignedOffset);
   }
 
-  template <class... Args> T *AppendEmplace(Args &&... args) {
-    if (UNLIKELY(Head == &SentinelSegment))
-      if (InitHeadAndTail() == nullptr)
+  T *Append(const T &E) XRAY_NEVER_INSTRUMENT {
+    // FIXME: This is a duplication of AppenEmplace with the copy semantics
+    // explicitly used, as a work-around to GCC 4.8 not invoking the copy
+    // constructor with the placement new with braced-init syntax.
+    DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) ||
+           (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
+    if (UNLIKELY(Head == &SentinelSegment)) {
+      auto R = InitHeadAndTail();
+      if (R == nullptr)
         return nullptr;
+    }
+
+    DCHECK_NE(Head, &SentinelSegment);
+    DCHECK_NE(Tail, &SentinelSegment);
 
     auto Offset = Size % ElementsPerSegment;
-    auto *LatestSegment = Tail;
-    if (UNLIKELY(Size != 0 && Offset == 0)) {
-      LatestSegment = AppendNewSegment();
-      if (LatestSegment == nullptr)
+    if (UNLIKELY(Size != 0 && Offset == 0))
+      if (AppendNewSegment() == nullptr)
         return nullptr;
-    }
 
     DCHECK_NE(Tail, &SentinelSegment);
-    auto Base = static_cast<Segment *>(LatestSegment)->Data;
+    auto Base = &Tail->Data;
     auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
-    auto Position = reinterpret_cast<T *>(AlignedOffset);
+    DCHECK_LE(AlignedOffset + sizeof(T),
+              reinterpret_cast<unsigned char *>(Tail) + SegmentSize);
 
     // In-place construct at Position.
-    new (Position) T{std::forward<Args>(args)...};
+    new (AlignedOffset) T(E);
     ++Size;
-    return reinterpret_cast<T *>(Position);
+    return reinterpret_cast<T *>(AlignedOffset);
   }
 
-  T &operator[](size_t Offset) const {
+  T &operator[](uint64_t Offset) const XRAY_NEVER_INSTRUMENT {
     DCHECK_LE(Offset, Size);
     // We need to traverse the array enough times to find the element at Offset.
     auto S = Head;
@@ -290,19 +421,19 @@ public:
       Offset -= ElementsPerSegment;
       DCHECK_NE(S, &SentinelSegment);
     }
-    auto Base = static_cast<Segment *>(S)->Data;
+    auto Base = &S->Data;
     auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
     auto Position = reinterpret_cast<T *>(AlignedOffset);
     return *reinterpret_cast<T *>(Position);
   }
 
-  T &front() const {
+  T &front() const XRAY_NEVER_INSTRUMENT {
     DCHECK_NE(Head, &SentinelSegment);
     DCHECK_NE(Size, 0u);
     return *begin();
   }
 
-  T &back() const {
+  T &back() const XRAY_NEVER_INSTRUMENT {
     DCHECK_NE(Tail, &SentinelSegment);
     DCHECK_NE(Size, 0u);
     auto It = end();
@@ -310,7 +441,8 @@ public:
     return *It;
   }
 
-  template <class Predicate> T *find_element(Predicate P) const {
+  template <class Predicate>
+  T *find_element(Predicate P) const XRAY_NEVER_INSTRUMENT {
     if (empty())
       return nullptr;
 
@@ -324,51 +456,195 @@ 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);
+  void trim(uint64_t Elements) XRAY_NEVER_INSTRUMENT {
     auto OldSize = Size;
+    Elements = Elements > Size ? Size : Elements;
     Size -= Elements;
 
-    DCHECK_NE(Head, &SentinelSegment);
-    DCHECK_NE(Tail, &SentinelSegment);
-
-    for (auto SegmentsToTrim = (nearest_boundary(OldSize, ElementsPerSegment) -
-                                nearest_boundary(Size, ElementsPerSegment)) /
-                               ElementsPerSegment;
-         SegmentsToTrim > 0; --SegmentsToTrim) {
+    // We compute the number of segments we're going to return from the tail by
+    // counting how many elements have been trimmed. Given the following:
+    //
+    // - Each segment has N valid positions, where N > 0
+    // - The previous size > current size
+    //
+    // To compute the number of segments to return, we need to perform the
+    // following calculations for the number of segments required given 'x'
+    // elements:
+    //
+    //   f(x) = {
+    //            x == 0          : 0
+    //          , 0 < x <= N      : 1
+    //          , N < x <= max    : x / N + (x % N ? 1 : 0)
+    //          }
+    //
+    // We can simplify this down to:
+    //
+    //   f(x) = {
+    //            x == 0          : 0,
+    //          , 0 < x <= max    : x / N + (x < N || x % N ? 1 : 0)
+    //          }
+    //
+    // And further down to:
+    //
+    //   f(x) = x ? x / N + (x < N || x % N ? 1 : 0) : 0
+    //
+    // We can then perform the following calculation `s` which counts the number
+    // of segments we need to remove from the end of the data structure:
+    //
+    //   s(p, c) = f(p) - f(c)
+    //
+    // If we treat p = previous size, and c = current size, and given the
+    // properties above, the possible range for s(...) is [0..max(typeof(p))/N]
+    // given that typeof(p) == typeof(c).
+    auto F = [](uint64_t X) {
+      return X ? (X / ElementsPerSegment) +
+                     (X < ElementsPerSegment || X % ElementsPerSegment ? 1 : 0)
+               : 0;
+    };
+    auto PS = F(OldSize);
+    auto CS = F(Size);
+    DCHECK_GE(PS, CS);
+    auto SegmentsToTrim = PS - CS;
+    for (auto I = 0uL; I < SegmentsToTrim; ++I) {
+      // Here we place the current tail segment to the freelist. To do this
+      // appropriately, we need to perform a splice operation on two
+      // bidirectional linked-lists. In particular, we have the current state of
+      // the doubly-linked list of segments:
+      //
+      //   @S@ <- s0 <-> s1 <-> ... <-> sT -> @S@
+      //
       DCHECK_NE(Head, &SentinelSegment);
       DCHECK_NE(Tail, &SentinelSegment);
-      // Put the tail into the Freelist.
-      auto *FreeSegment = Tail;
-      Tail = Tail->Prev;
-      if (Tail == &SentinelSegment)
-        Head = Tail;
-      else
-        Tail->Next = &SentinelSegment;
-
       DCHECK_EQ(Tail->Next, &SentinelSegment);
-      FreeSegment->Next = Freelist;
-      FreeSegment->Prev = &SentinelSegment;
-      if (Freelist != &SentinelSegment)
-        Freelist->Prev = FreeSegment;
-      Freelist = FreeSegment;
+
+      if (Freelist == &SentinelSegment) {
+        // Our two lists at this point are in this configuration:
+        //
+        //   Freelist: (potentially) @S@
+        //   Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
+        //                  ^ Head                ^ Tail
+        //
+        // The end state for us will be this configuration:
+        //
+        //   Freelist: @S@<-sT->@S@
+        //   Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
+        //                  ^ Head          ^ Tail
+        //
+        // The first step for us is to hold a reference to the tail of Mainlist,
+        // which in our notation is represented by sT. We call this our "free
+        // segment" which is the segment we are placing on the Freelist.
+        //
+        //   sF = sT
+        //
+        // Then, we also hold a reference to the "pre-tail" element, which we
+        // call sPT:
+        //
+        //   sPT = pred(sT)
+        //
+        // We want to splice sT into the beginning of the Freelist, which in
+        // an empty Freelist means placing a segment whose predecessor and
+        // successor is the sentinel segment.
+        //
+        // The splice operation then can be performed in the following
+        // algorithm:
+        //
+        //   succ(sPT) = S
+        //   pred(sT) = S
+        //   succ(sT) = Freelist
+        //   Freelist = sT
+        //   Tail = sPT
+        //
+        auto SPT = Tail->Prev;
+        SPT->Next = &SentinelSegment;
+        Tail->Prev = &SentinelSegment;
+        Tail->Next = Freelist;
+        Freelist = Tail;
+        Tail = SPT;
+
+        // Our post-conditions here are:
+        DCHECK_EQ(Tail->Next, &SentinelSegment);
+        DCHECK_EQ(Freelist->Prev, &SentinelSegment);
+      } else {
+        // In the other case, where the Freelist is not empty, we perform the
+        // following transformation instead:
+        //
+        // This transforms the current state:
+        //
+        //   Freelist: @S@<-f0->@S@
+        //                  ^ Freelist
+        //   Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
+        //                  ^ Head                ^ Tail
+        //
+        // Into the following:
+        //
+        //   Freelist: @S@<-sT<->f0->@S@
+        //                  ^ Freelist
+        //   Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
+        //                  ^ Head          ^ Tail
+        //
+        // The algorithm is:
+        //
+        //   sFH = Freelist
+        //   sPT = pred(sT)
+        //   pred(SFH) = sT
+        //   succ(sT) = Freelist
+        //   pred(sT) = S
+        //   succ(sPT) = S
+        //   Tail = sPT
+        //   Freelist = sT
+        //
+        auto SFH = Freelist;
+        auto SPT = Tail->Prev;
+        auto ST = Tail;
+        SFH->Prev = ST;
+        ST->Next = Freelist;
+        ST->Prev = &SentinelSegment;
+        SPT->Next = &SentinelSegment;
+        Tail = SPT;
+        Freelist = ST;
+
+        // Our post-conditions here are:
+        DCHECK_EQ(Tail->Next, &SentinelSegment);
+        DCHECK_EQ(Freelist->Prev, &SentinelSegment);
+        DCHECK_EQ(Freelist->Next->Prev, Freelist);
+      }
     }
+
+    // Now in case we've spliced all the segments in the end, we ensure that the
+    // main list is "empty", or both the head and tail pointing to the sentinel
+    // segment.
+    if (Tail == &SentinelSegment)
+      Head = Tail;
+
+    DCHECK(
+        (Size == 0 && Head == &SentinelSegment && Tail == &SentinelSegment) ||
+        (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
+    DCHECK(
+        (Freelist != &SentinelSegment && Freelist->Prev == &SentinelSegment) ||
+        (Freelist == &SentinelSegment && Tail->Next == &SentinelSegment));
   }
 
   // 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); }
+  Iterator<T> begin() const XRAY_NEVER_INSTRUMENT {
+    return Iterator<T>(Head, 0, Size);
+  }
+  Iterator<T> end() const XRAY_NEVER_INSTRUMENT {
+    return Iterator<T>(Tail, Size, Size);
+  }
+  Iterator<const T> cbegin() const XRAY_NEVER_INSTRUMENT {
+    return Iterator<const T>(Head, 0, Size);
+  }
+  Iterator<const T> cend() const XRAY_NEVER_INSTRUMENT {
+    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 SentinelSegment is defined and has a single
 // address.
 template <class T>
-typename Array<T>::SegmentBase Array<T>::SentinelSegment{
-    &Array<T>::SentinelSegment, &Array<T>::SentinelSegment};
+typename Array<T>::Segment Array<T>::SentinelSegment{
+    &Array<T>::SentinelSegment, &Array<T>::SentinelSegment, {'\0'}};
 
 } // namespace __xray