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