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"
34
class LockFreeStackTestElement {
35
typedef LockFreeStackTestElement Element;
37
Element* volatile _entry;
38
Element* volatile _entry1;
41
static Element* volatile* entry_ptr(Element& e) { return &e._entry; }
42
static Element* volatile* entry1_ptr(Element& e) { return &e._entry1; }
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; }
49
typedef LockFreeStack<Element, &entry_ptr> TestStack;
50
typedef LockFreeStack<Element, &entry1_ptr> TestStack1;
53
typedef LockFreeStackTestElement Element;
54
typedef Element::TestStack TestStack;
55
typedef Element::TestStack1 TestStack1;
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);
63
class LockFreeStackTestBasics : public ::testing::Test {
65
LockFreeStackTestBasics();
67
static const size_t nelements = 10;
68
Element elements[nelements];
75
const size_t LockFreeStackTestBasics::nelements;
77
LockFreeStackTestBasics::LockFreeStackTestBasics() : stack() {
78
initialize_ids(elements, nelements);
82
void LockFreeStackTestBasics::initialize() {
83
ASSERT_TRUE(stack.empty());
84
ASSERT_EQ(0u, stack.length());
85
ASSERT_TRUE(stack.pop() == nullptr);
86
ASSERT_TRUE(stack.top() == nullptr);
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());
93
ASSERT_FALSE(stack.empty());
94
ASSERT_EQ(e, stack.top());
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());
103
Element* e = stack.pop();
104
ASSERT_TRUE(e != nullptr);
105
ASSERT_EQ(&elements[i], e);
106
ASSERT_EQ(i, e->id());
108
ASSERT_TRUE(stack.empty());
109
ASSERT_EQ(0u, stack.length());
110
ASSERT_TRUE(stack.pop() == nullptr);
113
TEST_F(LockFreeStackTestBasics, prepend_one) {
114
TestStack other_stack;
115
ASSERT_TRUE(other_stack.empty());
116
ASSERT_TRUE(other_stack.pop() == nullptr);
117
ASSERT_EQ(0u, other_stack.length());
118
ASSERT_TRUE(other_stack.top() == nullptr);
119
ASSERT_TRUE(other_stack.pop() == nullptr);
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() == nullptr);
126
ASSERT_TRUE(stack.top() == nullptr);
128
for (size_t i = nelements; i > 0; ) {
129
ASSERT_EQ(i, other_stack.length());
131
Element* e = other_stack.pop();
132
ASSERT_TRUE(e != nullptr);
133
ASSERT_EQ(&elements[i], e);
134
ASSERT_EQ(i, e->id());
136
ASSERT_EQ(0u, other_stack.length());
137
ASSERT_TRUE(other_stack.pop() == nullptr);
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() == nullptr);
145
ASSERT_TRUE(other_stack.pop() == nullptr);
147
Element* top = stack.pop_all();
148
ASSERT_EQ(top, &elements[nelements - 1]);
149
other_stack.prepend(*top, elements[0]);
151
for (size_t i = nelements; i > 0; ) {
152
ASSERT_EQ(i, other_stack.length());
154
Element* e = other_stack.pop();
155
ASSERT_TRUE(e != nullptr);
156
ASSERT_EQ(&elements[i], e);
157
ASSERT_EQ(i, e->id());
159
ASSERT_EQ(0u, other_stack.length());
160
ASSERT_TRUE(other_stack.pop() == nullptr);
163
TEST_F(LockFreeStackTestBasics, two_stacks) {
165
ASSERT_TRUE(stack1.pop() == nullptr);
167
for (size_t id = 0; id < nelements; ++id) {
168
stack1.push(elements[id]);
170
ASSERT_EQ(nelements, stack1.length());
171
Element* e0 = stack.top();
172
Element* e1 = stack1.top();
175
if (e0 == nullptr) break;
176
e0 = stack.next(*e0);
177
e1 = stack1.next(*e1);
180
for (size_t i = nelements; i > 0; ) {
181
ASSERT_EQ(i, stack.length());
182
ASSERT_EQ(i, stack1.length());
184
Element* e = stack.pop();
185
ASSERT_TRUE(e != nullptr);
186
ASSERT_EQ(&elements[i], e);
187
ASSERT_EQ(i, e->id());
189
Element* e1 = stack1.pop();
190
ASSERT_TRUE(e1 != nullptr);
191
ASSERT_EQ(&elements[i], e1);
192
ASSERT_EQ(i, e1->id());
196
ASSERT_EQ(0u, stack.length());
197
ASSERT_EQ(0u, stack1.length());
198
ASSERT_TRUE(stack.pop() == nullptr);
199
ASSERT_TRUE(stack1.pop() == nullptr);
202
class LockFreeStackTestThread : public JavaTestThread {
206
volatile size_t* _processed;
207
size_t _process_limit;
208
size_t _local_processed;
209
volatile bool _ready;
212
LockFreeStackTestThread(Semaphore* post,
216
volatile size_t* processed,
217
size_t process_limit) :
218
JavaTestThread(post),
222
_processed(processed),
223
_process_limit(process_limit),
228
virtual void main_run() {
229
Atomic::release_store_fence(&_ready, true);
231
Element* e = _from->pop();
234
Atomic::inc(_processed);
236
} else if (Atomic::load_acquire(_processed) == _process_limit) {
237
tty->print_cr("thread %u processed " SIZE_FORMAT, _id, _local_processed);
243
bool ready() const { return Atomic::load_acquire(&_ready); }
246
TEST_VM(LockFreeStackTest, stress) {
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;
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]);
261
ASSERT_EQ(nelements, initial_stack.length());
268
const uint stage1_threads = 2;
269
const uint stage2_threads = 2;
270
const uint nthreads = stage1_threads + stage2_threads;
271
LockFreeStackTestThread* threads[nthreads] = {};
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;
280
processed = &stage2_processed;
283
new LockFreeStackTestThread(&post, i, from, to, processed, nelements);
285
while (!threads[i]->ready()) {}
289
start_stack.prepend(*initial_stack.pop_all());
292
for (uint i = 0; i < nthreads; ++i) {
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() != nullptr) {}
305
FREE_C_HEAP_ARRAY(Element, elements);