msan_origin.h revision 5d71de26cedae3dafc17449fe0182045c0bd20e8 
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  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