| //===-- msan_origin.h ----------------------------------*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Origin id utils. |
| //===----------------------------------------------------------------------===// |
| #ifndef MSAN_ORIGIN_H |
| #define MSAN_ORIGIN_H |
| |
| namespace __msan { |
| |
| // Origin handling. |
| // |
| // Origin is a 32-bit identifier that is attached to any uninitialized value in |
| // the program and describes, more or less exactly, how this memory came to be |
| // uninitialized. |
| // |
| // Origin ids are values of ChainedOriginDepot, which is a mapping of (stack_id, |
| // prev_id) -> id, where |
| // * stack_id describes an event in the program, usually a memory store. |
| // StackDepot keeps a mapping between those and corresponding stack traces. |
| // * prev_id is another origin id that describes the earlier part of the |
| // uninitialized value history. |
| // Following a chain of prev_id provides the full recorded history of an |
| // uninitialized value. |
| // |
| // This, effectively, defines a tree (or 2 trees, see below) where nodes are |
| // points in value history marked with origin ids, and edges are events that are |
| // marked with stack_id. |
| // |
| // There are 2 special root origin ids: |
| // * kHeapRoot - an origin with prev_id == kHeapRoot describes an event of |
| // allocating memory from heap. |
| // * kStackRoot - an origin with prev_id == kStackRoot describes an event of |
| // allocating memory from stack (i.e. on function entry). |
| // Note that ChainedOriginDepot does not store any node for kHeapRoot or |
| // kStackRoot. These are just special id values. |
| // |
| // Three highest bits of origin id are used to store the length (or depth) of |
| // the origin chain. Special depth value of 0 means unlimited. |
| |
| class Origin { |
| public: |
| static const int kDepthBits = 3; |
| static const int kDepthShift = 32 - kDepthBits; |
| static const u32 kIdMask = ((u32)-1) >> (32 - kDepthShift); |
| static const u32 kDepthMask = ~kIdMask; |
| |
| static const int kMaxDepth = (1 << kDepthBits) - 1; |
| |
| static const u32 kHeapRoot = (u32)-1; |
| static const u32 kStackRoot = (u32)-2; |
| |
| explicit Origin(u32 raw_id) : raw_id_(raw_id) {} |
| Origin(u32 id, u32 depth) : raw_id_((depth << kDepthShift) | id) { |
| CHECK_EQ(this->depth(), depth); |
| CHECK_EQ(this->id(), id); |
| } |
| int depth() const { return raw_id_ >> kDepthShift; } |
| u32 id() const { return raw_id_ & kIdMask; } |
| u32 raw_id() const { return raw_id_; } |
| bool isStackRoot() const { return raw_id_ == kStackRoot; } |
| bool isHeapRoot() const { return raw_id_ == kHeapRoot; } |
| bool isValid() const { return raw_id_ != 0 && raw_id_ != (u32)-1; } |
| |
| private: |
| u32 raw_id_; |
| }; |
| |
| } // namespace __msan |
| |
| #endif // MSAN_ORIGIN_H |