compiler-rt/lib/xray/xray_segmented_array.h

   1 //===-- xray_segmented_array.h ---------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file is a part of XRay, a dynamic runtime instrumentation system.
  10 //
  11 // Defines the implementation of a segmented array, with fixed-size segments
  12 // backing the segments.
  13 //
  14 //===----------------------------------------------------------------------===//
  15 #ifndef XRAY_SEGMENTED_ARRAY_H
  16 #define XRAY_SEGMENTED_ARRAY_H
  17
  18 #include "sanitizer_common/sanitizer_allocator.h"
  19 #include "xray_allocator.h"
  20 #include "xray_utils.h"
  21 #include <cassert>
  22 #include <type_traits>
  23 #include <utility>
  24
  25 namespace __xray {
  26
  27 /// The Array type provides an interface similar to std::vector<...> but does
  28 /// not shrink in size. Once constructed, elements can be appended but cannot be
  29 /// removed. The implementation is heavily dependent on the contract provided by
  30 /// the Allocator type, in that all memory will be released when the Allocator
  31 /// is destroyed. When an Array is destroyed, it will destroy elements in the
  32 /// backing store but will not free the memory.
  33 template <class T> class Array {
  34   struct Segment {
  35     Segment *Prev;
  36     Segment *Next;
  37     char Data[1];
  38   };
  39
  40 public:
  41   // Each segment of the array will be laid out with the following assumptions:
  42   //
  43   //   - Each segment will be on a cache-line address boundary (kCacheLineSize
  44   //     aligned).
  45   //
  46   //   - The elements will be accessed through an aligned pointer, dependent on
  47   //     the alignment of T.
  48   //
  49   //   - Each element is at least two-pointers worth from the beginning of the
  50   //     Segment, aligned properly, and the rest of the elements are accessed
  51   //     through appropriate alignment.
  52   //
  53   // We then compute the size of the segment to follow this logic:
  54   //
  55   //   - Compute the number of elements that can fit within
  56   //     kCacheLineSize-multiple segments, minus the size of two pointers.
  57   //
  58   //   - Request cacheline-multiple sized elements from the allocator.
  59   static constexpr uint64_t AlignedElementStorageSize = sizeof(T);
  60
  61   static constexpr uint64_t SegmentControlBlockSize = sizeof(Segment *) * 2;
  62
  63   static constexpr uint64_t SegmentSize = nearest_boundary(
  64       SegmentControlBlockSize + next_pow2(sizeof(T)), kCacheLineSize);
  65
  66   using AllocatorType = Allocator<SegmentSize>;
  67
  68   static constexpr uint64_t ElementsPerSegment =
  69       (SegmentSize - SegmentControlBlockSize) / next_pow2(sizeof(T));
  70
  71   static_assert(ElementsPerSegment > 0,
  72                 "Must have at least 1 element per segment.");
  73
  74   static Segment SentinelSegment;
  75
  76   using size_type = uint64_t;
  77
  78 private:
  79   // This Iterator models a BidirectionalIterator.
  80   template <class U> class Iterator {
  81     Segment *S = &SentinelSegment;
  82     uint64_t Offset = 0;
  83     uint64_t Size = 0;
  84
  85   public:
  86     Iterator(Segment *IS, uint64_t Off, uint64_t S) XRAY_NEVER_INSTRUMENT
  87         : S(IS),
  88           Offset(Off),
  89           Size(S) {}
  90     Iterator(const Iterator &) NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
  91     Iterator() NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
  92     Iterator(Iterator &&) NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
  93     Iterator &operator=(const Iterator &) XRAY_NEVER_INSTRUMENT = default;
  94     Iterator &operator=(Iterator &&) XRAY_NEVER_INSTRUMENT = default;
  95     ~Iterator() XRAY_NEVER_INSTRUMENT = default;
  96
  97     Iterator &operator++() XRAY_NEVER_INSTRUMENT {
  98       if (++Offset % ElementsPerSegment || Offset == Size)
  99         return *this;
 100
 101       // At this point, we know that Offset % N == 0, so we must advance the
 102       // segment pointer.
 103       DCHECK_EQ(Offset % ElementsPerSegment, 0);
 104       DCHECK_NE(Offset, Size);
 105       DCHECK_NE(S, &SentinelSegment);
 106       DCHECK_NE(S->Next, &SentinelSegment);
 107       S = S->Next;
 108       DCHECK_NE(S, &SentinelSegment);
 109       return *this;
 110     }
 111
 112     Iterator &operator--() XRAY_NEVER_INSTRUMENT {
 113       DCHECK_NE(S, &SentinelSegment);
 114       DCHECK_GT(Offset, 0);
 115
 116       auto PreviousOffset = Offset--;
 117       if (PreviousOffset != Size && PreviousOffset % ElementsPerSegment == 0) {
 118         DCHECK_NE(S->Prev, &SentinelSegment);
 119         S = S->Prev;
 120       }
 121
 122       return *this;
 123     }
 124
 125     Iterator operator++(int) XRAY_NEVER_INSTRUMENT {
 126       Iterator Copy(*this);
 127       ++(*this);
 128       return Copy;
 129     }
 130
 131     Iterator operator--(int) XRAY_NEVER_INSTRUMENT {
 132       Iterator Copy(*this);
 133       --(*this);
 134       return Copy;
 135     }
 136
 137     template <class V, class W>
 138     friend bool operator==(const Iterator<V> &L,
 139                            const Iterator<W> &R) XRAY_NEVER_INSTRUMENT {
 140       return L.S == R.S && L.Offset == R.Offset;
 141     }
 142
 143     template <class V, class W>
 144     friend bool operator!=(const Iterator<V> &L,
 145                            const Iterator<W> &R) XRAY_NEVER_INSTRUMENT {
 146       return !(L == R);
 147     }
 148
 149     U &operator*() const XRAY_NEVER_INSTRUMENT {
 150       DCHECK_NE(S, &SentinelSegment);
 151       auto RelOff = Offset % ElementsPerSegment;
 152
 153       // We need to compute the character-aligned pointer, offset from the
 154       // segment's Data location to get the element in the position of Offset.
 155       auto Base = &S->Data;
 156       auto AlignedOffset = Base + (RelOff * AlignedElementStorageSize);
 157       return *reinterpret_cast<U *>(AlignedOffset);
 158     }
 159
 160     U *operator->() const XRAY_NEVER_INSTRUMENT { return &(**this); }
 161   };
 162
 163   AllocatorType *Alloc;
 164   Segment *Head;
 165   Segment *Tail;
 166
 167   // Here we keep track of segments in the freelist, to allow us to re-use
 168   // segments when elements are trimmed off the end.
 169   Segment *Freelist;
 170   uint64_t Size;
 171
 172   // ===============================
 173   // In the following implementation, we work through the algorithms and the
 174   // list operations using the following notation:
 175   //
 176   //   - pred(s) is the predecessor (previous node accessor) and succ(s) is
 177   //     the successor (next node accessor).
 178   //
 179   //   - S is a sentinel segment, which has the following property:
 180   //
 181   //         pred(S) == succ(S) == S
 182   //
 183   //   - @ is a loop operator, which can imply pred(s) == s if it appears on
 184   //     the left of s, or succ(s) == S if it appears on the right of s.
 185   //
 186   //   - sL <-> sR : means a bidirectional relation between sL and sR, which
 187   //     means:
 188   //
 189   //         succ(sL) == sR && pred(SR) == sL
 190   //
 191   //   - sL -> sR : implies a unidirectional relation between sL and SR,
 192   //     with the following properties:
 193   //
 194   //         succ(sL) == sR
 195   //
 196   //     sL <- sR : implies a unidirectional relation between sR and sL,
 197   //     with the following properties:
 198   //
 199   //         pred(sR) == sL
 200   //
 201   // ===============================
 202
 203   Segment *NewSegment() XRAY_NEVER_INSTRUMENT {
 204     // We need to handle the case in which enough elements have been trimmed to
 205     // allow us to re-use segments we've allocated before. For this we look into
 206     // the Freelist, to see whether we need to actually allocate new blocks or
 207     // just re-use blocks we've already seen before.
 208     if (Freelist != &SentinelSegment) {
 209       // The current state of lists resemble something like this at this point:
 210       //
 211       //   Freelist: @S@<-f0->...<->fN->@S@
 212       //                  ^ Freelist
 213       //
 214       // We want to perform a splice of `f0` from Freelist to a temporary list,
 215       // which looks like:
 216       //
 217       //   Templist: @S@<-f0->@S@
 218       //                  ^ FreeSegment
 219       //
 220       // Our algorithm preconditions are:
 221       DCHECK_EQ(Freelist->Prev, &SentinelSegment);
 222
 223       // Then the algorithm we implement is:
 224       //
 225       //   SFS = Freelist
 226       //   Freelist = succ(Freelist)
 227       //   if (Freelist != S)
 228       //     pred(Freelist) = S
 229       //   succ(SFS) = S
 230       //   pred(SFS) = S
 231       //
 232       auto *FreeSegment = Freelist;
 233       Freelist = Freelist->Next;
 234
 235       // Note that we need to handle the case where Freelist is now pointing to
 236       // S, which we don't want to be overwriting.
 237       // TODO: Determine whether the cost of the branch is higher than the cost
 238       // of the blind assignment.
 239       if (Freelist != &SentinelSegment)
 240         Freelist->Prev = &SentinelSegment;
 241
 242       FreeSegment->Next = &SentinelSegment;
 243       FreeSegment->Prev = &SentinelSegment;
 244
 245       // Our postconditions are:
 246       DCHECK_EQ(Freelist->Prev, &SentinelSegment);
 247       DCHECK_NE(FreeSegment, &SentinelSegment);
 248       return FreeSegment;
 249     }
 250
 251     auto SegmentBlock = Alloc->Allocate();
 252     if (SegmentBlock.Data == nullptr)
 253       return nullptr;
 254
 255     // Placement-new the Segment element at the beginning of the SegmentBlock.
 256     new (SegmentBlock.Data) Segment{&SentinelSegment, &SentinelSegment, {0}};
 257     auto SB = reinterpret_cast<Segment *>(SegmentBlock.Data);
 258     return SB;
 259   }
 260
 261   Segment *InitHeadAndTail() XRAY_NEVER_INSTRUMENT {
 262     DCHECK_EQ(Head, &SentinelSegment);
 263     DCHECK_EQ(Tail, &SentinelSegment);
 264     auto S = NewSegment();
 265     if (S == nullptr)
 266       return nullptr;
 267     DCHECK_EQ(S->Next, &SentinelSegment);
 268     DCHECK_EQ(S->Prev, &SentinelSegment);
 269     DCHECK_NE(S, &SentinelSegment);
 270     Head = S;
 271     Tail = S;
 272     DCHECK_EQ(Head, Tail);
 273     DCHECK_EQ(Tail->Next, &SentinelSegment);
 274     DCHECK_EQ(Tail->Prev, &SentinelSegment);
 275     return S;
 276   }
 277
 278   Segment *AppendNewSegment() XRAY_NEVER_INSTRUMENT {
 279     auto S = NewSegment();
 280     if (S == nullptr)
 281       return nullptr;
 282     DCHECK_NE(Tail, &SentinelSegment);
 283     DCHECK_EQ(Tail->Next, &SentinelSegment);
 284     DCHECK_EQ(S->Prev, &SentinelSegment);
 285     DCHECK_EQ(S->Next, &SentinelSegment);
 286     S->Prev = Tail;
 287     Tail->Next = S;
 288     Tail = S;
 289     DCHECK_EQ(S, S->Prev->Next);
 290     DCHECK_EQ(Tail->Next, &SentinelSegment);
 291     return S;
 292   }
 293
 294 public:
 295   explicit Array(AllocatorType &A) XRAY_NEVER_INSTRUMENT
 296       : Alloc(&A),
 297         Head(&SentinelSegment),
 298         Tail(&SentinelSegment),
 299         Freelist(&SentinelSegment),
 300         Size(0) {}
 301
 302   Array() XRAY_NEVER_INSTRUMENT : Alloc(nullptr),
 303                                   Head(&SentinelSegment),
 304                                   Tail(&SentinelSegment),
 305                                   Freelist(&SentinelSegment),
 306                                   Size(0) {}
 307
 308   Array(const Array &) = delete;
 309   Array &operator=(const Array &) = delete;
 310
 311   Array(Array &&O) XRAY_NEVER_INSTRUMENT : Alloc(O.Alloc),
 312                                            Head(O.Head),
 313                                            Tail(O.Tail),
 314                                            Freelist(O.Freelist),
 315                                            Size(O.Size) {
 316     O.Alloc = nullptr;
 317     O.Head = &SentinelSegment;
 318     O.Tail = &SentinelSegment;
 319     O.Size = 0;
 320     O.Freelist = &SentinelSegment;
 321   }
 322
 323   Array &operator=(Array &&O) XRAY_NEVER_INSTRUMENT {
 324     Alloc = O.Alloc;
 325     O.Alloc = nullptr;
 326     Head = O.Head;
 327     O.Head = &SentinelSegment;
 328     Tail = O.Tail;
 329     O.Tail = &SentinelSegment;
 330     Freelist = O.Freelist;
 331     O.Freelist = &SentinelSegment;
 332     Size = O.Size;
 333     O.Size = 0;
 334     return *this;
 335   }
 336
 337   ~Array() XRAY_NEVER_INSTRUMENT {
 338     for (auto &E : *this)
 339       (&E)->~T();
 340   }
 341
 342   bool empty() const XRAY_NEVER_INSTRUMENT { return Size == 0; }
 343
 344   AllocatorType &allocator() const XRAY_NEVER_INSTRUMENT {
 345     DCHECK_NE(Alloc, nullptr);
 346     return *Alloc;
 347   }
 348
 349   uint64_t size() const XRAY_NEVER_INSTRUMENT { return Size; }
 350
 351   template <class... Args>
 352   T *AppendEmplace(Args &&... args) XRAY_NEVER_INSTRUMENT {
 353     DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) ||
 354            (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
 355     if (UNLIKELY(Head == &SentinelSegment)) {
 356       auto R = InitHeadAndTail();
 357       if (R == nullptr)
 358         return nullptr;
 359     }
 360
 361     DCHECK_NE(Head, &SentinelSegment);
 362     DCHECK_NE(Tail, &SentinelSegment);
 363
 364     auto Offset = Size % ElementsPerSegment;
 365     if (UNLIKELY(Size != 0 && Offset == 0))
 366       if (AppendNewSegment() == nullptr)
 367         return nullptr;
 368
 369     DCHECK_NE(Tail, &SentinelSegment);
 370     auto Base = &Tail->Data;
 371     auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
 372     DCHECK_LE(AlignedOffset + sizeof(T),
 373               reinterpret_cast<unsigned char *>(Base) + SegmentSize);
 374
 375     // In-place construct at Position.
 376     new (AlignedOffset) T{std::forward<Args>(args)...};
 377     ++Size;
 378     return reinterpret_cast<T *>(AlignedOffset);
 379   }
 380
 381   T *Append(const T &E) XRAY_NEVER_INSTRUMENT {
 382     // FIXME: This is a duplication of AppenEmplace with the copy semantics
 383     // explicitly used, as a work-around to GCC 4.8 not invoking the copy
 384     // constructor with the placement new with braced-init syntax.
 385     DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) ||
 386            (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
 387     if (UNLIKELY(Head == &SentinelSegment)) {
 388       auto R = InitHeadAndTail();
 389       if (R == nullptr)
 390         return nullptr;
 391     }
 392
 393     DCHECK_NE(Head, &SentinelSegment);
 394     DCHECK_NE(Tail, &SentinelSegment);
 395
 396     auto Offset = Size % ElementsPerSegment;
 397     if (UNLIKELY(Size != 0 && Offset == 0))
 398       if (AppendNewSegment() == nullptr)
 399         return nullptr;
 400
 401     DCHECK_NE(Tail, &SentinelSegment);
 402     auto Base = &Tail->Data;
 403     auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
 404     DCHECK_LE(AlignedOffset + sizeof(T),
 405               reinterpret_cast<unsigned char *>(Tail) + SegmentSize);
 406
 407     // In-place construct at Position.
 408     new (AlignedOffset) T(E);
 409     ++Size;
 410     return reinterpret_cast<T *>(AlignedOffset);
 411   }
 412
 413   T &operator[](uint64_t Offset) const XRAY_NEVER_INSTRUMENT {
 414     DCHECK_LE(Offset, Size);
 415     // We need to traverse the array enough times to find the element at Offset.
 416     auto S = Head;
 417     while (Offset >= ElementsPerSegment) {
 418       S = S->Next;
 419       Offset -= ElementsPerSegment;
 420       DCHECK_NE(S, &SentinelSegment);
 421     }
 422     auto Base = &S->Data;
 423     auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
 424     auto Position = reinterpret_cast<T *>(AlignedOffset);
 425     return *reinterpret_cast<T *>(Position);
 426   }
 427
 428   T &front() const XRAY_NEVER_INSTRUMENT {
 429     DCHECK_NE(Head, &SentinelSegment);
 430     DCHECK_NE(Size, 0u);
 431     return *begin();
 432   }
 433
 434   T &back() const XRAY_NEVER_INSTRUMENT {
 435     DCHECK_NE(Tail, &SentinelSegment);
 436     DCHECK_NE(Size, 0u);
 437     auto It = end();
 438     --It;
 439     return *It;
 440   }
 441
 442   template <class Predicate>
 443   T *find_element(Predicate P) const XRAY_NEVER_INSTRUMENT {
 444     if (empty())
 445       return nullptr;
 446
 447     auto E = end();
 448     for (auto I = begin(); I != E; ++I)
 449       if (P(*I))
 450         return &(*I);
 451
 452     return nullptr;
 453   }
 454
 455   /// Remove N Elements from the end. This leaves the blocks behind, and not
 456   /// require allocation of new blocks for new elements added after trimming.
 457   void trim(uint64_t Elements) XRAY_NEVER_INSTRUMENT {
 458     auto OldSize = Size;
 459     Elements = Elements > Size ? Size : Elements;
 460     Size -= Elements;
 461
 462     // We compute the number of segments we're going to return from the tail by
 463     // counting how many elements have been trimmed. Given the following:
 464     //
 465     // - Each segment has N valid positions, where N > 0
 466     // - The previous size > current size
 467     //
 468     // To compute the number of segments to return, we need to perform the
 469     // following calculations for the number of segments required given 'x'
 470     // elements:
 471     //
 472     //   f(x) = {
 473     //            x == 0          : 0
 474     //          , 0 < x <= N      : 1
 475     //          , N < x <= max    : x / N + (x % N ? 1 : 0)
 476     //          }
 477     //
 478     // We can simplify this down to:
 479     //
 480     //   f(x) = {
 481     //            x == 0          : 0,
 482     //          , 0 < x <= max    : x / N + (x < N || x % N ? 1 : 0)
 483     //          }
 484     //
 485     // And further down to:
 486     //
 487     //   f(x) = x ? x / N + (x < N || x % N ? 1 : 0) : 0
 488     //
 489     // We can then perform the following calculation `s` which counts the number
 490     // of segments we need to remove from the end of the data structure:
 491     //
 492     //   s(p, c) = f(p) - f(c)
 493     //
 494     // If we treat p = previous size, and c = current size, and given the
 495     // properties above, the possible range for s(...) is [0..max(typeof(p))/N]
 496     // given that typeof(p) == typeof(c).
 497     auto F = [](uint64_t X) {
 498       return X ? (X / ElementsPerSegment) +
 499                      (X < ElementsPerSegment || X % ElementsPerSegment ? 1 : 0)
 500                : 0;
 501     };
 502     auto PS = F(OldSize);
 503     auto CS = F(Size);
 504     DCHECK_GE(PS, CS);
 505     auto SegmentsToTrim = PS - CS;
 506     for (auto I = 0uL; I < SegmentsToTrim; ++I) {
 507       // Here we place the current tail segment to the freelist. To do this
 508       // appropriately, we need to perform a splice operation on two
 509       // bidirectional linked-lists. In particular, we have the current state of
 510       // the doubly-linked list of segments:
 511       //
 512       //   @S@ <- s0 <-> s1 <-> ... <-> sT -> @S@
 513       //
 514       DCHECK_NE(Head, &SentinelSegment);
 515       DCHECK_NE(Tail, &SentinelSegment);
 516       DCHECK_EQ(Tail->Next, &SentinelSegment);
 517
 518       if (Freelist == &SentinelSegment) {
 519         // Our two lists at this point are in this configuration:
 520         //
 521         //   Freelist: (potentially) @S@
 522         //   Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
 523         //                  ^ Head                ^ Tail
 524         //
 525         // The end state for us will be this configuration:
 526         //
 527         //   Freelist: @S@<-sT->@S@
 528         //   Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
 529         //                  ^ Head          ^ Tail
 530         //
 531         // The first step for us is to hold a reference to the tail of Mainlist,
 532         // which in our notation is represented by sT. We call this our "free
 533         // segment" which is the segment we are placing on the Freelist.
 534         //
 535         //   sF = sT
 536         //
 537         // Then, we also hold a reference to the "pre-tail" element, which we
 538         // call sPT:
 539         //
 540         //   sPT = pred(sT)
 541         //
 542         // We want to splice sT into the beginning of the Freelist, which in
 543         // an empty Freelist means placing a segment whose predecessor and
 544         // successor is the sentinel segment.
 545         //
 546         // The splice operation then can be performed in the following
 547         // algorithm:
 548         //
 549         //   succ(sPT) = S
 550         //   pred(sT) = S
 551         //   succ(sT) = Freelist
 552         //   Freelist = sT
 553         //   Tail = sPT
 554         //
 555         auto SPT = Tail->Prev;
 556         SPT->Next = &SentinelSegment;
 557         Tail->Prev = &SentinelSegment;
 558         Tail->Next = Freelist;
 559         Freelist = Tail;
 560         Tail = SPT;
 561
 562         // Our post-conditions here are:
 563         DCHECK_EQ(Tail->Next, &SentinelSegment);
 564         DCHECK_EQ(Freelist->Prev, &SentinelSegment);
 565       } else {
 566         // In the other case, where the Freelist is not empty, we perform the
 567         // following transformation instead:
 568         //
 569         // This transforms the current state:
 570         //
 571         //   Freelist: @S@<-f0->@S@
 572         //                  ^ Freelist
 573         //   Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
 574         //                  ^ Head                ^ Tail
 575         //
 576         // Into the following:
 577         //
 578         //   Freelist: @S@<-sT<->f0->@S@
 579         //                  ^ Freelist
 580         //   Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
 581         //                  ^ Head          ^ Tail
 582         //
 583         // The algorithm is:
 584         //
 585         //   sFH = Freelist
 586         //   sPT = pred(sT)
 587         //   pred(SFH) = sT
 588         //   succ(sT) = Freelist
 589         //   pred(sT) = S
 590         //   succ(sPT) = S
 591         //   Tail = sPT
 592         //   Freelist = sT
 593         //
 594         auto SFH = Freelist;
 595         auto SPT = Tail->Prev;
 596         auto ST = Tail;
 597         SFH->Prev = ST;
 598         ST->Next = Freelist;
 599         ST->Prev = &SentinelSegment;
 600         SPT->Next = &SentinelSegment;
 601         Tail = SPT;
 602         Freelist = ST;
 603
 604         // Our post-conditions here are:
 605         DCHECK_EQ(Tail->Next, &SentinelSegment);
 606         DCHECK_EQ(Freelist->Prev, &SentinelSegment);
 607         DCHECK_EQ(Freelist->Next->Prev, Freelist);
 608       }
 609     }
 610
 611     // Now in case we've spliced all the segments in the end, we ensure that the
 612     // main list is "empty", or both the head and tail pointing to the sentinel
 613     // segment.
 614     if (Tail == &SentinelSegment)
 615       Head = Tail;
 616
 617     DCHECK(
 618         (Size == 0 && Head == &SentinelSegment && Tail == &SentinelSegment) ||
 619         (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
 620     DCHECK(
 621         (Freelist != &SentinelSegment && Freelist->Prev == &SentinelSegment) ||
 622         (Freelist == &SentinelSegment && Tail->Next == &SentinelSegment));
 623   }
 624
 625   // Provide iterators.
 626   Iterator<T> begin() const XRAY_NEVER_INSTRUMENT {
 627     return Iterator<T>(Head, 0, Size);
 628   }
 629   Iterator<T> end() const XRAY_NEVER_INSTRUMENT {
 630     return Iterator<T>(Tail, Size, Size);
 631   }
 632   Iterator<const T> cbegin() const XRAY_NEVER_INSTRUMENT {
 633     return Iterator<const T>(Head, 0, Size);
 634   }
 635   Iterator<const T> cend() const XRAY_NEVER_INSTRUMENT {
 636     return Iterator<const T>(Tail, Size, Size);
 637   }
 638 };
 639
 640 // We need to have this storage definition out-of-line so that the compiler can
 641 // ensure that storage for the SentinelSegment is defined and has a single
 642 // address.
 643 template <class T>
 644 typename Array<T>::Segment Array<T>::SentinelSegment{
 645     &Array<T>::SentinelSegment, &Array<T>::SentinelSegment, {'\0'}};
 646
 647 } // namespace __xray
 648
 649 #endif // XRAY_SEGMENTED_ARRAY_H