jdk-sandbox: comparison src/hotspot/share/gc/shared/oopStorage.cpp

equal deleted inserted replaced

-:b6f32c533faf
+:3021c1ad958b
 #include "logging/logStream.hpp"
 #include "memory/allocation.inline.hpp"
 #include "runtime/atomic.hpp"
 #include "runtime/globals.hpp"
 #include "runtime/handles.inline.hpp"
+#include "runtime/interfaceSupport.inline.hpp"
 #include "runtime/mutex.hpp"
 #include "runtime/mutexLocker.hpp"
 #include "runtime/orderAccess.hpp"
 #include "runtime/safepoint.hpp"
 #include "runtime/stubRoutines.hpp"
 uintx OopStorage::Block::bitmask_for_entry(const oop* ptr) const {
 return bitmask_for_index(get_index(ptr));
 }
-// A block is deletable if
+// An empty block is not yet deletable if either:
-// (1) It is empty.
+// (1) There is a release() operation currently operating on it.
-// (2) There is not a release() operation currently operating on it.
+// (2) It is in the deferred updates list.
-// (3) It is not in the deferred updates list.
+// For interaction with release(), these must follow the empty check,
-// The order of tests is important for proper interaction between release()
+// and the order of these checks is important.
-// and concurrent deletion.
+bool OopStorage::Block::is_safe_to_delete() const {
-bool OopStorage::Block::is_deletable() const {
+assert(is_empty(), "precondition");
-return (OrderAccess::load_acquire(&_allocated_bitmask) == 0) &&
+OrderAccess::loadload();
-(OrderAccess::load_acquire(&_release_refcount) == 0) &&
+return (OrderAccess::load_acquire(&_release_refcount) == 0) &&
 (OrderAccess::load_acquire(&_deferred_updates_next) == NULL);
 }
 OopStorage::Block* OopStorage::Block::deferred_updates_next() const {
 return _deferred_updates_next;
 // through dedicated fields in the blocks.  Full blocks are removed from this
 // list, though they are still present in the _active_array.  Empty blocks are
 // kept at the end of the _allocation_list, to make it easy for empty block
 // deletion to find them.
 //
-// allocate(), and delete_empty_blocks_concurrent() lock the
+// allocate(), and delete_empty_blocks() lock the
 // _allocation_mutex while performing any list and array modifications.
 //
 // allocate() and release() update a block's _allocated_bitmask using CAS
 // loops.  This prevents loss of updates even though release() performs
 // its updates without any locking.
 // and updates that block's _allocated_bitmask to indicate the entry is in
 // use.  If this makes the block full (all entries in use), the block is
 // removed from the _allocation_list so it won't be considered by future
 // allocations until some entries in it are released.
 //
-// release() is performed lock-free. release() first looks up the block for
+// release() is performed lock-free. (Note: This means it can't notify the
+// service thread of pending cleanup work.  It must be lock-free because
+// it is called in all kinds of contexts where even quite low ranked locks
+// may be held.)  release() first looks up the block for
 // the entry, using address alignment to find the enclosing block (thereby
 // avoiding iteration over the _active_array).  Once the block has been
 // determined, its _allocated_bitmask needs to be updated, and its position in
 // the _allocation_list may need to be updated.  There are two cases:
 //
 //
 // (b) Otherwise, the _allocation_list also needs to be modified.  This requires
 // locking the _allocation_mutex.  To keep the release() operation lock-free,
 // rather than updating the _allocation_list itself, it instead performs a
 // lock-free push of the block onto the _deferred_updates list.  Entries on
-// that list are processed by allocate() and delete_empty_blocks_XXX(), while
+// that list are processed by allocate() and delete_empty_blocks(), while
 // they already hold the necessary lock.  That processing makes the block's
 // list state consistent with its current _allocated_bitmask.  The block is
 // added to the _allocation_list if not already present and the bitmask is not
 // full.  The block is moved to the end of the _allocation_list if the bitmask
 // is empty, for ease of empty block deletion processing.
 oop* OopStorage::allocate() {
 MutexLockerEx ml(_allocation_mutex, Mutex::_no_safepoint_check_flag);
-// Do some deferred update processing every time we allocate.
-// Continue processing deferred updates if _allocation_list is empty,
+// Note: Without this we might never perform cleanup.  As it is,
-// in the hope that we'll get a block from that, rather than
+// cleanup is only requested here, when completing a concurrent
-// allocating a new block.
+// iteration, or when someone entirely else wakes up the service
-while (reduce_deferred_updates() && (_allocation_list.head() == NULL)) {}
+// thread, which isn't ideal.  But we can't notify in release().
+if (reduce_deferred_updates()) {
-// Use the first block in _allocation_list for the allocation.
+notify_needs_cleanup();
-Block* block = _allocation_list.head();
+}
-if (block == NULL) {
-// No available blocks; make a new one, and add to storage.
+Block* block = block_for_allocation();
-{
+if (block == NULL) return NULL; // Block allocation failed.
-MutexUnlockerEx mul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
-block = Block::new_block(this);
-}
-if (block == NULL) {
-while (_allocation_list.head() == NULL) {
-if (!reduce_deferred_updates()) {
-// Failed to make new block, no other thread made a block
-// available while the mutex was released, and didn't get
-// one from a deferred update either, so return failure.
-log_debug(oopstorage, blocks)("%s: failed block allocation", name());
-return NULL;
-}
-}
-} else {
-// Add new block to storage.
-log_debug(oopstorage, blocks)("%s: new block " PTR_FORMAT, name(), p2i(block));
-// Add new block to the _active_array, growing if needed.
-if (!_active_array->push(block)) {
-if (expand_active_array()) {
-guarantee(_active_array->push(block), "push failed after expansion");
-} else {
-log_debug(oopstorage, blocks)("%s: failed active array expand", name());
-Block::delete_block(*block);
-return NULL;
-}
-}
-// Add to end of _allocation_list.  The mutex release allowed
-// other threads to add blocks to the _allocation_list.  We prefer
-// to allocate from non-empty blocks, to allow empty blocks to
-// be deleted.
-_allocation_list.push_back(*block);
-}
-block = _allocation_list.head();
-}
-// Allocate from first block.
-assert(block != NULL, "invariant");
 assert(!block->is_full(), "invariant");
 if (block->is_empty()) {
 // Transitioning from empty to not empty.
 log_debug(oopstorage, blocks)("%s: block not empty " PTR_FORMAT, name(), p2i(block));
 }
 log_debug(oopstorage, blocks)("%s: block full " PTR_FORMAT, name(), p2i(block));
 _allocation_list.unlink(*block);
 }
 log_trace(oopstorage, ref)("%s: allocated " PTR_FORMAT, name(), p2i(result));
 return result;
+}
+bool OopStorage::try_add_block() {
+assert_lock_strong(_allocation_mutex);
+Block* block;
+{
+MutexUnlockerEx ul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
+block = Block::new_block(this);
+}
+if (block == NULL) return false;
+// Add new block to the _active_array, growing if needed.
+if (!_active_array->push(block)) {
+if (expand_active_array()) {
+guarantee(_active_array->push(block), "push failed after expansion");
+} else {
+log_debug(oopstorage, blocks)("%s: failed active array expand", name());
+Block::delete_block(*block);
+return false;
+}
+}
+// Add to end of _allocation_list.  The mutex release allowed other
+// threads to add blocks to the _allocation_list.  We prefer to
+// allocate from non-empty blocks, to allow empty blocks to be
+// deleted.  But we don't bother notifying about the empty block
+// because we're (probably) about to allocate an entry from it.
+_allocation_list.push_back(*block);
+log_debug(oopstorage, blocks)("%s: new block " PTR_FORMAT, name(), p2i(block));
+return true;
+}
+OopStorage::Block* OopStorage::block_for_allocation() {
+assert_lock_strong(_allocation_mutex);
+while (true) {
+// Use the first block in _allocation_list for the allocation.
+Block* block = _allocation_list.head();
+if (block != NULL) {
+return block;
+} else if (reduce_deferred_updates()) {
+MutexUnlockerEx ul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
+notify_needs_cleanup();
+} else if (try_add_block()) {
+block = _allocation_list.head();
+assert(block != NULL, "invariant");
+return block;
+} else if (reduce_deferred_updates()) { // Once more before failure.
+MutexUnlockerEx ul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
+notify_needs_cleanup();
+} else {
+// Attempt to add a block failed, no other thread added a block,
+// and no deferred updated added a block, then allocation failed.
+log_debug(oopstorage, blocks)("%s: failed block allocation", name());
+return NULL;
+}
+}
 }
 // Create a new, larger, active array with the same content as the
 // current array, and then replace, relinquishing the old array.
 // Return true if the array was successfully expanded, false to
 if (releasing == old_allocated) {
 ls.print_cr("%s: block empty " PTR_FORMAT, owner->name(), p2i(block));
 }
 }
