1276789Sdim//===-- msan_origin.h ----------------------------------*- C++ -*-===// 2276789Sdim// 3276789Sdim// The LLVM Compiler Infrastructure 4276789Sdim// 5276789Sdim// This file is distributed under the University of Illinois Open Source 6276789Sdim// License. See LICENSE.TXT for details. 7276789Sdim// 8276789Sdim//===----------------------------------------------------------------------===// 9276789Sdim// 10276789Sdim// Origin id utils. 11276789Sdim//===----------------------------------------------------------------------===// 12276789Sdim#ifndef MSAN_ORIGIN_H 13276789Sdim#define MSAN_ORIGIN_H 14276789Sdim 15276789Sdim#include "sanitizer_common/sanitizer_stackdepot.h" 16276789Sdim#include "msan_chained_origin_depot.h" 17276789Sdim 18276789Sdimnamespace __msan { 19276789Sdim 20276789Sdim// Origin handling. 21276789Sdim// 22276789Sdim// Origin is a 32-bit identifier that is attached to any uninitialized value in 23276789Sdim// the program and describes, more or less exactly, how this memory came to be 24276789Sdim// uninitialized. 25276789Sdim// 26276789Sdim// There are 3 kinds of origin ids: 27276789Sdim// 1xxx xxxx xxxx xxxx heap origin id 28276789Sdim// 0000 xxxx xxxx xxxx stack origin id 29276789Sdim// 0zzz xxxx xxxx xxxx chained origin id 30276789Sdim// 31276789Sdim// Heap origin id describes a heap memory allocation and contains (in the xxx 32276789Sdim// part) a value of StackDepot. 33276789Sdim// 34276789Sdim// Stack origin id describes a stack memory allocation and contains (in the xxx 35276789Sdim// part) an index into StackOriginDescr and StackOriginPC. We don't store a 36276789Sdim// stack trace for such origins for performance reasons. 37276789Sdim// 38276789Sdim// Chained origin id describes an event of storing an uninitialized value to 39276789Sdim// memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of 40276789Sdim// (stack_id, prev_id) -> id, where 41276789Sdim// * stack_id describes the event. 42276789Sdim// StackDepot keeps a mapping between those and corresponding stack traces. 43276789Sdim// * prev_id is another origin id that describes the earlier part of the 44276789Sdim// uninitialized value history. 45276789Sdim// Following a chain of prev_id provides the full recorded history of an 46276789Sdim// uninitialized value. 47276789Sdim// 48276789Sdim// This, effectively, defines a tree (or 2 trees, see below) where nodes are 49276789Sdim// points in value history marked with origin ids, and edges are events that are 50276789Sdim// marked with stack_id. 51276789Sdim// 52276789Sdim// The "zzz" bits of chained origin id are used to store the length (or depth) 53276789Sdim// of the origin chain. 54276789Sdim 55276789Sdimclass Origin { 56276789Sdim public: 57276789Sdim static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; } 58276789Sdim 59276789Sdim u32 raw_id() const { return raw_id_; } 60276789Sdim bool isHeapOrigin() const { 61276789Sdim // 1xxx xxxx xxxx xxxx 62276789Sdim return raw_id_ >> kHeapShift == 0; 63276789Sdim } 64276789Sdim bool isStackOrigin() const { 65276789Sdim // 1000 xxxx xxxx xxxx 66276789Sdim return (raw_id_ >> kDepthShift) == (1 << kDepthBits); 67276789Sdim } 68276789Sdim bool isChainedOrigin() const { 69276789Sdim // 1zzz xxxx xxxx xxxx, zzz != 000 70276789Sdim return (raw_id_ >> kDepthShift) > (1 << kDepthBits); 71276789Sdim } 72276789Sdim u32 getChainedId() const { 73276789Sdim CHECK(isChainedOrigin()); 74276789Sdim return raw_id_ & kChainedIdMask; 75276789Sdim } 76276789Sdim u32 getStackId() const { 77276789Sdim CHECK(isStackOrigin()); 78276789Sdim return raw_id_ & kChainedIdMask; 79276789Sdim } 80276789Sdim u32 getHeapId() const { 81276789Sdim CHECK(isHeapOrigin()); 82276789Sdim return raw_id_ & kHeapIdMask; 83276789Sdim } 84276789Sdim 85276789Sdim // Returns the next origin in the chain and the current stack trace. 86276789Sdim Origin getNextChainedOrigin(StackTrace *stack) const { 87276789Sdim CHECK(isChainedOrigin()); 88276789Sdim u32 prev_id; 89276789Sdim u32 stack_id = ChainedOriginDepotGet(getChainedId(), &prev_id); 90288943Sdim if (stack) *stack = StackDepotGet(stack_id); 91276789Sdim return Origin(prev_id); 92276789Sdim } 93276789Sdim 94276789Sdim StackTrace getStackTraceForHeapOrigin() const { 95276789Sdim return StackDepotGet(getHeapId()); 96276789Sdim } 97276789Sdim 98276789Sdim static Origin CreateStackOrigin(u32 id) { 99276789Sdim CHECK((id & kStackIdMask) == id); 100276789Sdim return Origin((1 << kHeapShift) | id); 101276789Sdim } 102276789Sdim 103276789Sdim static Origin CreateHeapOrigin(StackTrace *stack) { 104276789Sdim u32 stack_id = StackDepotPut(*stack); 105276789Sdim CHECK(stack_id); 106276789Sdim CHECK((stack_id & kHeapIdMask) == stack_id); 107276789Sdim return Origin(stack_id); 108276789Sdim } 109276789Sdim 110276789Sdim static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) { 111276789Sdim int depth = prev.isChainedOrigin() ? prev.depth() : 0; 112276789Sdim // depth is the length of the chain minus 1. 113276789Sdim // origin_history_size of 0 means unlimited depth. 114276789Sdim if (flags()->origin_history_size > 0) { 115276789Sdim if (depth + 1 >= flags()->origin_history_size) { 116276789Sdim return prev; 117276789Sdim } else { 118276789Sdim ++depth; 119276789Sdim CHECK(depth < (1 << kDepthBits)); 120276789Sdim } 121276789Sdim } 122276789Sdim 123276789Sdim StackDepotHandle h = StackDepotPut_WithHandle(*stack); 124276789Sdim if (!h.valid()) return prev; 125276789Sdim 126276789Sdim if (flags()->origin_history_per_stack_limit > 0) { 127276789Sdim int use_count = h.use_count(); 128276789Sdim if (use_count > flags()->origin_history_per_stack_limit) return prev; 129276789Sdim } 130276789Sdim 131276789Sdim u32 chained_id; 132276789Sdim bool inserted = ChainedOriginDepotPut(h.id(), prev.raw_id(), &chained_id); 133276789Sdim CHECK((chained_id & kChainedIdMask) == chained_id); 134276789Sdim 135276789Sdim if (inserted && flags()->origin_history_per_stack_limit > 0) 136276789Sdim h.inc_use_count_unsafe(); 137276789Sdim 138276789Sdim return Origin((1 << kHeapShift) | (depth << kDepthShift) | chained_id); 139276789Sdim } 140276789Sdim 141276789Sdim static Origin FromRawId(u32 id) { 142276789Sdim return Origin(id); 143276789Sdim } 144276789Sdim 145276789Sdim private: 146276789Sdim static const int kDepthBits = 3; 147276789Sdim static const int kDepthShift = 32 - kDepthBits - 1; 148276789Sdim 149276789Sdim static const int kHeapShift = 31; 150276789Sdim static const u32 kChainedIdMask = ((u32)-1) >> (32 - kDepthShift); 151276789Sdim static const u32 kStackIdMask = ((u32)-1) >> (32 - kDepthShift); 152276789Sdim static const u32 kHeapIdMask = ((u32)-1) >> (32 - kHeapShift); 153276789Sdim 154276789Sdim u32 raw_id_; 155276789Sdim 156276789Sdim explicit Origin(u32 raw_id) : raw_id_(raw_id) {} 157276789Sdim 158276789Sdim int depth() const { 159276789Sdim CHECK(isChainedOrigin()); 160276789Sdim return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1); 161276789Sdim } 162276789Sdim 163276789Sdim public: 164276789Sdim static const int kMaxDepth = (1 << kDepthBits) - 1; 165276789Sdim}; 166276789Sdim 167276789Sdim} // namespace __msan 168276789Sdim 169276789Sdim#endif // MSAN_ORIGIN_H 170