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
34class 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
44public:
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> TestStack;
50 typedef LockFreeStack<Element, &entry1_ptr> TestStack1;
51};
52
53typedef LockFreeStackTestElement Element;
54typedef Element::TestStack TestStack;
55typedef Element::TestStack1 TestStack1;
56
57static 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
63class LockFreeStackTestBasics : public ::testing::Test {
64public:
65 LockFreeStackTestBasics();
66
67 static const size_t nelements = 10;
68 Element elements[nelements];
69 TestStack stack;
70
71private:
72 void initialize();
73};
74
75const size_t LockFreeStackTestBasics::nelements;
76
77LockFreeStackTestBasics::LockFreeStackTestBasics() : stack() {
78 initialize_ids(elements, nelements);
79 initialize();
80}
81
82void 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
98TEST_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
113TEST_F(LockFreeStackTestBasics, prepend_one) {
114 TestStack 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
140TEST_F(LockFreeStackTestBasics, prepend_two) {
141 TestStack 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
163TEST_F(LockFreeStackTestBasics, two_stacks) {
164 TestStack1 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
202class LockFreeStackTestThread : public JavaTestThread {
203 uint _id;
204 TestStack* _from;
205 TestStack* _to;
206 volatile size_t* _processed;
207 size_t _process_limit;
208 size_t _local_processed;
209 volatile bool _ready;
210
211public:
212 LockFreeStackTestThread(Semaphore* post,
213 uint id,
214 TestStack* from,
215 TestStack* 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
246TEST_VM(LockFreeStackTest, stress) {
247 Semaphore post;
248 TestStack initial_stack;
249 TestStack start_stack;
250 TestStack middle_stack;
251 TestStack 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 TestStack* from = &start_stack;
275 TestStack* 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}
307