Home | History | Annotate | Download | only in msan 
      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
    133