1 /* 2 * Copyright (c) 2001, 2010, 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/collectionSetChooser.hpp" 27 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp" 28 #include "gc_implementation/g1/g1CollectorPolicy.hpp" 29 #include "memory/space.inline.hpp" 30 31 CSetChooserCache::CSetChooserCache() { 32 for (int i = 0; i < CacheLength; ++i) 33 _cache[i] = NULL; 34 clear(); 35 } 36 37 void CSetChooserCache::clear() { 38 _occupancy = 0; 39 _first = 0; 40 for (int i = 0; i < CacheLength; ++i) { 41 HeapRegion *hr = _cache[i]; 42 if (hr != NULL) 43 hr->set_sort_index(-1); 44 _cache[i] = NULL; 45 } 46 } 47 48 #ifndef PRODUCT 49 bool CSetChooserCache::verify() { 50 int index = _first; 51 HeapRegion *prev = NULL; 52 for (int i = 0; i < _occupancy; ++i) { 53 guarantee(_cache[index] != NULL, "cache entry should not be empty"); 54 HeapRegion *hr = _cache[index]; 55 guarantee(!hr->is_young(), "should not be young!"); 56 if (prev != NULL) { 57 guarantee(prev->gc_efficiency() >= hr->gc_efficiency(), 58 "cache should be correctly ordered"); 59 } 60 guarantee(hr->sort_index() == get_sort_index(index), 61 "sort index should be correct"); 62 index = trim_index(index + 1); 63 prev = hr; 64 } 65 66 for (int i = 0; i < (CacheLength - _occupancy); ++i) { 67 guarantee(_cache[index] == NULL, "cache entry should be empty"); 68 index = trim_index(index + 1); 69 } 70 71 guarantee(index == _first, "we should have reached where we started from"); 72 return true; 73 } 74 #endif // PRODUCT 75 76 void CSetChooserCache::insert(HeapRegion *hr) { 77 assert(!is_full(), "cache should not be empty"); 78 hr->calc_gc_efficiency(); 79 80 int empty_index; 81 if (_occupancy == 0) { 82 empty_index = _first; 83 } else { 84 empty_index = trim_index(_first + _occupancy); 85 assert(_cache[empty_index] == NULL, "last slot should be empty"); 86 int last_index = trim_index(empty_index - 1); 87 HeapRegion *last = _cache[last_index]; 88 assert(last != NULL,"as the cache is not empty, last should not be empty"); 89 while (empty_index != _first && 90 last->gc_efficiency() < hr->gc_efficiency()) { 91 _cache[empty_index] = last; 92 last->set_sort_index(get_sort_index(empty_index)); 93 empty_index = last_index; 94 last_index = trim_index(last_index - 1); 95 last = _cache[last_index]; 96 } 97 } 98 _cache[empty_index] = hr; 99 hr->set_sort_index(get_sort_index(empty_index)); 100 101 ++_occupancy; 102 assert(verify(), "cache should be consistent"); 103 } 104 105 HeapRegion *CSetChooserCache::remove_first() { 106 if (_occupancy > 0) { 107 assert(_cache[_first] != NULL, "cache should have at least one region"); 108 HeapRegion *ret = _cache[_first]; 109 _cache[_first] = NULL; 110 ret->set_sort_index(-1); 111 --_occupancy; 112 _first = trim_index(_first + 1); 113 assert(verify(), "cache should be consistent"); 114 return ret; 115 } else { 116 return NULL; 117 } 118 } 119 120 // this is a bit expensive... but we expect that it should not be called 121 // to often. 122 void CSetChooserCache::remove(HeapRegion *hr) { 123 assert(_occupancy > 0, "cache should not be empty"); 124 assert(hr->sort_index() < -1, "should already be in the cache"); 125 int index = get_index(hr->sort_index()); 126 assert(_cache[index] == hr, "index should be correct"); 127 int next_index = trim_index(index + 1); 128 int last_index = trim_index(_first + _occupancy - 1); 129 while (index != last_index) { 130 assert(_cache[next_index] != NULL, "should not be null"); 131 _cache[index] = _cache[next_index]; 132 _cache[index]->set_sort_index(get_sort_index(index)); 133 134 index = next_index; 135 next_index = trim_index(next_index+1); 136 } 137 assert(index == last_index, "should have reached the last one"); 138 _cache[index] = NULL; 139 hr->set_sort_index(-1); 140 --_occupancy; 141 assert(verify(), "cache should be consistent"); 142 } 143 144 static inline int orderRegions(HeapRegion* hr1, HeapRegion* hr2) { 145 if (hr1 == NULL) { 146 if (hr2 == NULL) return 0; 147 else return 1; 148 } else if (hr2 == NULL) { 149 return -1; 150 } 151 if (hr2->gc_efficiency() < hr1->gc_efficiency()) return -1; 152 else if (hr1->gc_efficiency() < hr2->gc_efficiency()) return 1; 153 else return 0; 154 } 155 156 static int orderRegions(HeapRegion** hr1p, HeapRegion** hr2p) { 157 return orderRegions(*hr1p, *hr2p); 158 } 159 160 CollectionSetChooser::CollectionSetChooser() : 161 // The line below is the worst bit of C++ hackery I've ever written 162 // (Detlefs, 11/23). You should think of it as equivalent to 163 // "_regions(100, true)": initialize the growable array and inform it 164 // that it should allocate its elem array(s) on the C heap. 165 // 166 // The first argument, however, is actually a comma expression 167 // (set_allocation_type(this, C_HEAP), 100). The purpose of the 168 // set_allocation_type() call is to replace the default allocation 169 // type for embedded objects STACK_OR_EMBEDDED with C_HEAP. It will 170 // allow to pass the assert in GenericGrowableArray() which checks 171 // that a growable array object must be on C heap if elements are. 172 // 173 // Note: containing object is allocated on C heap since it is CHeapObj. 174 // 175 _markedRegions((ResourceObj::set_allocation_type((address)&_markedRegions, 176 ResourceObj::C_HEAP), 177 100), 178 true), 179 _curMarkedIndex(0), 180 _numMarkedRegions(0), 181 _unmarked_age_1_returned_as_new(false), 182 _first_par_unreserved_idx(0) 183 {} 184 185 186 187 #ifndef PRODUCT 188 bool CollectionSetChooser::verify() { 189 int index = 0; 190 guarantee(_curMarkedIndex <= _numMarkedRegions, 191 "_curMarkedIndex should be within bounds"); 192 while (index < _curMarkedIndex) { 193 guarantee(_markedRegions.at(index++) == NULL, 194 "all entries before _curMarkedIndex should be NULL"); 195 } 196 HeapRegion *prev = NULL; 197 while (index < _numMarkedRegions) { 198 HeapRegion *curr = _markedRegions.at(index++); 199 if (curr != NULL) { 200 int si = curr->sort_index(); 201 guarantee(!curr->is_young(), "should not be young!"); 202 guarantee(si > -1 && si == (index-1), "sort index invariant"); 203 if (prev != NULL) { 204 guarantee(orderRegions(prev, curr) != 1, "regions should be sorted"); 205 } 206 prev = curr; 207 } 208 } 209 return _cache.verify(); 210 } 211 #endif 212 213 bool 214 CollectionSetChooser::addRegionToCache() { 215 assert(!_cache.is_full(), "cache should not be full"); 216 217 HeapRegion *hr = NULL; 218 while (hr == NULL && _curMarkedIndex < _numMarkedRegions) { 219 hr = _markedRegions.at(_curMarkedIndex++); 220 } 221 if (hr == NULL) 222 return false; 223 assert(!hr->is_young(), "should not be young!"); 224 assert(hr->sort_index() == _curMarkedIndex-1, "sort_index invariant"); 225 _markedRegions.at_put(hr->sort_index(), NULL); 226 _cache.insert(hr); 227 assert(!_cache.is_empty(), "cache should not be empty"); 228 assert(verify(), "cache should be consistent"); 229 return false; 230 } 231 232 void 233 CollectionSetChooser::fillCache() { 234 while (!_cache.is_full() && addRegionToCache()) { 235 } 236 } 237 238 void 239 CollectionSetChooser::sortMarkedHeapRegions() { 240 guarantee(_cache.is_empty(), "cache should be empty"); 241 // First trim any unused portion of the top in the parallel case. 242 if (_first_par_unreserved_idx > 0) { 243 if (G1PrintParCleanupStats) { 244 gclog_or_tty->print(" Truncating _markedRegions from %d to %d.\n", 245 _markedRegions.length(), _first_par_unreserved_idx); 246 } 247 assert(_first_par_unreserved_idx <= _markedRegions.length(), 248 "Or we didn't reserved enough length"); 249 _markedRegions.trunc_to(_first_par_unreserved_idx); 250 } 251 _markedRegions.sort(orderRegions); 252 assert(_numMarkedRegions <= _markedRegions.length(), "Requirement"); 253 assert(_numMarkedRegions == 0 254 || _markedRegions.at(_numMarkedRegions-1) != NULL, 255 "Testing _numMarkedRegions"); 256 assert(_numMarkedRegions == _markedRegions.length() 257 || _markedRegions.at(_numMarkedRegions) == NULL, 258 "Testing _numMarkedRegions"); 259 if (G1PrintParCleanupStats) { 260 gclog_or_tty->print_cr(" Sorted %d marked regions.", _numMarkedRegions); 261 } 262 for (int i = 0; i < _numMarkedRegions; i++) { 263 assert(_markedRegions.at(i) != NULL, "Should be true by sorting!"); 264 _markedRegions.at(i)->set_sort_index(i); 265 if (G1PrintRegionLivenessInfo > 0) { 266 if (i == 0) gclog_or_tty->print_cr("Sorted marked regions:"); 267 if (i < G1PrintRegionLivenessInfo || 268 (_numMarkedRegions-i) < G1PrintRegionLivenessInfo) { 269 HeapRegion* hr = _markedRegions.at(i); 270 size_t u = hr->used(); 271 gclog_or_tty->print_cr(" Region %d: %d used, %d max live, %5.2f%%.", 272 i, u, hr->max_live_bytes(), 273 100.0*(float)hr->max_live_bytes()/(float)u); 274 } 275 } 276 } 277 if (G1PolicyVerbose > 1) 278 printSortedHeapRegions(); 279 assert(verify(), "should now be sorted"); 280 } 281 282 void 283 printHeapRegion(HeapRegion *hr) { 284 if (hr->isHumongous()) 285 gclog_or_tty->print("H: "); 286 if (hr->in_collection_set()) 287 gclog_or_tty->print("CS: "); 288 gclog_or_tty->print_cr("Region " PTR_FORMAT " (%s%s) " 289 "[" PTR_FORMAT ", " PTR_FORMAT"] " 290 "Used: " SIZE_FORMAT "K, garbage: " SIZE_FORMAT "K.", 291 hr, hr->is_young() ? "Y " : " ", 292 hr->is_marked()? "M1" : "M0", 293 hr->bottom(), hr->end(), 294 hr->used()/K, hr->garbage_bytes()/K); 295 } 296 297 void 298 CollectionSetChooser::addMarkedHeapRegion(HeapRegion* hr) { 299 assert(!hr->isHumongous(), 300 "Humongous regions shouldn't be added to the collection set"); 301 assert(!hr->is_young(), "should not be young!"); 302 _markedRegions.append(hr); 303 _numMarkedRegions++; 304 hr->calc_gc_efficiency(); 305 } 306 307 void 308 CollectionSetChooser:: 309 prepareForAddMarkedHeapRegionsPar(size_t n_regions, size_t chunkSize) { 310 _first_par_unreserved_idx = 0; 311 size_t max_waste = ParallelGCThreads * chunkSize; 312 // it should be aligned with respect to chunkSize 313 size_t aligned_n_regions = 314 (n_regions + (chunkSize - 1)) / chunkSize * chunkSize; 315 assert( aligned_n_regions % chunkSize == 0, "should be aligned" ); 316 _markedRegions.at_put_grow((int)(aligned_n_regions + max_waste - 1), NULL); 317 } 318 319 jint 320 CollectionSetChooser::getParMarkedHeapRegionChunk(jint n_regions) { 321 jint res = Atomic::add(n_regions, &_first_par_unreserved_idx); 322 assert(_markedRegions.length() > res + n_regions - 1, 323 "Should already have been expanded"); 324 return res - n_regions; 325 } 326 327 void 328 CollectionSetChooser::setMarkedHeapRegion(jint index, HeapRegion* hr) { 329 assert(_markedRegions.at(index) == NULL, "precondition"); 330 assert(!hr->is_young(), "should not be young!"); 331 _markedRegions.at_put(index, hr); 332 hr->calc_gc_efficiency(); 333 } 334 335 void 336 CollectionSetChooser::incNumMarkedHeapRegions(jint inc_by) { 337 (void)Atomic::add(inc_by, &_numMarkedRegions); 338 } 339 340 void 341 CollectionSetChooser::clearMarkedHeapRegions(){ 342 for (int i = 0; i < _markedRegions.length(); i++) { 343 HeapRegion* r = _markedRegions.at(i); 344 if (r != NULL) r->set_sort_index(-1); 345 } 346 _markedRegions.clear(); 347 _curMarkedIndex = 0; 348 _numMarkedRegions = 0; 349 _cache.clear(); 350 }; 351 352 void 353 CollectionSetChooser::updateAfterFullCollection() { 354 G1CollectedHeap* g1h = G1CollectedHeap::heap(); 355 clearMarkedHeapRegions(); 356 } 357 358 void 359 CollectionSetChooser::printSortedHeapRegions() { 360 gclog_or_tty->print_cr("Printing %d Heap Regions sorted by amount of known garbage", 361 _numMarkedRegions); 362 363 DEBUG_ONLY(int marked_count = 0;) 364 for (int i = 0; i < _markedRegions.length(); i++) { 365 HeapRegion* r = _markedRegions.at(i); 366 if (r != NULL) { 367 printHeapRegion(r); 368 DEBUG_ONLY(marked_count++;) 369 } 370 } 371 assert(marked_count == _numMarkedRegions, "must be"); 372 gclog_or_tty->print_cr("Done sorted heap region print"); 373 } 374 375 void CollectionSetChooser::removeRegion(HeapRegion *hr) { 376 int si = hr->sort_index(); 377 assert(si == -1 || hr->is_marked(), "Sort index not valid."); 378 if (si > -1) { 379 assert(_markedRegions.at(si) == hr, "Sort index not valid." ); 380 _markedRegions.at_put(si, NULL); 381 } else if (si < -1) { 382 assert(_cache.region_in_cache(hr), "should be in the cache"); 383 _cache.remove(hr); 384 assert(hr->sort_index() == -1, "sort index invariant"); 385 } 386 hr->set_sort_index(-1); 387 } 388 389 // if time_remaining < 0.0, then this method should try to return 390 // a region, whether it fits within the remaining time or not 391 HeapRegion* 392 CollectionSetChooser::getNextMarkedRegion(double time_remaining, 393 double avg_prediction) { 394 G1CollectedHeap* g1h = G1CollectedHeap::heap(); 395 G1CollectorPolicy* g1p = g1h->g1_policy(); 396 fillCache(); 397 if (_cache.is_empty()) { 398 assert(_curMarkedIndex == _numMarkedRegions, 399 "if cache is empty, list should also be empty"); 400 return NULL; 401 } 402 403 HeapRegion *hr = _cache.get_first(); 404 assert(hr != NULL, "if cache not empty, first entry should be non-null"); 405 double predicted_time = g1h->predict_region_elapsed_time_ms(hr, false); 406 407 if (g1p->adaptive_young_list_length()) { 408 if (time_remaining - predicted_time < 0.0) { 409 g1h->check_if_region_is_too_expensive(predicted_time); 410 return NULL; 411 } 412 } else { 413 if (predicted_time > 2.0 * avg_prediction) { 414 return NULL; 415 } 416 } 417 418 HeapRegion *hr2 = _cache.remove_first(); 419 assert(hr == hr2, "cache contents should not have changed"); 420 421 return hr; 422 }