-void OopStorage::Block::release_entries(uintx releasing, Block* volatile* deferred_list) {
+void OopStorage::Block::release_entries(uintx releasing, OopStorage* owner) {
 assert(releasing != 0, "preconditon");
 // Prevent empty block deletion when transitioning to empty.
 Atomic::inc(&_release_refcount);
 // Atomically update allocated bitmask.
 // Now that the bitmask has been updated, if we have a state transition
 // (updated bitmask is empty or old bitmask was full), atomically push
 // this block onto the deferred updates list.  Some future call to
 // reduce_deferred_updates will make any needed changes related to this
-// block and _allocation_list.  This deferral avoids list updates and the
+// block and _allocation_list.  This deferral avoids _allocation_list
-// associated locking here.
+// updates and the associated locking here.
 if ((releasing == old_allocated) || is_full_bitmask(old_allocated)) {
 // Log transitions.  Both transitions are possible in a single update.
 if (log_is_enabled(Debug, oopstorage, blocks)) {
 log_release_transitions(releasing, old_allocated, _owner, this);
 }
 // then someone else has made such a claim and the deferred update has not
 // yet been processed and will include our change, so we don't need to do
 // anything further.
 if (Atomic::replace_if_null(this, &_deferred_updates_next)) {
 // Successfully claimed.  Push, with self-loop for end-of-list.
-Block* head = *deferred_list;
+Block* head = owner->_deferred_updates;
 while (true) {
 _deferred_updates_next = (head == NULL) ? this : head;
-Block* fetched = Atomic::cmpxchg(this, deferred_list, head);
+Block* fetched = Atomic::cmpxchg(this, &owner->_deferred_updates, head);
 if (fetched == head) break; // Successful update.
 head = fetched;             // Retry with updated head.
 }
+owner->record_needs_cleanup();
 log_debug(oopstorage, blocks)("%s: deferred update " PTR_FORMAT,
 _owner->name(), p2i(this));
 }
 }
 // Release hold on empty block deletion.
 Atomic::dec(&_release_refcount);
 }
 // Process one available deferred update.  Returns true if one was processed.
 bool OopStorage::reduce_deferred_updates() {
-assert_locked_or_safepoint(_allocation_mutex);
+assert_lock_strong(_allocation_mutex);
 // Atomically pop a block off the list, if any available.
 // No ABA issue because this is only called by one thread at a time.
 // The atomicity is wrto pushes by release().
 Block* block = OrderAccess::load_acquire(&_deferred_updates);
 while (true) {
 block->set_deferred_updates_next(NULL); // Clear tail after updating head.
 // Ensure bitmask read after pop is complete, including clearing tail, for
 // ordering with release().  Without this, we may be processing a stale
 // bitmask state here while blocking a release() operation from recording
 // the deferred update needed for its bitmask change.
-OrderAccess::storeload();
+OrderAccess::fence();
 // Process popped block.
 uintx allocated = block->allocated_bitmask();
 // Make membership in list consistent with bitmask state.
 if ((_allocation_list.ctail() != NULL) &&
 // Move empty block to end of list, for possible deletion.
 if (is_empty_bitmask(allocated)) {
 _allocation_list.unlink(*block);
 _allocation_list.push_back(*block);
+notify_needs_cleanup();
 }
 log_debug(oopstorage, blocks)("%s: processed deferred update " PTR_FORMAT,
 name(), p2i(block));
 return true;              // Processed one pending update.
 void OopStorage::release(const oop* ptr) {
 check_release_entry(ptr);
 Block* block = find_block_or_null(ptr);
 assert(block != NULL, "%s: invalid release " PTR_FORMAT, name(), p2i(ptr));
 log_trace(oopstorage, ref)("%s: released " PTR_FORMAT, name(), p2i(ptr));
-block->release_entries(block->bitmask_for_entry(ptr), &_deferred_updates);
+block->release_entries(block->bitmask_for_entry(ptr), this);
 Atomic::dec(&_allocation_count);
 }
 void OopStorage::release(const oop* const* ptrs, size_t size) {
 size_t i = 0;
 "Duplicate entry: " PTR_FORMAT, p2i(entry));
 releasing |= entry_bitmask;
 ++count;
 }
 // Release the contiguous entries that are in block.
-block->release_entries(releasing, &_deferred_updates);
+block->release_entries(releasing, this);
 Atomic::sub(count, &_allocation_count);
 }
 }
 const char* dup_name(const char* name) {
 char* dup = NEW_C_HEAP_ARRAY(char, strlen(name) + 1, mtGC);
 strcpy(dup, name);
 return dup;
 }
+// Possible values for OopStorage::_needs_cleanup.
+const uint needs_cleanup_none = 0;     // No cleanup needed.
+const uint needs_cleanup_marked = 1;   // Requested, but no notification made.
+const uint needs_cleanup_notified = 2; // Requested and Service thread notified.
 const size_t initial_active_array_size = 8;
 OopStorage::OopStorage(const char* name,
 Mutex* allocation_mutex,
 _allocation_list(),
 _deferred_updates(NULL),
 _allocation_mutex(allocation_mutex),
 _active_mutex(active_mutex),
 _allocation_count(0),
-_concurrent_iteration_count(0)
+_concurrent_iteration_count(0),
+_needs_cleanup(needs_cleanup_none)
 {
 _active_array->increment_refcount();
 assert(_active_mutex->rank() < _allocation_mutex->rank(),
 "%s: active_mutex must have lower rank than allocation_mutex", _name);
+assert(Service_lock->rank() < _active_mutex->rank(),
+"%s: active_mutex must have higher rank than Service_lock", _name);
 assert(_active_mutex->_safepoint_check_required != Mutex::_safepoint_check_always,
 "%s: active mutex requires safepoint check", _name);
 assert(_allocation_mutex->_safepoint_check_required != Mutex::_safepoint_check_always,
 "%s: allocation mutex requires safepoint check", _name);
 }
 }
 ActiveArray::destroy(_active_array);
 FREE_C_HEAP_ARRAY(char, _name);
 }
