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