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