diff options
Diffstat (limited to 'compiler-rt/lib/sanitizer_common/sanitizer_lfstack.h')
-rw-r--r-- | compiler-rt/lib/sanitizer_common/sanitizer_lfstack.h | 72 |
1 files changed, 72 insertions, 0 deletions
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_lfstack.h b/compiler-rt/lib/sanitizer_common/sanitizer_lfstack.h new file mode 100644 index 000000000000..af2ca55ec3f6 --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/sanitizer_lfstack.h @@ -0,0 +1,72 @@ +//===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Lock-free stack. +// Uses 32/17 bits as ABA-counter on 32/64-bit platforms. +// The memory passed to Push() must not be ever munmap'ed. +// The type T must contain T *next field. +// +//===----------------------------------------------------------------------===// + +#ifndef SANITIZER_LFSTACK_H +#define SANITIZER_LFSTACK_H + +#include "sanitizer_internal_defs.h" +#include "sanitizer_common.h" +#include "sanitizer_atomic.h" + +namespace __sanitizer { + +template<typename T> +struct LFStack { + void Clear() { + atomic_store(&head_, 0, memory_order_relaxed); + } + + bool Empty() const { + return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0; + } + + void Push(T *p) { + u64 cmp = atomic_load(&head_, memory_order_relaxed); + for (;;) { + u64 cnt = (cmp & kCounterMask) + kCounterInc; + u64 xch = (u64)(uptr)p | cnt; + p->next = (T*)(uptr)(cmp & kPtrMask); + if (atomic_compare_exchange_weak(&head_, &cmp, xch, + memory_order_release)) + break; + } + } + + T *Pop() { + u64 cmp = atomic_load(&head_, memory_order_acquire); + for (;;) { + T *cur = (T*)(uptr)(cmp & kPtrMask); + if (!cur) + return nullptr; + T *nxt = cur->next; + u64 cnt = (cmp & kCounterMask); + u64 xch = (u64)(uptr)nxt | cnt; + if (atomic_compare_exchange_weak(&head_, &cmp, xch, + memory_order_acquire)) + return cur; + } + } + + // private: + static const int kCounterBits = FIRST_32_SECOND_64(32, 17); + static const u64 kPtrMask = ((u64)-1) >> kCounterBits; + static const u64 kCounterMask = ~kPtrMask; + static const u64 kCounterInc = kPtrMask + 1; + + atomic_uint64_t head_; +}; +} // namespace __sanitizer + +#endif // SANITIZER_LFSTACK_H |