1 //===-- sanitizer_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 "sanitizer_chained_origin_depot.h"
13
14 #include "sanitizer_persistent_allocator.h"
15 #include "sanitizer_stackdepotbase.h"
16
17 namespace __sanitizer {
18
19 namespace {
20 struct ChainedOriginDepotDesc {
21 u32 here_id;
22 u32 prev_id;
23 };
24
25 struct ChainedOriginDepotNode {
26 using hash_type = u32;
27 u32 link;
28 u32 here_id;
29 u32 prev_id;
30
31 typedef ChainedOriginDepotDesc args_type;
32
33 bool eq(hash_type hash, const args_type &args) const;
34
allocated__sanitizer::__anonee2bfc740111::ChainedOriginDepotNode35 static uptr allocated() { return 0; }
36
37 static hash_type hash(const args_type &args);
38
39 static bool is_valid(const args_type &args);
40
41 void store(u32 id, const args_type &args, hash_type other_hash);
42
43 args_type load(u32 id) const;
44
45 struct Handle {
46 const ChainedOriginDepotNode *node_ = nullptr;
47 u32 id_ = 0;
Handle__sanitizer::__anonee2bfc740111::ChainedOriginDepotNode::Handle48 Handle(const ChainedOriginDepotNode *node, u32 id) : node_(node), id_(id) {}
valid__sanitizer::__anonee2bfc740111::ChainedOriginDepotNode::Handle49 bool valid() const { return node_; }
id__sanitizer::__anonee2bfc740111::ChainedOriginDepotNode::Handle50 u32 id() const { return id_; }
here_id__sanitizer::__anonee2bfc740111::ChainedOriginDepotNode::Handle51 int here_id() const { return node_->here_id; }
prev_id__sanitizer::__anonee2bfc740111::ChainedOriginDepotNode::Handle52 int prev_id() const { return node_->prev_id; }
53 };
54
55 static Handle get_handle(u32 id);
56
57 typedef Handle handle_type;
58 };
59
60 } // namespace
61
62 static StackDepotBase<ChainedOriginDepotNode, 4, 20> depot;
63
eq(hash_type hash,const args_type & args) const64 bool ChainedOriginDepotNode::eq(hash_type hash, const args_type &args) const {
65 return here_id == args.here_id && prev_id == args.prev_id;
66 }
67
68 /* This is murmur2 hash for the 64->32 bit case.
69 It does not behave all that well because the keys have a very biased
70 distribution (I've seen 7-element buckets with the table only 14% full).
71
72 here_id is built of
73 * (1 bits) Reserved, zero.
74 * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
75 * (23 bits) Sequential number (each part has each own sequence).
76
77 prev_id has either the same distribution as here_id (but with 3:8:21)
78 split, or one of two reserved values (-1) or (-2). Either case can
79 dominate depending on the workload.
80 */
hash(const args_type & args)81 ChainedOriginDepotNode::hash_type ChainedOriginDepotNode::hash(
82 const args_type &args) {
83 const u32 m = 0x5bd1e995;
84 const u32 seed = 0x9747b28c;
85 const u32 r = 24;
86 u32 h = seed;
87 u32 k = args.here_id;
88 k *= m;
89 k ^= k >> r;
90 k *= m;
91 h *= m;
92 h ^= k;
93
94 k = args.prev_id;
95 k *= m;
96 k ^= k >> r;
97 k *= m;
98 h *= m;
99 h ^= k;
100
101 h ^= h >> 13;
102 h *= m;
103 h ^= h >> 15;
104 return h;
105 }
106
is_valid(const args_type & args)107 bool ChainedOriginDepotNode::is_valid(const args_type &args) { return true; }
108
store(u32 id,const args_type & args,hash_type other_hash)109 void ChainedOriginDepotNode::store(u32 id, const args_type &args,
110 hash_type other_hash) {
111 here_id = args.here_id;
112 prev_id = args.prev_id;
113 }
114
load(u32 id) const115 ChainedOriginDepotNode::args_type ChainedOriginDepotNode::load(u32 id) const {
116 args_type ret = {here_id, prev_id};
117 return ret;
118 }
119
get_handle(u32 id)120 ChainedOriginDepotNode::Handle ChainedOriginDepotNode::get_handle(u32 id) {
121 return Handle(&depot.nodes[id], id);
122 }
123
ChainedOriginDepot()124 ChainedOriginDepot::ChainedOriginDepot() {}
125
GetStats() const126 StackDepotStats ChainedOriginDepot::GetStats() const {
127 return depot.GetStats();
128 }
129
Put(u32 here_id,u32 prev_id,u32 * new_id)130 bool ChainedOriginDepot::Put(u32 here_id, u32 prev_id, u32 *new_id) {
131 ChainedOriginDepotDesc desc = {here_id, prev_id};
132 bool inserted;
133 *new_id = depot.Put(desc, &inserted);
134 return inserted;
135 }
136
Get(u32 id,u32 * other)137 u32 ChainedOriginDepot::Get(u32 id, u32 *other) {
138 ChainedOriginDepotDesc desc = depot.Get(id);
139 *other = desc.prev_id;
140 return desc.here_id;
141 }
142
LockAll()143 void ChainedOriginDepot::LockAll() { depot.LockAll(); }
144
UnlockAll()145 void ChainedOriginDepot::UnlockAll() { depot.UnlockAll(); }
146
147 } // namespace __sanitizer
148