[scudo][standalone] Add bytemap classes

Summary:
The bytemap classes will be used by the primary32 allocator to associate
classes with memory regions. It's similar to the sanitizer_common one
except for the fact that the base (level1) maps are mapped instead of
being static to reduce the memory footprint of an uninitialized allocator.

Reviewers: vitalybuka, eugenis, morehouse, flowerhack, dmmoore415, mcgrathr

Reviewed By: vitalybuka, morehouse

Subscribers: mgorny, delcypher, jfb, #sanitizers, llvm-commits

Tags: #llvm, #sanitizers

Differential Revision: https://reviews.llvm.org/D58723

llvm-svn: 355416

1 files changed, 73 insertions, 0 deletions

diff --git a/compiler-rt/lib/scudo/standalone/tests/bytemap_test.cc b/compiler-rt/lib/scudo/standalone/tests/bytemap_test.cc
new file mode 100644
index 00000000000..c83ff3f61f5
--- /dev/null
+++ b/compiler-rt/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 <string.h>
+
+template <typename T> 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<Size> Map;
+  testMap(Map, Size);
+}
+
+TEST(ScudoByteMapTest, TwoLevelByteMap) {
+  const scudo::uptr Size1 = 1U << 6, Size2 = 1U << 12;
+  scudo::TwoLevelByteMap<Size1, Size2> 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<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();
+}