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
17namespace __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
54class Origin {
55 public:
56 static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; }
57
58 u32 raw_id() const { return raw_id_; }
59 bool isHeapOrigin() const {
60 // 0xxx xxxx xxxx xxxx
61 return raw_id_ >> kHeapShift == 0;
62 }
63 bool isStackOrigin() const {
64 // 1000 xxxx xxxx xxxx
65 return (raw_id_ >> kDepthShift) == (1 << kDepthBits);
66 }
67 bool isChainedOrigin() const {
68 // 1zzz xxxx xxxx xxxx, zzz != 000
69 return (raw_id_ >> kDepthShift) > (1 << kDepthBits);
70 }
71 u32 getChainedId() const {
72 CHECK(isChainedOrigin());
73 return raw_id_ & kChainedIdMask;
74 }
75 u32 getStackId() const {
76 CHECK(isStackOrigin());
77 return raw_id_ & kChainedIdMask;
78 }
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.
85 Origin getNextChainedOrigin(StackTrace *stack) const {
86 CHECK(isChainedOrigin());
87 u32 prev_id;
88 u32 stack_id = ChainedOriginDepotGet(id: getChainedId(), other: &prev_id);
89 if (stack) *stack = StackDepotGet(id: stack_id);
90 return Origin(prev_id);
91 }
92
93 StackTrace getStackTraceForHeapOrigin() const {
94 return StackDepotGet(id: getHeapId());
95 }
96
97 static Origin CreateStackOrigin(u32 id) {
98 CHECK((id & kStackIdMask) == id);
99 return Origin((1 << kHeapShift) | id);
100 }
101
102 static Origin CreateHeapOrigin(StackTrace *stack) {
103 u32 stack_id = StackDepotPut(stack: *stack);
104 CHECK(stack_id);
105 CHECK((stack_id & kHeapIdMask) == stack_id);
106 return Origin(stack_id);
107 }
108
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: *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(here_id: h.id(), prev_id: prev.raw_id(), new_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
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
155 explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
156
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