169 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Origin id utils.10//===----------------------------------------------------------------------===//11#ifndef MSAN_ORIGIN_H12#define MSAN_ORIGIN_H13 14#include "sanitizer_common/sanitizer_stackdepot.h"15#include "msan_chained_origin_depot.h"16 17namespace __msan {18 19// Origin handling.20//21// Origin is a 32-bit identifier that is attached to any uninitialized value in22// the program and describes, more or less exactly, how this memory came to be23// uninitialized.24//25// There are 3 kinds of origin ids:26// 1xxx xxxx xxxx xxxx heap origin id27// 0000 xxxx xxxx xxxx stack origin id28// 0zzz xxxx xxxx xxxx chained origin id29//30// Heap origin id describes a heap memory allocation and contains (in the xxx31// part) a value of StackDepot.32//33// Stack origin id describes a stack memory allocation and contains (in the xxx34// part) an index into StackOriginDescr and StackOriginPC. We don't store a35// stack trace for such origins for performance reasons.36//37// Chained origin id describes an event of storing an uninitialized value to38// memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of39// (stack_id, prev_id) -> id, where40// * 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 the43// uninitialized value history.44// Following a chain of prev_id provides the full recorded history of an45// uninitialized value.46//47// This, effectively, defines a tree (or 2 trees, see below) where nodes are48// points in value history marked with origin ids, and edges are events that are49// 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 54class 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 xxxx61 return raw_id_ >> kHeapShift == 0;62 }63 bool isStackOrigin() const {64 // 1000 xxxx xxxx xxxx65 return (raw_id_ >> kDepthShift) == (1 << kDepthBits);66 }67 bool isChainedOrigin() const {68 // 1zzz xxxx xxxx xxxx, zzz != 00069 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 __msan167 168#endif // MSAN_ORIGIN_H169