1 /*
2 * Copyright (c) 2001, 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 "logging/log.hpp"
28 #include "memory/allocation.hpp"
29 #include "memory/allocation.inline.hpp"
30 #include "runtime/atomic.hpp"
31 #include "runtime/mutex.hpp"
32 #include "runtime/mutexLocker.hpp"
33 #include "runtime/orderAccess.hpp"
34 #include "runtime/thread.inline.hpp"
35 #include "utilities/globalCounter.inline.hpp"
36
37 #include <new>
38
39 PtrQueue::PtrQueue(PtrQueueSet* qset, bool permanent, bool active) :
40 _qset(qset),
41 _active(active),
42 _permanent(permanent),
43 _index(0),
44 _capacity_in_bytes(0),
45 _buf(NULL),
46 _lock(NULL)
47 {}
48
49 PtrQueue::~PtrQueue() {
50 assert(_permanent || (_buf == NULL), "queue must be flushed before delete");
51 }
52
53 void PtrQueue::flush_impl() {
54 if (_buf != NULL) {
55 BufferNode* node = BufferNode::make_node_from_buffer(_buf, index());
56 if (is_empty()) {
57 // No work to do.
58 qset()->deallocate_buffer(node);
59 } else {
60 qset()->enqueue_completed_buffer(node);
61 }
62 _buf = NULL;
63 set_index(0);
64 }
65 }
66
67
68 void PtrQueue::enqueue_known_active(void* ptr) {
69 while (_index == 0) {
70 handle_zero_index();
71 }
72
73 assert(_buf != NULL, "postcondition");
74 assert(index() > 0, "postcondition");
75 assert(index() <= capacity(), "invariant");
76 _index -= _element_size;
77 _buf[index()] = ptr;
78 }
79
80 BufferNode* BufferNode::allocate(size_t size) {
81 size_t byte_size = size * sizeof(void*);
82 void* data = NEW_C_HEAP_ARRAY(char, buffer_offset() + byte_size, mtGC);
83 return new (data) BufferNode;
84 }
85
86 void BufferNode::deallocate(BufferNode* node) {
87 node->~BufferNode();
88 FREE_C_HEAP_ARRAY(char, node);
89 }
90
91 BufferNode::Allocator::Allocator(const char* name, size_t buffer_size) :
92 _buffer_size(buffer_size),
93 _pending_list(),
94 _free_list(),
95 _pending_count(0),
96 _free_count(0),
97 _transfer_lock(false)
98 {
99 strncpy(_name, name, sizeof(_name));
100 _name[sizeof(_name) - 1] = '\0';
101 }
102
103 BufferNode::Allocator::~Allocator() {
104 delete_list(_free_list.pop_all());
105 delete_list(_pending_list.pop_all());
106 }
107
108 void BufferNode::Allocator::delete_list(BufferNode* list) {
109 while (list != NULL) {
110 BufferNode* next = list->next();
111 DEBUG_ONLY(list->set_next(NULL);)
112 BufferNode::deallocate(list);
113 list = next;
114 }
115 }
116
117 size_t BufferNode::Allocator::free_count() const {
118 return Atomic::load(&_free_count);
119 }
120
121 const size_t size_zero = 0;
122 const size_t size_one = 1;
123
124 BufferNode* BufferNode::Allocator::allocate() {
125 BufferNode* node;
126 {
127 // Protect against ABA; see release().
128 GlobalCounter::CriticalSection cs(Thread::current());
129 node = _free_list.pop();
130 }
131 if (node == NULL) {
132 node = BufferNode::allocate(_buffer_size);
133 } else {
134 // Decrement count after getting buffer from free list. This, along
135 // with incrementing count before adding to free list, ensures count
136 // never underflows.
137 size_t count = Atomic::sub(size_one, &_free_count);
138 assert((count + 1) != 0, "_free_count underflow");
139 }
140 return node;
141 }
142
143 // To solve the ABA problem for lock-free stack pop, allocate does the
144 // pop inside a critical section, and release synchronizes on the
145 // critical sections before adding to the _free_list. But we don't
146 // want to make every release have to do a synchronize. Instead, we
147 // initially place released nodes on the _pending_list, and transfer
148 // them to the _free_list in batches. Only one transfer at a time is
149 // permitted, with a lock bit to control access to that phase. A
150 // transfer takes all the nodes from the _pending_list, synchronizes on
151 // the _free_list pops, and then adds the former pending nodes to the
152 // _free_list. While that's happening, other threads might be adding
153 // other nodes to the _pending_list, to be dealt with by some later
154 // transfer.
155 void BufferNode::Allocator::release(BufferNode* node) {
156 assert(node != NULL, "precondition");
157 assert(node->next() == NULL, "precondition");
158
159 // Desired minimum transfer batch size. There is relatively little
160 // importance to the specific number. It shouldn't be too big, else
161 // we're wasting space when the release rate is low. If the release
162 // rate is high, we might accumulate more than this before being
163 // able to start a new transfer, but that's okay. Also note that
164 // the allocation rate and the release rate are going to be fairly
165 // similar, due to how the buffers are used.
166 const size_t trigger_transfer = 10;
167
168 // Add to pending list. Update count first so no underflow in transfer.
169 size_t pending_count = Atomic::add(size_one, &_pending_count);
170 _pending_list.push(*node);
171 if (pending_count > trigger_transfer) {
172 try_transfer_pending();
173 }
174 }
175
176 // Try to transfer nodes from _pending_list to _free_list, with a
177 // synchronization delay for any in-progress pops from the _free_list,
178 // to solve ABA there. Return true if performed a (possibly empty)
179 // transfer, false if blocked from doing so by some other thread's
180 // in-progress transfer.
181 bool BufferNode::Allocator::try_transfer_pending() {
182 // Attempt to claim the lock.
183 if (Atomic::load(&_transfer_lock) || // Skip CAS if likely to fail.
184 Atomic::cmpxchg(true, &_transfer_lock, false)) {
185 return false;
186 }
187 // Have the lock; perform the transfer.
188
189 // Claim all the pending nodes.
190 BufferNode* first = _pending_list.pop_all();
191 if (first != NULL) {
192 // Prepare to add the claimed nodes, and update _pending_count.
193 BufferNode* last = first;
194 size_t count = 1;
195 for (BufferNode* next = first->next(); next != NULL; next = next->next()) {
196 last = next;
197 ++count;
198 }
199 Atomic::sub(count, &_pending_count);
200
201 // Wait for any in-progress pops, to avoid ABA for them.
202 GlobalCounter::write_synchronize();
203
204 // Add synchronized nodes to _free_list.
205 // Update count first so no underflow in allocate().
206 Atomic::add(count, &_free_count);
207 _free_list.prepend(*first, *last);
208 log_trace(gc, ptrqueue, freelist)
209 ("Transferred %s pending to free: " SIZE_FORMAT, name(), count);
210 }
211 OrderAccess::release_store(&_transfer_lock, false);
212 return true;
213 }
214
215 size_t BufferNode::Allocator::reduce_free_list(size_t remove_goal) {
216 try_transfer_pending();
217 size_t removed = 0;
218 for ( ; removed < remove_goal; ++removed) {
219 BufferNode* node = _free_list.pop();
220 if (node == NULL) break;
221 BufferNode::deallocate(node);
222 }
223 size_t new_count = Atomic::sub(removed, &_free_count);
224 log_debug(gc, ptrqueue, freelist)
225 ("Reduced %s free list by " SIZE_FORMAT " to " SIZE_FORMAT,
226 name(), removed, new_count);
227 return removed;
228 }
229
230 PtrQueueSet::PtrQueueSet(bool notify_when_complete) :
231 _allocator(NULL),
232 _cbl_mon(NULL),
233 _completed_buffers_head(NULL),
234 _completed_buffers_tail(NULL),
235 _n_completed_buffers(0),
236 _process_completed_buffers_threshold(ProcessCompletedBuffersThresholdNever),
237 _process_completed_buffers(false),
238 _notify_when_complete(notify_when_complete),
239 _max_completed_buffers(MaxCompletedBuffersUnlimited),
240 _completed_buffers_padding(0),
241 _all_active(false)
242 {}
243
244 PtrQueueSet::~PtrQueueSet() {
245 // There are presently only a couple (derived) instances ever
246 // created, and they are permanent, so no harm currently done by
247 // doing nothing here.
248 }
249
250 void PtrQueueSet::initialize(Monitor* cbl_mon,
251 BufferNode::Allocator* allocator) {
252 assert(cbl_mon != NULL && allocator != NULL, "Init order issue?");
253 _cbl_mon = cbl_mon;
254 _allocator = allocator;
255 }
256
257 void** PtrQueueSet::allocate_buffer() {
258 BufferNode* node = _allocator->allocate();
259 return BufferNode::make_buffer_from_node(node);
260 }
261
262 void PtrQueueSet::deallocate_buffer(BufferNode* node) {
263 _allocator->release(node);
264 }
265
266 void PtrQueue::handle_zero_index() {
267 assert(index() == 0, "precondition");
268
269 // This thread records the full buffer and allocates a new one (while
270 // holding the lock if there is one).
271 if (_buf != NULL) {
272 if (!should_enqueue_buffer()) {
273 assert(index() > 0, "the buffer can only be re-used if it's not full");
274 return;
275 }
276
277 if (_lock) {
278 assert(_lock->owned_by_self(), "Required.");
279
280 BufferNode* node = BufferNode::make_node_from_buffer(_buf, index());
281 _buf = NULL; // clear shared _buf field
282
283 qset()->enqueue_completed_buffer(node);
284 assert(_buf == NULL, "multiple enqueuers appear to be racing");
285 } else {
286 BufferNode* node = BufferNode::make_node_from_buffer(_buf, index());
287 if (qset()->process_or_enqueue_completed_buffer(node)) {
288 // Recycle the buffer. No allocation.
289 assert(_buf == BufferNode::make_buffer_from_node(node), "invariant");
290 assert(capacity() == qset()->buffer_size(), "invariant");
291 reset();
292 return;
293 }
294 }
295 }
296 // Set capacity in case this is the first allocation.
297 set_capacity(qset()->buffer_size());
298 // Allocate a new buffer.
299 _buf = qset()->allocate_buffer();
300 reset();
301 }
302
303 bool PtrQueueSet::process_or_enqueue_completed_buffer(BufferNode* node) {
304 if (Thread::current()->is_Java_thread()) {
305 // If the number of buffers exceeds the limit, make this Java
306 // thread do the processing itself. We don't lock to access
307 // buffer count or padding; it is fine to be imprecise here. The
308 // add of padding could overflow, which is treated as unlimited.
309 size_t limit = _max_completed_buffers + _completed_buffers_padding;
310 if ((_n_completed_buffers > limit) && (limit >= _max_completed_buffers)) {
311 if (mut_process_buffer(node)) {
312 // Successfully processed; return true to allow buffer reuse.
313 return true;
314 }
315 }
316 }
317 // The buffer will be enqueued. The caller will have to get a new one.
318 enqueue_completed_buffer(node);
319 return false;
320 }
321
322 void PtrQueueSet::enqueue_completed_buffer(BufferNode* cbn) {
323 MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
324 cbn->set_next(NULL);
325 if (_completed_buffers_tail == NULL) {
326 assert(_completed_buffers_head == NULL, "Well-formedness");
327 _completed_buffers_head = cbn;
328 _completed_buffers_tail = cbn;
329 } else {
330 _completed_buffers_tail->set_next(cbn);
331 _completed_buffers_tail = cbn;
332 }
333 _n_completed_buffers++;
334
335 if (!_process_completed_buffers &&
336 (_n_completed_buffers > _process_completed_buffers_threshold)) {
337 _process_completed_buffers = true;
338 if (_notify_when_complete) {
339 _cbl_mon->notify();
340 }
341 }
342 assert_completed_buffers_list_len_correct_locked();
343 }
344
345 BufferNode* PtrQueueSet::get_completed_buffer(size_t stop_at) {
346 MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
347
348 if (_n_completed_buffers <= stop_at) {
349 return NULL;
350 }
351
352 assert(_n_completed_buffers > 0, "invariant");
353 assert(_completed_buffers_head != NULL, "invariant");
354 assert(_completed_buffers_tail != NULL, "invariant");
355
356 BufferNode* bn = _completed_buffers_head;
357 _n_completed_buffers--;
358 _completed_buffers_head = bn->next();
359 if (_completed_buffers_head == NULL) {
360 assert(_n_completed_buffers == 0, "invariant");
361 _completed_buffers_tail = NULL;
362 _process_completed_buffers = false;
363 }
364 assert_completed_buffers_list_len_correct_locked();
365 bn->set_next(NULL);
366 return bn;
367 }
368
369 void PtrQueueSet::abandon_completed_buffers() {
370 BufferNode* buffers_to_delete = NULL;
371 {
372 MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
373 buffers_to_delete = _completed_buffers_head;
374 _completed_buffers_head = NULL;
375 _completed_buffers_tail = NULL;
376 _n_completed_buffers = 0;
377 _process_completed_buffers = false;
378 }
379 while (buffers_to_delete != NULL) {
380 BufferNode* bn = buffers_to_delete;
381 buffers_to_delete = bn->next();
382 bn->set_next(NULL);
383 deallocate_buffer(bn);
384 }
385 }
386
387 #ifdef ASSERT
388
389 void PtrQueueSet::assert_completed_buffers_list_len_correct_locked() {
390 assert_lock_strong(_cbl_mon);
391 size_t n = 0;
392 for (BufferNode* bn = _completed_buffers_head; bn != NULL; bn = bn->next()) {
393 ++n;
394 }
395 assert(n == _n_completed_buffers,
396 "Completed buffer length is wrong: counted: " SIZE_FORMAT
397 ", expected: " SIZE_FORMAT, n, _n_completed_buffers);
398 }
399
400 #endif // ASSERT
401
402 // Merge lists of buffers. Notify the processing threads.
403 // The source queue is emptied as a result. The queues
404 // must share the monitor.
405 void PtrQueueSet::merge_bufferlists(PtrQueueSet *src) {
406 assert(_cbl_mon == src->_cbl_mon, "Should share the same lock");
407 MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
408 if (_completed_buffers_tail == NULL) {
409 assert(_completed_buffers_head == NULL, "Well-formedness");
410 _completed_buffers_head = src->_completed_buffers_head;
411 _completed_buffers_tail = src->_completed_buffers_tail;
412 } else {
413 assert(_completed_buffers_head != NULL, "Well formedness");
414 if (src->_completed_buffers_head != NULL) {
415 _completed_buffers_tail->set_next(src->_completed_buffers_head);
416 _completed_buffers_tail = src->_completed_buffers_tail;
417 }
418 }
419 _n_completed_buffers += src->_n_completed_buffers;
420
421 src->_n_completed_buffers = 0;
422 src->_completed_buffers_head = NULL;
423 src->_completed_buffers_tail = NULL;
424 src->_process_completed_buffers = false;
425
426 assert(_completed_buffers_head == NULL && _completed_buffers_tail == NULL ||
427 _completed_buffers_head != NULL && _completed_buffers_tail != NULL,
428 "Sanity");
429 assert_completed_buffers_list_len_correct_locked();
430 }
431
432 void PtrQueueSet::notify_if_necessary() {
433 MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
434 if (_n_completed_buffers > _process_completed_buffers_threshold) {
435 _process_completed_buffers = true;
436 if (_notify_when_complete)
437 _cbl_mon->notify();
438 }
439 }