[scudo][standalone] Adding vector, bytemap & stats

[cryptoad]

Summary

This CL adds a few more classes and some tests:

• bytemap: to be used by the primary when it lands;
• stats: to be used by the primary & secondary;
• vector: to be used by scoped strings when they land.

Code is clang-format with llvm style.

[vitalybuka]

lib/scudo/standalone/CMakeLists.txt

44

This patch should be 3 patches.

lib/scudo/standalone/bytemap.h

58

I assume this is mostly fork from sanitizer_common.
I do not insists, but it would be nice to do that it two steps:

1. Patch with unmodified copy (maybe single large patch for all files used in standalone version) so that fabricator shows this as a copy
2. Patch with changes

lib/scudo/standalone/vector.h

20

have you considered to use std::vector with custom allocator?

[cryptoad]

Redoing as 3 separate patches as per Vitaly's request. With some replies to comments.

lib/scudo/standalone/CMakeLists.txt

44

I will redo that in 3 patches.

lib/scudo/standalone/bytemap.h

58

So this is tricky.
There are enough form changes to have a diff be significantly unreadable:

• g3 code style becomes llvm code style (changing casing, function names, variable names)
• g3 clang-format becomes llvm code format (spacing, line cuts)

Added on top of that are content changes (not as many platforms supported, less backward compat "hacks").

lib/scudo/standalone/vector.h

20

We are compiling with -nostdinc++ and no standard c++ library as well (to be included in a libc).
So we are reimplementing basic c++ classes like that.

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
+  bytemap.h
+  internal_defs.h
+  linux.h
   list.h
   mutex.h
-  linux.h)
+  platform.h
+  stats.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/bytemap.h

+//===-- bytemap.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_BYTEMAP_H_
+#define SCUDO_BYTEMAP_H_
+
+#include "atomic_helpers.h"
+#include "common.h"
+#include "mutex.h"
+
+namespace scudo {
+
+template <uptr Size> class FlatByteMap {
+public:
+  void initLinkerInitialized() {
+    Map = reinterpret_cast<u8 *>(map(nullptr, Size, "scudo:bytemap"));
+  }
+  void init() { initLinkerInitialized(); }
+
+  void set(uptr Index, u8 Value) {
+    DCHECK_LT(Index, Size);
+    DCHECK_EQ(0U, Map[Index]);
+    Map[Index] = Value;
+  }
+  u8 operator[](uptr Index) {
+    DCHECK_LT(Index, Size);
+    return Map[Index];
+  }
+
+private:
+  u8 *Map;
+};
+
+template <uptr Level1Size, uptr Level2Size> class TwoLevelByteMap {
+public:
+  void initLinkerInitialized() {
+    Level1Map = reinterpret_cast<atomic_uptr *>(
+        map(nullptr, sizeof(atomic_uptr) * Level1Size, "scudo:bytemap"));
+  }
+  void init() {
+    initLinkerInitialized();
+    Mutex.init();
+  }
+
+  void reset() {
+    for (uptr I = 0; I < Level1Size; I++) {
+      u8 *P = get(I);
+      if (!P)
+        continue;
+      unmap(P, Level2Size);
+    }
+    memset(Level1Map, 0, sizeof(atomic_uptr) * Level1Size);
+  }
+
+  uptr size() const { return Level1Size * Level2Size; }
+
+  void set(uptr Index, u8 Value) {
+    DCHECK_LT(Index, Level1Size * Level2Size);
+    u8 *Level2Map = getOrCreate(Index / Level2Size);
+    DCHECK_EQ(0U, Level2Map[Index % Level2Size]);
+    Level2Map[Index % Level2Size] = Value;
+  }
+
+  u8 operator[](uptr Index) const {
+    DCHECK_LT(Index, Level1Size * Level2Size);
+    u8 *Level2Map = get(Index / Level2Size);
+    if (!Level2Map)
+      return 0;
+    return Level2Map[Index % Level2Size];
+  }
+
+private:
+  u8 *get(uptr Index) const {
+    DCHECK_LT(Index, Level1Size);
+    return reinterpret_cast<u8 *>(
+        atomic_load(&Level1Map[Index], memory_order_acquire));
+  }
+
+  u8 *getOrCreate(uptr Index) {
+    u8 *Res = get(Index);
+    if (!Res) {
+      SpinMutexLock L(&Mutex);
+      if (!(Res = get(Index))) {
+        Res = reinterpret_cast<u8 *>(map(nullptr, Level2Size, "scudo:bytemap"));
+        atomic_store(&Level1Map[Index], reinterpret_cast<uptr>(Res),
+                     memory_order_release);
+      }
+    }
+    return Res;
+  }
+
+  atomic_uptr *Level1Map;
+  StaticSpinMutex Mutex;
+};
+
+} // namespace scudo
+
+#endif // SCUDO_BYTEMAP_H_

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/stats.h

