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