73 lines · c
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-exception6//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_H17#define SANITIZER_LFSTACK_H18 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 __sanitizer71 72#endif // SANITIZER_LFSTACK_H73