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