[XRay][compiler-rt] Remove C++ STL from the buffer queue implementation

[dberris]

Summary

This change removes the dependency on C++ standard library
types/functions in the implementation of the buffer queue. This is an
incremental step in resolving llvm.org/PR32274.

[pelikan]

compiler-rt/lib/xray/xray_buffer_queue.cc

68

I'm slightly worried about what happens if we mark this "true", then a signal happens, the handler will be instrumented and this thing will be reentered and succeeds past the mutex-guarded thing at the bottom. We will resume afterwards and continue with incrementing First yet again, possibly wasting a buffer.

SpinMutex is clever enough to yield in case there is a different thread waiting (which isn't here) but not to be aware of signal processing. I think this should be addressed in a different diff though, using a lock-less mechanism. Shouldn't be too tricky for this simple case.

compiler-rt/lib/xray/xray_buffer_queue.h

39

I was having a bit of a problem realizing whether this means "is being used" or "has been used". Maybe you can think of a small comment to improve this, maybe not.

[dberris]

Update to add comments.

[dberris]

compiler-rt/lib/xray/xray_buffer_queue.cc

68

This 'Found' is in the process of just finding whether we own the buffer. It's also outside the critical section for a reason, since we never update OwnedBuffers anywhere outside the constructor.

There are potential issues with the signal-safety of this function, but we have another synchronisation mechanism (recursion guard) that must guard us against having an instrumented signal handler coming in while already in the process of handling the event.

compiler-rt/lib/xray/xray_buffer_queue.h

39

I'm not sure why the distinction matters.

compiler-rt/lib/xray/xray_buffer_queue.h

 // This file is a part of XRay, a dynamic runtime instrumentation system.
 //
 // Defines the interface for a buffer queue implementation.
 //
 //===----------------------------------------------------------------------===//
 #ifndef XRAY_BUFFER_QUEUE_H
 #define XRAY_BUFFER_QUEUE_H
 
+#include <cstddef>
 #include "sanitizer_common/sanitizer_atomic.h"
 #include "sanitizer_common/sanitizer_mutex.h"
-#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:
+  struct BufferRep {
+    // The managed buffer.
+    Buffer Buffer;
+
+    // This is true if the buffer has been returned to the available queue, and
+    // is considered "used" by another thread.
+    bool Used = false;
+  };
+
   // 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::unique_ptr<std::tuple<Buffer, bool>[]> Buffers;
+  BufferRep *Buffers;
   size_t BufferCount;
 
   __sanitizer::SpinMutex Mutex;
   __sanitizer::atomic_uint8_t Finalizing;
 
   // Pointers to buffers managed/owned by the BufferQueue.
-  std::unique_ptr<void *[]> OwnedBuffers;
+  void **OwnedBuffers;
 
   // Pointer to the next buffer to be handed out.
-  std::tuple<Buffer, bool> *Next;
+  BufferRep *Next;
 
   // Pointer to the entry in the array where the next released buffer will be
   // placed.
-  std::tuple<Buffer, bool> *First;
+  BufferRep *First;
 
   // Count of buffers that have been handed out through 'getBuffer'.
   size_t LiveBuffers;
 
  public:
   enum class ErrorCode : unsigned {
     Ok,
     NotEnoughMemory,
     QueueFinalizing,
     UnrecognizedBuffer,
     AlreadyFinalized,
   };
 
   static const char *getErrorString(ErrorCode E) {
     switch (E) {
       case ErrorCode::Ok:
         return "(none)";
       case ErrorCode::NotEnoughMemory:
         return "no available buffers in the queue";
       case ErrorCode::QueueFinalizing:
         return "queue already finalizing";
       case ErrorCode::UnrecognizedBuffer:
         return "buffer being returned not owned by buffer queue";
       case ErrorCode::AlreadyFinalized:
         return "queue already finalized";
     }
     return "unknown error";
   }
 
   /// Initialise a queue of size |N| with buffers of size |B|. We report success
   /// through |Success|.
   BufferQueue(size_t B, size_t N, bool &Success);
 
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) {
+  template <class F>
+  void apply(F Fn) {
     __sanitizer::SpinMutexLock G(&Mutex);
-    for (auto I = Buffers.get(), E = Buffers.get() + BufferCount; I != E; ++I) {
+    for (auto I = Buffers, E = Buffers + BufferCount; I != E; ++I) {
       const auto &T = *I;
-      if (std::get<1>(T))
-        Fn(std::get<0>(T));
+      if (T.Used) Fn(T.Buffer);
     }
   }
 
   // Cleans up allocated buffers.
   ~BufferQueue();
 };
 
-} // namespace __xray
+}  // namespace __xray
 
