1//===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Lock-free stack.
11// Uses 32/17 bits as ABA-counter on 32/64-bit platforms.
12// The memory passed to Push() must not be ever munmap'ed.
13// The type T must contain T *next field.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef SANITIZER_LFSTACK_H
18#define SANITIZER_LFSTACK_H
19
20#include "sanitizer_internal_defs.h"
21#include "sanitizer_common.h"
22#include "sanitizer_atomic.h"
23
24namespace __sanitizer {
25
26template<typename T>
27struct LFStack {
28  void Clear() {
29    atomic_store(&head_, 0, memory_order_relaxed);
30  }
31
32  bool Empty() const {
33    return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0;
34  }
35
36  void Push(T *p) {
37    u64 cmp = atomic_load(&head_, memory_order_relaxed);
38    for (;;) {
39      u64 cnt = (cmp & kCounterMask) + kCounterInc;
40      u64 xch = (u64)(uptr)p | cnt;
41      p->next = (T*)(uptr)(cmp & kPtrMask);
42      if (atomic_compare_exchange_weak(&head_, &cmp, xch,
43                                       memory_order_release))
44        break;
45    }
46  }
47
48  T *Pop() {
49    u64 cmp = atomic_load(&head_, memory_order_acquire);
50    for (;;) {
51      T *cur = (T*)(uptr)(cmp & kPtrMask);
52      if (cur == 0)
53        return 0;
54      T *nxt = cur->next;
55      u64 cnt = (cmp & kCounterMask);
56      u64 xch = (u64)(uptr)nxt | cnt;
57      if (atomic_compare_exchange_weak(&head_, &cmp, xch,
58                                       memory_order_acquire))
59        return cur;
60    }
61  }
62
63  // private:
64  static const int kCounterBits = FIRST_32_SECOND_64(32, 17);
65  static const u64 kPtrMask = ((u64)-1) >> kCounterBits;
66  static const u64 kCounterMask = ~kPtrMask;
67  static const u64 kCounterInc = kPtrMask + 1;
68
69  atomic_uint64_t head_;
70};
71}  // namespace __sanitizer
72
73#endif  // #ifndef SANITIZER_LFSTACK_H
74