msan_origin.h revision 2d1fdb26e458c4ddc04155c1d421bced3ba90cd0
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 15namespace __msan { 16 17// Origin handling. 18// 19// Origin is a 32-bit identifier that is attached to any uninitialized value in 20// the program and describes, more or less exactly, how this memory came to be 21// uninitialized. 22// 23// Origin ids are values of ChainedOriginDepot, which is a mapping of (stack_id, 24// prev_id) -> id, where 25// * stack_id describes an event in the program, usually a memory store. 26// StackDepot keeps a mapping between those and corresponding stack traces. 27// * prev_id is another origin id that describes the earlier part of the 28// uninitialized value history. 29// Following a chain of prev_id provides the full recorded history of an 30// uninitialized value. 31// 32// This, effectively, defines a tree (or 2 trees, see below) where nodes are 33// points in value history marked with origin ids, and edges are events that are 34// marked with stack_id. 35// 36// There are 2 special root origin ids: 37// * kHeapRoot - an origin with prev_id == kHeapRoot describes an event of 38// allocating memory from heap. 39// * kStackRoot - an origin with prev_id == kStackRoot describes an event of 40// allocating memory from stack (i.e. on function entry). 41// Note that ChainedOriginDepot does not store any node for kHeapRoot or 42// kStackRoot. These are just special id values. 43// 44// Three highest bits of origin id are used to store the length (or depth) of 45// the origin chain. Special depth value of 0 means unlimited. 46 47class Origin { 48 public: 49 static const int kDepthBits = 3; 50 static const int kDepthShift = 32 - kDepthBits; 51 static const u32 kIdMask = ((u32)-1) >> (32 - kDepthShift); 52 static const u32 kDepthMask = ~kIdMask; 53 54 static const int kMaxDepth = (1 << kDepthBits) - 1; 55 56 static const u32 kHeapRoot = (u32)-1; 57 static const u32 kStackRoot = (u32)-2; 58 59 explicit Origin(u32 raw_id) : raw_id_(raw_id) {} 60 Origin(u32 id, u32 depth) : raw_id_((depth << kDepthShift) | id) { 61 CHECK_EQ(this->depth(), depth); 62 CHECK_EQ(this->id(), id); 63 } 64 int depth() const { return raw_id_ >> kDepthShift; } 65 u32 id() const { return raw_id_ & kIdMask; } 66 u32 raw_id() const { return raw_id_; } 67 bool isStackRoot() const { return raw_id_ == kStackRoot; } 68 bool isHeapRoot() const { return raw_id_ == kHeapRoot; } 69 70 private: 71 u32 raw_id_; 72}; 73 74} // namespace __msan 75 76#endif // MSAN_ORIGIN_H 77