]>
Commit | Line | Data |
---|---|---|
2660d12d KS |
1 | //===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===// |
2 | // | |
b667dd70 ML |
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 | |
2660d12d KS |
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); | |
696d846a MO |
51 | if (!cur) |
52 | return nullptr; | |
2660d12d KS |
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 | }; | |
696d846a | 70 | } // namespace __sanitizer |
2660d12d | 71 | |
696d846a | 72 | #endif // SANITIZER_LFSTACK_H |