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