1 //===-- sanitizer_ring_buffer.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 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
12 #ifndef SANITIZER_RING_BUFFER_H
13 #define SANITIZER_RING_BUFFER_H
15 #include "sanitizer_common.h"
17 namespace __sanitizer
{
18 // RingBuffer<T>: fixed-size ring buffer optimized for speed of push().
19 // T should be a POD type and sizeof(T) should be divisible by sizeof(void*).
20 // At creation, all elements are zero.
24 COMPILER_CHECK(sizeof(T
) % sizeof(void *) == 0);
25 static RingBuffer
*New(uptr Size
) {
26 void *Ptr
= MmapOrDie(SizeInBytes(Size
), "RingBuffer");
27 RingBuffer
*RB
= reinterpret_cast<RingBuffer
*>(Ptr
);
28 uptr End
= reinterpret_cast<uptr
>(Ptr
) + SizeInBytes(Size
);
29 RB
->last_
= RB
->next_
= reinterpret_cast<T
*>(End
- sizeof(T
));
33 UnmapOrDie(this, SizeInBytes(size()));
37 reinterpret_cast<T
*>(reinterpret_cast<uptr
>(this) +
41 static uptr
SizeInBytes(uptr Size
) {
42 return Size
* sizeof(T
) + 2 * sizeof(T
*);
45 uptr
SizeInBytes() { return SizeInBytes(size()); }
50 static_assert((sizeof(T
) % sizeof(T
*)) == 0,
51 "The condition below works only if sizeof(T) is divisible by "
53 if (next_
<= reinterpret_cast<T
*>(&next_
))
57 T
operator[](uptr Idx
) const {
58 CHECK_LT(Idx
, size());
59 sptr IdxNext
= Idx
+ 1;
60 if (IdxNext
> last_
- next_
)
62 return next_
[IdxNext
];
68 RingBuffer(const RingBuffer
&) = delete;
73 // L: last_, always points to the last data element.
74 // N: next_, initially equals to last_, is decremented on every push,
75 // wraps around if it's less or equal than its own address.
78 T data_
[1]; // flexible array.
81 // A ring buffer with externally provided storage that encodes its state in 8
82 // bytes. Has significant constraints on size and alignment of storage.
83 // See a comment in hwasan/hwasan_thread_list.h for the motivation behind this.
84 #if SANITIZER_WORDSIZE == 64
86 class CompactRingBuffer
{
87 // Top byte of long_ stores the buffer size in pages.
88 // Lower bytes store the address of the next buffer element.
89 static constexpr int kPageSizeBits
= 12;
90 static constexpr int kSizeShift
= 56;
91 static constexpr int kSizeBits
= 64 - kSizeShift
;
92 static constexpr uptr kNextMask
= (1ULL << kSizeShift
) - 1;
94 uptr
GetStorageSize() const { return (long_
>> kSizeShift
) << kPageSizeBits
; }
96 static uptr
SignExtend(uptr x
) { return ((sptr
)x
) << kSizeBits
>> kSizeBits
; }
98 void Init(void *storage
, uptr size
) {
99 CHECK_EQ(sizeof(CompactRingBuffer
<T
>), sizeof(void *));
100 CHECK(IsPowerOfTwo(size
));
101 CHECK_GE(size
, 1 << kPageSizeBits
);
102 CHECK_LE(size
, 128 << kPageSizeBits
);
103 CHECK_EQ(size
% 4096, 0);
104 CHECK_EQ(size
% sizeof(T
), 0);
105 uptr st
= (uptr
)storage
;
106 CHECK_EQ(st
% (size
* 2), 0);
107 CHECK_EQ(st
, SignExtend(st
& kNextMask
));
108 long_
= (st
& kNextMask
) | ((size
>> kPageSizeBits
) << kSizeShift
);
111 void SetNext(const T
*next
) {
112 long_
= (long_
& ~kNextMask
) | ((uptr
)next
& kNextMask
);
116 CompactRingBuffer(void *storage
, uptr size
) {
120 // A copy constructor of sorts.
121 CompactRingBuffer(const CompactRingBuffer
&other
, void *storage
) {
122 uptr size
= other
.GetStorageSize();
123 internal_memcpy(storage
, other
.StartOfStorage(), size
);
125 uptr Idx
= other
.Next() - (const T
*)other
.StartOfStorage();
126 SetNext((const T
*)storage
+ Idx
);
129 T
*Next() const { return (T
*)(SignExtend(long_
& kNextMask
)); }
131 void *StartOfStorage() const {
132 return (void *)((uptr
)Next() & ~(GetStorageSize() - 1));
135 void *EndOfStorage() const {
136 return (void *)((uptr
)StartOfStorage() + GetStorageSize());
139 uptr
size() const { return GetStorageSize() / sizeof(T
); }
145 next
= (T
*)((uptr
)next
& ~GetStorageSize());
149 const T
&operator[](uptr Idx
) const {
150 CHECK_LT(Idx
, size());
151 const T
*Begin
= (const T
*)StartOfStorage();
152 sptr StorageIdx
= Next() - Begin
;
153 StorageIdx
-= (sptr
)(Idx
+ 1);
155 StorageIdx
+= size();
156 return Begin
[StorageIdx
];
160 ~CompactRingBuffer() {}
161 CompactRingBuffer(const CompactRingBuffer
&) = delete;
166 } // namespace __sanitizer
168 #endif // SANITIZER_RING_BUFFER_H