1 /*
   2  * Copyright (c) 2011, 2012, 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_implementation/g1/heapRegionRemSet.hpp"
  27 #include "gc_implementation/g1/heapRegionSet.inline.hpp"
  28 
  29 uint FreeRegionList::_unrealistically_long_length = 0;
  30 
  31 //////////////////// HeapRegionSetBase ////////////////////
  32 
  33 void HeapRegionSetBase::fill_in_ext_msg(hrs_ext_msg* msg, const char* message) {
  34   msg->append("[%s] %s ln: %u cy: "SIZE_FORMAT,
  35               name(), message, length(), total_capacity_bytes());
  36   fill_in_ext_msg_extra(msg);
  37 }
  38 
  39 #ifndef PRODUCT
  40 void HeapRegionSetBase::verify_region(HeapRegion* hr) {
  41   assert(hr->containing_set() == this, err_msg("Inconsistent containing set for %u", hr->hrs_index()));
  42   assert(!hr->is_young(), err_msg("Adding young region %u", hr->hrs_index())); // currently we don't use these sets for young regions
  43   assert(hr->isHumongous() == regions_humongous(), err_msg("Wrong humongous state for region %u and set %s", hr->hrs_index(), name()));
  44   assert(hr->is_empty() == regions_empty(), err_msg("Wrong empty state for region %u and set %s", hr->hrs_index(), name()));
  45   assert(hr->rem_set()->verify_ready_for_par_iteration(), err_msg("Wrong iteration state %u", hr->hrs_index()));
  46 }
  47 #endif
  48 
  49 void HeapRegionSetBase::verify() {
  50   // It's important that we also observe the MT safety protocol even
  51   // for the verification calls. If we do verification without the
  52   // appropriate locks and the set changes underneath our feet
  53   // verification might fail and send us on a wild goose chase.
  54   check_mt_safety();
  55 
  56   guarantee(( is_empty() && length() == 0 && total_capacity_bytes() == 0) ||
  57             (!is_empty() && length() >= 0 && total_capacity_bytes() >= 0),
  58             hrs_ext_msg(this, "invariant"));
  59 }
  60 
  61 void HeapRegionSetBase::verify_start() {
  62   // See comment in verify() about MT safety and verification.
  63   check_mt_safety();
  64   assert(!_verify_in_progress,
  65          hrs_ext_msg(this, "verification should not be in progress"));
  66 
  67   // Do the basic verification first before we do the checks over the regions.
  68   HeapRegionSetBase::verify();
  69 
  70   _verify_in_progress        = true;
  71 }
  72 
  73 void HeapRegionSetBase::verify_end() {
  74   // See comment in verify() about MT safety and verification.
  75   check_mt_safety();
  76   assert(_verify_in_progress,
  77          hrs_ext_msg(this, "verification should be in progress"));
  78 
  79   _verify_in_progress = false;
  80 }
  81 
  82 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
  83   out->cr();
  84   out->print_cr("Set: %s ("PTR_FORMAT")", name(), this);
  85   out->print_cr("  Region Assumptions");
  86   out->print_cr("    humongous         : %s", BOOL_TO_STR(regions_humongous()));
  87   out->print_cr("    empty             : %s", BOOL_TO_STR(regions_empty()));
  88   out->print_cr("  Attributes");
  89   out->print_cr("    length            : %14u", length());
  90   out->print_cr("    total capacity    : "SIZE_FORMAT_W(14)" bytes",
  91                 total_capacity_bytes());
  92 }
  93 
  94 HeapRegionSetBase::HeapRegionSetBase(const char* name, bool humongous, bool empty, HRSMtSafeChecker* mt_safety_checker)
  95   : _name(name), _verify_in_progress(false),
  96     _is_humongous(humongous), _is_empty(empty), _mt_safety_checker(mt_safety_checker),
  97     _count()
  98 { }
  99 
 100 //////////////////// HeapRegionSet ////////////////////
 101 
 102 void FreeRegionList::set_unrealistically_long_length(uint len) {
 103   guarantee(_unrealistically_long_length == 0, "should only be set once");
 104   _unrealistically_long_length = len;
 105 }
 106 
 107 void FreeRegionList::fill_in_ext_msg_extra(hrs_ext_msg* msg) {
 108   msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());
 109 }
 110 
 111 void FreeRegionList::add_as_head(FreeRegionList* from_list) {
 112   check_mt_safety();
 113   from_list->check_mt_safety();
 114 
 115   verify_optional();
 116   from_list->verify_optional();
 117 
 118   if (from_list->is_empty()) return;
 119 
 120 #ifdef ASSERT
 121   FreeRegionListIterator iter(from_list);
 122   while (iter.more_available()) {
 123     HeapRegion* hr = iter.get_next();
 124     // In set_containing_set() we check that we either set the value
 125     // from NULL to non-NULL or vice versa to catch bugs. So, we have
 126     // to NULL it first before setting it to the value.
 127     hr->set_containing_set(NULL);
 128     hr->set_containing_set(this);
 129   }
 130 #endif // ASSERT
 131 
 132   if (_head != NULL) {
 133     assert(length() >  0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
 134     from_list->_tail->set_next(_head);
 135   } else {
 136     assert(length() == 0 && _tail == NULL, hrs_ext_msg(this, "invariant"));
 137     _tail = from_list->_tail;
 138   }
 139   _head = from_list->_head;
 140 
 141   _count.increment(from_list->length(), from_list->total_capacity_bytes());
 142   from_list->clear();
 143 
 144   verify_optional();
 145   from_list->verify_optional();
 146 }
 147 
 148 void FreeRegionList::add_as_tail(FreeRegionList* from_list) {
 149   check_mt_safety();
 150   from_list->check_mt_safety();
 151 
 152   verify_optional();
 153   from_list->verify_optional();
 154 
 155   if (from_list->is_empty()) return;
 156 
 157 #ifdef ASSERT
 158   FreeRegionListIterator iter(from_list);
 159   while (iter.more_available()) {
 160     HeapRegion* hr = iter.get_next();
 161     // In set_containing_set() we check that we either set the value
 162     // from NULL to non-NULL or vice versa to catch bugs. So, we have
 163     // to NULL it first before setting it to the value.
 164     hr->set_containing_set(NULL);
 165     hr->set_containing_set(this);
 166   }
 167 #endif // ASSERT
 168 
 169   if (_tail != NULL) {
 170     assert(length() >  0 && _head != NULL, hrs_ext_msg(this, "invariant"));
 171     _tail->set_next(from_list->_head);
 172   } else {
 173     assert(length() == 0 && _head == NULL, hrs_ext_msg(this, "invariant"));
 174     _head = from_list->_head;
 175   }
 176   _tail = from_list->_tail;
 177 
 178   _count.increment(from_list->length(), from_list->total_capacity_bytes());
 179   from_list->clear();
 180 
 181   verify_optional();
 182   from_list->verify_optional();
 183 }
 184 
 185 void FreeRegionList::remove_all() {
 186   check_mt_safety();
 187   verify_optional();
 188 
 189   HeapRegion* curr = _head;
 190   while (curr != NULL) {
 191     verify_region(curr);
 192 
 193     HeapRegion* next = curr->next();
 194     curr->set_next(NULL);
 195     curr->set_containing_set(NULL);
 196     curr = next;
 197   }
 198   clear();
 199 
 200   verify_optional();
 201 }
 202 
 203 void FreeRegionList::remove_all_pending(uint target_count) {
 204   check_mt_safety();
 205   assert(target_count > 1, hrs_ext_msg(this, "pre-condition"));
 206   assert(!is_empty(), hrs_ext_msg(this, "pre-condition"));
 207 
 208   verify_optional();
 209   DEBUG_ONLY(uint old_length = length();)
 210 
 211   HeapRegion* curr = _head;
 212   HeapRegion* prev = NULL;
 213   uint count = 0;
 214   while (curr != NULL) {
 215     verify_region(curr);
 216     HeapRegion* next = curr->next();
 217 
 218     if (curr->pending_removal()) {
 219       assert(count < target_count,
 220              hrs_err_msg("[%s] should not come across more regions "
 221                          "pending for removal than target_count: %u",
 222                          name(), target_count));
 223 
 224       if (prev == NULL) {
 225         assert(_head == curr, hrs_ext_msg(this, "invariant"));
 226         _head = next;
 227       } else {
 228         assert(_head != curr, hrs_ext_msg(this, "invariant"));
 229         prev->set_next(next);
 230       }
 231       if (next == NULL) {
 232         assert(_tail == curr, hrs_ext_msg(this, "invariant"));
 233         _tail = prev;
 234       } else {
 235         assert(_tail != curr, hrs_ext_msg(this, "invariant"));
 236       }
 237 
 238       curr->set_next(NULL);
 239       remove(curr);
 240       curr->set_pending_removal(false);
 241 
 242       count += 1;
 243 
 244       // If we have come across the target number of regions we can
 245       // just bail out. However, for debugging purposes, we can just
 246       // carry on iterating to make sure there are not more regions
 247       // tagged with pending removal.
 248       DEBUG_ONLY(if (count == target_count) break;)
 249     } else {
 250       prev = curr;
 251     }
 252     curr = next;
 253   }
 254 
 255   assert(count == target_count,
 256          hrs_err_msg("[%s] count: %u should be == target_count: %u",
 257                      name(), count, target_count));
 258   assert(length() + target_count == old_length,
 259          hrs_err_msg("[%s] new length should be consistent "
 260                      "new length: %u old length: %u target_count: %u",
 261                      name(), length(), old_length, target_count));
 262 
 263   verify_optional();
 264 }
 265 
 266 void FreeRegionList::verify() {
 267   // See comment in HeapRegionSetBase::verify() about MT safety and
 268   // verification.
 269   check_mt_safety();
 270 
 271   // This will also do the basic verification too.
 272   verify_start();
 273 
 274   verify_list();
 275 
 276   verify_end();
 277 }
 278 
 279 void FreeRegionList::clear() {
 280   _count = HeapRegionSetCount();
 281   _head = NULL;
 282   _tail = NULL;
 283 }
 284 
 285 void FreeRegionList::print_on(outputStream* out, bool print_contents) {
 286   HeapRegionSetBase::print_on(out, print_contents);
 287   out->print_cr("  Linking");
 288   out->print_cr("    head              : "PTR_FORMAT, _head);
 289   out->print_cr("    tail              : "PTR_FORMAT, _tail);
 290 
 291   if (print_contents) {
 292     out->print_cr("  Contents");
 293     FreeRegionListIterator iter(this);
 294     while (iter.more_available()) {
 295       HeapRegion* hr = iter.get_next();
 296       hr->print_on(out);
 297     }
 298   }
 299 }