contrib/compiler-rt/lib/xray/xray_buffer_queue.h

   1 //===-- xray_buffer_queue.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 // This file is a part of XRay, a dynamic runtime instrumentation system.
  11 //
  12 // Defines the interface for a buffer queue implementation.
  13 //
  14 //===----------------------------------------------------------------------===//
  15 #ifndef XRAY_BUFFER_QUEUE_H
  16 #define XRAY_BUFFER_QUEUE_H
  17
  18 #include "sanitizer_common/sanitizer_atomic.h"
  19 #include "sanitizer_common/sanitizer_common.h"
  20 #include "sanitizer_common/sanitizer_mutex.h"
  21 #include <cstddef>
  22
  23 namespace __xray {
  24
  25 /// BufferQueue implements a circular queue of fixed sized buffers (much like a
  26 /// freelist) but is concerned mostly with making it really quick to initialise,
  27 /// finalise, and get/return buffers to the queue. This is one key component of
  28 /// the "flight data recorder" (FDR) mode to support ongoing XRay function call
  29 /// trace collection.
  30 class BufferQueue {
  31 public:
  32   struct alignas(64) BufferExtents {
  33     atomic_uint64_t Size;
  34   };
  35
  36   struct Buffer {
  37     void *Data = nullptr;
  38     size_t Size = 0;
  39     BufferExtents *Extents;
  40   };
  41
  42   struct BufferRep {
  43     // The managed buffer.
  44     Buffer Buff;
  45
  46     // This is true if the buffer has been returned to the available queue, and
  47     // is considered "used" by another thread.
  48     bool Used = false;
  49   };
  50
  51 private:
  52   // This models a ForwardIterator. |T| Must be either a `Buffer` or `const
  53   // Buffer`. Note that we only advance to the "used" buffers, when
  54   // incrementing, so that at dereference we're always at a valid point.
  55   template <class T> class Iterator {
  56   public:
  57     BufferRep *Buffers = nullptr;
  58     size_t Offset = 0;
  59     size_t Max = 0;
  60
  61     Iterator &operator++() {
  62       DCHECK_NE(Offset, Max);
  63       do {
  64         ++Offset;
  65       } while (!Buffers[Offset].Used && Offset != Max);
  66       return *this;
  67     }
  68
  69     Iterator operator++(int) {
  70       Iterator C = *this;
  71       ++(*this);
  72       return C;
  73     }
  74
  75     T &operator*() const { return Buffers[Offset].Buff; }
  76
  77     T *operator->() const { return &(Buffers[Offset].Buff); }
  78
  79     Iterator(BufferRep *Root, size_t O, size_t M)
  80         : Buffers(Root), Offset(O), Max(M) {
  81       // We want to advance to the first Offset where the 'Used' property is
  82       // true, or to the end of the list/queue.
  83       while (!Buffers[Offset].Used && Offset != Max) {
  84         ++Offset;
  85       }
  86     }
  87
  88     Iterator() = default;
  89     Iterator(const Iterator &) = default;
  90     Iterator(Iterator &&) = default;
  91     Iterator &operator=(const Iterator &) = default;
  92     Iterator &operator=(Iterator &&) = default;
  93     ~Iterator() = default;
  94
  95     template <class V>
  96     friend bool operator==(const Iterator &L, const Iterator<V> &R) {
  97       DCHECK_EQ(L.Max, R.Max);
  98       return L.Buffers == R.Buffers && L.Offset == R.Offset;
  99     }
 100
 101     template <class V>
 102     friend bool operator!=(const Iterator &L, const Iterator<V> &R) {
 103       return !(L == R);
 104     }
 105   };
 106
 107   // Size of each individual Buffer.
 108   size_t BufferSize;
 109
 110   BufferRep *Buffers;
 111
 112   // Amount of pre-allocated buffers.
 113   size_t BufferCount;
 114
 115   SpinMutex Mutex;
 116   atomic_uint8_t Finalizing;
 117
 118   // Pointers to buffers managed/owned by the BufferQueue.
 119   void **OwnedBuffers;
 120
 121   // Pointer to the next buffer to be handed out.
 122   BufferRep *Next;
 123
 124   // Pointer to the entry in the array where the next released buffer will be
 125   // placed.
 126   BufferRep *First;
 127
 128   // Count of buffers that have been handed out through 'getBuffer'.
 129   size_t LiveBuffers;
 130
 131 public:
 132   enum class ErrorCode : unsigned {
 133     Ok,
 134     NotEnoughMemory,
 135     QueueFinalizing,
 136     UnrecognizedBuffer,
 137     AlreadyFinalized,
 138   };
 139
 140   static const char *getErrorString(ErrorCode E) {
 141     switch (E) {
 142     case ErrorCode::Ok:
 143       return "(none)";
 144     case ErrorCode::NotEnoughMemory:
 145       return "no available buffers in the queue";
 146     case ErrorCode::QueueFinalizing:
 147       return "queue already finalizing";
 148     case ErrorCode::UnrecognizedBuffer:
 149       return "buffer being returned not owned by buffer queue";
 150     case ErrorCode::AlreadyFinalized:
 151       return "queue already finalized";
 152     }
 153     return "unknown error";
 154   }
 155
 156   /// Initialise a queue of size |N| with buffers of size |B|. We report success
 157   /// through |Success|.
 158   BufferQueue(size_t B, size_t N, bool &Success);
 159
 160   /// Updates |Buf| to contain the pointer to an appropriate buffer. Returns an
 161   /// error in case there are no available buffers to return when we will run
 162   /// over the upper bound for the total buffers.
 163   ///
 164   /// Requirements:
 165   ///   - BufferQueue is not finalising.
 166   ///
 167   /// Returns:
 168   ///   - ErrorCode::NotEnoughMemory on exceeding MaxSize.
 169   ///   - ErrorCode::Ok when we find a Buffer.
 170   ///   - ErrorCode::QueueFinalizing or ErrorCode::AlreadyFinalized on
 171   ///     a finalizing/finalized BufferQueue.
 172   ErrorCode getBuffer(Buffer &Buf);
 173
 174   /// Updates |Buf| to point to nullptr, with size 0.
 175   ///
 176   /// Returns:
 177   ///   - ErrorCode::Ok when we successfully release the buffer.
 178   ///   - ErrorCode::UnrecognizedBuffer for when this BufferQueue does not own
 179   ///     the buffer being released.
 180   ErrorCode releaseBuffer(Buffer &Buf);
 181
 182   bool finalizing() const {
 183     return atomic_load(&Finalizing, memory_order_acquire);
 184   }
 185
 186   /// Returns the configured size of the buffers in the buffer queue.
 187   size_t ConfiguredBufferSize() const { return BufferSize; }
 188
 189   /// Sets the state of the BufferQueue to finalizing, which ensures that:
 190   ///
 191   ///   - All subsequent attempts to retrieve a Buffer will fail.
 192   ///   - All releaseBuffer operations will not fail.
 193   ///
 194   /// After a call to finalize succeeds, all subsequent calls to finalize will
 195   /// fail with ErrorCode::QueueFinalizing.
 196   ErrorCode finalize();
 197
 198   /// Applies the provided function F to each Buffer in the queue, only if the
 199   /// Buffer is marked 'used' (i.e. has been the result of getBuffer(...) and a
 200   /// releaseBuffer(...) operation).
 201   template <class F> void apply(F Fn) {
 202     SpinMutexLock G(&Mutex);
 203     for (auto I = begin(), E = end(); I != E; ++I)
 204       Fn(*I);
 205   }
 206
 207   using const_iterator = Iterator<const Buffer>;
 208   using iterator = Iterator<Buffer>;
 209
 210   /// Provides iterator access to the raw Buffer instances.
 211   iterator begin() const { return iterator(Buffers, 0, BufferCount); }
 212   const_iterator cbegin() const {
 213     return const_iterator(Buffers, 0, BufferCount);
 214   }
 215   iterator end() const { return iterator(Buffers, BufferCount, BufferCount); }
 216   const_iterator cend() const {
 217     return const_iterator(Buffers, BufferCount, BufferCount);
 218   }
 219
 220   // Cleans up allocated buffers.
 221   ~BufferQueue();
 222 };
 223
 224 } // namespace __xray
 225
 226 #endif // XRAY_BUFFER_QUEUE_H