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"
15
16 #include "sanitizer_common.h"
17 #include "sanitizer_stackdepotbase.h"
18
19 namespace __sanitizer {
20
21 struct StackDepotDesc {
22 const uptr *stack;
23 uptr size;
hash__sanitizer::StackDepotDesc24 u32 hash() const {
25 // murmur2
26 const u32 m = 0x5bd1e995;
27 const u32 seed = 0x9747b28c;
28 const u32 r = 24;
29 u32 h = seed ^ (size * sizeof(uptr));
30 for (uptr i = 0; i < size; i++) {
31 u32 k = stack[i];
32 k *= m;
33 k ^= k >> r;
34 k *= m;
35 h *= m;
36 h ^= k;
37 }
38 h ^= h >> 13;
39 h *= m;
40 h ^= h >> 15;
41 return h;
42 }
is_valid__sanitizer::StackDepotDesc43 bool is_valid() { return size > 0 && stack; }
44 };
45
46 struct StackDepotNode {
47 StackDepotNode *link;
48 u32 id;
49 atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20;
50 uptr size;
51 uptr stack[1]; // [size]
52
53 static const u32 kTabSizeLog = 20;
54 // Lower kTabSizeLog bits are equal for all items in one bucket.
55 // We use these bits to store the per-stack use counter.
56 static const u32 kUseCountBits = kTabSizeLog;
57 static const u32 kMaxUseCount = 1 << kUseCountBits;
58 static const u32 kUseCountMask = (1 << kUseCountBits) - 1;
59 static const u32 kHashMask = ~kUseCountMask;
60
61 typedef StackDepotDesc args_type;
eq__sanitizer::StackDepotNode62 bool eq(u32 hash, const args_type &args) const {
63 u32 hash_bits =
64 atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask;
65 if ((hash & kHashMask) != hash_bits || args.size != size) return false;
66 uptr i = 0;
67 for (; i < size; i++) {
68 if (stack[i] != args.stack[i]) return false;
69 }
70 return true;
71 }
storage_size__sanitizer::StackDepotNode72 static uptr storage_size(const args_type &args) {
73 return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr);
74 }
store__sanitizer::StackDepotNode75 void store(const args_type &args, u32 hash) {
76 atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed);
77 size = args.size;
78 internal_memcpy(stack, args.stack, size * sizeof(uptr));
79 }
load__sanitizer::StackDepotNode80 args_type load() const {
81 args_type ret = {&stack[0], size};
82 return ret;
83 }
get_handle__sanitizer::StackDepotNode84 StackDepotHandle get_handle() { return StackDepotHandle(this); }
85
86 typedef StackDepotHandle handle_type;
87 };
88
89 COMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount);
90
id()91 u32 StackDepotHandle::id() { return node_->id; }
use_count()92 int StackDepotHandle::use_count() {
93 return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) &
94 StackDepotNode::kUseCountMask;
95 }
inc_use_count_unsafe()96 void StackDepotHandle::inc_use_count_unsafe() {
97 u32 prev =
98 atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) &
99 StackDepotNode::kUseCountMask;
100 CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount);
101 }
size()102 uptr StackDepotHandle::size() { return node_->size; }
stack()103 uptr *StackDepotHandle::stack() { return &node_->stack[0]; }
104
105 // FIXME(dvyukov): this single reserved bit is used in TSan.
106 typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog>
107 StackDepot;
108 static StackDepot theDepot;
109
StackDepotGetStats()110 StackDepotStats *StackDepotGetStats() {
111 return theDepot.GetStats();
112 }
113
StackDepotPut(const uptr * stack,uptr size)114 u32 StackDepotPut(const uptr *stack, uptr size) {
115 StackDepotDesc desc = {stack, size};
116 StackDepotHandle h = theDepot.Put(desc);
117 return h.valid() ? h.id() : 0;
118 }
119
StackDepotPut_WithHandle(const uptr * stack,uptr size)120 StackDepotHandle StackDepotPut_WithHandle(const uptr *stack, uptr size) {
121 StackDepotDesc desc = {stack, size};
122 return theDepot.Put(desc);
123 }
124
StackDepotGet(u32 id,uptr * size)125 const uptr *StackDepotGet(u32 id, uptr *size) {
126 StackDepotDesc desc = theDepot.Get(id);
127 *size = desc.size;
128 return desc.stack;
129 }
130
IdComparator(const StackDepotReverseMap::IdDescPair & a,const StackDepotReverseMap::IdDescPair & b)131 bool StackDepotReverseMap::IdDescPair::IdComparator(
132 const StackDepotReverseMap::IdDescPair &a,
133 const StackDepotReverseMap::IdDescPair &b) {
134 return a.id < b.id;
135 }
136
StackDepotReverseMap()137 StackDepotReverseMap::StackDepotReverseMap()
138 : map_(StackDepotGetStats()->n_uniq_ids + 100) {
139 for (int idx = 0; idx < StackDepot::kTabSize; idx++) {
140 atomic_uintptr_t *p = &theDepot.tab[idx];
141 uptr v = atomic_load(p, memory_order_consume);
142 StackDepotNode *s = (StackDepotNode*)(v & ~1);
143 for (; s; s = s->link) {
144 IdDescPair pair = {s->id, s};
145 map_.push_back(pair);
146 }
147 }
148 InternalSort(&map_, map_.size(), IdDescPair::IdComparator);
149 }
150
Get(u32 id,uptr * size)151 const uptr *StackDepotReverseMap::Get(u32 id, uptr *size) {
152 if (!map_.size()) return 0;
153 IdDescPair pair = {id, 0};
154 uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair,
155 IdDescPair::IdComparator);
156 if (idx > map_.size()) {
157 *size = 0;
158 return 0;
159 }
160 StackDepotNode *desc = map_[idx].desc;
161 *size = desc->size;
162 return desc->stack;
163 }
164
165 } // namespace __sanitizer
166