1//===-- sanitizer_stackdepotbase.h ------------------------------*- C++ -*-===//
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// Implementation of a mapping from arbitrary values to unique 32-bit
11// identifiers.
12//===----------------------------------------------------------------------===//
13
14#ifndef SANITIZER_STACKDEPOTBASE_H
15#define SANITIZER_STACKDEPOTBASE_H
16
17#include "sanitizer_internal_defs.h"
18#include "sanitizer_mutex.h"
19#include "sanitizer_atomic.h"
20#include "sanitizer_persistent_allocator.h"
21
22namespace __sanitizer {
23
24template <class Node, int kReservedBits, int kTabSizeLog>
25class StackDepotBase {
26 public:
27  typedef typename Node::args_type args_type;
28  typedef typename Node::handle_type handle_type;
29  // Maps stack trace to an unique id.
30  handle_type Put(args_type args, bool *inserted = nullptr);
31  // Retrieves a stored stack trace by the id.
32  args_type Get(u32 id);
33
34  StackDepotStats *GetStats() { return &stats; }
35
36  void LockAll();
37  void UnlockAll();
38
39 private:
40  static Node *find(Node *s, args_type args, u32 hash);
41  static Node *lock(atomic_uintptr_t *p);
42  static void unlock(atomic_uintptr_t *p, Node *s);
43
44  static const int kTabSize = 1 << kTabSizeLog;  // Hash table size.
45  static const int kPartBits = 8;
46  static const int kPartShift = sizeof(u32) * 8 - kPartBits - kReservedBits;
47  static const int kPartCount =
48      1 << kPartBits;  // Number of subparts in the table.
49  static const int kPartSize = kTabSize / kPartCount;
50  static const int kMaxId = 1 << kPartShift;
51
52  atomic_uintptr_t tab[kTabSize];   // Hash table of Node's.
53  atomic_uint32_t seq[kPartCount];  // Unique id generators.
54
55  StackDepotStats stats;
56
57  friend class StackDepotReverseMap;
58};
59
60template <class Node, int kReservedBits, int kTabSizeLog>
61Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(Node *s,
62                                                             args_type args,
63                                                             u32 hash) {
64  // Searches linked list s for the stack, returns its id.
65  for (; s; s = s->link) {
66    if (s->eq(hash, args)) {
67      return s;
68    }
69  }
70  return nullptr;
71}
72
73template <class Node, int kReservedBits, int kTabSizeLog>
74Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::lock(
75    atomic_uintptr_t *p) {
76  // Uses the pointer lsb as mutex.
77  for (int i = 0;; i++) {
78    uptr cmp = atomic_load(p, memory_order_relaxed);
79    if ((cmp & 1) == 0 &&
80        atomic_compare_exchange_weak(p, &cmp, cmp | 1, memory_order_acquire))
81      return (Node *)cmp;
82    if (i < 10)
83      proc_yield(10);
84    else
85      internal_sched_yield();
86  }
87}
88
89template <class Node, int kReservedBits, int kTabSizeLog>
90void StackDepotBase<Node, kReservedBits, kTabSizeLog>::unlock(
91    atomic_uintptr_t *p, Node *s) {
92  DCHECK_EQ((uptr)s & 1, 0);
93  atomic_store(p, (uptr)s, memory_order_release);
94}
95
96template <class Node, int kReservedBits, int kTabSizeLog>
97typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::handle_type
98StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,
99                                                      bool *inserted) {
100  if (inserted) *inserted = false;
101  if (!Node::is_valid(args)) return handle_type();
102  uptr h = Node::hash(args);
103  atomic_uintptr_t *p = &tab[h % kTabSize];
104  uptr v = atomic_load(p, memory_order_consume);
105  Node *s = (Node *)(v & ~1);
106  // First, try to find the existing stack.
107  Node *node = find(s, args, h);
108  if (node) return node->get_handle();
109  // If failed, lock, retry and insert new.
110  Node *s2 = lock(p);
111  if (s2 != s) {
112    node = find(s2, args, h);
113    if (node) {
114      unlock(p, s2);
115      return node->get_handle();
116    }
117  }
118  uptr part = (h % kTabSize) / kPartSize;
119  u32 id = atomic_fetch_add(&seq[part], 1, memory_order_relaxed) + 1;
120  stats.n_uniq_ids++;
121  CHECK_LT(id, kMaxId);
122  id |= part << kPartShift;
123  CHECK_NE(id, 0);
124  CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
125  uptr memsz = Node::storage_size(args);
126  s = (Node *)PersistentAlloc(memsz);
127  stats.allocated += memsz;
128  s->id = id;
129  s->store(args, h);
130  s->link = s2;
131  unlock(p, s);
132  if (inserted) *inserted = true;
133  return s->get_handle();
134}
135
136template <class Node, int kReservedBits, int kTabSizeLog>
137typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type
138StackDepotBase<Node, kReservedBits, kTabSizeLog>::Get(u32 id) {
139  if (id == 0) {
140    return args_type();
141  }
142  CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
143  // High kPartBits contain part id, so we need to scan at most kPartSize lists.
144  uptr part = id >> kPartShift;
145  for (int i = 0; i != kPartSize; i++) {
146    uptr idx = part * kPartSize + i;
147    CHECK_LT(idx, kTabSize);
148    atomic_uintptr_t *p = &tab[idx];
149    uptr v = atomic_load(p, memory_order_consume);
150    Node *s = (Node *)(v & ~1);
151    for (; s; s = s->link) {
152      if (s->id == id) {
153        return s->load();
154      }
155    }
156  }
157  return args_type();
158}
159
160template <class Node, int kReservedBits, int kTabSizeLog>
161void StackDepotBase<Node, kReservedBits, kTabSizeLog>::LockAll() {
162  for (int i = 0; i < kTabSize; ++i) {
163    lock(&tab[i]);
164  }
165}
166
167template <class Node, int kReservedBits, int kTabSizeLog>
168void StackDepotBase<Node, kReservedBits, kTabSizeLog>::UnlockAll() {
169  for (int i = 0; i < kTabSize; ++i) {
170    atomic_uintptr_t *p = &tab[i];
171    uptr s = atomic_load(p, memory_order_relaxed);
172    unlock(p, (Node *)(s & ~1UL));
173  }
174}
175
176} // namespace __sanitizer
177
178#endif // SANITIZER_STACKDEPOTBASE_H
179