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;
32 bool eq(u32 hash, const args_type &args) const {
33 return here_id == args.here_id && prev_id == args.prev_id;
36 static uptr storage_size(const args_type &args) {
37 return sizeof(ChainedOriginDepotNode);
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).
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).
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.
53 static u32 hash(const args_type &args) {
54 const u32 m = 0x5bd1e995;
55 const u32 seed = 0x9747b28c;
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;
83 args_type load() const {
84 args_type ret = {here_id, prev_id};
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; }
98 Handle get_handle() { return Handle(this); }
100 typedef Handle handle_type;
103 static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
105 StackDepotStats *ChainedOriginDepotGetStats() {
106 return chainedOriginDepot.GetStats();
109 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
110 ChainedOriginDepotDesc desc = {here_id, prev_id};
112 ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
113 *new_id = h.valid() ? h.id() : 0;
117 // Retrieves a stored stack trace by the id.
118 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
119 ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
120 *other = desc.prev_id;
124 void ChainedOriginDepotLockAll() {
125 chainedOriginDepot.LockAll();
128 void ChainedOriginDepotUnlockAll() {
129 chainedOriginDepot.UnlockAll();
132 } // namespace __msan