1 /* 2 * Copyright 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/heuristics/shenandoahYoungHeuristics.hpp" 29 #include "gc/shenandoah/shenandoahCollectorPolicy.hpp" 30 #include "gc/shenandoah/shenandoahGenerationalHeap.hpp" 31 #include "gc/shenandoah/shenandoahHeapRegion.inline.hpp" 32 #include "gc/shenandoah/shenandoahOldGeneration.hpp" 33 #include "gc/shenandoah/shenandoahYoungGeneration.hpp" 34 35 #include "utilities/quickSort.hpp" 36 37 ShenandoahYoungHeuristics::ShenandoahYoungHeuristics(ShenandoahYoungGeneration* generation) 38 : ShenandoahGenerationalHeuristics(generation) { 39 } 40 41 42 void ShenandoahYoungHeuristics::choose_collection_set_from_regiondata(ShenandoahCollectionSet* cset, 43 RegionData* data, size_t size, 44 size_t actual_free) { 45 // See comments in ShenandoahAdaptiveHeuristics::choose_collection_set_from_regiondata(): 46 // we do the same here, but with the following adjustments for generational mode: 47 // 48 // In generational mode, the sort order within the data array is not strictly descending amounts 49 // of garbage. In particular, regions that have reached tenure age will be sorted into this 50 // array before younger regions that typically contain more garbage. This is one reason why, 51 // for example, we continue examining regions even after rejecting a region that has 52 // more live data than we can evacuate. 53 54 // Better select garbage-first regions 55 QuickSort::sort<RegionData>(data, (int) size, compare_by_garbage); 56 57 size_t cur_young_garbage = add_preselected_regions_to_collection_set(cset, data, size); 58 59 choose_young_collection_set(cset, data, size, actual_free, cur_young_garbage); 60 61 log_cset_composition(cset); 62 } 63 64 void ShenandoahYoungHeuristics::choose_young_collection_set(ShenandoahCollectionSet* cset, 65 const RegionData* data, 66 size_t size, size_t actual_free, 67 size_t cur_young_garbage) const { 68 69 auto heap = ShenandoahGenerationalHeap::heap(); 70 71 size_t capacity = heap->young_generation()->max_capacity(); 72 size_t garbage_threshold = ShenandoahHeapRegion::region_size_bytes() * ShenandoahGarbageThreshold / 100; 73 size_t ignore_threshold = ShenandoahHeapRegion::region_size_bytes() * ShenandoahIgnoreGarbageThreshold / 100; 74 const uint tenuring_threshold = heap->age_census()->tenuring_threshold(); 75 76 // This is young-gen collection or a mixed evacuation. 77 // If this is mixed evacuation, the old-gen candidate regions have already been added. 78 size_t max_cset = (size_t) (heap->young_generation()->get_evacuation_reserve() / ShenandoahEvacWaste); 79 size_t cur_cset = 0; 80 size_t free_target = (capacity * ShenandoahMinFreeThreshold) / 100 + max_cset; 81 size_t min_garbage = (free_target > actual_free) ? (free_target - actual_free) : 0; 82 83 84 log_info(gc, ergo)( 85 "Adaptive CSet Selection for YOUNG. Max Evacuation: " SIZE_FORMAT "%s, Actual Free: " SIZE_FORMAT "%s.", 86 byte_size_in_proper_unit(max_cset), proper_unit_for_byte_size(max_cset), 87 byte_size_in_proper_unit(actual_free), proper_unit_for_byte_size(actual_free)); 88 89 for (size_t idx = 0; idx < size; idx++) { 90 ShenandoahHeapRegion* r = data[idx].get_region(); 91 if (cset->is_preselected(r->index())) { 92 continue; 93 } 94 if (r->age() < tenuring_threshold) { 95 size_t new_cset = cur_cset + r->get_live_data_bytes(); 96 size_t region_garbage = r->garbage(); 97 size_t new_garbage = cur_young_garbage + region_garbage; 98 bool add_regardless = (region_garbage > ignore_threshold) && (new_garbage < min_garbage); 99 assert(r->is_young(), "Only young candidates expected in the data array"); 100 if ((new_cset <= max_cset) && (add_regardless || (region_garbage > garbage_threshold))) { 101 cur_cset = new_cset; 102 cur_young_garbage = new_garbage; 103 cset->add_region(r); 104 } 105 } 106 // Note that we do not add aged regions if they were not pre-selected. The reason they were not preselected 107 // is because there is not sufficient room in old-gen to hold their to-be-promoted live objects or because 108 // they are to be promoted in place. 109 } 110 } 111 112 113 bool ShenandoahYoungHeuristics::should_start_gc() { 114 auto heap = ShenandoahGenerationalHeap::heap(); 115 ShenandoahOldHeuristics* old_heuristics = heap->old_generation()->heuristics(); 116 117 // Checks that an old cycle has run for at least ShenandoahMinimumOldMarkTimeMs before allowing a young cycle. 118 if (ShenandoahMinimumOldMarkTimeMs > 0 && heap->is_concurrent_old_mark_in_progress()) { 119 size_t old_mark_elapsed = size_t(old_heuristics->elapsed_cycle_time() * 1000); 120 if (old_mark_elapsed < ShenandoahMinimumOldMarkTimeMs) { 121 return false; 122 } 123 } 124 125 // inherited triggers have already decided to start a cycle, so no further evaluation is required 126 if (ShenandoahAdaptiveHeuristics::should_start_gc()) { 127 return true; 128 } 129 130 // Get through promotions and mixed evacuations as quickly as possible. These cycles sometimes require significantly 131 // more time than traditional young-generation cycles so start them up as soon as possible. This is a "mitigation" 132 // for the reality that old-gen and young-gen activities are not truly "concurrent". If there is old-gen work to 133 // be done, we start up the young-gen GC threads so they can do some of this old-gen work. As implemented, promotion 134 // gets priority over old-gen marking. 135 size_t promo_expedite_threshold = percent_of(heap->young_generation()->max_capacity(), ShenandoahExpeditePromotionsThreshold); 136 size_t promo_potential = heap->old_generation()->get_promotion_potential(); 137 if (promo_potential > promo_expedite_threshold) { 138 // Detect unsigned arithmetic underflow 139 assert(promo_potential < heap->capacity(), "Sanity"); 140 log_info(gc)("Trigger (%s): expedite promotion of " SIZE_FORMAT "%s", 141 _space_info->name(), 142 byte_size_in_proper_unit(promo_potential), 143 proper_unit_for_byte_size(promo_potential)); 144 return true; 145 } 146 147 size_t mixed_candidates = old_heuristics->unprocessed_old_collection_candidates(); 148 if (mixed_candidates > ShenandoahExpediteMixedThreshold && !heap->is_concurrent_weak_root_in_progress()) { 149 // We need to run young GC in order to open up some free heap regions so we can finish mixed evacuations. 150 // If concurrent weak root processing is in progress, it means the old cycle has chosen mixed collection 151 // candidates, but has not completed. There is no point in trying to start the young cycle before the old 152 // cycle completes. 153 log_info(gc)("Trigger (%s): expedite mixed evacuation of " SIZE_FORMAT " regions", 154 _space_info->name(), mixed_candidates); 155 return true; 156 } 157 158 return false; 159 } 160 161 // Return a conservative estimate of how much memory can be allocated before we need to start GC. The estimate is based 162 // on memory that is currently available within young generation plus all of the memory that will be added to the young 163 // generation at the end of the current cycle (as represented by young_regions_to_be_reclaimed) and on the anticipated 164 // amount of time required to perform a GC. 165 size_t ShenandoahYoungHeuristics::bytes_of_allocation_runway_before_gc_trigger(size_t young_regions_to_be_reclaimed) { 166 size_t capacity = _space_info->max_capacity(); 167 size_t usage = _space_info->used(); 168 size_t available = (capacity > usage)? capacity - usage: 0; 169 size_t allocated = _space_info->bytes_allocated_since_gc_start(); 170 171 size_t available_young_collected = ShenandoahHeap::heap()->collection_set()->get_young_available_bytes_collected(); 172 size_t anticipated_available = 173 available + young_regions_to_be_reclaimed * ShenandoahHeapRegion::region_size_bytes() - available_young_collected; 174 size_t spike_headroom = capacity * ShenandoahAllocSpikeFactor / 100; 175 size_t penalties = capacity * _gc_time_penalties / 100; 176 177 double rate = _allocation_rate.sample(allocated); 178 179 // At what value of available, would avg and spike triggers occur? 180 // if allocation_headroom < avg_cycle_time * avg_alloc_rate, then we experience avg trigger 181 // if allocation_headroom < avg_cycle_time * rate, then we experience spike trigger if is_spiking 182 // 183 // allocation_headroom = 184 // 0, if penalties > available or if penalties + spike_headroom > available 185 // available - penalties - spike_headroom, otherwise 186 // 187 // so we trigger if available - penalties - spike_headroom < avg_cycle_time * avg_alloc_rate, which is to say 188 // available < avg_cycle_time * avg_alloc_rate + penalties + spike_headroom 189 // or if available < penalties + spike_headroom 190 // 191 // since avg_cycle_time * avg_alloc_rate > 0, the first test is sufficient to test both conditions 192 // 193 // thus, evac_slack_avg is MIN2(0, available - avg_cycle_time * avg_alloc_rate + penalties + spike_headroom) 194 // 195 // similarly, evac_slack_spiking is MIN2(0, available - avg_cycle_time * rate + penalties + spike_headroom) 196 // but evac_slack_spiking is only relevant if is_spiking, as defined below. 197 198 double avg_cycle_time = _gc_cycle_time_history->davg() + (_margin_of_error_sd * _gc_cycle_time_history->dsd()); 199 double avg_alloc_rate = _allocation_rate.upper_bound(_margin_of_error_sd); 200 size_t evac_slack_avg; 201 if (anticipated_available > avg_cycle_time * avg_alloc_rate + penalties + spike_headroom) { 202 evac_slack_avg = anticipated_available - (avg_cycle_time * avg_alloc_rate + penalties + spike_headroom); 203 } else { 204 // we have no slack because it's already time to trigger 205 evac_slack_avg = 0; 206 } 207 208 bool is_spiking = _allocation_rate.is_spiking(rate, _spike_threshold_sd); 209 size_t evac_slack_spiking; 210 if (is_spiking) { 211 if (anticipated_available > avg_cycle_time * rate + penalties + spike_headroom) { 212 evac_slack_spiking = anticipated_available - (avg_cycle_time * rate + penalties + spike_headroom); 213 } else { 214 // we have no slack because it's already time to trigger 215 evac_slack_spiking = 0; 216 } 217 } else { 218 evac_slack_spiking = evac_slack_avg; 219 } 220 221 size_t threshold = min_free_threshold(); 222 size_t evac_min_threshold = (anticipated_available > threshold)? anticipated_available - threshold: 0; 223 return MIN3(evac_slack_spiking, evac_slack_avg, evac_min_threshold); 224 } 225