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/shenandoahGeneration.hpp"
 29 #include "gc/shenandoah/shenandoahOldGeneration.hpp"
 30 #include "gc/shenandoah/shenandoahYoungGeneration.hpp"
 31 #include "utilities/quickSort.hpp"
 32 
 33 ShenandoahOldHeuristics::ShenandoahOldHeuristics(ShenandoahGeneration* generation, ShenandoahHeuristics* trigger_heuristic) :
 34     ShenandoahHeuristics(generation),
 35     _old_collection_candidates(0),
 36     _next_old_collection_candidate(0),
 37     _hidden_old_collection_candidates(0),
 38     _hidden_next_old_collection_candidate(0),
 39     _old_coalesce_and_fill_candidates(0),
 40     _first_coalesce_and_fill_candidate(0),
 41     _trigger_heuristic(trigger_heuristic),
 42     _promotion_failed(false)
 43 {
 44 }
 45 
 46 bool ShenandoahOldHeuristics::prime_collection_set(ShenandoahCollectionSet* collection_set) {
 47   if (unprocessed_old_collection_candidates() == 0) {
 48     return false;
 49   }
 50 
 51   ShenandoahHeap* heap = ShenandoahHeap::heap();
 52   uint included_old_regions = 0;
 53   size_t evacuated_old_bytes = 0;
 54 
 55   // TODO:
 56   // The max_old_evacuation_bytes and promotion_budget_bytes constants represent a first
 57   // approximation to desired operating parameters.  Eventually, these values should be determined
 58   // by heuristics and should adjust dynamically based on most current execution behavior.  In the
 59   // interim, we offer command-line options to set the values of these configuration parameters.
 60 
 61   // max_old_evacuation_bytes represents a bound on how much evacuation effort is dedicated
 62   // to old-gen regions.
 63   size_t max_old_evacuation_bytes = (heap->old_generation()->soft_max_capacity() * ShenandoahOldEvacReserve) / 100;
 64   const size_t young_evacuation_bytes = (heap->young_generation()->soft_max_capacity() * ShenandoahEvacReserve) / 100;
 65   const size_t ratio_bound_on_old_evac_bytes = (young_evacuation_bytes * ShenandoahOldEvacRatioPercent) / 100;
 66   if (max_old_evacuation_bytes > ratio_bound_on_old_evac_bytes) {
 67     max_old_evacuation_bytes = ratio_bound_on_old_evac_bytes;
 68   }
 69 
 70   // Usually, old-evacuation is limited by the CPU bounds on effort.  However, it can also be bounded by available
 71   // memory within old-gen to hold the results of evacuation.  When we are bound by memory availability, we need
 72   // to account below for the loss of available memory from within each region that is added to the old-gen collection
 73   // set.
 74   size_t old_available = heap->old_generation()->available();
 75   size_t excess_old_capacity_for_evacuation;
 76   if (max_old_evacuation_bytes > old_available) {
 77     max_old_evacuation_bytes = old_available;
 78     excess_old_capacity_for_evacuation = 0;
 79   } else {
 80     excess_old_capacity_for_evacuation = old_available - max_old_evacuation_bytes;
 81   }
 82 
 83   // promotion_budget_bytes represents an "arbitrary" bound on how many bytes can be consumed by young-gen
 84   // objects promoted into old-gen memory.  We need to avoid a scenario under which promotion of objects
 85   // depletes old-gen available memory to the point that there is insufficient memory to hold old-gen objects
 86   // that need to be evacuated from within the old-gen collection set.
 87   //
 88   // Key idea: if there is not sufficient memory within old-gen to hold an object that wants to be promoted, defer
 89   // promotion until a subsequent evacuation pass.  Enforcement is provided at the time PLABs and shared allocations
 90   // in old-gen memory are requested.
 91 
 92   const size_t promotion_budget_bytes = heap->get_promotion_reserve();
 93 
 94   // old_evacuation_budget is an upper bound on the amount of live memory that can be evacuated.
 95   //
 96   // If a region is put into the collection set, then this region's free (not yet used) bytes are no longer
 97   // "available" to hold the results of other evacuations.  This may cause a decrease in the remaining amount
 98   // of memory that can still be evacuated.  We address this by reducing the evacuation budget by the amount
 99   // of live memory in that region and by the amount of unallocated memory in that region if the evacuation
100   // budget is constrained by availability of free memory.  See remaining_old_evacuation_budget below.
101 
102   size_t old_evacuation_budget = (size_t) (max_old_evacuation_bytes / ShenandoahEvacWaste);
103 
104   log_info(gc)("Choose old regions for mixed collection: old evacuation budget: " SIZE_FORMAT "%s",
105                 byte_size_in_proper_unit(old_evacuation_budget), proper_unit_for_byte_size(old_evacuation_budget));
106 
107   size_t remaining_old_evacuation_budget = old_evacuation_budget;
108   size_t lost_evacuation_capacity = 0;
109 
110   // The number of old-gen regions that were selected as candidates for collection at the end of the most recent
111   // old-gen concurrent marking phase and have not yet been collected is represented by
112   // unprocessed_old_collection_candidates()
113   while (unprocessed_old_collection_candidates() > 0) {
114     // Old collection candidates are sorted in order of decreasing garbage contained therein.
115     ShenandoahHeapRegion* r = next_old_collection_candidate();
116 
117 
118     // If we choose region r to be collected, then we need to decrease the capacity to hold other evacuations by
119     // the size of r's free memory.
120     if ((r->get_live_data_bytes() <= remaining_old_evacuation_budget) &&
121         ((lost_evacuation_capacity + r->free() <= excess_old_capacity_for_evacuation)
122          || (r->get_live_data_bytes() + r->free() <= remaining_old_evacuation_budget))) {
123 
124       // Decrement remaining evacuation budget by bytes that will be copied.  If the cumulative loss of free memory from
125       // regions that are to be collected exceeds excess_old_capacity_for_evacuation,  decrease
126       // remaining_old_evacuation_budget by this loss as well.
127       lost_evacuation_capacity += r->free();
128       remaining_old_evacuation_budget -= r->get_live_data_bytes();
129       if (lost_evacuation_capacity > excess_old_capacity_for_evacuation) {
130         // This is slightly conservative because we really only need to remove from the remaining evacuation budget
131         // the amount by which lost_evacution_capacity exceeds excess_old_capacity_for_evacuation, but this is relatively
132         // rare event and current thought is to be a bit conservative rather than mess up the math on code that is so
133         // difficult to test and maintain...
134 
135         // Once we have crossed the threshold of lost_evacuation_capacity exceeding excess_old_capacity_for_evacuation,
136         // every subsequent iteration of this loop will further decrease remaining_old_evacuation_budget.
137         remaining_old_evacuation_budget -= r->free();
138       }
139       collection_set->add_region(r);
140       included_old_regions++;
141       evacuated_old_bytes += r->get_live_data_bytes();
142       consume_old_collection_candidate();
143     } else {
144       break;
145     }
146   }
147 
148   if (included_old_regions > 0) {
149     log_info(gc)("Old-gen piggyback evac (" UINT32_FORMAT " regions, " SIZE_FORMAT " %s)",
150                  included_old_regions, byte_size_in_proper_unit(evacuated_old_bytes), proper_unit_for_byte_size(evacuated_old_bytes));
151   }
152   return (included_old_regions > 0);
153 }
154 
155 // Both arguments are don't cares for old-gen collections
156 void ShenandoahOldHeuristics::choose_collection_set(ShenandoahCollectionSet* collection_set,
157                                                     ShenandoahOldHeuristics* old_heuristics) {
158   assert((collection_set == nullptr) && (old_heuristics == nullptr),
159          "Expect null arguments in ShenandoahOldHeuristics::choose_collection_set()");
160   // Old-gen doesn't actually choose a collection set to be evacuated by its own gang of worker tasks.
161   // Instead, it computes the set of regions to be evacuated by subsequent young-gen evacuation passes.
162   prepare_for_old_collections();
163 }
164 
165 void ShenandoahOldHeuristics::prepare_for_old_collections() {
166   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
167   ShenandoahHeap* heap = ShenandoahHeap::heap();
168 
169   size_t cand_idx = 0;
170   size_t total_garbage = 0;
171   size_t num_regions = heap->num_regions();
172   size_t immediate_garbage = 0;
173   size_t immediate_regions = 0;
174 
175   RegionData* candidates = _region_data;
176   for (size_t i = 0; i < num_regions; i++) {
177     ShenandoahHeapRegion* region = heap->get_region(i);
178     if (!in_generation(region)) {
179       continue;
180     }
181 
182     size_t garbage = region->garbage();
183     total_garbage += garbage;
184 
185     if (region->is_regular()) {
186       if (!region->has_live()) {
187         region->make_trash_immediate();
188         immediate_regions++;
189         immediate_garbage += garbage;
190       } else {
191         region->begin_preemptible_coalesce_and_fill();
192         candidates[cand_idx]._region = region;
193         candidates[cand_idx]._garbage = garbage;
194         cand_idx++;
195       }
196     } else if (region->is_humongous_start()) {
197       if (!region->has_live()) {
198         // The humongous object is dead, we can just return this region and the continuations
199         // immediately to the freeset - no evacuations are necessary here. The continuations
200         // will be made into trash by this method, so they'll be skipped by the 'is_regular'
201         // check above.
202         size_t region_count = heap->trash_humongous_region_at(region);
203         log_debug(gc)("Trashed " SIZE_FORMAT " regions for humongous object.", region_count);
204       }
205     } else if (region->is_trash()) {
206       // Count humongous objects made into trash here.
207       immediate_regions++;
208       immediate_garbage += garbage;
209     }
210   }
211 
212   // TODO: Consider not running mixed collects if we recovered some threshold percentage of memory from immediate garbage.
213   // This would be similar to young and global collections shortcutting evacuation, though we'd probably want a separate
214   // threshold for the old generation.
215 
216   // Prioritize regions to select garbage-first regions
217   QuickSort::sort<RegionData>(candidates, cand_idx, compare_by_garbage, false);
218 
219   // Any old-gen region that contains (ShenandoahOldGarbageThreshold (default value 25))% garbage or more is to
220   // be evacuated.
221   //
222   // TODO: allow ShenandoahOldGarbageThreshold to be determined adaptively, by heuristics.
223 
224   const size_t garbage_threshold = ShenandoahHeapRegion::region_size_bytes() * ShenandoahOldGarbageThreshold / 100;
225   size_t candidates_garbage = 0;
226   for (size_t i = 0; i < cand_idx; i++) {
227     candidates_garbage += candidates[i]._garbage;
228     if (candidates[i]._garbage < garbage_threshold) {
229       // Candidates are sorted in decreasing order of garbage, so no regions after this will be above the threshold
230       _hidden_next_old_collection_candidate = 0;
231       _hidden_old_collection_candidates = (uint)i;
232       _first_coalesce_and_fill_candidate = (uint)i;
233       _old_coalesce_and_fill_candidates = (uint)(cand_idx - i);
234 
235       // Note that we do not coalesce and fill occupied humongous regions
236       // HR: humongous regions, RR: regular regions, CF: coalesce and fill regions
237       log_info(gc)("Old-gen mark evac (" UINT32_FORMAT " RR, " UINT32_FORMAT " CF)",
238                    _hidden_old_collection_candidates, _old_coalesce_and_fill_candidates);
239       return;
240     }
241   }
242 
243   // If we reach here, all of non-humogous old-gen regions are candidates for collection set.
244   _hidden_next_old_collection_candidate = 0;
245   _hidden_old_collection_candidates = (uint)cand_idx;
246   _first_coalesce_and_fill_candidate = 0;
247   _old_coalesce_and_fill_candidates = 0;
248 
249   // Note that we do not coalesce and fill occupied humongous regions
250   // HR: humongous regions, RR: regular regions, CF: coalesce and fill regions
251   size_t collectable_garbage = immediate_garbage + candidates_garbage;
252   log_info(gc)("Old-gen mark evac (" UINT32_FORMAT " RR, " UINT32_FORMAT " CF), "
253                "Collectable Garbage: " SIZE_FORMAT "%s, "
254                "Immediate Garbage: " SIZE_FORMAT "%s",
255                _hidden_old_collection_candidates, _old_coalesce_and_fill_candidates,
256                byte_size_in_proper_unit(collectable_garbage), proper_unit_for_byte_size(collectable_garbage),
257                byte_size_in_proper_unit(immediate_garbage), proper_unit_for_byte_size(immediate_garbage));
258 }
259 
260 void ShenandoahOldHeuristics::start_old_evacuations() {
261   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
262 
263   _old_collection_candidates = _hidden_old_collection_candidates;
264   _next_old_collection_candidate = _hidden_next_old_collection_candidate;
265 
266   _hidden_old_collection_candidates = 0;
267 }
268 
269 uint ShenandoahOldHeuristics::unprocessed_old_or_hidden_collection_candidates() {
270   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
271   return _old_collection_candidates + _hidden_old_collection_candidates;
272 }
273 
274 uint ShenandoahOldHeuristics::unprocessed_old_collection_candidates() {
275   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
276   return _old_collection_candidates;
277 }
278 
279 ShenandoahHeapRegion* ShenandoahOldHeuristics::next_old_collection_candidate() {
280   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
281   return _region_data[_next_old_collection_candidate]._region;
282 }
283 
284 void ShenandoahOldHeuristics::consume_old_collection_candidate() {
285   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
286   _next_old_collection_candidate++;
287   _old_collection_candidates--;
288 }
289 
290 uint ShenandoahOldHeuristics::old_coalesce_and_fill_candidates() {
291   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
292   return _old_coalesce_and_fill_candidates;
293 }
294 
295 void ShenandoahOldHeuristics::get_coalesce_and_fill_candidates(ShenandoahHeapRegion** buffer) {
296   assert(_generation->generation_mode() == OLD, "This service only available for old-gc heuristics");
297   uint count = _old_coalesce_and_fill_candidates;
298   int index = _first_coalesce_and_fill_candidate;
299   while (count-- > 0) {
300     *buffer++ = _region_data[index++]._region;
301   }
302 }
303 
304 void ShenandoahOldHeuristics::abandon_collection_candidates() {
305   _old_collection_candidates = 0;
306   _next_old_collection_candidate = 0;
307   _hidden_old_collection_candidates = 0;
308   _hidden_next_old_collection_candidate = 0;
309   _old_coalesce_and_fill_candidates = 0;
310   _first_coalesce_and_fill_candidate = 0;
311 }
312 
313 void ShenandoahOldHeuristics::handle_promotion_failure() {
314   _promotion_failed = true;
315 }
316 
317 void ShenandoahOldHeuristics::record_cycle_start() {
318   _promotion_failed = false;
319   _trigger_heuristic->record_cycle_start();
320 }
321 
322 void ShenandoahOldHeuristics::record_cycle_end() {
323   _trigger_heuristic->record_cycle_end();
324 }
325 
326 bool ShenandoahOldHeuristics::should_start_gc() {
327   // Cannot start a new old-gen GC until previous one has finished.
328   //
329   // Future refinement: under certain circumstances, we might be more sophisticated about this choice.
330   // For example, we could choose to abandon the previous old collection before it has completed evacuations,
331   // but this would require that we coalesce and fill all garbage within unevacuated collection-set regions.
332   if (unprocessed_old_or_hidden_collection_candidates() > 0) {
333     return false;
334   }
335 
336   // If there's been a promotion failure (and we don't have regions already scheduled for evacuation),
337   // start a new old generation collection.
338   if (_promotion_failed) {
339     log_info(gc)("Trigger: Promotion Failure");
340     return true;
341   }
342 
343   // Otherwise, defer to configured heuristic for gc trigger.
344   return _trigger_heuristic->should_start_gc();
345 }
346 
347 bool ShenandoahOldHeuristics::should_degenerate_cycle() {
348   return _trigger_heuristic->should_degenerate_cycle();
349 }
350 
351 void ShenandoahOldHeuristics::record_success_concurrent(bool abbreviated) {
352   _trigger_heuristic->record_success_concurrent(abbreviated);
353 }
354 
355 void ShenandoahOldHeuristics::record_success_degenerated() {
356   _trigger_heuristic->record_success_degenerated();
357 }
358 
359 void ShenandoahOldHeuristics::record_success_full() {
360   _trigger_heuristic->record_success_full();
361 }
362 
363 void ShenandoahOldHeuristics::record_allocation_failure_gc() {
364   _trigger_heuristic->record_allocation_failure_gc();
365 }
366 
367 void ShenandoahOldHeuristics::record_requested_gc() {
368   _trigger_heuristic->record_requested_gc();
369 }
370 
371 bool ShenandoahOldHeuristics::can_unload_classes() {
372   return _trigger_heuristic->can_unload_classes();
373 }
374 
375 bool ShenandoahOldHeuristics::can_unload_classes_normal() {
376   return _trigger_heuristic->can_unload_classes_normal();
377 }
378 
379 bool ShenandoahOldHeuristics::should_unload_classes() {
380   return _trigger_heuristic->should_unload_classes();
381 }
382 
383 const char* ShenandoahOldHeuristics::name() {
384   static char name[128];
385   jio_snprintf(name, sizeof(name), "%s (OLD)", _trigger_heuristic->name());
386   return name;
387 }
388 
389 bool ShenandoahOldHeuristics::is_diagnostic() {
390   return false;
391 }
392 
393 bool ShenandoahOldHeuristics::is_experimental() {
394   return true;
395 }
396 
397 void ShenandoahOldHeuristics::choose_collection_set_from_regiondata(ShenandoahCollectionSet* set,
398                                                                     ShenandoahHeuristics::RegionData* data,
399                                                                     size_t data_size, size_t free) {
400   ShouldNotReachHere();
401 }
402