53404
|
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.
|
|
58 |
template<typename T, T* volatile* (*next_ptr)(T&)>
|
|
59 |
class 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 |
|
|
76 |
public:
|
|
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
|