[esan] Add circular buffer data structure

[bruening]

Summary

Adds a new class, CircularBuffer, for holding a wrap-around fixed-size
sequence of a primitive data type. This will be used initially by the
working set tool.

Adds a unit test for CircularBuffer, including infrastructure support to
include esan headers and to link with the esan library by pretending to
want the working set tool.

[aizatsky]

lib/esan/esan_circular_buffer.h

20 ↗

(On Diff #58264)

Document that you need to call "initialize/free" rather than rely on constructors/destructors.

26 ↗

(On Diff #58264)

If you plan to have local-instances of this class (which I assume you don't), then please follow the tsan pattern with in-place new and

static ALIGNED(16) char thread_registry_placeholder[sizeof(ThreadRegistry)];

This would result in much better reusable utility class.

[filcab]

LGTM.

Unsure if I'd place the unit test like that, or just in the same dir as the regular esan tests.
ASan (and I guess the other sanitizers') unit tests are very different from regular tests.

[bruening]

Add placement new support.

[vitalybuka]

compiler-rt/trunk/lib/esan/esan_circular_buffer.h

43

private: free() ?

[bruening]

compiler-rt/trunk/lib/esan/esan_circular_buffer.h

43

See the comment at lines 19-22: one usage pattern is to explicitly call free so it needs to be public.

compiler-rt/trunk/lib/esan/esan_circular_buffer.h

+//===-- esan_circular_buffer.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 EfficiencySanitizer, a family of performance tuners.
+//
+// Circular buffer data structure.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common/sanitizer_common.h"
+
+namespace __esan {
+
+// A circular buffer for POD data whose memory is allocated using mmap.
+// There are two usage models: one is to use initialize/free (for global
+// instances) and the other is to use placement new with the
+// constructor and to call the destructor or free (they are equivalent).
+template<typename T>
+class CircularBuffer {
+ public:
+  // To support global instances we cannot initialize any field in the
+  // default constructor.
+  explicit CircularBuffer() {}
+  CircularBuffer(uptr BufferCapacity) {
+    initialize(BufferCapacity);
+  }
+  ~CircularBuffer() {
+    free();
+  }
+  void initialize(uptr BufferCapacity) {
+    Capacity = BufferCapacity;
+    // MmapOrDie rounds up to the page size for us.
+    Data = (T *)MmapOrDie(Capacity * sizeof(T), "CircularBuffer");
+    StartIdx = 0;
+    Count = 0;
+  }
+  void free() {
+    UnmapOrDie(Data, Capacity * sizeof(T));
+  }
+  T &operator[](uptr Idx) {
+    CHECK_LT(Idx, Count);
+    uptr ArrayIdx = (StartIdx + Idx) % Capacity;
+    return Data[ArrayIdx];
+  }
+  const T &operator[](uptr Idx) const {
+    CHECK_LT(Idx, Count);
+    uptr ArrayIdx = (StartIdx + Idx) % Capacity;
+    return Data[ArrayIdx];
+  }
+  void push_back(const T &Item) {
+    CHECK_GT(Capacity, 0);
+    uptr ArrayIdx = (StartIdx + Count) % Capacity;
+    Data[ArrayIdx] = Item;
+    if (Count < Capacity)
+      ++Count;
+    else
+      StartIdx = (StartIdx + 1) % Capacity;
+  }
+  T &back() {
+    CHECK_GT(Count, 0);
+    uptr ArrayIdx = (StartIdx + Count - 1) % Capacity;
+    return Data[ArrayIdx];
+  }
+  void pop_back() {
+    CHECK_GT(Count, 0);
+    --Count;
+  }
+  uptr size() const {
+    return Count;
+  }
+  void clear() {
+    StartIdx = 0;
+    Count = 0;
+  }
+  bool empty() const { return size() == 0; }
+
+ private:
+  CircularBuffer(const CircularBuffer&);
+  void operator=(const CircularBuffer&);
+
+  T *Data;
+  uptr Capacity;
+  uptr StartIdx;
+  uptr Count;
+};
+
+} // namespace __esan

compiler-rt/trunk/test/esan/Unit/circular_buffer.cpp

+// RUN: %clangxx_unit -O0 %s -o %t 2>&1
+// RUN: %run %t 2>&1 | FileCheck %s
+
+#include "esan/esan_circular_buffer.h"
+#include "sanitizer_common/sanitizer_placement_new.h"
+#include <assert.h>
+#include <stdio.h>
+
+static const int TestBufCapacity = 4;
+
+// The buffer should have a capacity of TestBufCapacity.
+void testBuffer(__esan::CircularBuffer<int> *Buf) {
+  assert(Buf->size() == 0);
+  assert(Buf->empty());
+
+  Buf->push_back(1);
+  assert(Buf->back() == 1);
+  assert((*Buf)[0] == 1);
+  assert(Buf->size() == 1);
+  assert(!Buf->empty());
+
+  Buf->push_back(2);
+  Buf->push_back(3);
+  Buf->push_back(4);
+  Buf->push_back(5);
+  assert((*Buf)[0] == 2);
+  assert(Buf->size() == 4);
+
+  Buf->pop_back();
+  assert((*Buf)[0] == 2);
+  assert(Buf->size() == 3);
+
+  Buf->pop_back();
+  Buf->pop_back();
+  assert((*Buf)[0] == 2);
+  assert(Buf->size() == 1);
+  assert(!Buf->empty());
+
+  Buf->pop_back();
+  assert(Buf->empty());
+}
+
+int main()
+{
+  // Test initialize/free.
+  __esan::CircularBuffer<int> GlobalBuf;
+  GlobalBuf.initialize(TestBufCapacity);
+  testBuffer(&GlobalBuf);
+  GlobalBuf.free();
+
+  // Test constructor/free.
+  __esan::CircularBuffer<int> *LocalBuf;
+  static char placeholder[sizeof(*LocalBuf)];
+  LocalBuf = new(placeholder) __esan::CircularBuffer<int>(TestBufCapacity);
+  testBuffer(LocalBuf);
+  LocalBuf->free();
+
+  fprintf(stderr, "All checks passed.\n");
+  // CHECK: All checks passed.
+  return 0;
+}

compiler-rt/trunk/test/esan/lit.cfg

 # -*- Python -*-
 
 import os
 
 # Setup config name.
 config.name = 'EfficiencySanitizer' + config.name_suffix
 
 # Setup source root.
 config.test_source_root = os.path.dirname(__file__)
 
 # Setup default compiler flags used with -fsanitize=efficiency option.
 base_cflags = ([config.target_cflags] + config.debug_info_flags)
 base_cxxflags = config.cxx_mode_flags + base_cflags
 
 frag_cflags = (["-fsanitize=efficiency-cache-frag"] + base_cflags)
 wset_cflags = (["-fsanitize=efficiency-working-set"] + base_cflags)
+esan_incdir = config.test_source_root + "/../../lib"
+unit_cxxflags = (["-I%s" % esan_incdir, "-std=c++11",
+                  # We need to link with the esan runtime.
+                  "-fsanitize=efficiency-working-set"] + base_cxxflags)
 
 def build_invocation(compile_flags):
   return " " + " ".join([config.clang] + compile_flags) + " "
 
 config.substitutions.append( ("%clang_esan_frag ",
                               build_invocation(frag_cflags)) )
 config.substitutions.append( ("%clang_esan_wset ",
                               build_invocation(wset_cflags)) )
+config.substitutions.append( ("%clangxx_unit",
+                              build_invocation(unit_cxxflags)) )
 
 default_esan_opts = ''
 config.substitutions.append(('%env_esan_opts=',
                              'env ESAN_OPTIONS=' + default_esan_opts))
 
 # Default test suffixes.
 config.suffixes = ['.c', '.cpp']
 
 # EfficiencySanitizer tests are currently supported on Linux x86-64 only.
 if config.host_os not in ['Linux'] or config.target_arch != 'x86_64':
   config.unsupported = True