12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- msan_origin.h ----------------------------------*- C++ -*-===// 22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The LLVM Compiler Infrastructure 42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is distributed under the University of Illinois Open Source 62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// License. See LICENSE.TXT for details. 72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Origin id utils. 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef MSAN_ORIGIN_H 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define MSAN_ORIGIN_H 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines#include "sanitizer_common/sanitizer_stackdepot.h" 1686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines#include "msan_chained_origin_depot.h" 1786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __msan { 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Origin handling. 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Origin is a 32-bit identifier that is attached to any uninitialized value in 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// the program and describes, more or less exactly, how this memory came to be 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// uninitialized. 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 2686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// There are 3 kinds of origin ids: 2786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// 1xxx xxxx xxxx xxxx heap origin id 2886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// 0000 xxxx xxxx xxxx stack origin id 2986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// 0zzz xxxx xxxx xxxx chained origin id 3086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// 3186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// Heap origin id describes a heap memory allocation and contains (in the xxx 3286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// part) a value of StackDepot. 3386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// 3486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// Stack origin id describes a stack memory allocation and contains (in the xxx 3586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// part) an index into StackOriginDescr and StackOriginPC. We don't store a 3686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// stack trace for such origins for performance reasons. 3786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// 3886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// Chained origin id describes an event of storing an uninitialized value to 3986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of 4086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// (stack_id, prev_id) -> id, where 4186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// * stack_id describes the event. 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// StackDepot keeps a mapping between those and corresponding stack traces. 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// * prev_id is another origin id that describes the earlier part of the 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// uninitialized value history. 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Following a chain of prev_id provides the full recorded history of an 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// uninitialized value. 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This, effectively, defines a tree (or 2 trees, see below) where nodes are 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// points in value history marked with origin ids, and edges are events that are 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// marked with stack_id. 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 5286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// The "zzz" bits of chained origin id are used to store the length (or depth) 5386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines// of the origin chain. 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass Origin { 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 5786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; } 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 5986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 raw_id() const { return raw_id_; } 6086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines bool isHeapOrigin() const { 6186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines // 1xxx xxxx xxxx xxxx 6286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return raw_id_ >> kHeapShift == 0; 6386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 6486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines bool isStackOrigin() const { 6586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines // 1000 xxxx xxxx xxxx 6686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return (raw_id_ >> kDepthShift) == (1 << kDepthBits); 6786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 6886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines bool isChainedOrigin() const { 6986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines // 1zzz xxxx xxxx xxxx, zzz != 000 7086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return (raw_id_ >> kDepthShift) > (1 << kDepthBits); 7186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 7286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 getChainedId() const { 7386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(isChainedOrigin()); 7486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return raw_id_ & kChainedIdMask; 7586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 7686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 getStackId() const { 7786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(isStackOrigin()); 7886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return raw_id_ & kChainedIdMask; 7986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 8086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 getHeapId() const { 8186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(isHeapOrigin()); 8286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return raw_id_ & kHeapIdMask; 8386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 8486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 8586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines // Returns the next origin in the chain and the current stack trace. 8686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines Origin getNextChainedOrigin(StackTrace *stack) const { 8786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(isChainedOrigin()); 8886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 prev_id; 8986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 stack_id = ChainedOriginDepotGet(getChainedId(), &prev_id); 9086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (stack) *stack = StackDepotGet(stack_id); 9186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return Origin(prev_id); 9286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 9486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines StackTrace getStackTraceForHeapOrigin() const { 9586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return StackDepotGet(getHeapId()); 9686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 9886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static Origin CreateStackOrigin(u32 id) { 9986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK((id & kStackIdMask) == id); 10086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return Origin((1 << kHeapShift) | id); 10186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 10286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 10386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static Origin CreateHeapOrigin(StackTrace *stack) { 10486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 stack_id = StackDepotPut(*stack); 10586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(stack_id); 10686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK((stack_id & kHeapIdMask) == stack_id); 10786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return Origin(stack_id); 10886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 10986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 11086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) { 11186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines int depth = prev.isChainedOrigin() ? prev.depth() : 0; 11286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines // depth is the length of the chain minus 1. 11386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines // origin_history_size of 0 means unlimited depth. 11486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (flags()->origin_history_size > 0) { 11586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (depth + 1 >= flags()->origin_history_size) { 11686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return prev; 11786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } else { 11886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines ++depth; 11986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(depth < (1 << kDepthBits)); 12086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 12186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 12286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 12386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines StackDepotHandle h = StackDepotPut_WithHandle(*stack); 12486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (!h.valid()) return prev; 12586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 12686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (flags()->origin_history_per_stack_limit > 0) { 12786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines int use_count = h.use_count(); 12886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (use_count > flags()->origin_history_per_stack_limit) return prev; 12986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 13086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 13186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines u32 chained_id; 13286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines bool inserted = ChainedOriginDepotPut(h.id(), prev.raw_id(), &chained_id); 13386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK((chained_id & kChainedIdMask) == chained_id); 13486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 13586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (inserted && flags()->origin_history_per_stack_limit > 0) 13686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines h.inc_use_count_unsafe(); 13786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 13886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return Origin((1 << kHeapShift) | (depth << kDepthShift) | chained_id); 13986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 14086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 14186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static Origin FromRawId(u32 id) { 14286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return Origin(id); 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 14686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static const int kDepthBits = 3; 14786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static const int kDepthShift = 32 - kDepthBits - 1; 14886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 14986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static const int kHeapShift = 31; 15086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static const u32 kChainedIdMask = ((u32)-1) >> (32 - kDepthShift); 15186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static const u32 kStackIdMask = ((u32)-1) >> (32 - kDepthShift); 15286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static const u32 kHeapIdMask = ((u32)-1) >> (32 - kHeapShift); 15386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 raw_id_; 15586277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 15686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines explicit Origin(u32 raw_id) : raw_id_(raw_id) {} 15786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 15886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines int depth() const { 15986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(isChainedOrigin()); 16086277eb844c4983c81de62d7c050e92fe7155788Stephen Hines return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1); 16186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines } 16286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 16386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines public: 16486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines static const int kMaxDepth = (1 << kDepthBits) - 1; 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} // namespace __msan 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif // MSAN_ORIGIN_H 170