1 /*
2 * Copyright (c) 2018, 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/oopStorage.inline.hpp"
27 #include "gc/shared/oopStorageParState.inline.hpp"
28 #include "logging/log.hpp"
29 #include "logging/logStream.hpp"
30 #include "memory/allocation.inline.hpp"
31 #include "runtime/atomic.hpp"
32 #include "runtime/globals.hpp"
33 #include "runtime/handles.inline.hpp"
34 #include "runtime/mutex.hpp"
35 #include "runtime/mutexLocker.hpp"
36 #include "runtime/orderAccess.hpp"
37 #include "runtime/safepoint.hpp"
38 #include "runtime/stubRoutines.hpp"
39 #include "runtime/thread.hpp"
40 #include "utilities/align.hpp"
41 #include "utilities/count_trailing_zeros.hpp"
42 #include "utilities/debug.hpp"
43 #include "utilities/globalDefinitions.hpp"
44 #include "utilities/macros.hpp"
45 #include "utilities/ostream.hpp"
46
47 OopStorage::AllocationListEntry::AllocationListEntry() : _prev(NULL), _next(NULL) {}
48
49 OopStorage::AllocationListEntry::~AllocationListEntry() {
50 assert(_prev == NULL, "deleting attached block");
51 assert(_next == NULL, "deleting attached block");
52 }
53
54 OopStorage::AllocationList::AllocationList() : _head(NULL), _tail(NULL) {}
55
56 OopStorage::AllocationList::~AllocationList() {
57 // ~OopStorage() empties its lists before destroying them.
58 assert(_head == NULL, "deleting non-empty block list");
59 assert(_tail == NULL, "deleting non-empty block list");
60 }
61
62 void OopStorage::AllocationList::push_front(const Block& block) {
63 const Block* old = _head;
64 if (old == NULL) {
65 assert(_tail == NULL, "invariant");
66 _head = _tail = █
67 } else {
68 block.allocation_list_entry()._next = old;
69 old->allocation_list_entry()._prev = █
70 _head = █
71 }
72 }
73
74 void OopStorage::AllocationList::push_back(const Block& block) {
75 const Block* old = _tail;
76 if (old == NULL) {
77 assert(_head == NULL, "invariant");
78 _head = _tail = █
79 } else {
80 old->allocation_list_entry()._next = █
81 block.allocation_list_entry()._prev = old;
82 _tail = █
83 }
84 }
85
86 void OopStorage::AllocationList::unlink(const Block& block) {
87 const AllocationListEntry& block_entry = block.allocation_list_entry();
88 const Block* prev_blk = block_entry._prev;
89 const Block* next_blk = block_entry._next;
90 block_entry._prev = NULL;
91 block_entry._next = NULL;
92 if ((prev_blk == NULL) && (next_blk == NULL)) {
93 assert(_head == &block, "invariant");
94 assert(_tail == &block, "invariant");
95 _head = _tail = NULL;
96 } else if (prev_blk == NULL) {
97 assert(_head == &block, "invariant");
98 next_blk->allocation_list_entry()._prev = NULL;
99 _head = next_blk;
100 } else if (next_blk == NULL) {
101 assert(_tail == &block, "invariant");
102 prev_blk->allocation_list_entry()._next = NULL;
103 _tail = prev_blk;
104 } else {
105 next_blk->allocation_list_entry()._prev = prev_blk;
106 prev_blk->allocation_list_entry()._next = next_blk;
107 }
108 }
109
110 OopStorage::ActiveArray::ActiveArray(size_t size) :
111 _size(size),
112 _block_count(0),
113 _refcount(0)
114 {}
115
116 OopStorage::ActiveArray::~ActiveArray() {
117 assert(_refcount == 0, "precondition");
118 }
119
120 OopStorage::ActiveArray* OopStorage::ActiveArray::create(size_t size, AllocFailType alloc_fail) {
121 size_t size_in_bytes = blocks_offset() + sizeof(Block*) * size;
122 void* mem = NEW_C_HEAP_ARRAY3(char, size_in_bytes, mtGC, CURRENT_PC, alloc_fail);
123 if (mem == NULL) return NULL;
124 return new (mem) ActiveArray(size);
125 }
126
127 void OopStorage::ActiveArray::destroy(ActiveArray* ba) {
128 ba->~ActiveArray();
129 FREE_C_HEAP_ARRAY(char, ba);
130 }
131
132 size_t OopStorage::ActiveArray::size() const {
133 return _size;
134 }
135
136 size_t OopStorage::ActiveArray::block_count() const {
137 return _block_count;
138 }
139
140 size_t OopStorage::ActiveArray::block_count_acquire() const {
141 return OrderAccess::load_acquire(&_block_count);
142 }
143
144 void OopStorage::ActiveArray::increment_refcount() const {
145 int new_value = Atomic::add(1, &_refcount);
146 assert(new_value >= 1, "negative refcount %d", new_value - 1);
147 }
148
149 bool OopStorage::ActiveArray::decrement_refcount() const {
150 int new_value = Atomic::sub(1, &_refcount);
151 assert(new_value >= 0, "negative refcount %d", new_value);
152 return new_value == 0;
153 }
154
155 bool OopStorage::ActiveArray::push(Block* block) {
156 size_t index = _block_count;
157 if (index < _size) {
158 block->set_active_index(index);
159 *block_ptr(index) = block;
160 // Use a release_store to ensure all the setup is complete before
161 // making the block visible.
162 OrderAccess::release_store(&_block_count, index + 1);
163 return true;
164 } else {
165 return false;
166 }
167 }
168
169 void OopStorage::ActiveArray::remove(Block* block) {
170 assert(_block_count > 0, "array is empty");
171 size_t index = block->active_index();
172 assert(*block_ptr(index) == block, "block not present");
173 size_t last_index = _block_count - 1;
174 Block* last_block = *block_ptr(last_index);
175 last_block->set_active_index(index);
176 *block_ptr(index) = last_block;
177 _block_count = last_index;
178 }
179
180 void OopStorage::ActiveArray::copy_from(const ActiveArray* from) {
181 assert(_block_count == 0, "array must be empty");
182 size_t count = from->_block_count;
183 assert(count <= _size, "precondition");
184 Block* const* from_ptr = from->block_ptr(0);
185 Block** to_ptr = block_ptr(0);
186 for (size_t i = 0; i < count; ++i) {
187 Block* block = *from_ptr++;
188 assert(block->active_index() == i, "invariant");
189 *to_ptr++ = block;
190 }
191 _block_count = count;
192 }
193
194 // Blocks start with an array of BitsPerWord oop entries. That array
195 // is divided into conceptual BytesPerWord sections of BitsPerByte
196 // entries. Blocks are allocated aligned on section boundaries, for
197 // the convenience of mapping from an entry to the containing block;
198 // see block_for_ptr(). Aligning on section boundary rather than on
199 // the full _data wastes a lot less space, but makes for a bit more
200 // work in block_for_ptr().
201
202 const unsigned section_size = BitsPerByte;
203 const unsigned section_count = BytesPerWord;
204 const unsigned block_alignment = sizeof(oop) * section_size;
205
206 OopStorage::Block::Block(const OopStorage* owner, void* memory) :
207 _data(),
208 _allocated_bitmask(0),
209 _owner(owner),
210 _memory(memory),
211 _active_index(0),
212 _allocation_list_entry(),
213 _deferred_updates_next(NULL),
214 _release_refcount(0)
215 {
216 STATIC_ASSERT(_data_pos == 0);
217 STATIC_ASSERT(section_size * section_count == ARRAY_SIZE(_data));
218 assert(offset_of(Block, _data) == _data_pos, "invariant");
219 assert(owner != NULL, "NULL owner");
220 assert(is_aligned(this, block_alignment), "misaligned block");
221 }
222
223 OopStorage::Block::~Block() {
224 assert(_release_refcount == 0, "deleting block while releasing");
225 assert(_deferred_updates_next == NULL, "deleting block with deferred update");
226 // Clear fields used by block_for_ptr and entry validation, which
227 // might help catch bugs. Volatile to prevent dead-store elimination.
228 const_cast<uintx volatile&>(_allocated_bitmask) = 0;
229 const_cast<OopStorage* volatile&>(_owner) = NULL;
230 }
231
232 size_t OopStorage::Block::allocation_size() {
233 // _data must be first member, so aligning Block aligns _data.
234 STATIC_ASSERT(_data_pos == 0);
235 return sizeof(Block) + block_alignment - sizeof(void*);
236 }
237
238 size_t OopStorage::Block::allocation_alignment_shift() {
239 return exact_log2(block_alignment);
240 }
241
242 inline bool is_full_bitmask(uintx bitmask) { return ~bitmask == 0; }
243 inline bool is_empty_bitmask(uintx bitmask) { return bitmask == 0; }
244
245 bool OopStorage::Block::is_full() const {
246 return is_full_bitmask(allocated_bitmask());
247 }
248
249 bool OopStorage::Block::is_empty() const {
250 return is_empty_bitmask(allocated_bitmask());
251 }
252
253 uintx OopStorage::Block::bitmask_for_entry(const oop* ptr) const {
254 return bitmask_for_index(get_index(ptr));
255 }
256
257 // A block is deletable if
258 // (1) It is empty.
259 // (2) There is not a release() operation currently operating on it.
260 // (3) It is not in the deferred updates list.
261 // The order of tests is important for proper interaction between release()
262 // and concurrent deletion.
263 bool OopStorage::Block::is_deletable() const {
264 return (OrderAccess::load_acquire(&_allocated_bitmask) == 0) &&
265 (OrderAccess::load_acquire(&_release_refcount) == 0) &&
266 (OrderAccess::load_acquire(&_deferred_updates_next) == NULL);
267 }
268
269 OopStorage::Block* OopStorage::Block::deferred_updates_next() const {
270 return _deferred_updates_next;
271 }
272
273 void OopStorage::Block::set_deferred_updates_next(Block* block) {
274 _deferred_updates_next = block;
275 }
276
277 bool OopStorage::Block::contains(const oop* ptr) const {
278 const oop* base = get_pointer(0);
279 return (base <= ptr) && (ptr < (base + ARRAY_SIZE(_data)));
280 }
281
282 size_t OopStorage::Block::active_index() const {
283 return _active_index;
284 }
285
286 void OopStorage::Block::set_active_index(size_t index) {
287 _active_index = index;
288 }
289
290 size_t OopStorage::Block::active_index_safe(const Block* block) {
291 STATIC_ASSERT(sizeof(intptr_t) == sizeof(block->_active_index));
292 assert(CanUseSafeFetchN(), "precondition");
293 return SafeFetchN((intptr_t*)&block->_active_index, 0);
294 }
295
296 unsigned OopStorage::Block::get_index(const oop* ptr) const {
297 assert(contains(ptr), PTR_FORMAT " not in block " PTR_FORMAT, p2i(ptr), p2i(this));
298 return static_cast<unsigned>(ptr - get_pointer(0));
299 }
300
301 oop* OopStorage::Block::allocate() {
302 // Use CAS loop because release may change bitmask outside of lock.
303 uintx allocated = allocated_bitmask();
304 while (true) {
305 assert(!is_full_bitmask(allocated), "attempt to allocate from full block");
306 unsigned index = count_trailing_zeros(~allocated);
307 uintx new_value = allocated | bitmask_for_index(index);
308 uintx fetched = Atomic::cmpxchg(new_value, &_allocated_bitmask, allocated);
309 if (fetched == allocated) {
310 return get_pointer(index); // CAS succeeded; return entry for index.
311 }
312 allocated = fetched; // CAS failed; retry with latest value.
313 }
314 }
315
316 OopStorage::Block* OopStorage::Block::new_block(const OopStorage* owner) {
317 // _data must be first member: aligning block => aligning _data.
318 STATIC_ASSERT(_data_pos == 0);
319 size_t size_needed = allocation_size();
320 void* memory = NEW_C_HEAP_ARRAY_RETURN_NULL(char, size_needed, mtGC);
321 if (memory == NULL) {
322 return NULL;
323 }
324 void* block_mem = align_up(memory, block_alignment);
325 assert(sizeof(Block) + pointer_delta(block_mem, memory, 1) <= size_needed,
326 "allocated insufficient space for aligned block");
327 return ::new (block_mem) Block(owner, memory);
328 }
329
330 void OopStorage::Block::delete_block(const Block& block) {
331 void* memory = block._memory;
332 block.Block::~Block();
333 FREE_C_HEAP_ARRAY(char, memory);
334 }
335
336 // This can return a false positive if ptr is not contained by some
337 // block. For some uses, it is a precondition that ptr is valid,
338 // e.g. contained in some block in owner's _active_array. Other uses
339 // require additional validation of the result.
340 OopStorage::Block*
341 OopStorage::Block::block_for_ptr(const OopStorage* owner, const oop* ptr) {
342 assert(CanUseSafeFetchN(), "precondition");
343 STATIC_ASSERT(_data_pos == 0);
344 // Const-ness of ptr is not related to const-ness of containing block.
345 // Blocks are allocated section-aligned, so get the containing section.
346 oop* section_start = align_down(const_cast<oop*>(ptr), block_alignment);
347 // Start with a guess that the containing section is the last section,
348 // so the block starts section_count-1 sections earlier.
349 oop* section = section_start - (section_size * (section_count - 1));
350 // Walk up through the potential block start positions, looking for
351 // the owner in the expected location. If we're below the actual block
352 // start position, the value at the owner position will be some oop
353 // (possibly NULL), which can never match the owner.
354 intptr_t owner_addr = reinterpret_cast<intptr_t>(owner);
355 for (unsigned i = 0; i < section_count; ++i, section += section_size) {
356 Block* candidate = reinterpret_cast<Block*>(section);
357 intptr_t* candidate_owner_addr
358 = reinterpret_cast<intptr_t*>(&candidate->_owner);
359 if (SafeFetchN(candidate_owner_addr, 0) == owner_addr) {
360 return candidate;
361 }
362 }
363 return NULL;
364 }
365
366 //////////////////////////////////////////////////////////////////////////////
367 // Allocation
368 //
369 // Allocation involves the _allocation_list, which contains a subset of the
370 // blocks owned by a storage object. This is a doubly-linked list, linked
371 // through dedicated fields in the blocks. Full blocks are removed from this
372 // list, though they are still present in the _active_array. Empty blocks are
373 // kept at the end of the _allocation_list, to make it easy for empty block
374 // deletion to find them.
375 //
376 // allocate(), and delete_empty_blocks_concurrent() lock the
377 // _allocation_mutex while performing any list and array modifications.
378 //
379 // allocate() and release() update a block's _allocated_bitmask using CAS
380 // loops. This prevents loss of updates even though release() performs
381 // its updates without any locking.
382 //
383 // allocate() obtains the entry from the first block in the _allocation_list,
384 // and updates that block's _allocated_bitmask to indicate the entry is in
385 // use. If this makes the block full (all entries in use), the block is
386 // removed from the _allocation_list so it won't be considered by future
387 // allocations until some entries in it are released.
388 //
389 // release() is performed lock-free. release() first looks up the block for
390 // the entry, using address alignment to find the enclosing block (thereby
391 // avoiding iteration over the _active_array). Once the block has been
392 // determined, its _allocated_bitmask needs to be updated, and its position in
393 // the _allocation_list may need to be updated. There are two cases:
394 //
395 // (a) If the block is neither full nor would become empty with the release of
396 // the entry, only its _allocated_bitmask needs to be updated. But if the CAS
397 // update fails, the applicable case may change for the retry.
398 //
399 // (b) Otherwise, the _allocation_list also needs to be modified. This requires
400 // locking the _allocation_mutex. To keep the release() operation lock-free,
401 // rather than updating the _allocation_list itself, it instead performs a
402 // lock-free push of the block onto the _deferred_updates list. Entries on
403 // that list are processed by allocate() and delete_empty_blocks_XXX(), while
404 // they already hold the necessary lock. That processing makes the block's
405 // list state consistent with its current _allocated_bitmask. The block is
406 // added to the _allocation_list if not already present and the bitmask is not
407 // full. The block is moved to the end of the _allocation_list if the bitmask
408 // is empty, for ease of empty block deletion processing.
409
410 oop* OopStorage::allocate() {
411 MutexLockerEx ml(_allocation_mutex, Mutex::_no_safepoint_check_flag);
412 // Do some deferred update processing every time we allocate.
413 // Continue processing deferred updates if _allocation_list is empty,
414 // in the hope that we'll get a block from that, rather than
415 // allocating a new block.
416 while (reduce_deferred_updates() && (_allocation_list.head() == NULL)) {}
417
418 // Use the first block in _allocation_list for the allocation.
419 Block* block = _allocation_list.head();
420 if (block == NULL) {
421 // No available blocks; make a new one, and add to storage.
422 {
423 MutexUnlockerEx mul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
424 block = Block::new_block(this);
425 }
426 if (block == NULL) {
427 while (_allocation_list.head() == NULL) {
428 if (!reduce_deferred_updates()) {
429 // Failed to make new block, no other thread made a block
430 // available while the mutex was released, and didn't get
431 // one from a deferred update either, so return failure.
432 log_info(oopstorage, ref)("%s: failed block allocation", name());
433 return NULL;
434 }
435 }
436 } else {
437 // Add new block to storage.
438 log_info(oopstorage, blocks)("%s: new block " PTR_FORMAT, name(), p2i(block));
439
440 // Add new block to the _active_array, growing if needed.
441 if (!_active_array->push(block)) {
442 if (expand_active_array()) {
443 guarantee(_active_array->push(block), "push failed after expansion");
444 } else {
445 log_info(oopstorage, blocks)("%s: failed active array expand", name());
446 Block::delete_block(*block);
447 return NULL;
448 }
449 }
450 // Add to end of _allocation_list. The mutex release allowed
451 // other threads to add blocks to the _allocation_list. We prefer
452 // to allocate from non-empty blocks, to allow empty blocks to
453 // be deleted.
454 _allocation_list.push_back(*block);
455 }
456 block = _allocation_list.head();
457 }
458 // Allocate from first block.
459 assert(block != NULL, "invariant");
460 assert(!block->is_full(), "invariant");
461 if (block->is_empty()) {
462 // Transitioning from empty to not empty.
463 log_debug(oopstorage, blocks)("%s: block not empty " PTR_FORMAT, name(), p2i(block));
464 }
465 oop* result = block->allocate();
466 assert(result != NULL, "allocation failed");
467 assert(!block->is_empty(), "postcondition");
468 Atomic::inc(&_allocation_count); // release updates outside lock.
469 if (block->is_full()) {
470 // Transitioning from not full to full.
471 // Remove full blocks from consideration by future allocates.
472 log_debug(oopstorage, blocks)("%s: block full " PTR_FORMAT, name(), p2i(block));
473 _allocation_list.unlink(*block);
474 }
475 log_info(oopstorage, ref)("%s: allocated " PTR_FORMAT, name(), p2i(result));
476 return result;
477 }
478
479 // Create a new, larger, active array with the same content as the
480 // current array, and then replace, relinquishing the old array.
481 // Return true if the array was successfully expanded, false to
482 // indicate allocation failure.
483 bool OopStorage::expand_active_array() {
484 assert_lock_strong(_allocation_mutex);
485 ActiveArray* old_array = _active_array;
486 size_t new_size = 2 * old_array->size();
487 log_info(oopstorage, blocks)("%s: expand active array " SIZE_FORMAT,
488 name(), new_size);
489 ActiveArray* new_array = ActiveArray::create(new_size, AllocFailStrategy::RETURN_NULL);
490 if (new_array == NULL) return false;
491 new_array->copy_from(old_array);
492 replace_active_array(new_array);
493 relinquish_block_array(old_array);
494 return true;
495 }
496
497 // Make new_array the _active_array. Increments new_array's refcount
498 // to account for the new reference. The assignment is atomic wrto
499 // obtain_active_array; once this function returns, it is safe for the
500 // caller to relinquish the old array.
501 void OopStorage::replace_active_array(ActiveArray* new_array) {
502 // Caller has the old array that is the current value of _active_array.
503 // Update new_array refcount to account for the new reference.
504 new_array->increment_refcount();
505 // Install new_array, ensuring its initialization is complete first.
506 OrderAccess::release_store(&_active_array, new_array);
507 // Wait for any readers that could read the old array from _active_array.
508 // Can't use GlobalCounter here, because this is called from allocate(),
509 // which may be called in the scope of a GlobalCounter critical section
510 // when inserting a StringTable entry.
511 _protect_active.synchronize();
512 // All obtain critical sections that could see the old array have
513 // completed, having incremented the refcount of the old array. The
514 // caller can now safely relinquish the old array.
515 }
516
517 // Atomically (wrto replace_active_array) get the active array and
518 // increment its refcount. This provides safe access to the array,
519 // even if an allocate operation expands and replaces the value of
520 // _active_array. The caller must relinquish the array when done
521 // using it.
522 OopStorage::ActiveArray* OopStorage::obtain_active_array() const {
523 SingleWriterSynchronizer::CriticalSection cs(&_protect_active);
524 ActiveArray* result = OrderAccess::load_acquire(&_active_array);
525 result->increment_refcount();
526 return result;
527 }
528
529 // Decrement refcount of array and destroy if refcount is zero.
530 void OopStorage::relinquish_block_array(ActiveArray* array) const {
531 if (array->decrement_refcount()) {
532 assert(array != _active_array, "invariant");
533 ActiveArray::destroy(array);
534 }
535 }
536
537 class OopStorage::WithActiveArray : public StackObj {
538 const OopStorage* _storage;
539 ActiveArray* _active_array;
540
541 public:
542 WithActiveArray(const OopStorage* storage) :
543 _storage(storage),
544 _active_array(storage->obtain_active_array())
545 {}
546
547 ~WithActiveArray() {
548 _storage->relinquish_block_array(_active_array);
549 }
550
551 ActiveArray& active_array() const {
552 return *_active_array;
553 }
554 };
555
556 OopStorage::Block* OopStorage::find_block_or_null(const oop* ptr) const {
557 assert(ptr != NULL, "precondition");
558 return Block::block_for_ptr(this, ptr);
559 }
560
561 static void log_release_transitions(uintx releasing,
562 uintx old_allocated,
563 const OopStorage* owner,
564 const void* block) {
565 Log(oopstorage, blocks) log;
566 LogStream ls(log.debug());
567 if (is_full_bitmask(old_allocated)) {
568 ls.print_cr("%s: block not full " PTR_FORMAT, owner->name(), p2i(block));
569 }
570 if (releasing == old_allocated) {
571 ls.print_cr("%s: block empty " PTR_FORMAT, owner->name(), p2i(block));
572 }
573 }
574
575 void OopStorage::Block::release_entries(uintx releasing, Block* volatile* deferred_list) {
576 assert(releasing != 0, "preconditon");
577 // Prevent empty block deletion when transitioning to empty.
578 Atomic::inc(&_release_refcount);
579
580 // Atomically update allocated bitmask.
581 uintx old_allocated = _allocated_bitmask;
582 while (true) {
583 assert((releasing & ~old_allocated) == 0, "releasing unallocated entries");
584 uintx new_value = old_allocated ^ releasing;
585 uintx fetched = Atomic::cmpxchg(new_value, &_allocated_bitmask, old_allocated);
586 if (fetched == old_allocated) break; // Successful update.
587 old_allocated = fetched; // Retry with updated bitmask.
588 }
589
590 // Now that the bitmask has been updated, if we have a state transition
591 // (updated bitmask is empty or old bitmask was full), atomically push
592 // this block onto the deferred updates list. Some future call to
593 // reduce_deferred_updates will make any needed changes related to this
594 // block and _allocation_list. This deferral avoids list updates and the
595 // associated locking here.
596 if ((releasing == old_allocated) || is_full_bitmask(old_allocated)) {
597 // Log transitions. Both transitions are possible in a single update.
598 if (log_is_enabled(Debug, oopstorage, blocks)) {
599 log_release_transitions(releasing, old_allocated, _owner, this);
600 }
601 // Attempt to claim responsibility for adding this block to the deferred
602 // list, by setting the link to non-NULL by self-looping. If this fails,
603 // then someone else has made such a claim and the deferred update has not
604 // yet been processed and will include our change, so we don't need to do
605 // anything further.
606 if (Atomic::replace_if_null(this, &_deferred_updates_next)) {
607 // Successfully claimed. Push, with self-loop for end-of-list.
608 Block* head = *deferred_list;
609 while (true) {
610 _deferred_updates_next = (head == NULL) ? this : head;
611 Block* fetched = Atomic::cmpxchg(this, deferred_list, head);
612 if (fetched == head) break; // Successful update.
613 head = fetched; // Retry with updated head.
614 }
615 log_debug(oopstorage, blocks)("%s: deferred update " PTR_FORMAT,
616 _owner->name(), p2i(this));
617 }
618 }
619 // Release hold on empty block deletion.
620 Atomic::dec(&_release_refcount);
621 }
622
623 // Process one available deferred update. Returns true if one was processed.
624 bool OopStorage::reduce_deferred_updates() {
625 assert_locked_or_safepoint(_allocation_mutex);
626 // Atomically pop a block off the list, if any available.
627 // No ABA issue because this is only called by one thread at a time.
628 // The atomicity is wrto pushes by release().
629 Block* block = OrderAccess::load_acquire(&_deferred_updates);
630 while (true) {
631 if (block == NULL) return false;
632 // Try atomic pop of block from list.
633 Block* tail = block->deferred_updates_next();
634 if (block == tail) tail = NULL; // Handle self-loop end marker.
635 Block* fetched = Atomic::cmpxchg(tail, &_deferred_updates, block);
636 if (fetched == block) break; // Update successful.
637 block = fetched; // Retry with updated block.
638 }
639 block->set_deferred_updates_next(NULL); // Clear tail after updating head.
640 // Ensure bitmask read after pop is complete, including clearing tail, for
641 // ordering with release(). Without this, we may be processing a stale
642 // bitmask state here while blocking a release() operation from recording
643 // the deferred update needed for its bitmask change.
644 OrderAccess::storeload();
645 // Process popped block.
646 uintx allocated = block->allocated_bitmask();
647
648 // Make membership in list consistent with bitmask state.
649 if ((_allocation_list.ctail() != NULL) &&
650 ((_allocation_list.ctail() == block) ||
651 (_allocation_list.next(*block) != NULL))) {
652 // Block is in the _allocation_list.
653 assert(!is_full_bitmask(allocated), "invariant");
654 } else if (!is_full_bitmask(allocated)) {
655 // Block is not in the _allocation_list, but now should be.
656 _allocation_list.push_front(*block);
657 } // Else block is full and not in list, which is correct.
658
659 // Move empty block to end of list, for possible deletion.
660 if (is_empty_bitmask(allocated)) {
661 _allocation_list.unlink(*block);
662 _allocation_list.push_back(*block);
663 }
664
665 log_debug(oopstorage, blocks)("%s: processed deferred update " PTR_FORMAT,
666 name(), p2i(block));
667 return true; // Processed one pending update.
668 }
669
670 inline void check_release_entry(const oop* entry) {
671 assert(entry != NULL, "Releasing NULL");
672 assert(*entry == NULL, "Releasing uncleared entry: " PTR_FORMAT, p2i(entry));
673 }
674
675 void OopStorage::release(const oop* ptr) {
676 check_release_entry(ptr);
677 Block* block = find_block_or_null(ptr);
678 assert(block != NULL, "%s: invalid release " PTR_FORMAT, name(), p2i(ptr));
679 log_info(oopstorage, ref)("%s: released " PTR_FORMAT, name(), p2i(ptr));
680 block->release_entries(block->bitmask_for_entry(ptr), &_deferred_updates);
681 Atomic::dec(&_allocation_count);
682 }
683
684 void OopStorage::release(const oop* const* ptrs, size_t size) {
685 size_t i = 0;
686 while (i < size) {
687 check_release_entry(ptrs[i]);
688 Block* block = find_block_or_null(ptrs[i]);
689 assert(block != NULL, "%s: invalid release " PTR_FORMAT, name(), p2i(ptrs[i]));
690 log_info(oopstorage, ref)("%s: released " PTR_FORMAT, name(), p2i(ptrs[i]));
691 size_t count = 0;
692 uintx releasing = 0;
693 for ( ; i < size; ++i) {
694 const oop* entry = ptrs[i];
695 check_release_entry(entry);
696 // If entry not in block, finish block and resume outer loop with entry.
697 if (!block->contains(entry)) break;
698 // Add entry to releasing bitmap.
699 log_info(oopstorage, ref)("%s: released " PTR_FORMAT, name(), p2i(entry));
700 uintx entry_bitmask = block->bitmask_for_entry(entry);
701 assert((releasing & entry_bitmask) == 0,
702 "Duplicate entry: " PTR_FORMAT, p2i(entry));
703 releasing |= entry_bitmask;
704 ++count;
705 }
706 // Release the contiguous entries that are in block.
707 block->release_entries(releasing, &_deferred_updates);
708 Atomic::sub(count, &_allocation_count);
709 }
710 }
711
712 const char* dup_name(const char* name) {
713 char* dup = NEW_C_HEAP_ARRAY(char, strlen(name) + 1, mtGC);
714 strcpy(dup, name);
715 return dup;
716 }
717
718 const size_t initial_active_array_size = 8;
719
720 OopStorage::OopStorage(const char* name,
721 Mutex* allocation_mutex,
722 Mutex* active_mutex) :
723 _name(dup_name(name)),
724 _active_array(ActiveArray::create(initial_active_array_size)),
725 _allocation_list(),
726 _deferred_updates(NULL),
727 _allocation_mutex(allocation_mutex),
728 _active_mutex(active_mutex),
729 _allocation_count(0),
730 _concurrent_iteration_count(0)
731 {
732 _active_array->increment_refcount();
733 assert(_active_mutex->rank() < _allocation_mutex->rank(),
734 "%s: active_mutex must have lower rank than allocation_mutex", _name);
735 assert(_active_mutex->_safepoint_check_required != Mutex::_safepoint_check_always,
736 "%s: active mutex requires safepoint check", _name);
737 assert(_allocation_mutex->_safepoint_check_required != Mutex::_safepoint_check_always,
738 "%s: allocation mutex requires safepoint check", _name);
739 }
740
741 void OopStorage::delete_empty_block(const Block& block) {
742 assert(block.is_empty(), "discarding non-empty block");
743 log_info(oopstorage, blocks)("%s: delete empty block " PTR_FORMAT, name(), p2i(&block));
744 Block::delete_block(block);
745 }
746
747 OopStorage::~OopStorage() {
748 Block* block;
749 while ((block = _deferred_updates) != NULL) {
750 _deferred_updates = block->deferred_updates_next();
751 block->set_deferred_updates_next(NULL);
752 }
753 while ((block = _allocation_list.head()) != NULL) {
754 _allocation_list.unlink(*block);
755 }
756 bool unreferenced = _active_array->decrement_refcount();
757 assert(unreferenced, "deleting storage while _active_array is referenced");
758 for (size_t i = _active_array->block_count(); 0 < i; ) {
759 block = _active_array->at(--i);
760 Block::delete_block(*block);
761 }
762 ActiveArray::destroy(_active_array);
763 FREE_C_HEAP_ARRAY(char, _name);
764 }
765
766 void OopStorage::delete_empty_blocks_safepoint() {
767 assert_at_safepoint();
768 // Process any pending release updates, which may make more empty
769 // blocks available for deletion.
770 while (reduce_deferred_updates()) {}
771 // Don't interfere with a concurrent iteration.
772 if (_concurrent_iteration_count > 0) return;
773 // Delete empty (and otherwise deletable) blocks from end of _allocation_list.
774 for (Block* block = _allocation_list.tail();
775 (block != NULL) && block->is_deletable();
776 block = _allocation_list.tail()) {
777 _active_array->remove(block);
778 _allocation_list.unlink(*block);
779 delete_empty_block(*block);
780 }
781 }
782
783 void OopStorage::delete_empty_blocks_concurrent() {
784 MutexLockerEx ml(_allocation_mutex, Mutex::_no_safepoint_check_flag);
785 // Other threads could be adding to the empty block count while we
786 // release the mutex across the block deletions. Set an upper bound
787 // on how many blocks we'll try to release, so other threads can't
788 // cause an unbounded stay in this function.
789 size_t limit = block_count();
790
791 for (size_t i = 0; i < limit; ++i) {
792 // Additional updates might become available while we dropped the
793 // lock. But limit number processed to limit lock duration.
794 reduce_deferred_updates();
795
796 Block* block = _allocation_list.tail();
797 if ((block == NULL) || !block->is_deletable()) {
798 // No block to delete, so done. There could be more pending
799 // deferred updates that could give us more work to do; deal with
800 // that in some later call, to limit lock duration here.
801 return;
802 }
803
804 {
805 MutexLockerEx aml(_active_mutex, Mutex::_no_safepoint_check_flag);
806 // Don't interfere with a concurrent iteration.
807 if (_concurrent_iteration_count > 0) return;
808 _active_array->remove(block);
809 }
810 // Remove block from _allocation_list and delete it.
811 _allocation_list.unlink(*block);
812 // Release mutex while deleting block.
813 MutexUnlockerEx ul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
814 delete_empty_block(*block);
815 }
816 }
817
818 OopStorage::EntryStatus OopStorage::allocation_status(const oop* ptr) const {
819 const Block* block = find_block_or_null(ptr);
820 if (block != NULL) {
821 // Prevent block deletion and _active_array modification.
822 MutexLockerEx ml(_allocation_mutex, Mutex::_no_safepoint_check_flag);
823 // Block could be a false positive, so get index carefully.
824 size_t index = Block::active_index_safe(block);
825 if ((index < _active_array->block_count()) &&
826 (block == _active_array->at(index)) &&
827 block->contains(ptr)) {
828 if ((block->allocated_bitmask() & block->bitmask_for_entry(ptr)) != 0) {
829 return ALLOCATED_ENTRY;
830 } else {
831 return UNALLOCATED_ENTRY;
832 }
833 }
834 }
835 return INVALID_ENTRY;
836 }
837
838 size_t OopStorage::allocation_count() const {
839 return _allocation_count;
840 }
841
842 size_t OopStorage::block_count() const {
843 WithActiveArray wab(this);
844 // Count access is racy, but don't care.
845 return wab.active_array().block_count();
846 }
847
848 size_t OopStorage::total_memory_usage() const {
849 size_t total_size = sizeof(OopStorage);
850 total_size += strlen(name()) + 1;
851 total_size += sizeof(ActiveArray);
852 WithActiveArray wab(this);
853 const ActiveArray& blocks = wab.active_array();
854 // Count access is racy, but don't care.
855 total_size += blocks.block_count() * Block::allocation_size();
856 total_size += blocks.size() * sizeof(Block*);
857 return total_size;
858 }
859
860 // Parallel iteration support
861
862 uint OopStorage::BasicParState::default_estimated_thread_count(bool concurrent) {
863 uint configured = concurrent ? ConcGCThreads : ParallelGCThreads;
864 return MAX2(1u, configured); // Never estimate zero threads.
865 }
866
867 OopStorage::BasicParState::BasicParState(const OopStorage* storage,
868 uint estimated_thread_count,
869 bool concurrent) :
870 _storage(storage),
871 _active_array(_storage->obtain_active_array()),
872 _block_count(0), // initialized properly below
873 _next_block(0),
874 _estimated_thread_count(estimated_thread_count),
875 _concurrent(concurrent)
876 {
877 assert(estimated_thread_count > 0, "estimated thread count must be positive");
878 update_concurrent_iteration_count(1);
879 // Get the block count *after* iteration state updated, so concurrent
880 // empty block deletion is suppressed and can't reduce the count. But
881 // ensure the count we use was written after the block with that count
882 // was fully initialized; see ActiveArray::push.
883 _block_count = _active_array->block_count_acquire();
884 }
885
886 OopStorage::BasicParState::~BasicParState() {
887 _storage->relinquish_block_array(_active_array);
888 update_concurrent_iteration_count(-1);
889 }
890
891 void OopStorage::BasicParState::update_concurrent_iteration_count(int value) {
892 if (_concurrent) {
893 MutexLockerEx ml(_storage->_active_mutex, Mutex::_no_safepoint_check_flag);
894 _storage->_concurrent_iteration_count += value;
895 assert(_storage->_concurrent_iteration_count >= 0, "invariant");
896 }
897 }
898
899 bool OopStorage::BasicParState::claim_next_segment(IterationData* data) {
900 data->_processed += data->_segment_end - data->_segment_start;
901 size_t start = OrderAccess::load_acquire(&_next_block);
902 if (start >= _block_count) {
903 return finish_iteration(data); // No more blocks available.
904 }
905 // Try to claim several at a time, but not *too* many. We want to
906 // avoid deciding there are many available and selecting a large
907 // quantity, get delayed, and then end up claiming most or all of
908 // the remaining largish amount of work, leaving nothing for other
909 // threads to do. But too small a step can lead to contention
910 // over _next_block, esp. when the work per block is small.
911 size_t max_step = 10;
912 size_t remaining = _block_count - start;
913 size_t step = MIN2(max_step, 1 + (remaining / _estimated_thread_count));
914 // Atomic::add with possible overshoot. This can perform better
915 // than a CAS loop on some platforms when there is contention.
916 // We can cope with the uncertainty by recomputing start/end from
917 // the result of the add, and dealing with potential overshoot.
918 size_t end = Atomic::add(step, &_next_block);
919 // _next_block may have changed, so recompute start from result of add.
920 start = end - step;
921 // _next_block may have changed so much that end has overshot.
922 end = MIN2(end, _block_count);
923 // _next_block may have changed so much that even start has overshot.
924 if (start < _block_count) {
925 // Record claimed segment for iteration.
926 data->_segment_start = start;
927 data->_segment_end = end;
928 return true; // Success.
929 } else {
930 // No more blocks to claim.
931 return finish_iteration(data);
932 }
933 }
934
935 bool OopStorage::BasicParState::finish_iteration(const IterationData* data) const {
936 log_debug(oopstorage, blocks, stats)
937 ("Parallel iteration on %s: blocks = " SIZE_FORMAT
938 ", processed = " SIZE_FORMAT " (%2.f%%)",
939 _storage->name(), _block_count, data->_processed,
940 percent_of(data->_processed, _block_count));
941 return false;
942 }
943
944 const char* OopStorage::name() const { return _name; }
945
946 #ifndef PRODUCT
947
948 void OopStorage::print_on(outputStream* st) const {
949 size_t allocations = _allocation_count;
950 size_t blocks = _active_array->block_count();
951
952 double data_size = section_size * section_count;
953 double alloc_percentage = percent_of((double)allocations, blocks * data_size);
954
955 st->print("%s: " SIZE_FORMAT " entries in " SIZE_FORMAT " blocks (%.F%%), " SIZE_FORMAT " bytes",
956 name(), allocations, blocks, alloc_percentage, total_memory_usage());
957 if (_concurrent_iteration_count > 0) {
958 st->print(", concurrent iteration active");
959 }
960 }
961
962 #endif // !PRODUCT