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   u32 hash() const {
     23     const u32 m = 0x5bd1e995;
     24     const u32 seed = 0x9747b28c;
     25     const u32 r = 24;
     26     u32 h = seed;
     27     u32 k = here_id;
     28     k *= m;
     29     k ^= k >> r;
     30     k *= m;
     31     h *= m;
     32     h ^= k;
     33 
     34     k = prev_id;
     35     k *= m;
     36     k ^= k >> r;
     37     k *= m;
     38     h *= m;
     39     h ^= k;
     40 
     41     h ^= h >> 13;
     42     h *= m;
     43     h ^= h >> 15;
     44     return h;
     45   }
     46   bool is_valid() { return true; }
     47 };
     48 
     49 struct ChainedOriginDepotNode {
     50   ChainedOriginDepotNode *link;
     51   u32 id;
     52   u32 here_id;
     53   u32 prev_id;
     54 
     55   typedef ChainedOriginDepotDesc args_type;
     56   bool eq(u32 hash, const args_type &args) const {
     57     return here_id == args.here_id && prev_id == args.prev_id;
     58   }
     59   static uptr storage_size(const args_type &args) {
     60     return sizeof(ChainedOriginDepotNode);
     61   }
     62   void store(const args_type &args, u32 other_hash) {
     63     here_id = args.here_id;
     64     prev_id = args.prev_id;
     65   }
     66   args_type load() const {
     67     args_type ret = {here_id, prev_id};
     68     return ret;
     69   }
     70   struct Handle {
     71     ChainedOriginDepotNode *node_;
     72     Handle() : node_(0) {}
     73     explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
     74     bool valid() { return node_; }
     75     u32 id() { return node_->id; }
     76     int here_id() { return node_->here_id; }
     77     int prev_id() { return node_->prev_id; }
     78   };
     79   Handle get_handle() { return Handle(this); }
     80 
     81   typedef Handle handle_type;
     82 };
     83 
     84 // kTabSizeLog = 22 => 32Mb static storage for bucket pointers.
     85 static StackDepotBase<ChainedOriginDepotNode, 3, 20> chainedOriginDepot;
     86 
     87 StackDepotStats *ChainedOriginDepotGetStats() {
     88   return chainedOriginDepot.GetStats();
     89 }
     90 
     91 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
     92   ChainedOriginDepotDesc desc = {here_id, prev_id};
     93   bool inserted;
     94   ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
     95   *new_id = h.valid() ? h.id() : 0;
     96   return inserted;
     97 }
     98 
     99 // Retrieves a stored stack trace by the id.
    100 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
    101   ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
    102   *other = desc.prev_id;
    103   return desc.here_id;
    104 }
    105 
    106 }  // namespace __msan
    107