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