contrib/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

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