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