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