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 |
#include "precompiled.hpp"
|
|
25 |
#include "memory/allocation.inline.hpp"
|
|
26 |
#include "runtime/atomic.hpp"
|
|
27 |
#include "runtime/orderAccess.hpp"
|
|
28 |
#include "utilities/globalDefinitions.hpp"
|
|
29 |
#include "utilities/lockFreeStack.hpp"
|
|
30 |
#include "threadHelper.inline.hpp"
|
|
31 |
#include "unittest.hpp"
|
|
32 |
#include <new>
|
|
33 |
|
|
34 |
class LockFreeStackTestElement {
|
|
35 |
typedef LockFreeStackTestElement Element;
|
|
36 |
|
|
37 |
Element* volatile _entry;
|
|
38 |
Element* volatile _entry1;
|
|
39 |
size_t _id;
|
|
40 |
|
|
41 |
static Element* volatile* entry_ptr(Element& e) { return &e._entry; }
|
|
42 |
static Element* volatile* entry1_ptr(Element& e) { return &e._entry1; }
|
|
43 |
|
|
44 |
public:
|
|
45 |
LockFreeStackTestElement(size_t id = 0) : _entry(), _entry1(), _id(id) {}
|
|
46 |
size_t id() const { return _id; }
|
|
47 |
void set_id(size_t value) { _id = value; }
|
|
48 |
|
|
49 |
typedef LockFreeStack<Element, &entry_ptr> Stack;
|
|
50 |
typedef LockFreeStack<Element, &entry1_ptr> Stack1;
|
|
51 |
};
|
|
52 |
|
|
53 |
typedef LockFreeStackTestElement Element;
|
|
54 |
typedef Element::Stack Stack;
|
|
55 |
typedef Element::Stack1 Stack1;
|
|
56 |
|
|
57 |
static void initialize_ids(Element* elements, size_t size) {
|
|
58 |
for (size_t i = 0; i < size; ++i) {
|
|
59 |
elements[i].set_id(i);
|
|
60 |
}
|
|
61 |
}
|
|
62 |
|
|
63 |
class LockFreeStackTestBasics : public ::testing::Test {
|
|
64 |
public:
|
|
65 |
LockFreeStackTestBasics();
|
|
66 |
|
|
67 |
static const size_t nelements = 10;
|
|
68 |
Element elements[nelements];
|
|
69 |
Stack stack;
|
|
70 |
|
|
71 |
private:
|
|
72 |
void initialize();
|
|
73 |
};
|
|
74 |
|
|
75 |
const size_t LockFreeStackTestBasics::nelements;
|
|
76 |
|
|
77 |
LockFreeStackTestBasics::LockFreeStackTestBasics() : stack() {
|
|
78 |
initialize_ids(elements, nelements);
|
|
79 |
initialize();
|
|
80 |
}
|
|
81 |
|
|
82 |
void LockFreeStackTestBasics::initialize() {
|
|
83 |
ASSERT_TRUE(stack.empty());
|
|
84 |
ASSERT_EQ(0u, stack.length());
|
|
85 |
ASSERT_TRUE(stack.pop() == NULL);
|
|
86 |
ASSERT_TRUE(stack.top() == NULL);
|
|
87 |
|
|
88 |
for (size_t id = 0; id < nelements; ++id) {
|
|
89 |
ASSERT_EQ(id, stack.length());
|
|
90 |
Element* e = &elements[id];
|
|
91 |
ASSERT_EQ(id, e->id());
|
|
92 |
stack.push(*e);
|
|
93 |
ASSERT_FALSE(stack.empty());
|
|
94 |
ASSERT_EQ(e, stack.top());
|
|
95 |
}
|
|
96 |
}
|
|
97 |
|
|
98 |
TEST_F(LockFreeStackTestBasics, push_pop) {
|
|
99 |
for (size_t i = nelements; i > 0; ) {
|
|
100 |
ASSERT_FALSE(stack.empty());
|
|
101 |
ASSERT_EQ(i, stack.length());
|
|
102 |
--i;
|
|
103 |
Element* e = stack.pop();
|
|
104 |
ASSERT_TRUE(e != NULL);
|
|
105 |
ASSERT_EQ(&elements[i], e);
|
|
106 |
ASSERT_EQ(i, e->id());
|
|
107 |
}
|
|
108 |
ASSERT_TRUE(stack.empty());
|
|
109 |
ASSERT_EQ(0u, stack.length());
|
|
110 |
ASSERT_TRUE(stack.pop() == NULL);
|
|
111 |
}
|
|
112 |
|
|
113 |
TEST_F(LockFreeStackTestBasics, prepend_one) {
|
|
114 |
Stack other_stack;
|
|
115 |
ASSERT_TRUE(other_stack.empty());
|
|
116 |
ASSERT_TRUE(other_stack.pop() == NULL);
|
|
117 |
ASSERT_EQ(0u, other_stack.length());
|
|
118 |
ASSERT_TRUE(other_stack.top() == NULL);
|
|
119 |
ASSERT_TRUE(other_stack.pop() == NULL);
|
|
120 |
|
|
121 |
other_stack.prepend(*stack.pop_all());
|
|
122 |
ASSERT_EQ(nelements, other_stack.length());
|
|
123 |
ASSERT_TRUE(stack.empty());
|
|
124 |
ASSERT_EQ(0u, stack.length());
|
|
125 |
ASSERT_TRUE(stack.pop() == NULL);
|
|
126 |
ASSERT_TRUE(stack.top() == NULL);
|
|
127 |
|
|
128 |
for (size_t i = nelements; i > 0; ) {
|
|
129 |
ASSERT_EQ(i, other_stack.length());
|
|
130 |
--i;
|
|
131 |
Element* e = other_stack.pop();
|
|
132 |
ASSERT_TRUE(e != NULL);
|
|
133 |
ASSERT_EQ(&elements[i], e);
|
|
134 |
ASSERT_EQ(i, e->id());
|
|
135 |
}
|
|
136 |
ASSERT_EQ(0u, other_stack.length());
|
|
137 |
ASSERT_TRUE(other_stack.pop() == NULL);
|
|
138 |
}
|
|
139 |
|
|
140 |
TEST_F(LockFreeStackTestBasics, prepend_two) {
|
|
141 |
Stack other_stack;
|
|
142 |
ASSERT_TRUE(other_stack.empty());
|
|
143 |
ASSERT_EQ(0u, other_stack.length());
|
|
144 |
ASSERT_TRUE(other_stack.top() == NULL);
|
|
145 |
ASSERT_TRUE(other_stack.pop() == NULL);
|
|
146 |
|
|
147 |
Element* top = stack.pop_all();
|
|
148 |
ASSERT_EQ(top, &elements[nelements - 1]);
|
|
149 |
other_stack.prepend(*top, elements[0]);
|
|
150 |
|
|
151 |
for (size_t i = nelements; i > 0; ) {
|
|
152 |
ASSERT_EQ(i, other_stack.length());
|
|
153 |
--i;
|
|
154 |
Element* e = other_stack.pop();
|
|
155 |
ASSERT_TRUE(e != NULL);
|
|
156 |
ASSERT_EQ(&elements[i], e);
|
|
157 |
ASSERT_EQ(i, e->id());
|
|
158 |
}
|
|
159 |
ASSERT_EQ(0u, other_stack.length());
|
|
160 |
ASSERT_TRUE(other_stack.pop() == NULL);
|
|
161 |
}
|
|
162 |
|
|
163 |
TEST_F(LockFreeStackTestBasics, two_stacks) {
|
|
164 |
Stack1 stack1;
|
|
165 |
ASSERT_TRUE(stack1.pop() == NULL);
|
|
166 |
|
|
167 |
for (size_t id = 0; id < nelements; ++id) {
|
|
168 |
stack1.push(elements[id]);
|
|
169 |
}
|
|
170 |
ASSERT_EQ(nelements, stack1.length());
|
|
171 |
Element* e0 = stack.top();
|
|
172 |
Element* e1 = stack1.top();
|
|
173 |
while (true) {
|
|
174 |
ASSERT_EQ(e0, e1);
|
|
175 |
if (e0 == NULL) break;
|
|
176 |
e0 = stack.next(*e0);
|
|
177 |
e1 = stack1.next(*e1);
|
|
178 |
}
|
|
179 |
|
|
180 |
for (size_t i = nelements; i > 0; ) {
|
|
181 |
ASSERT_EQ(i, stack.length());
|
|
182 |
ASSERT_EQ(i, stack1.length());
|
|
183 |
--i;
|
|
184 |
Element* e = stack.pop();
|
|
185 |
ASSERT_TRUE(e != NULL);
|
|
186 |
ASSERT_EQ(&elements[i], e);
|
|
187 |
ASSERT_EQ(i, e->id());
|
|
188 |
|
|
189 |
Element* e1 = stack1.pop();
|
|
190 |
ASSERT_TRUE(e1 != NULL);
|
|
191 |
ASSERT_EQ(&elements[i], e1);
|
|
192 |
ASSERT_EQ(i, e1->id());
|
|
193 |
|
|
194 |
ASSERT_EQ(e, e1);
|
|
195 |
}
|
|
196 |
ASSERT_EQ(0u, stack.length());
|
|
197 |
ASSERT_EQ(0u, stack1.length());
|
|
198 |
ASSERT_TRUE(stack.pop() == NULL);
|
|
199 |
ASSERT_TRUE(stack1.pop() == NULL);
|
|
200 |
}
|
|
201 |
|
|
202 |
class LockFreeStackTestThread : public JavaTestThread {
|
|
203 |
uint _id;
|
|
204 |
Stack* _from;
|
|
205 |
Stack* _to;
|
|
206 |
volatile size_t* _processed;
|
|
207 |
size_t _process_limit;
|
|
208 |
size_t _local_processed;
|
|
209 |
volatile bool _ready;
|
|
210 |
|
|
211 |
public:
|
|
212 |
LockFreeStackTestThread(Semaphore* post,
|
|
213 |
uint id,
|
|
214 |
Stack* from,
|
|
215 |
Stack* to,
|
|
216 |
volatile size_t* processed,
|
|
217 |
size_t process_limit) :
|
|
218 |
JavaTestThread(post),
|
|
219 |
_id(id),
|
|
220 |
_from(from),
|
|
221 |
_to(to),
|
|
222 |
_processed(processed),
|
|
223 |
_process_limit(process_limit),
|
|
224 |
_local_processed(0),
|
|
225 |
_ready(false)
|
|
226 |
{}
|
|
227 |
|
|
228 |
virtual void main_run() {
|
|
229 |
OrderAccess::release_store_fence(&_ready, true);
|
|
230 |
while (true) {
|
|
231 |
Element* e = _from->pop();
|
|
232 |
if (e != NULL) {
|
|
233 |
_to->push(*e);
|
|
234 |
Atomic::inc(_processed);
|
|
235 |
++_local_processed;
|
|
236 |
} else if (OrderAccess::load_acquire(_processed) == _process_limit) {
|
|
237 |
tty->print_cr("thread %u processed " SIZE_FORMAT, _id, _local_processed);
|
|
238 |
return;
|
|
239 |
}
|
|
240 |
}
|
|
241 |
}
|
|
242 |
|
|
243 |
bool ready() const { return OrderAccess::load_acquire(&_ready); }
|
|
244 |
};
|
|
245 |
|
|
246 |
TEST_VM(LockFreeStackTest, stress) {
|
|
247 |
Semaphore post;
|
|
248 |
Stack initial_stack;
|
|
249 |
Stack start_stack;
|
|
250 |
Stack middle_stack;
|
|
251 |
Stack final_stack;
|
|
252 |
volatile size_t stage1_processed = 0;
|
|
253 |
volatile size_t stage2_processed = 0;
|
|
254 |
|
|
255 |
const size_t nelements = 10000;
|
|
256 |
Element* elements = NEW_C_HEAP_ARRAY(Element, nelements, mtOther);
|
|
257 |
for (size_t id = 0; id < nelements; ++id) {
|
|
258 |
::new (&elements[id]) Element(id);
|
|
259 |
initial_stack.push(elements[id]);
|
|
260 |
}
|
|
261 |
ASSERT_EQ(nelements, initial_stack.length());
|
|
262 |
|
|
263 |
// - stage1 threads pop from start_stack and push to middle_stack.
|
|
264 |
// - stage2 threads pop from middle_stack and push to final_stack.
|
|
265 |
// - all threads in a stage count the number of elements processed in
|
|
266 |
// their corresponding stageN_processed counter.
|
|
267 |
|
|
268 |
const uint stage1_threads = 2;
|
|
269 |
const uint stage2_threads = 2;
|
|
270 |
const uint nthreads = stage1_threads + stage2_threads;
|
|
271 |
LockFreeStackTestThread* threads[nthreads] = {};
|
|
272 |
|
|
273 |
for (uint i = 0; i < ARRAY_SIZE(threads); ++i) {
|
|
274 |
Stack* from = &start_stack;
|
|
275 |
Stack* to = &middle_stack;
|
|
276 |
volatile size_t* processed = &stage1_processed;
|
|
277 |
if (i >= stage1_threads) {
|
|
278 |
from = &middle_stack;
|
|
279 |
to = &final_stack;
|
|
280 |
processed = &stage2_processed;
|
|
281 |
}
|
|
282 |
threads[i] =
|
|
283 |
new LockFreeStackTestThread(&post, i, from, to, processed, nelements);
|
|
284 |
threads[i]->doit();
|
|
285 |
while (!threads[i]->ready()) {} // Wait until ready to start test.
|
|
286 |
}
|
|
287 |
|
|
288 |
// Transfer elements to start_stack to start test.
|
|
289 |
start_stack.prepend(*initial_stack.pop_all());
|
|
290 |
|
|
291 |
// Wait for all threads to complete.
|
|
292 |
for (uint i = 0; i < nthreads; ++i) {
|
|
293 |
post.wait();
|
|
294 |
}
|
|
295 |
|
|
296 |
// Verify expected state.
|
|
297 |
ASSERT_EQ(nelements, stage1_processed);
|
|
298 |
ASSERT_EQ(nelements, stage2_processed);
|
|
299 |
ASSERT_EQ(0u, initial_stack.length());
|
|
300 |
ASSERT_EQ(0u, start_stack.length());
|
|
301 |
ASSERT_EQ(0u, middle_stack.length());
|
|
302 |
ASSERT_EQ(nelements, final_stack.length());
|
|
303 |
while (final_stack.pop() != NULL) {}
|
|
304 |
|
|
305 |
FREE_C_HEAP_ARRAY(Element, elements);
|
|
306 |
}
|