| 1 |
//===-- sanitizer_ring_buffer.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 |
// Simple ring buffer. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
#ifndef SANITIZER_RING_BUFFER_H |
| 13 |
#define SANITIZER_RING_BUFFER_H |
| 14 |
|
| 15 |
#include "sanitizer_common.h" |
| 16 |
|
| 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. |
| 21 |
template<class T> |
| 22 |
class RingBuffer { |
| 23 |
public: |
| 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)); |
| 30 |
return RB; |
| 31 |
} |
| 32 |
void Delete() { |
| 33 |
UnmapOrDie(this, SizeInBytes(size())); |
| 34 |
} |
| 35 |
uptr size() const { |
| 36 |
return last_ + 1 - |
| 37 |
reinterpret_cast<T *>(reinterpret_cast<uptr>(this) + |
| 38 |
2 * sizeof(T *)); |
| 39 |
} |
| 40 |
|
| 41 |
static uptr SizeInBytes(uptr Size) { |
| 42 |
return Size * sizeof(T) + 2 * sizeof(T*); |
| 43 |
} |
| 44 |
|
| 45 |
uptr SizeInBytes() { return SizeInBytes(size()); } |
| 46 |
|
| 47 |
void push(T t) { |
| 48 |
*next_ = t; |
| 49 |
next_--; |
| 50 |
static_assert((sizeof(T) % sizeof(T *)) == 0, |
| 51 |
"The condition below works only if sizeof(T) is divisible by " |
| 52 |
"sizeof(T*)."); |
| 53 |
if (next_ <= reinterpret_cast<T*>(&next_)) |
| 54 |
next_ = last_; |
| 55 |
} |
| 56 |
|
| 57 |
T operator[](uptr Idx) const { |
| 58 |
CHECK_LT(Idx, size()); |
| 59 |
sptr IdxNext = Idx + 1; |
| 60 |
if (IdxNext > last_ - next_) |
| 61 |
IdxNext -= size(); |
| 62 |
return next_[IdxNext]; |
| 63 |
} |
| 64 |
|
| 65 |
private: |
| 66 |
RingBuffer() {} |
| 67 |
~RingBuffer() {} |
| 68 |
RingBuffer(const RingBuffer&) = delete; |
| 69 |
|
| 70 |
// Data layout: |
| 71 |
// LNDDDDDDDD |
| 72 |
// D: data elements. |
| 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. |
| 76 |
T *last_; |
| 77 |
T *next_; |
| 78 |
T data_[1]; // flexible array. |
| 79 |
}; |
| 80 |
|
| 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 |
| 85 |
template <class T> |
| 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; |
| 93 |
|
| 94 |
uptr GetStorageSize() const { return (long_ >> kSizeShift) << kPageSizeBits; } |
| 95 |
|
| 96 |
static uptr SignExtend(uptr x) { return ((sptr)x) << kSizeBits >> kSizeBits; } |
| 97 |
|
| 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); |
| 109 |
} |
| 110 |
|
| 111 |
void SetNext(const T *next) { |
| 112 |
long_ = (long_ & ~kNextMask) | ((uptr)next & kNextMask); |
| 113 |
} |
| 114 |
|
| 115 |
public: |
| 116 |
CompactRingBuffer(void *storage, uptr size) { |
| 117 |
Init(storage, size); |
| 118 |
} |
| 119 |
|
| 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); |
| 124 |
Init(storage, size); |
| 125 |
uptr Idx = other.Next() - (const T *)other.StartOfStorage(); |
| 126 |
SetNext((const T *)storage + Idx); |
| 127 |
} |
| 128 |
|
| 129 |
T *Next() const { return (T *)(SignExtend(long_ & kNextMask)); } |
| 130 |
|
| 131 |
void *StartOfStorage() const { |
| 132 |
return (void *)((uptr)Next() & ~(GetStorageSize() - 1)); |
| 133 |
} |
| 134 |
|
| 135 |
void *EndOfStorage() const { |
| 136 |
return (void *)((uptr)StartOfStorage() + GetStorageSize()); |
| 137 |
} |
| 138 |
|
| 139 |
uptr size() const { return GetStorageSize() / sizeof(T); } |
| 140 |
|
| 141 |
void push(T t) { |
| 142 |
T *next = Next(); |
| 143 |
*next = t; |
| 144 |
next++; |
| 145 |
next = (T *)((uptr)next & ~GetStorageSize()); |
| 146 |
SetNext(next); |
| 147 |
} |
| 148 |
|
| 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); |
| 154 |
if (StorageIdx < 0) |
| 155 |
StorageIdx += size(); |
| 156 |
return Begin[StorageIdx]; |
| 157 |
} |
| 158 |
|
| 159 |
public: |
| 160 |
~CompactRingBuffer() {} |
| 161 |
CompactRingBuffer(const CompactRingBuffer &) = delete; |
| 162 |
|
| 163 |
uptr long_; |
| 164 |
}; |
| 165 |
#endif |
| 166 |
} // namespace __sanitizer |
| 167 |
|
| 168 |
#endif // SANITIZER_RING_BUFFER_H |