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::LockBeforeFork() { depot.LockBeforeFork(); } 143 144 void ChainedOriginDepot::UnlockAfterFork(bool fork_child) { 145 depot.UnlockAfterFork(fork_child); 146 } 147 148 void ChainedOriginDepot::TestOnlyUnmap() { depot.TestOnlyUnmap(); } 149 150 } // namespace __sanitizer 151