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