--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/gtest/utilities/test_lockFreeStack.cpp Sat Jan 19 19:50:01 2019 -0500
@@ -0,0 +1,306 @@
+/*
+ * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+#include "precompiled.hpp"
+#include "memory/allocation.inline.hpp"
+#include "runtime/atomic.hpp"
+#include "runtime/orderAccess.hpp"
+#include "utilities/globalDefinitions.hpp"
+#include "utilities/lockFreeStack.hpp"
+#include "threadHelper.inline.hpp"
+#include "unittest.hpp"
+#include <new>
+
+class LockFreeStackTestElement {
+ typedef LockFreeStackTestElement Element;
+
+ Element* volatile _entry;
+ Element* volatile _entry1;
+ size_t _id;
+
+ static Element* volatile* entry_ptr(Element& e) { return &e._entry; }
+ static Element* volatile* entry1_ptr(Element& e) { return &e._entry1; }
+
+public:
+ LockFreeStackTestElement(size_t id = 0) : _entry(), _entry1(), _id(id) {}
+ size_t id() const { return _id; }
+ void set_id(size_t value) { _id = value; }
+
+ typedef LockFreeStack<Element, &entry_ptr> Stack;
+ typedef LockFreeStack<Element, &entry1_ptr> Stack1;
+};
+
+typedef LockFreeStackTestElement Element;
+typedef Element::Stack Stack;
+typedef Element::Stack1 Stack1;
+
+static void initialize_ids(Element* elements, size_t size) {
+ for (size_t i = 0; i < size; ++i) {
+ elements[i].set_id(i);
+ }
+}
+
+class LockFreeStackTestBasics : public ::testing::Test {
+public:
+ LockFreeStackTestBasics();
+
+ static const size_t nelements = 10;
+ Element elements[nelements];
+ Stack stack;
+
+private:
+ void initialize();
+};
+
+const size_t LockFreeStackTestBasics::nelements;
+
+LockFreeStackTestBasics::LockFreeStackTestBasics() : stack() {
+ initialize_ids(elements, nelements);
+ initialize();
+}
+
+void LockFreeStackTestBasics::initialize() {
+ ASSERT_TRUE(stack.empty());
+ ASSERT_EQ(0u, stack.length());
+ ASSERT_TRUE(stack.pop() == NULL);
+ ASSERT_TRUE(stack.top() == NULL);
+
+ for (size_t id = 0; id < nelements; ++id) {
+ ASSERT_EQ(id, stack.length());
+ Element* e = &elements[id];
+ ASSERT_EQ(id, e->id());
+ stack.push(*e);
+ ASSERT_FALSE(stack.empty());
+ ASSERT_EQ(e, stack.top());
+ }
+}
+
+TEST_F(LockFreeStackTestBasics, push_pop) {
+ for (size_t i = nelements; i > 0; ) {
+ ASSERT_FALSE(stack.empty());
+ ASSERT_EQ(i, stack.length());
+ --i;
+ Element* e = stack.pop();
+ ASSERT_TRUE(e != NULL);
+ ASSERT_EQ(&elements[i], e);
+ ASSERT_EQ(i, e->id());
+ }
+ ASSERT_TRUE(stack.empty());
+ ASSERT_EQ(0u, stack.length());
+ ASSERT_TRUE(stack.pop() == NULL);
+}
+
+TEST_F(LockFreeStackTestBasics, prepend_one) {
+ Stack other_stack;
+ ASSERT_TRUE(other_stack.empty());
+ ASSERT_TRUE(other_stack.pop() == NULL);
+ ASSERT_EQ(0u, other_stack.length());
+ ASSERT_TRUE(other_stack.top() == NULL);
+ ASSERT_TRUE(other_stack.pop() == NULL);
+
+ other_stack.prepend(*stack.pop_all());
+ ASSERT_EQ(nelements, other_stack.length());
+ ASSERT_TRUE(stack.empty());
+ ASSERT_EQ(0u, stack.length());
+ ASSERT_TRUE(stack.pop() == NULL);
+ ASSERT_TRUE(stack.top() == NULL);
+
+ for (size_t i = nelements; i > 0; ) {
+ ASSERT_EQ(i, other_stack.length());
+ --i;
+ Element* e = other_stack.pop();
+ ASSERT_TRUE(e != NULL);
+ ASSERT_EQ(&elements[i], e);
+ ASSERT_EQ(i, e->id());
+ }
+ ASSERT_EQ(0u, other_stack.length());
+ ASSERT_TRUE(other_stack.pop() == NULL);
+}
+
+TEST_F(LockFreeStackTestBasics, prepend_two) {
+ Stack other_stack;
+ ASSERT_TRUE(other_stack.empty());
+ ASSERT_EQ(0u, other_stack.length());
+ ASSERT_TRUE(other_stack.top() == NULL);
+ ASSERT_TRUE(other_stack.pop() == NULL);
+
+ Element* top = stack.pop_all();
+ ASSERT_EQ(top, &elements[nelements - 1]);
+ other_stack.prepend(*top, elements[0]);
+
+ for (size_t i = nelements; i > 0; ) {
+ ASSERT_EQ(i, other_stack.length());
+ --i;
+ Element* e = other_stack.pop();
+ ASSERT_TRUE(e != NULL);
+ ASSERT_EQ(&elements[i], e);
+ ASSERT_EQ(i, e->id());
+ }
+ ASSERT_EQ(0u, other_stack.length());
+ ASSERT_TRUE(other_stack.pop() == NULL);
+}
+
+TEST_F(LockFreeStackTestBasics, two_stacks) {
+ Stack1 stack1;
+ ASSERT_TRUE(stack1.pop() == NULL);
+
+ for (size_t id = 0; id < nelements; ++id) {
+ stack1.push(elements[id]);
+ }
+ ASSERT_EQ(nelements, stack1.length());
+ Element* e0 = stack.top();
+ Element* e1 = stack1.top();
+ while (true) {
+ ASSERT_EQ(e0, e1);
+ if (e0 == NULL) break;
+ e0 = stack.next(*e0);
+ e1 = stack1.next(*e1);
+ }
+
+ for (size_t i = nelements; i > 0; ) {
+ ASSERT_EQ(i, stack.length());
+ ASSERT_EQ(i, stack1.length());
+ --i;
+ Element* e = stack.pop();
+ ASSERT_TRUE(e != NULL);
+ ASSERT_EQ(&elements[i], e);
+ ASSERT_EQ(i, e->id());
+
+ Element* e1 = stack1.pop();
+ ASSERT_TRUE(e1 != NULL);
+ ASSERT_EQ(&elements[i], e1);
+ ASSERT_EQ(i, e1->id());
+
+ ASSERT_EQ(e, e1);
+ }
+ ASSERT_EQ(0u, stack.length());
+ ASSERT_EQ(0u, stack1.length());
+ ASSERT_TRUE(stack.pop() == NULL);
+ ASSERT_TRUE(stack1.pop() == NULL);
+}
+
+class LockFreeStackTestThread : public JavaTestThread {
+ uint _id;
+ Stack* _from;
+ Stack* _to;
+ volatile size_t* _processed;
+ size_t _process_limit;
+ size_t _local_processed;
+ volatile bool _ready;
+
+public:
+ LockFreeStackTestThread(Semaphore* post,
+ uint id,
+ Stack* from,
+ Stack* to,
+ volatile size_t* processed,
+ size_t process_limit) :
+ JavaTestThread(post),
+ _id(id),
+ _from(from),
+ _to(to),
+ _processed(processed),
+ _process_limit(process_limit),
+ _local_processed(0),
+ _ready(false)
+ {}
+
+ virtual void main_run() {
+ OrderAccess::release_store_fence(&_ready, true);
+ while (true) {
+ Element* e = _from->pop();
+ if (e != NULL) {
+ _to->push(*e);
+ Atomic::inc(_processed);
+ ++_local_processed;
+ } else if (OrderAccess::load_acquire(_processed) == _process_limit) {
+ tty->print_cr("thread %u processed " SIZE_FORMAT, _id, _local_processed);
+ return;
+ }
+ }
+ }
+
+ bool ready() const { return OrderAccess::load_acquire(&_ready); }
+};
+
+TEST_VM(LockFreeStackTest, stress) {
+ Semaphore post;
+ Stack initial_stack;
+ Stack start_stack;
+ Stack middle_stack;
+ Stack final_stack;
+ volatile size_t stage1_processed = 0;
+ volatile size_t stage2_processed = 0;
+
+ const size_t nelements = 10000;
+ Element* elements = NEW_C_HEAP_ARRAY(Element, nelements, mtOther);
+ for (size_t id = 0; id < nelements; ++id) {
+ ::new (&elements[id]) Element(id);
+ initial_stack.push(elements[id]);
+ }
+ ASSERT_EQ(nelements, initial_stack.length());
+
+ // - stage1 threads pop from start_stack and push to middle_stack.
+ // - stage2 threads pop from middle_stack and push to final_stack.
+ // - all threads in a stage count the number of elements processed in
+ // their corresponding stageN_processed counter.
+
+ const uint stage1_threads = 2;
+ const uint stage2_threads = 2;
+ const uint nthreads = stage1_threads + stage2_threads;
+ LockFreeStackTestThread* threads[nthreads] = {};
+
+ for (uint i = 0; i < ARRAY_SIZE(threads); ++i) {
+ Stack* from = &start_stack;
+ Stack* to = &middle_stack;
+ volatile size_t* processed = &stage1_processed;
+ if (i >= stage1_threads) {
+ from = &middle_stack;
+ to = &final_stack;
+ processed = &stage2_processed;
+ }
+ threads[i] =
+ new LockFreeStackTestThread(&post, i, from, to, processed, nelements);
+ threads[i]->doit();
+ while (!threads[i]->ready()) {} // Wait until ready to start test.
+ }
+
+ // Transfer elements to start_stack to start test.
+ start_stack.prepend(*initial_stack.pop_all());
+
+ // Wait for all threads to complete.
+ for (uint i = 0; i < nthreads; ++i) {
+ post.wait();
+ }
+
+ // Verify expected state.
+ ASSERT_EQ(nelements, stage1_processed);
+ ASSERT_EQ(nelements, stage2_processed);
+ ASSERT_EQ(0u, initial_stack.length());
+ ASSERT_EQ(0u, start_stack.length());
+ ASSERT_EQ(0u, middle_stack.length());
+ ASSERT_EQ(nelements, final_stack.length());
+ while (final_stack.pop() != NULL) {}
+
+ FREE_C_HEAP_ARRAY(Element, elements);
+}