author | stefank |
Mon, 25 Nov 2019 12:30:24 +0100 | |
changeset 59248 | e92153ed8bdc |
parent 53404 | 9ff1e6cacac3 |
child 59251 | 4cbfa5077d68 |
permissions | -rw-r--r-- |
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) { |
|
59248
e92153ed8bdc
8234736: Harmonize parameter order in Atomic - store
stefank
parents:
53404
diff
changeset
|
173 |
Atomic::store(next_ptr(value), new_next); |
53404 | 174 |
} |
175 |
}; |
|
176 |
||
177 |
#endif // SHARE_UTILITIES_LOCKFREESTACK_HPP |