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 "sanitizer_internal_defs.h"
  17 #include "sanitizer_mutex.h"
  18 #include "sanitizer_atomic.h"
  19 #include "sanitizer_persistent_allocator.h"
  20
  21 namespace __sanitizer {
  22
  23 template <class Node, int kReservedBits, int kTabSizeLog>
  24 class StackDepotBase {
  25  public:
  26   typedef typename Node::args_type args_type;
  27   typedef typename Node::handle_type handle_type;
  28   // Maps stack trace to an unique id.
  29   handle_type Put(args_type args, bool *inserted = nullptr);
  30   // Retrieves a stored stack trace by the id.
  31   args_type Get(u32 id);
  32
  33   StackDepotStats *GetStats() { return &stats; }
  34
  35   void LockAll();
  36   void UnlockAll();
  37
  38  private:
  39   static Node *find(Node *s, args_type args, u32 hash);
  40   static Node *lock(atomic_uintptr_t *p);
  41   static void unlock(atomic_uintptr_t *p, Node *s);
  42
  43   static const int kTabSize = 1 << kTabSizeLog;  // Hash table size.
  44   static const int kPartBits = 8;
  45   static const int kPartShift = sizeof(u32) * 8 - kPartBits - kReservedBits;
  46   static const int kPartCount =
  47       1 << kPartBits;  // Number of subparts in the table.
  48   static const int kPartSize = kTabSize / kPartCount;
  49   static const int kMaxId = 1 << kPartShift;
  50
  51   atomic_uintptr_t tab[kTabSize];   // Hash table of Node's.
  52   atomic_uint32_t seq[kPartCount];  // Unique id generators.
  53
  54   StackDepotStats stats;
  55
  56   friend class StackDepotReverseMap;
  57 };
  58
  59 template <class Node, int kReservedBits, int kTabSizeLog>
  60 Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(Node *s,
  61                                                              args_type args,
  62                                                              u32 hash) {
  63   // Searches linked list s for the stack, returns its id.
  64   for (; s; s = s->link) {
  65     if (s->eq(hash, args)) {
  66       return s;
  67     }
  68   }
  69   return nullptr;
  70 }
  71
  72 template <class Node, int kReservedBits, int kTabSizeLog>
  73 Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::lock(
  74     atomic_uintptr_t *p) {
  75   // Uses the pointer lsb as mutex.
  76   for (int i = 0;; i++) {
  77     uptr cmp = atomic_load(p, memory_order_relaxed);
  78     if ((cmp & 1) == 0 &&
  79         atomic_compare_exchange_weak(p, &cmp, cmp | 1, memory_order_acquire))
  80       return (Node *)cmp;
  81     if (i < 10)
  82       proc_yield(10);
  83     else
  84       internal_sched_yield();
  85   }
  86 }
  87
  88 template <class Node, int kReservedBits, int kTabSizeLog>
  89 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::unlock(
  90     atomic_uintptr_t *p, Node *s) {
  91   DCHECK_EQ((uptr)s & 1, 0);
  92   atomic_store(p, (uptr)s, memory_order_release);
  93 }
  94
  95 template <class Node, int kReservedBits, int kTabSizeLog>
  96 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::handle_type
  97 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,
  98                                                       bool *inserted) {
  99   if (inserted) *inserted = false;
 100   if (!Node::is_valid(args)) return handle_type();
 101   uptr h = Node::hash(args);
 102   atomic_uintptr_t *p = &tab[h % kTabSize];
 103   uptr v = atomic_load(p, memory_order_consume);
 104   Node *s = (Node *)(v & ~1);
 105   // First, try to find the existing stack.
 106   Node *node = find(s, args, h);
 107   if (node) return node->get_handle();
 108   // If failed, lock, retry and insert new.
 109   Node *s2 = lock(p);
 110   if (s2 != s) {
 111     node = find(s2, args, h);
 112     if (node) {
 113       unlock(p, s2);
 114       return node->get_handle();
 115     }
 116   }
 117   uptr part = (h % kTabSize) / kPartSize;
 118   u32 id = atomic_fetch_add(&seq[part], 1, memory_order_relaxed) + 1;
 119   stats.n_uniq_ids++;
 120   CHECK_LT(id, kMaxId);
 121   id |= part << kPartShift;
 122   CHECK_NE(id, 0);
 123   CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
 124   uptr memsz = Node::storage_size(args);
 125   s = (Node *)PersistentAlloc(memsz);
 126   stats.allocated += memsz;
 127   s->id = id;
 128   s->store(args, h);
 129   s->link = s2;
 130   unlock(p, s);
 131   if (inserted) *inserted = true;
 132   return s->get_handle();
 133 }
 134
 135 template <class Node, int kReservedBits, int kTabSizeLog>
 136 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type
 137 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Get(u32 id) {
 138   if (id == 0) {
 139     return args_type();
 140   }
 141   CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
 142   // High kPartBits contain part id, so we need to scan at most kPartSize lists.
 143   uptr part = id >> kPartShift;
 144   for (int i = 0; i != kPartSize; i++) {
 145     uptr idx = part * kPartSize + i;
 146     CHECK_LT(idx, kTabSize);
 147     atomic_uintptr_t *p = &tab[idx];
 148     uptr v = atomic_load(p, memory_order_consume);
 149     Node *s = (Node *)(v & ~1);
 150     for (; s; s = s->link) {
 151       if (s->id == id) {
 152         return s->load();
 153       }
 154     }
 155   }
 156   return args_type();
 157 }
 158
 159 template <class Node, int kReservedBits, int kTabSizeLog>
 160 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::LockAll() {
 161   for (int i = 0; i < kTabSize; ++i) {
 162     lock(&tab[i]);
 163   }
 164 }
 165
 166 template <class Node, int kReservedBits, int kTabSizeLog>
 167 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::UnlockAll() {
 168   for (int i = 0; i < kTabSize; ++i) {
 169     atomic_uintptr_t *p = &tab[i];
 170     uptr s = atomic_load(p, memory_order_relaxed);
 171     unlock(p, (Node *)(s & ~1UL));
 172   }
 173 }
 174
 175 } // namespace __sanitizer
 176
 177 #endif // SANITIZER_STACKDEPOTBASE_H