-void OopStorage::delete_empty_blocks_safepoint() {
+// Called by service thread to check for pending work.
-assert_at_safepoint();
+bool OopStorage::needs_delete_empty_blocks() const {
-// Process any pending release updates, which may make more empty
+return Atomic::load(&_needs_cleanup) != needs_cleanup_none;
-// blocks available for deletion.
+}
-while (reduce_deferred_updates()) {}
-// Don't interfere with a concurrent iteration.
+// Record that cleanup is needed, without notifying the Service thread.
-if (_concurrent_iteration_count > 0) return;
+// Used by release(), where we can't lock even Service_lock.
-// Delete empty (and otherwise deletable) blocks from end of _allocation_list.
+void OopStorage::record_needs_cleanup() {
-for (Block* block = _allocation_list.tail();
+Atomic::cmpxchg(needs_cleanup_marked, &_needs_cleanup, needs_cleanup_none);
-(block != NULL) && block->is_deletable();
+}
-block = _allocation_list.tail()) {
-_active_array->remove(block);
+// Record that cleanup is needed, and notify the Service thread.
-_allocation_list.unlink(*block);
+void OopStorage::notify_needs_cleanup() {
-delete_empty_block(*block);
+// Avoid re-notification if already notified.
-}
+const uint notified = needs_cleanup_notified;
-}
+if (Atomic::xchg(notified, &_needs_cleanup) != notified) {
+MonitorLockerEx ml(Service_lock, Monitor::_no_safepoint_check_flag);
-void OopStorage::delete_empty_blocks_concurrent() {
+ml.notify_all();
+}
+}
+bool OopStorage::delete_empty_blocks() {
 MutexLockerEx ml(_allocation_mutex, Mutex::_no_safepoint_check_flag);
-// Other threads could be adding to the empty block count while we
-// release the mutex across the block deletions.  Set an upper bound
+// Clear the request before processing.
-// on how many blocks we'll try to release, so other threads can't
+Atomic::store(needs_cleanup_none, &_needs_cleanup);
-// cause an unbounded stay in this function.
+OrderAccess::fence();
+// Other threads could be adding to the empty block count or the
+// deferred update list while we're working.  Set an upper bound on
+// how many updates we'll process and blocks we'll try to release,
+// so other threads can't cause an unbounded stay in this function.
 size_t limit = block_count();
+if (limit == 0) return false; // Empty storage; nothing at all to do.
 for (size_t i = 0; i < limit; ++i) {
-// Additional updates might become available while we dropped the
+// Process deferred updates, which might make empty blocks available.
-// lock.  But limit number processed to limit lock duration.
+// Continue checking once deletion starts, since additional updates
-reduce_deferred_updates();
+// might become available while we're working.
+if (reduce_deferred_updates()) {
-Block* block = _allocation_list.tail();
+// Be safepoint-polite while looping.
-if ((block == NULL) || !block->is_deletable()) {
+MutexUnlockerEx ul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
-// No block to delete, so done.  There could be more pending
+ThreadBlockInVM tbiv(JavaThread::current());
-// deferred updates that could give us more work to do; deal with
+} else {
-// that in some later call, to limit lock duration here.
+Block* block = _allocation_list.tail();
-return;
+if ((block == NULL) || !block->is_empty()) {
+return false;
+} else if (!block->is_safe_to_delete()) {
+// Look for other work while waiting for block to be deletable.
+break;
+}
+// Try to delete the block.  First, try to remove from _active_array.
+{
+MutexLockerEx aml(_active_mutex, Mutex::_no_safepoint_check_flag);
+// Don't interfere with an active concurrent iteration.
+// Instead, give up immediately.  There is more work to do,
+// but don't re-notify, to avoid useless spinning of the
+// service thread.  Instead, iteration completion notifies.
+if (_concurrent_iteration_count > 0) return true;
+_active_array->remove(block);
+}
+// Remove block from _allocation_list and delete it.
+_allocation_list.unlink(*block);
+// Be safepoint-polite while deleting and looping.
+MutexUnlockerEx ul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
+delete_empty_block(*block);
+ThreadBlockInVM tbiv(JavaThread::current());
 }
+}
-{
+// Exceeded work limit or can't delete last block.  This will
-MutexLockerEx aml(_active_mutex, Mutex::_no_safepoint_check_flag);
+// cause the service thread to loop, giving other subtasks an
-// Don't interfere with a concurrent iteration.
+// opportunity to run too.  There's no need for a notification,
-if (_concurrent_iteration_count > 0) return;
+// because we are part of the service thread (unless gtesting).
-_active_array->remove(block);
+record_needs_cleanup();
-}
+return true;
-// Remove block from _allocation_list and delete it.
-_allocation_list.unlink(*block);
-// Release mutex while deleting block.
-MutexUnlockerEx ul(_allocation_mutex, Mutex::_no_safepoint_check_flag);
-delete_empty_block(*block);
-}
 }
 OopStorage::EntryStatus OopStorage::allocation_status(const oop* ptr) const {
 const Block* block = find_block_or_null(ptr);
 if (block != NULL) {
 }
 OopStorage::BasicParState::~BasicParState() {
 _storage->relinquish_block_array(_active_array);
 update_concurrent_iteration_count(-1);
+if (_concurrent) {
+// We may have deferred some work.
+const_cast<OopStorage*>(_storage)->notify_needs_cleanup();
+}
 }
 void OopStorage::BasicParState::update_concurrent_iteration_count(int value) {
 if (_concurrent) {
 MutexLockerEx ml(_storage->_active_mutex, Mutex::_no_safepoint_check_flag);

changeset 52421	3021c1ad958b
parent 52037	d2a6c3cbc110
child 54623	1126f0607c70