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