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 19namespace __sanitizer { 20 21template <class Node, int kReservedBits, int kTabSizeLog> 22class 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 57template <class Node, int kReservedBits, int kTabSizeLog> 58Node *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 70template <class Node, int kReservedBits, int kTabSizeLog> 71Node *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 86template <class Node, int kReservedBits, int kTabSizeLog> 87void 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 93template <class Node, int kReservedBits, int kTabSizeLog> 94typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::handle_type 95StackDepotBase<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 133template <class Node, int kReservedBits, int kTabSizeLog> 134typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type 135StackDepotBase<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 157template <class Node, int kReservedBits, int kTabSizeLog> 158void StackDepotBase<Node, kReservedBits, kTabSizeLog>::LockAll() { 159 for (int i = 0; i < kTabSize; ++i) { 160 lock(&tab[i]); 161 } 162} 163 164template <class Node, int kReservedBits, int kTabSizeLog> 165void 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 175