tonyp@2472: /*
tonyp@2472:  * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
tonyp@2472:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
tonyp@2472:  *
tonyp@2472:  * This code is free software; you can redistribute it and/or modify it
tonyp@2472:  * under the terms of the GNU General Public License version 2 only, as
tonyp@2472:  * published by the Free Software Foundation.
tonyp@2472:  *
tonyp@2472:  * This code is distributed in the hope that it will be useful, but WITHOUT
tonyp@2472:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
tonyp@2472:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
tonyp@2472:  * version 2 for more details (a copy is included in the LICENSE file that
tonyp@2472:  * accompanied this code).
tonyp@2472:  *
tonyp@2472:  * You should have received a copy of the GNU General Public License version
tonyp@2472:  * 2 along with this work; if not, write to the Free Software Foundation,
tonyp@2472:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
tonyp@2472:  *
tonyp@2472:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
tonyp@2472:  * or visit www.oracle.com if you need additional information or have any
tonyp@2472:  * questions.
tonyp@2472:  *
tonyp@2472:  */
tonyp@2472: 
tonyp@2472: #include "precompiled.hpp"
tonyp@2472: #include "gc_implementation/g1/heapRegionSet.inline.hpp"
tonyp@2472: 
tonyp@2472: size_t HeapRegionSetBase::_unrealistically_long_length = 0;
tonyp@2472: 
tonyp@2472: //////////////////// HeapRegionSetBase ////////////////////
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::set_unrealistically_long_length(size_t len) {
tonyp@2472:   guarantee(_unrealistically_long_length == 0, "should only be set once");
tonyp@2472:   _unrealistically_long_length = len;
tonyp@2472: }
tonyp@2472: 
tonyp@2472: size_t HeapRegionSetBase::calculate_region_num(HeapRegion* hr) {
tonyp@2472:   assert(hr->startsHumongous(), "pre-condition");
tonyp@2472:   assert(hr->capacity() % HeapRegion::GrainBytes == 0, "invariant");
tonyp@2472:   size_t region_num = hr->capacity() >> HeapRegion::LogOfHRGrainBytes;
tonyp@2472:   assert(region_num > 0, "sanity");
tonyp@2472:   return region_num;
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::fill_in_ext_msg(hrl_ext_msg* msg, const char* message) {
tonyp@2472:   msg->append("[%s] %s "
tonyp@2472:               "ln: "SIZE_FORMAT" rn: "SIZE_FORMAT" "
tonyp@2472:               "cy: "SIZE_FORMAT" ud: "SIZE_FORMAT,
tonyp@2472:               name(), message, length(), region_num(),
tonyp@2472:               total_capacity_bytes(), total_used_bytes());
tonyp@2472:   fill_in_ext_msg_extra(msg);
tonyp@2472: }
tonyp@2472: 
tonyp@2472: bool HeapRegionSetBase::verify_region(HeapRegion* hr,
tonyp@2472:                                   HeapRegionSetBase* expected_containing_set) {
tonyp@2472:   const char* error_message = NULL;
tonyp@2472: 
tonyp@2472:   if (!regions_humongous()) {
tonyp@2472:     if (hr->isHumongous()) {
tonyp@2472:       error_message = "the region should not be humongous";
tonyp@2472:     }
tonyp@2472:   } else {
tonyp@2472:     if (!hr->isHumongous() || !hr->startsHumongous()) {
tonyp@2472:       error_message = "the region should be 'starts humongous'";
tonyp@2472:     }
tonyp@2472:   }
tonyp@2472: 
tonyp@2472:   if (!regions_empty()) {
tonyp@2472:     if (hr->is_empty()) {
tonyp@2472:       error_message = "the region should not be empty";
tonyp@2472:     }
tonyp@2472:   } else {
tonyp@2472:     if (!hr->is_empty()) {
tonyp@2472:       error_message = "the region should be empty";
tonyp@2472:     }
tonyp@2472:   }
tonyp@2472: 
tonyp@2472: #ifdef ASSERT
tonyp@2472:   // The _containing_set field is only available when ASSERT is defined.
tonyp@2472:   if (hr->containing_set() != expected_containing_set) {
tonyp@2472:     error_message = "inconsistent containing set found";
tonyp@2472:   }
tonyp@2472: #endif // ASSERT
tonyp@2472: 
tonyp@2472:   const char* extra_error_message = verify_region_extra(hr);
tonyp@2472:   if (extra_error_message != NULL) {
tonyp@2472:     error_message = extra_error_message;
tonyp@2472:   }
tonyp@2472: 
tonyp@2472:   if (error_message != NULL) {
tonyp@2472:     outputStream* out = tty;
tonyp@2472:     out->cr();
tonyp@2472:     out->print_cr("## [%s] %s", name(), error_message);
tonyp@2472:     out->print_cr("## Offending Region: "PTR_FORMAT, hr);
tonyp@2472:     out->print_cr("   "HR_FORMAT, HR_FORMAT_PARAMS(hr));
tonyp@2472: #ifdef ASSERT
tonyp@2472:     out->print_cr("   containing set: "PTR_FORMAT, hr->containing_set());
tonyp@2472: #endif // ASSERT
tonyp@2472:     out->print_cr("## Offending Region Set: "PTR_FORMAT, this);
tonyp@2472:     print_on(out);
tonyp@2472:     return false;
tonyp@2472:   } else {
tonyp@2472:     return true;
tonyp@2472:   }
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::verify() {
tonyp@2472:   // It's important that we also observe the MT safety protocol even
tonyp@2472:   // for the verification calls. If we do verification without the
tonyp@2472:   // appropriate locks and the set changes underneath our feet
tonyp@2472:   // verification might fail and send us on a wild goose chase.
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472: 
tonyp@2472:   guarantee(( is_empty() && length() == 0 && region_num() == 0 &&
tonyp@2472:               total_used_bytes() == 0 && total_capacity_bytes() == 0) ||
tonyp@2472:             (!is_empty() && length() >= 0 && region_num() >= 0 &&
tonyp@2472:               total_used_bytes() >= 0 && total_capacity_bytes() >= 0),
tonyp@2472:             hrl_ext_msg(this, "invariant"));
tonyp@2472: 
tonyp@2472:   guarantee((!regions_humongous() && region_num() == length()) ||
tonyp@2472:             ( regions_humongous() && region_num() >= length()),
tonyp@2472:             hrl_ext_msg(this, "invariant"));
tonyp@2472: 
tonyp@2472:   guarantee(!regions_empty() || total_used_bytes() == 0,
tonyp@2472:             hrl_ext_msg(this, "invariant"));
tonyp@2472: 
tonyp@2472:   guarantee(total_used_bytes() <= total_capacity_bytes(),
tonyp@2472:             hrl_ext_msg(this, "invariant"));
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::verify_start() {
tonyp@2472:   // See comment in verify() about MT safety and verification.
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472:   assert(!_verify_in_progress,
tonyp@2472:          hrl_ext_msg(this, "verification should not be in progress"));
tonyp@2472: 
tonyp@2472:   // Do the basic verification first before we do the checks over the regions.
tonyp@2472:   HeapRegionSetBase::verify();
tonyp@2472: 
tonyp@2472:   _calc_length               = 0;
tonyp@2472:   _calc_region_num           = 0;
tonyp@2472:   _calc_total_capacity_bytes = 0;
tonyp@2472:   _calc_total_used_bytes     = 0;
tonyp@2472:   _verify_in_progress        = true;
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::verify_next_region(HeapRegion* hr) {
tonyp@2472:   // See comment in verify() about MT safety and verification.
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472:   assert(_verify_in_progress,
tonyp@2472:          hrl_ext_msg(this, "verification should be in progress"));
tonyp@2472: 
tonyp@2472:   guarantee(verify_region(hr, this), hrl_ext_msg(this, "region verification"));
tonyp@2472: 
tonyp@2472:   _calc_length               += 1;
tonyp@2472:   if (!hr->isHumongous()) {
tonyp@2472:     _calc_region_num         += 1;
tonyp@2472:   } else {
tonyp@2472:     _calc_region_num         += calculate_region_num(hr);
tonyp@2472:   }
tonyp@2472:   _calc_total_capacity_bytes += hr->capacity();
tonyp@2472:   _calc_total_used_bytes     += hr->used();
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::verify_end() {
tonyp@2472:   // See comment in verify() about MT safety and verification.
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472:   assert(_verify_in_progress,
tonyp@2472:          hrl_ext_msg(this, "verification should be in progress"));
tonyp@2472: 
tonyp@2472:   guarantee(length() == _calc_length,
tonyp@2472:             hrl_err_msg("[%s] length: "SIZE_FORMAT" should be == "
tonyp@2472:                         "calc length: "SIZE_FORMAT,
tonyp@2472:                         name(), length(), _calc_length));
tonyp@2472: 
tonyp@2472:   guarantee(region_num() == _calc_region_num,
tonyp@2472:             hrl_err_msg("[%s] region num: "SIZE_FORMAT" should be == "
tonyp@2472:                         "calc region num: "SIZE_FORMAT,
tonyp@2472:                         name(), region_num(), _calc_region_num));
tonyp@2472: 
tonyp@2472:   guarantee(total_capacity_bytes() == _calc_total_capacity_bytes,
tonyp@2472:             hrl_err_msg("[%s] capacity bytes: "SIZE_FORMAT" should be == "
tonyp@2472:                         "calc capacity bytes: "SIZE_FORMAT,
tonyp@2472:                         name(),
tonyp@2472:                         total_capacity_bytes(), _calc_total_capacity_bytes));
tonyp@2472: 
tonyp@2472:   guarantee(total_used_bytes() == _calc_total_used_bytes,
tonyp@2472:             hrl_err_msg("[%s] used bytes: "SIZE_FORMAT" should be == "
tonyp@2472:                         "calc used bytes: "SIZE_FORMAT,
tonyp@2472:                         name(), total_used_bytes(), _calc_total_used_bytes));
tonyp@2472: 
tonyp@2472:   _verify_in_progress = false;
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
tonyp@2472:   out->cr();
tonyp@2472:   out->print_cr("Set: %s ("PTR_FORMAT")", name(), this);
tonyp@2472:   out->print_cr("  Region Assumptions");
tonyp@2472:   out->print_cr("    humongous         : %s", BOOL_TO_STR(regions_humongous()));
tonyp@2472:   out->print_cr("    empty             : %s", BOOL_TO_STR(regions_empty()));
tonyp@2472:   out->print_cr("  Attributes");
tonyp@2472:   out->print_cr("    length            : "SIZE_FORMAT_W(14), length());
tonyp@2472:   out->print_cr("    region num        : "SIZE_FORMAT_W(14), region_num());
tonyp@2472:   out->print_cr("    total capacity    : "SIZE_FORMAT_W(14)" bytes",
tonyp@2472:                 total_capacity_bytes());
tonyp@2472:   out->print_cr("    total used        : "SIZE_FORMAT_W(14)" bytes",
tonyp@2472:                 total_used_bytes());
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionSetBase::clear() {
tonyp@2472:   _length           = 0;
tonyp@2472:   _region_num       = 0;
tonyp@2472:   _total_used_bytes = 0;
tonyp@2472: }
tonyp@2472: 
tonyp@2472: HeapRegionSetBase::HeapRegionSetBase(const char* name)
tonyp@2472:   : _name(name), _verify_in_progress(false),
tonyp@2472:     _calc_length(0), _calc_region_num(0),
tonyp@2472:     _calc_total_capacity_bytes(0), _calc_total_used_bytes(0) { }
tonyp@2472: 
tonyp@2472: //////////////////// HeapRegionSet ////////////////////
tonyp@2472: 
tonyp@2472: void HeapRegionSet::update_from_proxy(HeapRegionSet* proxy_set) {
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472:   hrl_assert_mt_safety_ok(proxy_set);
tonyp@2472:   hrl_assert_sets_match(this, proxy_set);
tonyp@2472: 
tonyp@2472:   verify_optional();
tonyp@2472:   proxy_set->verify_optional();
tonyp@2472: 
tonyp@2472:   if (proxy_set->is_empty()) return;
tonyp@2472: 
tonyp@2472:   assert(proxy_set->length() <= _length,
tonyp@2472:          hrl_err_msg("[%s] proxy set length: "SIZE_FORMAT" "
tonyp@2472:                      "should be <= length: "SIZE_FORMAT,
tonyp@2472:                      name(), proxy_set->length(), _length));
tonyp@2472:   _length -= proxy_set->length();
tonyp@2472: 
tonyp@2472:   assert(proxy_set->region_num() <= _region_num,
tonyp@2472:          hrl_err_msg("[%s] proxy set region num: "SIZE_FORMAT" "
tonyp@2472:                      "should be <= region num: "SIZE_FORMAT,
tonyp@2472:                      name(), proxy_set->region_num(), _region_num));
tonyp@2472:   _region_num -= proxy_set->region_num();
tonyp@2472: 
tonyp@2472:   assert(proxy_set->total_used_bytes() <= _total_used_bytes,
tonyp@2472:          hrl_err_msg("[%s] proxy set used bytes: "SIZE_FORMAT" "
tonyp@2472:                      "should be <= used bytes: "SIZE_FORMAT,
tonyp@2472:                      name(), proxy_set->total_used_bytes(),
tonyp@2472:                      _total_used_bytes));
tonyp@2472:   _total_used_bytes -= proxy_set->total_used_bytes();
tonyp@2472: 
tonyp@2472:   proxy_set->clear();
tonyp@2472: 
tonyp@2472:   verify_optional();
tonyp@2472:   proxy_set->verify_optional();
tonyp@2472: }
tonyp@2472: 
tonyp@2472: //////////////////// HeapRegionLinkedList ////////////////////
tonyp@2472: 
tonyp@2472: void HeapRegionLinkedList::fill_in_ext_msg_extra(hrl_ext_msg* msg) {
tonyp@2472:   msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionLinkedList::add_as_tail(HeapRegionLinkedList* from_list) {
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472:   hrl_assert_mt_safety_ok(from_list);
tonyp@2472: 
tonyp@2472:   verify_optional();
tonyp@2472:   from_list->verify_optional();
tonyp@2472: 
tonyp@2472:   if (from_list->is_empty()) return;
tonyp@2472: 
tonyp@2472: #ifdef ASSERT
tonyp@2472:   HeapRegionLinkedListIterator iter(from_list);
tonyp@2472:   while (iter.more_available()) {
tonyp@2472:     HeapRegion* hr = iter.get_next();
tonyp@2472:     // In set_containing_set() we check that we either set the value
tonyp@2472:     // from NULL to non-NULL or vice versa to catch bugs. So, we have
tonyp@2472:     // to NULL it first before setting it to the value.
tonyp@2472:     hr->set_containing_set(NULL);
tonyp@2472:     hr->set_containing_set(this);
tonyp@2472:   }
tonyp@2472: #endif // ASSERT
tonyp@2472: 
tonyp@2472:   if (_tail != NULL) {
tonyp@2472:     assert(length() >  0 && _head != NULL, hrl_ext_msg(this, "invariant"));
tonyp@2472:     _tail->set_next(from_list->_head);
tonyp@2472:   } else {
tonyp@2472:     assert(length() == 0 && _head == NULL, hrl_ext_msg(this, "invariant"));
tonyp@2472:     _head = from_list->_head;
tonyp@2472:   }
tonyp@2472:   _tail = from_list->_tail;
tonyp@2472: 
tonyp@2472:   _length           += from_list->length();
tonyp@2472:   _region_num       += from_list->region_num();
tonyp@2472:   _total_used_bytes += from_list->total_used_bytes();
tonyp@2472:   from_list->clear();
tonyp@2472: 
tonyp@2472:   verify_optional();
tonyp@2472:   from_list->verify_optional();
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionLinkedList::remove_all() {
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472:   verify_optional();
tonyp@2472: 
tonyp@2472:   HeapRegion* curr = _head;
tonyp@2472:   while (curr != NULL) {
tonyp@2472:     hrl_assert_region_ok(this, curr, this);
tonyp@2472: 
tonyp@2472:     HeapRegion* next = curr->next();
tonyp@2472:     curr->set_next(NULL);
tonyp@2472:     curr->set_containing_set(NULL);
tonyp@2472:     curr = next;
tonyp@2472:   }
tonyp@2472:   clear();
tonyp@2472: 
tonyp@2472:   verify_optional();
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionLinkedList::remove_all_pending(size_t target_count) {
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472:   assert(target_count > 1, hrl_ext_msg(this, "pre-condition"));
tonyp@2472:   assert(!is_empty(), hrl_ext_msg(this, "pre-condition"));
tonyp@2472: 
tonyp@2472:   verify_optional();
tonyp@2472:   DEBUG_ONLY(size_t old_length = length();)
tonyp@2472: 
tonyp@2472:   HeapRegion* curr = _head;
tonyp@2472:   HeapRegion* prev = NULL;
tonyp@2472:   size_t count = 0;
tonyp@2472:   while (curr != NULL) {
tonyp@2472:     hrl_assert_region_ok(this, curr, this);
tonyp@2472:     HeapRegion* next = curr->next();
tonyp@2472: 
tonyp@2472:     if (curr->pending_removal()) {
tonyp@2472:       assert(count < target_count,
tonyp@2472:              hrl_err_msg("[%s] should not come across more regions "
tonyp@2472:                          "pending for removal than target_count: "SIZE_FORMAT,
tonyp@2472:                          name(), target_count));
tonyp@2472: 
tonyp@2472:       if (prev == NULL) {
tonyp@2472:         assert(_head == curr, hrl_ext_msg(this, "invariant"));
tonyp@2472:         _head = next;
tonyp@2472:       } else {
tonyp@2472:         assert(_head != curr, hrl_ext_msg(this, "invariant"));
tonyp@2472:         prev->set_next(next);
tonyp@2472:       }
tonyp@2472:       if (next == NULL) {
tonyp@2472:         assert(_tail == curr, hrl_ext_msg(this, "invariant"));
tonyp@2472:         _tail = prev;
tonyp@2472:       } else {
tonyp@2472:         assert(_tail != curr, hrl_ext_msg(this, "invariant"));
tonyp@2472:       }
tonyp@2472: 
tonyp@2472:       curr->set_next(NULL);
tonyp@2472:       remove_internal(curr);
tonyp@2472:       curr->set_pending_removal(false);
tonyp@2472: 
tonyp@2472:       count += 1;
tonyp@2472: 
tonyp@2472:       // If we have come across the target number of regions we can
tonyp@2472:       // just bail out. However, for debugging purposes, we can just
tonyp@2472:       // carry on iterating to make sure there are not more regions
tonyp@2472:       // tagged with pending removal.
tonyp@2472:       DEBUG_ONLY(if (count == target_count) break;)
tonyp@2472:     } else {
tonyp@2472:       prev = curr;
tonyp@2472:     }
tonyp@2472:     curr = next;
tonyp@2472:   }
tonyp@2472: 
tonyp@2472:   assert(count == target_count,
tonyp@2472:          hrl_err_msg("[%s] count: "SIZE_FORMAT" should be == "
tonyp@2472:                      "target_count: "SIZE_FORMAT, name(), count, target_count));
tonyp@2472:   assert(length() + target_count == old_length,
tonyp@2472:          hrl_err_msg("[%s] new length should be consistent "
tonyp@2472:                      "new length: "SIZE_FORMAT" old length: "SIZE_FORMAT" "
tonyp@2472:                      "target_count: "SIZE_FORMAT,
tonyp@2472:                      name(), length(), old_length, target_count));
tonyp@2472: 
tonyp@2472:   verify_optional();
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionLinkedList::verify() {
tonyp@2472:   // See comment in HeapRegionSetBase::verify() about MT safety and
tonyp@2472:   // verification.
tonyp@2472:   hrl_assert_mt_safety_ok(this);
tonyp@2472: 
tonyp@2472:   // This will also do the basic verification too.
tonyp@2472:   verify_start();
tonyp@2472: 
tonyp@2472:   HeapRegion* curr  = _head;
tonyp@2472:   HeapRegion* prev1 = NULL;
tonyp@2472:   HeapRegion* prev0 = NULL;
tonyp@2472:   size_t      count = 0;
tonyp@2472:   while (curr != NULL) {
tonyp@2472:     verify_next_region(curr);
tonyp@2472: 
tonyp@2472:     count += 1;
tonyp@2472:     guarantee(count < _unrealistically_long_length,
tonyp@2472:               hrl_err_msg("[%s] the calculated length: "SIZE_FORMAT" "
tonyp@2472:                           "seems very long, is there maybe a cycle? "
tonyp@2472:                           "curr: "PTR_FORMAT" prev0: "PTR_FORMAT" "
tonyp@2472:                           "prev1: "PTR_FORMAT" length: "SIZE_FORMAT,
tonyp@2472:                           name(), count, curr, prev0, prev1, length()));
tonyp@2472: 
tonyp@2472:     prev1 = prev0;
tonyp@2472:     prev0 = curr;
tonyp@2472:     curr  = curr->next();
tonyp@2472:   }
tonyp@2472: 
tonyp@2472:   guarantee(_tail == prev0, hrl_ext_msg(this, "post-condition"));
tonyp@2472: 
tonyp@2472:   verify_end();
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionLinkedList::clear() {
tonyp@2472:   HeapRegionSetBase::clear();
tonyp@2472:   _head = NULL;
tonyp@2472:   _tail = NULL;
tonyp@2472: }
tonyp@2472: 
tonyp@2472: void HeapRegionLinkedList::print_on(outputStream* out, bool print_contents) {
tonyp@2472:   HeapRegionSetBase::print_on(out, print_contents);
tonyp@2472:   out->print_cr("  Linking");
tonyp@2472:   out->print_cr("    head              : "PTR_FORMAT, _head);
tonyp@2472:   out->print_cr("    tail              : "PTR_FORMAT, _tail);
tonyp@2472: 
tonyp@2472:   if (print_contents) {
tonyp@2472:     out->print_cr("  Contents");
tonyp@2472:     HeapRegionLinkedListIterator iter(this);
tonyp@2472:     while (iter.more_available()) {
tonyp@2472:       HeapRegion* hr = iter.get_next();
tonyp@2472:       hr->print_on(out);
tonyp@2472:     }
tonyp@2472:   }
tonyp@2472: }