1 //===-- sanitizer_stackdepotbase.h ------------------------------*- C++ -*-===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
8 // Implementation of a mapping from arbitrary values to unique 32-bit
10 //===----------------------------------------------------------------------===//
11 #ifndef SANITIZER_STACKDEPOTBASE_H
12 #define SANITIZER_STACKDEPOTBASE_H
14 #include "sanitizer_internal_defs.h"
15 #include "sanitizer_mutex.h"
16 #include "sanitizer_atomic.h"
17 #include "sanitizer_persistent_allocator.h"
19 namespace __sanitizer
{
21 template <class Node
, int kReservedBits
, int kTabSizeLog
>
22 class StackDepotBase
{
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
);
31 StackDepotStats
*GetStats() { return &stats
; }
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
);
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
;
49 atomic_uintptr_t tab
[kTabSize
]; // Hash table of Node's.
50 atomic_uint32_t seq
[kPartCount
]; // Unique id generators.
52 StackDepotStats stats
;
54 friend class StackDepotReverseMap
;
57 template <class Node
, int kReservedBits
, int kTabSizeLog
>
58 Node
*StackDepotBase
<Node
, kReservedBits
, kTabSizeLog
>::find(Node
*s
,
61 // Searches linked list s for the stack, returns its id.
62 for (; s
; s
= s
->link
) {
63 if (s
->eq(hash
, args
)) {
70 template <class Node
, int kReservedBits
, int kTabSizeLog
>
71 Node
*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
);
77 atomic_compare_exchange_weak(p
, &cmp
, cmp
| 1, memory_order_acquire
))
82 internal_sched_yield();
86 template <class Node
, int kReservedBits
, int kTabSizeLog
>
87 void 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
);
93 template <class Node
, int kReservedBits
, int kTabSizeLog
>
94 typename StackDepotBase
<Node
, kReservedBits
, kTabSizeLog
>::handle_type
95 StackDepotBase
<Node
, kReservedBits
, kTabSizeLog
>::Put(args_type args
,
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.
109 node
= find(s2
, args
, h
);
112 return node
->get_handle();
115 uptr part
= (h
% kTabSize
) / kPartSize
;
116 u32 id
= atomic_fetch_add(&seq
[part
], 1, memory_order_relaxed
) + 1;
118 CHECK_LT(id
, kMaxId
);
119 id
|= part
<< kPartShift
;
121 CHECK_EQ(id
& (((u32
)-1) >> kReservedBits
), id
);
122 uptr memsz
= Node::storage_size(args
);
123 s
= (Node
*)PersistentAlloc(memsz
);
124 stats
.allocated
+= memsz
;
129 if (inserted
) *inserted
= true;
130 return s
->get_handle();
133 template <class Node
, int kReservedBits
, int kTabSizeLog
>
134 typename StackDepotBase
<Node
, kReservedBits
, kTabSizeLog
>::args_type
135 StackDepotBase
<Node
, kReservedBits
, kTabSizeLog
>::Get(u32 id
) {
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
) {
157 template <class Node
, int kReservedBits
, int kTabSizeLog
>
158 void StackDepotBase
<Node
, kReservedBits
, kTabSizeLog
>::LockAll() {
159 for (int i
= 0; i
< kTabSize
; ++i
) {
164 template <class Node
, int kReservedBits
, int kTabSizeLog
>
165 void 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));
173 } // namespace __sanitizer
174 #endif // SANITIZER_STACKDEPOTBASE_H