1/*
2 * Copyright (c) 2018, 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
25#include "precompiled.hpp"
26#include "gc/shared/ptrQueue.hpp"
27#include "memory/allocation.hpp"
28#include "runtime/interfaceSupport.inline.hpp"
29#include "runtime/orderAccess.hpp"
30#include "runtime/semaphore.inline.hpp"
31#include "runtime/thread.hpp"
32#include "utilities/globalCounter.inline.hpp"
33#include "utilities/globalDefinitions.hpp"
34#include "utilities/ostream.hpp"
35#include "threadHelper.inline.hpp"
36#include "unittest.hpp"
37
38class BufferNode::TestSupport : AllStatic {
39public:
40 static bool try_transfer_pending(Allocator* allocator) {
41 return allocator->try_transfer_pending();
42 }
43
44 class CompletedList;
45 class AllocatorThread;
46 class ProcessorThread;
47};
48
49typedef BufferNode::TestSupport::CompletedList CompletedList;
50typedef BufferNode::TestSupport::AllocatorThread AllocatorThread;
51typedef BufferNode::TestSupport::ProcessorThread ProcessorThread;
52
53// Some basic testing of BufferNode::Allocator.
54TEST_VM(PtrQueueBufferAllocatorTest, test) {
55 const size_t buffer_size = 256;
56 BufferNode::Allocator allocator("Test Buffer Allocator", buffer_size);
57 ASSERT_EQ(buffer_size, allocator.buffer_size());
58
59 // Allocate some new nodes for use in testing.
60 BufferNode* nodes[10] = {};
61 const size_t node_count = ARRAY_SIZE(nodes);
62 for (size_t i = 0; i < node_count; ++i) {
63 ASSERT_EQ(0u, allocator.free_count());
64 nodes[i] = allocator.allocate();
65 ASSERT_EQ((BufferNode*)NULL, nodes[i]->next());
66 }
67
68 // Release the nodes, adding them to the allocator's free list.
69 for (size_t i = 0; i < node_count; ++i) {
70 allocator.release(nodes[i]);
71 }
72 ASSERT_TRUE(BufferNode::TestSupport::try_transfer_pending(&allocator));
73 ASSERT_EQ(node_count, allocator.free_count());
74 for (size_t i = 0; i < node_count; ++i) {
75 if (i == 0) {
76 ASSERT_EQ((BufferNode*)NULL, nodes[i]->next());
77 } else {
78 ASSERT_EQ(nodes[i - 1], nodes[i]->next());
79 }
80 }
81
82 // Allocate nodes from the free list.
83 for (size_t i = 0; i < node_count; ++i) {
84 size_t j = node_count - i;
85 ASSERT_EQ(nodes[j - 1], allocator.allocate());
86 }
87 ASSERT_EQ(0u, allocator.free_count());
88
89 // Release nodes back to the free list.
90 for (size_t i = 0; i < node_count; ++i) {
91 allocator.release(nodes[i]);
92 }
93 ASSERT_TRUE(BufferNode::TestSupport::try_transfer_pending(&allocator));
94 ASSERT_EQ(node_count, allocator.free_count());
95
96 // Destroy some nodes in the free list.
97 // We don't have a way to verify destruction, but we can at
98 // least verify we don't crash along the way.
99 size_t count = allocator.free_count();
100 ASSERT_EQ(count, allocator.reduce_free_list(count));
101 // destroy allocator.
102}
103
104// Stress test with lock-free allocator and completed buffer list.
105// Completed buffer list pop avoids ABA by also being in a critical
106// section that is synchronized by the allocator's release.
107
108class BufferNode::TestSupport::CompletedList {
109 BufferNode::Stack _completed_list;
110
111public:
112 CompletedList() : _completed_list() {}
113
114 ~CompletedList() {
115 assert(_completed_list.empty(), "completed list not empty");
116 }
117
118 void push(BufferNode* node) {
119 assert(node != NULL, "precondition");
120 _completed_list.push(*node);
121 }
122
123 BufferNode* pop() {
124 GlobalCounter::CriticalSection cs(Thread::current());
125 return _completed_list.pop();
126 }
127};
128
129// Simulate a mutator thread, allocating buffers and adding them to
130// the completed buffer list.
131class BufferNode::TestSupport::AllocatorThread : public JavaTestThread {
132 BufferNode::Allocator* _allocator;
133 CompletedList* _cbl;
134 volatile size_t* _total_allocations;
135 volatile bool* _continue_running;
136 size_t _allocations;
137
138public:
139 AllocatorThread(Semaphore* post,
140 BufferNode::Allocator* allocator,
141 CompletedList* cbl,
142 volatile size_t* total_allocations,
143 volatile bool* continue_running) :
144 JavaTestThread(post),
145 _allocator(allocator),
146 _cbl(cbl),
147 _total_allocations(total_allocations),
148 _continue_running(continue_running),
149 _allocations(0)
150 {}
151
152 virtual void main_run() {
153 while (OrderAccess::load_acquire(_continue_running)) {
154 BufferNode* node = _allocator->allocate();
155 _cbl->push(node);
156 ++_allocations;
157 ThreadBlockInVM tbiv(this); // Safepoint check.
158 }
159 tty->print_cr("allocations: " SIZE_FORMAT, _allocations);
160 Atomic::add(_allocations, _total_allocations);
161 }
162};
163
164// Simulate a GC thread, taking buffers from the completed buffer list
165// and returning them to the allocator.
166class BufferNode::TestSupport::ProcessorThread : public JavaTestThread {
167 BufferNode::Allocator* _allocator;
168 CompletedList* _cbl;
169 volatile bool* _continue_running;
170
171public:
172 ProcessorThread(Semaphore* post,
173 BufferNode::Allocator* allocator,
174 CompletedList* cbl,
175 volatile bool* continue_running) :
176 JavaTestThread(post),
177 _allocator(allocator),
178 _cbl(cbl),
179 _continue_running(continue_running)
180 {}
181
182 virtual void main_run() {
183 while (true) {
184 BufferNode* node = _cbl->pop();
185 if (node != NULL) {
186 _allocator->release(node);
187 } else if (!OrderAccess::load_acquire(_continue_running)) {
188 return;
189 }
190 ThreadBlockInVM tbiv(this); // Safepoint check.
191 }
192 }
193};
194
195static void run_test(BufferNode::Allocator* allocator, CompletedList* cbl) {
196 const uint nthreads = 4;
197 const uint milliseconds_to_run = 1000;
198
199 Semaphore post;
200 volatile size_t total_allocations = 0;
201 volatile bool allocator_running = true;
202 volatile bool processor_running = true;
203
204 ProcessorThread* proc_threads[nthreads] = {};
205 for (uint i = 0; i < nthreads; ++i) {
206 proc_threads[i] = new ProcessorThread(&post,
207 allocator,
208 cbl,
209 &processor_running);
210 proc_threads[i]->doit();
211 }
212
213 AllocatorThread* alloc_threads[nthreads] = {};
214 for (uint i = 0; i < nthreads; ++i) {
215 alloc_threads[i] = new AllocatorThread(&post,
216 allocator,
217 cbl,
218 &total_allocations,
219 &allocator_running);
220 alloc_threads[i]->doit();
221 }
222
223 JavaThread* this_thread = JavaThread::current();
224 tty->print_cr("Stressing allocator for %u ms", milliseconds_to_run);
225 {
226 ThreadInVMfromNative invm(this_thread);
227 os::sleep(this_thread, milliseconds_to_run, true);
228 }
229 OrderAccess::release_store(&allocator_running, false);
230 for (uint i = 0; i < nthreads; ++i) {
231 ThreadInVMfromNative invm(this_thread);
232 post.wait_with_safepoint_check(this_thread);
233 }
234 OrderAccess::release_store(&processor_running, false);
235 for (uint i = 0; i < nthreads; ++i) {
236 ThreadInVMfromNative invm(this_thread);
237 post.wait_with_safepoint_check(this_thread);
238 }
239 ASSERT_TRUE(BufferNode::TestSupport::try_transfer_pending(allocator));
240 tty->print_cr("total allocations: " SIZE_FORMAT, total_allocations);
241 tty->print_cr("allocator free count: " SIZE_FORMAT, allocator->free_count());
242}
243
244const size_t buffer_size = 1024;
245
246TEST_VM(PtrQueueBufferAllocatorTest, stress_free_list_allocator) {
247 BufferNode::Allocator allocator("Test Allocator", buffer_size);
248 CompletedList completed;
249 run_test(&allocator, &completed);
250}
251