[sanitizer] Switch to StackDepotNode to 64bit hash

[vitalybuka]

Summary

Now we can avoid scanning the stack on fast path.
The price is the false stack trace with probability of the hash collision.
This increase performance of lsan by 6% and pre-requirement for stack compression.

Depends on D111182.

[vitalybuka]

include tag into hash

[vitalybuka]

fix compilation

[morehouse]

LGTM

[vitalybuka]

move 64bit field front, for better alignment

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

23

wonder if the header can be compressed back to 3 words
size is pretty small and maybe can be combined with something else

but we could remove id entirely (and simplify code along the way)
the algorithm used by kernel is better in this regard, we make the id an index in a dense allocator:
https://elixir.bootlin.com/linux/v5.15-rc4/source/lib/stackdepot.c#L136
then id does not need to be stored explicitly and can be easily mapped back to the stack in O(1):
https://elixir.bootlin.com/linux/v5.15-rc4/source/lib/stackdepot.c#L231

this would also remove all of StackDepotReverseMap machinery

36

args are now unused and can be removed

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

23

I am planing to move out size completely and put it with compressed data in "compression" patches.

Thanks, I was thinking about switching to single sequential id and remove map, but didn't realized that we can reuse some info from allocator. I will check these links. Still it's going to be done in separate patches.

36

This interface is used by "origin" depots, which is actually needs just a hash table part. There is some opportunity for refactoring.

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

23

tsan_dense_alloc.h is almost the allocator we need (maps allocated objects to u32 and back), but it only supports objects of fixed size; while in the kernel stackdepot we allocate variable size objects (due to variable size stack traces)
maybe tsan_dense_alloc.h can be extended to handle such case as well, not sure

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

 
 #include "sanitizer_common.h"
 #include "sanitizer_hash.h"
 #include "sanitizer_stackdepotbase.h"
 
 namespace __sanitizer {
 
 struct StackDepotNode {
-  using hash_type = u32;
+  using hash_type = u64;
+  hash_type stack_hash;
   StackDepotNode *link;
   u32 id;
-  hash_type stack_hash;
   u32 size;
   atomic_uint32_t tag_and_use_count;  // tag : 12 high bits; use_count : 20;
   uptr stack[1];  // [size]
 
   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 {
-    u32 tag =
-        atomic_load(&tag_and_use_count, memory_order_relaxed) >> kUseCountBits;
-    if (stack_hash != hash || args.size != size || args.tag != tag)
-      return false;
-    uptr i = 0;
-    for (; i < size; i++) {
-      if (stack[i] != args.trace[i]) return false;
-    }
-    return true;
+    return hash == stack_hash;
   }
   static uptr storage_size(const args_type &args) {
     return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr);
   }
   static hash_type hash(const args_type &args) {
-    MurMur2HashBuilder H(args.size * sizeof(uptr));
+    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,