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; |
| 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 | } |
Stephen Hines | 6d18623 | 2014-11-26 17:56:19 -0800 | [diff] [blame] | 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; } |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 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 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 97 | static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 98 | |
| 99 | StackDepotStats *ChainedOriginDepotGetStats() { |
| 100 | return chainedOriginDepot.GetStats(); |
| 101 | } |
| 102 | |
| 103 | bool 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. |
| 112 | u32 ChainedOriginDepotGet(u32 id, u32 *other) { |
| 113 | ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id); |
| 114 | *other = desc.prev_id; |
| 115 | return desc.here_id; |
| 116 | } |
| 117 | |
Stephen Hines | 6d18623 | 2014-11-26 17:56:19 -0800 | [diff] [blame] | 118 | void ChainedOriginDepotLockAll() { |
| 119 | chainedOriginDepot.LockAll(); |
| 120 | } |
| 121 | |
| 122 | void ChainedOriginDepotUnlockAll() { |
| 123 | chainedOriginDepot.UnlockAll(); |
| 124 | } |
| 125 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 126 | } // namespace __msan |