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