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