tsan: refactor storage of meta information for heap blocks and sync objects

The new storage (MetaMap) is based on direct shadow (instead of a hashmap + per-block lists).
This solves a number of problems:
 - eliminates quadratic behaviour in SyncTab::GetAndLock (https://code.google.com/p/thread-sanitizer/issues/detail?id=26)
 - eliminates contention in SyncTab
 - eliminates contention in internal allocator during allocation of sync objects
 - removes a bunch of ad-hoc code in java interface
 - reduces java shadow from 2x to 1/2x
 - allows to memorize heap block meta info for Java and Go
 - allows to cleanup sync object meta info for Go
 - which in turn enabled deadlock detector for Go

llvm-svn: 209810

1 files changed, 55 insertions, 0 deletions

diff --git a/compiler-rt/lib/tsan/tests/unit/tsan_dense_alloc_test.cc b/compiler-rt/lib/tsan/tests/unit/tsan_dense_alloc_test.cc
new file mode 100644
index 00000000000..fc9e4cbb7df
--- /dev/null
+++ b/compiler-rt/lib/tsan/tests/unit/tsan_dense_alloc_test.cc
@@ -0,0 +1,55 @@
+//===-- tsan_dense_alloc_test.cc ------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of ThreadSanitizer (TSan), a race detector.
+//
+//===----------------------------------------------------------------------===//
+#include "tsan_dense_alloc.h"
+#include "tsan_rtl.h"
+#include "tsan_mman.h"
+#include "gtest/gtest.h"
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <map>
+
+namespace __tsan {
+
+TEST(DenseSlabAlloc, Basic) {
+  typedef DenseSlabAlloc<int, 128, 128> Alloc;
+  typedef Alloc::Cache Cache;
+  typedef Alloc::IndexT IndexT;
+  const int N = 1000;
+
+  Alloc alloc;
+  Cache cache;
+  alloc.InitCache(&cache);
+
+  IndexT blocks[N];
+  for (int ntry = 0; ntry < 3; ntry++) {
+    for (int i = 0; i < N; i++) {
+      IndexT idx = alloc.Alloc(&cache);
+      blocks[i] = idx;
+      EXPECT_NE(idx, 0);
+      int *v = alloc.Map(idx);
+      *v = i;
+    }
+
+    for (int i = 0; i < N; i++) {
+      IndexT idx = blocks[i];
+      int *v = alloc.Map(idx);
+      EXPECT_EQ(*v, i);
+      alloc.Free(&cache, idx);
+    }
+
+    alloc.FlushCache(&cache);
+  }
+}
+
+}  // namespace __tsan