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 MemRegion HeapRegionSeq::expand_to(HeapWord* new_end, FreeRegionList* list) { 75 assert(_heap_end < new_end && new_end <= _max_heap_end, 76 err_msg("new_end: "PTR_FORMAT" heap end: "PTR_FORMAT" " 77 "max heap end: "PTR_FORMAT, new_end, _heap_end, _max_heap_end)); 78 G1CollectedHeap* g1h = G1CollectedHeap::heap(); 79 80 uint new_length = length_for(new_end); 81 uint index = length(); 82 HeapWord* next_hr_bottom = _heap_end; 83 while (index < new_length) { 84 assert(length_for(next_hr_bottom) == index, 85 err_msg("invariant, length_for: "PTR_FORMAT" %u index: %u", 86 next_hr_bottom, length_for(next_hr_bottom), index)); 87 88 if (index == 0) { 89 // We have not allocated any regions so far. 90 assert(next_hr_bottom == _heap_bottom, "invariant"); 91 } else { 92 // The previous region should exist. 93 assert(_regions[index - 1] != NULL, "invariant"); 94 // next_hr_bottom should match the end of the previous region. 95 assert(next_hr_bottom == _regions[index - 1]->end(), "invariant"); 96 } 97 98 HeapRegion* hr; 99 if (index < _length_high_watermark) { 100 // This region should have been previously allocated. 101 assert(_regions[index] != NULL, err_msg("invariant, index: %u", index)); 102 103 hr = _regions[index]; 104 } else { 105 // We have to allocate a new region. 106 assert(_regions[index] == NULL, err_msg("invariant, index: %u", index)); 107 108 hr = g1h->new_heap_region(index, next_hr_bottom); 109 // If allocation fails, bail out and return what we have done so far. 110 if (hr == NULL) break; 111 _regions[index] = hr; 112 } 113 list->add_as_tail(hr); 114 115 index += 1; 116 next_hr_bottom = hr->end(); 117 } 118 119 HeapWord* prev_heap_end = update_heap_end(next_hr_bottom); 120 return MemRegion(prev_heap_end, next_hr_bottom); 121 } 122 123 uint HeapRegionSeq::free_suffix() { 124 uint res = 0; 125 uint index = length(); 126 while (index > 0) { 127 index -= 1; 128 if (!at(index)->is_empty()) break; 129 res += 1; 130 } 131 return res; 132 } 133 134 uint HeapRegionSeq::find_contiguous(uint num) { 135 assert(num > 1, "use this only for sequences of length 2 or greater"); 136 assert(_next_search_index <= length(), 137 err_msg("_next_search_index: %u should be valid and <= than %u", 138 _next_search_index, length())); 139 140 uint start = _next_search_index; 141 uint res = find_contiguous_from(start, num); 142 if (res == G1_NULL_HRS_INDEX && start > 0) { 143 // Try starting from the beginning. If _next_search_index was 0, 144 // no point in doing this again. 145 res = find_contiguous_from(0, num); 146 } 147 if (res != G1_NULL_HRS_INDEX) { 148 assert(res < length(), err_msg("res: %u should be valid", res)); 149 _next_search_index = res + num; 150 assert(_next_search_index <= length(), 151 err_msg("_next_search_index: %u should be valid and <= than %u", 152 _next_search_index, length())); 153 } 154 return res; 155 } 156 157 void HeapRegionSeq::iterate(HeapRegionClosure* blk) const { 158 iterate_from((HeapRegion*) NULL, blk); 159 } 160 161 void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const { 162 uint hr_index = 0; 163 if (hr != NULL) { 164 hr_index = hr->hrs_index(); 165 } 166 167 uint len = length(); 168 for (uint i = hr_index; i < len; i += 1) { 169 bool res = blk->doHeapRegion(at(i)); 170 if (res) { 171 blk->incomplete(); 172 return; 173 } 174 } 175 for (uint i = 0; i < hr_index; i += 1) { 176 bool res = blk->doHeapRegion(at(i)); 177 if (res) { 178 blk->incomplete(); 179 return; 180 } 181 } 182 } 183 184 MemRegion HeapRegionSeq::shrink_to(HeapWord* new_end, 185 uint* num_regions_deleted) { 186 assert(_heap_bottom < new_end && new_end <= _heap_end, 187 err_msg("new_end: "PTR_FORMAT" heap bottom: "PTR_FORMAT" " 188 "heap end: "PTR_FORMAT, new_end, _heap_bottom, _heap_end)); 189 190 // Reset this in case it's currently pointing into the regions that 191 // we just removed. 192 _next_search_index = 0; 193 194 uint new_length = length_for(new_end); 195 uint index = length(); 196 HeapWord* last_hr_bottom = _heap_end; 197 while (index > new_length) { 198 assert(length_for(last_hr_bottom) == index, 199 err_msg("invariant, length_for: "PTR_FORMAT" %u index: %u", 200 last_hr_bottom, length_for(last_hr_bottom), index)); 201 202 HeapRegion* hr = at(index - 1); 203 // We should leave the humongous regions where they are. 204 if (hr->isHumongous()) break; 205 // We should stop shrinking if we come across a non-empty region. 206 if (!hr->is_empty()) break; 207 208 index -= 1; 209 last_hr_bottom = hr->bottom(); 210 } 211 212 *num_regions_deleted = length() - index; 213 214 if (new_end == _heap_end) { 215 assert(*num_regions_deleted == 0, "invariant"); 216 } else { 217 assert(*num_regions_deleted > 0, "invariant"); 218 } 219 220 HeapWord* prev_heap_end = update_heap_end(last_hr_bottom); 221 return MemRegion(last_hr_bottom, prev_heap_end); 222 } 223 224 #ifndef PRODUCT 225 void HeapRegionSeq::verify_optional() { 226 G1HeapSpanningTableBase::verify_optional(); 227 228 guarantee(_next_search_index <= _length, 229 err_msg("invariant: _next_search_index: %u _length: %u", 230 _next_search_index, _length)); 231 232 HeapWord* prev_end = _heap_bottom; 233 for (uint i = 0; i < _length_high_watermark; i += 1) { 234 HeapRegion* hr = _regions[i]; 235 guarantee(hr != NULL, err_msg("invariant: i: %u", i)); 236 guarantee(hr->bottom() == prev_end, 237 err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT, 238 i, HR_FORMAT_PARAMS(hr), prev_end)); 239 guarantee(hr->hrs_index() == i, 240 err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index())); 241 if (i < _length) { 242 // Asserts will fire if i is >= _length 243 HeapWord* addr = hr->bottom(); 244 guarantee(at(addr) == hr, "sanity"); 245 guarantee(at_unsafe(addr) == hr, "sanity"); 246 } else { 247 guarantee(hr->is_empty(), "sanity"); 248 guarantee(!hr->isHumongous(), "sanity"); 249 // using assert instead of guarantee here since containing_set() 250 // is only available in non-product builds. 251 assert(hr->containing_set() == NULL, "sanity"); 252 } 253 if (hr->startsHumongous()) { 254 prev_end = hr->orig_end(); 255 } else { 256 prev_end = hr->end(); 257 } 258 } 259 for (uint i = _length_high_watermark; i < _max_length; i += 1) { 260 guarantee(_regions[i] == NULL, err_msg("invariant i: %u", i)); 261 } 262 } 263 #endif // PRODUCT 264 265 void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* max_end) { 266 initialize_base(bottom, max_end, HeapRegion::LogOfHRGrainBytes); 267 _next_search_index = 0; 268 _regions = create_new_array(); 269 _regions_biased = get_biased_array(_regions); 270 }