[XRay][compiler-rt] XRay Buffer Queue

[dberris]

Summary

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.

[dberris]

• Add proper files for testing

[rSerge]

lib/xray/CMakeLists.txt

9

Can here be a comment on what FDR is?

lib/xray/tests/unit/buffer_queue_test.cc

21

Here http://man7.org/linux/man-pages/man2/getpagesize.2.html they say "Portable applications should employ sysconf(_SC_PAGESIZE) instead of getpagesize():".
Also, AFAIK, page sizes can be large (gigabytes). Would this code work then?

lib/xray/xray_buffer_queue.cc

25

Why not to do just 1 malloc and then distribute the pointers with offsets?

33

Shouldn't this be checked inside the mutex lock?

47

You are making it a queue, so the least recently used memory region is popped. This is bad for CPU cache. Why not to make it a stack, so that the most recently used buffer is returned first?
It needs just a change to push_front here... and perhaps renaming the data structure.

[dberris]

• Address review comments

[dberris]

lib/xray/tests/unit/buffer_queue_test.cc

21

This is really just a test, the page size is a convenient way of getting large-ish values. :)

lib/xray/xray_buffer_queue.cc

25

The idea is to have differentiated buffers that can be treated as individual thunks of memory. It also allows us to check for when malloc fails.

33

Nope, Finalizing is atomic, and is already synchronised -- so we avoid locking the mutex when the BufferQueue is already finalizing.

47

The point of the queue is so that we can ensure a temporal bound, i.e. we can keep around buffers that have been filled before. We explicitly want to actually keep the data around in the buffers, so that operations that have happened in the past are kept.

This is a key concept that the flight data recorder mode described in the whitepaper actually requires. Otherwise, if we made this a stack, then only the most recent operations will ever be kept (as opposed to a running log of things that have happened in the past).

[rSerge]

lib/xray/xray_buffer_queue.cc

25

Ok, I see.

33

What if finalize() is called between Finalizing.load(std::memory_order_acquire) and std::lock_guard<std::mutex> Guard(Mutex); here? The description for this data structure claims that getBuffer requests must be denied after finalize() is called, but this doesn't happen in this scenario. To enforce that invariant, the finalization flag must be set and read with mutex locked, so the flag itself doesn't have to be atomic (because the mutex provides the necessary acquire/release semantics).

47

So is this data structure just dropping the least recently used data? I didn't get that initially.

[dberris]

lib/xray/xray_buffer_queue.cc

33

What if finalize() is called between Finalizing.load(std::memory_order_acquire) and std::lock_guard<std::mutex> Guard(Mutex); here? The description for this data structure claims that getBuffer requests must be denied after finalize() is called, but this doesn't happen in this scenario.

But it does, right?

If one thread called getBuffer(...) just before another thread called finalize() then the ongoing getBuffer(...) should continue because finalize() had not technically been called yet when it started. We don't intend to make finalize() block on outstanding/ongoing getBuffer(...) calls (or the other way around).

How do I make the documentation on the function clear about this?

To enforce that invariant, the finalization flag must be set and read with mutex locked, so the flag itself doesn't have to be atomic (because the mutex provides the necessary acquire/release semantics).

On some platforms, operations on std::mutex may be implemented much more heavily compared to an atomic bool (hence the avoidance of locking the mutex in the first place). I'm actually thinking about whether a relaxed load is actually sufficient (at least in x86 it makes it faster) for the check, while using a release store on the finalize() side.

At this point I'm trying to avoid having to manually implement a wait-free or lock-free circular buffer, but maybe that's what this needs to end up becoming. ;)

Let me think about it a little more.

[rSerge]

lib/xray/xray_buffer_queue.cc

33

Have you considered http://en.cppreference.com/w/cpp/atomic/atomic_flag ? There is an example on how to acquire and release it, so to get a "spin lock" you need just to spin more.
I am not sure if "relaxed" will work, but you can avoid 2 acquire operations in a row (1 for Finalizing, 1 for the mutex) and instead just lock on the atomic flag, then check whether we are finalizing from a normal variable, then do the work and release the spin lock. It should not be spinning a lot because (if I understood correctly) finalize operation is rare and getBuffer is not called from multiple threads concurrently.

[dberris]

I'll be adding more representative use-case tests (making sure we're doing the right thing when functions are called in multiple threads).

lib/xray/xray_buffer_queue.cc

33

Have you considered http://en.cppreference.com/w/cpp/atomic/atomic_flag ? There is an example on how to acquire and release it, so to get a "spin lock" you need just to spin more.

I have considered atomic_flag, but see no advantage to using that instead of std::atomic<bool>. I also don't need to spin-lock here, I just need to make sure that as soon as finalize() is done, all future getBuffer() calls will fail reliably.

I am not sure if "relaxed" will work, but you can avoid 2 acquire operations in a row (1 for Finalizing, 1 for the mutex) and instead just lock on the atomic flag, then check whether we are finalizing from a normal variable, then do the work and release the spin lock. It should not be spinning a lot because (if I understood correctly) finalize operation is rare and getBuffer is not called from multiple threads concurrently.

getBuffer() is meant to be called in all threads that need a buffer (consider each thread to be writing to its own buffer) so this has to be synchronised appropriately. Now I could just use a spinlock, assuming that the pop_front() operation on a std::deque<...> will be fast enough, but pay dearly when the process is preempted in the middle of that critical section (i.e. while other threads are spinning).

I suppose I should add a set of tests to make sure we're fine here, let me do that next.

[dberris]

• Add a multi-threaded test

[dberris]

• Fix conditional on spin

[dberris]

• Make the launch policy explicitly async

[dberris]

PTAL

[rSerge]

LGTM

lib/xray/xray_buffer_queue.cc

33

Ok, I see.

[dberris]

