1 /*
2 * Copyright (c) 2021, 2024, 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_HPP
26 #define SHARE_UTILITIES_NONBLOCKINGQUEUE_HPP
27
28 #include "memory/padded.hpp"
29 #include "utilities/globalDefinitions.hpp"
30 #include "utilities/pair.hpp"
31
32 // The NonblockingQueue template provides a non-blocking FIFO.
33 // It has inner padding of one cache line between its two internal pointers.
34 //
35 // The queue is internally represented by a linked list of elements, with
36 // the link to the next element provided by a member of each element.
37 // Access to this member is provided by the next_ptr function.
38 //
39 // The queue has a special pseudo-element that marks the end of the list.
40 // Each queue has its own unique special element. A pointer to this element
41 // can be recognized using the is_end() function. Such a pointer must never
42 // be dereferenced. This end marker is the value of the next member of the
43 // last element in the queue, and possibly other elements while modifying
44 // the queue.
45 //
46 // A queue may temporarily appear to be empty even though elements have been
47 // added and not removed. For example, after running the following program,
48 // the value of r may be null.
49 //
50 // thread1: q.push(a); r = q.pop();
51 // thread2: q.push(b);
52 //
53 // This can occur if the push of b started before the push of a, but didn't
54 // complete until after the pop.
55 //
56 // \tparam T is the class of the elements in the queue.
57 //
58 // \tparam next_ptr is a function pointer. Applying this function to
59 // an object of type T must return a pointer to the list entry member
60 // of the object associated with the NonblockingQueue type.
61 template<typename T, T* volatile* (*next_ptr)(T&)>
62 class NonblockingQueue {
63 T* volatile _head;
64 // Padding of one cache line to avoid false sharing.
65 DEFINE_PAD_MINUS_SIZE(1, DEFAULT_PADDING_SIZE, sizeof(T*));
66 T* volatile _tail;
67
68 NONCOPYABLE(NonblockingQueue);
69
70 // Return the entry following node in the list used by the
71 // specialized NonblockingQueue class.
72 static inline T* next(const T& node);
73
74 // Set the entry following node to new_next in the list used by the
75 // specialized NonblockingQueue class. Not thread-safe, as it cannot
76 // concurrently run with push or try_pop operations that modify this
77 // node.
78 static inline void set_next(T& node, T* new_next);
79
80 // A unique pseudo-object pointer associated with this specific queue.
81 // The resulting pointer must not be dereferenced.
82 inline T* end_marker() const;
83
84 public:
85 inline NonblockingQueue();
86 inline ~NonblockingQueue() NOT_DEBUG(= default);
87
88 // Return true if the queue is empty.
89 // Not thread-safe. There must be no concurrent modification while the
90 // queue is being tested.
91 inline bool empty() const;
92
93 // Return the number of objects in the queue.
94 // Not thread-safe. There must be no concurrent modification while the
95 // length is being determined.
96 inline size_t length() const;
97
98 // Thread-safe add the object to the end of the queue.
99 // Subject to ABA behavior; callers must ensure usage is safe.
100 inline void push(T& node) { append(node, node); }
101
102 // Thread-safe add the objects from first to last to the end of the queue.
103 // Subject to ABA behavior; callers must ensure usage is safe.
104 inline void append(T& first, T& last);
105
106 // Thread-safe attempt to remove and return the first object in the queue.
107 // Returns true if successful. If successful then *node_ptr is the former
108 // first object, or null if the queue was empty. If unsuccessful, because
109 // of contention with a concurrent modification, then returns false with
110 // the value of *node_ptr unspecified. Subject to ABA behavior; callers
111 // must ensure usage is safe.
112 inline bool try_pop(T** node_ptr);
113
114 // Thread-safe remove and return the first object in the queue, or null
115 // if the queue was empty. This just iterates on try_pop() until it
116 // succeeds, returning the (possibly null) element obtained from that.
117 // Subject to ABA behavior; callers must ensure usage is safe.
118 inline T* pop();
119
120 // Take all the objects from the queue, leaving the queue empty.
121 // Not thread-safe. There must be no concurrent operations.
122 // Returns a pair of <head, tail> pointers to the current queue.
123 inline Pair<T*, T*> take_all();
124
125 // Iteration support is provided by first() and is_end(). The queue must
126 // not be modified while iterating over its elements.
127
128 // Return the first object in the queue, or an end marker (a pointer p for
129 // which is_end(p) is true) if the queue is empty.
130 inline T* first() const;
131
132 // Test whether entry is an end marker for this queue.
133 inline bool is_end(const T* entry) const;
134 };
135
136 #endif // SHARE_UTILITIES_NONBLOCKINGQUEUE_HPP