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