1 /*
   2  * Copyright (c) 2011, 2015, 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/g1/g1CollectedHeap.inline.hpp"
  27 #include "gc/g1/heapRegionRemSet.hpp"
  28 #include "gc/g1/heapRegionSet.inline.hpp"
  29 
  30 uint FreeRegionList::_unrealistically_long_length = 0;
  31 
  32 #ifndef PRODUCT
  33 void HeapRegionSetBase::verify_region(HeapRegion* hr) {
  34   assert(hr->containing_set() == this, "Inconsistent containing set for %u", hr->hrm_index());
  35   assert(!hr->is_young(), "Adding young region %u", hr->hrm_index()); // currently we don't use these sets for young regions
  36   assert(hr->is_humongous() == regions_humongous(), "Wrong humongous state for region %u and set %s", hr->hrm_index(), name());
  37   assert(hr->is_free() == regions_free(), "Wrong free state for region %u and set %s", hr->hrm_index(), name());
  38   assert(!hr->is_free() || hr->is_empty(), "Free region %u is not empty for set %s", hr->hrm_index(), name());
  39   assert(!hr->is_empty() || hr->is_free() || hr->is_archive(),
  40          "Empty region %u is not free or archive for set %s", hr->hrm_index(), name());
  41   assert(hr->rem_set()->verify_ready_for_par_iteration(), "Wrong iteration state %u", hr->hrm_index());
  42 }
  43 #endif
  44 
  45 void HeapRegionSetBase::verify() {
  46   // It's important that we also observe the MT safety protocol even
  47   // for the verification calls. If we do verification without the
  48   // appropriate locks and the set changes underneath our feet
  49   // verification might fail and send us on a wild goose chase.
  50   check_mt_safety();
  51 
  52   guarantee_heap_region_set(( is_empty() && length() == 0) ||
  53                             (!is_empty() && length() > 0),
  54                             "invariant");
  55 }
  56 
  57 void HeapRegionSetBase::verify_start() {
  58   // See comment in verify() about MT safety and verification.
  59   check_mt_safety();
  60   assert_heap_region_set(!_verify_in_progress, "verification should not be in progress");
  61 
  62   // Do the basic verification first before we do the checks over the regions.
  63   HeapRegionSetBase::verify();
  64 
  65   _verify_in_progress = true;
  66 }
  67 
  68 void HeapRegionSetBase::verify_end() {
  69   // See comment in verify() about MT safety and verification.
  70   check_mt_safety();
  71   assert_heap_region_set(_verify_in_progress, "verification should be in progress");
  72 
  73   _verify_in_progress = false;
  74 }
  75 
  76 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
  77   out->cr();
  78   out->print_cr("Set: %s (" PTR_FORMAT ")", name(), p2i(this));
  79   out->print_cr("  Region Assumptions");
  80   out->print_cr("    humongous         : %s", BOOL_TO_STR(regions_humongous()));
  81   out->print_cr("    free              : %s", BOOL_TO_STR(regions_free()));
  82   out->print_cr("  Attributes");
  83   out->print_cr("    length            : %14u", length());
  84 }
  85 
  86 HeapRegionSetBase::HeapRegionSetBase(const char* name, bool humongous, bool free, HRSMtSafeChecker* mt_safety_checker)
  87   : _name(name), _verify_in_progress(false),
  88     _is_humongous(humongous), _is_free(free), _mt_safety_checker(mt_safety_checker),
  89     _length(0)
  90 { }
  91 
  92 void FreeRegionList::set_unrealistically_long_length(uint len) {
  93   guarantee(_unrealistically_long_length == 0, "should only be set once");
  94   _unrealistically_long_length = len;
  95 }
  96 
  97 void FreeRegionList::remove_all() {
  98   check_mt_safety();
  99   verify_optional();
 100 
 101   HeapRegion* curr = _head;
 102   while (curr != NULL) {
 103     verify_region(curr);
 104 
 105     HeapRegion* next = curr->next();
 106     curr->set_next(NULL);
 107     curr->set_prev(NULL);
 108     curr->set_containing_set(NULL);
 109     curr = next;
 110   }
 111   clear();
 112 
 113   verify_optional();
 114 }
 115 
 116 void FreeRegionList::add_ordered(FreeRegionList* from_list) {
 117   check_mt_safety();
 118   from_list->check_mt_safety();
 119 
 120   verify_optional();
 121   from_list->verify_optional();
 122 
 123   if (from_list->is_empty()) {
 124     return;
 125   }
 126 
 127   #ifdef ASSERT
 128   FreeRegionListIterator iter(from_list);
 129   while (iter.more_available()) {
 130     HeapRegion* hr = iter.get_next();
 131     // In set_containing_set() we check that we either set the value
 132     // from NULL to non-NULL or vice versa to catch bugs. So, we have
 133     // to NULL it first before setting it to the value.
 134     hr->set_containing_set(NULL);
 135     hr->set_containing_set(this);
 136   }
 137   #endif // ASSERT
 138 
 139   if (is_empty()) {
 140     assert_free_region_list(length() == 0 && _tail == NULL, "invariant");
 141     _head = from_list->_head;
 142     _tail = from_list->_tail;
 143   } else {
 144     HeapRegion* curr_to = _head;
 145     HeapRegion* curr_from = from_list->_head;
 146 
 147     while (curr_from != NULL) {
 148       while (curr_to != NULL && curr_to->hrm_index() < curr_from->hrm_index()) {
 149         curr_to = curr_to->next();
 150       }
 151 
 152       if (curr_to == NULL) {
 153         // The rest of the from list should be added as tail
 154         _tail->set_next(curr_from);
 155         curr_from->set_prev(_tail);
 156         curr_from = NULL;
 157       } else {
 158         HeapRegion* next_from = curr_from->next();
 159 
 160         curr_from->set_next(curr_to);
 161         curr_from->set_prev(curr_to->prev());
 162         if (curr_to->prev() == NULL) {
 163           _head = curr_from;
 164         } else {
 165           curr_to->prev()->set_next(curr_from);
 166         }
 167         curr_to->set_prev(curr_from);
 168 
 169         curr_from = next_from;
 170       }
 171     }
 172 
 173     if (_tail->hrm_index() < from_list->_tail->hrm_index()) {
 174       _tail = from_list->_tail;
 175     }
 176   }
 177 
 178   _length += from_list->length();
 179   from_list->clear();
 180 
 181   verify_optional();
 182   from_list->verify_optional();
 183 }
 184 
 185 void FreeRegionList::remove_starting_at(HeapRegion* first, uint num_regions) {
 186   check_mt_safety();
 187   assert_free_region_list(num_regions >= 1, "pre-condition");
 188   assert_free_region_list(!is_empty(), "pre-condition");
 189 
 190   verify_optional();
 191   DEBUG_ONLY(uint old_length = length();)
 192 
 193   HeapRegion* curr = first;
 194   uint count = 0;
 195   while (count < num_regions) {
 196     verify_region(curr);
 197     HeapRegion* next = curr->next();
 198     HeapRegion* prev = curr->prev();
 199 
 200     assert(count < num_regions,
 201            "[%s] should not come across more regions "
 202            "pending for removal than num_regions: %u",
 203            name(), num_regions);
 204 
 205     if (prev == NULL) {
 206       assert_free_region_list(_head == curr, "invariant");
 207       _head = next;
 208     } else {
 209       assert_free_region_list(_head != curr, "invariant");
 210       prev->set_next(next);
 211     }
 212     if (next == NULL) {
 213       assert_free_region_list(_tail == curr, "invariant");
 214       _tail = prev;
 215     } else {
 216       assert_free_region_list(_tail != curr, "invariant");
 217       next->set_prev(prev);
 218     }
 219     if (_last == curr) {
 220       _last = NULL;
 221     }
 222 
 223     curr->set_next(NULL);
 224     curr->set_prev(NULL);
 225     remove(curr);
 226 
 227     count++;
 228     curr = next;
 229   }
 230 
 231   assert(count == num_regions,
 232          "[%s] count: %u should be == num_regions: %u",
 233          name(), count, num_regions);
 234   assert(length() + num_regions == old_length,
 235          "[%s] new length should be consistent "
 236          "new length: %u old length: %u num_regions: %u",
 237          name(), length(), old_length, num_regions);
 238 
 239   verify_optional();
 240 }
 241 
 242 void FreeRegionList::verify() {
 243   // See comment in HeapRegionSetBase::verify() about MT safety and
 244   // verification.
 245   check_mt_safety();
 246 
 247   // This will also do the basic verification too.
 248   verify_start();
 249 
 250   verify_list();
 251 
 252   verify_end();
 253 }
 254 
 255 void FreeRegionList::clear() {
 256   _length = 0;
 257   _head = NULL;
 258   _tail = NULL;
 259   _last = NULL;
 260 }
 261 
 262 void FreeRegionList::verify_list() {
 263   HeapRegion* curr = _head;
 264   HeapRegion* prev1 = NULL;
 265   HeapRegion* prev0 = NULL;
 266   uint count = 0;
 267   size_t capacity = 0;
 268   uint last_index = 0;
 269 
 270   guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev");
 271   while (curr != NULL) {
 272     verify_region(curr);
 273 
 274     count++;
 275     guarantee(count < _unrealistically_long_length,
 276               "[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: " PTR_FORMAT " prev0: " PTR_FORMAT " " "prev1: " PTR_FORMAT " length: %u",
 277               name(), count, p2i(curr), p2i(prev0), p2i(prev1), length());
 278 
 279     if (curr->next() != NULL) {
 280       guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up");
 281     }
 282     guarantee(curr->hrm_index() == 0 || curr->hrm_index() > last_index, "List should be sorted");
 283     last_index = curr->hrm_index();
 284 
 285     capacity += curr->capacity();
 286 
 287     prev1 = prev0;
 288     prev0 = curr;
 289     curr = curr->next();
 290   }
 291 
 292   guarantee(_tail == prev0, "Expected %s to end with %u but it ended with %u.", name(), _tail->hrm_index(), prev0->hrm_index());
 293   guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next");
 294   guarantee(length() == count, "%s count mismatch. Expected %u, actual %u.", name(), length(), count);
 295 }
 296 
 297 // Note on the check_mt_safety() methods below:
 298 //
 299 // Verification of the "master" heap region sets / lists that are
 300 // maintained by G1CollectedHeap is always done during a STW pause and
 301 // by the VM thread at the start / end of the pause. The standard
 302 // verification methods all assert check_mt_safety(). This is
 303 // important as it ensures that verification is done without
 304 // concurrent updates taking place at the same time. It follows, that,
 305 // for the "master" heap region sets / lists, the check_mt_safety()
 306 // method should include the VM thread / STW case.
 307 
 308 void MasterFreeRegionListMtSafeChecker::check() {
 309   // Master Free List MT safety protocol:
 310   // (a) If we're at a safepoint, operations on the master free list
 311   // should be invoked by either the VM thread (which will serialize
 312   // them) or by the GC workers while holding the
 313   // FreeList_lock.
 314   // (b) If we're not at a safepoint, operations on the master free
 315   // list should be invoked while holding the Heap_lock.
 316 
 317   if (SafepointSynchronize::is_at_safepoint()) {
 318     guarantee(Thread::current()->is_VM_thread() ||
 319               FreeList_lock->owned_by_self(), "master free list MT safety protocol at a safepoint");
 320   } else {
 321     guarantee(Heap_lock->owned_by_self(), "master free list MT safety protocol outside a safepoint");
 322   }
 323 }
 324 
 325 void SecondaryFreeRegionListMtSafeChecker::check() {
 326   // Secondary Free List MT safety protocol:
 327   // Operations on the secondary free list should always be invoked
 328   // while holding the SecondaryFreeList_lock.
 329 
 330   guarantee(SecondaryFreeList_lock->owned_by_self(), "secondary free list MT safety protocol");
 331 }
 332 
 333 void OldRegionSetMtSafeChecker::check() {
 334   // Master Old Set MT safety protocol:
 335   // (a) If we're at a safepoint, operations on the master old set
 336   // should be invoked:
 337   // - by the VM thread (which will serialize them), or
 338   // - by the GC workers while holding the FreeList_lock, if we're
 339   //   at a safepoint for an evacuation pause (this lock is taken
 340   //   anyway when an GC alloc region is retired so that a new one
 341   //   is allocated from the free list), or
 342   // - by the GC workers while holding the OldSets_lock, if we're at a
 343   //   safepoint for a cleanup pause.
 344   // (b) If we're not at a safepoint, operations on the master old set
 345   // should be invoked while holding the Heap_lock.
 346 
 347   if (SafepointSynchronize::is_at_safepoint()) {
 348     guarantee(Thread::current()->is_VM_thread()
 349         || FreeList_lock->owned_by_self() || OldSets_lock->owned_by_self(),
 350         "master old set MT safety protocol at a safepoint");
 351   } else {
 352     guarantee(Heap_lock->owned_by_self(), "master old set MT safety protocol outside a safepoint");
 353   }
 354 }
 355 
 356 void HumongousRegionSetMtSafeChecker::check() {
 357   // Humongous Set MT safety protocol:
 358   // (a) If we're at a safepoint, operations on the master humongous
 359   // set should be invoked by either the VM thread (which will
 360   // serialize them) or by the GC workers while holding the
 361   // OldSets_lock.
 362   // (b) If we're not at a safepoint, operations on the master
 363   // humongous set should be invoked while holding the Heap_lock.
 364 
 365   if (SafepointSynchronize::is_at_safepoint()) {
 366     guarantee(Thread::current()->is_VM_thread() ||
 367               OldSets_lock->owned_by_self(),
 368               "master humongous set MT safety protocol at a safepoint");
 369   } else {
 370     guarantee(Heap_lock->owned_by_self(),
 371               "master humongous set MT safety protocol outside a safepoint");
 372   }
 373 }
 374 
 375 void FreeRegionList_test() {
 376   FreeRegionList l("test");
 377 
 378   const uint num_regions_in_test = 5;
 379   // Create a fake heap. It does not need to be valid, as the HeapRegion constructor
 380   // does not access it.
 381   MemRegion heap(NULL, num_regions_in_test * HeapRegion::GrainWords);
 382   // Allocate a fake BOT because the HeapRegion constructor initializes
 383   // the BOT.
 384   size_t bot_size = G1BlockOffsetSharedArray::compute_size(heap.word_size());
 385   HeapWord* bot_data = NEW_C_HEAP_ARRAY(HeapWord, bot_size, mtGC);
 386   ReservedSpace bot_rs(G1BlockOffsetSharedArray::compute_size(heap.word_size()));
 387   G1RegionToSpaceMapper* bot_storage =
 388     G1RegionToSpaceMapper::create_mapper(bot_rs,
 389                                          bot_rs.size(),
 390                                          os::vm_page_size(),
 391                                          HeapRegion::GrainBytes,
 392                                          G1BlockOffsetSharedArray::N_bytes,
 393                                          mtGC);
 394   G1BlockOffsetSharedArray oa(heap, bot_storage);
 395   bot_storage->commit_regions(0, num_regions_in_test);
 396 
 397   // Set up memory regions for the heap regions.
 398   MemRegion mr0(heap.start(), HeapRegion::GrainWords);
 399   MemRegion mr1(mr0.end(), HeapRegion::GrainWords);
 400   MemRegion mr2(mr1.end(), HeapRegion::GrainWords);
 401   MemRegion mr3(mr2.end(), HeapRegion::GrainWords);
 402   MemRegion mr4(mr3.end(), HeapRegion::GrainWords);
 403 
 404   HeapRegion hr0(0, &oa, mr0);
 405   HeapRegion hr1(1, &oa, mr1);
 406   HeapRegion hr2(2, &oa, mr2);
 407   HeapRegion hr3(3, &oa, mr3);
 408   HeapRegion hr4(4, &oa, mr4);
 409   l.add_ordered(&hr1);
 410   l.add_ordered(&hr0);
 411   l.add_ordered(&hr3);
 412   l.add_ordered(&hr4);
 413   l.add_ordered(&hr2);
 414   assert(l.length() == num_regions_in_test, "wrong length");
 415   l.verify_list();
 416 
 417   bot_storage->uncommit_regions(0, num_regions_in_test);
 418   delete bot_storage;
 419   FREE_C_HEAP_ARRAY(HeapWord, bot_data);
 420 }