ysr@777: /*
tonyp@3713:  * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved.
ysr@777:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
ysr@777:  *
ysr@777:  * This code is free software; you can redistribute it and/or modify it
ysr@777:  * under the terms of the GNU General Public License version 2 only, as
ysr@777:  * published by the Free Software Foundation.
ysr@777:  *
ysr@777:  * This code is distributed in the hope that it will be useful, but WITHOUT
ysr@777:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
ysr@777:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
ysr@777:  * version 2 for more details (a copy is included in the LICENSE file that
ysr@777:  * accompanied this code).
ysr@777:  *
ysr@777:  * You should have received a copy of the GNU General Public License version
ysr@777:  * 2 along with this work; if not, write to the Free Software Foundation,
ysr@777:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
ysr@777:  *
trims@1907:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@1907:  * or visit www.oracle.com if you need additional information or have any
trims@1907:  * questions.
ysr@777:  *
ysr@777:  */
ysr@777: 
stefank@2314: #include "precompiled.hpp"
tonyp@2963: #include "gc_implementation/g1/heapRegion.hpp"
tonyp@2963: #include "gc_implementation/g1/heapRegionSeq.inline.hpp"
tonyp@2963: #include "gc_implementation/g1/heapRegionSets.hpp"
stefank@2314: #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
stefank@2314: #include "memory/allocation.hpp"
ysr@777: 
tonyp@2963: // Private
ysr@777: 
tonyp@3713: uint HeapRegionSeq::find_contiguous_from(uint from, uint num) {
tonyp@3713:   uint len = length();
tonyp@2963:   assert(num > 1, "use this only for sequences of length 2 or greater");
tonyp@2963:   assert(from <= len,
tonyp@3713:          err_msg("from: %u should be valid and <= than %u", from, len));
ysr@777: 
tonyp@3713:   uint curr = from;
tonyp@3713:   uint first = G1_NULL_HRS_INDEX;
tonyp@3713:   uint num_so_far = 0;
tonyp@2963:   while (curr < len && num_so_far < num) {
tonyp@2963:     if (at(curr)->is_empty()) {
tonyp@2963:       if (first == G1_NULL_HRS_INDEX) {
tonyp@2472:         first = curr;
tonyp@2472:         num_so_far = 1;
tonyp@2472:       } else {
tonyp@2472:         num_so_far += 1;
tonyp@2472:       }
tonyp@2472:     } else {
tonyp@2963:       first = G1_NULL_HRS_INDEX;
tonyp@2472:       num_so_far = 0;
tonyp@2472:     }
tonyp@2472:     curr += 1;
tonyp@2472:   }
tonyp@2472:   assert(num_so_far <= num, "post-condition");
tonyp@2472:   if (num_so_far == num) {
tonyp@2643:     // we found enough space for the humongous object
tonyp@2963:     assert(from <= first && first < len, "post-condition");
tonyp@2963:     assert(first < curr && (curr - first) == num, "post-condition");
tonyp@3713:     for (uint i = first; i < first + num; ++i) {
tonyp@2963:       assert(at(i)->is_empty(), "post-condition");
tonyp@2472:     }
tonyp@2472:     return first;
tonyp@2472:   } else {
tonyp@2472:     // we failed to find enough space for the humongous object
tonyp@2963:     return G1_NULL_HRS_INDEX;
tonyp@2472:   }
tonyp@2472: }
tonyp@2472: 
tonyp@2963: // Public
tonyp@2472: 
tonyp@2963: void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* end,
tonyp@3713:                                uint max_length) {
tonyp@3713:   assert((uintptr_t) bottom % HeapRegion::GrainBytes == 0,
tonyp@2963:          "bottom should be heap region aligned");
tonyp@3713:   assert((uintptr_t) end % HeapRegion::GrainBytes == 0,
tonyp@2963:          "end should be heap region aligned");
tonyp@2963: 
tonyp@2963:   _length = 0;
tonyp@2963:   _heap_bottom = bottom;
tonyp@2963:   _heap_end = end;
tonyp@2963:   _region_shift = HeapRegion::LogOfHRGrainBytes;
tonyp@2963:   _next_search_index = 0;
tonyp@2963:   _allocated_length = 0;
tonyp@2963:   _max_length = max_length;
tonyp@2963: 
zgu@3900:   _regions = NEW_C_HEAP_ARRAY(HeapRegion*, max_length, mtGC);
tonyp@3713:   memset(_regions, 0, (size_t) max_length * sizeof(HeapRegion*));
tonyp@3713:   _regions_biased = _regions - ((uintx) bottom >> _region_shift);
tonyp@2963: 
tonyp@2963:   assert(&_regions[0] == &_regions_biased[addr_to_index_biased(bottom)],
tonyp@2963:          "bottom should be included in the region with index 0");
tonyp@2963: }
tonyp@2963: 
tonyp@2963: MemRegion HeapRegionSeq::expand_by(HeapWord* old_end,
tonyp@2963:                                    HeapWord* new_end,
tonyp@2963:                                    FreeRegionList* list) {
tonyp@2963:   assert(old_end < new_end, "don't call it otherwise");
tonyp@2963:   G1CollectedHeap* g1h = G1CollectedHeap::heap();
tonyp@2963: 
tonyp@2963:   HeapWord* next_bottom = old_end;
tonyp@2963:   assert(_heap_bottom <= next_bottom, "invariant");
tonyp@2963:   while (next_bottom < new_end) {
tonyp@2963:     assert(next_bottom < _heap_end, "invariant");
tonyp@3713:     uint index = length();
tonyp@2963: 
tonyp@2963:     assert(index < _max_length, "otherwise we cannot expand further");
tonyp@2963:     if (index == 0) {
tonyp@2963:       // We have not allocated any regions so far
tonyp@2963:       assert(next_bottom == _heap_bottom, "invariant");
tonyp@2963:     } else {
tonyp@2963:       // next_bottom should match the end of the last/previous region
tonyp@2963:       assert(next_bottom == at(index - 1)->end(), "invariant");
tonyp@2963:     }
tonyp@2963: 
tonyp@2963:     if (index == _allocated_length) {
tonyp@2963:       // We have to allocate a new HeapRegion.
tonyp@2963:       HeapRegion* new_hr = g1h->new_heap_region(index, next_bottom);
tonyp@2963:       if (new_hr == NULL) {
tonyp@2963:         // allocation failed, we bail out and return what we have done so far
tonyp@2963:         return MemRegion(old_end, next_bottom);
tonyp@2963:       }
tonyp@2963:       assert(_regions[index] == NULL, "invariant");
tonyp@2963:       _regions[index] = new_hr;
brutisso@5074:       increment_allocated_length();
tonyp@2963:     }
tonyp@2963:     // Have to increment the length first, otherwise we will get an
tonyp@2963:     // assert failure at(index) below.
brutisso@5074:     increment_length();
tonyp@2963:     HeapRegion* hr = at(index);
tonyp@2963:     list->add_as_tail(hr);
tonyp@2963: 
tonyp@2963:     next_bottom = hr->end();
tonyp@2472:   }
tonyp@2963:   assert(next_bottom == new_end, "post-condition");
tonyp@2963:   return MemRegion(old_end, next_bottom);
tonyp@2963: }
tonyp@2963: 
tonyp@3713: uint HeapRegionSeq::free_suffix() {
tonyp@3713:   uint res = 0;
tonyp@3713:   uint index = length();
tonyp@2963:   while (index > 0) {
tonyp@2963:     index -= 1;
tonyp@2963:     if (!at(index)->is_empty()) {
tonyp@2963:       break;
tonyp@2963:     }
tonyp@2963:     res += 1;
tonyp@2472:   }
ysr@777:   return res;
ysr@777: }
ysr@777: 
tonyp@3713: uint HeapRegionSeq::find_contiguous(uint num) {
tonyp@2963:   assert(num > 1, "use this only for sequences of length 2 or greater");
tonyp@2963:   assert(_next_search_index <= length(),
tonyp@3713:          err_msg("_next_search_index: %u should be valid and <= than %u",
tonyp@2963:                  _next_search_index, length()));
tonyp@2963: 
tonyp@3713:   uint start = _next_search_index;
tonyp@3713:   uint res = find_contiguous_from(start, num);
tonyp@2963:   if (res == G1_NULL_HRS_INDEX && start > 0) {
tonyp@2963:     // Try starting from the beginning. If _next_search_index was 0,
tonyp@2963:     // no point in doing this again.
tonyp@2963:     res = find_contiguous_from(0, num);
tonyp@2963:   }
tonyp@2963:   if (res != G1_NULL_HRS_INDEX) {
tonyp@3713:     assert(res < length(), err_msg("res: %u should be valid", res));
tonyp@2963:     _next_search_index = res + num;
tonyp@2963:     assert(_next_search_index <= length(),
tonyp@3713:            err_msg("_next_search_index: %u should be valid and <= than %u",
tonyp@2963:                    _next_search_index, length()));
tonyp@2963:   }
tonyp@2963:   return res;
ysr@777: }
ysr@777: 
tonyp@2963: void HeapRegionSeq::iterate(HeapRegionClosure* blk) const {
tonyp@2963:   iterate_from((HeapRegion*) NULL, blk);
tonyp@2963: }
ysr@777: 
tonyp@2963: void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const {
tonyp@3713:   uint hr_index = 0;
tonyp@2963:   if (hr != NULL) {
tonyp@3713:     hr_index = hr->hrs_index();
tonyp@2963:   }
ysr@777: 
tonyp@3713:   uint len = length();
tonyp@3713:   for (uint i = hr_index; i < len; i += 1) {
tonyp@2963:     bool res = blk->doHeapRegion(at(i));
ysr@777:     if (res) {
ysr@777:       blk->incomplete();
ysr@777:       return;
ysr@777:     }
ysr@777:   }
tonyp@3713:   for (uint i = 0; i < hr_index; i += 1) {
tonyp@2963:     bool res = blk->doHeapRegion(at(i));
ysr@777:     if (res) {
ysr@777:       blk->incomplete();
ysr@777:       return;
ysr@777:     }
ysr@777:   }
ysr@777: }
ysr@777: 
brutisso@5074: uint HeapRegionSeq::shrink_by(uint num_regions_to_remove) {
tonyp@2472:   // Reset this in case it's currently pointing into the regions that
tonyp@2472:   // we just removed.
tonyp@2963:   _next_search_index = 0;
tonyp@2472: 
tonyp@2963:   assert(length() > 0, "the region sequence should not be empty");
tonyp@2963:   assert(length() <= _allocated_length, "invariant");
tonyp@2963:   assert(_allocated_length > 0, "we should have at least one region committed");
brutisso@5074:   assert(num_regions_to_remove < length(), "We should never remove all regions");
ysr@777: 
brutisso@5074:   uint i = 0;
brutisso@5074:   for (; i < num_regions_to_remove; i++) {
brutisso@5074:     HeapRegion* cur = at(length() - 1);
tonyp@2963: 
brutisso@5074:     if (!cur->is_empty()) {
brutisso@5074:       // We have to give up if the region can not be moved
brutisso@5074:       break;
ysr@777:   }
brutisso@5074:     assert(!cur->isHumongous(), "Humongous regions should not be empty");
brutisso@5074: 
brutisso@5074:     decrement_length();
brutisso@5074:   }
brutisso@5074:   return i;
ysr@777: }
ysr@777: 
tonyp@2963: #ifndef PRODUCT
tonyp@2963: void HeapRegionSeq::verify_optional() {
tonyp@2963:   guarantee(_length <= _allocated_length,
tonyp@3713:             err_msg("invariant: _length: %u _allocated_length: %u",
tonyp@2963:                     _length, _allocated_length));
tonyp@2963:   guarantee(_allocated_length <= _max_length,
tonyp@3713:             err_msg("invariant: _allocated_length: %u _max_length: %u",
tonyp@2963:                     _allocated_length, _max_length));
tonyp@2963:   guarantee(_next_search_index <= _length,
tonyp@3713:             err_msg("invariant: _next_search_index: %u _length: %u",
tonyp@2963:                     _next_search_index, _length));
tonyp@2963: 
tonyp@2963:   HeapWord* prev_end = _heap_bottom;
tonyp@3713:   for (uint i = 0; i < _allocated_length; i += 1) {
tonyp@2963:     HeapRegion* hr = _regions[i];
tonyp@3713:     guarantee(hr != NULL, err_msg("invariant: i: %u", i));
tonyp@2963:     guarantee(hr->bottom() == prev_end,
tonyp@3713:               err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT,
tonyp@2963:                       i, HR_FORMAT_PARAMS(hr), prev_end));
tonyp@2963:     guarantee(hr->hrs_index() == i,
tonyp@3713:               err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index()));
tonyp@2963:     if (i < _length) {
tonyp@2963:       // Asserts will fire if i is >= _length
tonyp@2963:       HeapWord* addr = hr->bottom();
tonyp@2963:       guarantee(addr_to_region(addr) == hr, "sanity");
tonyp@2963:       guarantee(addr_to_region_unsafe(addr) == hr, "sanity");
tonyp@2963:     } else {
tonyp@2963:       guarantee(hr->is_empty(), "sanity");
tonyp@2963:       guarantee(!hr->isHumongous(), "sanity");
tonyp@2963:       // using assert instead of guarantee here since containing_set()
tonyp@2963:       // is only available in non-product builds.
tonyp@2963:       assert(hr->containing_set() == NULL, "sanity");
tonyp@2963:     }
tonyp@2963:     if (hr->startsHumongous()) {
tonyp@2963:       prev_end = hr->orig_end();
tonyp@2963:     } else {
tonyp@2963:       prev_end = hr->end();
tonyp@2963:     }
ysr@777:   }
tonyp@3713:   for (uint i = _allocated_length; i < _max_length; i += 1) {
tonyp@3713:     guarantee(_regions[i] == NULL, err_msg("invariant i: %u", i));
tonyp@2963:   }
ysr@777: }
tonyp@2963: #endif // PRODUCT