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