650 lines · c
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-exception6//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 segments12// backing the segments.13//14//===----------------------------------------------------------------------===//15#ifndef XRAY_SEGMENTED_ARRAY_H16#define XRAY_SEGMENTED_ARRAY_H17 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 25namespace __xray {26 27/// The Array type provides an interface similar to std::vector<...> but does28/// not shrink in size. Once constructed, elements can be appended but cannot be29/// removed. The implementation is heavily dependent on the contract provided by30/// the Allocator type, in that all memory will be released when the Allocator31/// is destroyed. When an Array is destroyed, it will destroy elements in the32/// backing store but will not free the memory.33template <class T> class Array {34 struct Segment {35 Segment *Prev;36 Segment *Next;37 char Data[1];38 };39 40public: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 (kCacheLineSize44 // aligned).45 //46 // - The elements will be accessed through an aligned pointer, dependent on47 // the alignment of T.48 //49 // - Each element is at least two-pointers worth from the beginning of the50 // Segment, aligned properly, and the rest of the elements are accessed51 // 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 within56 // 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 78private: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_INSTRUMENT87 : 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 the102 // 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 the154 // 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-use168 // 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 the174 // list operations using the following notation:175 //176 // - pred(s) is the predecessor (previous node accessor) and succ(s) is177 // the successor (next node accessor).178 //179 // - S is a sentinel segment, which has the following property:180 //181 // pred(S) == succ(S) == S182 //183 // - @ is a loop operator, which can imply pred(s) == s if it appears on184 // 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, which187 // means:188 //189 // succ(sL) == sR && pred(SR) == sL190 //191 // - sL -> sR : implies a unidirectional relation between sL and SR,192 // with the following properties:193 //194 // succ(sL) == sR195 //196 // sL <- sR : implies a unidirectional relation between sR and sL,197 // with the following properties:198 //199 // pred(sR) == sL200 //201 // ===============================202 203 Segment *NewSegment() XRAY_NEVER_INSTRUMENT {204 // We need to handle the case in which enough elements have been trimmed to205 // allow us to re-use segments we've allocated before. For this we look into206 // the Freelist, to see whether we need to actually allocate new blocks or207 // 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 // ^ Freelist213 //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 // ^ FreeSegment219 //220 // Our algorithm preconditions are:221 DCHECK_EQ(Freelist->Prev, &SentinelSegment);222 223 // Then the algorithm we implement is:224 //225 // SFS = Freelist226 // Freelist = succ(Freelist)227 // if (Freelist != S)228 // pred(Freelist) = S229 // succ(SFS) = S230 // pred(SFS) = S231 //232 auto *FreeSegment = Freelist;233 Freelist = Freelist->Next;234 235 // Note that we need to handle the case where Freelist is now pointing to236 // S, which we don't want to be overwriting.237 // TODO: Determine whether the cost of the branch is higher than the cost238 // 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 294public:295 explicit Array(AllocatorType &A) XRAY_NEVER_INSTRUMENT296 : 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 semantics383 // explicitly used, as a work-around to GCC 4.8 not invoking the copy384 // 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 not456 /// 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 by463 // counting how many elements have been trimmed. Given the following:464 //465 // - Each segment has N valid positions, where N > 0466 // - The previous size > current size467 //468 // To compute the number of segments to return, we need to perform the469 // following calculations for the number of segments required given 'x'470 // elements:471 //472 // f(x) = {473 // x == 0 : 0474 // , 0 < x <= N : 1475 // , 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) : 0488 //489 // We can then perform the following calculation `s` which counts the number490 // 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 the495 // 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 this508 // appropriately, we need to perform a splice operation on two509 // bidirectional linked-lists. In particular, we have the current state of510 // 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 ^ Tail524 //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 ^ Tail530 //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 "free533 // segment" which is the segment we are placing on the Freelist.534 //535 // sF = sT536 //537 // Then, we also hold a reference to the "pre-tail" element, which we538 // call sPT:539 //540 // sPT = pred(sT)541 //542 // We want to splice sT into the beginning of the Freelist, which in543 // an empty Freelist means placing a segment whose predecessor and544 // successor is the sentinel segment.545 //546 // The splice operation then can be performed in the following547 // algorithm:548 //549 // succ(sPT) = S550 // pred(sT) = S551 // succ(sT) = Freelist552 // Freelist = sT553 // Tail = sPT554 //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 the567 // following transformation instead:568 //569 // This transforms the current state:570 //571 // Freelist: @S@<-f0->@S@572 // ^ Freelist573 // Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@574 // ^ Head ^ Tail575 //576 // Into the following:577 //578 // Freelist: @S@<-sT<->f0->@S@579 // ^ Freelist580 // Mainlist: @S@<-s0<->s1<->...<->sPT->@S@581 // ^ Head ^ Tail582 //583 // The algorithm is:584 //585 // sFH = Freelist586 // sPT = pred(sT)587 // pred(SFH) = sT588 // succ(sT) = Freelist589 // pred(sT) = S590 // succ(sPT) = S591 // Tail = sPT592 // Freelist = sT593 //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 the612 // main list is "empty", or both the head and tail pointing to the sentinel613 // 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 can641// ensure that storage for the SentinelSegment is defined and has a single642// address.643template <class T>644typename Array<T>::Segment Array<T>::SentinelSegment{645 &Array<T>::SentinelSegment, &Array<T>::SentinelSegment, {'\0'}};646 647} // namespace __xray648 649#endif // XRAY_SEGMENTED_ARRAY_H650