Add a RingBuffer class to sanitizer_common

[kcc]

Summary

a constrained RingBuffer optimized for fast push

[kcc]

Rewrite RingBuffer using a different approach (suggested by eugenis@)

[eugenis]

lib/sanitizer_common/sanitizer_ring_buffer.h

31

I think you need to check that sizeof(T) is divisible by sizeof(void*), otherwise wrap-around check is not correct.

52

I think this is UB.

60

delete copy constructor?

[kcc]

address comments

lib/sanitizer_common/sanitizer_ring_buffer.h

31

done

52

done

60

done

[kcc]

updated a comment

[eugenis]

LGTM, thanks!

lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_platform_limits_netbsd.h
   sanitizer_platform_limits_openbsd.h
   sanitizer_platform_limits_posix.h
   sanitizer_platform_limits_solaris.h
   sanitizer_posix.h
   sanitizer_procmaps.h
   sanitizer_quarantine.h
   sanitizer_report_decorator.h
+  sanitizer_ring_buffer.h
   sanitizer_rtems.h
   sanitizer_signal_interceptors.inc
   sanitizer_stackdepot.h
   sanitizer_stackdepotbase.h
   sanitizer_stacktrace.h
   sanitizer_stacktrace_printer.h
   sanitizer_stoptheworld.h
   sanitizer_suppressions.h

lib/sanitizer_common/sanitizer_ring_buffer.h

+//===-- sanitizer_ring_buffer.h ---------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Simple ring buffer.
+//
+//===----------------------------------------------------------------------===//
+#ifndef SANITIZER_RING_BUFFER_H
+#define SANITIZER_RING_BUFFER_H
+
+#include "sanitizer_common.h"
+
+namespace __sanitizer {
+// RingBuffer<T>: fixed-size ring buffer optimized for speed of push().
+// T should be a POD type and sizeof(T) should be divisible by sizeof(void*).
+// At creation, all elements are zero.
+template<class T>
+class RingBuffer {
+ public:
+  static RingBuffer *New(uptr Size) {
+    void *Ptr = MmapOrDie(SizeInBytes(Size), "RingBuffer");
+    RingBuffer *RB = reinterpret_cast<RingBuffer*>(Ptr);
+    uptr End = reinterpret_cast<uptr>(Ptr) + SizeInBytes(Size);
+    RB->last_ = RB->next_ = reinterpret_cast<T*>(End - sizeof(T));
+    CHECK_EQ(sizeof(T) % sizeof(void*), 0U);
+    return RB;
+  }
+  void Delete() {
+    UnmapOrDie(this, SizeInBytes(size()));
+  }
+  uptr size() const {
+    return last_ + 1 -
+           reinterpret_cast<T *>(reinterpret_cast<uptr>(this) +
+                                 2 * sizeof(T *));
+  }
+  void push(T t) {
+    *next_ = t;
+    next_--;
+    // The condition below works only if sizeof(T) >= sizeof(T*).
+    if (next_ <= reinterpret_cast<T*>(&next_))
+      next_ = last_;
+  }
+
+  T operator[](uptr Idx) const {
+    CHECK_LT(Idx, size());
+    sptr IdxNext = Idx + 1;
+    if (IdxNext > last_ - next_)
+      IdxNext -= size();
+    return next_[IdxNext];
+  }
+
+ private:
+  RingBuffer() {}
+  ~RingBuffer() {}
+  RingBuffer(const RingBuffer&) = delete;
+
+  static uptr SizeInBytes(uptr Size) {
+    return Size * sizeof(T) + 2 * sizeof(T*);
+  }
+
+  // Data layout:
+  // LNDDDDDDDD
+  // D: data elements.
+  // L: last_, always points to the last data element.
+  // N: next_, initially equals to last_, is decremented on every push,
+  //    wraps around if it's less or equal than its own address.
+
+  T *last_;
+  T *next_;
+  T data_[1];  // flexible array.
+};
+
+}  // namespace __sanitizer
+
+#endif  // SANITIZER_RING_BUFFER_H

