[scudo][standalone] Add a standalone vector class

[cryptoad]

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).

[vitalybuka]

lib/scudo/standalone/vector.h

112

memcmp here does not look right (as in sanitizer common), as documented it works only for POD
if you don't need these operators, maybe it's safe just to remove them

[cryptoad]

lib/scudo/standalone/vector.h

112

I removed both operators & swap that is for sure not used.
Some accessors (begin/end) are currently not used but are low cost so I figure I would leave them.

[cryptoad]

Removing some unused functions.

[cryptoad]

Rebasing.

lib/scudo/standalone/CMakeLists.txt

 endif()
 
 set(SCUDO_SOURCES
   common.cc
   fuchsia.cc
   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
     ARCHS ${SCUDO_STANDALONE_SUPPORTED_ARCH}
     SOURCES ${SCUDO_SOURCES}
     ADDITIONAL_HEADERS ${SCUDO_HEADERS}
     CFLAGS ${SCUDO_CFLAGS})
 

lib/scudo/standalone/common.h

template <class Dest, class Source> INLINE Dest bit_cast(const Source &S) {
   memcpy(&D, &S, sizeof(D));
   return D;
 }
 
 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);
 }
 
 INLINE constexpr bool isAligned(uptr X, uptr Alignment) {
   return (X & (Alignment - 1)) == 0;
 }
 
 template <class T> constexpr T Min(T A, T B) { return A < B ? A : B; }

lib/scudo/standalone/tests/CMakeLists.txt

macro(add_scudo_unittest testname)
   endif()
 endmacro()
 
 set(SCUDO_UNIT_TEST_SOURCES
   atomic_test.cc
   list_test.cc
   map_test.cc
   mutex_test.cc
+  vector_test.cc
   scudo_unit_test_main.cc)
 
 add_scudo_unittest(ScudoUnitTest
   SOURCES ${SCUDO_UNIT_TEST_SOURCES})

lib/scudo/standalone/tests/vector_test.cc

+//===-- 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);
+}

lib/scudo/standalone/vector.h

+//===-- 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_