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 "xray_defs.h"
  22 #include <cstddef>
  23 #include <cstdint>
  24
  25 namespace __xray {
  26
  27 /// BufferQueue implements a circular queue of fixed sized buffers (much like a
  28 /// freelist) but is concerned with making it quick to initialise, finalise, and
  29 /// get from or return buffers to the queue. This is one key component of the
  30 /// "flight data recorder" (FDR) mode to support ongoing XRay function call
  31 /// trace collection.
  32 class BufferQueue {
  33 public:
  34   /// ControlBlock represents the memory layout of how we interpret the backing
  35   /// store for all buffers and extents managed by a BufferQueue instance. The
  36   /// ControlBlock has the reference count as the first member, sized according
  37   /// to platform-specific cache-line size. We never use the Buffer member of
  38   /// the union, which is only there for compiler-supported alignment and
  39   /// sizing.
  40   ///
  41   /// This ensures that the `Data` member will be placed at least kCacheLineSize
  42   /// bytes from the beginning of the structure.
  43   struct ControlBlock {
  44     union {
  45       atomic_uint64_t RefCount;
  46       char Buffer[kCacheLineSize];
  47     };
  48
  49     /// We need to make this size 1, to conform to the C++ rules for array data
  50     /// members. Typically, we want to subtract this 1 byte for sizing
  51     /// information.
  52     char Data[1];
  53   };
  54
  55   struct Buffer {
  56     atomic_uint64_t *Extents = nullptr;
  57     uint64_t Generation{0};
  58     void *Data = nullptr;
  59     size_t Size = 0;
  60
  61   private:
  62     friend class BufferQueue;
  63     ControlBlock *BackingStore = nullptr;
  64     ControlBlock *ExtentsBackingStore = nullptr;
  65     size_t Count = 0;
  66   };
  67
  68   struct BufferRep {
  69     // The managed buffer.
  70     Buffer Buff;
  71
  72     // This is true if the buffer has been returned to the available queue, and
  73     // is considered "used" by another thread.
  74     bool Used = false;
  75   };
  76
  77 private:
  78   // This models a ForwardIterator. |T| Must be either a `Buffer` or `const
  79   // Buffer`. Note that we only advance to the "used" buffers, when
  80   // incrementing, so that at dereference we're always at a valid point.
  81   template <class T> class Iterator {
  82   public:
  83     BufferRep *Buffers = nullptr;
  84     size_t Offset = 0;
  85     size_t Max = 0;
  86
  87     Iterator &operator++() {
  88       DCHECK_NE(Offset, Max);
  89       do {
  90         ++Offset;
  91       } while (!Buffers[Offset].Used && Offset != Max);
  92       return *this;
  93     }
  94
  95     Iterator operator++(int) {
  96       Iterator C = *this;
  97       ++(*this);
  98       return C;
  99     }
 100
 101     T &operator*() const { return Buffers[Offset].Buff; }
 102
 103     T *operator->() const { return &(Buffers[Offset].Buff); }
 104
 105     Iterator(BufferRep *Root, size_t O, size_t M) XRAY_NEVER_INSTRUMENT
 106         : Buffers(Root),
 107           Offset(O),
 108           Max(M) {
 109       // We want to advance to the first Offset where the 'Used' property is
 110       // true, or to the end of the list/queue.
 111       while (!Buffers[Offset].Used && Offset != Max) {
 112         ++Offset;
 113       }
 114     }
 115
 116     Iterator() = default;
 117     Iterator(const Iterator &) = default;
 118     Iterator(Iterator &&) = default;
 119     Iterator &operator=(const Iterator &) = default;
 120     Iterator &operator=(Iterator &&) = default;
 121     ~Iterator() = default;
 122
 123     template <class V>
 124     friend bool operator==(const Iterator &L, const Iterator<V> &R) {
 125       DCHECK_EQ(L.Max, R.Max);
 126       return L.Buffers == R.Buffers && L.Offset == R.Offset;
 127     }
 128
 129     template <class V>
 130     friend bool operator!=(const Iterator &L, const Iterator<V> &R) {
 131       return !(L == R);
 132     }
 133   };
 134
 135   // Size of each individual Buffer.
 136   size_t BufferSize;
 137
 138   // Amount of pre-allocated buffers.
 139   size_t BufferCount;
 140
 141   SpinMutex Mutex;
 142   atomic_uint8_t Finalizing;
 143
 144   // The collocated ControlBlock and buffer storage.
 145   ControlBlock *BackingStore;
 146
 147   // The collocated ControlBlock and extents storage.
 148   ControlBlock *ExtentsBackingStore;
 149
 150   // A dynamically allocated array of BufferRep instances.
 151   BufferRep *Buffers;
 152
 153   // Pointer to the next buffer to be handed out.
 154   BufferRep *Next;
 155
 156   // Pointer to the entry in the array where the next released buffer will be
 157   // placed.
 158   BufferRep *First;
 159
 160   // Count of buffers that have been handed out through 'getBuffer'.
 161   size_t LiveBuffers;
 162
 163   // We use a generation number to identify buffers and which generation they're
 164   // associated with.
 165   atomic_uint64_t Generation;
 166
 167   /// Releases references to the buffers backed by the current buffer queue.
 168   void cleanupBuffers();
 169
 170 public:
 171   enum class ErrorCode : unsigned {
 172     Ok,
 173     NotEnoughMemory,
 174     QueueFinalizing,
 175     UnrecognizedBuffer,
 176     AlreadyFinalized,
 177     AlreadyInitialized,
 178   };
 179
 180   static const char *getErrorString(ErrorCode E) {
 181     switch (E) {
 182     case ErrorCode::Ok:
 183       return "(none)";
 184     case ErrorCode::NotEnoughMemory:
 185       return "no available buffers in the queue";
 186     case ErrorCode::QueueFinalizing:
 187       return "queue already finalizing";
 188     case ErrorCode::UnrecognizedBuffer:
 189       return "buffer being returned not owned by buffer queue";
 190     case ErrorCode::AlreadyFinalized:
 191       return "queue already finalized";
 192     case ErrorCode::AlreadyInitialized:
 193       return "queue already initialized";
 194     }
 195     return "unknown error";
 196   }
 197
 198   /// Initialise a queue of size |N| with buffers of size |B|. We report success
 199   /// through |Success|.
 200   BufferQueue(size_t B, size_t N, bool &Success);
 201
 202   /// Updates |Buf| to contain the pointer to an appropriate buffer. Returns an
 203   /// error in case there are no available buffers to return when we will run
 204   /// over the upper bound for the total buffers.
 205   ///
 206   /// Requirements:
 207   ///   - BufferQueue is not finalising.
 208   ///
 209   /// Returns:
 210   ///   - ErrorCode::NotEnoughMemory on exceeding MaxSize.
 211   ///   - ErrorCode::Ok when we find a Buffer.
 212   ///   - ErrorCode::QueueFinalizing or ErrorCode::AlreadyFinalized on
 213   ///     a finalizing/finalized BufferQueue.
 214   ErrorCode getBuffer(Buffer &Buf);
 215
 216   /// Updates |Buf| to point to nullptr, with size 0.
 217   ///
 218   /// Returns:
 219   ///   - ErrorCode::Ok when we successfully release the buffer.
 220   ///   - ErrorCode::UnrecognizedBuffer for when this BufferQueue does not own
 221   ///     the buffer being released.
 222   ErrorCode releaseBuffer(Buffer &Buf);
 223
 224   /// Initializes the buffer queue, starting a new generation. We can re-set the
 225   /// size of buffers with |BS| along with the buffer count with |BC|.
 226   ///
 227   /// Returns:
 228   ///   - ErrorCode::Ok when we successfully initialize the buffer. This
 229   ///   requires that the buffer queue is previously finalized.
 230   ///   - ErrorCode::AlreadyInitialized when the buffer queue is not finalized.
 231   ErrorCode init(size_t BS, size_t BC);
 232
 233   bool finalizing() const {
 234     return atomic_load(&Finalizing, memory_order_acquire);
 235   }
 236
 237   uint64_t generation() const {
 238     return atomic_load(&Generation, memory_order_acquire);
 239   }
 240
 241   /// Returns the configured size of the buffers in the buffer queue.
 242   size_t ConfiguredBufferSize() const { return BufferSize; }
 243
 244   /// Sets the state of the BufferQueue to finalizing, which ensures that:
 245   ///
 246   ///   - All subsequent attempts to retrieve a Buffer will fail.
 247   ///   - All releaseBuffer operations will not fail.
 248   ///
 249   /// After a call to finalize succeeds, all subsequent calls to finalize will
 250   /// fail with ErrorCode::QueueFinalizing.
 251   ErrorCode finalize();
 252
 253   /// Applies the provided function F to each Buffer in the queue, only if the
 254   /// Buffer is marked 'used' (i.e. has been the result of getBuffer(...) and a
 255   /// releaseBuffer(...) operation).
 256   template <class F> void apply(F Fn) XRAY_NEVER_INSTRUMENT {
 257     SpinMutexLock G(&Mutex);
 258     for (auto I = begin(), E = end(); I != E; ++I)
 259       Fn(*I);
 260   }
 261
 262   using const_iterator = Iterator<const Buffer>;
 263   using iterator = Iterator<Buffer>;
 264
 265   /// Provides iterator access to the raw Buffer instances.
 266   iterator begin() const { return iterator(Buffers, 0, BufferCount); }
 267   const_iterator cbegin() const {
 268     return const_iterator(Buffers, 0, BufferCount);
 269   }
 270   iterator end() const { return iterator(Buffers, BufferCount, BufferCount); }
 271   const_iterator cend() const {
 272     return const_iterator(Buffers, BufferCount, BufferCount);
 273   }
 274
 275   // Cleans up allocated buffers.
 276   ~BufferQueue();
 277 };
 278
 279 } // namespace __xray
 280
 281 #endif // XRAY_BUFFER_QUEUE_H