1 //===-- msan_origin.h ----------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
15 #include "sanitizer_common/sanitizer_stackdepot.h"
16 #include "msan_chained_origin_depot.h"
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
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
31 // Heap origin id describes a heap memory allocation and contains (in the xxx
32 // part) a value of StackDepot.
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.
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.
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.
52 // The "zzz" bits of chained origin id are used to store the length (or depth)
53 // of the origin chain.
57 static bool isValidId(u32 id
) { return id
!= 0 && id
!= (u32
)-1; }
59 u32
raw_id() const { return raw_id_
; }
60 bool isHeapOrigin() const {
61 // 1xxx xxxx xxxx xxxx
62 return raw_id_
>> kHeapShift
== 0;
64 bool isStackOrigin() const {
65 // 1000 xxxx xxxx xxxx
66 return (raw_id_
>> kDepthShift
) == (1 << kDepthBits
);
68 bool isChainedOrigin() const {
69 // 1zzz xxxx xxxx xxxx, zzz != 000
70 return (raw_id_
>> kDepthShift
) > (1 << kDepthBits
);
72 u32
getChainedId() const {
73 CHECK(isChainedOrigin());
74 return raw_id_
& kChainedIdMask
;
76 u32
getStackId() const {
77 CHECK(isStackOrigin());
78 return raw_id_
& kChainedIdMask
;
80 u32
getHeapId() const {
81 CHECK(isHeapOrigin());
82 return raw_id_
& kHeapIdMask
;
85 // Returns the next origin in the chain and the current stack trace.
86 Origin
getNextChainedOrigin(StackTrace
*stack
) const {
87 CHECK(isChainedOrigin());
89 u32 stack_id
= ChainedOriginDepotGet(getChainedId(), &prev_id
);
90 if (stack
) *stack
= StackDepotGet(stack_id
);
91 return Origin(prev_id
);
94 StackTrace
getStackTraceForHeapOrigin() const {
95 return StackDepotGet(getHeapId());
98 static Origin
CreateStackOrigin(u32 id
) {
99 CHECK((id
& kStackIdMask
) == id
);
100 return Origin((1 << kHeapShift
) | id
);
103 static Origin
CreateHeapOrigin(StackTrace
*stack
) {
104 u32 stack_id
= StackDepotPut(*stack
);
106 CHECK((stack_id
& kHeapIdMask
) == stack_id
);
107 return Origin(stack_id
);
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
) {
119 CHECK(depth
< (1 << kDepthBits
));
123 StackDepotHandle h
= StackDepotPut_WithHandle(*stack
);
124 if (!h
.valid()) return prev
;
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
;
132 bool inserted
= ChainedOriginDepotPut(h
.id(), prev
.raw_id(), &chained_id
);
133 CHECK((chained_id
& kChainedIdMask
) == chained_id
);
135 if (inserted
&& flags()->origin_history_per_stack_limit
> 0)
136 h
.inc_use_count_unsafe();
138 return Origin((1 << kHeapShift
) | (depth
<< kDepthShift
) | chained_id
);
141 static Origin
FromRawId(u32 id
) {
146 static const int kDepthBits
= 3;
147 static const int kDepthShift
= 32 - kDepthBits
- 1;
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
);
156 explicit Origin(u32 raw_id
) : raw_id_(raw_id
) {}
159 CHECK(isChainedOrigin());
160 return (raw_id_
>> kDepthShift
) & ((1 << kDepthBits
) - 1);
164 static const int kMaxDepth
= (1 << kDepthBits
) - 1;
167 } // namespace __msan
169 #endif // MSAN_ORIGIN_H