]>
Commit | Line | Data |
---|---|---|
d0fee87e ML |
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 | namespace __sanitizer { | |
15 | ||
16 | bool ChainedOriginDepot::ChainedOriginDepotNode::eq( | |
17 | u32 hash, const args_type &args) const { | |
18 | return here_id == args.here_id && prev_id == args.prev_id; | |
19 | } | |
20 | ||
21 | uptr ChainedOriginDepot::ChainedOriginDepotNode::storage_size( | |
22 | const args_type &args) { | |
23 | return sizeof(ChainedOriginDepotNode); | |
24 | } | |
25 | ||
26 | /* This is murmur2 hash for the 64->32 bit case. | |
27 | It does not behave all that well because the keys have a very biased | |
28 | distribution (I've seen 7-element buckets with the table only 14% full). | |
29 | ||
30 | here_id is built of | |
31 | * (1 bits) Reserved, zero. | |
32 | * (8 bits) Part id = bits 13..20 of the hash value of here_id's key. | |
33 | * (23 bits) Sequential number (each part has each own sequence). | |
34 | ||
35 | prev_id has either the same distribution as here_id (but with 3:8:21) | |
36 | split, or one of two reserved values (-1) or (-2). Either case can | |
37 | dominate depending on the workload. | |
38 | */ | |
39 | u32 ChainedOriginDepot::ChainedOriginDepotNode::hash(const args_type &args) { | |
40 | const u32 m = 0x5bd1e995; | |
41 | const u32 seed = 0x9747b28c; | |
42 | const u32 r = 24; | |
43 | u32 h = seed; | |
44 | u32 k = args.here_id; | |
45 | k *= m; | |
46 | k ^= k >> r; | |
47 | k *= m; | |
48 | h *= m; | |
49 | h ^= k; | |
50 | ||
51 | k = args.prev_id; | |
52 | k *= m; | |
53 | k ^= k >> r; | |
54 | k *= m; | |
55 | h *= m; | |
56 | h ^= k; | |
57 | ||
58 | h ^= h >> 13; | |
59 | h *= m; | |
60 | h ^= h >> 15; | |
61 | return h; | |
62 | } | |
63 | ||
64 | bool ChainedOriginDepot::ChainedOriginDepotNode::is_valid( | |
65 | const args_type &args) { | |
66 | return true; | |
67 | } | |
68 | ||
69 | void ChainedOriginDepot::ChainedOriginDepotNode::store(const args_type &args, | |
70 | u32 other_hash) { | |
71 | here_id = args.here_id; | |
72 | prev_id = args.prev_id; | |
73 | } | |
74 | ||
75 | ChainedOriginDepot::ChainedOriginDepotNode::args_type | |
76 | ChainedOriginDepot::ChainedOriginDepotNode::load() const { | |
77 | args_type ret = {here_id, prev_id}; | |
78 | return ret; | |
79 | } | |
80 | ||
81 | ChainedOriginDepot::ChainedOriginDepotNode::Handle | |
82 | ChainedOriginDepot::ChainedOriginDepotNode::get_handle() { | |
83 | return Handle(this); | |
84 | } | |
85 | ||
86 | ChainedOriginDepot::ChainedOriginDepot() {} | |
87 | ||
88 | StackDepotStats *ChainedOriginDepot::GetStats() { return depot.GetStats(); } | |
89 | ||
90 | bool ChainedOriginDepot::Put(u32 here_id, u32 prev_id, u32 *new_id) { | |
91 | ChainedOriginDepotDesc desc = {here_id, prev_id}; | |
92 | bool inserted; | |
93 | ChainedOriginDepotNode::Handle h = depot.Put(desc, &inserted); | |
94 | *new_id = h.valid() ? h.id() : 0; | |
95 | return inserted; | |
96 | } | |
97 | ||
98 | u32 ChainedOriginDepot::Get(u32 id, u32 *other) { | |
99 | ChainedOriginDepotDesc desc = depot.Get(id); | |
100 | *other = desc.prev_id; | |
101 | return desc.here_id; | |
102 | } | |
103 | ||
104 | void ChainedOriginDepot::LockAll() { depot.LockAll(); } | |
105 | ||
106 | void ChainedOriginDepot::UnlockAll() { depot.UnlockAll(); } | |
107 | ||
108 | } // namespace __sanitizer |