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