• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- sanitizer_stackdepot.cc -------------------------------------------===//
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 // This file is shared between AddressSanitizer and ThreadSanitizer
11 // run-time libraries.
12 //===----------------------------------------------------------------------===//
13 
14 #include "sanitizer_stackdepot.h"
15 #include "sanitizer_common.h"
16 #include "sanitizer_internal_defs.h"
17 #include "sanitizer_mutex.h"
18 #include "sanitizer_atomic.h"
19 
20 namespace __sanitizer {
21 
22 const int kTabSize = 1024 * 1024;  // Hash table size.
23 const int kPartBits = 8;
24 const int kPartShift = sizeof(u32) * 8 - kPartBits - 1;
25 const int kPartCount = 1 << kPartBits;  // Number of subparts in the table.
26 const int kPartSize = kTabSize / kPartCount;
27 const int kMaxId = 1 << kPartShift;
28 
29 struct StackDesc {
30   StackDesc *link;
31   u32 id;
32   u32 hash;
33   uptr size;
34   uptr stack[1];  // [size]
35 };
36 
37 static struct {
38   StaticSpinMutex mtx;  // Protects alloc of new blocks for region allocator.
39   atomic_uintptr_t region_pos;  // Region allocator for StackDesc's.
40   atomic_uintptr_t region_end;
41   atomic_uintptr_t tab[kTabSize];  // Hash table of StackDesc's.
42   atomic_uint32_t seq[kPartCount];  // Unique id generators.
43 } depot;
44 
45 static StackDepotStats stats;
46 
StackDepotGetStats()47 StackDepotStats *StackDepotGetStats() {
48   return &stats;
49 }
50 
hash(const uptr * stack,uptr size)51 static u32 hash(const uptr *stack, uptr size) {
52   // murmur2
53   const u32 m = 0x5bd1e995;
54   const u32 seed = 0x9747b28c;
55   const u32 r = 24;
56   u32 h = seed ^ (size * sizeof(uptr));
57   for (uptr i = 0; i < size; i++) {
58     u32 k = stack[i];
59     k *= m;
60     k ^= k >> r;
61     k *= m;
62     h *= m;
63     h ^= k;
64   }
65   h ^= h >> 13;
66   h *= m;
67   h ^= h >> 15;
68   return h;
69 }
70 
tryallocDesc(uptr memsz)71 static StackDesc *tryallocDesc(uptr memsz) {
72   // Optimisic lock-free allocation, essentially try to bump the region ptr.
73   for (;;) {
74     uptr cmp = atomic_load(&depot.region_pos, memory_order_acquire);
75     uptr end = atomic_load(&depot.region_end, memory_order_acquire);
76     if (cmp == 0 || cmp + memsz > end)
77       return 0;
78     if (atomic_compare_exchange_weak(
79         &depot.region_pos, &cmp, cmp + memsz,
80         memory_order_acquire))
81       return (StackDesc*)cmp;
82   }
83 }
84 
allocDesc(uptr size)85 static StackDesc *allocDesc(uptr size) {
86   // First, try to allocate optimisitically.
87   uptr memsz = sizeof(StackDesc) + (size - 1) * sizeof(uptr);
88   StackDesc *s = tryallocDesc(memsz);
89   if (s)
90     return s;
91   // If failed, lock, retry and alloc new superblock.
92   SpinMutexLock l(&depot.mtx);
93   for (;;) {
94     s = tryallocDesc(memsz);
95     if (s)
96       return s;
97     atomic_store(&depot.region_pos, 0, memory_order_relaxed);
98     uptr allocsz = 64 * 1024;
99     if (allocsz < memsz)
100       allocsz = memsz;
101     uptr mem = (uptr)MmapOrDie(allocsz, "stack depot");
102     stats.mapped += allocsz;
103     atomic_store(&depot.region_end, mem + allocsz, memory_order_release);
104     atomic_store(&depot.region_pos, mem, memory_order_release);
105   }
106 }
107 
find(StackDesc * s,const uptr * stack,uptr size,u32 hash)108 static u32 find(StackDesc *s, const uptr *stack, uptr size, u32 hash) {
109   // Searches linked list s for the stack, returns its id.
110   for (; s; s = s->link) {
111     if (s->hash == hash && s->size == size) {
112       uptr i = 0;
113       for (; i < size; i++) {
114         if (stack[i] != s->stack[i])
115           break;
116       }
117       if (i == size)
118         return s->id;
119     }
120   }
121   return 0;
122 }
123 
lock(atomic_uintptr_t * p)124 static StackDesc *lock(atomic_uintptr_t *p) {
125   // Uses the pointer lsb as mutex.
126   for (int i = 0;; i++) {
127     uptr cmp = atomic_load(p, memory_order_relaxed);
128     if ((cmp & 1) == 0
129         && atomic_compare_exchange_weak(p, &cmp, cmp | 1,
130                                         memory_order_acquire))
131       return (StackDesc*)cmp;
132     if (i < 10)
133       proc_yield(10);
134     else
135       internal_sched_yield();
136   }
137 }
138 
unlock(atomic_uintptr_t * p,StackDesc * s)139 static void unlock(atomic_uintptr_t *p, StackDesc *s) {
140   DCHECK_EQ((uptr)s & 1, 0);
141   atomic_store(p, (uptr)s, memory_order_release);
142 }
143 
StackDepotPut(const uptr * stack,uptr size)144 u32 StackDepotPut(const uptr *stack, uptr size) {
145   if (stack == 0 || size == 0)
146     return 0;
147   uptr h = hash(stack, size);
148   atomic_uintptr_t *p = &depot.tab[h % kTabSize];
149   uptr v = atomic_load(p, memory_order_consume);
150   StackDesc *s = (StackDesc*)(v & ~1);
151   // First, try to find the existing stack.
152   u32 id = find(s, stack, size, h);
153   if (id)
154     return id;
155   // If failed, lock, retry and insert new.
156   StackDesc *s2 = lock(p);
157   if (s2 != s) {
158     id = find(s2, stack, size, h);
159     if (id) {
160       unlock(p, s2);
161       return id;
162     }
163   }
164   uptr part = (h % kTabSize) / kPartSize;
165   id = atomic_fetch_add(&depot.seq[part], 1, memory_order_relaxed) + 1;
166   stats.n_uniq_ids++;
167   CHECK_LT(id, kMaxId);
168   id |= part << kPartShift;
169   CHECK_NE(id, 0);
170   CHECK_EQ(id & (1u << 31), 0);
171   s = allocDesc(size);
172   s->id = id;
173   s->hash = h;
174   s->size = size;
175   internal_memcpy(s->stack, stack, size * sizeof(uptr));
176   s->link = s2;
177   unlock(p, s);
178   return id;
179 }
180 
StackDepotGet(u32 id,uptr * size)181 const uptr *StackDepotGet(u32 id, uptr *size) {
182   if (id == 0)
183     return 0;
184   CHECK_EQ(id & (1u << 31), 0);
185   // High kPartBits contain part id, so we need to scan at most kPartSize lists.
186   uptr part = id >> kPartShift;
187   for (int i = 0; i != kPartSize; i++) {
188     uptr idx = part * kPartSize + i;
189     CHECK_LT(idx, kTabSize);
190     atomic_uintptr_t *p = &depot.tab[idx];
191     uptr v = atomic_load(p, memory_order_consume);
192     StackDesc *s = (StackDesc*)(v & ~1);
193     for (; s; s = s->link) {
194       if (s->id == id) {
195         *size = s->size;
196         return s->stack;
197       }
198     }
199   }
200   *size = 0;
201   return 0;
202 }
203 
204 }  // namespace __sanitizer
205