1 /*
   2  * Copyright (c) 2001, 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/heapRegion.hpp"
  27 #include "gc_implementation/g1/heapRegionSeq.inline.hpp"
  28 #include "gc_implementation/g1/heapRegionSets.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                                uint max_length) {
  76   assert((uintptr_t) bottom % HeapRegion::GrainBytes == 0,
  77          "bottom should be heap region aligned");
  78   assert((uintptr_t) end % HeapRegion::GrainBytes == 0,
  79          "end should be heap region aligned");
  80 
  81   _length = 0;
  82   _heap_bottom = bottom;
  83   _heap_end = end;
  84   _region_shift = HeapRegion::LogOfHRGrainBytes;
  85   _next_search_index = 0;
  86   _allocated_length = 0;
  87   _max_length = max_length;
  88 
  89   _regions = NEW_C_HEAP_ARRAY(HeapRegion*, max_length, mtGC);
  90   memset(_regions, 0, (size_t) max_length * sizeof(HeapRegion*));
  91   _regions_biased = _regions - ((uintx) bottom >> _region_shift);
  92 
  93   assert(&_regions[0] == &_regions_biased[addr_to_index_biased(bottom)],
  94          "bottom should be included in the region with index 0");
  95 }
  96 
  97 MemRegion HeapRegionSeq::expand_by(HeapWord* old_end,
  98                                    HeapWord* new_end,
  99                                    FreeRegionList* list) {
 100   assert(old_end < new_end, "don't call it otherwise");
 101   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 102 
 103   HeapWord* next_bottom = old_end;
 104   assert(_heap_bottom <= next_bottom, "invariant");
 105   while (next_bottom < new_end) {
 106     assert(next_bottom < _heap_end, "invariant");
 107     uint index = length();
 108 
 109     assert(index < _max_length, "otherwise we cannot expand further");
 110     if (index == 0) {
 111       // We have not allocated any regions so far
 112       assert(next_bottom == _heap_bottom, "invariant");
 113     } else {
 114       // next_bottom should match the end of the last/previous region
 115       assert(next_bottom == at(index - 1)->end(), "invariant");
 116     }
 117 
 118     if (index == _allocated_length) {
 119       // We have to allocate a new HeapRegion.
 120       HeapRegion* new_hr = g1h->new_heap_region(index, next_bottom);
 121       if (new_hr == NULL) {
 122         // allocation failed, we bail out and return what we have done so far
 123         return MemRegion(old_end, next_bottom);
 124       }
 125       assert(_regions[index] == NULL, "invariant");
 126       _regions[index] = new_hr;
 127       increment_length(&_allocated_length);
 128     }
 129     // Have to increment the length first, otherwise we will get an
 130     // assert failure at(index) below.
 131     increment_length(&_length);
 132     HeapRegion* hr = at(index);
 133     list->add_as_tail(hr);
 134 
 135     next_bottom = hr->end();
 136   }
 137   assert(next_bottom == new_end, "post-condition");
 138   return MemRegion(old_end, next_bottom);
 139 }
 140 
 141 uint HeapRegionSeq::free_suffix() {
 142   uint res = 0;
 143   uint index = length();
 144   while (index > 0) {
 145     index -= 1;
 146     if (!at(index)->is_empty()) {
 147       break;
 148     }
 149     res += 1;
 150   }
 151   return res;
 152 }
 153 
 154 uint HeapRegionSeq::find_contiguous(uint num) {
 155   assert(num > 1, "use this only for sequences of length 2 or greater");
 156   assert(_next_search_index <= length(),
 157          err_msg("_next_search_index: %u should be valid and <= than %u",
 158                  _next_search_index, length()));
 159 
 160   uint start = _next_search_index;
 161   uint res = find_contiguous_from(start, num);
 162   if (res == G1_NULL_HRS_INDEX && start > 0) {
 163     // Try starting from the beginning. If _next_search_index was 0,
 164     // no point in doing this again.
 165     res = find_contiguous_from(0, num);
 166   }
 167   if (res != G1_NULL_HRS_INDEX) {
 168     assert(res < length(), err_msg("res: %u should be valid", res));
 169     _next_search_index = res + num;
 170     assert(_next_search_index <= length(),
 171            err_msg("_next_search_index: %u should be valid and <= than %u",
 172                    _next_search_index, length()));
 173   }
 174   return res;
 175 }
 176 
 177 void HeapRegionSeq::iterate(HeapRegionClosure* blk) const {
 178   iterate_from((HeapRegion*) NULL, blk);
 179 }
 180 
 181 void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const {
 182   uint hr_index = 0;
 183   if (hr != NULL) {
 184     hr_index = hr->hrs_index();
 185   }
 186 
 187   uint len = length();
 188   for (uint i = hr_index; i < len; i += 1) {
 189     bool res = blk->doHeapRegion(at(i));
 190     if (res) {
 191       blk->incomplete();
 192       return;
 193     }
 194   }
 195   for (uint i = 0; i < hr_index; i += 1) {
 196     bool res = blk->doHeapRegion(at(i));
 197     if (res) {
 198       blk->incomplete();
 199       return;
 200     }
 201   }
 202 }
 203 
 204 MemRegion HeapRegionSeq::shrink_by(size_t shrink_bytes,
 205                                    uint* num_regions_deleted) {
 206   // Reset this in case it's currently pointing into the regions that
 207   // we just removed.
 208   _next_search_index = 0;
 209 
 210   assert(shrink_bytes % os::vm_page_size() == 0, "unaligned");
 211   assert(shrink_bytes % HeapRegion::GrainBytes == 0, "unaligned");
 212   assert(length() > 0, "the region sequence should not be empty");
 213   assert(length() <= _allocated_length, "invariant");
 214   assert(_allocated_length > 0, "we should have at least one region committed");
 215 
 216   // around the loop, i will be the next region to be removed
 217   uint i = length() - 1;
 218   assert(i > 0, "we should never remove all regions");
 219   // [last_start, end) is the MemRegion that covers the regions we will remove.
 220   HeapWord* end = at(i)->end();
 221   HeapWord* last_start = end;
 222   *num_regions_deleted = 0;
 223   while (shrink_bytes > 0) {
 224     HeapRegion* cur = at(i);
 225     // We should leave the humongous regions where they are.
 226     if (cur->isHumongous()) break;
 227     // We should stop shrinking if we come across a non-empty region.
 228     if (!cur->is_empty()) break;
 229 
 230     i -= 1;
 231     *num_regions_deleted += 1;
 232     shrink_bytes -= cur->capacity();
 233     last_start = cur->bottom();
 234     decrement_length(&_length);
 235     // We will reclaim the HeapRegion. _allocated_length should be
 236     // covering this index. So, even though we removed the region from
 237     // the active set by decreasing _length, we still have it
 238     // available in the future if we need to re-use it.
 239     assert(i > 0, "we should never remove all regions");
 240     assert(length() > 0, "we should never remove all regions");
 241   }
 242   return MemRegion(last_start, end);
 243 }
 244 
 245 #ifndef PRODUCT
 246 void HeapRegionSeq::verify_optional() {
 247   guarantee(_length <= _allocated_length,
 248             err_msg("invariant: _length: %u _allocated_length: %u",
 249                     _length, _allocated_length));
 250   guarantee(_allocated_length <= _max_length,
 251             err_msg("invariant: _allocated_length: %u _max_length: %u",
 252                     _allocated_length, _max_length));
 253   guarantee(_next_search_index <= _length,
 254             err_msg("invariant: _next_search_index: %u _length: %u",
 255                     _next_search_index, _length));
 256 
 257   HeapWord* prev_end = _heap_bottom;
 258   for (uint i = 0; i < _allocated_length; i += 1) {
 259     HeapRegion* hr = _regions[i];
 260     guarantee(hr != NULL, err_msg("invariant: i: %u", i));
 261     guarantee(hr->bottom() == prev_end,
 262               err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT,
 263                       i, HR_FORMAT_PARAMS(hr), prev_end));
 264     guarantee(hr->hrs_index() == i,
 265               err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index()));
 266     if (i < _length) {
 267       // Asserts will fire if i is >= _length
 268       HeapWord* addr = hr->bottom();
 269       guarantee(addr_to_region(addr) == hr, "sanity");
 270       guarantee(addr_to_region_unsafe(addr) == hr, "sanity");
 271     } else {
 272       guarantee(hr->is_empty(), "sanity");
 273       guarantee(!hr->isHumongous(), "sanity");
 274       // using assert instead of guarantee here since containing_set()
 275       // is only available in non-product builds.
 276       assert(hr->containing_set() == NULL, "sanity");
 277     }
 278     if (hr->startsHumongous()) {
 279       prev_end = hr->orig_end();
 280     } else {
 281       prev_end = hr->end();
 282     }
 283   }
 284   for (uint i = _allocated_length; i < _max_length; i += 1) {
 285     guarantee(_regions[i] == NULL, err_msg("invariant i: %u", i));
 286   }
 287 }
 288 #endif // PRODUCT