[sanitizer] Move out stack trace pointer from header StackDepot

[vitalybuka]

Summary

Trace pointers accessed very rarely and don't need to
be in hot data.

Depends on D111613.

[dvyukov]

This is not immediately obvious to me that this is beneficial. When we load the first node in the chain and follow node.link's, we are chasing random pointers anyway so for every access it's a cache miss anyway, no?

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

23

restore empty line

72

This probably deserves a comment so that the next developer does not move it back to node.

[vitalybuka]

In D111614#3057458, @dvyukov wrote:

This is not immediately obvious to me that this is beneficial. When we load the first node in the chain and follow node.link's, we are chasing random pointers anyway so for every access it's a cache miss anyway, no?

I guess no immediate strong benefits for now. Perf improvements on large benchmarks below the noise.
But there are some weak reasons:

1. Less cache pressure by hot data. Amount of data we want in cache is 1/3 smaller now.
2. System may pageout/zswap old regions of tracePtrs and traceAllocator. Maybe with help of madvice.

Even less important:

3. It's related to next two patches: I like to think about this hash table as pure stack->id mapping. The rest we will retrive by id somehow.
4. Easy to do now :)
5. Flat hashtable with resize with a linear lookup when we care about cachelines. If you don't like all above I can get back with this patch after the experiment.

[vitalybuka]

rebase

[vitalybuka]

comments

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

struct ChainedOriginDepotNode {
   bool eq(hash_type hash, const args_type &args) const;
 
   static uptr allocated() { return 0; }
 
   static hash_type hash(const args_type &args);
 
   static bool is_valid(const args_type &args);
 
-  void store(const args_type &args, hash_type other_hash);
+  void store(u32 id, const args_type &args, hash_type other_hash);
 
-  args_type load() const;
+  args_type load(u32 id) const;
 
   struct Handle {
     const ChainedOriginDepotNode *node_ = nullptr;
     u32 id_ = 0;
     Handle(const ChainedOriginDepotNode *node, u32 id) : node_(node), id_(id) {}
     bool valid() const { return node_; }
     u32 id() const { return id_; }
     int here_id() const { return node_->here_id; }
ChainedOriginDepotNode::hash_type ChainedOriginDepotNode::hash(
   h ^= h >> 13;
   h *= m;
   h ^= h >> 15;
   return h;
 }
 
