1 //===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #ifndef SANITIZER_LFSTACK_H
17 #define SANITIZER_LFSTACK_H
19 #include "sanitizer_internal_defs.h"
20 #include "sanitizer_common.h"
21 #include "sanitizer_atomic.h"
23 namespace __sanitizer {
28 atomic_store(&head_, 0, memory_order_relaxed);
32 return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0;
36 u64 cmp = atomic_load(&head_, memory_order_relaxed);
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))
48 u64 cmp = atomic_load(&head_, memory_order_acquire);
50 T *cur = (T*)(uptr)(cmp & kPtrMask);
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))
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;
68 atomic_uint64_t head_;
70 } // namespace __sanitizer
72 #endif // SANITIZER_LFSTACK_H