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