 bool ChainedOriginDepotNode::is_valid(const args_type &args) { return true; }
 
-void ChainedOriginDepotNode::store(const args_type &args,
+void ChainedOriginDepotNode::store(u32 id, const args_type &args,
                                    hash_type other_hash) {
   here_id = args.here_id;
   prev_id = args.prev_id;
 }
 
-ChainedOriginDepotNode::args_type ChainedOriginDepotNode::load() const {
+ChainedOriginDepotNode::args_type ChainedOriginDepotNode::load(u32 id) const {
   args_type ret = {here_id, prev_id};
   return ret;
 }
 
 ChainedOriginDepotNode::Handle ChainedOriginDepotNode::get_handle(u32 id) {
   return Handle(&depot.nodes[id], id);
 }
 

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

 #include "sanitizer_common.h"
 #include "sanitizer_hash.h"
 #include "sanitizer_persistent_allocator.h"
 #include "sanitizer_stackdepotbase.h"
 
 namespace __sanitizer {
 
 static PersistentAllocator<uptr> traceAllocator;
-
 struct StackDepotNode {
   using hash_type = u64;
   hash_type stack_hash;
-  uptr *stack_trace;
   u32 link;
   atomic_uint32_t tag_and_use_count;  // tag : 12 high bits; use_count : 20;
 
   static const u32 kTabSizeLog = SANITIZER_ANDROID ? 16 : 20;
   static const u32 kUseCountBits = 20;
   static const u32 kMaxUseCount = 1 << kUseCountBits;
   static const u32 kUseCountMask = (1 << kUseCountBits) - 1;
 
   typedef StackTrace args_type;
   bool eq(hash_type hash, const args_type &args) const {
     return hash == stack_hash;
   }
   static uptr allocated() { return traceAllocator.allocated(); }
   static hash_type hash(const args_type &args) {
     MurMur2Hash64Builder H(args.size * sizeof(uptr));
     for (uptr i = 0; i < args.size; i++) H.add(args.trace[i]);
     H.add(args.tag);
     return H.get();
   }
   static bool is_valid(const args_type &args) {
     return args.size > 0 && args.trace;
   }
-  void store(const args_type &args, hash_type hash) {
-    CHECK_EQ(args.tag & (~kUseCountMask >> kUseCountBits), args.tag);
-    atomic_store(&tag_and_use_count, args.tag << kUseCountBits,
-                 memory_order_relaxed);
-    stack_hash = hash;
-    stack_trace = traceAllocator.alloc(args.size + 1);
-    *stack_trace = args.size;
-    internal_memcpy(stack_trace + 1, args.trace, args.size * sizeof(uptr));
-  }
-  args_type load() const {
-    if (!stack_trace)
-      return {};
-    u32 tag =
-        atomic_load(&tag_and_use_count, memory_order_relaxed) >> kUseCountBits;
-    return args_type(stack_trace + 1, *stack_trace, tag);
-  }
+  void store(u32 id, const args_type &args, hash_type hash);
+  args_type load(u32 id) const;
   static StackDepotHandle get_handle(u32 id);
 
   typedef StackDepotHandle handle_type;
 };
 
 COMPILER_CHECK(StackDepotNode::kMaxUseCount >= (u32)kStackDepotMaxUseCount);
 
 int StackDepotHandle::use_count() const {
   return atomic_load(&node_->tag_and_use_count, memory_order_relaxed) &
          StackDepotNode::kUseCountMask;
 }
 void StackDepotHandle::inc_use_count_unsafe() {
   u32 prev =
       atomic_fetch_add(&node_->tag_and_use_count, 1, memory_order_relaxed) &
       StackDepotNode::kUseCountMask;
   CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount);
 }
 
 // FIXME(dvyukov): this single reserved bit is used in TSan.
 typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog>
     StackDepot;
 static StackDepot theDepot;
+static TwoLevelMap<uptr *, 1 << StackDepot::kNodesSize1Log,
+                   1 << StackDepot::kNodesSize2Log>
+    tracePtrs;
+
+void StackDepotNode::store(u32 id, const args_type &args, hash_type hash) {
+  CHECK_EQ(args.tag & (~kUseCountMask >> kUseCountBits), args.tag);
+  atomic_store(&tag_and_use_count, args.tag << kUseCountBits,
+               memory_order_relaxed);
+  stack_hash = hash;
+  uptr *stack_trace = traceAllocator.alloc(args.size + 1);
+  *stack_trace = args.size;
+  internal_memcpy(stack_trace + 1, args.trace, args.size * sizeof(uptr));
+  tracePtrs[id] = stack_trace;
+}
+
+StackDepotNode::args_type StackDepotNode::load(u32 id) const {
+  const uptr *stack_trace = tracePtrs[id];
+  if (!stack_trace)
+    return {};
+  u32 tag =
+      atomic_load(&tag_and_use_count, memory_order_relaxed) >> kUseCountBits;
+  return args_type(stack_trace + 1, *stack_trace, tag);
+}
 
 StackDepotStats StackDepotGetStats() { return theDepot.GetStats(); }
 
 u32 StackDepotPut(StackTrace stack) { return theDepot.Put(stack); }
 
 StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) {
   return StackDepotNode::get_handle(theDepot.Put(stack));
 }

compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

 #include "sanitizer_internal_defs.h"
 #include "sanitizer_mutex.h"
 
 namespace __sanitizer {
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 class StackDepotBase {
  public:
+  static const int kNodesSize1Log = (32 - kReservedBits) / 2;
+  static const int kNodesSize2Log = 32 - kReservedBits - kNodesSize1Log;
+
   typedef typename Node::args_type args_type;
   typedef typename Node::handle_type handle_type;
   typedef typename Node::hash_type hash_type;
 
   // Maps stack trace to an unique id.
   u32 Put(args_type args, bool *inserted = nullptr);
   // Retrieves a stored stack trace by the id.
   args_type Get(u32 id);
private:
   u32 find(u32 s, args_type args, hash_type hash) const;
   static u32 lock(atomic_uint32_t *p);
   static void unlock(atomic_uint32_t *p, u32 s);
 
   static const u32 kUnlockMask = (~u32(0)) >> 1;
   static const u32 kLockMask = ~kUnlockMask;
 
   static const int kTabSize = 1 << kTabSizeLog;  // Hash table size.
-  static const int kNodesSize1Log = (32 - kReservedBits) / 2;
-  static const int kNodesSize2Log = 32 - kReservedBits - kNodesSize1Log;
 
   atomic_uint32_t tab[kTabSize];  // Hash table of Node's.
 
   atomic_uint32_t n_uniq_ids;
 
   TwoLevelMap<Node, 1 << kNodesSize1Log, 1 << kNodesSize2Log> nodes;
 
   friend class StackDepotReverseMap;
if (node) {
       unlock(p, s2);
       return node;
     }
   }
   s = atomic_fetch_add(&n_uniq_ids, 1, memory_order_relaxed) + 1;
   CHECK_EQ(s & kUnlockMask, s);
   CHECK_EQ(s & (((u32)-1) >> kReservedBits), s);
   Node &new_node = nodes[s];
-  new_node.store(args, h);
+  new_node.store(s, args, h);
   new_node.link = s2;
   unlock(p, s);
   if (inserted) *inserted = true;
   return s;
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type
 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Get(u32 id) {
   if (id == 0)
     return args_type();
   CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
   if (!nodes.contains(id))
     return args_type();
   const Node &node = nodes[id];
-  return node.load();
+  return node.load(id);
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::LockAll() {
   for (int i = 0; i < kTabSize; ++i) {
     lock(&tab[i]);
   }
 }

 template <class Node, int kReservedBits, int kTabSizeLog>
 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::PrintAll() {
   for (int i = 0; i < kTabSize; ++i) {
     atomic_uint32_t *p = &tab[i];
     u32 s = atomic_load(p, memory_order_consume) & kUnlockMask;
     for (; s;) {
       const Node &node = nodes[s];
       Printf("Stack for id %u:\n", s);
-      node.load().Print();
+      node.load(s).Print();
       s = node.link;
     }
   }
 }
 
 } // namespace __sanitizer
 
 #endif // SANITIZER_STACKDEPOTBASE_H