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 178