11320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===-- sanitizer_stackdepot.cc -------------------------------------------===// 21320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 31320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// The LLVM Compiler Infrastructure 41320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 51320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// This file is distributed under the University of Illinois Open Source 61320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// License. See LICENSE.TXT for details. 71320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 81320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 91320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// This file is shared between AddressSanitizer and ThreadSanitizer 111320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// run-time libraries. 121320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 131320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "sanitizer_stackdepot.h" 151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "sanitizer_common.h" 171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "sanitizer_stackdepotbase.h" 181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccinamespace __sanitizer { 201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccistruct StackDepotDesc { 221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const uptr *stack; 231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uptr size; 241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci u32 hash() const { 251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // murmur2 261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const u32 m = 0x5bd1e995; 271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const u32 seed = 0x9747b28c; 281320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const u32 r = 24; 291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci u32 h = seed ^ (size * sizeof(uptr)); 301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (uptr i = 0; i < size; i++) { 311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci u32 k = stack[i]; 321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci k *= m; 331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci k ^= k >> r; 341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci k *= m; 351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci h *= m; 361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci h ^= k; 371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci h ^= h >> 13; 391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci h *= m; 401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci h ^= h >> 15; 411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return h; 421320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 431320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool is_valid() { return size > 0 && stack; } 441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci}; 451320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 461320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccistruct StackDepotNode { 471320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotNode *link; 481320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci u32 id; 491320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20; 501320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uptr size; 511320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uptr stack[1]; // [size] 521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static const u32 kTabSizeLog = 20; 541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Lower kTabSizeLog bits are equal for all items in one bucket. 551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // We use these bits to store the per-stack use counter. 561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static const u32 kUseCountBits = kTabSizeLog; 571320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static const u32 kMaxUseCount = 1 << kUseCountBits; 581320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static const u32 kUseCountMask = (1 << kUseCountBits) - 1; 591320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static const u32 kHashMask = ~kUseCountMask; 601320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 611320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef StackDepotDesc args_type; 621320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool eq(u32 hash, const args_type &args) const { 631320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci u32 hash_bits = 641320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask; 651320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if ((hash & kHashMask) != hash_bits || args.size != size) return false; 661320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uptr i = 0; 671320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (; i < size; i++) { 681320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (stack[i] != args.stack[i]) return false; 691320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 701320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return true; 711320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static uptr storage_size(const args_type &args) { 731320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr); 741320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void store(const args_type &args, u32 hash) { 761320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed); 771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci size = args.size; 781320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci internal_memcpy(stack, args.stack, size * sizeof(uptr)); 791320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 801320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci args_type load() const { 811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci args_type ret = {&stack[0], size}; 821320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return ret; 831320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 841320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotHandle get_handle() { return StackDepotHandle(this); } 851320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 861320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef StackDepotHandle handle_type; 871320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci}; 881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 891320f92c476a1ad9d19dba2a48c72b75566198e9Primiano TucciCOMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount); 901320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 911320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciu32 StackDepotHandle::id() { return node_->id; } 921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciint StackDepotHandle::use_count() { 931320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) & 941320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotNode::kUseCountMask; 951320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 961320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccivoid StackDepotHandle::inc_use_count_unsafe() { 971320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci u32 prev = 981320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) & 991320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotNode::kUseCountMask; 1001320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount); 1011320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 1021320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciuptr StackDepotHandle::size() { return node_->size; } 1031320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciuptr *StackDepotHandle::stack() { return &node_->stack[0]; } 1041320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1051320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// FIXME(dvyukov): this single reserved bit is used in TSan. 1061320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccitypedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog> 1071320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepot; 1081320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccistatic StackDepot theDepot; 1091320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano TucciStackDepotStats *StackDepotGetStats() { 1111320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return theDepot.GetStats(); 1121320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 1131320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciu32 StackDepotPut(const uptr *stack, uptr size) { 1151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotDesc desc = {stack, size}; 1161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotHandle h = theDepot.Put(desc); 1171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return h.valid() ? h.id() : 0; 1181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 1191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano TucciStackDepotHandle StackDepotPut_WithHandle(const uptr *stack, uptr size) { 1211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotDesc desc = {stack, size}; 1221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return theDepot.Put(desc); 1231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 1241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciconst uptr *StackDepotGet(u32 id, uptr *size) { 1261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotDesc desc = theDepot.Get(id); 1271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci *size = desc.size; 1281320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return desc.stack; 1291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 1301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccibool StackDepotReverseMap::IdDescPair::IdComparator( 1321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const StackDepotReverseMap::IdDescPair &a, 1331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const StackDepotReverseMap::IdDescPair &b) { 1341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return a.id < b.id; 1351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 1361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano TucciStackDepotReverseMap::StackDepotReverseMap() 1381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci : map_(StackDepotGetStats()->n_uniq_ids + 100) { 1391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (int idx = 0; idx < StackDepot::kTabSize; idx++) { 1401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci atomic_uintptr_t *p = &theDepot.tab[idx]; 1411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uptr v = atomic_load(p, memory_order_consume); 1421320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotNode *s = (StackDepotNode*)(v & ~1); 1431320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (; s; s = s->link) { 1441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci IdDescPair pair = {s->id, s}; 1451320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci map_.push_back(pair); 1461320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1471320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1481320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci InternalSort(&map_, map_.size(), IdDescPair::IdComparator); 1491320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci} 1501320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1511320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciconst uptr *StackDepotReverseMap::Get(u32 id, uptr *size) { 1521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (!map_.size()) return 0; 1531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci IdDescPair pair = {id, 0}; 1541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair, 1551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci IdDescPair::IdComparator); 1561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (idx > map_.size()) { 1571320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci *size = 0; 1581320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return 0; 1591320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1601320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci StackDepotNode *desc = map_[idx].desc; 1611320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci *size = desc->size; 1621320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return desc->stack; 163} 164 165} // namespace __sanitizer 166