1 //===-- sanitizer_ring_buffer.h ---------------------------------*- C++ -*-===// 2 // 3 // This file is distributed under the University of Illinois Open Source 4 // License. See LICENSE.TXT for details. 5 // 6 //===----------------------------------------------------------------------===// 7 // 8 // Simple ring buffer. 9 // 10 //===----------------------------------------------------------------------===// 11 #ifndef SANITIZER_RING_BUFFER_H 12 #define SANITIZER_RING_BUFFER_H 13 14 #include "sanitizer_common.h" 15 16 namespace __sanitizer { 17 // RingBuffer<T>: fixed-size ring buffer optimized for speed of push(). 18 // T should be a POD type and sizeof(T) should be divisible by sizeof(void*). 19 // At creation, all elements are zero. 20 template<class T> 21 class RingBuffer { 22 public: 23 COMPILER_CHECK(sizeof(T) % sizeof(void *) == 0); 24 static RingBuffer *New(uptr Size) { 25 void *Ptr = MmapOrDie(SizeInBytes(Size), "RingBuffer"); 26 RingBuffer *RB = reinterpret_cast<RingBuffer*>(Ptr); 27 uptr End = reinterpret_cast<uptr>(Ptr) + SizeInBytes(Size); 28 RB->last_ = RB->next_ = reinterpret_cast<T*>(End - sizeof(T)); 29 return RB; 30 } 31 void Delete() { 32 UnmapOrDie(this, SizeInBytes(size())); 33 } 34 uptr size() const { 35 return last_ + 1 - 36 reinterpret_cast<T *>(reinterpret_cast<uptr>(this) + 37 2 * sizeof(T *)); 38 } 39 40 static uptr SizeInBytes(uptr Size) { 41 return Size * sizeof(T) + 2 * sizeof(T*); 42 } 43 44 uptr SizeInBytes() { return SizeInBytes(size()); } 45 46 void push(T t) { 47 *next_ = t; 48 next_--; 49 // The condition below works only if sizeof(T) is divisible by sizeof(T*). 50 if (next_ <= reinterpret_cast<T*>(&next_)) 51 next_ = last_; 52 } 53 54 T operator[](uptr Idx) const { 55 CHECK_LT(Idx, size()); 56 sptr IdxNext = Idx + 1; 57 if (IdxNext > last_ - next_) 58 IdxNext -= size(); 59 return next_[IdxNext]; 60 } 61 62 private: 63 RingBuffer() {} 64 ~RingBuffer() {} 65 RingBuffer(const RingBuffer&) = delete; 66 67 // Data layout: 68 // LNDDDDDDDD 69 // D: data elements. 70 // L: last_, always points to the last data element. 71 // N: next_, initially equals to last_, is decremented on every push, 72 // wraps around if it's less or equal than its own address. 73 T *last_; 74 T *next_; 75 T data_[1]; // flexible array. 76 }; 77 78 // A ring buffer with externally provided storage that encodes its state in 8 79 // bytes. Has significant constraints on size and alignment of storage. 80 // See a comment in hwasan/hwasan_thread_list.h for the motivation behind this. 81 #if SANITIZER_WORDSIZE == 64 82 template <class T> 83 class CompactRingBuffer { 84 // Top byte of long_ stores the buffer size in pages. 85 // Lower bytes store the address of the next buffer element. 86 static constexpr int kPageSizeBits = 12; 87 static constexpr int kSizeShift = 56; 88 static constexpr uptr kNextMask = (1ULL << kSizeShift) - 1; 89 90 uptr GetStorageSize() const { return (long_ >> kSizeShift) << kPageSizeBits; } 91 92 void Init(void *storage, uptr size) { 93 CHECK_EQ(sizeof(CompactRingBuffer<T>), sizeof(void *)); 94 CHECK(IsPowerOfTwo(size)); 95 CHECK_GE(size, 1 << kPageSizeBits); 96 CHECK_LE(size, 128 << kPageSizeBits); 97 CHECK_EQ(size % 4096, 0); 98 CHECK_EQ(size % sizeof(T), 0); 99 CHECK_EQ((uptr)storage % (size * 2), 0); 100 long_ = (uptr)storage | ((size >> kPageSizeBits) << kSizeShift); 101 } 102 103 void SetNext(const T *next) { 104 long_ = (long_ & ~kNextMask) | (uptr)next; 105 } 106 107 public: 108 CompactRingBuffer(void *storage, uptr size) { 109 Init(storage, size); 110 } 111 112 // A copy constructor of sorts. 113 CompactRingBuffer(const CompactRingBuffer &other, void *storage) { 114 uptr size = other.GetStorageSize(); 115 internal_memcpy(storage, other.StartOfStorage(), size); 116 Init(storage, size); 117 uptr Idx = other.Next() - (const T *)other.StartOfStorage(); 118 SetNext((const T *)storage + Idx); 119 } 120 121 T *Next() const { return (T *)(long_ & kNextMask); } 122 123 void *StartOfStorage() const { 124 return (void *)((uptr)Next() & ~(GetStorageSize() - 1)); 125 } 126 127 void *EndOfStorage() const { 128 return (void *)((uptr)StartOfStorage() + GetStorageSize()); 129 } 130 131 uptr size() const { return GetStorageSize() / sizeof(T); } 132 133 void push(T t) { 134 T *next = Next(); 135 *next = t; 136 next++; 137 next = (T *)((uptr)next & ~GetStorageSize()); 138 SetNext(next); 139 } 140 141 T operator[](uptr Idx) const { 142 CHECK_LT(Idx, size()); 143 const T *Begin = (const T *)StartOfStorage(); 144 sptr StorageIdx = Next() - Begin; 145 StorageIdx -= (sptr)(Idx + 1); 146 if (StorageIdx < 0) 147 StorageIdx += size(); 148 return Begin[StorageIdx]; 149 } 150 151 public: 152 ~CompactRingBuffer() {} 153 CompactRingBuffer(const CompactRingBuffer &) = delete; 154 155 uptr long_; 156 }; 157 #endif 158 } // namespace __sanitizer 159 160 #endif // SANITIZER_RING_BUFFER_H 161