[sanitizer] Add a fast version of StackDepotGet() for use in LSan.

Add a class that holds a snapshot of the StackDepot optimized for querying by
ID. This allows us to speed up LSan dramatically.

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@189217 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 34 insertions, 0 deletions

diff --git a/lib/sanitizer_common/sanitizer_stackdepot.cc b/lib/sanitizer_common/sanitizer_stackdepot.cc
index 08e523832..2793bd071 100644
--- a/lib/sanitizer_common/sanitizer_stackdepot.cc
+++ b/lib/sanitizer_common/sanitizer_stackdepot.cc
@@ -201,4 +201,38 @@ const uptr *StackDepotGet(u32 id, uptr *size) {
   return 0;
 }
 
+bool StackDepotReverseMap::IdDescPair::IdComparator(
+    const StackDepotReverseMap::IdDescPair &a,
+    const StackDepotReverseMap::IdDescPair &b) {
+  return a.id < b.id;
+}
+
+StackDepotReverseMap::StackDepotReverseMap()
+    : map_(StackDepotGetStats()->n_uniq_ids + 100) {
+  for (int idx = 0; idx < kTabSize; idx++) {
+    atomic_uintptr_t *p = &depot.tab[idx];
+    uptr v = atomic_load(p, memory_order_consume);
+    StackDesc *s = (StackDesc*)(v & ~1);
+    for (; s; s = s->link) {
+      IdDescPair pair = {s->id, s};
+      map_.push_back(pair);
+    }
+  }
+  InternalSort(&map_, map_.size(), IdDescPair::IdComparator);
+}
+
+const uptr *StackDepotReverseMap::Get(u32 id, uptr *size) {
+  if (!map_.size()) return 0;
+  IdDescPair pair = {id, 0};
+  uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair,
+                                  IdDescPair::IdComparator);
+  if (idx > map_.size()) {
+    *size = 0;
+    return 0;
+  }
+  StackDesc *desc = map_[idx].desc;
+  *size = desc->size;
+  return desc->stack;
+}
+
 }  // namespace __sanitizer