[scudo][standalone] Add a standalone vector class

Summary:
This CL adds a standalone vector class that will be used by the scoped
strings when they land. We reimplement our own vector class because we
can't use the std library one.

It's mostly borrowed from the current sanitizer_common one, with LLVM
code style changes.

Additionnally a casing change in a function name that slipped through
the previous review (the function isn't used yet).

Reviewers: vitalybuka, eugenis, flowerhack, dmmoore415, mcgrathr, morehouse

Reviewed By: vitalybuka

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

Tags: #llvm, #sanitizers

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

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

5 files changed, 167 insertions, 4 deletions

diff --git a/lib/scudo/standalone/CMakeLists.txt b/lib/scudo/standalone/CMakeLists.txt
index 7a3dad673..3957fa2e8 100644
--- a/lib/scudo/standalone/CMakeLists.txt
+++ b/lib/scudo/standalone/CMakeLists.txt
@@ -39,12 +39,13 @@ set(SCUDO_SOURCES
   linux.cc)
 
 set(SCUDO_HEADERS
-  platform.h
-  internal_defs.h
   atomic_helpers.h
+  internal_defs.h
+  linux.h
   list.h
   mutex.h
-  linux.h)
+  platform.h
+  vector.h)
 
 if(COMPILER_RT_HAS_SCUDO_STANDALONE)
   add_compiler_rt_object_libraries(RTScudoStandalone
diff --git a/lib/scudo/standalone/common.h b/lib/scudo/standalone/common.h
index 6bdf9df6c..89b8d11ab 100644
--- a/lib/scudo/standalone/common.h
+++ b/lib/scudo/standalone/common.h
@@ -27,7 +27,7 @@ INLINE constexpr uptr roundUpTo(uptr X, uptr Boundary) {
   return (X + Boundary - 1) & ~(Boundary - 1);
 }
 
-INLINE constexpr uptr RoundDownTo(uptr X, uptr Boundary) {
+INLINE constexpr uptr roundDownTo(uptr X, uptr Boundary) {
   return X & ~(Boundary - 1);
 }
 
diff --git a/lib/scudo/standalone/tests/CMakeLists.txt b/lib/scudo/standalone/tests/CMakeLists.txt
index fe63dcf04..d898d8a70 100644
--- a/lib/scudo/standalone/tests/CMakeLists.txt
+++ b/lib/scudo/standalone/tests/CMakeLists.txt
@@ -53,6 +53,7 @@ set(SCUDO_UNIT_TEST_SOURCES
   list_test.cc
   map_test.cc
   mutex_test.cc
+  vector_test.cc
   scudo_unit_test_main.cc)
 
 add_scudo_unittest(ScudoUnitTest
diff --git a/lib/scudo/standalone/tests/vector_test.cc b/lib/scudo/standalone/tests/vector_test.cc
new file mode 100644
index 000000000..ebfcc43cc
--- /dev/null
+++ b/lib/scudo/standalone/tests/vector_test.cc
@@ -0,0 +1,43 @@
+//===-- vector_test.cc ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "vector.h"
+
+#include "gtest/gtest.h"
+
+TEST(ScudoVectorTest, Basic) {
+  scudo::Vector<int> V;
+  EXPECT_EQ(V.size(), 0U);
+  V.push_back(42);
+  EXPECT_EQ(V.size(), 1U);
+  EXPECT_EQ(V[0], 42);
+  V.push_back(43);
+  EXPECT_EQ(V.size(), 2U);
+  EXPECT_EQ(V[0], 42);
+  EXPECT_EQ(V[1], 43);
+}
+
+TEST(ScudoVectorTest, Stride) {
+  scudo::Vector<int> V;
+  for (int i = 0; i < 1000; i++) {
+    V.push_back(i);
+    EXPECT_EQ(V.size(), i + 1U);
+    EXPECT_EQ(V[i], i);
+  }
+  for (int i = 0; i < 1000; i++)
+    EXPECT_EQ(V[i], i);
+}
+
+TEST(ScudoVectorTest, ResizeReduction) {
+  scudo::Vector<int> V;
+  V.push_back(0);
+  V.push_back(0);
+  EXPECT_EQ(V.size(), 2U);
+  V.resize(1);
+  EXPECT_EQ(V.size(), 1U);
+}
diff --git a/lib/scudo/standalone/vector.h b/lib/scudo/standalone/vector.h
new file mode 100644
index 000000000..3cb4005ed
--- /dev/null
+++ b/lib/scudo/standalone/vector.h
@@ -0,0 +1,118 @@
+//===-- vector.h ------------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SCUDO_VECTOR_H_
+#define SCUDO_VECTOR_H_
+
+#include "common.h"
+
+#include <string.h>
+
+namespace scudo {
+
+// A low-level vector based on map. May incur a significant memory overhead for
+// small vectors. The current implementation supports only POD types.
+template <typename T> class VectorNoCtor {
+public:
+  void init(uptr InitialCapacity) {
+    CapacityBytes = 0;
+    Size = 0;
+    Data = nullptr;
+    reserve(InitialCapacity);
+  }
+  void destroy() {
+    if (Data)
+      unmap(Data, CapacityBytes);
+  }
+  T &operator[](uptr I) {
+    DCHECK_LT(I, Size);
+    return Data[I];
+  }
+  const T &operator[](uptr I) const {
+    DCHECK_LT(I, Size);
+    return Data[I];
+  }
+  void push_back(const T &Element) {
+    DCHECK_LE(Size, capacity());
+    if (Size == capacity()) {
+      const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1);
+      reallocate(NewCapacity);
+    }
+    memcpy(&Data[Size++], &Element, sizeof(T));
+  }
+  T &back() {
+    DCHECK_GT(Size, 0);
+    return Data[Size - 1];
+  }
+  void pop_back() {
+    DCHECK_GT(Size, 0);
+    Size--;
+  }
+  uptr size() const { return Size; }
+  const T *data() const { return Data; }
+  T *data() { return Data; }
+  uptr capacity() const { return CapacityBytes / sizeof(T); }
+  void reserve(uptr NewSize) {
+    // Never downsize internal buffer.
+    if (NewSize > capacity())
+      reallocate(NewSize);
+  }
+  void resize(uptr NewSize) {
+    if (NewSize > Size) {
+      reserve(NewSize);
+      memset(&Data[Size], 0, sizeof(T) * (NewSize - Size));
+    }
+    Size = NewSize;
+  }
+
+  void clear() { Size = 0; }
+  bool empty() const { return size() == 0; }
+
+  const T *begin() const { return data(); }
+  T *begin() { return data(); }
+  const T *end() const { return data() + size(); }
+  T *end() { return data() + size(); }
+
+private:
+  void reallocate(uptr NewCapacity) {
+    DCHECK_GT(NewCapacity, 0);
+    DCHECK_LE(Size, NewCapacity);
+    const uptr NewCapacityBytes =
+        roundUpTo(NewCapacity * sizeof(T), getPageSizeCached());
+    T *NewData = (T *)map(nullptr, NewCapacityBytes, "scudo:vector");
+    if (Data) {
+      memcpy(NewData, Data, Size * sizeof(T));
+      unmap(Data, CapacityBytes);
+    }
+    Data = NewData;
+    CapacityBytes = NewCapacityBytes;
+  }
+
+  T *Data;
+  uptr CapacityBytes;
+  uptr Size;
+};
+
+template <typename T> class Vector : public VectorNoCtor<T> {
+public:
+  Vector() { VectorNoCtor<T>::init(1); }
+  explicit Vector(uptr Count) {
+    VectorNoCtor<T>::init(Count);
+    this->resize(Count);
+  }
+  ~Vector() { VectorNoCtor<T>::destroy(); }
+  // Disallow copies and moves.
+  Vector(const Vector &) = delete;
+  Vector &operator=(const Vector &) = delete;
+  Vector(Vector &&) = delete;
+  Vector &operator=(Vector &&) = delete;
+};
+
+} // namespace scudo
+
+#endif // SCUDO_VECTOR_H_