[NFC][sanitizers] Add StackDepotBase Node::hash_type

[vitalybuka]

Summary

Depends on D111177.

[morehouse]

LGTM

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.h

 
  private:
   struct ChainedOriginDepotDesc {
     u32 here_id;
     u32 prev_id;
   };
 
   struct ChainedOriginDepotNode {
+    using hash_type = u32;
     ChainedOriginDepotNode *link;
     u32 id;
     u32 here_id;
     u32 prev_id;
 
     typedef ChainedOriginDepotDesc args_type;
 
-    bool eq(u32 hash, const args_type &args) const;
+    bool eq(hash_type hash, const args_type &args) const;
 
     static uptr storage_size(const args_type &args);
 
-    static u32 hash(const args_type &args);
+    static hash_type hash(const args_type &args);
 
     static bool is_valid(const args_type &args);
 
-    void store(const args_type &args, u32 other_hash);
+    void store(const args_type &args, hash_type other_hash);
 
     args_type load() const;
 
     struct Handle {
       ChainedOriginDepotNode *node_;
       Handle() : node_(nullptr) {}
       explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
       bool valid() { return node_; }

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

 //===-- sanitizer_chained_origin_depot.cpp --------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // A storage for chained origins.
 //===----------------------------------------------------------------------===//
 
 #include "sanitizer_chained_origin_depot.h"
 
 namespace __sanitizer {
 
 bool ChainedOriginDepot::ChainedOriginDepotNode::eq(
-    u32 hash, const args_type &args) const {
+    hash_type hash, const args_type &args) const {
   return here_id == args.here_id && prev_id == args.prev_id;
 }
 
 uptr ChainedOriginDepot::ChainedOriginDepotNode::storage_size(
     const args_type &args) {
   return sizeof(ChainedOriginDepotNode);
 }
 
 /* This is murmur2 hash for the 64->32 bit case.
    It does not behave all that well because the keys have a very biased
    distribution (I've seen 7-element buckets with the table only 14% full).
 
    here_id is built of
    * (1 bits) Reserved, zero.
    * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
    * (23 bits) Sequential number (each part has each own sequence).
 
    prev_id has either the same distribution as here_id (but with 3:8:21)
    split, or one of two reserved values (-1) or (-2). Either case can
    dominate depending on the workload.
 */
-u32 ChainedOriginDepot::ChainedOriginDepotNode::hash(const args_type &args) {
+ChainedOriginDepot::ChainedOriginDepotNode::hash_type
+ChainedOriginDepot::ChainedOriginDepotNode::hash(const args_type &args) {
   const u32 m = 0x5bd1e995;
   const u32 seed = 0x9747b28c;
   const u32 r = 24;
   u32 h = seed;
   u32 k = args.here_id;
   k *= m;
   k ^= k >> r;
   k *= m;

 }
 
 bool ChainedOriginDepot::ChainedOriginDepotNode::is_valid(
     const args_type &args) {
   return true;
 }
 
 void ChainedOriginDepot::ChainedOriginDepotNode::store(const args_type &args,
-                                                       u32 other_hash) {
+                                                       hash_type other_hash) {
   here_id = args.here_id;
   prev_id = args.prev_id;
 }
 
 ChainedOriginDepot::ChainedOriginDepotNode::args_type
 ChainedOriginDepot::ChainedOriginDepotNode::load() const {
   args_type ret = {here_id, prev_id};
   return ret;

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;
   StackDepotNode *link;
   u32 id;
-  u32 stack_hash;
+  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(u32 hash, const args_type &args) const {
+  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;
   }
   static uptr storage_size(const args_type &args) {
     return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr);
   }
-  static u32 hash(const args_type &args) {
+  static hash_type hash(const args_type &args) {
     MurMur2HashBuilder H(args.size * sizeof(uptr));
     for (uptr i = 0; i < args.size; i++) H.add(args.trace[i]);
     return H.get();
   }
   static bool is_valid(const args_type &args) {
     return args.size > 0 && args.trace;
   }
-  void store(const args_type &args, u32 hash) {
+  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;
     size = args.size;
     internal_memcpy(stack, args.trace, size * sizeof(uptr));
   }
   args_type load() const {

compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

 
 namespace __sanitizer {
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 class StackDepotBase {
  public:
   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.
   handle_type Put(args_type args, bool *inserted = nullptr);
   // Retrieves a stored stack trace by the id.
   args_type Get(u32 id);
 
   StackDepotStats GetStats() const { return stats; }
 
   void LockAll();
   void UnlockAll();
   void PrintAll();
 
  private:
-  static Node *find(Node *s, args_type args, u32 hash);
+  static Node *find(Node *s, args_type args, hash_type hash);
   static Node *lock(atomic_uintptr_t *p);
   static void unlock(atomic_uintptr_t *p, Node *s);
 
   static const int kTabSize = 1 << kTabSizeLog;  // 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, int kTabSizeLog>
 Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(Node *s,
                                                              args_type args,
-                                                             u32 hash) {
+                                                             hash_type hash) {
   // Searches linked list s for the stack, returns its id.
   for (; s; s = s->link) {
     if (s->eq(hash, args)) {
       return s;
     }
   }
   return nullptr;
 }

 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::handle_type
 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,
                                                       bool *inserted) {
   if (inserted) *inserted = false;
   if (!Node::is_valid(args)) return handle_type();
-  uptr h = Node::hash(args);
+  hash_type h = Node::hash(args);
   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);