summaryrefslogtreecommitdiff
path: root/lib/msan/msan_origin.h
diff options
context:
space:
mode:
authorEvgeniy Stepanov <eugeni.stepanov@gmail.com>2014-12-03 13:58:40 +0000
committerEvgeniy Stepanov <eugeni.stepanov@gmail.com>2014-12-03 13:58:40 +0000
commit434a3e4dee2031afbb10c68a0f944071d131840e (patch)
treee84df970340820eb2d06bf4f60e8f084af0252fa /lib/msan/msan_origin.h
parent948698a1c629005cc27de7ca5497504a2f6159e9 (diff)
[msan] Change the way origin ids are built.
Previously, all origin ids were "chained" origins, i.e values of ChainedOriginDepot. This added a level of indirection for simple stack and heap allocation, which were represented as chains of length 1. This costs both RAM and CPU, but provides a joined 2**29 origin id space. It also made function (any instrumented function) entry non-async-signal-safe, but that does not really matter because memory stores in track-origins=2 mode are not async-signal-safe anyway. With this change, the type of the origin is encoded in origin id. See comment in msan_origin.h for more details. This reduces chained and stack origin id range to 2**28 each, but leaves extra 2**31 for heap origins. This change should not have any user-visible effects. git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@223233 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/msan/msan_origin.h')
-rw-r--r--lib/msan/msan_origin.h152
1 files changed, 122 insertions, 30 deletions
diff --git a/lib/msan/msan_origin.h b/lib/msan/msan_origin.h
index a4156507b..1284c01bf 100644
--- a/lib/msan/msan_origin.h
+++ b/lib/msan/msan_origin.h
@@ -12,6 +12,9 @@
#ifndef MSAN_ORIGIN_H
#define MSAN_ORIGIN_H
+#include "sanitizer_common/sanitizer_stackdepot.h"
+#include "msan_chained_origin_depot.h"
+
namespace __msan {
// Origin handling.
@@ -20,9 +23,22 @@ namespace __msan {
// the program and describes, more or less exactly, how this memory came to be
// uninitialized.
//
-// Origin ids are values of ChainedOriginDepot, which is a mapping of (stack_id,
-// prev_id) -> id, where
-// * stack_id describes an event in the program, usually a memory store.
+// 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.
@@ -33,43 +49,119 @@ namespace __msan {
// points in value history marked with origin ids, and edges are events that are
// marked with stack_id.
//
-// There are 2 special root origin ids:
-// * kHeapRoot - an origin with prev_id == kHeapRoot describes an event of
-// allocating memory from heap.
-// * kStackRoot - an origin with prev_id == kStackRoot describes an event of
-// allocating memory from stack (i.e. on function entry).
-// Note that ChainedOriginDepot does not store any node for kHeapRoot or
-// kStackRoot. These are just special id values.
-//
-// Three highest bits of origin id are used to store the length (or depth) of
-// the origin chain. Special depth value of 0 means unlimited.
+// The "zzz" bits of chained origin id are used to store the length (or depth)
+// of the origin chain.
class Origin {
public:
- static const int kDepthBits = 3;
- static const int kDepthShift = 32 - kDepthBits;
- static const u32 kIdMask = ((u32)-1) >> (32 - kDepthShift);
- static const u32 kDepthMask = ~kIdMask;
+ static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; }
- static const int kMaxDepth = (1 << kDepthBits) - 1;
+ u32 raw_id() const { return raw_id_; }
+ bool isHeapOrigin() const {
+ // 1xxx 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);
+ *stack = StackDepotGet(stack_id);
+ return Origin(prev_id);
+ }
- static const u32 kHeapRoot = (u32)-1;
- static const u32 kStackRoot = (u32)-2;
+ StackTrace getStackTraceForHeapOrigin() const {
+ return StackDepotGet(getHeapId());
+ }
- explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
- Origin(u32 id, u32 depth) : raw_id_((depth << kDepthShift) | id) {
- CHECK_EQ(this->depth(), depth);
- CHECK_EQ(this->id(), id);
+ 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);
}
- int depth() const { return raw_id_ >> kDepthShift; }
- u32 id() const { return raw_id_ & kIdMask; }
- u32 raw_id() const { return raw_id_; }
- bool isStackRoot() const { return raw_id_ == kStackRoot; }
- bool isHeapRoot() const { return raw_id_ == kHeapRoot; }
- bool isValid() const { return raw_id_ != 0 && raw_id_ != (u32)-1; }
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