[XRay][compiler-rt] Use a hand-written circular buffer in BufferQueue

[dberris]

Summary

This change removes the dependency on using a std::deque<...> for the
storage of the buffers in the buffer queue. We instead implement a
fixed-size circular buffer that's resilient to exhaustion, and preserves
the semantics of the BufferQueue.

We're moving away from using std::deque<...> for two reasons:

• We want to remove dependencies on the STL for data structures.
• We want the data structure we use to not require re-allocation in the normal course of operation.

The internal implementation of the buffer queue uses heap-allocated
arrays that are initialized once when the BufferQueue is created, and
re-uses slots in the buffer array as buffers are returned in order.

We also change the lock used in the implementation to a spinlock
instead of a blocking mutex. We reason that since the release operations
now take very little time in the critical section, that a spinlock would
be appropriate.

This change is related to D38073.

[dberris]

ping @dblaikie?

[dblaikie]

Does this class have unit test coverage?

lib/xray/xray_buffer_queue.cc

28

Remove the Mutex() here, since that's the default (& probably () for the Finalizing initialization for consistency)?

49–51

Why the change in locks/locking scheme?

69

std::none_of?

97–98

Maybe here and other similar loops:

for (auto I = Buffers.get(), E = I + BufferCount; I != E; ++I)

(there's an LLVM style guide rule/suggestion to cache the end)

[dberris]

Address comment.

[dberris]

In D38119#882394, @dblaikie wrote:

Does this class have unit test coverage?

Yes.

lib/xray/xray_buffer_queue.cc

28

We can't use (...) for Finalizing because it's an aggregate (no constructors).

49–51

We explain it in the commit description -- since we no longer need to be allocating memory, and we posit that the bodies of these functions are now quicker, that we'd have a better chance to not causing too much latency due to contention for these functions.

[dblaikie]

Why all the logging & test changes in the latest update? Did they slip in accidentally?

lib/xray/xray_buffer_queue.cc

30

Looks like LLVM uses lowercase 'i' for integer counters much more often than uppercase 'I' (the uppercase is often used for iterators, but not so often used for integer counters).

(& probably "!=" rather than "<" I would guess is more idiomatic in LLVM)

[dberris]

• fixup: I -> i.

[dberris]

In D38119#883667, @dblaikie wrote:

Why all the logging & test changes in the latest update? Did they slip in accidentally?

Not accidental -- it turns out that sometimes, f2() doesn't last long enough to be logged, and despite the threshold for deltas being 0 it seems we are still able to get to that state.

That seems like a separate "bug" that I need to investigate.

Adding the fences in the test made it exhibit the problem less, so I kept it.

The atomic global is there to ensure that there's an observable dependency between the threads writing to the variable and the output of the main function.

[dberris]

Ah, I see one bit that did slip in to the logging implementation. Let me break that out as a separate NFC change.

[dberris]

Rebase after NFC, breaking out logging-specific refactoring.

[pelikan]

I'm wondering how much will all the malloc(3) calls in one thread impact the thread locality work done in tcmalloc. Better ask a tcmalloc expert though, I've lost track of what's going on.

[dberris]

Reverted as it caused unit test failures, for some reason weren't caught in local testing.

Re-opening now to keep track of review history.

[dberris]

• fixup: keep track of live buffers indepdendent of the pointers

[dberris]

• fixup: remove unused include

[dblaikie]

compiler-rt/trunk/lib/xray/xray_buffer_queue.h

45 ↗

(On Diff #117475)

Shouldn't we be avoiding adding more standard library memory allocation to compiler-rt? (I thought that was one of the goals)

& that reminds me: I think the reason to avoid /all/ C++ standard library in compiler-rt is because of the possibility of mismatch between the standard library used to build compiler-rt and the one used to build user code. If theer is such a mismatch then the comdat functions will be chosen essentially at random and either the user code or the compiler-rt code using such a library function could end up quite broken. Right?

[dberris]

compiler-rt/trunk/lib/xray/xray_buffer_queue.h

45 ↗

(On Diff #117475)

What's the harm with using std::unique_ptr<T[]> here? That it will use the standard allocator? Is there an alternative, should we be using raw pointers instead? Should we be allocating it with new[] or with malloc directly?

lib/xray/xray_buffer_queue.h

 // Defines the interface for a buffer queue implementation.
 //
 //===----------------------------------------------------------------------===//
 #ifndef XRAY_BUFFER_QUEUE_H
 #define XRAY_BUFFER_QUEUE_H
 
 #include "sanitizer_common/sanitizer_atomic.h"
 #include "sanitizer_common/sanitizer_mutex.h"
-#include <deque>
-#include <unordered_set>
+#include <cstdint>
+#include <memory>
 #include <utility>
 
 namespace __xray {
 
 /// BufferQueue implements a circular queue of fixed sized buffers (much like a
 /// freelist) but is concerned mostly with making it really quick to initialise,
 /// finalise, and get/return buffers to the queue. This is one key component of
 /// the "flight data recorder" (FDR) mode to support ongoing XRay function call
 /// trace collection.
 class BufferQueue {
 public:
   struct Buffer {
     void *Buffer = nullptr;
     size_t Size = 0;
   };
 
 private:
+  // Size of each individual Buffer.
   size_t BufferSize;
 
   // We use a bool to indicate whether the Buffer has been used in this
   // freelist implementation.
-  std::deque<std::tuple<Buffer, bool>> Buffers;
-  __sanitizer::BlockingMutex Mutex;
-  std::unordered_set<void *> OwnedBuffers;
+  std::unique_ptr<std::tuple<Buffer, bool>[]> Buffers;
+  size_t BufferCount;
+
+  __sanitizer::SpinMutex Mutex;
   __sanitizer::atomic_uint8_t Finalizing;
 
+  // Sorted buffer pointers, making it quick to find buffers that we own.
+  std::unique_ptr<void *[]> OwnedBuffers;
+
+  std::tuple<Buffer, bool> *Next;
+  std::tuple<Buffer, bool> *First;
+
 public:
   enum class ErrorCode : unsigned {
     Ok,
     NotEnoughMemory,
     QueueFinalizing,
     UnrecognizedBuffer,
     AlreadyFinalized,
   };
public:
   /// After a call to finalize succeeds, all subsequent calls to finalize will
   /// fail with ErrorCode::QueueFinalizing.
   ErrorCode finalize();
 
   /// Applies the provided function F to each Buffer in the queue, only if the
   /// Buffer is marked 'used' (i.e. has been the result of getBuffer(...) and a
   /// releaseBuffer(...) operation).
   template <class F> void apply(F Fn) {
-    __sanitizer::BlockingMutexLock G(&Mutex);
-    for (const auto &T : Buffers) {
+    __sanitizer::SpinMutexLock G(&Mutex);
+    for (auto I = Buffers.get(), E = Buffers.get() + BufferCount; I != E; ++I) {
+      const auto &T = *I;
       if (std::get<1>(T))
         Fn(std::get<0>(T));
     }
   }
 
   // Cleans up allocated buffers.
   ~BufferQueue();
 };
 
 } // namespace __xray
 
 #endif // XRAY_BUFFER_QUEUE_H

lib/xray/xray_buffer_queue.cc

 //
 // Defines the interface for a buffer queue implementation.
 //
 //===----------------------------------------------------------------------===//
 #include "xray_buffer_queue.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_libc.h"
 
+#include <algorithm>
 #include <cstdlib>
 #include <tuple>
 
 using namespace __xray;
 using namespace __sanitizer;
 
 BufferQueue::BufferQueue(std::size_t B, std::size_t N, bool &Success)
-    : BufferSize(B), Buffers(N), Mutex(), OwnedBuffers(), Finalizing{0} {
-  for (auto &T : Buffers) {
+    : BufferSize(B), Buffers(new std::tuple<Buffer, bool>[N]()),
+      BufferCount(N), Finalizing{0}, OwnedBuffers(new void *[N]()),
+      Next(Buffers.get()), First(nullptr) {
+  for (size_t i = 0; i < N; ++i) {
+    auto &T = Buffers[i];
     void *Tmp = malloc(BufferSize);
     if (Tmp == nullptr) {
       Success = false;
       return;
     }
-
     auto &Buf = std::get<0>(T);
+    std::get<1>(T) = false;
     Buf.Buffer = Tmp;
     Buf.Size = B;
-    OwnedBuffers.emplace(Tmp);
+    OwnedBuffers[i] = Tmp;
   }
   Success = true;
 }
 
 BufferQueue::ErrorCode BufferQueue::getBuffer(Buffer &Buf) {
   if (__sanitizer::atomic_load(&Finalizing, __sanitizer::memory_order_acquire))
     return ErrorCode::QueueFinalizing;
-  __sanitizer::BlockingMutexLock Guard(&Mutex);
-  if (Buffers.empty())
+  __sanitizer::SpinMutexLock Guard(&Mutex);
+
+  if (Next == First)
     return ErrorCode::NotEnoughMemory;
-  auto &T = Buffers.front();
+
+  auto &T = *Next;
   auto &B = std::get<0>(T);
   Buf = B;
-  B.Buffer = nullptr;
-  B.Size = 0;
-  Buffers.pop_front();
+
+  if (First == nullptr)
+    First = Next;
+  ++Next;
+  if (Next == (Buffers.get() + BufferCount))
+    Next = Buffers.get();
+
   return ErrorCode::Ok;
 }
 
 BufferQueue::ErrorCode BufferQueue::releaseBuffer(Buffer &Buf) {
-  if (OwnedBuffers.count(Buf.Buffer) == 0)
+  // Blitz through the buffers array to find the buffer.
+  if (std::none_of(OwnedBuffers.get(), OwnedBuffers.get() + BufferCount,
+                   [&Buf](void *P) { return P == Buf.Buffer; }))
     return ErrorCode::UnrecognizedBuffer;
-  __sanitizer::BlockingMutexLock Guard(&Mutex);
+  __sanitizer::SpinMutexLock Guard(&Mutex);
+
+  // This points to a semantic bug, we really ought to not be releasing more
+  // buffers than we actually get.
+  if (First == nullptr || First == Next)
+    return ErrorCode::NotEnoughMemory;
 
   // Now that the buffer has been released, we mark it as "used".
-  Buffers.emplace(Buffers.end(), Buf, true /* used */);
+  *First = std::make_tuple(Buf, true);
   Buf.Buffer = nullptr;
   Buf.Size = 0;
+  ++First;
+  if (First == (Buffers.get() + BufferCount))
+    First = Buffers.get();
   return ErrorCode::Ok;
 }
 
 BufferQueue::ErrorCode BufferQueue::finalize() {
   if (__sanitizer::atomic_exchange(&Finalizing, 1,
                                    __sanitizer::memory_order_acq_rel))
     return ErrorCode::QueueFinalizing;
   return ErrorCode::Ok;
 }
 
 BufferQueue::~BufferQueue() {
-  for (auto &T : Buffers) {
+  for (auto I = Buffers.get(), E = Buffers.get() + BufferCount; I != E; ++I) {
+    auto &T = *I;
     auto &Buf = std::get<0>(T);
     free(Buf.Buffer);
   }
 }

lib/xray/xray_fdr_logging_impl.h

public:
   explicit operator bool() const { return Valid; }
 
   ~RecursionGuard() noexcept {
     if (Valid)
       Running = false;
   }
 };
 
-inline bool loggingInitialized(
-    const __sanitizer::atomic_sint32_t &LoggingStatus) XRAY_NEVER_INSTRUMENT {
+inline bool loggingInitialized() XRAY_NEVER_INSTRUMENT {
   return __sanitizer::atomic_load(&LoggingStatus,
                                   __sanitizer::memory_order_acquire) ==
          XRayLogInitStatus::XRAY_LOG_INITIALIZED;
 }
 
 } // namespace
 
 inline void writeNewBufferPreamble(pid_t Tid, timespec TS,
if (TLD.RecordPtr != nullptr &&
         return false;
       TLD.RecordPtr = nullptr;
       LBQ = nullptr;
       return false;
     }
     return false;
   }
 
-  if (!loggingInitialized(LoggingStatus) || LBQ->finalizing()) {
+  if (!loggingInitialized() || LBQ->finalizing()) {
     writeEOBMetadata();
     if (!releaseThreadLocalBuffer(*LBQ))
       return false;
     TLD.RecordPtr = nullptr;
   }
 
   if (TLD.Buffer.Buffer == nullptr) {
     auto EC = LBQ->getBuffer(TLD.Buffer);

test/xray/TestCases/Linux/fdr-thread-order.cc

 // RUN: %clangxx_xray -g -std=c++11 %s -o %t
 // RUN: rm fdr-thread-order.* || true
-// RUN: XRAY_OPTIONS="patch_premain=false xray_naive_log=false xray_logfile_base=fdr-thread-order. xray_fdr_log=true verbosity=1 xray_fdr_log_func_duration_threshold_us=0" %run %t 2>&1 | FileCheck %s
-// RUN: %llvm_xray convert --symbolize --output-format=yaml -instr_map=%t "`ls fdr-thread-order.* | head -1`" | FileCheck %s --check-prefix TRACE
+// RUN: XRAY_OPTIONS="patch_premain=false xray_naive_log=false \
+// RUN:    xray_logfile_base=fdr-thread-order. xray_fdr_log=true verbosity=1 \
+// RUN:    xray_fdr_log_func_duration_threshold_us=0" %run %t 2>&1 | \
+// RUN:    FileCheck %s
+// RUN: %llvm_xray convert --symbolize --output-format=yaml -instr_map=%t \
+// RUN:    "`ls fdr-thread-order.* | head -1`"
+// RUN: %llvm_xray convert --symbolize --output-format=yaml -instr_map=%t \
+// RUN:    "`ls fdr-thread-order.* | head -1`" | \
+// RUN:    FileCheck %s --check-prefix TRACE
 // RUN: rm fdr-thread-order.*
 // FIXME: Make llvm-xray work on non-x86_64 as well.
 // REQUIRES: x86_64-linux
 // REQUIRES: built-in-llvm-tree
 
 #include "xray/xray_log_interface.h"
-#include <thread>
+#include <atomic>
 #include <cassert>
+#include <thread>
 
 constexpr auto kBufferSize = 16384;
 constexpr auto kBufferMax = 10;
 
-thread_local uint64_t var = 0;
-[[clang::xray_always_instrument]] void __attribute__((noinline)) f1() { ++var; }
-[[clang::xray_always_instrument]] void __attribute__((noinline)) f2() { ++var; }
+std::atomic<uint64_t> var{0};
+
+[[clang::xray_always_instrument]] void __attribute__((noinline)) f1() {
+  for (auto i = 0; i < 1 << 20; ++i)
+    ++var;
+}
+
+[[clang::xray_always_instrument]] void __attribute__((noinline)) f2() {
+  for (auto i = 0; i < 1 << 20; ++i)
+    ++var;
+}
 
 int main(int argc, char *argv[]) {
   using namespace __xray;
   FDRLoggingOptions Options;
+  __xray_patch();
   assert(__xray_log_init(kBufferSize, kBufferMax, &Options,
                          sizeof(FDRLoggingOptions)) ==
          XRayLogInitStatus::XRAY_LOG_INITIALIZED);
-  __xray_patch();
+
+  std::atomic_thread_fence(std::memory_order_acq_rel);
+
+  {
     std::thread t1([] { f1(); });
     std::thread t2([] { f2(); });
     t1.join();
     t2.join();
+  }
+
+  std::atomic_thread_fence(std::memory_order_acq_rel);
   __xray_log_finalize();
   __xray_log_flushLog();
+  __xray_unpatch();
+  return var > 0 ? 0 : 1;
   // CHECK: {{.*}}XRay: Log file in '{{.*}}'
+  // CHECK-NOT: Failed
 }
 
 // We want to make sure that the order of the function log doesn't matter.
 // TRACE-DAG: - { type: 0, func-id: [[FID1:[0-9]+]], function: {{.*f1.*}}, cpu: {{.*}}, thread: [[THREAD1:[0-9]+]], kind: function-enter, tsc: {{[0-9]+}} }
 // TRACE-DAG: - { type: 0, func-id: [[FID2:[0-9]+]], function: {{.*f2.*}}, cpu: {{.*}}, thread: [[THREAD2:[0-9]+]], kind: function-enter, tsc: {{[0-9]+}} }
 // TRACE-DAG: - { type: 0, func-id: [[FID1]], function: {{.*f1.*}}, cpu: {{.*}}, thread: [[THREAD1]], kind: {{function-exit|function-tail-exit}}, tsc: {{[0-9]+}} }
 // TRACE-DAG: - { type: 0, func-id: [[FID2]], function: {{.*f2.*}}, cpu: {{.*}}, thread: [[THREAD2]], kind: {{function-exit|function-tail-exit}}, tsc: {{[0-9]+}} }