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