1*0b57cec5SDimitry Andric //===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===// 2*0b57cec5SDimitry Andric // 3*0b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*0b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*0b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*0b57cec5SDimitry Andric // 7*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 8*0b57cec5SDimitry Andric // 9*0b57cec5SDimitry Andric // Lock-free stack. 10*0b57cec5SDimitry Andric // Uses 32/17 bits as ABA-counter on 32/64-bit platforms. 11*0b57cec5SDimitry Andric // The memory passed to Push() must not be ever munmap'ed. 12*0b57cec5SDimitry Andric // The type T must contain T *next field. 13*0b57cec5SDimitry Andric // 14*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 15*0b57cec5SDimitry Andric 16*0b57cec5SDimitry Andric #ifndef SANITIZER_LFSTACK_H 17*0b57cec5SDimitry Andric #define SANITIZER_LFSTACK_H 18*0b57cec5SDimitry Andric 19*0b57cec5SDimitry Andric #include "sanitizer_internal_defs.h" 20*0b57cec5SDimitry Andric #include "sanitizer_common.h" 21*0b57cec5SDimitry Andric #include "sanitizer_atomic.h" 22*0b57cec5SDimitry Andric 23*0b57cec5SDimitry Andric namespace __sanitizer { 24*0b57cec5SDimitry Andric 25*0b57cec5SDimitry Andric template<typename T> 26*0b57cec5SDimitry Andric struct LFStack { ClearLFStack27*0b57cec5SDimitry Andric void Clear() { 28*0b57cec5SDimitry Andric atomic_store(&head_, 0, memory_order_relaxed); 29*0b57cec5SDimitry Andric } 30*0b57cec5SDimitry Andric EmptyLFStack31*0b57cec5SDimitry Andric bool Empty() const { 32*0b57cec5SDimitry Andric return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0; 33*0b57cec5SDimitry Andric } 34*0b57cec5SDimitry Andric PushLFStack35*0b57cec5SDimitry Andric void Push(T *p) { 36*0b57cec5SDimitry Andric u64 cmp = atomic_load(&head_, memory_order_relaxed); 37*0b57cec5SDimitry Andric for (;;) { 38*0b57cec5SDimitry Andric u64 cnt = (cmp & kCounterMask) + kCounterInc; 39*0b57cec5SDimitry Andric u64 xch = (u64)(uptr)p | cnt; 40*0b57cec5SDimitry Andric p->next = (T*)(uptr)(cmp & kPtrMask); 41*0b57cec5SDimitry Andric if (atomic_compare_exchange_weak(&head_, &cmp, xch, 42*0b57cec5SDimitry Andric memory_order_release)) 43*0b57cec5SDimitry Andric break; 44*0b57cec5SDimitry Andric } 45*0b57cec5SDimitry Andric } 46*0b57cec5SDimitry Andric PopLFStack47*0b57cec5SDimitry Andric T *Pop() { 48*0b57cec5SDimitry Andric u64 cmp = atomic_load(&head_, memory_order_acquire); 49*0b57cec5SDimitry Andric for (;;) { 50*0b57cec5SDimitry Andric T *cur = (T*)(uptr)(cmp & kPtrMask); 51*0b57cec5SDimitry Andric if (!cur) 52*0b57cec5SDimitry Andric return nullptr; 53*0b57cec5SDimitry Andric T *nxt = cur->next; 54*0b57cec5SDimitry Andric u64 cnt = (cmp & kCounterMask); 55*0b57cec5SDimitry Andric u64 xch = (u64)(uptr)nxt | cnt; 56*0b57cec5SDimitry Andric if (atomic_compare_exchange_weak(&head_, &cmp, xch, 57*0b57cec5SDimitry Andric memory_order_acquire)) 58*0b57cec5SDimitry Andric return cur; 59*0b57cec5SDimitry Andric } 60*0b57cec5SDimitry Andric } 61*0b57cec5SDimitry Andric 62*0b57cec5SDimitry Andric // private: 63*0b57cec5SDimitry Andric static const int kCounterBits = FIRST_32_SECOND_64(32, 17); 64*0b57cec5SDimitry Andric static const u64 kPtrMask = ((u64)-1) >> kCounterBits; 65*0b57cec5SDimitry Andric static const u64 kCounterMask = ~kPtrMask; 66*0b57cec5SDimitry Andric static const u64 kCounterInc = kPtrMask + 1; 67*0b57cec5SDimitry Andric 68*0b57cec5SDimitry Andric atomic_uint64_t head_; 69*0b57cec5SDimitry Andric }; 70*0b57cec5SDimitry Andric } // namespace __sanitizer 71*0b57cec5SDimitry Andric 72*0b57cec5SDimitry Andric #endif // SANITIZER_LFSTACK_H 73