contrib/compiler-rt/lib/xray/xray_segmented_array.h

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