compiler-rt/lib/xray/xray_buffer_queue.h

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