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_