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 
24 namespace __sanitizer {
25 
26 template<typename T>
27 struct LFStack {
ClearLFStack28   void Clear() {
29     atomic_store(&head_, 0, memory_order_relaxed);
30   }
31 
EmptyLFStack32   bool Empty() const {
33     return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0;
34   }
35 
PushLFStack36   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 
PopLFStack48   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