contrib/compiler-rt/lib/sanitizer_common/sanitizer_ring_buffer.h

   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);
  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   }
  33   void Delete() {
  34     UnmapOrDie(this, SizeInBytes(size()));
  35   }
  36   uptr size() const {
  37     return last_ + 1 -
  38            reinterpret_cast<T *>(reinterpret_cast<uptr>(this) +
  39                                  2 * sizeof(T *));
  40   }
  41
  42   static uptr SizeInBytes(uptr Size) {
  43     return Size * sizeof(T) + 2 * sizeof(T*);
  44   }
  45
  46   uptr SizeInBytes() { return SizeInBytes(size()); }
  47
  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:
  65   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
  92   uptr GetStorageSize() const { return (long_ >> kSizeShift) << kPageSizeBits; }
  93
  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
 105   void SetNext(const T *next) {
 106     long_ = (long_ & ~kNextMask) | (uptr)next;
 107   }
 108
 109  public:
 110   CompactRingBuffer(void *storage, uptr size) {
 111     Init(storage, size);
 112   }
 113
 114   // A copy constructor of sorts.
 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
 123   T *Next() const { return (T *)(long_ & kNextMask); }
 124
 125   void *StartOfStorage() const {
 126     return (void *)((uptr)Next() & ~(GetStorageSize() - 1));
 127   }
 128
 129   void *EndOfStorage() const {
 130     return (void *)((uptr)StartOfStorage() + GetStorageSize());
 131   }
 132
 133   uptr size() const { return GetStorageSize() / sizeof(T); }
 134
 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:
 154   ~CompactRingBuffer() {}
 155   CompactRingBuffer(const CompactRingBuffer &) = delete;
 156
 157   uptr long_;
 158 };
 159 #endif
 160 }  // namespace __sanitizer
 161
 162 #endif  // SANITIZER_RING_BUFFER_H