Index: lib/scudo/standalone/CMakeLists.txt =================================================================== --- lib/scudo/standalone/CMakeLists.txt +++ lib/scudo/standalone/CMakeLists.txt @@ -39,12 +39,15 @@ 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 Index: lib/scudo/standalone/bytemap.h =================================================================== --- /dev/null +++ lib/scudo/standalone/bytemap.h @@ -0,0 +1,103 @@ +//===-- 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 class FlatByteMap { +public: + void initLinkerInitialized() { + Map = reinterpret_cast(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 class TwoLevelByteMap { +public: + void initLinkerInitialized() { + Level1Map = reinterpret_cast( + 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( + 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(map(nullptr, Level2Size, "scudo:bytemap")); + atomic_store(&Level1Map[Index], reinterpret_cast(Res), + memory_order_release); + } + } + return Res; + } + + atomic_uptr *Level1Map; + StaticSpinMutex Mutex; +}; + +} // namespace scudo + +#endif // SCUDO_BYTEMAP_H_ Index: lib/scudo/standalone/common.h =================================================================== --- lib/scudo/standalone/common.h +++ lib/scudo/standalone/common.h @@ -27,7 +27,7 @@ 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); } Index: lib/scudo/standalone/stats.h =================================================================== --- /dev/null +++ lib/scudo/standalone/stats.h @@ -0,0 +1,101 @@ +//===-- 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 + +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(S[I]) >= 0 ? S[I] : 0; + } + +private: + mutable StaticSpinMutex Mutex; +}; + +} // namespace scudo + +#endif // SCUDO_STATS_H_ Index: lib/scudo/standalone/tests/CMakeLists.txt =================================================================== --- lib/scudo/standalone/tests/CMakeLists.txt +++ lib/scudo/standalone/tests/CMakeLists.txt @@ -50,9 +50,11 @@ 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 Index: lib/scudo/standalone/tests/bytemap_test.cc =================================================================== --- /dev/null +++ lib/scudo/standalone/tests/bytemap_test.cc @@ -0,0 +1,64 @@ +//===-- 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 + +TEST(ScudoByteMapTest, TwoLevelByteMap) { + const scudo::uptr Size1 = 1U << 6, Size2 = 1U << 12; + const scudo::uptr N = Size1 * Size2; + scudo::TwoLevelByteMap 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(Param); + for (scudo::uptr I = P->Shard; I < P->Map->size(); I += P->NumberOfShards) { + scudo::u8 V = static_cast((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 = ⤅ + 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(); +} Index: lib/scudo/standalone/tests/vector_test.cc =================================================================== --- /dev/null +++ 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 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 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 V; + V.push_back(0); + V.push_back(0); + EXPECT_EQ(V.size(), 2U); + V.resize(1); + EXPECT_EQ(V.size(), 1U); +} Index: lib/scudo/standalone/vector.h =================================================================== --- /dev/null +++ lib/scudo/standalone/vector.h @@ -0,0 +1,136 @@ +//===-- 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 + +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 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 +bool operator==(const VectorNoCtor &Lhs, const VectorNoCtor &Rhs) { + if (Lhs.size() != Rhs.size()) + return false; + return memcmp(Lhs.data(), Rhs.data(), Lhs.size() * sizeof(T)) == 0; +} + +template +bool operator!=(const VectorNoCtor &Lhs, const VectorNoCtor &Rhs) { + return !(Lhs == Rhs); +} + +template class Vector : public VectorNoCtor { +public: + Vector() { VectorNoCtor::init(1); } + explicit Vector(uptr Count) { + VectorNoCtor::init(Count); + this->resize(Count); + } + ~Vector() { VectorNoCtor::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_