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