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