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);
New(uptr Size)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   }
Delete()32   void Delete() {
33     UnmapOrDie(this, SizeInBytes(size()));
34   }
size()35   uptr size() const {
36     return last_ + 1 -
37            reinterpret_cast<T *>(reinterpret_cast<uptr>(this) +
38                                  2 * sizeof(T *));
39   }
40 
SizeInBytes(uptr Size)41   static uptr SizeInBytes(uptr Size) {
42     return Size * sizeof(T) + 2 * sizeof(T*);
43   }
44 
SizeInBytes()45   uptr SizeInBytes() { return SizeInBytes(size()); }
46 
push(T t)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:
RingBuffer()66   RingBuffer() {}
~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 
GetStorageSize()94   uptr GetStorageSize() const { return (long_ >> kSizeShift) << kPageSizeBits; }
95 
SignExtend(uptr x)96   static uptr SignExtend(uptr x) { return ((sptr)x) << kSizeBits >> kSizeBits; }
97 
Init(void * storage,uptr size)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 
SetNext(const T * next)111   void SetNext(const T *next) {
112     long_ = (long_ & ~kNextMask) | ((uptr)next & kNextMask);
113   }
114 
115  public:
CompactRingBuffer(void * storage,uptr size)116   CompactRingBuffer(void *storage, uptr size) {
117     Init(storage, size);
118   }
119 
120   // A copy constructor of sorts.
CompactRingBuffer(const CompactRingBuffer & other,void * storage)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 
Next()129   T *Next() const { return (T *)(SignExtend(long_ & kNextMask)); }
130 
StartOfStorage()131   void *StartOfStorage() const {
132     return (void *)((uptr)Next() & ~(GetStorageSize() - 1));
133   }
134 
EndOfStorage()135   void *EndOfStorage() const {
136     return (void *)((uptr)StartOfStorage() + GetStorageSize());
137   }
138 
size()139   uptr size() const { return GetStorageSize() / sizeof(T); }
140 
push(T t)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:
~CompactRingBuffer()160   ~CompactRingBuffer() {}
161   CompactRingBuffer(const CompactRingBuffer &) = delete;
162 
163   uptr long_;
164 };
165 #endif
166 }  // namespace __sanitizer
167 
168 #endif  // SANITIZER_RING_BUFFER_H
169