compiler-rt/lib/dfsan/dfsan_origin.h

   1 //===-- dfsan_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 // This file is a part of DataFlowSanitizer.
  10 //
  11 // Origin id utils.
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef DFSAN_ORIGIN_H
  15 #define DFSAN_ORIGIN_H
  16
  17 #include "dfsan_chained_origin_depot.h"
  18 #include "dfsan_flags.h"
  19 #include "sanitizer_common/sanitizer_stackdepot.h"
  20
  21 namespace __dfsan {
  22
  23 // Origin handling.
  24 //
  25 // Origin is a 32-bit identifier that is attached to any taint value in the
  26 // program and describes how this memory came to be tainted.
  27 //
  28 // Chained origin id is like:
  29 // zzzz xxxx xxxx xxxx
  30 //
  31 // Chained origin id describes an event of storing a taint value to
  32 // memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of
  33 // (stack_id, prev_id) -> id, where
  34 //  * stack_id describes the event.
  35 //    StackDepot keeps a mapping between those and corresponding stack traces.
  36 //  * prev_id is another origin id that describes the earlier part of the
  37 //    taint value history. 0 prev_id indicates the start of a chain.
  38 // Following a chain of prev_id provides the full recorded history of a taint
  39 // value.
  40 //
  41 // This, effectively, defines a forest where nodes are points in value history
  42 // marked with origin ids, and edges are events that are marked with stack_id.
  43 //
  44 // The "zzzz" bits of chained origin id are used to store the length of the
  45 // origin chain.
  46
  47 class Origin {
  48  public:
  49   static bool isValidId(u32 id) { return id != 0; }
  50
  51   u32 raw_id() const { return raw_id_; }
  52
  53   bool isChainedOrigin() const { return Origin::isValidId(raw_id_); }
  54
  55   u32 getChainedId() const {
  56     CHECK(Origin::isValidId(raw_id_));
  57     return raw_id_ & kChainedIdMask;
  58   }
  59
  60   // Returns the next origin in the chain and the current stack trace.
  61   //
  62   // It scans a partition of StackDepot linearly, and is used only by origin
  63   // tracking report.
  64   Origin getNextChainedOrigin(StackTrace *stack) const {
  65     CHECK(Origin::isValidId(raw_id_));
  66     u32 prev_id;
  67     u32 stack_id = GetChainedOriginDepot()->Get(getChainedId(), &prev_id);
  68     if (stack)
  69       *stack = StackDepotGet(stack_id);
  70     return Origin(prev_id);
  71   }
  72
  73   static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) {
  74     int depth = prev.isChainedOrigin() ? prev.depth() : -1;
  75     // depth is the length of the chain minus 1.
  76     // origin_history_size of 0 means unlimited depth.
  77     if (flags().origin_history_size > 0) {
  78       ++depth;
  79       if (depth >= flags().origin_history_size || depth > kMaxDepth)
  80         return prev;
  81     }
  82
  83     StackDepotHandle h = StackDepotPut_WithHandle(*stack);
  84     if (!h.valid())
  85       return prev;
  86
  87     if (flags().origin_history_per_stack_limit > 0) {
  88       int use_count = h.use_count();
  89       if (use_count > flags().origin_history_per_stack_limit)
  90         return prev;
  91     }
  92
  93     u32 chained_id;
  94     bool inserted =
  95         GetChainedOriginDepot()->Put(h.id(), prev.raw_id(), &chained_id);
  96     CHECK((chained_id & kChainedIdMask) == chained_id);
  97
  98     if (inserted && flags().origin_history_per_stack_limit > 0)
  99       h.inc_use_count_unsafe();
 100
 101     return Origin((depth << kDepthShift) | chained_id);
 102   }
 103
 104   static Origin FromRawId(u32 id) { return Origin(id); }
 105
 106  private:
 107   static const int kDepthBits = 4;
 108   static const int kDepthShift = 32 - kDepthBits;
 109
 110   static const u32 kChainedIdMask = ((u32)-1) >> kDepthBits;
 111
 112   u32 raw_id_;
 113
 114   explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
 115
 116   int depth() const {
 117     CHECK(isChainedOrigin());
 118     return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1);
 119   }
 120
 121  public:
 122   static const int kMaxDepth = (1 << kDepthBits) - 1;
 123 };
 124
 125 }  // namespace __dfsan
 126
 127 #endif  // DFSAN_ORIGIN_H