lib/sanitizer_common/tests/CMakeLists.txt

set(SANITIZER_UNITTESTS
   sanitizer_libc_test.cc
   sanitizer_linux_test.cc
   sanitizer_list_test.cc
   sanitizer_mutex_test.cc
   sanitizer_nolibc_test.cc
   sanitizer_posix_test.cc
   sanitizer_printf_test.cc
   sanitizer_procmaps_test.cc
+  sanitizer_ring_buffer_test.cc
   sanitizer_quarantine_test.cc
   sanitizer_stackdepot_test.cc
   sanitizer_stacktrace_printer_test.cc
   sanitizer_stacktrace_test.cc
   sanitizer_stoptheworld_test.cc
   sanitizer_suppressions_test.cc
   sanitizer_symbolizer_test.cc
   sanitizer_test_main.cc

lib/sanitizer_common/tests/sanitizer_ring_buffer_test.cc

+//===-- sanitizer_vector_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 *Sanitizer runtime.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_ring_buffer.h"
+#include "gtest/gtest.h"
+
+namespace __sanitizer {
+
+struct LargeStruct {
+  long v;
+  long extra[3];
+
+  LargeStruct(long v) : v(v) {}
+  operator long() { return v; }
+};
+
+struct Struct12Bytes {
+  int t[3];
+};
+
+TEST(RingBuffer, Construct) {
+
+  RingBuffer<long> *RBlong = RingBuffer<long>::New(20);
+  EXPECT_EQ(RBlong->size(), 20U);
+  RBlong->Delete();
+}
+
+template <class T> void TestRB() {
+  RingBuffer<T> *RB;
+  const size_t Sizes[] = {1, 2, 3, 5, 8, 16, 20, 40, 10000};
+  for (size_t Size: Sizes) {
+    RB = RingBuffer<T>::New(Size);
+    EXPECT_EQ(RB->size(), Size);
+    RB->Delete();
+  }
+
+  RB = RingBuffer<T>::New(4);
+  EXPECT_EQ(RB->size(), 4U);
+#define EXPECT_RING_BUFFER(a0, a1, a2, a3) \
+  EXPECT_EQ((long)(*RB)[0], (long)a0);                 \
+  EXPECT_EQ((long)(*RB)[1], (long)a1);                 \
+  EXPECT_EQ((long)(*RB)[2], (long)a2);                 \
+  EXPECT_EQ((long)(*RB)[3], (long)a3);
+
+  RB->push(1); EXPECT_RING_BUFFER(1, 0, 0, 0);
+  RB->push(2); EXPECT_RING_BUFFER(2, 1, 0, 0);
+  RB->push(3); EXPECT_RING_BUFFER(3, 2, 1, 0);
+  RB->push(4); EXPECT_RING_BUFFER(4, 3, 2, 1);
+  RB->push(5); EXPECT_RING_BUFFER(5, 4, 3, 2);
+  RB->push(6); EXPECT_RING_BUFFER(6, 5, 4, 3);
+  RB->push(7); EXPECT_RING_BUFFER(7, 6, 5, 4);
+  RB->push(8); EXPECT_RING_BUFFER(8, 7, 6, 5);
+  RB->push(9); EXPECT_RING_BUFFER(9, 8, 7, 6);
+  RB->push(10); EXPECT_RING_BUFFER(10, 9, 8, 7);
+  RB->push(11); EXPECT_RING_BUFFER(11, 10, 9, 8);
+  RB->push(12); EXPECT_RING_BUFFER(12, 11, 10, 9);
+
+#undef EXPECT_RING_BUFFER
+}
+
+TEST(RingBuffer, Int) {
+  EXPECT_DEATH(RingBuffer<int>::New(10), "");
+  EXPECT_DEATH(RingBuffer<Struct12Bytes>::New(10), "");
+}
+
+TEST(RingBuffer, Long) {
+  TestRB<long>();
+}
+
+TEST(RingBuffer, LargeStruct) {
+  TestRB<LargeStruct>();
+}
+
+}  // namespace __sanitizer