libsanitizer/sanitizer_common/sanitizer_stackdepotbase.h

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