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 (;;) { 39 u64 cnt = (cmp & kCounterMask) + kCounterInc; 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) 53 return nullptr; 54 T *nxt = cur->next; 55 u64 cnt = (cmp & kCounterMask); 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 }; 71 } // namespace __sanitizer 72 73 #endif // SANITIZER_LFSTACK_H 74
