compiler-rt/lib/msan/msan_origin.h

   1 //===-- msan_origin.h ----------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Origin id utils.
  10 //===----------------------------------------------------------------------===//
  11 #ifndef MSAN_ORIGIN_H
  12 #define MSAN_ORIGIN_H
  13
  14 #include "sanitizer_common/sanitizer_stackdepot.h"
  15 #include "msan_chained_origin_depot.h"
  16
  17 namespace __msan {
  18
  19 // Origin handling.
  20 //
  21 // Origin is a 32-bit identifier that is attached to any uninitialized value in
  22 // the program and describes, more or less exactly, how this memory came to be
  23 // uninitialized.
  24 //
  25 // There are 3 kinds of origin ids:
  26 // 1xxx xxxx xxxx xxxx   heap origin id
  27 // 0000 xxxx xxxx xxxx   stack origin id
  28 // 0zzz xxxx xxxx xxxx   chained origin id
  29 //
  30 // Heap origin id describes a heap memory allocation and contains (in the xxx
  31 // part) a value of StackDepot.
  32 //
  33 // Stack origin id describes a stack memory allocation and contains (in the xxx
  34 // part) an index into StackOriginDescr and StackOriginPC. We don't store a
  35 // stack trace for such origins for performance reasons.
  36 //
  37 // Chained origin id describes an event of storing an uninitialized value to
  38 // memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of
  39 // (stack_id, prev_id) -> id, where
  40 //  * stack_id describes the event.
  41 //    StackDepot keeps a mapping between those and corresponding stack traces.
  42 //  * prev_id is another origin id that describes the earlier part of the
  43 //    uninitialized value history.
  44 // Following a chain of prev_id provides the full recorded history of an
  45 // uninitialized value.
  46 //
  47 // This, effectively, defines a tree (or 2 trees, see below) where nodes are
  48 // points in value history marked with origin ids, and edges are events that are
  49 // marked with stack_id.
  50 //
  51 // The "zzz" bits of chained origin id are used to store the length (or depth)
  52 // of the origin chain.
  53
  54 class Origin {
  55  public:
  56   static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; }
  57
  58   u32 raw_id() const { return raw_id_; }
  59   bool isHeapOrigin() const {
  60     // 0xxx xxxx xxxx xxxx
  61     return raw_id_ >> kHeapShift == 0;
  62   }
  63   bool isStackOrigin() const {
  64     // 1000 xxxx xxxx xxxx
  65     return (raw_id_ >> kDepthShift) == (1 << kDepthBits);
  66   }
  67   bool isChainedOrigin() const {
  68     // 1zzz xxxx xxxx xxxx, zzz != 000
  69     return (raw_id_ >> kDepthShift) > (1 << kDepthBits);
  70   }
  71   u32 getChainedId() const {
  72     CHECK(isChainedOrigin());
  73     return raw_id_ & kChainedIdMask;
  74   }
  75   u32 getStackId() const {
  76     CHECK(isStackOrigin());
  77     return raw_id_ & kChainedIdMask;
  78   }
  79   u32 getHeapId() const {
  80     CHECK(isHeapOrigin());
  81     return raw_id_ & kHeapIdMask;
  82   }
  83
  84   // Returns the next origin in the chain and the current stack trace.
  85   Origin getNextChainedOrigin(StackTrace *stack) const {
  86     CHECK(isChainedOrigin());
  87     u32 prev_id;
  88     u32 stack_id = ChainedOriginDepotGet(getChainedId(), &prev_id);
  89     if (stack) *stack = StackDepotGet(stack_id);
  90     return Origin(prev_id);
  91   }
  92
  93   StackTrace getStackTraceForHeapOrigin() const {
  94     return StackDepotGet(getHeapId());
  95   }
  96
  97   static Origin CreateStackOrigin(u32 id) {
  98     CHECK((id & kStackIdMask) == id);
  99     return Origin((1 << kHeapShift) | id);
 100   }
 101
 102   static Origin CreateHeapOrigin(StackTrace *stack) {
 103     u32 stack_id = StackDepotPut(*stack);
 104     CHECK(stack_id);
 105     CHECK((stack_id & kHeapIdMask) == stack_id);
 106     return Origin(stack_id);
 107   }
 108
 109   static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) {
 110     int depth = prev.isChainedOrigin() ? prev.depth() : 0;
 111     // depth is the length of the chain minus 1.
 112     // origin_history_size of 0 means unlimited depth.
 113     if (flags()->origin_history_size > 0) {
 114       if (depth + 1 >= flags()->origin_history_size) {
 115         return prev;
 116       } else {
 117         ++depth;
 118         CHECK(depth < (1 << kDepthBits));
 119       }
 120     }
 121
 122     StackDepotHandle h = StackDepotPut_WithHandle(*stack);
 123     if (!h.valid()) return prev;
 124
 125     if (flags()->origin_history_per_stack_limit > 0) {
 126       int use_count = h.use_count();
 127       if (use_count > flags()->origin_history_per_stack_limit) return prev;
 128     }
 129
 130     u32 chained_id;
 131     bool inserted = ChainedOriginDepotPut(h.id(), prev.raw_id(), &chained_id);
 132     CHECK((chained_id & kChainedIdMask) == chained_id);
 133
 134     if (inserted && flags()->origin_history_per_stack_limit > 0)
 135       h.inc_use_count_unsafe();
 136
 137     return Origin((1 << kHeapShift) | (depth << kDepthShift) | chained_id);
 138   }
 139
 140   static Origin FromRawId(u32 id) {
 141     return Origin(id);
 142   }
 143
 144  private:
 145   static const int kDepthBits = 3;
 146   static const int kDepthShift = 32 - kDepthBits - 1;
 147
 148   static const int kHeapShift = 31;
 149   static const u32 kChainedIdMask = ((u32)-1) >> (32 - kDepthShift);
 150   static const u32 kStackIdMask = ((u32)-1) >> (32 - kDepthShift);
 151   static const u32 kHeapIdMask = ((u32)-1) >> (32 - kHeapShift);
 152
 153   u32 raw_id_;
 154
 155   explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
 156
 157   int depth() const {
 158     CHECK(isChainedOrigin());
 159     return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1);
 160   }
 161
 162  public:
 163   static const int kMaxDepth = (1 << kDepthBits) - 1;
 164 };
 165
 166 }  // namespace __msan
 167
 168 #endif  // MSAN_ORIGIN_H