libsanitizer/sanitizer_common/sanitizer_ring_buffer.h

   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