diff options
author | Evgeniy Stepanov <eugeni.stepanov@gmail.com> | 2014-12-03 13:58:40 +0000 |
---|---|---|
committer | Evgeniy Stepanov <eugeni.stepanov@gmail.com> | 2014-12-03 13:58:40 +0000 |
commit | 434a3e4dee2031afbb10c68a0f944071d131840e (patch) | |
tree | e84df970340820eb2d06bf4f60e8f084af0252fa /lib/msan/msan_origin.h | |
parent | 948698a1c629005cc27de7ca5497504a2f6159e9 (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.h | 152 |
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 |