1//===-- sanitizer_stackdepot.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// This file is shared between AddressSanitizer and ThreadSanitizer
11// run-time libraries.
12//===----------------------------------------------------------------------===//
13
14#include "sanitizer_stackdepot.h"
15
16#include "sanitizer_common.h"
17#include "sanitizer_stackdepotbase.h"
18
19namespace __sanitizer {
20
21struct StackDepotNode {
22  StackDepotNode *link;
23  u32 id;
24  atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20;
25  u32 size;
26  u32 tag;
27  uptr stack[1];  // [size]
28
29  static const u32 kTabSizeLog = SANITIZER_ANDROID ? 16 : 20;
30  // Lower kTabSizeLog bits are equal for all items in one bucket.
31  // We use these bits to store the per-stack use counter.
32  static const u32 kUseCountBits = kTabSizeLog;
33  static const u32 kMaxUseCount = 1 << kUseCountBits;
34  static const u32 kUseCountMask = (1 << kUseCountBits) - 1;
35  static const u32 kHashMask = ~kUseCountMask;
36
37  typedef StackTrace args_type;
38  bool eq(u32 hash, const args_type &args) const {
39    u32 hash_bits =
40        atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask;
41    if ((hash & kHashMask) != hash_bits || args.size != size || args.tag != tag)
42      return false;
43    uptr i = 0;
44    for (; i < size; i++) {
45      if (stack[i] != args.trace[i]) return false;
46    }
47    return true;
48  }
49  static uptr storage_size(const args_type &args) {
50    return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr);
51  }
52  static u32 hash(const args_type &args) {
53    // murmur2
54    const u32 m = 0x5bd1e995;
55    const u32 seed = 0x9747b28c;
56    const u32 r = 24;
57    u32 h = seed ^ (args.size * sizeof(uptr));
58    for (uptr i = 0; i < args.size; i++) {
59      u32 k = args.trace[i];
60      k *= m;
61      k ^= k >> r;
62      k *= m;
63      h *= m;
64      h ^= k;
65    }
66    h ^= h >> 13;
67    h *= m;
68    h ^= h >> 15;
69    return h;
70  }
71  static bool is_valid(const args_type &args) {
72    return args.size > 0 && args.trace;
73  }
74  void store(const args_type &args, u32 hash) {
75    atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed);
76    size = args.size;
77    tag = args.tag;
78    internal_memcpy(stack, args.trace, size * sizeof(uptr));
79  }
80  args_type load() const {
81    return args_type(&stack[0], size, tag);
82  }
83  StackDepotHandle get_handle() { return StackDepotHandle(this); }
84
85  typedef StackDepotHandle handle_type;
86};
87
88COMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount);
89
90u32 StackDepotHandle::id() { return node_->id; }
91int StackDepotHandle::use_count() {
92  return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) &
93         StackDepotNode::kUseCountMask;
94}
95void StackDepotHandle::inc_use_count_unsafe() {
96  u32 prev =
97      atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) &
98      StackDepotNode::kUseCountMask;
99  CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount);
100}
101
102// FIXME(dvyukov): this single reserved bit is used in TSan.
103typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog>
104    StackDepot;
105static StackDepot theDepot;
106
107StackDepotStats *StackDepotGetStats() {
108  return theDepot.GetStats();
109}
110
111u32 StackDepotPut(StackTrace stack) {
112  StackDepotHandle h = theDepot.Put(stack);
113  return h.valid() ? h.id() : 0;
114}
115
116StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) {
117  return theDepot.Put(stack);
118}
119
120StackTrace StackDepotGet(u32 id) {
121  return theDepot.Get(id);
122}
123
124void StackDepotLockAll() {
125  theDepot.LockAll();
126}
127
128void StackDepotUnlockAll() {
129  theDepot.UnlockAll();
130}
131
132bool StackDepotReverseMap::IdDescPair::IdComparator(
133    const StackDepotReverseMap::IdDescPair &a,
134    const StackDepotReverseMap::IdDescPair &b) {
135  return a.id < b.id;
136}
137
138StackDepotReverseMap::StackDepotReverseMap() {
139  map_.reserve(StackDepotGetStats()->n_uniq_ids + 100);
140  for (int idx = 0; idx < StackDepot::kTabSize; idx++) {
141    atomic_uintptr_t *p = &theDepot.tab[idx];
142    uptr v = atomic_load(p, memory_order_consume);
143    StackDepotNode *s = (StackDepotNode*)(v & ~1);
144    for (; s; s = s->link) {
145      IdDescPair pair = {s->id, s};
146      map_.push_back(pair);
147    }
148  }
149  Sort(map_.data(), map_.size(), &IdDescPair::IdComparator);
150}
151
152StackTrace StackDepotReverseMap::Get(u32 id) {
153  if (!map_.size())
154    return StackTrace();
155  IdDescPair pair = {id, nullptr};
156  uptr idx =
157      InternalLowerBound(map_, 0, map_.size(), pair, IdDescPair::IdComparator);
158  if (idx > map_.size() || map_[idx].id != id)
159    return StackTrace();
160  return map_[idx].desc->load();
161}
162
163} // namespace __sanitizer
164