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 47 StackDepotStats *StackDepotGetStats() { 48 return &stats; 49 } 50 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 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 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 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 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 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 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 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
