|
111
|
1 //===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===//
|
|
|
2 //
|
|
145
|
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
|
|
111
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8 //
|
|
|
9 // Lock-free stack.
|
|
|
10 // Uses 32/17 bits as ABA-counter on 32/64-bit platforms.
|
|
|
11 // The memory passed to Push() must not be ever munmap'ed.
|
|
|
12 // The type T must contain T *next field.
|
|
|
13 //
|
|
|
14 //===----------------------------------------------------------------------===//
|
|
|
15
|
|
|
16 #ifndef SANITIZER_LFSTACK_H
|
|
|
17 #define SANITIZER_LFSTACK_H
|
|
|
18
|
|
|
19 #include "sanitizer_internal_defs.h"
|
|
|
20 #include "sanitizer_common.h"
|
|
|
21 #include "sanitizer_atomic.h"
|
|
|
22
|
|
|
23 namespace __sanitizer {
|
|
|
24
|
|
|
25 template<typename T>
|
|
|
26 struct LFStack {
|
|
|
27 void Clear() {
|
|
|
28 atomic_store(&head_, 0, memory_order_relaxed);
|
|
|
29 }
|
|
|
30
|
|
|
31 bool Empty() const {
|
|
|
32 return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0;
|
|
|
33 }
|
|
|
34
|
|
|
35 void Push(T *p) {
|
|
|
36 u64 cmp = atomic_load(&head_, memory_order_relaxed);
|
|
|
37 for (;;) {
|
|
|
38 u64 cnt = (cmp & kCounterMask) + kCounterInc;
|
|
|
39 u64 xch = (u64)(uptr)p | cnt;
|
|
|
40 p->next = (T*)(uptr)(cmp & kPtrMask);
|
|
|
41 if (atomic_compare_exchange_weak(&head_, &cmp, xch,
|
|
|
42 memory_order_release))
|
|
|
43 break;
|
|
|
44 }
|
|
|
45 }
|
|
|
46
|
|
|
47 T *Pop() {
|
|
|
48 u64 cmp = atomic_load(&head_, memory_order_acquire);
|
|
|
49 for (;;) {
|
|
|
50 T *cur = (T*)(uptr)(cmp & kPtrMask);
|
|
|
51 if (!cur)
|
|
|
52 return nullptr;
|
|
|
53 T *nxt = cur->next;
|
|
|
54 u64 cnt = (cmp & kCounterMask);
|
|
|
55 u64 xch = (u64)(uptr)nxt | cnt;
|
|
|
56 if (atomic_compare_exchange_weak(&head_, &cmp, xch,
|
|
|
57 memory_order_acquire))
|
|
|
58 return cur;
|
|
|
59 }
|
|
|
60 }
|
|
|
61
|
|
|
62 // private:
|
|
|
63 static const int kCounterBits = FIRST_32_SECOND_64(32, 17);
|
|
|
64 static const u64 kPtrMask = ((u64)-1) >> kCounterBits;
|
|
|
65 static const u64 kCounterMask = ~kPtrMask;
|
|
|
66 static const u64 kCounterInc = kPtrMask + 1;
|
|
|
67
|
|
|
68 atomic_uint64_t head_;
|
|
|
69 };
|
|
|
70 } // namespace __sanitizer
|
|
|
71
|
|
|
72 #endif // SANITIZER_LFSTACK_H
|
