1 //===-- xray_segmented_array.h ---------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file is a part of XRay, a dynamic runtime instrumentation system.
11 // Defines the implementation of a segmented array, with fixed-size segments
12 // backing the segments.
14 //===----------------------------------------------------------------------===//
15 #ifndef XRAY_SEGMENTED_ARRAY_H
16 #define XRAY_SEGMENTED_ARRAY_H
18 #include "sanitizer_common/sanitizer_allocator.h"
19 #include "xray_allocator.h"
20 #include "xray_utils.h"
22 #include <type_traits>
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
{
41 // Each segment of the array will be laid out with the following assumptions:
43 // - Each segment will be on a cache-line address boundary (kCacheLineSize
46 // - The elements will be accessed through an aligned pointer, dependent on
47 // the alignment of T.
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.
53 // We then compute the size of the segment to follow this logic:
55 // - Compute the number of elements that can fit within
56 // kCacheLineSize-multiple segments, minus the size of two pointers.
58 // - Request cacheline-multiple sized elements from the allocator.
59 static constexpr uint64_t AlignedElementStorageSize
=
60 sizeof(typename
std::aligned_storage
<sizeof(T
), alignof(T
)>::type
);
62 static constexpr uint64_t SegmentControlBlockSize
= sizeof(Segment
*) * 2;
64 static constexpr uint64_t SegmentSize
= nearest_boundary(
65 SegmentControlBlockSize
+ next_pow2(sizeof(T
)), kCacheLineSize
);
67 using AllocatorType
= Allocator
<SegmentSize
>;
69 static constexpr uint64_t ElementsPerSegment
=
70 (SegmentSize
- SegmentControlBlockSize
) / next_pow2(sizeof(T
));
72 static_assert(ElementsPerSegment
> 0,
73 "Must have at least 1 element per segment.");
75 static Segment SentinelSegment
;
77 using size_type
= uint64_t;
80 // This Iterator models a BidirectionalIterator.
81 template <class U
> class Iterator
{
82 Segment
*S
= &SentinelSegment
;
87 Iterator(Segment
*IS
, uint64_t Off
, uint64_t S
) XRAY_NEVER_INSTRUMENT
91 Iterator(const Iterator
&) NOEXCEPT XRAY_NEVER_INSTRUMENT
= default;
92 Iterator() NOEXCEPT XRAY_NEVER_INSTRUMENT
= default;
93 Iterator(Iterator
&&) NOEXCEPT XRAY_NEVER_INSTRUMENT
= default;
94 Iterator
&operator=(const Iterator
&) XRAY_NEVER_INSTRUMENT
= default;
95 Iterator
&operator=(Iterator
&&) XRAY_NEVER_INSTRUMENT
= default;
96 ~Iterator() XRAY_NEVER_INSTRUMENT
= default;
98 Iterator
&operator++() XRAY_NEVER_INSTRUMENT
{
99 if (++Offset
% ElementsPerSegment
|| Offset
== Size
)
102 // At this point, we know that Offset % N == 0, so we must advance the
104 DCHECK_EQ(Offset
% ElementsPerSegment
, 0);
105 DCHECK_NE(Offset
, Size
);
106 DCHECK_NE(S
, &SentinelSegment
);
107 DCHECK_NE(S
->Next
, &SentinelSegment
);
109 DCHECK_NE(S
, &SentinelSegment
);
113 Iterator
&operator--() XRAY_NEVER_INSTRUMENT
{
114 DCHECK_NE(S
, &SentinelSegment
);
115 DCHECK_GT(Offset
, 0);
117 auto PreviousOffset
= Offset
--;
118 if (PreviousOffset
!= Size
&& PreviousOffset
% ElementsPerSegment
== 0) {
119 DCHECK_NE(S
->Prev
, &SentinelSegment
);
126 Iterator
operator++(int) XRAY_NEVER_INSTRUMENT
{
127 Iterator
Copy(*this);
132 Iterator
operator--(int) XRAY_NEVER_INSTRUMENT
{
133 Iterator
Copy(*this);
138 template <class V
, class W
>
139 friend bool operator==(const Iterator
<V
> &L
,
140 const Iterator
<W
> &R
) XRAY_NEVER_INSTRUMENT
{
141 return L
.S
== R
.S
&& L
.Offset
== R
.Offset
;
144 template <class V
, class W
>
145 friend bool operator!=(const Iterator
<V
> &L
,
146 const Iterator
<W
> &R
) XRAY_NEVER_INSTRUMENT
{
150 U
&operator*() const XRAY_NEVER_INSTRUMENT
{
151 DCHECK_NE(S
, &SentinelSegment
);
152 auto RelOff
= Offset
% ElementsPerSegment
;
154 // We need to compute the character-aligned pointer, offset from the
155 // segment's Data location to get the element in the position of Offset.
156 auto Base
= &S
->Data
;
157 auto AlignedOffset
= Base
+ (RelOff
* AlignedElementStorageSize
);
158 return *reinterpret_cast<U
*>(AlignedOffset
);
161 U
*operator->() const XRAY_NEVER_INSTRUMENT
{ return &(**this); }
164 AllocatorType
*Alloc
;
168 // Here we keep track of segments in the freelist, to allow us to re-use
169 // segments when elements are trimmed off the end.
173 // ===============================
174 // In the following implementation, we work through the algorithms and the
175 // list operations using the following notation:
177 // - pred(s) is the predecessor (previous node accessor) and succ(s) is
178 // the successor (next node accessor).
180 // - S is a sentinel segment, which has the following property:
182 // pred(S) == succ(S) == S
184 // - @ is a loop operator, which can imply pred(s) == s if it appears on
185 // the left of s, or succ(s) == S if it appears on the right of s.
187 // - sL <-> sR : means a bidirectional relation between sL and sR, which
190 // succ(sL) == sR && pred(SR) == sL
192 // - sL -> sR : implies a unidirectional relation between sL and SR,
193 // with the following properties:
197 // sL <- sR : implies a unidirectional relation between sR and sL,
198 // with the following properties:
202 // ===============================
204 Segment
*NewSegment() XRAY_NEVER_INSTRUMENT
{
205 // We need to handle the case in which enough elements have been trimmed to
206 // allow us to re-use segments we've allocated before. For this we look into
207 // the Freelist, to see whether we need to actually allocate new blocks or
208 // just re-use blocks we've already seen before.
209 if (Freelist
!= &SentinelSegment
) {
210 // The current state of lists resemble something like this at this point:
212 // Freelist: @S@<-f0->...<->fN->@S@
215 // We want to perform a splice of `f0` from Freelist to a temporary list,
218 // Templist: @S@<-f0->@S@
221 // Our algorithm preconditions are:
222 DCHECK_EQ(Freelist
->Prev
, &SentinelSegment
);
224 // Then the algorithm we implement is:
227 // Freelist = succ(Freelist)
228 // if (Freelist != S)
229 // pred(Freelist) = S
233 auto *FreeSegment
= Freelist
;
234 Freelist
= Freelist
->Next
;
236 // Note that we need to handle the case where Freelist is now pointing to
237 // S, which we don't want to be overwriting.
238 // TODO: Determine whether the cost of the branch is higher than the cost
239 // of the blind assignment.
240 if (Freelist
!= &SentinelSegment
)
241 Freelist
->Prev
= &SentinelSegment
;
243 FreeSegment
->Next
= &SentinelSegment
;
244 FreeSegment
->Prev
= &SentinelSegment
;
246 // Our postconditions are:
247 DCHECK_EQ(Freelist
->Prev
, &SentinelSegment
);
248 DCHECK_NE(FreeSegment
, &SentinelSegment
);
252 auto SegmentBlock
= Alloc
->Allocate();
253 if (SegmentBlock
.Data
== nullptr)
256 // Placement-new the Segment element at the beginning of the SegmentBlock.
257 new (SegmentBlock
.Data
) Segment
{&SentinelSegment
, &SentinelSegment
, {0}};
258 auto SB
= reinterpret_cast<Segment
*>(SegmentBlock
.Data
);
262 Segment
*InitHeadAndTail() XRAY_NEVER_INSTRUMENT
{
263 DCHECK_EQ(Head
, &SentinelSegment
);
264 DCHECK_EQ(Tail
, &SentinelSegment
);
265 auto S
= NewSegment();
268 DCHECK_EQ(S
->Next
, &SentinelSegment
);
269 DCHECK_EQ(S
->Prev
, &SentinelSegment
);
270 DCHECK_NE(S
, &SentinelSegment
);
273 DCHECK_EQ(Head
, Tail
);
274 DCHECK_EQ(Tail
->Next
, &SentinelSegment
);
275 DCHECK_EQ(Tail
->Prev
, &SentinelSegment
);
279 Segment
*AppendNewSegment() XRAY_NEVER_INSTRUMENT
{
280 auto S
= NewSegment();
283 DCHECK_NE(Tail
, &SentinelSegment
);
284 DCHECK_EQ(Tail
->Next
, &SentinelSegment
);
285 DCHECK_EQ(S
->Prev
, &SentinelSegment
);
286 DCHECK_EQ(S
->Next
, &SentinelSegment
);
290 DCHECK_EQ(S
, S
->Prev
->Next
);
291 DCHECK_EQ(Tail
->Next
, &SentinelSegment
);
296 explicit Array(AllocatorType
&A
) XRAY_NEVER_INSTRUMENT
298 Head(&SentinelSegment
),
299 Tail(&SentinelSegment
),
300 Freelist(&SentinelSegment
),
303 Array() XRAY_NEVER_INSTRUMENT
: Alloc(nullptr),
304 Head(&SentinelSegment
),
305 Tail(&SentinelSegment
),
306 Freelist(&SentinelSegment
),
309 Array(const Array
&) = delete;
310 Array
&operator=(const Array
&) = delete;
312 Array(Array
&&O
) XRAY_NEVER_INSTRUMENT
: Alloc(O
.Alloc
),
315 Freelist(O
.Freelist
),
318 O
.Head
= &SentinelSegment
;
319 O
.Tail
= &SentinelSegment
;
321 O
.Freelist
= &SentinelSegment
;
324 Array
&operator=(Array
&&O
) XRAY_NEVER_INSTRUMENT
{
328 O
.Head
= &SentinelSegment
;
330 O
.Tail
= &SentinelSegment
;
331 Freelist
= O
.Freelist
;
332 O
.Freelist
= &SentinelSegment
;
338 ~Array() XRAY_NEVER_INSTRUMENT
{
339 for (auto &E
: *this)
343 bool empty() const XRAY_NEVER_INSTRUMENT
{ return Size
== 0; }
345 AllocatorType
&allocator() const XRAY_NEVER_INSTRUMENT
{
346 DCHECK_NE(Alloc
, nullptr);
350 uint64_t size() const XRAY_NEVER_INSTRUMENT
{ return Size
; }
352 template <class... Args
>
353 T
*AppendEmplace(Args
&&... args
) XRAY_NEVER_INSTRUMENT
{
354 DCHECK((Size
== 0 && Head
== &SentinelSegment
&& Head
== Tail
) ||
355 (Size
!= 0 && Head
!= &SentinelSegment
&& Tail
!= &SentinelSegment
));
356 if (UNLIKELY(Head
== &SentinelSegment
)) {
357 auto R
= InitHeadAndTail();
362 DCHECK_NE(Head
, &SentinelSegment
);
363 DCHECK_NE(Tail
, &SentinelSegment
);
365 auto Offset
= Size
% ElementsPerSegment
;
366 if (UNLIKELY(Size
!= 0 && Offset
== 0))
367 if (AppendNewSegment() == nullptr)
370 DCHECK_NE(Tail
, &SentinelSegment
);
371 auto Base
= &Tail
->Data
;
372 auto AlignedOffset
= Base
+ (Offset
* AlignedElementStorageSize
);
373 DCHECK_LE(AlignedOffset
+ sizeof(T
),
374 reinterpret_cast<unsigned char *>(Base
) + SegmentSize
);
376 // In-place construct at Position.
377 new (AlignedOffset
) T
{std::forward
<Args
>(args
)...};
379 return reinterpret_cast<T
*>(AlignedOffset
);
382 T
*Append(const T
&E
) XRAY_NEVER_INSTRUMENT
{
383 // FIXME: This is a duplication of AppenEmplace with the copy semantics
384 // explicitly used, as a work-around to GCC 4.8 not invoking the copy
385 // constructor with the placement new with braced-init syntax.
386 DCHECK((Size
== 0 && Head
== &SentinelSegment
&& Head
== Tail
) ||
387 (Size
!= 0 && Head
!= &SentinelSegment
&& Tail
!= &SentinelSegment
));
388 if (UNLIKELY(Head
== &SentinelSegment
)) {
389 auto R
= InitHeadAndTail();
394 DCHECK_NE(Head
, &SentinelSegment
);
395 DCHECK_NE(Tail
, &SentinelSegment
);
397 auto Offset
= Size
% ElementsPerSegment
;
398 if (UNLIKELY(Size
!= 0 && Offset
== 0))
399 if (AppendNewSegment() == nullptr)
402 DCHECK_NE(Tail
, &SentinelSegment
);
403 auto Base
= &Tail
->Data
;
404 auto AlignedOffset
= Base
+ (Offset
* AlignedElementStorageSize
);
405 DCHECK_LE(AlignedOffset
+ sizeof(T
),
406 reinterpret_cast<unsigned char *>(Tail
) + SegmentSize
);
408 // In-place construct at Position.
409 new (AlignedOffset
) T(E
);
411 return reinterpret_cast<T
*>(AlignedOffset
);
414 T
&operator[](uint64_t Offset
) const XRAY_NEVER_INSTRUMENT
{
415 DCHECK_LE(Offset
, Size
);
416 // We need to traverse the array enough times to find the element at Offset.
418 while (Offset
>= ElementsPerSegment
) {
420 Offset
-= ElementsPerSegment
;
421 DCHECK_NE(S
, &SentinelSegment
);
423 auto Base
= &S
->Data
;
424 auto AlignedOffset
= Base
+ (Offset
* AlignedElementStorageSize
);
425 auto Position
= reinterpret_cast<T
*>(AlignedOffset
);
426 return *reinterpret_cast<T
*>(Position
);
429 T
&front() const XRAY_NEVER_INSTRUMENT
{
430 DCHECK_NE(Head
, &SentinelSegment
);
435 T
&back() const XRAY_NEVER_INSTRUMENT
{
436 DCHECK_NE(Tail
, &SentinelSegment
);
443 template <class Predicate
>
444 T
*find_element(Predicate P
) const XRAY_NEVER_INSTRUMENT
{
449 for (auto I
= begin(); I
!= E
; ++I
)
456 /// Remove N Elements from the end. This leaves the blocks behind, and not
457 /// require allocation of new blocks for new elements added after trimming.
458 void trim(uint64_t Elements
) XRAY_NEVER_INSTRUMENT
{
460 Elements
= Elements
> Size
? Size
: Elements
;
463 // We compute the number of segments we're going to return from the tail by
464 // counting how many elements have been trimmed. Given the following:
466 // - Each segment has N valid positions, where N > 0
467 // - The previous size > current size
469 // To compute the number of segments to return, we need to perform the
470 // following calculations for the number of segments required given 'x'
476 // , N < x <= max : x / N + (x % N ? 1 : 0)
479 // We can simplify this down to:
483 // , 0 < x <= max : x / N + (x < N || x % N ? 1 : 0)
486 // And further down to:
488 // f(x) = x ? x / N + (x < N || x % N ? 1 : 0) : 0
490 // We can then perform the following calculation `s` which counts the number
491 // of segments we need to remove from the end of the data structure:
493 // s(p, c) = f(p) - f(c)
495 // If we treat p = previous size, and c = current size, and given the
496 // properties above, the possible range for s(...) is [0..max(typeof(p))/N]
497 // given that typeof(p) == typeof(c).
498 auto F
= [](uint64_t X
) {
499 return X
? (X
/ ElementsPerSegment
) +
500 (X
< ElementsPerSegment
|| X
% ElementsPerSegment
? 1 : 0)
503 auto PS
= F(OldSize
);
506 auto SegmentsToTrim
= PS
- CS
;
507 for (auto I
= 0uL; I
< SegmentsToTrim
; ++I
) {
508 // Here we place the current tail segment to the freelist. To do this
509 // appropriately, we need to perform a splice operation on two
510 // bidirectional linked-lists. In particular, we have the current state of
511 // the doubly-linked list of segments:
513 // @S@ <- s0 <-> s1 <-> ... <-> sT -> @S@
515 DCHECK_NE(Head
, &SentinelSegment
);
516 DCHECK_NE(Tail
, &SentinelSegment
);
517 DCHECK_EQ(Tail
->Next
, &SentinelSegment
);
519 if (Freelist
== &SentinelSegment
) {
520 // Our two lists at this point are in this configuration:
522 // Freelist: (potentially) @S@
523 // Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
526 // The end state for us will be this configuration:
528 // Freelist: @S@<-sT->@S@
529 // Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
532 // The first step for us is to hold a reference to the tail of Mainlist,
533 // which in our notation is represented by sT. We call this our "free
534 // segment" which is the segment we are placing on the Freelist.
538 // Then, we also hold a reference to the "pre-tail" element, which we
543 // We want to splice sT into the beginning of the Freelist, which in
544 // an empty Freelist means placing a segment whose predecessor and
545 // successor is the sentinel segment.
547 // The splice operation then can be performed in the following
552 // succ(sT) = Freelist
556 auto SPT
= Tail
->Prev
;
557 SPT
->Next
= &SentinelSegment
;
558 Tail
->Prev
= &SentinelSegment
;
559 Tail
->Next
= Freelist
;
563 // Our post-conditions here are:
564 DCHECK_EQ(Tail
->Next
, &SentinelSegment
);
565 DCHECK_EQ(Freelist
->Prev
, &SentinelSegment
);
567 // In the other case, where the Freelist is not empty, we perform the
568 // following transformation instead:
570 // This transforms the current state:
572 // Freelist: @S@<-f0->@S@
574 // Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
577 // Into the following:
579 // Freelist: @S@<-sT<->f0->@S@
581 // Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
589 // succ(sT) = Freelist
596 auto SPT
= Tail
->Prev
;
600 ST
->Prev
= &SentinelSegment
;
601 SPT
->Next
= &SentinelSegment
;
605 // Our post-conditions here are:
606 DCHECK_EQ(Tail
->Next
, &SentinelSegment
);
607 DCHECK_EQ(Freelist
->Prev
, &SentinelSegment
);
608 DCHECK_EQ(Freelist
->Next
->Prev
, Freelist
);
612 // Now in case we've spliced all the segments in the end, we ensure that the
613 // main list is "empty", or both the head and tail pointing to the sentinel
615 if (Tail
== &SentinelSegment
)
619 (Size
== 0 && Head
== &SentinelSegment
&& Tail
== &SentinelSegment
) ||
620 (Size
!= 0 && Head
!= &SentinelSegment
&& Tail
!= &SentinelSegment
));
622 (Freelist
!= &SentinelSegment
&& Freelist
->Prev
== &SentinelSegment
) ||
623 (Freelist
== &SentinelSegment
&& Tail
->Next
== &SentinelSegment
));
626 // Provide iterators.
627 Iterator
<T
> begin() const XRAY_NEVER_INSTRUMENT
{
628 return Iterator
<T
>(Head
, 0, Size
);
630 Iterator
<T
> end() const XRAY_NEVER_INSTRUMENT
{
631 return Iterator
<T
>(Tail
, Size
, Size
);
633 Iterator
<const T
> cbegin() const XRAY_NEVER_INSTRUMENT
{
634 return Iterator
<const T
>(Head
, 0, Size
);
636 Iterator
<const T
> cend() const XRAY_NEVER_INSTRUMENT
{
637 return Iterator
<const T
>(Tail
, Size
, Size
);
641 // We need to have this storage definition out-of-line so that the compiler can
642 // ensure that storage for the SentinelSegment is defined and has a single
645 typename Array
<T
>::Segment Array
<T
>::SentinelSegment
{
646 &Array
<T
>::SentinelSegment
, &Array
<T
>::SentinelSegment
, {'\0'}};
648 } // namespace __xray
650 #endif // XRAY_SEGMENTED_ARRAY_H