1245614Sandrew//===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===// 2245614Sandrew// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6245614Sandrew// 7245614Sandrew//===----------------------------------------------------------------------===// 8245614Sandrew// 9245614Sandrew// Lock-free stack. 10245614Sandrew// Uses 32/17 bits as ABA-counter on 32/64-bit platforms. 11245614Sandrew// The memory passed to Push() must not be ever munmap'ed. 12245614Sandrew// The type T must contain T *next field. 13245614Sandrew// 14245614Sandrew//===----------------------------------------------------------------------===// 15245614Sandrew 16245614Sandrew#ifndef SANITIZER_LFSTACK_H 17245614Sandrew#define SANITIZER_LFSTACK_H 18245614Sandrew 19245614Sandrew#include "sanitizer_internal_defs.h" 20245614Sandrew#include "sanitizer_common.h" 21245614Sandrew#include "sanitizer_atomic.h" 22245614Sandrew 23245614Sandrewnamespace __sanitizer { 24245614Sandrew 25245614Sandrewtemplate<typename T> 26245614Sandrewstruct LFStack { 27245614Sandrew void Clear() { 28245614Sandrew atomic_store(&head_, 0, memory_order_relaxed); 29245614Sandrew } 30245614Sandrew 31245614Sandrew bool Empty() const { 32245614Sandrew return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0; 33245614Sandrew } 34245614Sandrew 35245614Sandrew void Push(T *p) { 36245614Sandrew u64 cmp = atomic_load(&head_, memory_order_relaxed); 37245614Sandrew for (;;) { 38245614Sandrew u64 cnt = (cmp & kCounterMask) + kCounterInc; 39245614Sandrew u64 xch = (u64)(uptr)p | cnt; 40245614Sandrew p->next = (T*)(uptr)(cmp & kPtrMask); 41245614Sandrew if (atomic_compare_exchange_weak(&head_, &cmp, xch, 42245614Sandrew memory_order_release)) 43245614Sandrew break; 44245614Sandrew } 45245614Sandrew } 46245614Sandrew 47245614Sandrew T *Pop() { 48245614Sandrew u64 cmp = atomic_load(&head_, memory_order_acquire); 49245614Sandrew for (;;) { 50245614Sandrew T *cur = (T*)(uptr)(cmp & kPtrMask); 51296417Sdim if (!cur) 52296417Sdim return nullptr; 53245614Sandrew T *nxt = cur->next; 54245614Sandrew u64 cnt = (cmp & kCounterMask); 55245614Sandrew u64 xch = (u64)(uptr)nxt | cnt; 56245614Sandrew if (atomic_compare_exchange_weak(&head_, &cmp, xch, 57245614Sandrew memory_order_acquire)) 58245614Sandrew return cur; 59245614Sandrew } 60245614Sandrew } 61245614Sandrew 62245614Sandrew // private: 63245614Sandrew static const int kCounterBits = FIRST_32_SECOND_64(32, 17); 64245614Sandrew static const u64 kPtrMask = ((u64)-1) >> kCounterBits; 65245614Sandrew static const u64 kCounterMask = ~kPtrMask; 66245614Sandrew static const u64 kCounterInc = kPtrMask + 1; 67245614Sandrew 68245614Sandrew atomic_uint64_t head_; 69245614Sandrew}; 70296417Sdim} // namespace __sanitizer 71245614Sandrew 72296417Sdim#endif // SANITIZER_LFSTACK_H 73