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
 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}  // namespace
 60
 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 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*/
 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 __sanitizer