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

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