[XRay][compiler-rt] XRay Buffer Queue

This implements a simple buffer queue to manage a pre-allocated queue of
fixed-sized buffers to hold XRay records. We need this to support
Flight Data Recorder (FDR) mode. We also implement this as a sub-library
first to allow for development before actually using it in an
implementation.

Some important properties of the buffer queue:

- Thread-safe enqueueing/dequeueing of fixed-size buffers.
- Pre-allocation of buffers at construction.

This is a re-roll of the previous attempt to submit, because it caused
failures in arm and aarch64.

Reviewers: majnemer, echristo, rSerge

Subscribers: tberghammer, danalbert, srhines, modocache, mehdi_amini, mgorny, llvm-commits

Differential Revision: https://reviews.llvm.org/D26232

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@288775 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 347 insertions, 17 deletions

diff --git a/lib/xray/CMakeLists.txt b/lib/xray/CMakeLists.txt
index bab84d835..9c7cf6ce3 100644
--- a/lib/xray/CMakeLists.txt
+++ b/lib/xray/CMakeLists.txt
@@ -1,11 +1,15 @@
 # Build for the XRay runtime support library.
 
+# Core XRay runtime library implementation files.
 set(XRAY_SOURCES
   xray_init.cc
   xray_interface.cc
   xray_flags.cc
-  xray_inmemory_log.cc
-)
+  xray_inmemory_log.cc)
+
+# XRay flight data recorder (FDR) implementation files.
+set(XRAY_FDR_SOURCES
+  xray_buffer_queue.cc)
 
 set(x86_64_SOURCES
     xray_x86_64.cc
@@ -28,31 +32,48 @@ include_directories(..)
 include_directories(../../include)
 
 set(XRAY_CFLAGS ${SANITIZER_COMMON_CFLAGS})
-
 set(XRAY_COMMON_DEFINITIONS XRAY_HAS_EXCEPTIONS=1)
 append_list_if(
   COMPILER_RT_HAS_XRAY_COMPILER_FLAG XRAY_SUPPORTED=1 XRAY_COMMON_DEFINITIONS)
 
 add_compiler_rt_object_libraries(RTXray
-    ARCHS ${XRAY_SUPPORTED_ARCH}
-    SOURCES ${XRAY_SOURCES} CFLAGS ${XRAY_CFLAGS}
-    DEFS ${XRAY_COMMON_DEFINITIONS})
+  ARCHS ${XRAY_SUPPORTED_ARCH}
+  SOURCES ${XRAY_SOURCES} CFLAGS ${XRAY_CFLAGS}
+  DEFS ${XRAY_COMMON_DEFINITIONS})
+
+add_compiler_rt_object_libraries(RTXrayFDR
+  ARCHS ${XRAY_SUPPORTED_ARCH}
+  SOURCES ${XRAY_FDR_SOURCES} CFLAGS ${XRAY_CFLAGS}
+  DEFS ${XRAY_COMMON_DEFINITIONS})
 
 add_compiler_rt_component(xray)
+add_compiler_rt_component(xray-fdr)
 
 set(XRAY_COMMON_RUNTIME_OBJECT_LIBS
     RTSanitizerCommon
     RTSanitizerCommonLibc)
 
-foreach (arch ${XRAY_SUPPORTED_ARCH})
-    if (CAN_TARGET_${arch})
-        add_compiler_rt_runtime(clang_rt.xray
-            STATIC
-            ARCHS ${arch}
-            SOURCES ${${arch}_SOURCES}
-            CFLAGS ${XRAY_CFLAGS}
-            DEFS ${XRAY_COMMON_DEFINITIONS}
-            OBJECT_LIBS ${XRAY_COMMON_RUNTIME_OBJECT_LIBS}
-            PARENT_TARGET xray)
-    endif ()
+foreach(arch ${XRAY_SUPPORTED_ARCH})
+  if(CAN_TARGET_${arch})
+    add_compiler_rt_runtime(clang_rt.xray
+     STATIC
+     ARCHS ${arch}
+     SOURCES ${${arch}_SOURCES}
+     CFLAGS ${XRAY_CFLAGS}
+     DEFS ${XRAY_COMMON_DEFINITIONS}
+     OBJECT_LIBS ${XRAY_COMMON_RUNTIME_OBJECT_LIBS}
+     PARENT_TARGET xray)
+   add_compiler_rt_runtime(clang_rt.xray-fdr
+     STATIC
+     ARCHS ${arch}
+     SOURCES ${XRAY_FDR_SOURCES}
+     CFLAGS ${XRAY_CFLAGS}
+     DEFS ${XRAY_COMMON_DEFINITIONS}
+     OBJECT_LIBS ${XRAY_COMMON_RUNTIME_OBJECT_LIBS}
+     PARENT_TARGET xray-fdr)
+  endif()
 endforeach()
