1 //===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===// 2 // 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 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); 51 if (!cur) 52 return nullptr; 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 }; 70 } // namespace __sanitizer 71 72 #endif // SANITIZER_LFSTACK_H 73