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