msan_origin.h revision 288943 
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#include "sanitizer_common/sanitizer_stackdepot.h"
16#include "msan_chained_origin_depot.h"
17
18namespace __msan {
19
20// Origin handling.
21//
22// Origin is a 32-bit identifier that is attached to any uninitialized value in
23// the program and describes, more or less exactly, how this memory came to be
24// uninitialized.
25//
26// There are 3 kinds of origin ids:
27// 1xxx xxxx xxxx xxxx   heap origin id
28// 0000 xxxx xxxx xxxx   stack origin id
29// 0zzz xxxx xxxx xxxx   chained origin id
30//
31// Heap origin id describes a heap memory allocation and contains (in the xxx
32// part) a value of StackDepot.
33//
34// Stack origin id describes a stack memory allocation and contains (in the xxx
35// part) an index into StackOriginDescr and StackOriginPC. We don't store a
36// stack trace for such origins for performance reasons.
37//
38// Chained origin id describes an event of storing an uninitialized value to
39// memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of
40// (stack_id, prev_id) -> id, where
41//  * stack_id describes the event.
42//    StackDepot keeps a mapping between those and corresponding stack traces.
43//  * prev_id is another origin id that describes the earlier part of the
44//    uninitialized value history.
45// Following a chain of prev_id provides the full recorded history of an
46// uninitialized value.
47//
48// This, effectively, defines a tree (or 2 trees, see below) where nodes are
49// points in value history marked with origin ids, and edges are events that are
50// marked with stack_id.
51//
52// The "zzz" bits of chained origin id are used to store the length (or depth)
53// of the origin chain.
54
55class Origin {
56 public:
57  static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; }
58
59  u32 raw_id() const { return raw_id_; }
60  bool isHeapOrigin() const {
61    // 1xxx xxxx xxxx xxxx
62    return raw_id_ >> kHeapShift == 0;
63  }
64  bool isStackOrigin() const {
65    // 1000 xxxx xxxx xxxx
66    return (raw_id_ >> kDepthShift) == (1 << kDepthBits);
67  }
68  bool isChainedOrigin() const {
69    // 1zzz xxxx xxxx xxxx, zzz != 000
70    return (raw_id_ >> kDepthShift) > (1 << kDepthBits);
71  }
72  u32 getChainedId() const {
73    CHECK(isChainedOrigin());
74    return raw_id_ & kChainedIdMask;
75  }
76  u32 getStackId() const {
77    CHECK(isStackOrigin());
78    return raw_id_ & kChainedIdMask;
79  }
80  u32 getHeapId() const {
81    CHECK(isHeapOrigin());
82    return raw_id_ & kHeapIdMask;
83  }
84
85  // Returns the next origin in the chain and the current stack trace.
86  Origin getNextChainedOrigin(StackTrace *stack) const {
87    CHECK(isChainedOrigin());
88    u32 prev_id;
89    u32 stack_id = ChainedOriginDepotGet(getChainedId(), &prev_id);
90    if (stack) *stack = StackDepotGet(stack_id);
91    return Origin(prev_id);
92  }
93
94  StackTrace getStackTraceForHeapOrigin() const {
95    return StackDepotGet(getHeapId());
96  }
97
98  static Origin CreateStackOrigin(u32 id) {
99    CHECK((id & kStackIdMask) == id);
100    return Origin((1 << kHeapShift) | id);
101  }
102
103  static Origin CreateHeapOrigin(StackTrace *stack) {
104    u32 stack_id = StackDepotPut(*stack);
105    CHECK(stack_id);
106    CHECK((stack_id & kHeapIdMask) == stack_id);
107    return Origin(stack_id);
108  }
109
110  static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) {
111    int depth = prev.isChainedOrigin() ? prev.depth() : 0;
112    // depth is the length of the chain minus 1.
113    // origin_history_size of 0 means unlimited depth.
114    if (flags()->origin_history_size > 0) {
115      if (depth + 1 >= flags()->origin_history_size) {
116        return prev;
117      } else {
118        ++depth;
119        CHECK(depth < (1 << kDepthBits));
120      }
121    }
122
123    StackDepotHandle h = StackDepotPut_WithHandle(*stack);
124    if (!h.valid()) return prev;
125
126    if (flags()->origin_history_per_stack_limit > 0) {
127      int use_count = h.use_count();
128      if (use_count > flags()->origin_history_per_stack_limit) return prev;
129    }
130
131    u32 chained_id;
132    bool inserted = ChainedOriginDepotPut(h.id(), prev.raw_id(), &chained_id);
133    CHECK((chained_id & kChainedIdMask) == chained_id);
134
135    if (inserted && flags()->origin_history_per_stack_limit > 0)
136      h.inc_use_count_unsafe();
137
138    return Origin((1 << kHeapShift) | (depth << kDepthShift) | chained_id);
139  }
140
141  static Origin FromRawId(u32 id) {
142    return Origin(id);
143  }
144
145 private:
146  static const int kDepthBits = 3;
147  static const int kDepthShift = 32 - kDepthBits - 1;
148
149  static const int kHeapShift = 31;
150  static const u32 kChainedIdMask = ((u32)-1) >> (32 - kDepthShift);
151  static const u32 kStackIdMask = ((u32)-1) >> (32 - kDepthShift);
152  static const u32 kHeapIdMask = ((u32)-1) >> (32 - kHeapShift);
153
154  u32 raw_id_;
155
156  explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
157
158  int depth() const {
159    CHECK(isChainedOrigin());
160    return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1);
161  }
162
163 public:
164  static const int kMaxDepth = (1 << kDepthBits) - 1;
165};
166
167}  // namespace __msan
168
169#endif  // MSAN_ORIGIN_H
170