jdk

1
/*
2
 * Copyright (c) 2019, 2024, 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

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() == nullptr);
86
  ASSERT_TRUE(stack.top() == nullptr);
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 != nullptr);
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() == nullptr);
111
}
112

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);
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() == nullptr);
126
  ASSERT_TRUE(stack.top() == nullptr);
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 != nullptr);
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() == nullptr);
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() == nullptr);
145
  ASSERT_TRUE(other_stack.pop() == nullptr);
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 != nullptr);
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() == nullptr);
161
}
162

163
TEST_F(LockFreeStackTestBasics, two_stacks) {
164
  TestStack1 stack1;
165
  ASSERT_TRUE(stack1.pop() == nullptr);
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 == nullptr) 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 != nullptr);
186
    ASSERT_EQ(&elements[i], e);
187
    ASSERT_EQ(i, e->id());
188

189
    Element* e1 = stack1.pop();
190
    ASSERT_TRUE(e1 != nullptr);
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() == nullptr);
199
  ASSERT_TRUE(stack1.pop() == nullptr);
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
    Atomic::release_store_fence(&_ready, true);
230
    while (true) {
231
      Element* e = _from->pop();
232
      if (e != nullptr) {
233
        _to->push(*e);
234
        Atomic::inc(_processed);
235
        ++_local_processed;
236
      } else if (Atomic::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 Atomic::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() != nullptr) {}
304

305
  FREE_C_HEAP_ARRAY(Element, elements);
306
}
307