• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
17 namespace __msan {
18 
19 struct ChainedOriginDepotDesc {
20   u32 here_id;
21   u32 prev_id;
22 };
23 
24 struct ChainedOriginDepotNode {
25   ChainedOriginDepotNode *link;
26   u32 id;
27   u32 here_id;
28   u32 prev_id;
29 
30   typedef ChainedOriginDepotDesc args_type;
31 
eq__msan::ChainedOriginDepotNode32   bool eq(u32 hash, const args_type &args) const {
33     return here_id == args.here_id && prev_id == args.prev_id;
34   }
35 
storage_size__msan::ChainedOriginDepotNode36   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   */
hash__msan::ChainedOriginDepotNode53   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   }
is_valid__msan::ChainedOriginDepotNode77   static bool is_valid(const args_type &args) { return true; }
store__msan::ChainedOriginDepotNode78   void store(const args_type &args, u32 other_hash) {
79     here_id = args.here_id;
80     prev_id = args.prev_id;
81   }
82 
load__msan::ChainedOriginDepotNode83   args_type load() const {
84     args_type ret = {here_id, prev_id};
85     return ret;
86   }
87 
88   struct Handle {
89     ChainedOriginDepotNode *node_;
Handle__msan::ChainedOriginDepotNode::Handle90     Handle() : node_(nullptr) {}
Handle__msan::ChainedOriginDepotNode::Handle91     explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
valid__msan::ChainedOriginDepotNode::Handle92     bool valid() { return node_; }
id__msan::ChainedOriginDepotNode::Handle93     u32 id() { return node_->id; }
here_id__msan::ChainedOriginDepotNode::Handle94     int here_id() { return node_->here_id; }
prev_id__msan::ChainedOriginDepotNode::Handle95     int prev_id() { return node_->prev_id; }
96   };
97 
get_handle__msan::ChainedOriginDepotNode98   Handle get_handle() { return Handle(this); }
99 
100   typedef Handle handle_type;
101 };
102 
103 static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
104 
ChainedOriginDepotGetStats()105 StackDepotStats *ChainedOriginDepotGetStats() {
106   return chainedOriginDepot.GetStats();
107 }
108 
ChainedOriginDepotPut(u32 here_id,u32 prev_id,u32 * new_id)109 bool 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.
ChainedOriginDepotGet(u32 id,u32 * other)118 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
119   ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
120   *other = desc.prev_id;
121   return desc.here_id;
122 }
123 
ChainedOriginDepotLockAll()124 void ChainedOriginDepotLockAll() {
125   chainedOriginDepot.LockAll();
126 }
127 
ChainedOriginDepotUnlockAll()128 void ChainedOriginDepotUnlockAll() {
129   chainedOriginDepot.UnlockAll();
130 }
131 
132 } // namespace __msan
133