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 
18 namespace __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 
55 class Origin {
56  public:
isValidId(u32 id)57   static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; }
58 
raw_id()59   u32 raw_id() const { return raw_id_; }
isHeapOrigin()60   bool isHeapOrigin() const {
61     // 1xxx xxxx xxxx xxxx
62     return raw_id_ >> kHeapShift == 0;
63   }
isStackOrigin()64   bool isStackOrigin() const {
65     // 1000 xxxx xxxx xxxx
66     return (raw_id_ >> kDepthShift) == (1 << kDepthBits);
67   }
isChainedOrigin()68   bool isChainedOrigin() const {
69     // 1zzz xxxx xxxx xxxx, zzz != 000
70     return (raw_id_ >> kDepthShift) > (1 << kDepthBits);
71   }
getChainedId()72   u32 getChainedId() const {
73     CHECK(isChainedOrigin());
74     return raw_id_ & kChainedIdMask;
75   }
getStackId()76   u32 getStackId() const {
77     CHECK(isStackOrigin());
78     return raw_id_ & kChainedIdMask;
79   }
getHeapId()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.
getNextChainedOrigin(StackTrace * stack)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 
getStackTraceForHeapOrigin()94   StackTrace getStackTraceForHeapOrigin() const {
95     return StackDepotGet(getHeapId());
96   }
97 
CreateStackOrigin(u32 id)98   static Origin CreateStackOrigin(u32 id) {
99     CHECK((id & kStackIdMask) == id);
100     return Origin((1 << kHeapShift) | id);
101   }
102 
CreateHeapOrigin(StackTrace * stack)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 
CreateChainedOrigin(Origin prev,StackTrace * stack)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 
FromRawId(u32 id)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 
Origin(u32 raw_id)156   explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
157 
depth()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