[sanitizer] Remove use_count from StackDepotNode

[vitalybuka]

Summary

This is msan/dfsan data which does not need waste cache
of other sanitizers.

Depends on D111614.

[dvyukov]

But this does not reduce size of the node, it's still 16 bytes. So what's the point?

[vitalybuka]

This comment was removed by vitalybuka.

[vitalybuka]

In D111615#3057474, @dvyukov wrote:

But this does not reduce size of the node, it's still 16 bytes. So what's the point?

3-5 of https://reviews.llvm.org/D111614#3058999
in 5 I have no idea what to do with this atomic if I resize/rehash flat hash table. We will need to realloc the memory block. This called inc_use_count_unsafe so maybe under-counting is fine.

[vitalybuka]

rebase

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

63

These 2 changes combined (this and D111616) increase memory usage. Previously we had 16 byte node, after these changes we still 16 byte node, but also u32 in useCounts.

If node size is not shrinking, we can as well leave tag/size there.

It may also simplify things if we move useCounts into the trace (where we currently store size). Then we don't need a separate TwoLevelMap for useCounts.

Potentially we could get rid of tracePtrs as well, if the idx will point directly into traceAllocator (the current PersistentAllocator does not support it, but it could, or we could use something else, something like TwoLevelMap but with batch allocation where we can ask for N consecutive uptr's).

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

63

D111616 does not increase memory, it shares tag with size? This one increases.

These patches increment StackDepot memory usage by about 1/N where N is average frames per trace. So I don't think it's a concern.

Also it's msan-track-origins/dfsab only, for any other sanitizer it's not going to allocate anything.

It may also simplify things if we move useCounts into the trace (where we currently store size). Then we don't need a separate TwoLevelMap for useCounts.

That's not going to work.
Most memory consumed by StackDepot are traces and they are never accessed after that (tag as well). So it's go to cold storage (out of cache or even page out or even compressed, which is WIP).
But useCounts is continuously incremented by msan and it will fetch cache-lines with mostly irrelevant data, and I don't want to mix compressible constant data with mutable counter. Moving Tag like in D111616 is fine.

[vitalybuka]

Actually even as-is this patch is beneficial.

So as I said this patch is NOOP for anything but msan-origins/dfsan.
I've submitted simple benchmark, _UseCount mimics msan/dfsan use:

After the patch:

autoninja -C ../out/z/ SanitizerUnitTests && ../out/z/projects/compiler-rt/lib/sanitizer_common/tests/./Sanitizer-x86_64-Test --gtest_also_run_disabled_tests --gtest_filter=*Benchmark* --gtest_repeat=1
[       OK ] SanitizerCommonBenchmarkSuite/SanitizerCommonBenchmark.DISABLED_BenchmarkInsertUniqueThreaded/3000000_10_16_UseCount (13520 ms)

Before patch:

autoninja -C ../out/z/ SanitizerUnitTests && ../out/z/projects/compiler-rt/lib/sanitizer_common/tests/./Sanitizer-x86_64-Test --gtest_also_run_disabled_tests --gtest_filter=*Benchmark* --gtest_repeat=1
[       OK ] SanitizerCommonBenchmarkSuite/SanitizerCommonBenchmark.DISABLED_BenchmarkInsertUniqueThreaded/3000000_10_16_UseCount (17402 ms)

I assume this is because nodes are now in cache lines which are not modified by other threads.

[vitalybuka]

rebase

[vitalybuka]

In D111615#3062400, @vitalybuka wrote:

Actually even as-is this patch is beneficial.

Please disregard that message. "After" also included D111614.
So most perf benefits are form D111614 which is quite expected.

[dvyukov]

Also it's msan-track-origins/dfsab only, for any other sanitizer it's not going to allocate anything.

fair

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

 namespace __sanitizer {
 
 static PersistentAllocator<uptr> traceAllocator;
 
 struct StackDepotNode {
   using hash_type = u64;
   hash_type stack_hash;
   u32 link;
-  atomic_uint32_t tag_and_use_count;  // tag : 12 high bits; use_count : 20;
+  u32 tag;
 
   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();
   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(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;
+// Keep mutable data out of frequently access nodes to improve caching
+// efficiency.
+static TwoLevelMap<atomic_uint32_t, StackDepot::kNodesSize1,
+                   StackDepot::kNodesSize2>
+    useCounts;
+
+int StackDepotHandle::use_count() const {
+  return atomic_load_relaxed(&useCounts[id_]);
+}
+
+void StackDepotHandle::inc_use_count_unsafe() {
+  atomic_fetch_add(&useCounts[id_], 1, memory_order_relaxed);
+}
 
 uptr StackDepotNode::allocated() {
-  return traceAllocator.allocated() + tracePtrs.MemoryUsage();
+  return traceAllocator.allocated() + tracePtrs.MemoryUsage() +
+         useCounts.MemoryUsage();
 }
 
 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);
+  tag = args.tag;
   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) {