diff options
Diffstat (limited to 'lib/msan/msan_origin.h')
-rw-r--r-- | lib/msan/msan_origin.h | 169 |
1 files changed, 169 insertions, 0 deletions
diff --git a/lib/msan/msan_origin.h b/lib/msan/msan_origin.h new file mode 100644 index 000000000000..1284c01bf2af --- /dev/null +++ b/lib/msan/msan_origin.h @@ -0,0 +1,169 @@ +//===-- msan_origin.h ----------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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 { + // 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); + } + + 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 |