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
GetStats()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>
find(Node * s,args_type args,u32 hash)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>
lock(atomic_uintptr_t * p)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>
unlock(atomic_uintptr_t * p,Node * s)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
Put(args_type args,bool * inserted)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
Get(u32 id)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>
LockAll()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>
UnlockAll()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