Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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
    149