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