+
+if(COMPILER_RT_INCLUDE_TESTS)
+  add_subdirectory(tests)
+endif()
diff --git a/lib/xray/tests/CMakeLists.txt b/lib/xray/tests/CMakeLists.txt
new file mode 100644
index 000000000..cdccd776b
--- /dev/null
+++ b/lib/xray/tests/CMakeLists.txt
@@ -0,0 +1,58 @@
+include_directories(..)
+
+add_custom_target(XRayUnitTests)
+set_target_properties(XRayUnitTests PROPERTIES FOLDER "XRay unittests")
+
+set(XRAY_UNITTEST_CFLAGS
+  ${XRAY_CFLAGS}
+  ${COMPILER_RT_UNITTEST_CFLAGS}
+  ${COMPILER_RT_GTEST_CFLAGS}
+  -I${COMPILER_RT_SOURCE_DIR}/include
+  -I${COMPILER_RT_SOURCE_DIR}/lib/xray)
+
+macro(xray_compile obj_list source arch)
+  get_filename_component(basename ${source} NAME)
+  set(output_obj "${basename}.${arch}.o")
+  get_target_flags_for_arch(${arch} TARGET_CFLAGS)
+  if(NOT COMPILER_RT_STANDALONE_BUILD)
+    list(APPEND COMPILE_DEPS gtest_main xray-fdr)
+  endif()
+  clang_compile(${output_obj} ${source}
+    CFLAGS ${XRAY_UNITTEST_CFLAGS} ${TARGET_CFLAGS}
+    DEPS ${COMPILE_DEPS})
+  list(APPEND ${obj_list} ${output_obj})
+endmacro()
+
+macro(add_xray_unittest testname)
+  set(XRAY_TEST_ARCH ${XRAY_SUPPORTED_ARCH})
+  if (APPLE)
+    darwin_filter_host_archs(XRAY_SUPPORTED_ARCH)
+  endif()
+  if(UNIX)
+    foreach(arch ${XRAY_TEST_ARCH})
+      cmake_parse_arguments(TEST "" "" "SOURCES;HEADERS" ${ARGN})
+      set(TEST_OBJECTS)
+      foreach(SOURCE ${TEST_SOURCES} ${COMPILER_RT_GTEST_SOURCE})
+        xray_compile(TEST_OBJECTS ${SOURCE} ${arch} ${TEST_HEADERS})
+      endforeach()
+      get_target_flags_for_arch(${arch} TARGET_LINK_FLAGS)
+      set(TEST_DEPS ${TEST_OBJECTS})
+      if(NOT COMPILER_RT_STANDALONE_BUILD)
+        list(APPEND TEST_DEPS gtest_main xray-fdr)
+      endif()
+      if(NOT APPLE)
+        add_compiler_rt_test(XRayUnitTests ${testname}
+          OBJECTS ${TEST_OBJECTS}
+          DEPS ${TEST_DEPS}
+          LINK_FLAGS ${TARGET_LINK_FLAGS}
+          -lstdc++ -lm ${CMAKE_THREAD_LIBS_INIT}
+          -L${COMPILER_RT_LIBRARY_OUTPUT_DIR} -lclang_rt.xray-fdr-${arch})
+      endif()
+      # FIXME: Figure out how to run even just the unit tests on APPLE.
+    endforeach()
+  endif()
+endmacro()
+
+if(COMPILER_RT_CAN_EXECUTE_TESTS AND NOT ANDROID)
+  add_subdirectory(unit)
+endif()
diff --git a/lib/xray/tests/unit/CMakeLists.txt b/lib/xray/tests/unit/CMakeLists.txt
new file mode 100644
index 000000000..3e5412d41
--- /dev/null
+++ b/lib/xray/tests/unit/CMakeLists.txt
@@ -0,0 +1,2 @@
+add_xray_unittest(XRayBufferQueueTest SOURCES
+  buffer_queue_test.cc xray_unit_test_main.cc)
diff --git a/lib/xray/tests/unit/buffer_queue_test.cc b/lib/xray/tests/unit/buffer_queue_test.cc
new file mode 100644
index 000000000..fd7d5afbb
--- /dev/null
+++ b/lib/xray/tests/unit/buffer_queue_test.cc
@@ -0,0 +1,80 @@
+//===-- buffer_queue_test.cc ----------------------------------------------===//
+//
+//                     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 function call tracing system.
+//
+//===----------------------------------------------------------------------===//
+#include "xray_buffer_queue.h"
+#include "gtest/gtest.h"
+
+#include <future>
+#include <unistd.h>
+
+namespace __xray {
+
+static constexpr size_t kSize = 4096;
+
+TEST(BufferQueueTest, API) { BufferQueue Buffers(kSize, 1); }
+
+TEST(BufferQueueTest, GetAndRelease) {
+  BufferQueue Buffers(kSize, 1);
+  BufferQueue::Buffer Buf;
+  ASSERT_FALSE(Buffers.getBuffer(Buf));
+  ASSERT_NE(nullptr, Buf.Buffer);
+  ASSERT_FALSE(Buffers.releaseBuffer(Buf));
+  ASSERT_EQ(nullptr, Buf.Buffer);
+}
+
+TEST(BufferQueueTest, GetUntilFailed) {
+  BufferQueue Buffers(kSize, 1);
+  BufferQueue::Buffer Buf0;
+  EXPECT_FALSE(Buffers.getBuffer(Buf0));
+  BufferQueue::Buffer Buf1;
+  EXPECT_EQ(std::errc::not_enough_memory, Buffers.getBuffer(Buf1));
+  EXPECT_FALSE(Buffers.releaseBuffer(Buf0));
+}
+
+TEST(BufferQueueTest, ReleaseUnknown) {
+  BufferQueue Buffers(kSize, 1);
+  BufferQueue::Buffer Buf;
+  Buf.Buffer = reinterpret_cast<void *>(0xdeadbeef);
+  Buf.Size = kSize;
+  EXPECT_EQ(std::errc::argument_out_of_domain, Buffers.releaseBuffer(Buf));
+}
+
+TEST(BufferQueueTest, ErrorsWhenFinalising) {
+  BufferQueue Buffers(kSize, 2);
+  BufferQueue::Buffer Buf;
+  ASSERT_FALSE(Buffers.getBuffer(Buf));
+  ASSERT_NE(nullptr, Buf.Buffer);
+  ASSERT_FALSE(Buffers.finalize());
+  BufferQueue::Buffer OtherBuf;
+  ASSERT_EQ(std::errc::state_not_recoverable, Buffers.getBuffer(OtherBuf));
+  ASSERT_EQ(std::errc::state_not_recoverable, Buffers.finalize());
+  ASSERT_FALSE(Buffers.releaseBuffer(Buf));
+}
+
+TEST(BufferQueueTest, MultiThreaded) {
+  BufferQueue Buffers(kSize, 100);
+  auto F = [&] {
+    BufferQueue::Buffer B;
+    while (!Buffers.getBuffer(B)) {
+      Buffers.releaseBuffer(B);
+    }
+  };
+  auto T0 = std::async(std::launch::async, F);
+  auto T1 = std::async(std::launch::async, F);
+  auto T2 = std::async(std::launch::async, [&] {
+    while (!Buffers.finalize())
+      ;
+  });
+  F();
+}
+
+} // namespace __xray
diff --git a/lib/xray/tests/unit/xray_unit_test_main.cc b/lib/xray/tests/unit/xray_unit_test_main.cc
new file mode 100644
index 000000000..27d17527d
--- /dev/null
+++ b/lib/xray/tests/unit/xray_unit_test_main.cc
@@ -0,0 +1,18 @@
+//===-- xray_unit_test_main.cc --------------------------------------------===//
+//
+//                     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 function call tracing system.
+//
+//===----------------------------------------------------------------------===//
+#include "gtest/gtest.h"
+
+int main(int argc, char **argv) {
+  testing::InitGoogleTest(&argc, argv);
+  return RUN_ALL_TESTS();
+}
diff --git a/lib/xray/xray_buffer_queue.cc b/lib/xray/xray_buffer_queue.cc
new file mode 100644
index 000000000..17878eb85
--- /dev/null
+++ b/lib/xray/xray_buffer_queue.cc
@@ -0,0 +1,65 @@
+//===-- 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 <cassert>
+#include <cstdlib>
+
+using namespace __xray;
+
+BufferQueue::BufferQueue(std::size_t B, std::size_t N)
+    : BufferSize(B), Buffers(N) {
+  for (auto &Buf : Buffers) {
+    void *Tmp = malloc(BufferSize);
+    Buf.Buffer = Tmp;
+    Buf.Size = B;
+    if (Tmp != 0)
+      OwnedBuffers.insert(Tmp);
+  }
+}
+
+std::error_code BufferQueue::getBuffer(Buffer &Buf) {
+  if (Finalizing.load(std::memory_order_acquire))
+    return std::make_error_code(std::errc::state_not_recoverable);
+  std::lock_guard<std::mutex> Guard(Mutex);
+  if (Buffers.empty())
+    return std::make_error_code(std::errc::not_enough_memory);
+  Buf = Buffers.front();
+  Buffers.pop_front();
+  return {};
+}
+
+std::error_code BufferQueue::releaseBuffer(Buffer &Buf) {
+  if (OwnedBuffers.count(Buf.Buffer) == 0)
+    return std::make_error_code(std::errc::argument_out_of_domain);
+  std::lock_guard<std::mutex> Guard(Mutex);
+  Buffers.push_back(Buf);
+  Buf.Buffer = nullptr;
+  Buf.Size = BufferSize;
+  return {};
+}
+
+std::error_code BufferQueue::finalize() {
+  if (Finalizing.exchange(true, std::memory_order_acq_rel))
+    return std::make_error_code(std::errc::state_not_recoverable);
+  return {};
+}
+
+BufferQueue::~BufferQueue() {
+  for (auto &Buf : Buffers) {
+    free(Buf.Buffer);
+    Buf.Buffer = nullptr;
+    Buf.Size = 0;
+  }
+}
diff --git a/lib/xray/xray_buffer_queue.h b/lib/xray/xray_buffer_queue.h
new file mode 100644
index 000000000..bf0b7af9d
--- /dev/null
+++ b/lib/xray/xray_buffer_queue.h
@@ -0,0 +1,86 @@
+//===-- xray_buffer_queue.h ------------------------------------*- 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 instrumentation system.
+//
+// Defines the interface for a buffer queue implementation.
+//
+//===----------------------------------------------------------------------===//
+#ifndef XRAY_BUFFER_QUEUE_H
+#define XRAY_BUFFER_QUEUE_H
+
+#include <atomic>
+#include <cstdint>
+#include <deque>
+#include <mutex>
+#include <system_error>
+#include <unordered_set>
+
+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;
+    std::size_t Size = 0;
+  };
+
+private:
+  std::size_t BufferSize;
+  std::deque<Buffer> Buffers;
+  std::mutex Mutex;
+  std::unordered_set<void *> OwnedBuffers;
+  std::atomic<bool> Finalizing;
+
+public:
+  /// Initialise a queue of size |N| with buffers of size |B|.
+  BufferQueue(std::size_t B, std::size_t N);
+
+  /// Updates |Buf| to contain the pointer to an appropriate buffer. Returns an
+  /// error in case there are no available buffers to return when we will run
+  /// over the upper bound for the total buffers.
+  ///
+  /// Requirements:
+  ///   - BufferQueue is not finalising.
+  ///
+  /// Returns:
+  ///   - std::errc::not_enough_memory on exceeding MaxSize.
+  ///   - no error when we find a Buffer.
+  ///   - std::errc::state_not_recoverable on finalising BufferQueue.
+  std::error_code getBuffer(Buffer &Buf);
+
+  /// Updates |Buf| to point to nullptr, with size 0.
+  ///
+  /// Returns:
+  ///   - ...
+  std::error_code releaseBuffer(Buffer &Buf);
+
+  bool finalizing() const { return Finalizing.load(std::memory_order_acquire); }
+
+  // Sets the state of the BufferQueue to finalizing, which ensures that:
+  //
+  //   - All subsequent attempts to retrieve a Buffer will fail.
+  //   - All releaseBuffer operations will not fail.
+  //
+  // After a call to finalize succeeds, all subsequent calls to finalize will
+  // fail with std::errc::state_not_recoverable.
+  std::error_code finalize();
+
+  // Cleans up allocated buffers.
+  ~BufferQueue();
+};
+
+} // namespace __xray
+
+#endif // XRAY_BUFFER_QUEUE_H