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(a: &head_, v: 0, mo: memory_order_relaxed);
29 }
30
31 bool Empty() const {
32 return (atomic_load(a: &head_, mo: memory_order_relaxed) & kPtrMask) == 0;
33 }
34
35 void Push(T *p) {
36 u64 cmp = atomic_load(a: &head_, mo: 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(a: &head_, cmp: &cmp, xchg: xch,
42 mo: memory_order_release))
43 break;
44 }
45 }
46
47 T *Pop() {
48 u64 cmp = atomic_load(a: &head_, mo: 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(a: &head_, cmp: &cmp, xchg: xch,
57 mo: 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