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