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;
eq__msan::ChainedOriginDepotNode31 bool eq(u32 hash, const args_type &args) const {
32 return here_id == args.here_id && prev_id == args.prev_id;
33 }
storage_size__msan::ChainedOriginDepotNode34 static uptr storage_size(const args_type &args) {
35 return sizeof(ChainedOriginDepotNode);
36 }
37 /* This is murmur2 hash for the 64->32 bit case.
38 It does not behave all that well because the keys have a very biased
39 distribution (I've seen 7-element buckets with the table only 14% full).
40
41 here_id is built of
42 * (1 bits) Reserved, zero.
43 * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
44 * (23 bits) Sequential number (each part has each own sequence).
45
46 prev_id has either the same distribution as here_id (but with 3:8:21)
47 split, or one of two reserved values (-1) or (-2). Either case can
48 dominate depending on the workload.
49 */
hash__msan::ChainedOriginDepotNode50 static u32 hash(const args_type &args) {
51 const u32 m = 0x5bd1e995;
52 const u32 seed = 0x9747b28c;
53 const u32 r = 24;
54 u32 h = seed;
55 u32 k = args.here_id;
56 k *= m;
57 k ^= k >> r;
58 k *= m;
59 h *= m;
60 h ^= k;
61
62 k = args.prev_id;
63 k *= m;
64 k ^= k >> r;
65 k *= m;
66 h *= m;
67 h ^= k;
68
69 h ^= h >> 13;
70 h *= m;
71 h ^= h >> 15;
72 return h;
73 }
is_valid__msan::ChainedOriginDepotNode74 static bool is_valid(const args_type &args) { return true; }
store__msan::ChainedOriginDepotNode75 void store(const args_type &args, u32 other_hash) {
76 here_id = args.here_id;
77 prev_id = args.prev_id;
78 }
load__msan::ChainedOriginDepotNode79 args_type load() const {
80 args_type ret = {here_id, prev_id};
81 return ret;
82 }
83 struct Handle {
84 ChainedOriginDepotNode *node_;
Handle__msan::ChainedOriginDepotNode::Handle85 Handle() : node_(0) {}
Handle__msan::ChainedOriginDepotNode::Handle86 explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
valid__msan::ChainedOriginDepotNode::Handle87 bool valid() { return node_; }
id__msan::ChainedOriginDepotNode::Handle88 u32 id() { return node_->id; }
here_id__msan::ChainedOriginDepotNode::Handle89 int here_id() { return node_->here_id; }
prev_id__msan::ChainedOriginDepotNode::Handle90 int prev_id() { return node_->prev_id; }
91 };
get_handle__msan::ChainedOriginDepotNode92 Handle get_handle() { return Handle(this); }
93
94 typedef Handle handle_type;
95 };
96
97 static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
98
ChainedOriginDepotGetStats()99 StackDepotStats *ChainedOriginDepotGetStats() {
100 return chainedOriginDepot.GetStats();
101 }
102
ChainedOriginDepotPut(u32 here_id,u32 prev_id,u32 * new_id)103 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
104 ChainedOriginDepotDesc desc = {here_id, prev_id};
105 bool inserted;
106 ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
107 *new_id = h.valid() ? h.id() : 0;
108 return inserted;
109 }
110
111 // Retrieves a stored stack trace by the id.
ChainedOriginDepotGet(u32 id,u32 * other)112 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
113 ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
114 *other = desc.prev_id;
115 return desc.here_id;
116 }
117
ChainedOriginDepotLockAll()118 void ChainedOriginDepotLockAll() {
119 chainedOriginDepot.LockAll();
120 }
121
ChainedOriginDepotUnlockAll()122 void ChainedOriginDepotUnlockAll() {
123 chainedOriginDepot.UnlockAll();
124 }
125
126 } // namespace __msan
127