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 15 namespace __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 47 class 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 bool isValid() const { return raw_id_ != 0 && raw_id_ != (u32)-1; } 70 71 private: 72 u32 raw_id_; 73 }; 74 75 } // namespace __msan 76 77 #endif // MSAN_ORIGIN_H 78