+//===-- stats.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_STATS_H_
+#define SCUDO_STATS_H_
+
+#include "atomic_helpers.h"
+#include "mutex.h"
+
+#include <string.h>
+
+namespace scudo {
+
+// Memory allocator statistics
+enum StatType { StatAllocated, StatMapped, StatCount };
+
+typedef uptr StatCounters[StatCount];
+
+// Per-thread Stats, live in per-thread cache.
+class LocalStats {
+public:
+  void initLinkerInitialized() {}
+  void init() { memset(this, 0, sizeof(*this)); }
+
+  void add(StatType I, uptr V) {
+    V += atomic_load_relaxed(&StatsArray[I]);
+    atomic_store_relaxed(&StatsArray[I], V);
+  }
+
+  void sub(StatType I, uptr V) {
+    V = atomic_load_relaxed(&StatsArray[I]) - V;
+    atomic_store_relaxed(&StatsArray[I], V);
+  }
+
+  void set(StatType I, uptr V) { atomic_store_relaxed(&StatsArray[I], V); }
+
+  uptr get(StatType I) const { return atomic_load_relaxed(&StatsArray[I]); }
+
+private:
+  friend class GlobalStats;
+  atomic_uptr StatsArray[StatCount];
+  LocalStats *Next;
+  LocalStats *Prev;
+};
+
+// Global stats, used for aggregation and querying.
+class GlobalStats : public LocalStats {
+public:
+  void initLinkerInitialized() {
+    Next = this;
+    Prev = this;
+  }
+  void init() {
+    memset(this, 0, sizeof(*this));
+    initLinkerInitialized();
+  }
+
+  void link(LocalStats *S) {
+    SpinMutexLock l(&Mutex);
+    S->Next = Next;
+    S->Prev = this;
+    Next->Prev = S;
+    Next = S;
+  }
+
+  void unlink(LocalStats *S) {
+    SpinMutexLock l(&Mutex);
+    S->Prev->Next = S->Next;
+    S->Next->Prev = S->Prev;
+    for (uptr I = 0; I < StatCount; I++)
+      add(StatType(I), S->get(StatType(I)));
+  }
+
+  void get(StatCounters S) const {
+    memset(S, 0, StatCount * sizeof(uptr));
+    SpinMutexLock l(&Mutex);
+    const LocalStats *Stats = this;
+    for (;;) {
+      for (uptr I = 0; I < StatCount; I++)
+        S[I] += Stats->get(StatType(I));
+      Stats = Stats->Next;
+      if (Stats == this)
+        break;
+    }
+    // All Stats must be non-negative.
+    for (uptr I = 0; I < StatCount; I++)
+      S[I] = static_cast<sptr>(S[I]) >= 0 ? S[I] : 0;
+  }
+
+private:
+  mutable StaticSpinMutex Mutex;
+};
+
+} // namespace scudo
+
+#endif // SCUDO_STATS_H_

lib/scudo/standalone/tests/CMakeLists.txt

foreach(arch ${SCUDO_TEST_ARCH})
         CFLAGS ${SCUDO_UNITTEST_CFLAGS}
         LINK_FLAGS ${LINK_FLAGS})
     endforeach()
   endif()
 endmacro()
 
 set(SCUDO_UNIT_TEST_SOURCES
   atomic_test.cc
+  bytemap_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/bytemap_test.cc

+//===-- bytemap_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 "bytemap.h"
+
+#include "gtest/gtest.h"
+
+#include <string.h>
+
+TEST(ScudoByteMapTest, TwoLevelByteMap) {
+  const scudo::uptr Size1 = 1U << 6, Size2 = 1U << 12;
+  const scudo::uptr N = Size1 * Size2;
+  scudo::TwoLevelByteMap<Size1, Size2> Map;
+  Map.init();
+  for (scudo::uptr I = 0; I < N; I += 7)
+    Map.set(I, (I % 100) + 1);
+  for (scudo::uptr J = 0; J < N; J++) {
+    if (J % 7)
+      EXPECT_EQ(Map[J], 0);
+    else
+      EXPECT_EQ(Map[J], (J % 100) + 1);
+  }
+  Map.reset();
+}
+
+using TestByteMap = scudo::TwoLevelByteMap<1U << 12, 1U << 13>;
+
+struct TestByteMapParam {
+  TestByteMap *Map;
+  scudo::uptr Shard;
+  scudo::uptr NumberOfShards;
+};
+
+void *populateByteMap(void *Param) {
+  TestByteMapParam *P = reinterpret_cast<TestByteMapParam *>(Param);
+  for (scudo::uptr I = P->Shard; I < P->Map->size(); I += P->NumberOfShards) {
+    scudo::u8 V = static_cast<scudo::u8>((I % 100) + 1);
+    P->Map->set(I, V);
+    EXPECT_EQ((*P->Map)[I], V);
+  }
+  return 0;
+}
+
+TEST(ScudoByteMapTest, ThreadedTwoLevelByteMap) {
+  TestByteMap Map;
+  Map.init();
+  static const scudo::uptr NumberOfThreads = 16U;
+  pthread_t T[NumberOfThreads];
+  TestByteMapParam P[NumberOfThreads];
+  for (scudo::uptr I = 0; I < NumberOfThreads; I++) {
+    P[I].Map = &Map;
+    P[I].Shard = I;
+    P[I].NumberOfShards = NumberOfThreads;
+    pthread_create(&T[I], 0, populateByteMap, &P[I]);
+  }
+  for (scudo::uptr I = 0; I < NumberOfThreads; I++)
+    pthread_join(T[I], 0);
+  Map.reset();
+}

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(); }
+
+  void swap(VectorNoCtor &Other) {
+    Swap(Data, Other.Data);
+    Swap(CapacityBytes, Other.CapacityBytes);
+    Swap(Size, Other.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>
+bool operator==(const VectorNoCtor<T> &Lhs, const VectorNoCtor<T> &Rhs) {
+  if (Lhs.size() != Rhs.size())
+    return false;
+  return memcmp(Lhs.data(), Rhs.data(), Lhs.size() * sizeof(T)) == 0;
+}
+
+template <typename T>
+bool operator!=(const VectorNoCtor<T> &Lhs, const VectorNoCtor<T> &Rhs) {
+  return !(Lhs == Rhs);
+}
+
+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_