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 { ClearLFStack26 void Clear() { 27 atomic_store(&head_, 0, memory_order_relaxed); 28 } 29 EmptyLFStack30 bool Empty() const { 31 return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0; 32 } 33 PushLFStack34 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 PopLFStack46 T *Pop() { 47 u64 cmp = atomic_load(&head_, memory_order_acquire); 48 for (;;) { 49 T *cur = (T*)(uptr)(cmp & kPtrMask); 50 if (!cur) 51 return nullptr; 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 }; 69 } // namespace __sanitizer 70 71 #endif // SANITIZER_LFSTACK_H 72