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> TestStack; 50 typedef LockFreeStack<Element, &entry1_ptr> TestStack1; 51 }; 52 53 typedef LockFreeStackTestElement Element; 54 typedef Element::TestStack TestStack; 55 typedef Element::TestStack1 TestStack1; 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 TestStack 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 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 140 TEST_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 163 TEST_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 202 class 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 211 public: 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 246 TEST_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 }