1 /*
   2  * Copyright (c) 2001, 2013, 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/heapRegion.hpp"
  27 #include "gc_implementation/g1/heapRegionSeq.inline.hpp"
  28 #include "gc_implementation/g1/heapRegionSet.hpp"
  29 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
  30 #include "memory/allocation.hpp"
  31 
  32 // Private
  33 
  34 uint HeapRegionSeq::find_contiguous_from(uint from, uint num) {
  35   uint len = length();
  36   assert(num > 1, "use this only for sequences of length 2 or greater");
  37   assert(from <= len,
  38          err_msg("from: %u should be valid and <= than %u", from, len));
  39 
  40   uint curr = from;
  41   uint first = G1_NULL_HRS_INDEX;
  42   uint num_so_far = 0;
  43   while (curr < len && num_so_far < num) {
  44     if (at(curr)->is_empty()) {
  45       if (first == G1_NULL_HRS_INDEX) {
  46         first = curr;
  47         num_so_far = 1;
  48       } else {
  49         num_so_far += 1;
  50       }
  51     } else {
  52       first = G1_NULL_HRS_INDEX;
  53       num_so_far = 0;
  54     }
  55     curr += 1;
  56   }
  57   assert(num_so_far <= num, "post-condition");
  58   if (num_so_far == num) {
  59     // we found enough space for the humongous object
  60     assert(from <= first && first < len, "post-condition");
  61     assert(first < curr && (curr - first) == num, "post-condition");
  62     for (uint i = first; i < first + num; ++i) {
  63       assert(at(i)->is_empty(), "post-condition");
  64     }
  65     return first;
  66   } else {
  67     // we failed to find enough space for the humongous object
  68     return G1_NULL_HRS_INDEX;
  69   }
  70 }
  71 
  72 // Public
  73 
  74 void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* end) {
  75   assert((uintptr_t) bottom % HeapRegion::GrainBytes == 0,
  76          "bottom should be heap region aligned");
  77   assert((uintptr_t) end % HeapRegion::GrainBytes == 0,
  78          "end should be heap region aligned");
  79 
  80   _next_search_index = 0;
  81   _allocated_length = 0;
  82 
  83   _regions.initialize(bottom, end, HeapRegion::GrainBytes);
  84 }
  85 
  86 MemRegion HeapRegionSeq::expand_by(HeapWord* old_end,
  87                                    HeapWord* new_end,
  88                                    FreeRegionList* list) {
  89   assert(old_end < new_end, "don't call it otherwise");
  90   G1CollectedHeap* g1h = G1CollectedHeap::heap();
  91 
  92   HeapWord* next_bottom = old_end;
  93   assert(heap_bottom() <= next_bottom, "invariant");
  94   while (next_bottom < new_end) {
  95     assert(next_bottom < heap_end(), "invariant");
  96     uint index = length();
  97 
  98     assert(index < max_length(), "otherwise we cannot expand further");
  99     if (index == 0) {
 100       // We have not allocated any regions so far
 101       assert(next_bottom == heap_bottom(), "invariant");
 102     } else {
 103       // next_bottom should match the end of the last/previous region
 104       assert(next_bottom == at(index - 1)->end(), "invariant");
 105     }
 106 
 107     if (index == _allocated_length) {
 108       // We have to allocate a new HeapRegion.
 109       HeapRegion* new_hr = g1h->new_heap_region(index, next_bottom);
 110       if (new_hr == NULL) {
 111         // allocation failed, we bail out and return what we have done so far
 112         return MemRegion(old_end, next_bottom);
 113       }
 114       assert(_regions.get_by_index(index) == NULL, "invariant");
 115       _regions.set_by_index(index, new_hr);
 116       increment_allocated_length();
 117     }
 118     // Have to increment the length first, otherwise we will get an
 119     // assert failure at(index) below.
 120     increment_length();
 121     HeapRegion* hr = at(index);
 122     list->add_as_tail(hr);
 123 
 124     next_bottom = hr->end();
 125   }
 126   assert(next_bottom == new_end, "post-condition");
 127   return MemRegion(old_end, next_bottom);
 128 }
 129 
 130 uint HeapRegionSeq::free_suffix() {
 131   uint res = 0;
 132   uint index = length();
 133   while (index > 0) {
 134     index -= 1;
 135     if (!at(index)->is_empty()) {
 136       break;
 137     }
 138     res += 1;
 139   }
 140   return res;
 141 }
 142 
 143 uint HeapRegionSeq::find_contiguous(uint num) {
 144   assert(num > 1, "use this only for sequences of length 2 or greater");
 145   assert(_next_search_index <= length(),
 146          err_msg("_next_search_index: %u should be valid and <= than %u",
 147                  _next_search_index, length()));
 148 
 149   uint start = _next_search_index;
 150   uint res = find_contiguous_from(start, num);
 151   if (res == G1_NULL_HRS_INDEX && start > 0) {
 152     // Try starting from the beginning. If _next_search_index was 0,
 153     // no point in doing this again.
 154     res = find_contiguous_from(0, num);
 155   }
 156   if (res != G1_NULL_HRS_INDEX) {
 157     assert(res < length(), err_msg("res: %u should be valid", res));
 158     _next_search_index = res + num;
 159     assert(_next_search_index <= length(),
 160            err_msg("_next_search_index: %u should be valid and <= than %u",
 161                    _next_search_index, length()));
 162   }
 163   return res;
 164 }
 165 
 166 void HeapRegionSeq::iterate(HeapRegionClosure* blk) const {
 167   iterate_from((HeapRegion*) NULL, blk);
 168 }
 169 
 170 void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const {
 171   uint hr_index = 0;
 172   if (hr != NULL) {
 173     hr_index = hr->hrs_index();
 174   }
 175 
 176   uint len = length();
 177   for (uint i = hr_index; i < len; i += 1) {
 178     bool res = blk->doHeapRegion(at(i));
 179     if (res) {
 180       blk->incomplete();
 181       return;
 182     }
 183   }
 184   for (uint i = 0; i < hr_index; i += 1) {
 185     bool res = blk->doHeapRegion(at(i));
 186     if (res) {
 187       blk->incomplete();
 188       return;
 189     }
 190   }
 191 }
 192 
 193 uint HeapRegionSeq::shrink_by(uint num_regions_to_remove) {
 194   // Reset this in case it's currently pointing into the regions that
 195   // we just removed.
 196   _next_search_index = 0;
 197 
 198   assert(length() > 0, "the region sequence should not be empty");
 199   assert(length() <= _allocated_length, "invariant");
 200   assert(_allocated_length > 0, "we should have at least one region committed");
 201   assert(num_regions_to_remove < length(), "We should never remove all regions");
 202 
 203   uint i = 0;
 204   for (; i < num_regions_to_remove; i++) {
 205     HeapRegion* cur = at(length() - 1);
 206 
 207     if (!cur->is_empty()) {
 208       // We have to give up if the region can not be moved
 209       break;
 210   }
 211     assert(!cur->isHumongous(), "Humongous regions should not be empty");
 212 
 213     decrement_length();
 214   }
 215   return i;
 216 }
 217 
 218 #ifndef PRODUCT
 219 void HeapRegionSeq::verify_optional() {
 220   guarantee(length() <= _allocated_length,
 221             err_msg("invariant: _length: %u _allocated_length: %u",
 222                     length(), _allocated_length));
 223   guarantee(_allocated_length <= max_length(),
 224             err_msg("invariant: _allocated_length: %u _max_length: %u",
 225                     _allocated_length, max_length()));
 226   guarantee(_next_search_index <= length(),
 227             err_msg("invariant: _next_search_index: %u _length: %u",
 228                     _next_search_index, length()));
 229 
 230   HeapWord* prev_end = heap_bottom();
 231   for (uint i = 0; i < _allocated_length; i += 1) {
 232     HeapRegion* hr = _regions.get_by_index(i);
 233     guarantee(hr != NULL, err_msg("invariant: i: %u", i));
 234     guarantee(hr->bottom() == prev_end,
 235               err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT,
 236                       i, HR_FORMAT_PARAMS(hr), prev_end));
 237     guarantee(hr->hrs_index() == i,
 238               err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index()));
 239     if (i < length()) {
 240       // Asserts will fire if i is >= _length
 241       HeapWord* addr = hr->bottom();
 242       guarantee(addr_to_region(addr) == hr, "sanity");
 243       guarantee(addr_to_region_unsafe(addr) == hr, "sanity");
 244     } else {
 245       guarantee(hr->is_empty(), "sanity");
 246       guarantee(!hr->isHumongous(), "sanity");
 247       // using assert instead of guarantee here since containing_set()
 248       // is only available in non-product builds.
 249       assert(hr->containing_set() == NULL, "sanity");
 250     }
 251     if (hr->startsHumongous()) {
 252       prev_end = hr->orig_end();
 253     } else {
 254       prev_end = hr->end();
 255     }
 256   }
 257   for (uint i = _allocated_length; i < max_length(); i += 1) {
 258     guarantee(_regions.get_by_index(i) == NULL, err_msg("invariant i: %u", i));
 259   }
 260 }
 261 #endif // PRODUCT