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 Iterator(BufferRep * Root,size_t O,size_t M)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 getErrorString(ErrorCode E)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 finalizing()233 bool finalizing() const { 234 return atomic_load(&Finalizing, memory_order_acquire); 235 } 236 generation()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. ConfiguredBufferSize()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). apply(F Fn)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. begin()266 iterator begin() const { return iterator(Buffers, 0, BufferCount); } cbegin()267 const_iterator cbegin() const { 268 return const_iterator(Buffers, 0, BufferCount); 269 } end()270 iterator end() const { return iterator(Buffers, BufferCount, BufferCount); } cend()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 282