1 //===-- msan_chained_origin_depot.cpp ----------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // A storage for chained origins. 10 //===----------------------------------------------------------------------===// 11 12 #include "msan_chained_origin_depot.h" 13 14 #include "sanitizer_common/sanitizer_stackdepotbase.h" 15 16 namespace __msan { 17 18 struct ChainedOriginDepotDesc { 19 u32 here_id; 20 u32 prev_id; 21 }; 22 23 struct ChainedOriginDepotNode { 24 ChainedOriginDepotNode *link; 25 u32 id; 26 u32 here_id; 27 u32 prev_id; 28 29 typedef ChainedOriginDepotDesc args_type; 30 31 bool eq(u32 hash, const args_type &args) const { 32 return here_id == args.here_id && prev_id == args.prev_id; 33 } 34 35 static uptr storage_size(const args_type &args) { 36 return sizeof(ChainedOriginDepotNode); 37 } 38 39 /* This is murmur2 hash for the 64->32 bit case. 40 It does not behave all that well because the keys have a very biased 41 distribution (I've seen 7-element buckets with the table only 14% full). 42 43 here_id is built of 44 * (1 bits) Reserved, zero. 45 * (8 bits) Part id = bits 13..20 of the hash value of here_id's key. 46 * (23 bits) Sequential number (each part has each own sequence). 47 48 prev_id has either the same distribution as here_id (but with 3:8:21) 49 split, or one of two reserved values (-1) or (-2). Either case can 50 dominate depending on the workload. 51 */ 52 static u32 hash(const args_type &args) { 53 const u32 m = 0x5bd1e995; 54 const u32 seed = 0x9747b28c; 55 const u32 r = 24; 56 u32 h = seed; 57 u32 k = args.here_id; 58 k *= m; 59 k ^= k >> r; 60 k *= m; 61 h *= m; 62 h ^= k; 63 64 k = args.prev_id; 65 k *= m; 66 k ^= k >> r; 67 k *= m; 68 h *= m; 69 h ^= k; 70 71 h ^= h >> 13; 72 h *= m; 73 h ^= h >> 15; 74 return h; 75 } 76 static bool is_valid(const args_type &args) { return true; } 77 void store(const args_type &args, u32 other_hash) { 78 here_id = args.here_id; 79 prev_id = args.prev_id; 80 } 81 82 args_type load() const { 83 args_type ret = {here_id, prev_id}; 84 return ret; 85 } 86 87 struct Handle { 88 ChainedOriginDepotNode *node_; 89 Handle() : node_(nullptr) {} 90 explicit Handle(ChainedOriginDepotNode *node) : node_(node) {} 91 bool valid() { return node_; } 92 u32 id() { return node_->id; } 93 int here_id() { return node_->here_id; } 94 int prev_id() { return node_->prev_id; } 95 }; 96 97 Handle get_handle() { return Handle(this); } 98 99 typedef Handle handle_type; 100 }; 101 102 static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot; 103 104 StackDepotStats *ChainedOriginDepotGetStats() { 105 return chainedOriginDepot.GetStats(); 106 } 107 108 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) { 109 ChainedOriginDepotDesc desc = {here_id, prev_id}; 110 bool inserted; 111 ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted); 112 *new_id = h.valid() ? h.id() : 0; 113 return inserted; 114 } 115 116 // Retrieves a stored stack trace by the id. 117 u32 ChainedOriginDepotGet(u32 id, u32 *other) { 118 ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id); 119 *other = desc.prev_id; 120 return desc.here_id; 121 } 122 123 void ChainedOriginDepotLockAll() { 124 chainedOriginDepot.LockAll(); 125 } 126 127 void ChainedOriginDepotUnlockAll() { 128 chainedOriginDepot.UnlockAll(); 129 } 130 131 } // namespace __msan 132