Move __tsan::Vector to __sanitizer

Summary:
The low-fat STL-like vector container will be reused in MSan.

It is needed to implement an atexit(3) interceptor on NetBSD/amd64 in MSan.

Sponsored by <The NetBSD Foundation>

Reviewers: joerg, dvyukov, eugenis, vitalybuka, kcc

Reviewed By: dvyukov

Subscribers: kubamracek, mgorny, llvm-commits, #sanitizers

Tags: #sanitizers

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

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

4 files changed, 170 insertions, 1 deletions

diff --git a/lib/sanitizer_common/CMakeLists.txt b/lib/sanitizer_common/CMakeLists.txt
index db077b565..60caa5c4f 100644
--- a/lib/sanitizer_common/CMakeLists.txt
+++ b/lib/sanitizer_common/CMakeLists.txt
@@ -140,6 +140,7 @@ set(SANITIZER_HEADERS
   sanitizer_syscall_linux_x86_64.inc
   sanitizer_syscall_linux_aarch64.inc
   sanitizer_thread_registry.h
+  sanitizer_vector.h
   sanitizer_win.h)
 
 include_directories(..)
diff --git a/lib/sanitizer_common/sanitizer_vector.h b/lib/sanitizer_common/sanitizer_vector.h
new file mode 100644
index 000000000..25cfeed35
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_vector.h
@@ -0,0 +1,125 @@
+//===-- sanitizer_vector.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 shared between sanitizers run-time libraries.
+//
+//===----------------------------------------------------------------------===//
+
+// Low-fat STL-like vector container.
+
+#ifndef SANITIZER_VECTOR_H
+#define SANITIZER_VECTOR_H
+
+#include "sanitizer_common/sanitizer_allocator_internal.h"
+#include "sanitizer_common/sanitizer_libc.h"
+
+namespace __sanitizer {
+
+template<typename T>
+class Vector {
+ public:
+  explicit Vector()
+      : begin_()
+      , end_()
+      , last_() {
+  }
+
+  ~Vector() {
+    if (begin_)
+      InternalFree(begin_);
+  }
+
+  void Reset() {
+    if (begin_)
+      InternalFree(begin_);
+    begin_ = 0;
+    end_ = 0;
+    last_ = 0;
+  }
+
+  uptr Size() const {
+    return end_ - begin_;
+  }
+
+  T &operator[](uptr i) {
+    DCHECK_LT(i, end_ - begin_);
+    return begin_[i];
+  }
+
+  const T &operator[](uptr i) const {
+    DCHECK_LT(i, end_ - begin_);
+    return begin_[i];
+  }
+
+  T *PushBack() {
+    EnsureSize(Size() + 1);
+    T *p = &end_[-1];
+    internal_memset(p, 0, sizeof(*p));
+    return p;
+  }
+
+  T *PushBack(const T& v) {
+    EnsureSize(Size() + 1);
+    T *p = &end_[-1];
+    internal_memcpy(p, &v, sizeof(*p));
+    return p;
+  }
+
+  void PopBack() {
+    DCHECK_GT(end_, begin_);
+    end_--;
+  }
+
+  void Resize(uptr size) {
+    if (size == 0) {
+      end_ = begin_;
+      return;
+    }
+    uptr old_size = Size();
+    EnsureSize(size);
+    if (old_size < size) {
+      for (uptr i = old_size; i < size; i++)
+        internal_memset(&begin_[i], 0, sizeof(begin_[i]));
+    }
+  }
+
+ private:
+  T *begin_;
+  T *end_;
+  T *last_;
+
+  void EnsureSize(uptr size) {
+    if (size <= Size())
+      return;
+    if (size <= (uptr)(last_ - begin_)) {
+      end_ = begin_ + size;
+      return;
+    }
+    uptr cap0 = last_ - begin_;
+    uptr cap = cap0 * 5 / 4;  // 25% growth
+    if (cap == 0)
+      cap = 16;
+    if (cap < size)
+      cap = size;
+    T *p = (T*)InternalAlloc(cap * sizeof(T));
+    if (cap0) {
+      internal_memcpy(p, begin_, cap0 * sizeof(T));
+      InternalFree(begin_);
+    }
+    begin_ = p;
+    end_ = begin_ + size;
+    last_ = begin_ + cap;
+  }
+
+  Vector(const Vector&);
+  void operator=(const Vector&);
+};
+}  // namespace __sanitizer
+
+#endif  // #ifndef SANITIZER_VECTOR_H
diff --git a/lib/sanitizer_common/tests/CMakeLists.txt b/lib/sanitizer_common/tests/CMakeLists.txt
index 2e55257da..1bccaa78f 100644
--- a/lib/sanitizer_common/tests/CMakeLists.txt
+++ b/lib/sanitizer_common/tests/CMakeLists.txt
@@ -34,7 +34,8 @@ set(SANITIZER_UNITTESTS
   sanitizer_suppressions_test.cc
   sanitizer_symbolizer_test.cc
   sanitizer_test_main.cc
-  sanitizer_thread_registry_test.cc)
+  sanitizer_thread_registry_test.cc
+  sanitizer_vector_test.cc)
 
 set(SANITIZER_TEST_HEADERS
   sanitizer_pthread_wrappers.h
diff --git a/lib/sanitizer_common/tests/sanitizer_vector_test.cc b/lib/sanitizer_common/tests/sanitizer_vector_test.cc
new file mode 100644
index 000000000..33ed14e19
--- /dev/null
+++ b/lib/sanitizer_common/tests/sanitizer_vector_test.cc
@@ -0,0 +1,42 @@
+//===-- 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_vector.h"
+#include "gtest/gtest.h"
+
+namespace __sanitizer {
+
+TEST(Vector, Basic) {
+  Vector<int> v;
+  EXPECT_EQ(v.Size(), (uptr)0);
+  v.PushBack(42);
+  EXPECT_EQ(v.Size(), (uptr)1);
+  EXPECT_EQ(v[0], 42);
+  v.PushBack(43);
+  EXPECT_EQ(v.Size(), (uptr)2);
+  EXPECT_EQ(v[0], 42);
+  EXPECT_EQ(v[1], 43);
+}
+
+TEST(Vector, Stride) {
+  Vector<int> v;
+  for (int i = 0; i < 1000; i++) {
+    v.PushBack(i);
+    EXPECT_EQ(v.Size(), (uptr)(i + 1));
+    EXPECT_EQ(v[i], i);
+  }
+  for (int i = 0; i < 1000; i++) {
+    EXPECT_EQ(v[i], i);
+  }
+}
+
+}  // namespace __sanitizer