Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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
    163