contrib/compiler-rt/lib/msan/msan_origin.h

   1 //===-- msan_origin.h ----------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Origin id utils.
  11 //===----------------------------------------------------------------------===//
  12 #ifndef MSAN_ORIGIN_H
  13 #define MSAN_ORIGIN_H
  14
  15 #include "sanitizer_common/sanitizer_stackdepot.h"
  16 #include "msan_chained_origin_depot.h"
  17
  18 namespace __msan {
  19
  20 // Origin handling.
  21 //
  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
  24 // uninitialized.
  25 //
  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
  30 //
  31 // Heap origin id describes a heap memory allocation and contains (in the xxx
  32 // part) a value of StackDepot.
  33 //
  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.
  37 //
  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.
  47 //
  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.
  51 //
  52 // The "zzz" bits of chained origin id are used to store the length (or depth)
  53 // of the origin chain.
  54
  55 class Origin {
  56  public:
  57   static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; }
  58
  59   u32 raw_id() const { return raw_id_; }
  60   bool isHeapOrigin() const {
  61     // 1xxx xxxx xxxx xxxx
  62     return raw_id_ >> kHeapShift == 0;
  63   }
  64   bool isStackOrigin() const {
  65     // 1000 xxxx xxxx xxxx
  66     return (raw_id_ >> kDepthShift) == (1 << kDepthBits);
  67   }
  68   bool isChainedOrigin() const {
  69     // 1zzz xxxx xxxx xxxx, zzz != 000
  70     return (raw_id_ >> kDepthShift) > (1 << kDepthBits);
  71   }
  72   u32 getChainedId() const {
  73     CHECK(isChainedOrigin());
  74     return raw_id_ & kChainedIdMask;
  75   }
  76   u32 getStackId() const {
  77     CHECK(isStackOrigin());
  78     return raw_id_ & kChainedIdMask;
  79   }
  80   u32 getHeapId() const {
  81     CHECK(isHeapOrigin());
  82     return raw_id_ & kHeapIdMask;
  83   }
  84
  85   // Returns the next origin in the chain and the current stack trace.
  86   Origin getNextChainedOrigin(StackTrace *stack) const {
  87     CHECK(isChainedOrigin());
  88     u32 prev_id;
  89     u32 stack_id = ChainedOriginDepotGet(getChainedId(), &prev_id);
  90     if (stack) *stack = StackDepotGet(stack_id);
  91     return Origin(prev_id);
  92   }
  93
  94   StackTrace getStackTraceForHeapOrigin() const {
  95     return StackDepotGet(getHeapId());
  96   }
  97
  98   static Origin CreateStackOrigin(u32 id) {
  99     CHECK((id & kStackIdMask) == id);
 100     return Origin((1 << kHeapShift) | id);
 101   }
 102
 103   static Origin CreateHeapOrigin(StackTrace *stack) {
 104     u32 stack_id = StackDepotPut(*stack);
 105     CHECK(stack_id);
 106     CHECK((stack_id & kHeapIdMask) == stack_id);
 107     return Origin(stack_id);
 108   }
 109
 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) {
 116         return prev;
 117       } else {
 118         ++depth;
 119         CHECK(depth < (1 << kDepthBits));
 120       }
 121     }
 122
 123     StackDepotHandle h = StackDepotPut_WithHandle(*stack);
 124     if (!h.valid()) return prev;
 125
 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;
 129     }
 130
 131     u32 chained_id;
 132     bool inserted = ChainedOriginDepotPut(h.id(), prev.raw_id(), &chained_id);
 133     CHECK((chained_id & kChainedIdMask) == chained_id);
 134
 135     if (inserted && flags()->origin_history_per_stack_limit > 0)
 136       h.inc_use_count_unsafe();
 137
 138     return Origin((1 << kHeapShift) | (depth << kDepthShift) | chained_id);
 139   }
 140
 141   static Origin FromRawId(u32 id) {
 142     return Origin(id);
 143   }
 144
 145  private:
 146   static const int kDepthBits = 3;
 147   static const int kDepthShift = 32 - kDepthBits - 1;
 148
 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);
 153
 154   u32 raw_id_;
 155
 156   explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
 157
 158   int depth() const {
 159     CHECK(isChainedOrigin());
 160     return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1);
 161   }
 162
 163  public:
 164   static const int kMaxDepth = (1 << kDepthBits) - 1;
 165 };
 166
 167 }  // namespace __msan
 168
 169 #endif  // MSAN_ORIGIN_H