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