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