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 }