1 /*
2 * Copyright (c) 2021, 2025, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_NONBLOCKINGQUEUE_INLINE_HPP
26 #define SHARE_UTILITIES_NONBLOCKINGQUEUE_INLINE_HPP
27
28 #include "utilities/nonblockingQueue.hpp"
29
30 #include "runtime/atomicAccess.hpp"
31
32 template<typename T, T* volatile* (*next_ptr)(T&)>
33 T* NonblockingQueue<T, next_ptr>::next(const T& node) {
34 return AtomicAccess::load(next_ptr(const_cast<T&>(node)));
35 }
36
37 template<typename T, T* volatile* (*next_ptr)(T&)>
38 void NonblockingQueue<T, next_ptr>::set_next(T& node, T* new_next) {
39 AtomicAccess::store(next_ptr(node), new_next);
40 }
41
42 template<typename T, T* volatile* (*next_ptr)(T&)>
43 NonblockingQueue<T, next_ptr>::NonblockingQueue() : _head(nullptr), _tail(nullptr) {}
44
45 #ifdef ASSERT
46 template<typename T, T* volatile* (*next_ptr)(T&)>
47 NonblockingQueue<T, next_ptr>::~NonblockingQueue() {
48 assert(_head == nullptr, "precondition");
49 assert(_tail == nullptr, "precondition");
50 }
51 #endif
52
53 // The end_marker must be uniquely associated with the specific queue, in
54 // case queue elements can make their way through multiple queues. A
55 // pointer to the queue itself (after casting) satisfies that requirement.
56 template<typename T, T* volatile* (*next_ptr)(T&)>
57 T* NonblockingQueue<T, next_ptr>::end_marker() const {
58 return const_cast<T*>(reinterpret_cast<const T*>(this));
59 }
60
61 template<typename T, T* volatile* (*next_ptr)(T&)>
62 T* NonblockingQueue<T, next_ptr>::first() const {
63 T* head = AtomicAccess::load(&_head);
64 return head == nullptr ? end_marker() : head;
65 }
66
67 template<typename T, T* volatile* (*next_ptr)(T&)>
68 bool NonblockingQueue<T, next_ptr>::is_end(const T* entry) const {
69 return entry == end_marker();
70 }
71
72 template<typename T, T* volatile* (*next_ptr)(T&)>
73 bool NonblockingQueue<T, next_ptr>::empty() const {
74 return AtomicAccess::load(&_head) == nullptr;
75 }
76
77 template<typename T, T* volatile* (*next_ptr)(T&)>
78 size_t NonblockingQueue<T, next_ptr>::length() const {
79 size_t result = 0;
80 for (T* cur = first(); !is_end(cur); cur = next(*cur)) {
81 ++result;
82 }
83 return result;
84 }
85
86 // An append operation atomically exchanges the new tail with the queue tail.
87 // It then sets the "next" value of the old tail to the head of the list being
88 // appended. If the old tail is null then the queue was empty, then the
89 // head of the list being appended is instead stored in the queue head.
90 //
91 // This means there is a period between the exchange and the old tail update
92 // where the queue sequence is split into two parts, the list from the queue
93 // head to the old tail, and the list being appended. If there are concurrent
94 // push/append operations, each may introduce another such segment. But they
95 // all eventually get resolved by their respective updates of their old tail's
96 // "next" value. This also means that try_pop operation must handle an object
97 // differently depending on its "next" value.
98 //
99 // A push operation is just a degenerate append, where the object being pushed
100 // is both the head and the tail of the list being appended.
101 template<typename T, T* volatile* (*next_ptr)(T&)>
102 void NonblockingQueue<T, next_ptr>::append(T& first, T& last) {
103 assert(next(last) == nullptr, "precondition");
104 // Make last the new end of the queue. Any further push/appends will
105 // extend after last. We will try to extend from the previous end of
106 // queue.
107 set_next(last, end_marker());
108 T* old_tail = AtomicAccess::xchg(&_tail, &last);
109 if (old_tail == nullptr) {
110 // If old_tail is null then the queue was empty, and _head must also be
111 // null. The correctness of this assertion depends on try_pop clearing
112 // first _head then _tail when taking the last entry.
113 assert(AtomicAccess::load(&_head) == nullptr, "invariant");
114 // Fall through to common update of _head.
115 } else if (is_end(AtomicAccess::cmpxchg(next_ptr(*old_tail), end_marker(), &first))) {
116 // Successfully extended the queue list from old_tail to first. No
117 // other push/append could have competed with us, because we claimed
118 // old_tail for extension. We won any races with try_pop by changing
119 // away from end-marker. So we're done.
120 //
121 // Note that ABA is possible here. A concurrent try_pop could take
122 // old_tail before our update of old_tail's next_ptr, old_tail gets
123 // recycled and re-added to the end of this queue, and then we
124 // successfully cmpxchg, making the list in _tail circular. Callers
125 // must ensure this can't happen.
126 return;
127 } else {
128 // A concurrent try_pop has claimed old_tail, so it is no longer in the
129 // list. The queue was logically empty. _head is either null or
130 // old_tail, depending on how far try_pop operations have progressed.
131 DEBUG_ONLY(T* old_head = AtomicAccess::load(&_head);)
132 assert((old_head == nullptr) || (old_head == old_tail), "invariant");
133 // Fall through to common update of _head.
134 }
135 // The queue was empty, and first should become the new _head. The queue
136 // will appear to be empty to any further try_pops until done.
137 AtomicAccess::store(&_head, &first);
138 }
139
140 template<typename T, T* volatile* (*next_ptr)(T&)>
141 bool NonblockingQueue<T, next_ptr>::try_pop(T** node_ptr) {
142 // We only need memory_order_consume. Upgrade it to "load_acquire"
143 // as the memory_order_consume API is not ready for use yet.
144 T* old_head = AtomicAccess::load_acquire(&_head);
145 if (old_head == nullptr) {
146 *node_ptr = nullptr;
147 return true; // Queue is empty.
148 }
149
150 T* next_node = AtomicAccess::load_acquire(next_ptr(*old_head));
151 if (!is_end(next_node)) {
152 // [Clause 1]
153 // There are several cases for next_node.
154 // (1) next_node is the extension of the queue's list.
155 // (2) next_node is null, because a competing try_pop took old_head.
156 // (3) next_node is the extension of some unrelated list, because a
157 // competing try_pop took old_head and put it in some other list.
158 //
159 // Attempt to advance the list, replacing old_head with next_node in
160 // _head. The success or failure of that attempt, along with the value
161 // of next_node, are used to partially determine which case we're in and
162 // how to proceed. In particular, advancement will fail for case (3).
163 if (old_head != AtomicAccess::cmpxchg(&_head, old_head, next_node)) {
164 // [Clause 1a]
165 // The cmpxchg to advance the list failed; a concurrent try_pop won
166 // the race and claimed old_head. This can happen for any of the
167 // next_node cases.
168 return false;
169 } else if (next_node == nullptr) {
170 // [Clause 1b]
171 // The cmpxchg to advance the list succeeded, but a concurrent try_pop
172 // has already claimed old_head (see [Clause 2] - old_head was the last
173 // entry in the list) by nulling old_head's next field. The advance set
174 // _head to null, "helping" the competing try_pop. _head will remain
175 // nullptr until a subsequent push/append. This is a lost race, and we
176 // report it as such for consistency, though we could report the queue
177 // was empty. We don't attempt to further help [Clause 2] by also
178 // trying to set _tail to nullptr, as that would just ensure that one or
179 // the other cmpxchg is a wasted failure.
180 return false;
181 } else {
182 // [Clause 1c]
183 // Successfully advanced the list and claimed old_head. next_node was
184 // in the extension of the queue's list. Return old_head after
185 // unlinking it from next_node.
186 set_next(*old_head, nullptr);
187 *node_ptr = old_head;
188 return true;
189 }
190
191 } else if (is_end(AtomicAccess::cmpxchg(next_ptr(*old_head), next_node, (T*)nullptr))) {
192 // [Clause 2]
193 // Old_head was the last entry and we've claimed it by setting its next
194 // value to null. However, this leaves the queue in disarray. Fix up
195 // the queue, possibly in conjunction with other concurrent operations.
196 // Any further try_pops will consider the queue empty until a
197 // push/append completes by installing a new head.
198
199 // The order of the two cmpxchgs doesn't matter algorithmically, but
200 // dealing with _head first gives a stronger invariant in append, and is
201 // also consistent with [Clause 1b].
202
203 // Attempt to change the queue head from old_head to null. Failure of
204 // the cmpxchg indicates a concurrent operation updated _head first. That
205 // could be either a push/append or a try_pop in [Clause 1b].
206 AtomicAccess::cmpxchg(&_head, old_head, (T*)nullptr);
207
208 // Attempt to change the queue tail from old_head to null. Failure of
209 // the cmpxchg indicates that a concurrent push/append updated _tail first.
210 // That operation will eventually recognize the old tail (our old_head) is
211 // no longer in the list and update _head from the list being appended.
212 AtomicAccess::cmpxchg(&_tail, old_head, (T*)nullptr);
213
214 // The queue has been restored to order, and we can return old_head.
215 *node_ptr = old_head;
216 return true;
217
218 } else {
219 // [Clause 3]
220 // Old_head was the last entry in the list, but either a concurrent
221 // try_pop claimed it first or a concurrent push/append extended the
222 // list from it. Either way, we lost the race to claim it.
223 return false;
224 }
225 }
226
227 template<typename T, T* volatile* (*next_ptr)(T&)>
228 T* NonblockingQueue<T, next_ptr>::pop() {
229 T* result = nullptr;
230 // Typically try_pop() will succeed without retrying many times, thus we
231 // omit SpinPause in the loop body. SpinPause or yield may be worthwhile
232 // in rare, highly contended cases, and client code could implement such
233 // with try_pop().
234 while (!try_pop(&result)) {}
235 return result;
236 }
237
238 template<typename T, T* volatile* (*next_ptr)(T&)>
239 Pair<T*, T*> NonblockingQueue<T, next_ptr>::take_all() {
240 T* tail = AtomicAccess::load(&_tail);
241 if (tail != nullptr) set_next(*tail, nullptr); // Clear end marker.
242 Pair<T*, T*> result(AtomicAccess::load(&_head), tail);
243 AtomicAccess::store(&_head, (T*)nullptr);
244 AtomicAccess::store(&_tail, (T*)nullptr);
245 return result;
246 }
247
248 #endif // SHARE_UTILITIES_NONBLOCKINGQUEUE_INLINE_HPP