libsanitizer/sanitizer_common/sanitizer_ring_buffer.h

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