1 /* 2 * Copyright (c) 2021, Amazon.com, Inc. 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 27 #include "gc/shenandoah/heuristics/shenandoahOldHeuristics.hpp" 28 #include "gc/shenandoah/shenandoahCollectionSet.hpp" 29 #include "gc/shenandoah/shenandoahHeap.hpp" 30 #include "gc/shenandoah/shenandoahHeapRegion.inline.hpp" 31 #include "gc/shenandoah/shenandoahOldGeneration.hpp" 32 #include "gc/shenandoah/shenandoahYoungGeneration.hpp" 33 #include "utilities/quickSort.hpp" 34 35 uint ShenandoahOldHeuristics::NOT_FOUND = -1U; 36 37 ShenandoahOldHeuristics::ShenandoahOldHeuristics(ShenandoahOldGeneration* generation, ShenandoahHeuristics* trigger_heuristic) : 38 ShenandoahHeuristics(generation), 39 _first_pinned_candidate(NOT_FOUND), 40 _last_old_collection_candidate(0), 41 _next_old_collection_candidate(0), 42 _last_old_region(0), 43 _trigger_heuristic(trigger_heuristic), 44 _promotion_failed(false), 45 _old_generation(generation) 46 { 47 assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics"); 48 } 49 50 bool ShenandoahOldHeuristics::prime_collection_set(ShenandoahCollectionSet* collection_set) { 51 if (unprocessed_old_collection_candidates() == 0) { 52 return false; 53 } 54 55 _first_pinned_candidate = NOT_FOUND; 56 57 ShenandoahHeap* heap = ShenandoahHeap::heap(); 58 uint included_old_regions = 0; 59 size_t evacuated_old_bytes = 0; 60 size_t collected_old_bytes = 0; 61 62 // If a region is put into the collection set, then this region's free (not yet used) bytes are no longer 63 // "available" to hold the results of other evacuations. This may cause a decrease in the remaining amount 64 // of memory that can still be evacuated. We address this by reducing the evacuation budget by the amount 65 // of live memory in that region and by the amount of unallocated memory in that region if the evacuation 66 // budget is constrained by availability of free memory. 67 size_t old_evacuation_budget = (size_t) ((double) heap->get_old_evac_reserve() / ShenandoahEvacWaste); 68 size_t remaining_old_evacuation_budget = old_evacuation_budget; 69 size_t lost_evacuation_capacity = 0; 70 log_info(gc)("Choose old regions for mixed collection: old evacuation budget: " SIZE_FORMAT "%s, candidates: %u", 71 byte_size_in_proper_unit(old_evacuation_budget), proper_unit_for_byte_size(old_evacuation_budget), 72 unprocessed_old_collection_candidates()); 73 74 // The number of old-gen regions that were selected as candidates for collection at the end of the most recent old-gen 75 // concurrent marking phase and have not yet been collected is represented by unprocessed_old_collection_candidates() 76 while (unprocessed_old_collection_candidates() > 0) { 77 // Old collection candidates are sorted in order of decreasing garbage contained therein. 78 ShenandoahHeapRegion* r = next_old_collection_candidate(); 79 if (r == nullptr) { 80 break; 81 } 82 83 // If we choose region r to be collected, then we need to decrease the capacity to hold other evacuations by 84 // the size of r's free memory. 85 86 // It's probably overkill to compensate with lost_evacuation_capacity. But it's the safe thing to do and 87 // has minimal impact on content of primed collection set. 88 if (r->get_live_data_bytes() + lost_evacuation_capacity <= remaining_old_evacuation_budget) { 89 // Decrement remaining evacuation budget by bytes that will be copied. 90 lost_evacuation_capacity += r->free(); 91 remaining_old_evacuation_budget -= r->get_live_data_bytes(); 92 collection_set->add_region(r); 93 included_old_regions++; 94 evacuated_old_bytes += r->get_live_data_bytes(); 95 collected_old_bytes += r->garbage(); 96 consume_old_collection_candidate(); 97 } else { 98 break; 99 } 100 } 101 102 if (_first_pinned_candidate != NOT_FOUND) { 103 // Need to deal with pinned regions 104 slide_pinned_regions_to_front(); 105 } 106 107 if (included_old_regions > 0) { 108 log_info(gc)("Old-gen piggyback evac (" UINT32_FORMAT " regions, evacuating " SIZE_FORMAT "%s, reclaiming: " SIZE_FORMAT "%s)", 109 included_old_regions, 110 byte_size_in_proper_unit(evacuated_old_bytes), proper_unit_for_byte_size(evacuated_old_bytes), 111 byte_size_in_proper_unit(collected_old_bytes), proper_unit_for_byte_size(collected_old_bytes)); 112 } 113 114 if (unprocessed_old_collection_candidates() == 0) { 115 _old_generation->transition_to(ShenandoahOldGeneration::IDLE); 116 } 117 118 return (included_old_regions > 0); 119 } 120 121 void ShenandoahOldHeuristics::slide_pinned_regions_to_front() { 122 // Find the first unpinned region to the left of the next region that 123 // will be added to the collection set. These regions will have been 124 // added to the cset, so we can use them to hold pointers to regions 125 // that were pinned when the cset was chosen. 126 // [ r p r p p p r r ] 127 // ^ ^ ^ 128 // | | | pointer to next region to add to a mixed collection is here. 129 // | | first r to the left should be in the collection set now. 130 // | first pinned region, we don't need to look past this 131 uint write_index = NOT_FOUND; 132 for (uint search = _next_old_collection_candidate - 1; search > _first_pinned_candidate; --search) { 133 ShenandoahHeapRegion* region = _region_data[search]._region; 134 if (!region->is_pinned()) { 135 write_index = search; 136 assert(region->is_cset(), "Expected unpinned region to be added to the collection set."); 137 break; 138 } 139 } 140 141 // If we could not find an unpinned region, it means there are no slots available 142 // to move up the pinned regions. In this case, we just reset our next index in the 143 // hopes that some of these regions will become unpinned before the next mixed 144 // collection. We may want to bailout of here instead, as it should be quite 145 // rare to have so many pinned regions and may indicate something is wrong. 146 if (write_index == NOT_FOUND) { 147 assert(_first_pinned_candidate != NOT_FOUND, "Should only be here if there are pinned regions."); 148 _next_old_collection_candidate = _first_pinned_candidate; 149 return; 150 } 151 152 // Find pinned regions to the left and move their pointer into a slot 153 // that was pointing at a region that has been added to the cset (or was pointing 154 // to a pinned region that we've already moved up). We are done when the leftmost 155 // pinned region has been slid up. 156 // [ r p r x p p p r ] 157 // ^ ^ 158 // | | next region for mixed collections 159 // | Write pointer is here. We know this region is already in the cset 160 // | so we can clobber it with the next pinned region we find. 161 for (int32_t search = write_index - 1; search >= (int32_t)_first_pinned_candidate; --search) { 162 RegionData& skipped = _region_data[search]; 163 if (skipped._region->is_pinned()) { 164 RegionData& available_slot = _region_data[write_index]; 165 available_slot._region = skipped._region; 166 available_slot._garbage = skipped._garbage; 167 --write_index; 168 } 169 } 170 171 // Update to read from the leftmost pinned region. Plus one here because we decremented 172 // the write index to hold the next found pinned region. We are just moving it back now 173 // to point to the first pinned region. 174 _next_old_collection_candidate = write_index + 1; 175 } 176 177 // Both arguments are don't cares for old-gen collections 178 void ShenandoahOldHeuristics::choose_collection_set(ShenandoahCollectionSet* collection_set, 179 ShenandoahOldHeuristics* old_heuristics) { 180 assert((collection_set == nullptr) && (old_heuristics == nullptr), 181 "Expect null arguments in ShenandoahOldHeuristics::choose_collection_set()"); 182 // Old-gen doesn't actually choose a collection set to be evacuated by its own gang of worker tasks. 183 // Instead, it computes the set of regions to be evacuated by subsequent young-gen evacuation passes. 184 prepare_for_old_collections(); 185 } 186 187 void ShenandoahOldHeuristics::prepare_for_old_collections() { 188 assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics"); 189 ShenandoahHeap* heap = ShenandoahHeap::heap(); 190 191 size_t cand_idx = 0; 192 size_t total_garbage = 0; 193 size_t num_regions = heap->num_regions(); 194 size_t immediate_garbage = 0; 195 size_t immediate_regions = 0; 196 197 RegionData* candidates = _region_data; 198 for (size_t i = 0; i < num_regions; i++) { 199 ShenandoahHeapRegion* region = heap->get_region(i); 200 if (!in_generation(region)) { 201 continue; 202 } 203 204 size_t garbage = region->garbage(); 205 total_garbage += garbage; 206 207 if (region->is_regular() || region->is_pinned()) { 208 if (!region->has_live()) { 209 assert(!region->is_pinned(), "Pinned region should have live (pinned) objects."); 210 region->make_trash_immediate(); 211 immediate_regions++; 212 immediate_garbage += garbage; 213 } else { 214 region->begin_preemptible_coalesce_and_fill(); 215 candidates[cand_idx]._region = region; 216 candidates[cand_idx]._garbage = garbage; 217 cand_idx++; 218 } 219 } else if (region->is_humongous_start()) { 220 if (!region->has_live()) { 221 // The humongous object is dead, we can just return this region and the continuations 222 // immediately to the freeset - no evacuations are necessary here. The continuations 223 // will be made into trash by this method, so they'll be skipped by the 'is_regular' 224 // check above, but we still need to count the start region. 225 immediate_regions++; 226 immediate_garbage += garbage; 227 size_t region_count = heap->trash_humongous_region_at(region); 228 log_debug(gc)("Trashed " SIZE_FORMAT " regions for humongous object.", region_count); 229 } 230 } else if (region->is_trash()) { 231 // Count humongous objects made into trash here. 232 immediate_regions++; 233 immediate_garbage += garbage; 234 } 235 } 236 237 // TODO: Consider not running mixed collects if we recovered some threshold percentage of memory from immediate garbage. 238 // This would be similar to young and global collections shortcutting evacuation, though we'd probably want a separate 239 // threshold for the old generation. 240 241 // Prioritize regions to select garbage-first regions 242 QuickSort::sort<RegionData>(candidates, cand_idx, compare_by_garbage, false); 243 244 // Any old-gen region that contains (ShenandoahOldGarbageThreshold (default value 25))% garbage or more is to 245 // be evacuated. 246 // 247 // TODO: allow ShenandoahOldGarbageThreshold to be determined adaptively, by heuristics. 248 249 250 const size_t garbage_threshold = ShenandoahHeapRegion::region_size_bytes() * ShenandoahOldGarbageThreshold / 100; 251 size_t candidates_garbage = 0; 252 _last_old_region = (uint)cand_idx; 253 _last_old_collection_candidate = (uint)cand_idx; 254 _next_old_collection_candidate = 0; 255 256 for (size_t i = 0; i < cand_idx; i++) { 257 if (candidates[i]._garbage < garbage_threshold) { 258 // Candidates are sorted in decreasing order of garbage, so no regions after this will be above the threshold 259 _last_old_collection_candidate = (uint)i; 260 break; 261 } 262 candidates_garbage += candidates[i]._garbage; 263 } 264 265 // Note that we do not coalesce and fill occupied humongous regions 266 // HR: humongous regions, RR: regular regions, CF: coalesce and fill regions 267 size_t collectable_garbage = immediate_garbage + candidates_garbage; 268 log_info(gc)("Old-Gen Collectable Garbage: " SIZE_FORMAT "%s over " UINT32_FORMAT " regions, " 269 "Old-Gen Immediate Garbage: " SIZE_FORMAT "%s over " SIZE_FORMAT " regions.", 270 byte_size_in_proper_unit(collectable_garbage), proper_unit_for_byte_size(collectable_garbage), _last_old_collection_candidate, 271 byte_size_in_proper_unit(immediate_garbage), proper_unit_for_byte_size(immediate_garbage), immediate_regions); 272 273 if (unprocessed_old_collection_candidates() == 0) { 274 _old_generation->transition_to(ShenandoahOldGeneration::IDLE); 275 } else { 276 _old_generation->transition_to(ShenandoahOldGeneration::WAITING); 277 } 278 } 279 280 uint ShenandoahOldHeuristics::last_old_collection_candidate_index() { 281 return _last_old_collection_candidate; 282 } 283 284 uint ShenandoahOldHeuristics::unprocessed_old_collection_candidates() { 285 return _last_old_collection_candidate - _next_old_collection_candidate; 286 } 287 288 ShenandoahHeapRegion* ShenandoahOldHeuristics::next_old_collection_candidate() { 289 while (_next_old_collection_candidate < _last_old_collection_candidate) { 290 ShenandoahHeapRegion* next = _region_data[_next_old_collection_candidate]._region; 291 if (!next->is_pinned()) { 292 return next; 293 } else { 294 assert(next->is_pinned(), "sanity"); 295 if (_first_pinned_candidate == NOT_FOUND) { 296 _first_pinned_candidate = _next_old_collection_candidate; 297 } 298 } 299 300 _next_old_collection_candidate++; 301 } 302 return nullptr; 303 } 304 305 void ShenandoahOldHeuristics::consume_old_collection_candidate() { 306 _next_old_collection_candidate++; 307 } 308 309 uint ShenandoahOldHeuristics::last_old_region_index() const { 310 return _last_old_region; 311 } 312 313 unsigned int ShenandoahOldHeuristics::get_coalesce_and_fill_candidates(ShenandoahHeapRegion** buffer) { 314 uint end = _last_old_region; 315 uint index = _next_old_collection_candidate; 316 while (index < end) { 317 *buffer++ = _region_data[index++]._region; 318 } 319 return _last_old_region - _next_old_collection_candidate; 320 } 321 322 void ShenandoahOldHeuristics::abandon_collection_candidates() { 323 _last_old_collection_candidate = 0; 324 _next_old_collection_candidate = 0; 325 _last_old_region = 0; 326 } 327 328 void ShenandoahOldHeuristics::handle_promotion_failure() { 329 if (!_promotion_failed) { 330 if (ShenandoahHeap::heap()->generation_sizer()->transfer_capacity(_old_generation)) { 331 log_info(gc)("Increased size of old generation due to promotion failure."); 332 } 333 // TODO: Increase tenuring threshold to push back on promotions. 334 } 335 _promotion_failed = true; 336 } 337 338 void ShenandoahOldHeuristics::record_cycle_start() { 339 _promotion_failed = false; 340 _trigger_heuristic->record_cycle_start(); 341 } 342 343 void ShenandoahOldHeuristics::record_cycle_end() { 344 _trigger_heuristic->record_cycle_end(); 345 } 346 347 bool ShenandoahOldHeuristics::should_start_gc() { 348 // Cannot start a new old-gen GC until previous one has finished. 349 // 350 // Future refinement: under certain circumstances, we might be more sophisticated about this choice. 351 // For example, we could choose to abandon the previous old collection before it has completed evacuations. 352 if (unprocessed_old_collection_candidates() > 0) { 353 return false; 354 } 355 356 // If there's been a promotion failure (and we don't have regions already scheduled for evacuation), 357 // start a new old generation collection. 358 if (_promotion_failed) { 359 log_info(gc)("Trigger: Promotion Failure"); 360 return true; 361 } 362 363 // Otherwise, defer to configured heuristic for gc trigger. 364 return _trigger_heuristic->should_start_gc(); 365 } 366 367 bool ShenandoahOldHeuristics::should_degenerate_cycle() { 368 return _trigger_heuristic->should_degenerate_cycle(); 369 } 370 371 void ShenandoahOldHeuristics::record_success_concurrent(bool abbreviated) { 372 _trigger_heuristic->record_success_concurrent(abbreviated); 373 } 374 375 void ShenandoahOldHeuristics::record_success_degenerated() { 376 _trigger_heuristic->record_success_degenerated(); 377 } 378 379 void ShenandoahOldHeuristics::record_success_full() { 380 _trigger_heuristic->record_success_full(); 381 } 382 383 void ShenandoahOldHeuristics::record_allocation_failure_gc() { 384 _trigger_heuristic->record_allocation_failure_gc(); 385 } 386 387 void ShenandoahOldHeuristics::record_requested_gc() { 388 _trigger_heuristic->record_requested_gc(); 389 } 390 391 void ShenandoahOldHeuristics::reset_gc_learning() { 392 _trigger_heuristic->reset_gc_learning(); 393 } 394 395 bool ShenandoahOldHeuristics::can_unload_classes() { 396 return _trigger_heuristic->can_unload_classes(); 397 } 398 399 bool ShenandoahOldHeuristics::can_unload_classes_normal() { 400 return _trigger_heuristic->can_unload_classes_normal(); 401 } 402 403 bool ShenandoahOldHeuristics::should_unload_classes() { 404 return _trigger_heuristic->should_unload_classes(); 405 } 406 407 const char* ShenandoahOldHeuristics::name() { 408 static char name[128]; 409 jio_snprintf(name, sizeof(name), "%s (OLD)", _trigger_heuristic->name()); 410 return name; 411 } 412 413 bool ShenandoahOldHeuristics::is_diagnostic() { 414 return false; 415 } 416 417 bool ShenandoahOldHeuristics::is_experimental() { 418 return true; 419 } 420 421 void ShenandoahOldHeuristics::choose_collection_set_from_regiondata(ShenandoahCollectionSet* set, 422 ShenandoahHeuristics::RegionData* data, 423 size_t data_size, size_t free) { 424 ShouldNotReachHere(); 425 } 426 427