1 //===-- msan_chained_origin_depot.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 // A storage for chained origins.
11 //===----------------------------------------------------------------------===//
12
13 #include "msan_chained_origin_depot.h"
14
15 #include "sanitizer_common/sanitizer_stackdepotbase.h"
16
17 namespace __msan {
18
19 struct ChainedOriginDepotDesc {
20 u32 here_id;
21 u32 prev_id;
22 };
23
24 struct ChainedOriginDepotNode {
25 ChainedOriginDepotNode *link;
26 u32 id;
27 u32 here_id;
28 u32 prev_id;
29
30 typedef ChainedOriginDepotDesc args_type;
31
eq__msan::ChainedOriginDepotNode32 bool eq(u32 hash, const args_type &args) const {
33 return here_id == args.here_id && prev_id == args.prev_id;
34 }
35
storage_size__msan::ChainedOriginDepotNode36 static uptr storage_size(const args_type &args) {
37 return sizeof(ChainedOriginDepotNode);
38 }
39
40 /* This is murmur2 hash for the 64->32 bit case.
41 It does not behave all that well because the keys have a very biased
42 distribution (I've seen 7-element buckets with the table only 14% full).
43
44 here_id is built of
45 * (1 bits) Reserved, zero.
46 * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
47 * (23 bits) Sequential number (each part has each own sequence).
48
49 prev_id has either the same distribution as here_id (but with 3:8:21)
50 split, or one of two reserved values (-1) or (-2). Either case can
51 dominate depending on the workload.
52 */
hash__msan::ChainedOriginDepotNode53 static u32 hash(const args_type &args) {
54 const u32 m = 0x5bd1e995;
55 const u32 seed = 0x9747b28c;
56 const u32 r = 24;
57 u32 h = seed;
58 u32 k = args.here_id;
59 k *= m;
60 k ^= k >> r;
61 k *= m;
62 h *= m;
63 h ^= k;
64
65 k = args.prev_id;
66 k *= m;
67 k ^= k >> r;
68 k *= m;
69 h *= m;
70 h ^= k;
71
72 h ^= h >> 13;
73 h *= m;
74 h ^= h >> 15;
75 return h;
76 }
is_valid__msan::ChainedOriginDepotNode77 static bool is_valid(const args_type &args) { return true; }
store__msan::ChainedOriginDepotNode78 void store(const args_type &args, u32 other_hash) {
79 here_id = args.here_id;
80 prev_id = args.prev_id;
81 }
82
load__msan::ChainedOriginDepotNode83 args_type load() const {
84 args_type ret = {here_id, prev_id};
85 return ret;
86 }
87
88 struct Handle {
89 ChainedOriginDepotNode *node_;
Handle__msan::ChainedOriginDepotNode::Handle90 Handle() : node_(nullptr) {}
Handle__msan::ChainedOriginDepotNode::Handle91 explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
valid__msan::ChainedOriginDepotNode::Handle92 bool valid() { return node_; }
id__msan::ChainedOriginDepotNode::Handle93 u32 id() { return node_->id; }
here_id__msan::ChainedOriginDepotNode::Handle94 int here_id() { return node_->here_id; }
prev_id__msan::ChainedOriginDepotNode::Handle95 int prev_id() { return node_->prev_id; }
96 };
97
get_handle__msan::ChainedOriginDepotNode98 Handle get_handle() { return Handle(this); }
99
100 typedef Handle handle_type;
101 };
102
103 static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
104
ChainedOriginDepotGetStats()105 StackDepotStats *ChainedOriginDepotGetStats() {
106 return chainedOriginDepot.GetStats();
107 }
108
ChainedOriginDepotPut(u32 here_id,u32 prev_id,u32 * new_id)109 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
110 ChainedOriginDepotDesc desc = {here_id, prev_id};
111 bool inserted;
112 ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
113 *new_id = h.valid() ? h.id() : 0;
114 return inserted;
115 }
116
117 // Retrieves a stored stack trace by the id.
ChainedOriginDepotGet(u32 id,u32 * other)118 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
119 ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
120 *other = desc.prev_id;
121 return desc.here_id;
122 }
123
ChainedOriginDepotLockAll()124 void ChainedOriginDepotLockAll() {
125 chainedOriginDepot.LockAll();
126 }
127
ChainedOriginDepotUnlockAll()128 void ChainedOriginDepotUnlockAll() {
129 chainedOriginDepot.UnlockAll();
130 }
131
132 } // namespace __msan
133