[msan] Chained origins re-design.

Generalize StackDepot and create a new specialized instance of it to
efficiently (i.e. without duplicating stack trace data) store the
origin history tree.

This reduces memory usage for chained origins roughly by an order of
magnitude.

Most importantly, this new design allows us to put two limits on
stored history data (exposed in MSAN_OPTIONS) that help avoid
exponential growth in used memory on certain workloads.

See comments in lib/msan/msan_origin.h for more details.



git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@209284 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 76 insertions, 0 deletions

diff --git a/lib/msan/msan_origin.h b/lib/msan/msan_origin.h
new file mode 100644
index 000000000..64acf1e06
--- /dev/null
+++ b/lib/msan/msan_origin.h
@@ -0,0 +1,76 @@
+//===-- 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
+
+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.
+//
+// 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.
+//    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.
+//
+// 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.
+
+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 const int kMaxDepth = (1 << kDepthBits) - 1;
+
+  static const u32 kHeapRoot = (u32)-1;
+  static const u32 kStackRoot = (u32)-2;
+
+  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);
+  }
+  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; }
+
+ private:
+  u32 raw_id_;
+};
+
+}  // namespace __msan
+
+#endif  // MSAN_ORIGIN_H