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 23namespace __sanitizer { 24 25template<typename T> 26struct 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