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" 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 161b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov#include "sanitizer_common.h" 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_stackdepotbase.h" 181b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 191b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukovnamespace __sanitizer { 201b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstruct StackDepotDesc { 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const uptr *stack; 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size; 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 hash() const { 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // murmur2 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const u32 m = 0x5bd1e995; 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const u32 seed = 0x9747b28c; 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const u32 r = 24; 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 h = seed ^ (size * sizeof(uptr)); 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < size; i++) { 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 k = stack[i]; 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines k *= m; 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines k ^= k >> r; 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines k *= m; 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h *= m; 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h ^= k; 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h ^= h >> 13; 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h *= m; 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h ^= h >> 15; 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return h; 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool is_valid() { return size > 0 && stack; } 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 4584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstruct StackDepotNode { 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode *link; 481b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov u32 id; 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20; 501b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov uptr size; 5184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr stack[1]; // [size] 521b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 535d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines static const u32 kTabSizeLog = 20; 545d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines // Lower kTabSizeLog bits are equal for all items in one bucket. 555d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines // We use these bits to store the per-stack use counter. 565d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines static const u32 kUseCountBits = kTabSizeLog; 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const u32 kMaxUseCount = 1 << kUseCountBits; 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const u32 kUseCountMask = (1 << kUseCountBits) - 1; 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const u32 kHashMask = ~kUseCountMask; 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typedef StackDepotDesc args_type; 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool eq(u32 hash, const args_type &args) const { 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 hash_bits = 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask; 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if ((hash & kHashMask) != hash_bits || args.size != size) return false; 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i = 0; 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (; i < size; i++) { 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (stack[i] != args.stack[i]) return false; 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static uptr storage_size(const args_type &args) { 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr); 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void store(const args_type &args, u32 hash) { 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed); 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines size = args.size; 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines internal_memcpy(stack, args.stack, size * sizeof(uptr)); 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines args_type load() const { 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines args_type ret = {&stack[0], size}; 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return ret; 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotHandle get_handle() { return StackDepotHandle(this); } 851b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typedef StackDepotHandle handle_type; 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 889e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesCOMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount); 909e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesu32 StackDepotHandle::id() { return node_->id; } 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesint StackDepotHandle::use_count() { 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) & 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode::kUseCountMask; 9584112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid StackDepotHandle::inc_use_count_unsafe() { 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 prev = 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) & 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode::kUseCountMask; 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount); 1011b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesuptr StackDepotHandle::size() { return node_->size; } 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesuptr *StackDepotHandle::stack() { return &node_->stack[0]; } 1041b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// FIXME(dvyukov): this single reserved bit is used in TSan. 1065d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestypedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog> 1075d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines StackDepot; 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstatic StackDepot theDepot; 10984112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesStackDepotStats *StackDepotGetStats() { 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return theDepot.GetStats(); 11284112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 11384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesu32 StackDepotPut(const uptr *stack, uptr size) { 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotDesc desc = {stack, size}; 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotHandle h = theDepot.Put(desc); 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return h.valid() ? h.id() : 0; 1181b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1191b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesStackDepotHandle StackDepotPut_WithHandle(const uptr *stack, uptr size) { 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotDesc desc = {stack, size}; 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return theDepot.Put(desc); 1231b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1241b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 125ff35f1d82b4f145b3477ef27a7a2e7b63c486988Dmitry Vyukovconst uptr *StackDepotGet(u32 id, uptr *size) { 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotDesc desc = theDepot.Get(id); 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *size = desc.size; 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return desc.stack; 1291b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1301b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 131384a448fbe081352f7b3bb927093412ad1725cffSergey Matveevbool StackDepotReverseMap::IdDescPair::IdComparator( 132384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev const StackDepotReverseMap::IdDescPair &a, 133384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev const StackDepotReverseMap::IdDescPair &b) { 134384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev return a.id < b.id; 135384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev} 136384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev 137384a448fbe081352f7b3bb927093412ad1725cffSergey MatveevStackDepotReverseMap::StackDepotReverseMap() 138384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev : map_(StackDepotGetStats()->n_uniq_ids + 100) { 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int idx = 0; idx < StackDepot::kTabSize; idx++) { 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t *p = &theDepot.tab[idx]; 141384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev uptr v = atomic_load(p, memory_order_consume); 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode *s = (StackDepotNode*)(v & ~1); 143384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev for (; s; s = s->link) { 144384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev IdDescPair pair = {s->id, s}; 145384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev map_.push_back(pair); 146384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev } 147384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev } 148384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev InternalSort(&map_, map_.size(), IdDescPair::IdComparator); 149384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev} 150384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev 151384a448fbe081352f7b3bb927093412ad1725cffSergey Matveevconst uptr *StackDepotReverseMap::Get(u32 id, uptr *size) { 152384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev if (!map_.size()) return 0; 153384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev IdDescPair pair = {id, 0}; 154384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair, 155384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev IdDescPair::IdComparator); 156384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev if (idx > map_.size()) { 157384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev *size = 0; 158384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev return 0; 159384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev } 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode *desc = map_[idx].desc; 161384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev *size = desc->size; 162384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev return desc->stack; 163384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev} 164384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev 1651b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} // namespace __sanitizer 166