contrib/compiler-rt/lib/msan/msan_chained_origin_depot.cc

   1 //===-- msan_chained_origin_depot.cc -----------------------------------===//
   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 // A storage for chained origins.
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "msan_chained_origin_depot.h"
  14
  15 #include "sanitizer_common/sanitizer_stackdepotbase.h"
  16
  17 namespace __msan {
  18
  19 struct ChainedOriginDepotDesc {
  20   u32 here_id;
  21   u32 prev_id;
  22 };
  23
  24 struct ChainedOriginDepotNode {
  25   ChainedOriginDepotNode *link;
  26   u32 id;
  27   u32 here_id;
  28   u32 prev_id;
  29
  30   typedef ChainedOriginDepotDesc args_type;
  31
  32   bool eq(u32 hash, const args_type &args) const {
  33     return here_id == args.here_id && prev_id == args.prev_id;
  34   }
  35
  36   static uptr storage_size(const args_type &args) {
  37     return sizeof(ChainedOriginDepotNode);
  38   }
  39
  40   /* This is murmur2 hash for the 64->32 bit case.
  41      It does not behave all that well because the keys have a very biased
  42      distribution (I've seen 7-element buckets with the table only 14% full).
  43
  44      here_id is built of
  45      * (1 bits) Reserved, zero.
  46      * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
  47      * (23 bits) Sequential number (each part has each own sequence).
  48
  49      prev_id has either the same distribution as here_id (but with 3:8:21)
  50      split, or one of two reserved values (-1) or (-2). Either case can
  51      dominate depending on the workload.
  52   */
  53   static u32 hash(const args_type &args) {
  54     const u32 m = 0x5bd1e995;
  55     const u32 seed = 0x9747b28c;
  56     const u32 r = 24;
  57     u32 h = seed;
  58     u32 k = args.here_id;
  59     k *= m;
  60     k ^= k >> r;
  61     k *= m;
  62     h *= m;
  63     h ^= k;
  64
  65     k = args.prev_id;
  66     k *= m;
  67     k ^= k >> r;
  68     k *= m;
  69     h *= m;
  70     h ^= k;
  71
  72     h ^= h >> 13;
  73     h *= m;
  74     h ^= h >> 15;
  75     return h;
  76   }
  77   static bool is_valid(const args_type &args) { return true; }
  78   void store(const args_type &args, u32 other_hash) {
  79     here_id = args.here_id;
  80     prev_id = args.prev_id;
  81   }
  82
  83   args_type load() const {
  84     args_type ret = {here_id, prev_id};
  85     return ret;
  86   }
  87
  88   struct Handle {
  89     ChainedOriginDepotNode *node_;
  90     Handle() : node_(nullptr) {}
  91     explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
  92     bool valid() { return node_; }
  93     u32 id() { return node_->id; }
  94     int here_id() { return node_->here_id; }
  95     int prev_id() { return node_->prev_id; }
  96   };
  97
  98   Handle get_handle() { return Handle(this); }
  99
 100   typedef Handle handle_type;
 101 };
 102
 103 static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
 104
 105 StackDepotStats *ChainedOriginDepotGetStats() {
 106   return chainedOriginDepot.GetStats();
 107 }
 108
 109 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
 110   ChainedOriginDepotDesc desc = {here_id, prev_id};
 111   bool inserted;
 112   ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
 113   *new_id = h.valid() ? h.id() : 0;
 114   return inserted;
 115 }
 116
 117 // Retrieves a stored stack trace by the id.
 118 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
 119   ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
 120   *other = desc.prev_id;
 121   return desc.here_id;
 122 }
 123
 124 void ChainedOriginDepotLockAll() {
 125   chainedOriginDepot.LockAll();
 126 }
 127
 128 void ChainedOriginDepotUnlockAll() {
 129   chainedOriginDepot.UnlockAll();
 130 }
 131
 132 } // namespace __msan