sanitizer_stackdepot.cc revision 6d1862363c88c183b0ed7740fca876342cf0474b
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 StackDepotNode { 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode *link; 231b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov u32 id; 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20; 251b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov uptr size; 2684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov uptr stack[1]; // [size] 271b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 286a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines static const u32 kTabSizeLog = 20; 296a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines // Lower kTabSizeLog bits are equal for all items in one bucket. 306a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines // We use these bits to store the per-stack use counter. 316a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines static const u32 kUseCountBits = kTabSizeLog; 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const u32 kMaxUseCount = 1 << kUseCountBits; 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const u32 kUseCountMask = (1 << kUseCountBits) - 1; 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const u32 kHashMask = ~kUseCountMask; 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 366d1862363c88c183b0ed7740fca876342cf0474bStephen Hines typedef StackTrace args_type; 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool eq(u32 hash, const args_type &args) const { 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 hash_bits = 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask; 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if ((hash & kHashMask) != hash_bits || args.size != size) return false; 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i = 0; 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (; i < size; i++) { 436d1862363c88c183b0ed7740fca876342cf0474bStephen Hines if (stack[i] != args.trace[i]) return false; 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static uptr storage_size(const args_type &args) { 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr); 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 506d1862363c88c183b0ed7740fca876342cf0474bStephen Hines static u32 hash(const args_type &args) { 516d1862363c88c183b0ed7740fca876342cf0474bStephen Hines // murmur2 526d1862363c88c183b0ed7740fca876342cf0474bStephen Hines const u32 m = 0x5bd1e995; 536d1862363c88c183b0ed7740fca876342cf0474bStephen Hines const u32 seed = 0x9747b28c; 546d1862363c88c183b0ed7740fca876342cf0474bStephen Hines const u32 r = 24; 556d1862363c88c183b0ed7740fca876342cf0474bStephen Hines u32 h = seed ^ (args.size * sizeof(uptr)); 566d1862363c88c183b0ed7740fca876342cf0474bStephen Hines for (uptr i = 0; i < args.size; i++) { 576d1862363c88c183b0ed7740fca876342cf0474bStephen Hines u32 k = args.trace[i]; 586d1862363c88c183b0ed7740fca876342cf0474bStephen Hines k *= m; 596d1862363c88c183b0ed7740fca876342cf0474bStephen Hines k ^= k >> r; 606d1862363c88c183b0ed7740fca876342cf0474bStephen Hines k *= m; 616d1862363c88c183b0ed7740fca876342cf0474bStephen Hines h *= m; 626d1862363c88c183b0ed7740fca876342cf0474bStephen Hines h ^= k; 636d1862363c88c183b0ed7740fca876342cf0474bStephen Hines } 646d1862363c88c183b0ed7740fca876342cf0474bStephen Hines h ^= h >> 13; 656d1862363c88c183b0ed7740fca876342cf0474bStephen Hines h *= m; 666d1862363c88c183b0ed7740fca876342cf0474bStephen Hines h ^= h >> 15; 676d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return h; 686d1862363c88c183b0ed7740fca876342cf0474bStephen Hines } 696d1862363c88c183b0ed7740fca876342cf0474bStephen Hines static bool is_valid(const args_type &args) { 706d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return args.size > 0 && args.trace; 716d1862363c88c183b0ed7740fca876342cf0474bStephen Hines } 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void store(const args_type &args, u32 hash) { 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed); 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines size = args.size; 756d1862363c88c183b0ed7740fca876342cf0474bStephen Hines internal_memcpy(stack, args.trace, size * sizeof(uptr)); 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines args_type load() const { 786d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return args_type(&stack[0], size); 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotHandle get_handle() { return StackDepotHandle(this); } 811b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typedef StackDepotHandle handle_type; 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 849e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesCOMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount); 869e3bd38388a7c182db57f6e3fc0943e6d12f012eKostya Serebryany 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesu32 StackDepotHandle::id() { return node_->id; } 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesint StackDepotHandle::use_count() { 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) & 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode::kUseCountMask; 9184112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid StackDepotHandle::inc_use_count_unsafe() { 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 prev = 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) & 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode::kUseCountMask; 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount); 971b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 981b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// FIXME(dvyukov): this single reserved bit is used in TSan. 1006a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hinestypedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog> 1016a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines StackDepot; 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstatic StackDepot theDepot; 10384112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesStackDepotStats *StackDepotGetStats() { 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return theDepot.GetStats(); 10684112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov} 10784112a3553bfe10dd4c9e20567495804a15f4545Dmitry Vyukov 1086d1862363c88c183b0ed7740fca876342cf0474bStephen Hinesu32 StackDepotPut(StackTrace stack) { 1096d1862363c88c183b0ed7740fca876342cf0474bStephen Hines StackDepotHandle h = theDepot.Put(stack); 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return h.valid() ? h.id() : 0; 1111b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1121b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 1136d1862363c88c183b0ed7740fca876342cf0474bStephen HinesStackDepotHandle StackDepotPut_WithHandle(StackTrace stack) { 1146d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return theDepot.Put(stack); 1151b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1161b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 1176d1862363c88c183b0ed7740fca876342cf0474bStephen HinesStackTrace StackDepotGet(u32 id) { 1186d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return theDepot.Get(id); 1196d1862363c88c183b0ed7740fca876342cf0474bStephen Hines} 1206d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 1216d1862363c88c183b0ed7740fca876342cf0474bStephen Hinesvoid StackDepotLockAll() { 1226d1862363c88c183b0ed7740fca876342cf0474bStephen Hines theDepot.LockAll(); 1236d1862363c88c183b0ed7740fca876342cf0474bStephen Hines} 1246d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 1256d1862363c88c183b0ed7740fca876342cf0474bStephen Hinesvoid StackDepotUnlockAll() { 1266d1862363c88c183b0ed7740fca876342cf0474bStephen Hines theDepot.UnlockAll(); 1271b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} 1281b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov 129384a448fbe081352f7b3bb927093412ad1725cffSergey Matveevbool StackDepotReverseMap::IdDescPair::IdComparator( 130384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev const StackDepotReverseMap::IdDescPair &a, 131384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev const StackDepotReverseMap::IdDescPair &b) { 132384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev return a.id < b.id; 133384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev} 134384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev 135384a448fbe081352f7b3bb927093412ad1725cffSergey MatveevStackDepotReverseMap::StackDepotReverseMap() 136384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev : map_(StackDepotGetStats()->n_uniq_ids + 100) { 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int idx = 0; idx < StackDepot::kTabSize; idx++) { 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t *p = &theDepot.tab[idx]; 139384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev uptr v = atomic_load(p, memory_order_consume); 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotNode *s = (StackDepotNode*)(v & ~1); 141384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev for (; s; s = s->link) { 142384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev IdDescPair pair = {s->id, s}; 143384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev map_.push_back(pair); 144384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev } 145384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev } 146384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev InternalSort(&map_, map_.size(), IdDescPair::IdComparator); 147384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev} 148384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev 1496d1862363c88c183b0ed7740fca876342cf0474bStephen HinesStackTrace StackDepotReverseMap::Get(u32 id) { 1506d1862363c88c183b0ed7740fca876342cf0474bStephen Hines if (!map_.size()) 1516d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return StackTrace(); 152384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev IdDescPair pair = {id, 0}; 153384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair, 154384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev IdDescPair::IdComparator); 1556d1862363c88c183b0ed7740fca876342cf0474bStephen Hines if (idx > map_.size()) 1566d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return StackTrace(); 1576d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return map_[idx].desc->load(); 158384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev} 159384a448fbe081352f7b3bb927093412ad1725cffSergey Matveev 1601b37017f0216d0b8f3ae3a7dea8b3cc20d74db25Dmitry Vyukov} // namespace __sanitizer 161