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