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 
  40   static Element* volatile* entry_ptr(Element& e) { return &e._entry; }
  41   static Element* volatile* entry1_ptr(Element& e) { return &e._entry1; }
  42 
  43 public:
  44   LockFreeStackTestElement(size_t id = 0) : _entry(), _entry1(), _id(id) {}
  45   size_t id() const { return _id; }
  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 
  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 
  76 LockFreeStackTestBasics::LockFreeStackTestBasics() : stack() {
  77   initialize_ids(elements, nelements);
  78   initialize();
  79 }
  80 
  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 
  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 
 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 
 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 
 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:
 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 
 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 
 242   bool ready() const { return Atomic::load_acquire(&_ready); }
 243 };
 244 
 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 }