asan/tsan: first version of "stack depot"


git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@162897 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/sanitizer_common/sanitizer_mutex.h b/lib/sanitizer_common/sanitizer_mutex.h
index ca3e2f9..6b6c25d 100644
--- a/lib/sanitizer_common/sanitizer_mutex.h
+++ b/lib/sanitizer_common/sanitizer_mutex.h
@@ -20,9 +20,9 @@
 
 namespace __sanitizer {
 
-class SpinMutex {
+class StaticSpinMutex {
  public:
-  SpinMutex() {
+  void Init() {
     atomic_store(&state_, 0, memory_order_relaxed);
   }
 
@@ -50,7 +50,15 @@
         return;
     }
   }
+};
 
+class SpinMutex : public StaticSpinMutex {
+ public:
+  SpinMutex() {
+    Init();
+  }
+
+ private:
   SpinMutex(const SpinMutex&);
   void operator=(const SpinMutex&);
 };
@@ -93,7 +101,7 @@
   void operator=(const GenericScopedReadLock&);
 };
 
-typedef GenericScopedLock<SpinMutex> SpinMutexLock;
+typedef GenericScopedLock<StaticSpinMutex> SpinMutexLock;
 
 }  // namespace __sanitizer
 
diff --git a/lib/sanitizer_common/sanitizer_stackdepot.cc b/lib/sanitizer_common/sanitizer_stackdepot.cc
new file mode 100644
index 0000000..08d6234
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_stackdepot.cc
@@ -0,0 +1,87 @@
+//===-- sanitizer_stackdepot.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 shared between AddressSanitizer and ThreadSanitizer
+// run-time libraries.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_stackdepot.h"
+#include "sanitizer_common.h"
+#include "sanitizer_mutex.h"
+
+namespace __sanitizer {
+
+struct StackDesc {
+  StackDesc *link;
+  u32 id;
+  uptr hash;
+  uptr size;
+  uptr stack[1];
+};
+
+static struct {
+  StaticSpinMutex mtx;
+  StackDesc *head;
+  u8 *region_pos;
+  u8 *region_end;
+  u32 seq;
+} depot;
+
+static uptr hash(uptr *stack, uptr size) {
+  return 0;
+}
+
+static StackDesc *allocDesc(uptr size) {
+  uptr memsz = sizeof(StackDesc) + (size - 1) * sizeof(uptr);
+  if (depot.region_pos + memsz > depot.region_end) {
+    uptr allocsz = 64*1024;
+    if (allocsz < memsz)
+      allocsz = memsz;
+    depot.region_pos = (u8*)MmapOrDie(allocsz, "stack depot");
+    depot.region_end = depot.region_pos + allocsz;
+  }
+  StackDesc *s = (StackDesc*)depot.region_pos;
+  depot.region_pos += memsz;
+  return s;
+}
+
+u32 StackDepotPut(uptr *stack, uptr size) {
+  if (stack == 0 || size == 0)
+    return 0;
+  uptr h = hash(stack, size);
+  SpinMutexLock l(&depot.mtx);
+  for (StackDesc *s = depot.head; s; s = s->link) {
+    if (s->hash == h && s->size == size
+        && internal_memcmp(s->stack, stack, size * sizeof(uptr)) == 0)
+      return s->id;
+  }
+  StackDesc *s = allocDesc(size);
+  s->id = ++depot.seq;
+  s->hash = h;
+  s->size = size;
+  internal_memcpy(s->stack, stack, size * sizeof(uptr));
+  s->link = depot.head;
+  depot.head = s;
+  return s->id;
+}
+
+uptr *StackDepotGet(u32 id, uptr *size) {
+  if (id == 0)
+    return 0;
+  SpinMutexLock l(&depot.mtx);
+  for (StackDesc *s = depot.head; s; s = s->link) {
+    if (s->id == id) {
+      *size = s->size;
+      return s->stack;
+    }
+  }
+  return 0;
+}
+
+}  // namespace __sanitizer
diff --git a/lib/sanitizer_common/sanitizer_stackdepot.h b/lib/sanitizer_common/sanitizer_stackdepot.h
new file mode 100644
index 0000000..ba0c5c1
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_stackdepot.h
@@ -0,0 +1,29 @@
+//===-- sanitizer_stackdepot.h ----------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is shared between AddressSanitizer and ThreadSanitizer
+// run-time libraries.
+//===----------------------------------------------------------------------===//
+#ifndef SANITIZER_STACKDEPOT_H
+#define SANITIZER_STACKDEPOT_H
+
+#include "sanitizer/common_interface_defs.h"
+
+namespace __sanitizer {
+
+// StackDepot efficiently stores huge amounts of stack traces.
+
+// Maps stack trace to an unique id.
+u32 StackDepotPut(uptr *stack, uptr size);
+// Retrieves a stored stack trace by the id.
+uptr *StackDepotGet(u32 id, uptr *size);
+
+}  // namespace __sanitizer
+
+#endif  // SANITIZER_STACKDEPOT_H
diff --git a/lib/sanitizer_common/tests/sanitizer_stackdepot_test.cc b/lib/sanitizer_common/tests/sanitizer_stackdepot_test.cc
new file mode 100644
index 0000000..eafb90f
--- /dev/null
+++ b/lib/sanitizer_common/tests/sanitizer_stackdepot_test.cc
@@ -0,0 +1,63 @@
+//===-- sanitizer_stackdepot_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/AddressSanitizer runtime.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_stackdepot.h"
+#include "sanitizer_common/sanitizer_internal_defs.h"
+#include "sanitizer_common/sanitizer_libc.h"
+#include "gtest/gtest.h"
+
+namespace __sanitizer {
+
+TEST(SanitizerCommon, StackDepotBasic) {
+  uptr s1[] = {1, 2, 3, 4, 5};
+  u32 i1 = StackDepotPut(s1, ARRAY_SIZE(s1));
+  uptr sz1 = 0;
+  uptr *sp1 = StackDepotGet(i1, &sz1);
+  EXPECT_NE(sp1, (uptr*)0);
+  EXPECT_EQ(sz1, ARRAY_SIZE(s1));
+  EXPECT_EQ(internal_memcmp(sp1?:s1, s1, sizeof(s1)), 0);
+}
+
+TEST(SanitizerCommon, StackDepotAbsent) {
+  uptr sz1 = 0;
+  uptr *sp1 = StackDepotGet(-10, &sz1);
+  EXPECT_EQ(sp1, (uptr*)0);
+}
+
+TEST(SanitizerCommon, StackDepotZero) {
+  u32 i1 = StackDepotPut(0, 0);
+  uptr sz1 = 0;
+  uptr *sp1 = StackDepotGet(i1, &sz1);
+  EXPECT_EQ(sp1, (uptr*)0);
+}
+
+TEST(SanitizerCommon, StackDepotSame) {
+  uptr s1[] = {1, 2, 3, 4, 6};
+  u32 i1 = StackDepotPut(s1, ARRAY_SIZE(s1));
+  u32 i2 = StackDepotPut(s1, ARRAY_SIZE(s1));
+  EXPECT_EQ(i1, i2);
+  uptr sz1 = 0;
+  uptr *sp1 = StackDepotGet(i1, &sz1);
+  EXPECT_NE(sp1, (uptr*)0);
+  EXPECT_EQ(sz1, ARRAY_SIZE(s1));
+  EXPECT_EQ(internal_memcmp(sp1?:s1, s1, sizeof(s1)), 0);
+}
+
+TEST(SanitizerCommon, StackDepotSeveral) {
+  uptr s1[] = {1, 2, 3, 4, 7};
+  u32 i1 = StackDepotPut(s1, ARRAY_SIZE(s1));
+  uptr s2[] = {1, 2, 3, 4, 8, 9};
+  u32 i2 = StackDepotPut(s2, ARRAY_SIZE(s2));
+  EXPECT_NE(i1, i2);
+}
+
+}  // namespace __sanitizer