1 //===-- msan_origin.h ----------------------------------*- C++ -*-===// 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 // Origin id utils. 11 //===----------------------------------------------------------------------===// 12 #ifndef MSAN_ORIGIN_H 13 #define MSAN_ORIGIN_H 14 15 #include "sanitizer_common/sanitizer_stackdepot.h" 16 #include "msan_chained_origin_depot.h" 17 18 namespace __msan { 19 20 // Origin handling. 21 // 22 // Origin is a 32-bit identifier that is attached to any uninitialized value in 23 // the program and describes, more or less exactly, how this memory came to be 24 // uninitialized. 25 // 26 // There are 3 kinds of origin ids: 27 // 1xxx xxxx xxxx xxxx heap origin id 28 // 0000 xxxx xxxx xxxx stack origin id 29 // 0zzz xxxx xxxx xxxx chained origin id 30 // 31 // Heap origin id describes a heap memory allocation and contains (in the xxx 32 // part) a value of StackDepot. 33 // 34 // Stack origin id describes a stack memory allocation and contains (in the xxx 35 // part) an index into StackOriginDescr and StackOriginPC. We don't store a 36 // stack trace for such origins for performance reasons. 37 // 38 // Chained origin id describes an event of storing an uninitialized value to 39 // memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of 40 // (stack_id, prev_id) -> id, where 41 // * stack_id describes the event. 42 // StackDepot keeps a mapping between those and corresponding stack traces. 43 // * prev_id is another origin id that describes the earlier part of the 44 // uninitialized value history. 45 // Following a chain of prev_id provides the full recorded history of an 46 // uninitialized value. 47 // 48 // This, effectively, defines a tree (or 2 trees, see below) where nodes are 49 // points in value history marked with origin ids, and edges are events that are 50 // marked with stack_id. 51 // 52 // The "zzz" bits of chained origin id are used to store the length (or depth) 53 // of the origin chain. 54 55 class Origin { 56 public: 57 static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; } 58 59 u32 raw_id() const { return raw_id_; } 60 bool isHeapOrigin() const { 61 // 1xxx xxxx xxxx xxxx 62 return raw_id_ >> kHeapShift == 0; 63 } 64 bool isStackOrigin() const { 65 // 1000 xxxx xxxx xxxx 66 return (raw_id_ >> kDepthShift) == (1 << kDepthBits); 67 } 68 bool isChainedOrigin() const { 69 // 1zzz xxxx xxxx xxxx, zzz != 000 70 return (raw_id_ >> kDepthShift) > (1 << kDepthBits); 71 } 72 u32 getChainedId() const { 73 CHECK(isChainedOrigin()); 74 return raw_id_ & kChainedIdMask; 75 } 76 u32 getStackId() const { 77 CHECK(isStackOrigin()); 78 return raw_id_ & kChainedIdMask; 79 } 80 u32 getHeapId() const { 81 CHECK(isHeapOrigin()); 82 return raw_id_ & kHeapIdMask; 83 } 84 85 // Returns the next origin in the chain and the current stack trace. 86 Origin getNextChainedOrigin(StackTrace *stack) const { 87 CHECK(isChainedOrigin()); 88 u32 prev_id; 89 u32 stack_id = ChainedOriginDepotGet(getChainedId(), &prev_id); 90 if (stack) *stack = StackDepotGet(stack_id); 91 return Origin(prev_id); 92 } 93 94 StackTrace getStackTraceForHeapOrigin() const { 95 return StackDepotGet(getHeapId()); 96 } 97 98 static Origin CreateStackOrigin(u32 id) { 99 CHECK((id & kStackIdMask) == id); 100 return Origin((1 << kHeapShift) | id); 101 } 102 103 static Origin CreateHeapOrigin(StackTrace *stack) { 104 u32 stack_id = StackDepotPut(*stack); 105 CHECK(stack_id); 106 CHECK((stack_id & kHeapIdMask) == stack_id); 107 return Origin(stack_id); 108 } 109 110 static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) { 111 int depth = prev.isChainedOrigin() ? prev.depth() : 0; 112 // depth is the length of the chain minus 1. 113 // origin_history_size of 0 means unlimited depth. 114 if (flags()->origin_history_size > 0) { 115 if (depth + 1 >= flags()->origin_history_size) { 116 return prev; 117 } else { 118 ++depth; 119 CHECK(depth < (1 << kDepthBits)); 120 } 121 } 122 123 StackDepotHandle h = StackDepotPut_WithHandle(*stack); 124 if (!h.valid()) return prev; 125 126 if (flags()->origin_history_per_stack_limit > 0) { 127 int use_count = h.use_count(); 128 if (use_count > flags()->origin_history_per_stack_limit) return prev; 129 } 130 131 u32 chained_id; 132 bool inserted = ChainedOriginDepotPut(h.id(), prev.raw_id(), &chained_id); 133 CHECK((chained_id & kChainedIdMask) == chained_id); 134 135 if (inserted && flags()->origin_history_per_stack_limit > 0) 136 h.inc_use_count_unsafe(); 137 138 return Origin((1 << kHeapShift) | (depth << kDepthShift) | chained_id); 139 } 140 141 static Origin FromRawId(u32 id) { 142 return Origin(id); 143 } 144 145 private: 146 static const int kDepthBits = 3; 147 static const int kDepthShift = 32 - kDepthBits - 1; 148 149 static const int kHeapShift = 31; 150 static const u32 kChainedIdMask = ((u32)-1) >> (32 - kDepthShift); 151 static const u32 kStackIdMask = ((u32)-1) >> (32 - kDepthShift); 152 static const u32 kHeapIdMask = ((u32)-1) >> (32 - kHeapShift); 153 154 u32 raw_id_; 155 156 explicit Origin(u32 raw_id) : raw_id_(raw_id) {} 157 158 int depth() const { 159 CHECK(isChainedOrigin()); 160 return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1); 161 } 162 163 public: 164 static const int kMaxDepth = (1 << kDepthBits) - 1; 165 }; 166 167 } // namespace __msan 168 169 #endif // MSAN_ORIGIN_H 170
