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 
16 namespace __sanitizer {
17 
18 namespace {
19 struct ChainedOriginDepotDesc {
20   u32 here_id;
21   u32 prev_id;
22 };
23 
24 struct 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 
61 static StackDepotBase<ChainedOriginDepotNode, 4, 20> depot;
62 
63 bool 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 */
80 ChainedOriginDepotNode::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 
106 bool ChainedOriginDepotNode::is_valid(const args_type &args) { return true; }
107 
108 void 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 
114 ChainedOriginDepotNode::args_type ChainedOriginDepotNode::load(u32 id) const {
115   args_type ret = {here_id, prev_id};
116   return ret;
117 }
118 
119 ChainedOriginDepotNode::Handle ChainedOriginDepotNode::get_handle(u32 id) {
120   return Handle(&depot.nodes[id], id);
121 }
122 
123 ChainedOriginDepot::ChainedOriginDepot() {}
124 
125 StackDepotStats ChainedOriginDepot::GetStats() const {
126   return depot.GetStats();
127 }
128 
129 bool ChainedOriginDepot::Put(u32 here_id, u32 prev_id, u32 *new_id) {
130   ChainedOriginDepotDesc desc = {here_id, prev_id};
131   bool inserted;
132   *new_id = depot.Put(desc, &inserted);
133   return inserted;
134 }
135 
136 u32 ChainedOriginDepot::Get(u32 id, u32 *other) {
137   ChainedOriginDepotDesc desc = depot.Get(id);
138   *other = desc.prev_id;
139   return desc.here_id;
140 }
141 
142 void ChainedOriginDepot::LockAll() { depot.LockAll(); }
143 
144 void ChainedOriginDepot::UnlockAll() { depot.UnlockAll(); }
145 
146 void ChainedOriginDepot::TestOnlyUnmap() { depot.TestOnlyUnmap(); }
147 
148 }  // namespace __sanitizer
149