[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

73

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;
+// Keep rarely accessed stack traces out of frequently access nodes to improve
+// caching efficiency.
+static TwoLevelMap<uptr *, StackDepot::kNodesSize1, StackDepot::kNodesSize2>
+    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

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