libsanitizer/sanitizer_common/sanitizer_stackdepotbase.h

   1 //===-- sanitizer_stackdepotbase.h ------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Implementation of a mapping from arbitrary values to unique 32-bit
  10 // identifiers.
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef SANITIZER_STACKDEPOTBASE_H
  14 #define SANITIZER_STACKDEPOTBASE_H
  15
  16 #include <stdio.h>
  17
  18 #include "sanitizer_atomic.h"
  19 #include "sanitizer_flat_map.h"
  20 #include "sanitizer_internal_defs.h"
  21 #include "sanitizer_mutex.h"
  22
  23 namespace __sanitizer {
  24
  25 template <class Node, int kReservedBits, int kTabSizeLog>
  26 class StackDepotBase {
  27   static constexpr u32 kIdSizeLog =
  28       sizeof(u32) * 8 - Max(kReservedBits, 1 /* At least 1 bit for locking. */);
  29   static constexpr u32 kNodesSize1Log = kIdSizeLog / 2;
  30   static constexpr u32 kNodesSize2Log = kIdSizeLog - kNodesSize1Log;
  31   static constexpr int kTabSize = 1 << kTabSizeLog;  // Hash table size.
  32   static constexpr u32 kUnlockMask = (1ull << kIdSizeLog) - 1;
  33   static constexpr u32 kLockMask = ~kUnlockMask;
  34
  35  public:
  36   typedef typename Node::args_type args_type;
  37   typedef typename Node::handle_type handle_type;
  38   typedef typename Node::hash_type hash_type;
  39
  40   static constexpr u64 kNodesSize1 = 1ull << kNodesSize1Log;
  41   static constexpr u64 kNodesSize2 = 1ull << kNodesSize2Log;
  42
  43   // Maps stack trace to an unique id.
  44   u32 Put(args_type args, bool *inserted = nullptr);
  45   // Retrieves a stored stack trace by the id.
  46   args_type Get(u32 id);
  47
  48   StackDepotStats GetStats() const {
  49     return {
  50         atomic_load_relaxed(&n_uniq_ids),
  51         nodes.MemoryUsage() + Node::allocated(),
  52     };
  53   }
  54
  55   void LockAll();
  56   void UnlockAll();
  57   void PrintAll();
  58
  59   void TestOnlyUnmap() {
  60     nodes.TestOnlyUnmap();
  61     internal_memset(this, 0, sizeof(*this));
  62   }
  63
  64  private:
  65   friend Node;
  66   u32 find(u32 s, args_type args, hash_type hash) const;
  67   static u32 lock(atomic_uint32_t *p);
  68   static void unlock(atomic_uint32_t *p, u32 s);
  69   atomic_uint32_t tab[kTabSize];  // Hash table of Node's.
  70
  71   atomic_uint32_t n_uniq_ids;
  72
  73   TwoLevelMap<Node, kNodesSize1, kNodesSize2> nodes;
  74
  75   friend class StackDepotReverseMap;
  76 };
  77
  78 template <class Node, int kReservedBits, int kTabSizeLog>
  79 u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(
  80     u32 s, args_type args, hash_type hash) const {
  81   // Searches linked list s for the stack, returns its id.
  82   for (; s;) {
  83     const Node &node = nodes[s];
  84     if (node.eq(hash, args))
  85       return s;
  86     s = node.link;
  87   }
  88   return 0;
  89 }
  90
  91 template <class Node, int kReservedBits, int kTabSizeLog>
  92 u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::lock(atomic_uint32_t *p) {
  93   // Uses the pointer lsb as mutex.
  94   for (int i = 0;; i++) {
  95     u32 cmp = atomic_load(p, memory_order_relaxed);
  96     if ((cmp & kLockMask) == 0 &&
  97         atomic_compare_exchange_weak(p, &cmp, cmp | kLockMask,
  98                                      memory_order_acquire))
  99       return cmp;
 100     if (i < 10)
 101       proc_yield(10);
 102     else
 103       internal_sched_yield();
 104   }
 105 }
 106
 107 template <class Node, int kReservedBits, int kTabSizeLog>
 108 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::unlock(
 109     atomic_uint32_t *p, u32 s) {
 110   DCHECK_EQ(s & kLockMask, 0);
 111   atomic_store(p, s, memory_order_release);
 112 }
 113
 114 template <class Node, int kReservedBits, int kTabSizeLog>
 115 u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,
 116                                                           bool *inserted) {
 117   if (inserted)
 118     *inserted = false;
 119   if (!LIKELY(Node::is_valid(args)))
 120     return 0;
 121   hash_type h = Node::hash(args);
 122   atomic_uint32_t *p = &tab[h % kTabSize];
 123   u32 v = atomic_load(p, memory_order_consume);
 124   u32 s = v & kUnlockMask;
 125   // First, try to find the existing stack.
 126   u32 node = find(s, args, h);
 127   if (LIKELY(node))
 128     return node;
 129
 130   // If failed, lock, retry and insert new.
 131   u32 s2 = lock(p);
 132   if (s2 != s) {
 133     node = find(s2, args, h);
 134     if (node) {
 135       unlock(p, s2);
 136       return node;
 137     }
 138   }
 139   s = atomic_fetch_add(&n_uniq_ids, 1, memory_order_relaxed) + 1;
 140   CHECK_EQ(s & kUnlockMask, s);
 141   CHECK_EQ(s & (((u32)-1) >> kReservedBits), s);
 142   Node &new_node = nodes[s];
 143   new_node.store(s, args, h);
 144   new_node.link = s2;
 145   unlock(p, s);
 146   if (inserted) *inserted = true;
 147   return s;
 148 }
 149
 150 template <class Node, int kReservedBits, int kTabSizeLog>
 151 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type
 152 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Get(u32 id) {
 153   if (id == 0)
 154     return args_type();
 155   CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
 156   if (!nodes.contains(id))
 157     return args_type();
 158   const Node &node = nodes[id];
 159   return node.load(id);
 160 }
 161
 162 template <class Node, int kReservedBits, int kTabSizeLog>
 163 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::LockAll() {
 164   for (int i = 0; i < kTabSize; ++i) {
 165     lock(&tab[i]);
 166   }
 167 }
 168
 169 template <class Node, int kReservedBits, int kTabSizeLog>
 170 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::UnlockAll() {
 171   for (int i = 0; i < kTabSize; ++i) {
 172     atomic_uint32_t *p = &tab[i];
 173     uptr s = atomic_load(p, memory_order_relaxed);
 174     unlock(p, s & kUnlockMask);
 175   }
 176 }
 177
 178 template <class Node, int kReservedBits, int kTabSizeLog>
 179 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::PrintAll() {
 180   for (int i = 0; i < kTabSize; ++i) {
 181     atomic_uint32_t *p = &tab[i];
 182     u32 s = atomic_load(p, memory_order_consume) & kUnlockMask;
 183     for (; s;) {
 184       const Node &node = nodes[s];
 185       Printf("Stack for id %u:\n", s);
 186       node.load(s).Print();
 187       s = node.link;
 188     }
 189   }
 190 }
 191
 192 } // namespace __sanitizer
 193
 194 #endif // SANITIZER_STACKDEPOTBASE_H