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