1 /*
   2  * Copyright (c) 2011, 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/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(_checker == NULL || _checker->is_correct_type(hr), "Wrong type of region %u (%s) and set %s",
  37          hr->hrm_index(), hr->get_type_str(), 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 }
  42 #endif
  43 
  44 void HeapRegionSetBase::verify() {
  45   // It's important that we also observe the MT safety protocol even
  46   // for the verification calls. If we do verification without the
  47   // appropriate locks and the set changes underneath our feet
  48   // verification might fail and send us on a wild goose chase.
  49   check_mt_safety();
  50 
  51   guarantee_heap_region_set(( is_empty() && length() == 0) ||
  52                             (!is_empty() && length() > 0),
  53                             "invariant");
  54 }
  55 
  56 void HeapRegionSetBase::verify_start() {
  57   // See comment in verify() about MT safety and verification.
  58   check_mt_safety();
  59   assert_heap_region_set(!_verify_in_progress, "verification should not be in progress");
  60 
  61   // Do the basic verification first before we do the checks over the regions.
  62   HeapRegionSetBase::verify();
  63 
  64   _verify_in_progress = true;
  65 }
  66 
  67 void HeapRegionSetBase::verify_end() {
  68   // See comment in verify() about MT safety and verification.
  69   check_mt_safety();
  70   assert_heap_region_set(_verify_in_progress, "verification should be in progress");
  71 
  72   _verify_in_progress = false;
  73 }
  74 
  75 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
  76   out->cr();
  77   out->print_cr("Set: %s (" PTR_FORMAT ")", name(), p2i(this));
  78   out->print_cr("  Region Type         : %s", _checker->get_description());
  79   out->print_cr("  Length              : %14u", length());
  80 }
  81 
  82 HeapRegionSetBase::HeapRegionSetBase(const char* name, HeapRegionSetChecker* checker)
  83   : _checker(checker), _length(0), _name(name), _verify_in_progress(false)
  84 {
  85 }
  86 
  87 void FreeRegionList::set_unrealistically_long_length(uint len) {
  88   guarantee(_unrealistically_long_length == 0, "should only be set once");
  89   _unrealistically_long_length = len;
  90 }
  91 
  92 void FreeRegionList::remove_all() {
  93   check_mt_safety();
  94   verify_optional();
  95 
  96   HeapRegion* curr = _head;
  97   while (curr != NULL) {
  98     verify_region(curr);
  99 
 100     HeapRegion* next = curr->next();
 101     curr->set_next(NULL);
 102     curr->set_prev(NULL);
 103     curr->set_containing_set(NULL);
 104     curr = next;
 105   }
 106   clear();
 107 
 108   verify_optional();
 109 }
 110 
 111 void FreeRegionList::add_ordered(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()) {
 119     return;
 120   }
 121 
 122   #ifdef ASSERT
 123   FreeRegionListIterator iter(from_list);
 124   while (iter.more_available()) {
 125     HeapRegion* hr = iter.get_next();
 126     // In set_containing_set() we check that we either set the value
 127     // from NULL to non-NULL or vice versa to catch bugs. So, we have
 128     // to NULL it first before setting it to the value.
 129     hr->set_containing_set(NULL);
 130     hr->set_containing_set(this);
 131   }
 132   #endif // ASSERT
 133 
 134   if (is_empty()) {
 135     assert_free_region_list(length() == 0 && _tail == NULL, "invariant");
 136     _head = from_list->_head;
 137     _tail = from_list->_tail;
 138   } else {
 139     HeapRegion* curr_to = _head;
 140     HeapRegion* curr_from = from_list->_head;
 141 
 142     while (curr_from != NULL) {
 143       while (curr_to != NULL && curr_to->hrm_index() < curr_from->hrm_index()) {
 144         curr_to = curr_to->next();
 145       }
 146 
 147       if (curr_to == NULL) {
 148         // The rest of the from list should be added as tail
 149         _tail->set_next(curr_from);
 150         curr_from->set_prev(_tail);
 151         curr_from = NULL;
 152       } else {
 153         HeapRegion* next_from = curr_from->next();
 154 
 155         curr_from->set_next(curr_to);
 156         curr_from->set_prev(curr_to->prev());
 157         if (curr_to->prev() == NULL) {
 158           _head = curr_from;
 159         } else {
 160           curr_to->prev()->set_next(curr_from);
 161         }
 162         curr_to->set_prev(curr_from);
 163 
 164         curr_from = next_from;
 165       }
 166     }
 167 
 168     if (_tail->hrm_index() < from_list->_tail->hrm_index()) {
 169       _tail = from_list->_tail;
 170     }
 171   }
 172 
 173   _length += from_list->length();
 174   from_list->clear();
 175 
 176   verify_optional();
 177   from_list->verify_optional();
 178 }
 179 
 180 void FreeRegionList::remove_starting_at(HeapRegion* first, uint num_regions) {
 181   check_mt_safety();
 182   assert_free_region_list(num_regions >= 1, "pre-condition");
 183   assert_free_region_list(!is_empty(), "pre-condition");
 184 
 185   verify_optional();
 186   DEBUG_ONLY(uint old_length = length();)
 187 
 188   HeapRegion* curr = first;
 189   uint count = 0;
 190   while (count < num_regions) {
 191     verify_region(curr);
 192     HeapRegion* next = curr->next();
 193     HeapRegion* prev = curr->prev();
 194 
 195     assert(count < num_regions,
 196            "[%s] should not come across more regions "
 197            "pending for removal than num_regions: %u",
 198            name(), num_regions);
 199 
 200     if (prev == NULL) {
 201       assert_free_region_list(_head == curr, "invariant");
 202       _head = next;
 203     } else {
 204       assert_free_region_list(_head != curr, "invariant");
 205       prev->set_next(next);
 206     }
 207     if (next == NULL) {
 208       assert_free_region_list(_tail == curr, "invariant");
 209       _tail = prev;
 210     } else {
 211       assert_free_region_list(_tail != curr, "invariant");
 212       next->set_prev(prev);
 213     }
 214     if (_last == curr) {
 215       _last = NULL;
 216     }
 217 
 218     curr->set_next(NULL);
 219     curr->set_prev(NULL);
 220     remove(curr);
 221 
 222     count++;
 223     curr = next;
 224   }
 225 
 226   assert(count == num_regions,
 227          "[%s] count: %u should be == num_regions: %u",
 228          name(), count, num_regions);
 229   assert(length() + num_regions == old_length,
 230          "[%s] new length should be consistent "
 231          "new length: %u old length: %u num_regions: %u",
 232          name(), length(), old_length, num_regions);
 233 
 234   verify_optional();
 235 }
 236 
 237 uint FreeRegionList::num_of_regions_in_range(uint start, uint end) const {
 238   HeapRegion* cur = _head;
 239   uint num = 0;
 240   bool started = false;
 241   while (cur != NULL && cur->hrm_index() <= end) {
 242     if (!started && cur->hrm_index() >= start) {
 243       started = true;
 244     }
 245     if(started) {
 246       num++;
 247     }
 248     cur = cur->next();
 249   }
 250   return num;
 251 }
 252 
 253 void FreeRegionList::verify() {
 254   // See comment in HeapRegionSetBase::verify() about MT safety and
 255   // verification.
 256   check_mt_safety();
 257 
 258   // This will also do the basic verification too.
 259   verify_start();
 260 
 261   verify_list();
 262 
 263   verify_end();
 264 }
 265 
 266 void FreeRegionList::clear() {
 267   _length = 0;
 268   _head = NULL;
 269   _tail = NULL;
 270   _last = NULL;
 271 }
 272 
 273 void FreeRegionList::verify_list() {
 274   HeapRegion* curr = _head;
 275   HeapRegion* prev1 = NULL;
 276   HeapRegion* prev0 = NULL;
 277   uint count = 0;
 278   size_t capacity = 0;
 279   uint last_index = 0;
 280 
 281   guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev");
 282   while (curr != NULL) {
 283     verify_region(curr);
 284 
 285     count++;
 286     guarantee(count < _unrealistically_long_length,
 287               "[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: " PTR_FORMAT " prev0: " PTR_FORMAT " " "prev1: " PTR_FORMAT " length: %u",
 288               name(), count, p2i(curr), p2i(prev0), p2i(prev1), length());
 289 
 290     if (curr->next() != NULL) {
 291       guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up");
 292     }
 293     guarantee(curr->hrm_index() == 0 || curr->hrm_index() > last_index, "List should be sorted");
 294     last_index = curr->hrm_index();
 295 
 296     capacity += curr->capacity();
 297 
 298     prev1 = prev0;
 299     prev0 = curr;
 300     curr = curr->next();
 301   }
 302 
 303   guarantee(_tail == prev0, "Expected %s to end with %u but it ended with %u.", name(), _tail->hrm_index(), prev0->hrm_index());
 304   guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next");
 305   guarantee(length() == count, "%s count mismatch. Expected %u, actual %u.", name(), length(), count);
 306 }