1/*
2 * Copyright (c) 2019, 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_LOCKFREESTACK_HPP
26#define SHARE_UTILITIES_LOCKFREESTACK_HPP
27
28#include "runtime/atomic.hpp"
29#include "utilities/debug.hpp"
30#include "utilities/macros.hpp"
31
32// The LockFreeStack class template provides a lock-free LIFO. The objects
33// in the sequence are intrusively linked via a member in the objects. As
34// a result, there is no allocation involved in adding objects to the stack
35// or removing them from the stack.
36//
37// To be used in a LockFreeStack of objects of type T, an object of
38// type T must have a list entry member of type T* volatile, with an
39// non-member accessor function returning a pointer to that member. A
40// LockFreeStack is associated with the class of its elements and an
41// entry member from that class.
42//
43// An object can be in multiple stacks at the same time, so long as
44// each stack uses a different entry member. That is, the class of the
45// object must have multiple LockFreeStack entry members, one for each
46// stack in which the object may simultaneously be an element.
47//
48// LockFreeStacks support polymorphic elements. Because the objects
49// in a stack are externally managed, rather than being embedded
50// values in the stack, the actual type of such objects may be more
51// specific than the stack's element type.
52//
53// \tparam T is the class of the elements in the stack.
54//
55// \tparam next_ptr is a function pointer. Applying this function to
56// an object of type T must return a pointer to the list entry member
57// of the object associated with the LockFreeStack type.
58template<typename T, T* volatile* (*next_ptr)(T&)>
59class LockFreeStack {
60 T* volatile _top;
61
62 void prepend_impl(T* first, T* last) {
63 T* cur = top();
64 T* old;
65 do {
66 old = cur;
67 set_next(*last, cur);
68 cur = Atomic::cmpxchg(first, &_top, cur);
69 } while (old != cur);
70 }
71
72 // Noncopyable.
73 LockFreeStack(const LockFreeStack&);
74 LockFreeStack& operator=(const LockFreeStack&);
75
76public:
77 LockFreeStack() : _top(NULL) {}
78 ~LockFreeStack() { assert(empty(), "stack not empty"); }
79
80 // Atomically removes the top object from this stack and returns a
81 // pointer to that object, or NULL if this stack is empty. Acts as a
82 // full memory barrier. Subject to ABA behavior; callers must ensure
83 // usage is safe.
84 T* pop() {
85 T* result = top();
86 T* old;
87 do {
88 old = result;
89 T* new_top = NULL;
90 if (result != NULL) {
91 new_top = next(*result);
92 }
93 // CAS even on empty pop, for consistent membar bahavior.
94 result = Atomic::cmpxchg(new_top, &_top, result);
95 } while (result != old);
96 if (result != NULL) {
97 set_next(*result, NULL);
98 }
99 return result;
100 }
101
102 // Atomically exchange the list of elements with NULL, returning the old
103 // list of elements. Acts as a full memory barrier.
104 // postcondition: empty()
105 T* pop_all() {
106 return Atomic::xchg((T*)NULL, &_top);
107 }
108
109 // Atomically adds value to the top of this stack. Acts as a full
110 // memory barrier.
111 void push(T& value) {
112 assert(next(value) == NULL, "precondition");
113 prepend_impl(&value, &value);
114 }
115
116 // Atomically adds the list of objects (designated by first and
117 // last) before the objects already in this stack, in the same order
118 // as in the list. Acts as a full memory barrier.
119 // precondition: next(last) == NULL.
120 // postcondition: top() == &first, next(last) == old top().
121 void prepend(T& first, T& last) {
122 assert(next(last) == NULL, "precondition");
123#ifdef ASSERT
124 for (T* p = &first; p != &last; p = next(*p)) {
125 assert(p != NULL, "invalid prepend list");
126 }
127#endif
128 prepend_impl(&first, &last);
129 }
130
131 // Atomically adds the list of objects headed by first before the
132 // objects already in this stack, in the same order as in the list.
133 // Acts as a full memory barrier.
134 // postcondition: top() == &first.
135 void prepend(T& first) {
136 T* last = &first;
137 while (true) {
138 T* step_to = next(*last);
139 if (step_to == NULL) break;
140 last = step_to;
141 }
142 prepend_impl(&first, last);
143 }
144
145 // Return true if the stack is empty.
146 bool empty() const { return top() == NULL; }
147
148 // Return the most recently pushed element, or NULL if the stack is empty.
149 // The returned element is not removed from the stack.
150 T* top() const { return Atomic::load(&_top); }
151
152 // Return the number of objects in the stack. There must be no concurrent
153 // pops while the length is being determined.
154 size_t length() const {
155 size_t result = 0;
156 for (const T* current = top(); current != NULL; current = next(*current)) {
157 ++result;
158 }
159 return result;
160 }
161
162 // Return the entry following value in the list used by the
163 // specialized LockFreeStack class.
164 static T* next(const T& value) {
165 return Atomic::load(next_ptr(const_cast<T&>(value)));
166 }
167
168 // Set the entry following value to new_next in the list used by the
169 // specialized LockFreeStack class. Not thread-safe; in particular,
170 // if value is in an instance of this specialization of LockFreeStack,
171 // there must be no concurrent push or pop operations on that stack.
172 static void set_next(T& value, T* new_next) {
173 Atomic::store(new_next, next_ptr(value));
174 }
175};
176
177#endif // SHARE_UTILITIES_LOCKFREESTACK_HPP
178