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