Broke the build in arm7 and aarch64.

[rSerge]

I forgot one argument in favor of a spinlock: to alleviate the problem of sudden long-running operations (such as thread preemption), after spinning for N times (where N is such that 95% of times the guarded operation takes less time), the spinlock acquisition code should issue std::this_thread::yield(), so not to consume CPU if other threads have real work to do. Even though the CPU load with such approach is higher than with syscall-based mutexes, that load is effectively in background priority. While the responsiveness of spinlock is sub-nanosecond, while for a mutex it's on the order of microsecond.
But see yourself, perhaps it's not a good idea to optimize prematurely.

[dberris]

In D26232#605943, @rSerge wrote:

I forgot one argument in favor of a spinlock: to alleviate the problem of sudden long-running operations (such as thread preemption), after spinning for N times (where N is such that 95% of times the guarded operation takes less time), the spinlock acquisition code should issue std::this_thread::yield(), so not to consume CPU if other threads have real work to do. Even though the CPU load with such approach is higher than with syscall-based mutexes, that load is effectively in background priority. While the responsiveness of spinlock is sub-nanosecond, while for a mutex it's on the order of microsecond.
But see yourself, perhaps it's not a good idea to optimize prematurely.

Yeah, I think we can do this later when we have a better idea as to the cost of the short critical section involved in updating the data structure (the deque). The spin lock should be fine with a yield after a few iterations, but can't tell whether this will be something worth optimising yet. :)

Trying to submit again now that we have some workarounds to the arm and aarch64 builds failing and being flaky.

[rSerge]

compiler-rt/trunk/lib/xray/tests/unit/buffer_queue_test.cc

28 ↗

(On Diff #80380)

Here and in the other places ASSERT_NE(Buffers.getBuffer(Buf), 0) would give more information in case the test fails: the error code would get into the report produced by gtest.
Forcing it to boolean producess less informative report:

Value of: Buffers.getBuffer(Buf)
Actual: true
Expected: false

http://lab.llvm.org:8011/builders/clang-native-aarch64-full/builds/100/steps/ninja%20check%202/logs/FAIL%3A%20XRay-Unit%3A%3ABufferQueueTest.GetAndRelease

[dberris]

compiler-rt/trunk/lib/xray/tests/unit/buffer_queue_test.cc

28 ↗

(On Diff #80380)

Good point -- I'll go improve these in a separate patch.

Thanks @rSerge!

lib/xray/CMakeLists.txt

 # Build for the XRay runtime support library.
 
 set(XRAY_SOURCES
   xray_init.cc
-  xray_interface.cc
-  xray_flags.cc
-  xray_inmemory_log.cc
-)
+  xray_interface.cc
+  xray_flags.cc
+  xray_inmemory_log.cc)
+
+set(XRAY_FDR_SOURCES
+  xray_buffer_queue.cc)
 
 set(x86_64_SOURCES
-    xray_x86_64.cc
-    xray_trampoline_x86_64.S
-    ${XRAY_SOURCES})
+  xray_x86_64.cc
+  xray_trampoline_x86_64.S
+  ${XRAY_SOURCES})
 
 set(arm_SOURCES
-    xray_arm.cc
-    xray_trampoline_arm.S
-    ${XRAY_SOURCES})
+  xray_arm.cc
+  xray_trampoline_arm.S
+  ${XRAY_SOURCES})
 
 set(armhf_SOURCES ${arm_SOURCES})
 
 include_directories(..)
 include_directories(../../include)
 
 set(XRAY_CFLAGS ${SANITIZER_COMMON_CFLAGS})
-
 set(XRAY_COMMON_DEFINITIONS XRAY_HAS_EXCEPTIONS=1)
 
 add_compiler_rt_object_libraries(RTXray
-    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)
+    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()

lib/xray/tests/CMakeLists.txt

+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)
+  add_subdirectory(unit)
+endif()

lib/xray/tests/unit/CMakeLists.txt

+add_xray_unittest(XRayBufferQueueTest SOURCES
+  buffer_queue_test.cc xray_unit_test_main.cc)

lib/xray/tests/unit/buffer_queue_test.cc

+//===-- 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 <unistd.h>
+
+namespace __xray {
+
+TEST(BufferQueueTest, API) { BufferQueue Buffers(getpagesize(), 10); }
+
+TEST(BufferQueueTest, GetAndRelease) {
+  BufferQueue Buffers(getpagesize(), 10);
+  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(getpagesize(), 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(getpagesize(), 1);
+  BufferQueue::Buffer Buf;
+  Buf.Buffer = reinterpret_cast<void*>(0xdeadbeef);
+  Buf.Size = getpagesize();
+  EXPECT_EQ(std::errc::argument_out_of_domain, Buffers.releaseBuffer(Buf));
+}
+
+} // namespace __xray

lib/xray/tests/unit/xray_unit_test_main.cc

+//===-- 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();
+}

lib/xray/xray_buffer_queue.h

+//===-- 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 <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;
+
+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.
+  ///
+  /// Requirements:
+  ///   - BufferQueue is not finalising.
+  ///
+  /// Returns:
+  ///   - ...
+  std::error_code releaseBuffer(Buffer &Buf);
+
+  // Cleans up allocated buffers.
+  ~BufferQueue();
+};
+
+} // namespace __xray
+
+#endif // XRAY_BUFFER_QUEUE_H

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 <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;
+    OwnedBuffers.insert(Tmp);
+  }
+}
+
+std::error_code BufferQueue::getBuffer(Buffer &Buf) {
+  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 {};
+}
+
+BufferQueue::~BufferQueue() {
+  for (auto &Buf : Buffers) {
+    free(Buf.Buffer);
+    Buf.Buffer = nullptr;
+    Buf.Size = 0;
+  }
+}