Index: lib/scudo/standalone/CMakeLists.txt =================================================================== --- lib/scudo/standalone/CMakeLists.txt +++ lib/scudo/standalone/CMakeLists.txt @@ -40,6 +40,7 @@ set(SCUDO_HEADERS atomic_helpers.h + bytemap.h internal_defs.h linux.h list.h Index: lib/scudo/standalone/bytemap.h =================================================================== --- lib/scudo/standalone/bytemap.h +++ 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/tests/CMakeLists.txt =================================================================== --- lib/scudo/standalone/tests/CMakeLists.txt +++ lib/scudo/standalone/tests/CMakeLists.txt @@ -50,6 +50,7 @@ set(SCUDO_UNIT_TEST_SOURCES atomic_test.cc + bytemap_test.cc list_test.cc map_test.cc mutex_test.cc Index: lib/scudo/standalone/tests/bytemap_test.cc =================================================================== --- lib/scudo/standalone/tests/bytemap_test.cc +++ lib/scudo/standalone/tests/bytemap_test.cc @@ -0,0 +1,73 @@ +//===-- 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 + +template void testMap(T &Map, scudo::uptr Size) { + Map.init(); + for (scudo::uptr I = 0; I < Size; I += 7) + Map.set(I, (I % 100) + 1); + for (scudo::uptr J = 0; J < Size; J++) { + if (J % 7) + EXPECT_EQ(Map[J], 0); + else + EXPECT_EQ(Map[J], (J % 100) + 1); + } +} + +TEST(ScudoByteMapTest, FlatByteMap) { + const scudo::uptr Size = 1U << 10; + scudo::FlatByteMap Map; + testMap(Map, Size); +} + +TEST(ScudoByteMapTest, TwoLevelByteMap) { + const scudo::uptr Size1 = 1U << 6, Size2 = 1U << 12; + scudo::TwoLevelByteMap Map; + testMap(Map, Size1 * Size2); + 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(); +}