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 //===----------------------------------------------------------------------===//
13 
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 
24 template <class Node, int kReservedBits, int kTabSizeLog>
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.
30   handle_type Put(args_type args, bool *inserted = nullptr);
31   // Retrieves a stored stack trace by the id.
32   args_type Get(u32 id);
33 
GetStats()34   StackDepotStats *GetStats() { return &stats; }
35 
36   void LockAll();
37   void UnlockAll();
38 
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 
44   static const int kTabSize = 1 << kTabSizeLog;  // Hash table size.
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 
60 template <class Node, int kReservedBits, int kTabSizeLog>
find(Node * s,args_type args,u32 hash)61 Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(Node *s,
62                                                              args_type args,
63                                                              u32 hash) {
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   }
70   return nullptr;
71 }
72 
73 template <class Node, int kReservedBits, int kTabSizeLog>
lock(atomic_uintptr_t * p)74 Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::lock(
75     atomic_uintptr_t *p) {
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 
89 template <class Node, int kReservedBits, int kTabSizeLog>
unlock(atomic_uintptr_t * p,Node * s)90 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::unlock(
91     atomic_uintptr_t *p, Node *s) {
92   DCHECK_EQ((uptr)s & 1, 0);
93   atomic_store(p, (uptr)s, memory_order_release);
94 }
95 
96 template <class Node, int kReservedBits, int kTabSizeLog>
97 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::handle_type
Put(args_type args,bool * inserted)98 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,
99                                                       bool *inserted) {
100   if (inserted) *inserted = false;
101   if (!Node::is_valid(args)) return handle_type();
102   uptr h = Node::hash(args);
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 
136 template <class Node, int kReservedBits, int kTabSizeLog>
137 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type
Get(u32 id)138 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Get(u32 id) {
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 
160 template <class Node, int kReservedBits, int kTabSizeLog>
LockAll()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>
UnlockAll()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 
176 } // namespace __sanitizer
177 
178 #endif // SANITIZER_STACKDEPOTBASE_H
179