-#endif // XRAY_BUFFER_QUEUE_H
+#endif  // XRAY_BUFFER_QUEUE_H

compiler-rt/lib/xray/xray_buffer_queue.cc

 //===-- xray_buffer_queue.cc -----------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of XRay, a dynamic runtime instruementation system.
 //
 // Defines the interface for a buffer queue implementation.
 //
 //===----------------------------------------------------------------------===//
 #include "xray_buffer_queue.h"
+#include "sanitizer_common/sanitizer_allocator_internal.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(new std::tuple<Buffer, bool>[N]()),
-      BufferCount(N), Finalizing{0}, OwnedBuffers(new void *[N]()),
-      Next(Buffers.get()), First(Buffers.get()), LiveBuffers(0) {
+BufferQueue::BufferQueue(size_t B, size_t N, bool &Success)
+    : BufferSize(B),
+      Buffers(new BufferRep[N]()),
+      BufferCount(N),
+      Finalizing{0},
+      OwnedBuffers(new void *[N]()),
+      Next(Buffers),
+      First(Buffers),
+      LiveBuffers(0) {
   for (size_t i = 0; i < N; ++i) {
     auto &T = Buffers[i];
-    void *Tmp = malloc(BufferSize);
+    void *Tmp = InternalAlloc(BufferSize);
     if (Tmp == nullptr) {
       Success = false;
       return;
     }
-    auto &Buf = std::get<0>(T);
-    std::get<1>(T) = false;
+    auto &Buf = T.Buffer;
     Buf.Buffer = Tmp;
     Buf.Size = B;
     OwnedBuffers[i] = Tmp;
   }
   Success = true;
 }
 
 BufferQueue::ErrorCode BufferQueue::getBuffer(Buffer &Buf) {
   if (__sanitizer::atomic_load(&Finalizing, __sanitizer::memory_order_acquire))
     return ErrorCode::QueueFinalizing;
   __sanitizer::SpinMutexLock Guard(&Mutex);
-  if (LiveBuffers == BufferCount)
-    return ErrorCode::NotEnoughMemory;
+  if (LiveBuffers == BufferCount) return ErrorCode::NotEnoughMemory;
 
   auto &T = *Next;
-  auto &B = std::get<0>(T);
+  auto &B = T.Buffer;
   Buf = B;
   ++LiveBuffers;
 
-  if (++Next == (Buffers.get() + BufferCount))
-    Next = Buffers.get();
+  if (++Next == (Buffers + BufferCount)) Next = Buffers;
 
   return ErrorCode::Ok;
 }
 
 BufferQueue::ErrorCode BufferQueue::releaseBuffer(Buffer &Buf) {
   // 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;
+  bool Found = false;
+  for (auto I = OwnedBuffers, E = OwnedBuffers + BufferCount; I != E; ++I) {
+    if (*I == Buf.Buffer) {
+      Found = true;
+      break;
+    }
+  }
+  if (!Found) return ErrorCode::UnrecognizedBuffer;
+
   __sanitizer::SpinMutexLock Guard(&Mutex);
 
   // This points to a semantic bug, we really ought to not be releasing more
   // buffers than we actually get.
-  if (LiveBuffers == 0)
-    return ErrorCode::NotEnoughMemory;
+  if (LiveBuffers == 0) return ErrorCode::NotEnoughMemory;
 
   // Now that the buffer has been released, we mark it as "used".
-  *First = std::make_tuple(Buf, true);
+  First->Buffer = Buf;
+  First->Used = true;
   Buf.Buffer = nullptr;
   Buf.Size = 0;
   --LiveBuffers;
-  if (++First == (Buffers.get() + BufferCount))
-    First = Buffers.get();
+  if (++First == (Buffers + BufferCount)) First = Buffers;
 
   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 I = Buffers.get(), E = Buffers.get() + BufferCount; I != E; ++I) {
+  for (auto I = Buffers, E = Buffers + BufferCount; I != E; ++I) {
     auto &T = *I;
-    auto &Buf = std::get<0>(T);
-    free(Buf.Buffer);
+    auto &Buf = T.Buffer;
+    InternalFree(Buf.Buffer);
   }
+  delete[] Buffers;
+  delete[] OwnedBuffers;
 }