[msan] Chained origins re-design.

Generalize StackDepot and create a new specialized instance of it to
efficiently (i.e. without duplicating stack trace data) store the
origin history tree.

This reduces memory usage for chained origins roughly by an order of
magnitude.

Most importantly, this new design allows us to put two limits on
stored history data (exposed in MSAN_OPTIONS) that help avoid
exponential growth in used memory on certain workloads.

See comments in lib/msan/msan_origin.h for more details.



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

1 files changed, 153 insertions, 0 deletions

diff --git a/lib/sanitizer_common/sanitizer_stackdepotbase.h b/lib/sanitizer_common/sanitizer_stackdepotbase.h
new file mode 100644
index 000000000..07a973c44
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_stackdepotbase.h
@@ -0,0 +1,153 @@
+//===-- sanitizer_stackdepotbase.h ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of a mapping from arbitrary values to unique 32-bit
+// identifiers.
+//===----------------------------------------------------------------------===//
+#ifndef SANITIZER_STACKDEPOTBASE_H
+#define SANITIZER_STACKDEPOTBASE_H
+
+#include "sanitizer_internal_defs.h"
+#include "sanitizer_mutex.h"
+#include "sanitizer_atomic.h"
+#include "sanitizer_persistent_allocator.h"
+
+namespace __sanitizer {
+
+template <class Node, int kReservedBits>
+class StackDepotBase {
+ public:
+  typedef typename Node::args_type args_type;
+  typedef typename Node::handle_type handle_type;
+  // Maps stack trace to an unique id.
+  handle_type Put(args_type args, bool *inserted = 0);
+  // Retrieves a stored stack trace by the id.
+  args_type Get(u32 id);
+
+  StackDepotStats *GetStats() { return &stats; }
+
+ private:
+  static Node *find(Node *s, args_type args, u32 hash);
+  static Node *lock(atomic_uintptr_t *p);
+  static void unlock(atomic_uintptr_t *p, Node *s);
+
+  static const int kTabSize = 1024 * 1024;  // Hash table size.
+  static const int kPartBits = 8;
+  static const int kPartShift = sizeof(u32) * 8 - kPartBits - kReservedBits;
+  static const int kPartCount =
+      1 << kPartBits;  // Number of subparts in the table.
+  static const int kPartSize = kTabSize / kPartCount;
+  static const int kMaxId = 1 << kPartShift;
+
+  atomic_uintptr_t tab[kTabSize];   // Hash table of Node's.
+  atomic_uint32_t seq[kPartCount];  // Unique id generators.
+
+  StackDepotStats stats;
+
+  friend class StackDepotReverseMap;
+};
+
+template <class Node, int kReservedBits>
+Node *StackDepotBase<Node, kReservedBits>::find(Node *s, args_type args,
+                                                u32 hash) {
+  // Searches linked list s for the stack, returns its id.
+  for (; s; s = s->link) {
+    if (s->eq(hash, args)) {
+      return s;
+    }
+  }
+  return 0;
+}
+
+template <class Node, int kReservedBits>
+Node *StackDepotBase<Node, kReservedBits>::lock(atomic_uintptr_t *p) {
+  // Uses the pointer lsb as mutex.
+  for (int i = 0;; i++) {
+    uptr cmp = atomic_load(p, memory_order_relaxed);
+    if ((cmp & 1) == 0 &&
+        atomic_compare_exchange_weak(p, &cmp, cmp | 1, memory_order_acquire))
+      return (Node *)cmp;
+    if (i < 10)
+      proc_yield(10);
+    else
+      internal_sched_yield();
+  }
+}
+
+template <class Node, int kReservedBits>
+void StackDepotBase<Node, kReservedBits>::unlock(atomic_uintptr_t *p, Node *s) {
+  DCHECK_EQ((uptr)s & 1, 0);
+  atomic_store(p, (uptr)s, memory_order_release);
+}
+
+template <class Node, int kReservedBits>
+typename StackDepotBase<Node, kReservedBits>::handle_type
+StackDepotBase<Node, kReservedBits>::Put(args_type args, bool *inserted) {
+  if (inserted) *inserted = false;
+  if (!args.is_valid()) return handle_type();
+  uptr h = args.hash();
+  atomic_uintptr_t *p = &tab[h % kTabSize];
+  uptr v = atomic_load(p, memory_order_consume);
+  Node *s = (Node *)(v & ~1);
+  // First, try to find the existing stack.
+  Node *node = find(s, args, h);
+  if (node) return node->get_handle();
+  // If failed, lock, retry and insert new.
+  Node *s2 = lock(p);
+  if (s2 != s) {
+    node = find(s2, args, h);
+    if (node) {
+      unlock(p, s2);
+      return node->get_handle();
+    }
+  }
+  uptr part = (h % kTabSize) / kPartSize;
+  u32 id = atomic_fetch_add(&seq[part], 1, memory_order_relaxed) + 1;
+  stats.n_uniq_ids++;
+  CHECK_LT(id, kMaxId);
+  id |= part << kPartShift;
+  CHECK_NE(id, 0);
+  CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
+  uptr memsz = Node::storage_size(args);
+  s = (Node *)PersistentAlloc(memsz);
+  stats.allocated += memsz;
+  s->id = id;
+  s->store(args, h);
+  s->link = s2;
+  unlock(p, s);
+  if (inserted) *inserted = true;
+  return s->get_handle();
+}
+
+template <class Node, int kReservedBits>
+typename StackDepotBase<Node, kReservedBits>::args_type
+StackDepotBase<Node, kReservedBits>::Get(u32 id) {
+  if (id == 0) {
+    return args_type();
+  }
+  CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
+  // High kPartBits contain part id, so we need to scan at most kPartSize lists.
+  uptr part = id >> kPartShift;
+  for (int i = 0; i != kPartSize; i++) {
+    uptr idx = part * kPartSize + i;
+    CHECK_LT(idx, kTabSize);
+    atomic_uintptr_t *p = &tab[idx];
+    uptr v = atomic_load(p, memory_order_consume);
+    Node *s = (Node *)(v & ~1);
+    for (; s; s = s->link) {
+      if (s->id == id) {
+        return s->load();
+      }
+    }
+  }
+  return args_type();
+}
+
+} // namespace __sanitizer
+#endif  // SANITIZER_STACKDEPOTBASE_H