sanitizer_stackdepot.cc revision 9e3bd38388a7c182db57f6e3fc0943e6d12f012e
11b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov//===-- sanitizer_stackdepot.cc -------------------------------------------===// 21b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// 31b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// The LLVM Compiler Infrastructure 41b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// 51b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// This file is distributed under the University of Illinois Open Source 61b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// License. See LICENSE.TXT for details. 71b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// 81b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov//===----------------------------------------------------------------------===// 91b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// 101b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// This file is shared between AddressSanitizer and ThreadSanitizer 111b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov// run-time libraries. 121b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov//===----------------------------------------------------------------------===// 131b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 141b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov#include "sanitizer_stackdepot.h" 151b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov#include "sanitizer_common.h" 16d0dc91869f197d2df69ceaecce0889931e18de67Dmitry Vyukov#include "sanitizer_internal_defs.h" 171b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov#include "sanitizer_mutex.h" 1884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov#include "sanitizer_atomic.h" 191b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 201b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukovnamespace __sanitizer { 211b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 2284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovconst int kTabSize = 1024 * 1024; // Hash table size. 23d0dc91869f197d2df69ceaecce0889931e18de67Dmitry Vyukovconst int kPartBits = 8; 24d0dc91869f197d2df69ceaecce0889931e18de67Dmitry Vyukovconst int kPartShift = sizeof(u32) * 8 - kPartBits - 1; 2584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovconst int kPartCount = 1 << kPartBits; // Number of subparts in the table. 2684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovconst int kPartSize = kTabSize / kPartCount; 2784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovconst int kMaxId = 1 << kPartShift; 2884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 291b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukovstruct StackDesc { 301b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov StackDesc *link; 311b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov u32 id; 3284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov u32 hash; 331b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov uptr size; 3484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr stack[1]; // [size] 351b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov}; 361b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 371b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukovstatic struct { 3884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov StaticSpinMutex mtx; // Protects alloc of new blocks for region allocator. 3984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_uintptr_t region_pos; // Region allocator for StackDesc's. 4084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_uintptr_t region_end; 4184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_uintptr_t tab[kTabSize]; // Hash table of StackDesc's. 4284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_uint32_t seq[kPartCount]; // Unique id generators. 431b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} depot; 441b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 459e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryanystatic StackDepotStats stats; 469e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany 479e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya SerebryanyStackDepotStats *StackDepotGetStats() { 489e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany return &stats; 499e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany} 509e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany 5184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovstatic u32 hash(const uptr *stack, uptr size) { 5284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // murmur2 5384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov const u32 m = 0x5bd1e995; 5484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov const u32 seed = 0x9747b28c; 5584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov const u32 r = 24; 5684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov u32 h = seed ^ (size * sizeof(uptr)); 5784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (uptr i = 0; i < size; i++) { 5884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov u32 k = stack[i]; 5984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov k *= m; 6084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov k ^= k >> r; 6184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov k *= m; 6284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov h *= m; 6384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov h ^= k; 6484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 6584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov h ^= h >> 13; 6684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov h *= m; 6784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov h ^= h >> 15; 6884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return h; 6984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 7084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 7184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovstatic StackDesc *tryallocDesc(uptr memsz) { 7284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // Optimisic lock-free allocation, essentially try to bump the region ptr. 7384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (;;) { 7484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr cmp = atomic_load(&depot.region_pos, memory_order_acquire); 7584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr end = atomic_load(&depot.region_end, memory_order_acquire); 7684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (cmp == 0 || cmp + memsz > end) 7784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return 0; 7884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (atomic_compare_exchange_weak( 7984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov &depot.region_pos, &cmp, cmp + memsz, 8084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov memory_order_acquire)) 8184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return (StackDesc*)cmp; 8284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 831b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 841b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 851b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukovstatic StackDesc *allocDesc(uptr size) { 869e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany // First, try to allocate optimisitically. 871b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov uptr memsz = sizeof(StackDesc) + (size - 1) * sizeof(uptr); 8884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov StackDesc *s = tryallocDesc(memsz); 8984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (s) 9084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return s; 9184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // If failed, lock, retry and alloc new superblock. 9284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov SpinMutexLock l(&depot.mtx); 9384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (;;) { 9484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov s = tryallocDesc(memsz); 9584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (s) 9684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return s; 9784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_store(&depot.region_pos, 0, memory_order_relaxed); 9884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr allocsz = 64 * 1024; 991b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov if (allocsz < memsz) 1001b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov allocsz = memsz; 10184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr mem = (uptr)MmapOrDie(allocsz, "stack depot"); 1029e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany stats.mapped += allocsz; 10384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_store(&depot.region_end, mem + allocsz, memory_order_release); 10484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_store(&depot.region_pos, mem, memory_order_release); 10584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 10684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 10784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 10884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovstatic u32 find(StackDesc *s, const uptr *stack, uptr size, u32 hash) { 10984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // Searches linked list s for the stack, returns its id. 11084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (; s; s = s->link) { 11184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (s->hash == hash && s->size == size) { 11284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr i = 0; 11384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (; i < size; i++) { 11484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (stack[i] != s->stack[i]) 11584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov break; 11684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 11784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (i == size) 11884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return s->id; 11984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 12084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 12184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return 0; 12284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 12384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 12484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovstatic StackDesc *lock(atomic_uintptr_t *p) { 12584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // Uses the pointer lsb as mutex. 12684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (int i = 0;; i++) { 12784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr cmp = atomic_load(p, memory_order_relaxed); 12884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if ((cmp & 1) == 0 12984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov && atomic_compare_exchange_weak(p, &cmp, cmp | 1, 13084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov memory_order_acquire)) 13184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return (StackDesc*)cmp; 13284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (i < 10) 13384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov proc_yield(10); 13484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov else 13584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov internal_sched_yield(); 1361b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov } 13784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 13884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 13984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukovstatic void unlock(atomic_uintptr_t *p, StackDesc *s) { 14084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov DCHECK_EQ((uptr)s & 1, 0); 14184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_store(p, (uptr)s, memory_order_release); 1421b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1431b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 144ff35f1d82b4f145b3477ef27a7a2e7b63c486988Dmitry Vyukovu32 StackDepotPut(const uptr *stack, uptr size) { 1451b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov if (stack == 0 || size == 0) 1461b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov return 0; 1471b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov uptr h = hash(stack, size); 14884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_uintptr_t *p = &depot.tab[h % kTabSize]; 14984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr v = atomic_load(p, memory_order_consume); 15084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov StackDesc *s = (StackDesc*)(v & ~1); 15184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // First, try to find the existing stack. 15284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov u32 id = find(s, stack, size, h); 15384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (id) 15484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return id; 15584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // If failed, lock, retry and insert new. 15684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov StackDesc *s2 = lock(p); 15784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (s2 != s) { 15884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov id = find(s2, stack, size, h); 15984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (id) { 16084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov unlock(p, s2); 16184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return id; 16284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 1631b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov } 16484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr part = (h % kTabSize) / kPartSize; 16584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov id = atomic_fetch_add(&depot.seq[part], 1, memory_order_relaxed) + 1; 1669e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany stats.n_uniq_ids++; 16784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov CHECK_LT(id, kMaxId); 16884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov id |= part << kPartShift; 169d0dc91869f197d2df69ceaecce0889931e18de67Dmitry Vyukov CHECK_NE(id, 0); 170d0dc91869f197d2df69ceaecce0889931e18de67Dmitry Vyukov CHECK_EQ(id & (1u << 31), 0); 17184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov s = allocDesc(size); 17284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov s->id = id; 1731b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov s->hash = h; 1741b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov s->size = size; 1751b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov internal_memcpy(s->stack, stack, size * sizeof(uptr)); 17684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov s->link = s2; 17784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov unlock(p, s); 17884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return id; 1791b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1801b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 181ff35f1d82b4f145b3477ef27a7a2e7b63c486988Dmitry Vyukovconst uptr *StackDepotGet(u32 id, uptr *size) { 1821b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov if (id == 0) 1831b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov return 0; 184d0dc91869f197d2df69ceaecce0889931e18de67Dmitry Vyukov CHECK_EQ(id & (1u << 31), 0); 18584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov // High kPartBits contain part id, so we need to scan at most kPartSize lists. 18684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr part = id >> kPartShift; 18784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (int i = 0; i != kPartSize; i++) { 18884112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr idx = part * kPartSize + i; 18984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov CHECK_LT(idx, kTabSize); 19084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov atomic_uintptr_t *p = &depot.tab[idx]; 19184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr v = atomic_load(p, memory_order_consume); 19284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov StackDesc *s = (StackDesc*)(v & ~1); 19384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov for (; s; s = s->link) { 19484112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov if (s->id == id) { 19584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov *size = s->size; 19684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov return s->stack; 19784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov } 1981b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov } 1991b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov } 20084112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov *size = 0; 2011b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov return 0; 2021b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 2031b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 2041b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} // namespace __sanitizer 205