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 <cstddef>
19 #include "sanitizer_common/sanitizer_atomic.h"
20 #include "sanitizer_common/sanitizer_mutex.h"
21 
22 namespace __xray {
23 
24 /// BufferQueue implements a circular queue of fixed sized buffers (much like a
25 /// freelist) but is concerned mostly with making it really quick to initialise,
26 /// finalise, and get/return buffers to the queue. This is one key component of
27 /// the "flight data recorder" (FDR) mode to support ongoing XRay function call
28 /// trace collection.
29 class BufferQueue {
30  public:
31   struct alignas(64) BufferExtents {
32     __sanitizer::atomic_uint64_t Size;
33   };
34 
35   struct Buffer {
36     void *Data = nullptr;
37     size_t Size = 0;
38     BufferExtents* Extents;
39   };
40 
41  private:
42   struct BufferRep {
43     // The managed buffer.
44     Buffer Buff;
45 
46     // This is true if the buffer has been returned to the available queue, and
47     // is considered "used" by another thread.
48     bool Used = false;
49   };
50 
51   // Size of each individual Buffer.
52   size_t BufferSize;
53 
54   BufferRep *Buffers;
55   size_t BufferCount;
56 
57   __sanitizer::SpinMutex Mutex;
58   __sanitizer::atomic_uint8_t Finalizing;
59 
60   // Pointers to buffers managed/owned by the BufferQueue.
61   void **OwnedBuffers;
62 
63   // Pointer to the next buffer to be handed out.
64   BufferRep *Next;
65 
66   // Pointer to the entry in the array where the next released buffer will be
67   // placed.
68   BufferRep *First;
69 
70   // Count of buffers that have been handed out through 'getBuffer'.
71   size_t LiveBuffers;
72 
73  public:
74   enum class ErrorCode : unsigned {
75     Ok,
76     NotEnoughMemory,
77     QueueFinalizing,
78     UnrecognizedBuffer,
79     AlreadyFinalized,
80   };
81 
82   static const char *getErrorString(ErrorCode E) {
83     switch (E) {
84       case ErrorCode::Ok:
85         return "(none)";
86       case ErrorCode::NotEnoughMemory:
87         return "no available buffers in the queue";
88       case ErrorCode::QueueFinalizing:
89         return "queue already finalizing";
90       case ErrorCode::UnrecognizedBuffer:
91         return "buffer being returned not owned by buffer queue";
92       case ErrorCode::AlreadyFinalized:
93         return "queue already finalized";
94     }
95     return "unknown error";
96   }
97 
98   /// Initialise a queue of size |N| with buffers of size |B|. We report success
99   /// through |Success|.
100   BufferQueue(size_t B, size_t N, bool &Success);
101 
102   /// Updates |Buf| to contain the pointer to an appropriate buffer. Returns an
103   /// error in case there are no available buffers to return when we will run
104   /// over the upper bound for the total buffers.
105   ///
106   /// Requirements:
107   ///   - BufferQueue is not finalising.
108   ///
109   /// Returns:
110   ///   - ErrorCode::NotEnoughMemory on exceeding MaxSize.
111   ///   - ErrorCode::Ok when we find a Buffer.
112   ///   - ErrorCode::QueueFinalizing or ErrorCode::AlreadyFinalized on
113   ///     a finalizing/finalized BufferQueue.
114   ErrorCode getBuffer(Buffer &Buf);
115 
116   /// Updates |Buf| to point to nullptr, with size 0.
117   ///
118   /// Returns:
119   ///   - ErrorCode::Ok when we successfully release the buffer.
120   ///   - ErrorCode::UnrecognizedBuffer for when this BufferQueue does not own
121   ///     the buffer being released.
122   ErrorCode releaseBuffer(Buffer &Buf);
123 
124   bool finalizing() const {
125     return __sanitizer::atomic_load(&Finalizing,
126                                     __sanitizer::memory_order_acquire);
127   }
128 
129   /// Returns the configured size of the buffers in the buffer queue.
130   size_t ConfiguredBufferSize() const { return BufferSize; }
131 
132   /// Sets the state of the BufferQueue to finalizing, which ensures that:
133   ///
134   ///   - All subsequent attempts to retrieve a Buffer will fail.
135   ///   - All releaseBuffer operations will not fail.
136   ///
137   /// After a call to finalize succeeds, all subsequent calls to finalize will
138   /// fail with ErrorCode::QueueFinalizing.
139   ErrorCode finalize();
140 
141   /// Applies the provided function F to each Buffer in the queue, only if the
142   /// Buffer is marked 'used' (i.e. has been the result of getBuffer(...) and a
143   /// releaseBuffer(...) operation).
144   template <class F>
145   void apply(F Fn) {
146     __sanitizer::SpinMutexLock G(&Mutex);
147     for (auto I = Buffers, E = Buffers + BufferCount; I != E; ++I) {
148       const auto &T = *I;
149       if (T.Used) Fn(T.Buff);
150     }
151   }
152 
153   // Cleans up allocated buffers.
154   ~BufferQueue();
155 };
156 
157 }  // namespace __xray
158 
159 #endif  // XRAY_BUFFER_QUEUE_H
160