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 namespace __sanitizer {
  15
  16 bool ChainedOriginDepot::ChainedOriginDepotNode::eq(
  17     u32 hash, const args_type &args) const {
  18   return here_id == args.here_id && prev_id == args.prev_id;
  19 }
  20
  21 uptr ChainedOriginDepot::ChainedOriginDepotNode::storage_size(
  22     const args_type &args) {
  23   return sizeof(ChainedOriginDepotNode);
  24 }
  25
  26 /* This is murmur2 hash for the 64->32 bit case.
  27    It does not behave all that well because the keys have a very biased
  28    distribution (I've seen 7-element buckets with the table only 14% full).
  29
  30    here_id is built of
  31    * (1 bits) Reserved, zero.
  32    * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
  33    * (23 bits) Sequential number (each part has each own sequence).
  34
  35    prev_id has either the same distribution as here_id (but with 3:8:21)
  36    split, or one of two reserved values (-1) or (-2). Either case can
  37    dominate depending on the workload.
  38 */
  39 u32 ChainedOriginDepot::ChainedOriginDepotNode::hash(const args_type &args) {
  40   const u32 m = 0x5bd1e995;
  41   const u32 seed = 0x9747b28c;
  42   const u32 r = 24;
  43   u32 h = seed;
  44   u32 k = args.here_id;
  45   k *= m;
  46   k ^= k >> r;
  47   k *= m;
  48   h *= m;
  49   h ^= k;
  50
  51   k = args.prev_id;
  52   k *= m;
  53   k ^= k >> r;
  54   k *= m;
  55   h *= m;
  56   h ^= k;
  57
  58   h ^= h >> 13;
  59   h *= m;
  60   h ^= h >> 15;
  61   return h;
  62 }
  63
  64 bool ChainedOriginDepot::ChainedOriginDepotNode::is_valid(
  65     const args_type &args) {
  66   return true;
  67 }
  68
  69 void ChainedOriginDepot::ChainedOriginDepotNode::store(const args_type &args,
  70                                                        u32 other_hash) {
  71   here_id = args.here_id;
  72   prev_id = args.prev_id;
  73 }
  74
  75 ChainedOriginDepot::ChainedOriginDepotNode::args_type
  76 ChainedOriginDepot::ChainedOriginDepotNode::load() const {
  77   args_type ret = {here_id, prev_id};
  78   return ret;
  79 }
  80
  81 ChainedOriginDepot::ChainedOriginDepotNode::Handle
  82 ChainedOriginDepot::ChainedOriginDepotNode::get_handle() {
  83   return Handle(this);
  84 }
  85
  86 ChainedOriginDepot::ChainedOriginDepot() {}
  87
  88 StackDepotStats *ChainedOriginDepot::GetStats() { return depot.GetStats(); }
  89
  90 bool ChainedOriginDepot::Put(u32 here_id, u32 prev_id, u32 *new_id) {
  91   ChainedOriginDepotDesc desc = {here_id, prev_id};
  92   bool inserted;
  93   ChainedOriginDepotNode::Handle h = depot.Put(desc, &inserted);
  94   *new_id = h.valid() ? h.id() : 0;
  95   return inserted;
  96 }
  97
  98 u32 ChainedOriginDepot::Get(u32 id, u32 *other) {
  99   ChainedOriginDepotDesc desc = depot.Get(id);
 100   *other = desc.prev_id;
 101   return desc.here_id;
 102 }
 103
 104 void ChainedOriginDepot::LockAll() { depot.LockAll(); }
 105
 106 void ChainedOriginDepot::UnlockAll() { depot.UnlockAll(); }
 107
 108 }  // namespace __sanitizer