hotspot/src/share/vm/gc_implementation/g1/heapRegionSeq.cpp
changeset 12381 1438e0fbfa27
parent 9989 305a76435cf1
child 13195 be27e1b6a4b9
equal deleted inserted replaced
12380:48f69987dbca 12381:1438e0fbfa27
     1 /*
     1 /*
     2  * Copyright (c) 2001, 2011, Oracle and/or its affiliates. All rights reserved.
     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.
     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     4  *
     4  *
     5  * This code is free software; you can redistribute it and/or modify it
     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
     6  * under the terms of the GNU General Public License version 2 only, as
     7  * published by the Free Software Foundation.
     7  * published by the Free Software Foundation.
    29 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
    29 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
    30 #include "memory/allocation.hpp"
    30 #include "memory/allocation.hpp"
    31 
    31 
    32 // Private
    32 // Private
    33 
    33 
    34 size_t HeapRegionSeq::find_contiguous_from(size_t from, size_t num) {
    34 uint HeapRegionSeq::find_contiguous_from(uint from, uint num) {
    35   size_t len = length();
    35   uint len = length();
    36   assert(num > 1, "use this only for sequences of length 2 or greater");
    36   assert(num > 1, "use this only for sequences of length 2 or greater");
    37   assert(from <= len,
    37   assert(from <= len,
    38          err_msg("from: "SIZE_FORMAT" should be valid and <= than "SIZE_FORMAT,
    38          err_msg("from: %u should be valid and <= than %u", from, len));
    39                  from, len));
    39 
    40 
    40   uint curr = from;
    41   size_t curr = from;
    41   uint first = G1_NULL_HRS_INDEX;
    42   size_t first = G1_NULL_HRS_INDEX;
    42   uint num_so_far = 0;
    43   size_t num_so_far = 0;
       
    44   while (curr < len && num_so_far < num) {
    43   while (curr < len && num_so_far < num) {
    45     if (at(curr)->is_empty()) {
    44     if (at(curr)->is_empty()) {
    46       if (first == G1_NULL_HRS_INDEX) {
    45       if (first == G1_NULL_HRS_INDEX) {
    47         first = curr;
    46         first = curr;
    48         num_so_far = 1;
    47         num_so_far = 1;
    58   assert(num_so_far <= num, "post-condition");
    57   assert(num_so_far <= num, "post-condition");
    59   if (num_so_far == num) {
    58   if (num_so_far == num) {
    60     // we found enough space for the humongous object
    59     // we found enough space for the humongous object
    61     assert(from <= first && first < len, "post-condition");
    60     assert(from <= first && first < len, "post-condition");
    62     assert(first < curr && (curr - first) == num, "post-condition");
    61     assert(first < curr && (curr - first) == num, "post-condition");
    63     for (size_t i = first; i < first + num; ++i) {
    62     for (uint i = first; i < first + num; ++i) {
    64       assert(at(i)->is_empty(), "post-condition");
    63       assert(at(i)->is_empty(), "post-condition");
    65     }
    64     }
    66     return first;
    65     return first;
    67   } else {
    66   } else {
    68     // we failed to find enough space for the humongous object
    67     // we failed to find enough space for the humongous object
    71 }
    70 }
    72 
    71 
    73 // Public
    72 // Public
    74 
    73 
    75 void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* end,
    74 void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* end,
    76                                size_t max_length) {
    75                                uint max_length) {
    77   assert((size_t) bottom % HeapRegion::GrainBytes == 0,
    76   assert((uintptr_t) bottom % HeapRegion::GrainBytes == 0,
    78          "bottom should be heap region aligned");
    77          "bottom should be heap region aligned");
    79   assert((size_t) end % HeapRegion::GrainBytes == 0,
    78   assert((uintptr_t) end % HeapRegion::GrainBytes == 0,
    80          "end should be heap region aligned");
    79          "end should be heap region aligned");
    81 
    80 
    82   _length = 0;
    81   _length = 0;
    83   _heap_bottom = bottom;
    82   _heap_bottom = bottom;
    84   _heap_end = end;
    83   _heap_end = end;
    86   _next_search_index = 0;
    85   _next_search_index = 0;
    87   _allocated_length = 0;
    86   _allocated_length = 0;
    88   _max_length = max_length;
    87   _max_length = max_length;
    89 
    88 
    90   _regions = NEW_C_HEAP_ARRAY(HeapRegion*, max_length);
    89   _regions = NEW_C_HEAP_ARRAY(HeapRegion*, max_length);
    91   memset(_regions, 0, max_length * sizeof(HeapRegion*));
    90   memset(_regions, 0, (size_t) max_length * sizeof(HeapRegion*));
    92   _regions_biased = _regions - ((size_t) bottom >> _region_shift);
    91   _regions_biased = _regions - ((uintx) bottom >> _region_shift);
    93 
    92 
    94   assert(&_regions[0] == &_regions_biased[addr_to_index_biased(bottom)],
    93   assert(&_regions[0] == &_regions_biased[addr_to_index_biased(bottom)],
    95          "bottom should be included in the region with index 0");
    94          "bottom should be included in the region with index 0");
    96 }
    95 }
    97 
    96 
   103 
   102 
   104   HeapWord* next_bottom = old_end;
   103   HeapWord* next_bottom = old_end;
   105   assert(_heap_bottom <= next_bottom, "invariant");
   104   assert(_heap_bottom <= next_bottom, "invariant");
   106   while (next_bottom < new_end) {
   105   while (next_bottom < new_end) {
   107     assert(next_bottom < _heap_end, "invariant");
   106     assert(next_bottom < _heap_end, "invariant");
   108     size_t index = length();
   107     uint index = length();
   109 
   108 
   110     assert(index < _max_length, "otherwise we cannot expand further");
   109     assert(index < _max_length, "otherwise we cannot expand further");
   111     if (index == 0) {
   110     if (index == 0) {
   112       // We have not allocated any regions so far
   111       // We have not allocated any regions so far
   113       assert(next_bottom == _heap_bottom, "invariant");
   112       assert(next_bottom == _heap_bottom, "invariant");
   137   }
   136   }
   138   assert(next_bottom == new_end, "post-condition");
   137   assert(next_bottom == new_end, "post-condition");
   139   return MemRegion(old_end, next_bottom);
   138   return MemRegion(old_end, next_bottom);
   140 }
   139 }
   141 
   140 
   142 size_t HeapRegionSeq::free_suffix() {
   141 uint HeapRegionSeq::free_suffix() {
   143   size_t res = 0;
   142   uint res = 0;
   144   size_t index = length();
   143   uint index = length();
   145   while (index > 0) {
   144   while (index > 0) {
   146     index -= 1;
   145     index -= 1;
   147     if (!at(index)->is_empty()) {
   146     if (!at(index)->is_empty()) {
   148       break;
   147       break;
   149     }
   148     }
   150     res += 1;
   149     res += 1;
   151   }
   150   }
   152   return res;
   151   return res;
   153 }
   152 }
   154 
   153 
   155 size_t HeapRegionSeq::find_contiguous(size_t num) {
   154 uint HeapRegionSeq::find_contiguous(uint num) {
   156   assert(num > 1, "use this only for sequences of length 2 or greater");
   155   assert(num > 1, "use this only for sequences of length 2 or greater");
   157   assert(_next_search_index <= length(),
   156   assert(_next_search_index <= length(),
   158          err_msg("_next_search_indeex: "SIZE_FORMAT" "
   157          err_msg("_next_search_index: %u should be valid and <= than %u",
   159                  "should be valid and <= than "SIZE_FORMAT,
       
   160                  _next_search_index, length()));
   158                  _next_search_index, length()));
   161 
   159 
   162   size_t start = _next_search_index;
   160   uint start = _next_search_index;
   163   size_t res = find_contiguous_from(start, num);
   161   uint res = find_contiguous_from(start, num);
   164   if (res == G1_NULL_HRS_INDEX && start > 0) {
   162   if (res == G1_NULL_HRS_INDEX && start > 0) {
   165     // Try starting from the beginning. If _next_search_index was 0,
   163     // Try starting from the beginning. If _next_search_index was 0,
   166     // no point in doing this again.
   164     // no point in doing this again.
   167     res = find_contiguous_from(0, num);
   165     res = find_contiguous_from(0, num);
   168   }
   166   }
   169   if (res != G1_NULL_HRS_INDEX) {
   167   if (res != G1_NULL_HRS_INDEX) {
   170     assert(res < length(),
   168     assert(res < length(), err_msg("res: %u should be valid", res));
   171            err_msg("res: "SIZE_FORMAT" should be valid", res));
       
   172     _next_search_index = res + num;
   169     _next_search_index = res + num;
   173     assert(_next_search_index <= length(),
   170     assert(_next_search_index <= length(),
   174            err_msg("_next_search_indeex: "SIZE_FORMAT" "
   171            err_msg("_next_search_index: %u should be valid and <= than %u",
   175                    "should be valid and <= than "SIZE_FORMAT,
       
   176                    _next_search_index, length()));
   172                    _next_search_index, length()));
   177   }
   173   }
   178   return res;
   174   return res;
   179 }
   175 }
   180 
   176 
   181 void HeapRegionSeq::iterate(HeapRegionClosure* blk) const {
   177 void HeapRegionSeq::iterate(HeapRegionClosure* blk) const {
   182   iterate_from((HeapRegion*) NULL, blk);
   178   iterate_from((HeapRegion*) NULL, blk);
   183 }
   179 }
   184 
   180 
   185 void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const {
   181 void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const {
   186   size_t hr_index = 0;
   182   uint hr_index = 0;
   187   if (hr != NULL) {
   183   if (hr != NULL) {
   188     hr_index = (size_t) hr->hrs_index();
   184     hr_index = hr->hrs_index();
   189   }
   185   }
   190 
   186 
   191   size_t len = length();
   187   uint len = length();
   192   for (size_t i = hr_index; i < len; i += 1) {
   188   for (uint i = hr_index; i < len; i += 1) {
   193     bool res = blk->doHeapRegion(at(i));
   189     bool res = blk->doHeapRegion(at(i));
   194     if (res) {
   190     if (res) {
   195       blk->incomplete();
   191       blk->incomplete();
   196       return;
   192       return;
   197     }
   193     }
   198   }
   194   }
   199   for (size_t i = 0; i < hr_index; i += 1) {
   195   for (uint i = 0; i < hr_index; i += 1) {
   200     bool res = blk->doHeapRegion(at(i));
   196     bool res = blk->doHeapRegion(at(i));
   201     if (res) {
   197     if (res) {
   202       blk->incomplete();
   198       blk->incomplete();
   203       return;
   199       return;
   204     }
   200     }
   205   }
   201   }
   206 }
   202 }
   207 
   203 
   208 MemRegion HeapRegionSeq::shrink_by(size_t shrink_bytes,
   204 MemRegion HeapRegionSeq::shrink_by(size_t shrink_bytes,
   209                                    size_t* num_regions_deleted) {
   205                                    uint* num_regions_deleted) {
   210   // Reset this in case it's currently pointing into the regions that
   206   // Reset this in case it's currently pointing into the regions that
   211   // we just removed.
   207   // we just removed.
   212   _next_search_index = 0;
   208   _next_search_index = 0;
   213 
   209 
   214   assert(shrink_bytes % os::vm_page_size() == 0, "unaligned");
   210   assert(shrink_bytes % os::vm_page_size() == 0, "unaligned");
   216   assert(length() > 0, "the region sequence should not be empty");
   212   assert(length() > 0, "the region sequence should not be empty");
   217   assert(length() <= _allocated_length, "invariant");
   213   assert(length() <= _allocated_length, "invariant");
   218   assert(_allocated_length > 0, "we should have at least one region committed");
   214   assert(_allocated_length > 0, "we should have at least one region committed");
   219 
   215 
   220   // around the loop, i will be the next region to be removed
   216   // around the loop, i will be the next region to be removed
   221   size_t i = length() - 1;
   217   uint i = length() - 1;
   222   assert(i > 0, "we should never remove all regions");
   218   assert(i > 0, "we should never remove all regions");
   223   // [last_start, end) is the MemRegion that covers the regions we will remove.
   219   // [last_start, end) is the MemRegion that covers the regions we will remove.
   224   HeapWord* end = at(i)->end();
   220   HeapWord* end = at(i)->end();
   225   HeapWord* last_start = end;
   221   HeapWord* last_start = end;
   226   *num_regions_deleted = 0;
   222   *num_regions_deleted = 0;
   247 }
   243 }
   248 
   244 
   249 #ifndef PRODUCT
   245 #ifndef PRODUCT
   250 void HeapRegionSeq::verify_optional() {
   246 void HeapRegionSeq::verify_optional() {
   251   guarantee(_length <= _allocated_length,
   247   guarantee(_length <= _allocated_length,
   252             err_msg("invariant: _length: "SIZE_FORMAT" "
   248             err_msg("invariant: _length: %u _allocated_length: %u",
   253                     "_allocated_length: "SIZE_FORMAT,
       
   254                     _length, _allocated_length));
   249                     _length, _allocated_length));
   255   guarantee(_allocated_length <= _max_length,
   250   guarantee(_allocated_length <= _max_length,
   256             err_msg("invariant: _allocated_length: "SIZE_FORMAT" "
   251             err_msg("invariant: _allocated_length: %u _max_length: %u",
   257                     "_max_length: "SIZE_FORMAT,
       
   258                     _allocated_length, _max_length));
   252                     _allocated_length, _max_length));
   259   guarantee(_next_search_index <= _length,
   253   guarantee(_next_search_index <= _length,
   260             err_msg("invariant: _next_search_index: "SIZE_FORMAT" "
   254             err_msg("invariant: _next_search_index: %u _length: %u",
   261                     "_length: "SIZE_FORMAT,
       
   262                     _next_search_index, _length));
   255                     _next_search_index, _length));
   263 
   256 
   264   HeapWord* prev_end = _heap_bottom;
   257   HeapWord* prev_end = _heap_bottom;
   265   for (size_t i = 0; i < _allocated_length; i += 1) {
   258   for (uint i = 0; i < _allocated_length; i += 1) {
   266     HeapRegion* hr = _regions[i];
   259     HeapRegion* hr = _regions[i];
   267     guarantee(hr != NULL, err_msg("invariant: i: "SIZE_FORMAT, i));
   260     guarantee(hr != NULL, err_msg("invariant: i: %u", i));
   268     guarantee(hr->bottom() == prev_end,
   261     guarantee(hr->bottom() == prev_end,
   269               err_msg("invariant i: "SIZE_FORMAT" "HR_FORMAT" "
   262               err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT,
   270                       "prev_end: "PTR_FORMAT,
       
   271                       i, HR_FORMAT_PARAMS(hr), prev_end));
   263                       i, HR_FORMAT_PARAMS(hr), prev_end));
   272     guarantee(hr->hrs_index() == i,
   264     guarantee(hr->hrs_index() == i,
   273               err_msg("invariant: i: "SIZE_FORMAT" hrs_index(): "SIZE_FORMAT,
   265               err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index()));
   274                       i, hr->hrs_index()));
       
   275     if (i < _length) {
   266     if (i < _length) {
   276       // Asserts will fire if i is >= _length
   267       // Asserts will fire if i is >= _length
   277       HeapWord* addr = hr->bottom();
   268       HeapWord* addr = hr->bottom();
   278       guarantee(addr_to_region(addr) == hr, "sanity");
   269       guarantee(addr_to_region(addr) == hr, "sanity");
   279       guarantee(addr_to_region_unsafe(addr) == hr, "sanity");
   270       guarantee(addr_to_region_unsafe(addr) == hr, "sanity");
   288       prev_end = hr->orig_end();
   279       prev_end = hr->orig_end();
   289     } else {
   280     } else {
   290       prev_end = hr->end();
   281       prev_end = hr->end();
   291     }
   282     }
   292   }
   283   }
   293   for (size_t i = _allocated_length; i < _max_length; i += 1) {
   284   for (uint i = _allocated_length; i < _max_length; i += 1) {
   294     guarantee(_regions[i] == NULL, err_msg("invariant i: "SIZE_FORMAT, i));
   285     guarantee(_regions[i] == NULL, err_msg("invariant i: %u", i));
   295   }
   286   }
   296 }
   287 }
   297 #endif // PRODUCT
   288 #endif // PRODUCT