151 lines · cpp
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-exception6//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} // namespace60 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 biased69 distribution (I've seen 7-element buckets with the table only 14% full).70 71 here_id is built of72 * (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 can78 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, 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, prev_id};131 bool inserted;132 *new_id = depot.Put(desc, &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 __sanitizer151