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