1 //===-- msan_chained_origin_depot.cc -----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // A storage for chained origins.
11 //===----------------------------------------------------------------------===//
13 #include "msan_chained_origin_depot.h"
15 #include "sanitizer_common/sanitizer_stackdepotbase.h"
19 struct ChainedOriginDepotDesc {
24 struct ChainedOriginDepotNode {
25 ChainedOriginDepotNode *link;
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;
34 static uptr storage_size(const args_type &args) {
35 return sizeof(ChainedOriginDepotNode);
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).
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).
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.
50 static u32 hash(const args_type &args) {
51 const u32 m = 0x5bd1e995;
52 const u32 seed = 0x9747b28c;
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;
79 args_type load() const {
80 args_type ret = {here_id, prev_id};
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; }
92 Handle get_handle() { return Handle(this); }
94 typedef Handle handle_type;
97 static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
99 StackDepotStats *ChainedOriginDepotGetStats() {
100 return chainedOriginDepot.GetStats();
103 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
104 ChainedOriginDepotDesc desc = {here_id, prev_id};
106 ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
107 *new_id = h.valid() ? h.id() : 0;
111 // Retrieves a stored stack trace by the id.
112 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
113 ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
114 *other = desc.prev_id;
118 void ChainedOriginDepotLockAll() {
119 chainedOriginDepot.LockAll();
122 void ChainedOriginDepotUnlockAll() {
123 chainedOriginDepot.UnlockAll();
126 } // namespace __msan