Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 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; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 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; |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 31 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 32 | bool eq(u32 hash, const args_type &args) const { |
| 33 | return here_id == args.here_id && prev_id == args.prev_id; |
| 34 | } |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 35 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 36 | static uptr storage_size(const args_type &args) { |
| 37 | return sizeof(ChainedOriginDepotNode); |
| 38 | } |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 39 | |
Stephen Hines | 6d18623 | 2014-11-26 17:56:19 -0800 | [diff] [blame] | 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; } |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 78 | void store(const args_type &args, u32 other_hash) { |
| 79 | here_id = args.here_id; |
| 80 | prev_id = args.prev_id; |
| 81 | } |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 82 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 83 | args_type load() const { |
| 84 | args_type ret = {here_id, prev_id}; |
| 85 | return ret; |
| 86 | } |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 87 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 88 | struct Handle { |
| 89 | ChainedOriginDepotNode *node_; |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 90 | Handle() : node_(nullptr) {} |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 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 | }; |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 97 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 98 | Handle get_handle() { return Handle(this); } |
| 99 | |
| 100 | typedef Handle handle_type; |
| 101 | }; |
| 102 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 103 | static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 104 | |
| 105 | StackDepotStats *ChainedOriginDepotGetStats() { |
| 106 | return chainedOriginDepot.GetStats(); |
| 107 | } |
| 108 | |
| 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. |
| 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 | |
Stephen Hines | 6d18623 | 2014-11-26 17:56:19 -0800 | [diff] [blame] | 124 | void ChainedOriginDepotLockAll() { |
| 125 | chainedOriginDepot.LockAll(); |
| 126 | } |
| 127 | |
| 128 | void ChainedOriginDepotUnlockAll() { |
| 129 | chainedOriginDepot.UnlockAll(); |
| 130 | } |
| 131 | |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 132 | } // namespace __msan |