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