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; 22 u32 hash() const { 23 const u32 m = 0x5bd1e995; 24 const u32 seed = 0x9747b28c; 25 const u32 r = 24; 26 u32 h = seed; 27 u32 k = here_id; 28 k *= m; 29 k ^= k >> r; 30 k *= m; 31 h *= m; 32 h ^= k; 33 34 k = prev_id; 35 k *= m; 36 k ^= k >> r; 37 k *= m; 38 h *= m; 39 h ^= k; 40 41 h ^= h >> 13; 42 h *= m; 43 h ^= h >> 15; 44 return h; 45 } 46 bool is_valid() { return true; } 47 }; 48 49 struct ChainedOriginDepotNode { 50 ChainedOriginDepotNode *link; 51 u32 id; 52 u32 here_id; 53 u32 prev_id; 54 55 typedef ChainedOriginDepotDesc args_type; 56 bool eq(u32 hash, const args_type &args) const { 57 return here_id == args.here_id && prev_id == args.prev_id; 58 } 59 static uptr storage_size(const args_type &args) { 60 return sizeof(ChainedOriginDepotNode); 61 } 62 void store(const args_type &args, u32 other_hash) { 63 here_id = args.here_id; 64 prev_id = args.prev_id; 65 } 66 args_type load() const { 67 args_type ret = {here_id, prev_id}; 68 return ret; 69 } 70 struct Handle { 71 ChainedOriginDepotNode *node_; 72 Handle() : node_(0) {} 73 explicit Handle(ChainedOriginDepotNode *node) : node_(node) {} 74 bool valid() { return node_; } 75 u32 id() { return node_->id; } 76 int here_id() { return node_->here_id; } 77 int prev_id() { return node_->prev_id; } 78 }; 79 Handle get_handle() { return Handle(this); } 80 81 typedef Handle handle_type; 82 }; 83 84 // kTabSizeLog = 22 => 32Mb static storage for bucket pointers. 85 static StackDepotBase<ChainedOriginDepotNode, 3, 20> chainedOriginDepot; 86 87 StackDepotStats *ChainedOriginDepotGetStats() { 88 return chainedOriginDepot.GetStats(); 89 } 90 91 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) { 92 ChainedOriginDepotDesc desc = {here_id, prev_id}; 93 bool inserted; 94 ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted); 95 *new_id = h.valid() ? h.id() : 0; 96 return inserted; 97 } 98 99 // Retrieves a stored stack trace by the id. 100 u32 ChainedOriginDepotGet(u32 id, u32 *other) { 101 ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id); 102 *other = desc.prev_id; 103 return desc.here_id; 104 } 105 106 } // namespace __msan 107