sanitizer_stackdepot.cc revision d0dc91869f197d2df69ceaecce0889931e18de67
18d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt//===-- sanitizer_stackdepot.cc -------------------------------------------===// 28d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// 38d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// The LLVM Compiler Infrastructure 48d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// 58d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// This file is distributed under the University of Illinois Open Source 6c5ec7f57ead87efa365800228aa0b09a12d9e6c4Dmitry Shmidt// License. See LICENSE.TXT for details. 7c5ec7f57ead87efa365800228aa0b09a12d9e6c4Dmitry Shmidt// 88d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt//===----------------------------------------------------------------------===// 98d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// 108d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// This file is shared between AddressSanitizer and ThreadSanitizer 118d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// run-time libraries. 128d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt//===----------------------------------------------------------------------===// 138d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 148d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "sanitizer_stackdepot.h" 158d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "sanitizer_common.h" 168d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "sanitizer_internal_defs.h" 178d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "sanitizer_mutex.h" 188d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "sanitizer_atomic.h" 198d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 208d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtnamespace __sanitizer { 218d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 228d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst int kTabSize = 1024 * 1024; // Hash table size. 238d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst int kPartBits = 8; 248d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst int kPartShift = sizeof(u32) * 8 - kPartBits - 1; 258d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst int kPartCount = 1 << kPartBits; // Number of subparts in the table. 268d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst int kPartSize = kTabSize / kPartCount; 278d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst int kMaxId = 1 << kPartShift; 288d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 298d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstruct StackDesc { 308d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt StackDesc *link; 318d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt u32 id; 328d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt u32 hash; 338d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr size; 348d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr stack[1]; // [size] 358d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt}; 368d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 378d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstatic struct { 388d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt StaticSpinMutex mtx; // Protects alloc of new blocks for region allocator. 398d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_uintptr_t region_pos; // Region allocator for StackDesc's. 408d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_uintptr_t region_end; 418d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_uintptr_t tab[kTabSize]; // Hash table of StackDesc's. 428d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_uint32_t seq[kPartCount]; // Unique id generators. 438d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} depot; 448d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 458d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstatic u32 hash(const uptr *stack, uptr size) { 468d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // murmur2 478d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const u32 m = 0x5bd1e995; 488d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const u32 seed = 0x9747b28c; 498d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const u32 r = 24; 508d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt u32 h = seed ^ (size * sizeof(uptr)); 518d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (uptr i = 0; i < size; i++) { 528d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt u32 k = stack[i]; 538d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt k *= m; 548d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt k ^= k >> r; 558d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt k *= m; 568d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt h *= m; 578d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt h ^= k; 588d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 598d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt h ^= h >> 13; 608d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt h *= m; 618d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt h ^= h >> 15; 628d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return h; 638d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 648d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 658d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstatic StackDesc *tryallocDesc(uptr memsz) { 668d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Optimisic lock-free allocation, essentially try to bump the region ptr. 678d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (;;) { 688d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr cmp = atomic_load(&depot.region_pos, memory_order_acquire); 698d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr end = atomic_load(&depot.region_end, memory_order_acquire); 708d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (cmp == 0 || cmp + memsz > end) 718d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return 0; 728d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (atomic_compare_exchange_weak( 738d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt &depot.region_pos, &cmp, cmp + memsz, 748d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt memory_order_acquire)) 758d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return (StackDesc*)cmp; 768d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 778d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 788d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 79d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidtstatic StackDesc *allocDesc(uptr size) { 808d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Frist, try to allocate optimisitically. 818d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr memsz = sizeof(StackDesc) + (size - 1) * sizeof(uptr); 828d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt StackDesc *s = tryallocDesc(memsz); 838d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (s) 848d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return s; 858d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // If failed, lock, retry and alloc new superblock. 868d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SpinMutexLock l(&depot.mtx); 878d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (;;) { 888d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt s = tryallocDesc(memsz); 898d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (s) 908d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return s; 918d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_store(&depot.region_pos, 0, memory_order_relaxed); 928d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr allocsz = 64 * 1024; 938d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (allocsz < memsz) 948d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt allocsz = memsz; 958d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr mem = (uptr)MmapOrDie(allocsz, "stack depot"); 968d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_store(&depot.region_end, mem + allocsz, memory_order_release); 978d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_store(&depot.region_pos, mem, memory_order_release); 988d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 998d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1008d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1018d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstatic u32 find(StackDesc *s, const uptr *stack, uptr size, u32 hash) { 1028d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Searches linked list s for the stack, returns its id. 1038d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (; s; s = s->link) { 1048d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (s->hash == hash && s->size == size) { 1058d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr i = 0; 1068d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (; i < size; i++) { 1078d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (stack[i] != s->stack[i]) 1088d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt break; 1098d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 1108d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (i == size) 1118d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return s->id; 1128d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 1138d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 1148d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return 0; 1158d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1168d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1178d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstatic StackDesc *lock(atomic_uintptr_t *p) { 1188d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Uses the pointer lsb as mutex. 1198d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (int i = 0;; i++) { 1208d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr cmp = atomic_load(p, memory_order_relaxed); 1218d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if ((cmp & 1) == 0 1228d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt && atomic_compare_exchange_weak(p, &cmp, cmp | 1, 1238d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt memory_order_acquire)) 1248d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return (StackDesc*)cmp; 1258d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (i < 10) 1268d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt proc_yield(10); 1278d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt else 1288d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt internal_sched_yield(); 1298d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 1308d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1318d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1328d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstatic void unlock(atomic_uintptr_t *p, StackDesc *s) { 1338d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DCHECK_EQ((uptr)s & 1, 0); 1348d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_store(p, (uptr)s, memory_order_release); 1358d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1368d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1378d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtu32 StackDepotPut(const uptr *stack, uptr size) { 1388d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (stack == 0 || size == 0) 1398d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return 0; 1408d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr h = hash(stack, size); 1418d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_uintptr_t *p = &depot.tab[h % kTabSize]; 1428d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr v = atomic_load(p, memory_order_consume); 1438d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt StackDesc *s = (StackDesc*)(v & ~1); 1448d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // First, try to find the existing stack. 1458d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt u32 id = find(s, stack, size, h); 1468d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (id) 1478d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return id; 1488d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // If failed, lock, retry and insert new. 1498d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt StackDesc *s2 = lock(p); 1508d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (s2 != s) { 1511f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt id = find(s2, stack, size, h); 1521f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt if (id) { 1531f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt unlock(p, s2); 1541f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt return id; 1551f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 1561f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 1571f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt uptr part = (h % kTabSize) / kPartSize; 1581f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt id = atomic_fetch_add(&depot.seq[part], 1, memory_order_relaxed) + 1; 1591f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt CHECK_LT(id, kMaxId); 1608d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt id |= part << kPartShift; 161d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt CHECK_NE(id, 0); 162d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt CHECK_EQ(id & (1u << 31), 0); 1631f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt s = allocDesc(size); 1647d5c8f257a74ac0d12828962a492e8b84ef83923Dmitry Shmidt s->id = id; 165fb79edc9df1f20461e90e478363d207348213d35Dmitry Shmidt s->hash = h; 1668d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt s->size = size; 1678d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt internal_memcpy(s->stack, stack, size * sizeof(uptr)); 1688d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt s->link = s2; 1698d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt unlock(p, s); 1708d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return id; 1718d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1728d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1738d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst uptr *StackDepotGet(u32 id, uptr *size) { 1748d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (id == 0) 1758d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return 0; 1768d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt CHECK_EQ(id & (1u << 31), 0); 1778d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // High kPartBits contain part id, so we need to scan at most kPartSize lists. 1788d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr part = id >> kPartShift; 1798d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (int i = 0; i != kPartSize; i++) { 1808d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr idx = part * kPartSize + i; 1818d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt CHECK_LT(idx, kTabSize); 1828d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt atomic_uintptr_t *p = &depot.tab[idx]; 1838d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt uptr v = atomic_load(p, memory_order_consume); 1848d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt StackDesc *s = (StackDesc*)(v & ~1); 1858d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (; s; s = s->link) { 1868d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (s->id == id) { 1878d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt *size = s->size; 1888d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return s->stack; 1898d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 1908d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 1918d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 1928d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt *size = 0; 1938d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return 0; 1948d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1958d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1968d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} // namespace __sanitizer 1978d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt