1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef BERBERIS_BASE_LOCK_FREE_STACK_H_
18 #define BERBERIS_BASE_LOCK_FREE_STACK_H_
19 
20 #include <atomic>
21 #include <cstdint>
22 
23 #include "berberis/base/macros.h"  // DISALLOW_COPY_AND_ASSIGN
24 #include "berberis/base/pointer_and_counter.h"
25 
26 namespace berberis {
27 
28 // Lock-free stack.
29 // Can be linker-initialized.
30 // Uses 32/16 bits ABA counter on 32/64-bit platforms.
31 // Memory passed to Push should never be reused.
32 // Type T should have T* next field.
33 template <typename T>
34 class LockFreeStack {
35  public:
LockFreeStack()36   constexpr LockFreeStack() : head_(0) {}
37 
Empty()38   bool Empty() const {
39     return PointerAndCounter<T>::UnpackPointer(head_.load(std::memory_order_relaxed)) == nullptr;
40   }
41 
PushRange(T * p,T * l)42   void PushRange(T* p, T* l) {
43     // TODO(b/232598137): CHECK p, l, p(->next)* == l?
44     uint64_t cmp = head_.load(std::memory_order_relaxed);
45     while (true) {
46       uint64_t cnt = PointerAndCounter<T>::UnpackCounter(cmp) + 1;
47       uint64_t xch = PointerAndCounter<T>::PackUnsafe(p, cnt);
48       l->next = PointerAndCounter<T>::UnpackPointer(cmp);
49       // Updates cmp!
50       if (head_.compare_exchange_weak(cmp, xch, std::memory_order_release)) {
51         break;
52       }
53     }
54   }
55 
Push(T * p)56   void Push(T* p) { PushRange(p, p); }
57 
Pop()58   T* Pop() {
59     uint64_t cmp = head_.load(std::memory_order_acquire);
60     while (true) {
61       T* curr = PointerAndCounter<T>::UnpackPointer(cmp);
62       if (!curr) {
63         return nullptr;
64       }
65       T* next = curr->next;
66       uint64_t cnt = PointerAndCounter<T>::UnpackCounter(cmp);
67       uint64_t xch = PointerAndCounter<T>::PackUnsafe(next, cnt);
68       // Updates cmp!
69       if (head_.compare_exchange_weak(cmp, xch, std::memory_order_acquire)) {
70         return curr;
71       }
72     }
73   }
74 
TopForTesting()75   T* TopForTesting() { return PointerAndCounter<T>::UnpackPointer(head_); }
76 
77  private:
78   std::atomic_uint_fast64_t head_;
79 
80   DISALLOW_COPY_AND_ASSIGN(LockFreeStack);
81 };
82 
83 }  // namespace berberis
84 
85 #endif  // BERBERIS_BASE_LOCK_FREE_STACK_H_
86