1 //===-- sanitizer_stackdepot.cc -------------------------------------------===// 2 // 3 // This file is distributed under the University of Illinois Open Source 4 // License. See LICENSE.TXT for details. 5 // 6 //===----------------------------------------------------------------------===// 7 // 8 // This file is shared between AddressSanitizer and ThreadSanitizer 9 // run-time libraries. 10 //===----------------------------------------------------------------------===// 11 12 #include "sanitizer_stackdepot.h" 13 14 #include "sanitizer_common.h" 15 #include "sanitizer_stackdepotbase.h" 16 17 namespace __sanitizer { 18 19 struct StackDepotNode { 20 StackDepotNode *link; 21 u32 id; 22 atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20; 23 u32 size; 24 u32 tag; 25 uptr stack[1]; // [size] 26 27 static const u32 kTabSizeLog = 20; 28 // Lower kTabSizeLog bits are equal for all items in one bucket. 29 // We use these bits to store the per-stack use counter. 30 static const u32 kUseCountBits = kTabSizeLog; 31 static const u32 kMaxUseCount = 1 << kUseCountBits; 32 static const u32 kUseCountMask = (1 << kUseCountBits) - 1; 33 static const u32 kHashMask = ~kUseCountMask; 34 35 typedef StackTrace args_type; 36 bool eq(u32 hash, const args_type &args) const { 37 u32 hash_bits = 38 atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask; 39 if ((hash & kHashMask) != hash_bits || args.size != size || args.tag != tag) 40 return false; 41 uptr i = 0; 42 for (; i < size; i++) { 43 if (stack[i] != args.trace[i]) return false; 44 } 45 return true; 46 } 47 static uptr storage_size(const args_type &args) { 48 return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr); 49 } 50 static u32 hash(const args_type &args) { 51 // murmur2 52 const u32 m = 0x5bd1e995; 53 const u32 seed = 0x9747b28c; 54 const u32 r = 24; 55 u32 h = seed ^ (args.size * sizeof(uptr)); 56 for (uptr i = 0; i < args.size; i++) { 57 u32 k = args.trace[i]; 58 k *= m; 59 k ^= k >> r; 60 k *= m; 61 h *= m; 62 h ^= k; 63 } 64 h ^= h >> 13; 65 h *= m; 66 h ^= h >> 15; 67 return h; 68 } 69 static bool is_valid(const args_type &args) { 70 return args.size > 0 && args.trace; 71 } 72 void store(const args_type &args, u32 hash) { 73 atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed); 74 size = args.size; 75 tag = args.tag; 76 internal_memcpy(stack, args.trace, size * sizeof(uptr)); 77 } 78 args_type load() const { 79 return args_type(&stack[0], size, tag); 80 } 81 StackDepotHandle get_handle() { return StackDepotHandle(this); } 82 83 typedef StackDepotHandle handle_type; 84 }; 85 86 COMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount); 87 88 u32 StackDepotHandle::id() { return node_->id; } 89 int StackDepotHandle::use_count() { 90 return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) & 91 StackDepotNode::kUseCountMask; 92 } 93 void StackDepotHandle::inc_use_count_unsafe() { 94 u32 prev = 95 atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) & 96 StackDepotNode::kUseCountMask; 97 CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount); 98 } 99 100 // FIXME(dvyukov): this single reserved bit is used in TSan. 101 typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog> 102 StackDepot; 103 static StackDepot theDepot; 104 105 StackDepotStats *StackDepotGetStats() { 106 return theDepot.GetStats(); 107 } 108 109 u32 StackDepotPut(StackTrace stack) { 110 StackDepotHandle h = theDepot.Put(stack); 111 return h.valid() ? h.id() : 0; 112 } 113 114 StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) { 115 return theDepot.Put(stack); 116 } 117 118 StackTrace StackDepotGet(u32 id) { 119 return theDepot.Get(id); 120 } 121 122 void StackDepotLockAll() { 123 theDepot.LockAll(); 124 } 125 126 void StackDepotUnlockAll() { 127 theDepot.UnlockAll(); 128 } 129 130 bool StackDepotReverseMap::IdDescPair::IdComparator( 131 const StackDepotReverseMap::IdDescPair &a, 132 const StackDepotReverseMap::IdDescPair &b) { 133 return a.id < b.id; 134 } 135 136 StackDepotReverseMap::StackDepotReverseMap() { 137 map_.reserve(StackDepotGetStats()->n_uniq_ids + 100); 138 for (int idx = 0; idx < StackDepot::kTabSize; idx++) { 139 atomic_uintptr_t *p = &theDepot.tab[idx]; 140 uptr v = atomic_load(p, memory_order_consume); 141 StackDepotNode *s = (StackDepotNode*)(v & ~1); 142 for (; s; s = s->link) { 143 IdDescPair pair = {s->id, s}; 144 map_.push_back(pair); 145 } 146 } 147 Sort(map_.data(), map_.size(), &IdDescPair::IdComparator); 148 } 149 150 StackTrace StackDepotReverseMap::Get(u32 id) { 151 if (!map_.size()) 152 return StackTrace(); 153 IdDescPair pair = {id, nullptr}; 154 uptr idx = 155 InternalLowerBound(map_, 0, map_.size(), pair, IdDescPair::IdComparator); 156 if (idx > map_.size() || map_[idx].id != id) 157 return StackTrace(); 158 return map_[idx].desc->load(); 159 } 160 161 } // namespace __sanitizer 162