libsanitizer/sanitizer_common/sanitizer_chained_origin_depot.cpp

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