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