[tsan] first step in implementing a custom allocator for tsan (and msan) which saves precious shadow

llvm-svn: 158913

4 files changed, 130 insertions, 4 deletions

diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_allocator64.h b/compiler-rt/lib/sanitizer_common/sanitizer_allocator64.h
new file mode 100644
index 00000000000..2129681210e
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_allocator64.h
@@ -0,0 +1,80 @@
+//===-- sanitizer_allocator64.h ---------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Specialized allocator which works only in 64-bit address space.
+// To be used by ThreadSanitizer, MemorySanitizer and possibly other tools.
+// The main feature of this allocator is that the header is located far away
+// from the user memory region, so that the tool does not use extra shadow
+// for the header.
+//
+// Status: not yet ready.
+//===----------------------------------------------------------------------===//
+#ifndef SANITIZER_ALLOCATOR_H
+#define SANITIZER_ALLOCATOR_H
+
+#include "sanitizer_common.h"
+#include "sanitizer_internal_defs.h"
+
+namespace __sanitizer {
+
+// Maps size class to size and back.
+class DefaultSizeClassMap {
+ private:
+  // Here we use a spline composed of 5 polynomials of oder 1.
+  // The first size class is l0, then the classes go with step s0
+  // untill they reach l1, after which they go with step s1 and so on.
+  // Steps should be powers of two for cheap division.
+  // The size of the last size class should be a power of two.
+  // There should be at most 256 size classes.
+  static const uptr l0 = 1 << 4;
+  static const uptr l1 = 1 << 9;
+  static const uptr l2 = 1 << 12;
+  static const uptr l3 = 1 << 15;
+  static const uptr l4 = 1 << 18;
+  static const uptr l5 = 1 << 21;
+
+  static const uptr s0 = 1 << 4;
+  static const uptr s1 = 1 << 6;
+  static const uptr s2 = 1 << 9;
+  static const uptr s3 = 1 << 12;
+  static const uptr s4 = 1 << 15;
+
+  static const uptr u0 = 0  + (l1 - l0) / s0;
+  static const uptr u1 = u0 + (l2 - l1) / s1;
+  static const uptr u2 = u1 + (l3 - l2) / s2;
+  static const uptr u3 = u2 + (l4 - l3) / s3;
+  static const uptr u4 = u3 + (l5 - l4) / s4;
+
+ public:
+  static const uptr kNumClasses = u4 + 1;
+  static const uptr kMaxSize = l5;
+
+  COMPILER_CHECK(kNumClasses <= 256);
+  COMPILER_CHECK((kMaxSize & (kMaxSize - 1)) == 0);
+
+  static uptr Size(uptr size_class) {
+    if (size_class <= u0) return l0 + s0 * (size_class - 0);
+    if (size_class <= u1) return l1 + s1 * (size_class - u0);
+    if (size_class <= u2) return l2 + s2 * (size_class - u1);
+    if (size_class <= u3) return l3 + s3 * (size_class - u2);
+    if (size_class <= u4) return l4 + s4 * (size_class - u3);
+    return 0;
+  }
+  static uptr Class(uptr size) {
+    if (size <= l1) return 0  + (size - l0 + s0 - 1) / s0;
+    if (size <= l2) return u0 + (size - l1 + s1 - 1) / s1;
+    if (size <= l3) return u1 + (size - l2 + s2 - 1) / s2;
+    if (size <= l4) return u2 + (size - l3 + s3 - 1) / s3;
+    if (size <= l5) return u3 + (size - l4 + s4 - 1) / s4;
+    return 0;
+  }
+};
+
+}  // namespace __sanitizer
+
+#endif  // SANITIZER_ALLOCATOR_H
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_internal_defs.h b/compiler-rt/lib/sanitizer_common/sanitizer_internal_defs.h
index 8003aaec79b..5e0fb6945a4 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_internal_defs.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_internal_defs.h
@@ -107,6 +107,12 @@ void NORETURN CheckFailed(const char *file, int line, const char *cond,
 
 #define UNIMPLEMENTED() CHECK("unimplemented" && 0)
 
+#define COMPILER_CHECK(pred) IMPL_COMPILER_ASSERT(pred, __LINE__)
+
+#define IMPL_PASTE(a, b) a##b
+#define IMPL_COMPILER_ASSERT(pred, line) \
+    typedef char IMPL_PASTE(assertion_failed_##_, line)[2*(int)(pred)-1];
+
 // Limits for integral types. We have to redefine it in case we don't
 // have stdint.h (like in Visual Studio 9).
 #if __WORDSIZE == 64
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_allocator64_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_allocator64_test.cc
new file mode 100644
index 00000000000..76220a137d4
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_allocator64_test.cc
@@ -0,0 +1,43 @@
+//===-- sanitizer_allocator64_test.cc -------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Tests for sanitizer_allocator64.h.
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_allocator64.h"
+#include "gtest/gtest.h"
+
+TEST(SanitizerCommon, DefaultSizeClassMap) {
+  typedef DefaultSizeClassMap SCMap;
+
+  for (uptr i = 0; i < SCMap::kNumClasses; i++) {
+    // printf("% 3ld: % 5ld (%4lx);   ", i, SCMap::Size(i), SCMap::Size(i));
+    printf("c%ld => %ld  ", i, SCMap::Size(i));
+    if ((i % 8) == 7)
+      printf("\n");
+  }
+  printf("\n");
+
+  for (uptr c = 0; c < SCMap::kNumClasses; c++) {
+    uptr s = SCMap::Size(c);
+    CHECK_EQ(SCMap::Class(s), c);
+    if (c != SCMap::kNumClasses - 1)
+      CHECK_EQ(SCMap::Class(s + 1), c + 1);
+    CHECK_EQ(SCMap::Class(s - 1), c);
+    if (c)
+      CHECK_GT(SCMap::Size(c), SCMap::Size(c-1));
+  }
+  CHECK_EQ(SCMap::Class(SCMap::kMaxSize + 1), 0);
+
+  for (uptr s = 1; s <= SCMap::kMaxSize; s++) {
+    uptr c = SCMap::Class(s);
+    CHECK_LT(c, SCMap::kNumClasses);
+    CHECK_GE(SCMap::Size(c), s);
+    if (c > 0)
+      CHECK_LT(SCMap::Size(c-1), s);
+  }
+}
diff --git a/compiler-rt/lib/tsan/Makefile.old b/compiler-rt/lib/tsan/Makefile.old
index d8cbf154cfa..5740315ca15 100644
--- a/compiler-rt/lib/tsan/Makefile.old
+++ b/compiler-rt/lib/tsan/Makefile.old
@@ -21,7 +21,7 @@ RTL_TEST_SRC=$(wildcard rtl_tests/*.cc)
 RTL_TEST_OBJ=$(patsubst %.cc,%.o,$(RTL_TEST_SRC))
 UNIT_TEST_SRC=$(wildcard unit_tests/*_test.cc)
 UNIT_TEST_OBJ=$(patsubst %.cc,%.o,$(UNIT_TEST_SRC))
-UNIT_TEST_HDR=$(wildcard rtl/*.h)
+UNIT_TEST_HDR=$(wildcard rtl/*.h) $(wildcard ../sanitizer_common/*.h)
 
 INCLUDES=-Irtl -I.. $(GTEST_INCLUDE)
 
@@ -44,9 +44,6 @@ libtsan:
 %.o: %.cc $(UNIT_TEST_HDR)
 	$(CXX) $(CXXFLAGS) $(CFLAGS) $(INCLUDES) -o $@ -c $<
 
-#rtl_tests/%.o: rtl_tests/%.cc $(LIBTSAN_HEADERS)
-#	$(CXX) $(CXXFLAGS) $(CFLAGS) $(INCLUDES) -o $@ -c $<
-
 tsan_test: $(TEST_OBJ) $(UNIT_TEST_OBJ) $(RTL_TEST_OBJ) \
            $(SANITIZER_COMMON_TESTS_OBJ) $(LIBTSAN) $(GTEST_LIB)
 	$(CXX) $^ -o $@ $(LDFLAGS)