1 /*
  2  * Copyright (c) 2020, 2021 Amazon.com, Inc. 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 "precompiled.hpp"
 26 
 27 #include "gc/shenandoah/shenandoahFreeSet.hpp"
 28 #include "gc/shenandoah/shenandoahGeneration.hpp"
 29 #include "gc/shenandoah/shenandoahHeap.hpp"
 30 #include "gc/shenandoah/shenandoahMarkClosures.hpp"
 31 #include "gc/shenandoah/shenandoahMonitoringSupport.hpp"
 32 #include "gc/shenandoah/shenandoahReferenceProcessor.hpp"
 33 #include "gc/shenandoah/shenandoahTaskqueue.inline.hpp"
 34 #include "gc/shenandoah/shenandoahUtils.hpp"
 35 #include "gc/shenandoah/shenandoahVerifier.hpp"
 36 #include "gc/shenandoah/shenandoahYoungGeneration.hpp"
 37 #include "gc/shenandoah/heuristics/shenandoahHeuristics.hpp"
 38 
 39 class ShenandoahResetUpdateRegionStateClosure : public ShenandoahHeapRegionClosure {
 40  private:
 41   ShenandoahMarkingContext* const _ctx;
 42  public:
 43   ShenandoahResetUpdateRegionStateClosure() :
 44     _ctx(ShenandoahHeap::heap()->marking_context()) {}
 45 
 46   void heap_region_do(ShenandoahHeapRegion* r) {
 47     if (r->is_active()) {
 48       // Reset live data and set TAMS optimistically. We would recheck these under the pause
 49       // anyway to capture any updates that happened since now.
 50       _ctx->capture_top_at_mark_start(r);
 51       r->clear_live_data();
 52     }
 53   }
 54 
 55   bool is_thread_safe() { return true; }
 56 };
 57 
 58 class ShenandoahResetBitmapTask : public ShenandoahHeapRegionClosure {
 59  private:
 60   ShenandoahHeap* _heap;
 61   ShenandoahMarkingContext* const _ctx;
 62  public:
 63   ShenandoahResetBitmapTask() :
 64      _heap(ShenandoahHeap::heap()),
 65     _ctx(_heap->marking_context()) {}
 66 
 67   void heap_region_do(ShenandoahHeapRegion* region) {
 68     if (_heap->is_bitmap_slice_committed(region)) {
 69       _ctx->clear_bitmap(region);
 70     }
 71   }
 72 
 73   bool is_thread_safe() { return true; }
 74 };
 75 
 76 class ShenandoahMergeWriteTable: public ShenandoahHeapRegionClosure {
 77  private:
 78   ShenandoahHeap* _heap;
 79   RememberedScanner* _scanner;
 80  public:
 81   ShenandoahMergeWriteTable() : _heap(ShenandoahHeap::heap()), _scanner(_heap->card_scan()) {}
 82 
 83   virtual void heap_region_do(ShenandoahHeapRegion* r) override {
 84     if (r->is_old()) {
 85       _scanner->merge_write_table(r->bottom(), ShenandoahHeapRegion::region_size_words());
 86     }
 87   }
 88 
 89   virtual bool is_thread_safe() override {
 90     return true;
 91   }
 92 };
 93 
 94 class ShenandoahSquirrelAwayCardTable: public ShenandoahHeapRegionClosure {
 95  private:
 96   ShenandoahHeap* _heap;
 97   RememberedScanner* _scanner;
 98  public:
 99   ShenandoahSquirrelAwayCardTable() :
100     _heap(ShenandoahHeap::heap()),
101     _scanner(_heap->card_scan()) {}
102 
103   void heap_region_do(ShenandoahHeapRegion* region) {
104     if (region->is_old()) {
105       _scanner->reset_remset(region->bottom(), ShenandoahHeapRegion::region_size_words());
106     }
107   }
108 
109   bool is_thread_safe() { return true; }
110 };
111 
112 void ShenandoahGeneration::confirm_heuristics_mode() {
113   if (_heuristics->is_diagnostic() && !UnlockDiagnosticVMOptions) {
114     vm_exit_during_initialization(
115             err_msg("Heuristics \"%s\" is diagnostic, and must be enabled via -XX:+UnlockDiagnosticVMOptions.",
116                     _heuristics->name()));
117   }
118   if (_heuristics->is_experimental() && !UnlockExperimentalVMOptions) {
119     vm_exit_during_initialization(
120             err_msg("Heuristics \"%s\" is experimental, and must be enabled via -XX:+UnlockExperimentalVMOptions.",
121                     _heuristics->name()));
122   }
123 }
124 
125 ShenandoahHeuristics* ShenandoahGeneration::initialize_heuristics(ShenandoahMode* gc_mode) {
126   _heuristics = gc_mode->initialize_heuristics(this);
127   _heuristics->set_guaranteed_gc_interval(ShenandoahGuaranteedGCInterval);
128   confirm_heuristics_mode();
129   return _heuristics;
130 }
131 
132 size_t ShenandoahGeneration::bytes_allocated_since_gc_start() {
133   return Atomic::load(&_bytes_allocated_since_gc_start);;
134 }
135 
136 void ShenandoahGeneration::reset_bytes_allocated_since_gc_start() {
137   Atomic::store(&_bytes_allocated_since_gc_start, (size_t)0);
138 }
139 
140 void ShenandoahGeneration::increase_allocated(size_t bytes) {
141   Atomic::add(&_bytes_allocated_since_gc_start, bytes, memory_order_relaxed);
142 }
143 
144 void ShenandoahGeneration::log_status() const {
145   typedef LogTarget(Info, gc, ergo) LogGcInfo;
146 
147   if (!LogGcInfo::is_enabled()) {
148     return;
149   }
150 
151   // Not under a lock here, so read each of these once to make sure
152   // byte size in proper unit and proper unit for byte size are consistent.
153   size_t v_used = used();
154   size_t v_used_regions = used_regions_size();
155   size_t v_soft_max_capacity = soft_max_capacity();
156   size_t v_max_capacity = max_capacity();
157   size_t v_available = available();
158   LogGcInfo::print("%s generation used: " SIZE_FORMAT "%s, used regions: " SIZE_FORMAT "%s, "
159                    "soft capacity: " SIZE_FORMAT "%s, max capacity: " SIZE_FORMAT " %s, available: " SIZE_FORMAT " %s",
160                    name(),
161                    byte_size_in_proper_unit(v_used), proper_unit_for_byte_size(v_used),
162                    byte_size_in_proper_unit(v_used_regions), proper_unit_for_byte_size(v_used_regions),
163                    byte_size_in_proper_unit(v_soft_max_capacity), proper_unit_for_byte_size(v_soft_max_capacity),
164                    byte_size_in_proper_unit(v_max_capacity), proper_unit_for_byte_size(v_max_capacity),
165                    byte_size_in_proper_unit(v_available), proper_unit_for_byte_size(v_available));
166 }
167 
168 void ShenandoahGeneration::reset_mark_bitmap() {
169   ShenandoahHeap* heap = ShenandoahHeap::heap();
170   heap->assert_gc_workers(heap->workers()->active_workers());
171 
172   set_mark_incomplete();
173 
174   ShenandoahResetBitmapTask task;
175   parallel_heap_region_iterate(&task);
176 }
177 
178 // The ideal is to swap the remembered set so the safepoint effort is no more than a few pointer manipulations.
179 // However, limitations in the implementation of the mutator write-barrier make it difficult to simply change the
180 // location of the card table.  So the interim implementation of swap_remembered_set will copy the write-table
181 // onto the read-table and will then clear the write-table.
182 void ShenandoahGeneration::swap_remembered_set() {
183   // Must be sure that marking is complete before we swap remembered set.
184   ShenandoahHeap* heap = ShenandoahHeap::heap();
185   heap->assert_gc_workers(heap->workers()->active_workers());
186   shenandoah_assert_safepoint();
187 
188   // TODO: Eventually, we want replace this with a constant-time exchange of pointers.
189   ShenandoahSquirrelAwayCardTable task;
190   heap->old_generation()->parallel_heap_region_iterate(&task);
191 }
192 
193 // If a concurrent cycle fails _after_ the card table has been swapped we need to update the read card
194 // table with any writes that have occurred during the transition to the degenerated cycle. Without this,
195 // newly created objects which are only referenced by old objects could be lost when the remembered set
196 // is scanned during the degenerated mark.
197 void ShenandoahGeneration::merge_write_table() {
198   // This should only happen for degenerated cycles
199   ShenandoahHeap* heap = ShenandoahHeap::heap();
200   heap->assert_gc_workers(heap->workers()->active_workers());
201   shenandoah_assert_safepoint();
202 
203   ShenandoahMergeWriteTable task;
204   heap->old_generation()->parallel_heap_region_iterate(&task);
205 }
206 
207 void ShenandoahGeneration::prepare_gc(bool do_old_gc_bootstrap) {
208   // Reset mark bitmap for this generation (typically young)
209   reset_mark_bitmap();
210   if (do_old_gc_bootstrap) {
211     // Reset mark bitmap for old regions also.  Note that do_old_gc_bootstrap is only true if this generation is YOUNG.
212     ShenandoahHeap::heap()->old_generation()->reset_mark_bitmap();
213   }
214 
215   // Capture Top At Mark Start for this generation (typically young)
216   ShenandoahResetUpdateRegionStateClosure cl;
217   parallel_heap_region_iterate(&cl);
218   if (do_old_gc_bootstrap) {
219     // Capture top at mark start for both old-gen regions also.  Note that do_old_gc_bootstrap is only true if generation is YOUNG.
220     ShenandoahHeap::heap()->old_generation()->parallel_heap_region_iterate(&cl);
221   }
222 }
223 
224 void  ShenandoahGeneration::prepare_regions_and_collection_set(bool concurrent) {
225 
226   ShenandoahHeap* heap = ShenandoahHeap::heap();
227   assert(!heap->is_full_gc_in_progress(), "Only for concurrent and degenerated GC");
228   assert(generation_mode() != OLD, "Only YOUNG and GLOBAL GC perform evacuations");
229   {
230     ShenandoahGCPhase phase(concurrent ? ShenandoahPhaseTimings::final_update_region_states :
231                                          ShenandoahPhaseTimings::degen_gc_final_update_region_states);
232     ShenandoahFinalMarkUpdateRegionStateClosure cl(complete_marking_context());
233 
234     parallel_heap_region_iterate(&cl);
235     heap->assert_pinned_region_status();
236 
237     if (generation_mode() == YOUNG) {
238       // Also capture update_watermark for old-gen regions.
239       ShenandoahCaptureUpdateWaterMarkForOld old_cl(complete_marking_context());
240       heap->old_generation()->parallel_heap_region_iterate(&old_cl);
241     }
242   }
243 
244   {
245     ShenandoahGCPhase phase(concurrent ? ShenandoahPhaseTimings::choose_cset :
246                             ShenandoahPhaseTimings::degen_gc_choose_cset);
247     ShenandoahHeapLocker locker(heap->lock());
248     heap->collection_set()->clear();
249 
250 
251     if (heap->mode()->is_generational()) {
252 
253       // During initialization and phase changes, it is more likely that fewer objects die young and old-gen
254       // memory is not yet full (or is in the process of being replaced).  During these tiems especially, it
255       // is beneficial to loan memory from old-gen to young-gen during the evacuation and update-refs phases
256       // of execution.
257 
258       //  PromotionReserve for old generation: how much memory are we reserving to hold the results of
259       //     promoting young-gen objects that have reached tenure age?  This value is not "critical".  If we
260       //     underestimate, certain promotions will simply be deferred.  The basis of this estimate is
261       //     historical precedent.  Conservatively, budget this value to be twice the amount of memory
262       //     promoted in previous GC pass.  Whenever the amount promoted during previous GC is zero,
263       //     including initial passes before any objects have reached tenure age, use live memory within
264       //     young-gen memory divided by (ShenandoahTenureAge multiplied by InitialTenuringThreshold) as the
265       //     the very conservative value of this parameter.  Note that during initialization, there is
266       //     typically plentiful old-gen memory so it's ok to be conservative with the initial estimates
267       //     of this value.  But PromotionReserve can be no larger than available memory.  In summary, we
268       //     compute PromotionReserve as the smaller of:
269       //      1. old_gen->available
270       //      2. young_gen->capacity() * ShenandoahEvacReserve
271       //      3. (bytes promoted by previous promotion) * 2 if (bytes promoted by previous promotion) is not zero
272       //      4. if (bytes promoted by previous promotion) is zero, divide young_gen->used()
273       //         by (ShenandoahTenureAge * InitialTenuringThreshold)
274       //
275       //     We don't yet know how much live memory.  Inside choose_collection_set(), after it computes live memory,
276       //     the PromotionReserve may be further reduced.
277       //
278       //      5. live bytes in young-gen divided by (ShenandoahTenureAge * InitialTenuringThreshold
279       //         if the number of bytes promoted by previous promotion is zero
280       //
281       ShenandoahGeneration* old_generation = heap->old_generation();
282       ShenandoahYoungGeneration* young_generation = heap->young_generation();
283       size_t promotion_reserve = old_generation->available();
284 
285       size_t max_young_evacuation = (young_generation->soft_max_capacity() * ShenandoahOldEvacReserve) / 100;
286       if (max_young_evacuation < promotion_reserve) {
287         promotion_reserve = max_young_evacuation;
288       }
289 
290       size_t previously_promoted = heap->get_previous_promotion();
291       if (previously_promoted == 0) {
292         // Very conservatively, assume linear population decay (rather than more typical exponential) and assume all of
293         // used is live.
294         size_t proposed_reserve = young_generation->used() / (ShenandoahAgingCyclePeriod * InitialTenuringThreshold);
295         if (promotion_reserve > proposed_reserve) {
296           promotion_reserve = proposed_reserve;
297         }
298       } else if (previously_promoted * 2 < promotion_reserve) {
299         promotion_reserve = previously_promoted * 2;
300       }
301 
302       heap->set_promotion_reserve(promotion_reserve);
303       heap->capture_old_usage(old_generation->used());
304 
305       //  OldEvacuationReserve for old generation: how much memory are we reserving to hold the results of
306       //     evacuating old-gen heap regions?  In order to sustain a consistent pace of young-gen collections,
307       //     the goal is to maintain a consistent value for this parameter (when the candidate set is not
308       //     empty).  This value is the minimum of:
309       //       1. old_gen->available() - PromotionReserve
310       //       2. (young_gen->capacity() scaled by ShenandoahEvacReserve) scaled by ShenandoahOldEvacRatioPercent
311 
312       // Don't reserve for old_evac any more than the memory that is available in old_gen.
313       size_t old_evacuation_reserve = old_generation->available() - promotion_reserve;
314 
315       // Make sure old evacuation is no more than ShenandoahOldEvacRatioPercent of the total evacuation budget.
316       size_t max_total_evac = (young_generation->soft_max_capacity() * ShenandoahEvacReserve) / 100;
317       size_t max_old_evac_portion = (max_total_evac * ShenandoahOldEvacRatioPercent) / 100;
318 
319       if (old_evacuation_reserve > max_old_evac_portion) {
320         old_evacuation_reserve = max_old_evac_portion;
321       }
322 
323       heap->set_old_evac_reserve(old_evacuation_reserve);
324       heap->reset_old_evac_expended();
325 
326       // Compute YoungEvacuationReserve after we prime the collection set with old-gen candidates.  This depends
327       // on how much memory old-gen wants to evacuate.  This is done within _heuristics->choose_collection_set().
328 
329       // There's no need to pass this information to ShenandoahFreeSet::rebuild().  The GC allocator automatically borrows
330       // memory from mutator regions when necessary.
331     }
332 
333     // The heuristics may consult and/or change the values of PromotionReserved, OldEvacuationReserved, and
334     // YoungEvacuationReserved, all of which are represented in the shared ShenandoahHeap data structure.
335     _heuristics->choose_collection_set(heap->collection_set(), heap->old_heuristics());
336 
337     //  EvacuationAllocationSupplement: This represents memory that can be allocated in excess of young_gen->available()
338     //     during evacuation and update-refs.  This memory can be temporarily borrowed from old-gen allotment, then
339     //     repaid at the end of update-refs from the recycled collection set.  After we have computed the collection set
340     //     based on the parameters established above, we can make additional calculates based on our knowledge of the
341     //     collection set to determine how much allocation we can allow during the evacuation and update-refs phases
342     //     of execution.  With full awareness of collection set, we can shrink the values of PromotionReserve,
343     //     OldEvacuationReserve, and YoungEvacuationReserve.  Then, we can compute EvacuationAllocationReserve as the
344     //     minimum of:
345     //       1. old_gen->available - (PromotionReserve + OldEvacuationReserve)
346     //       2. The replenishment budget (number of regions in collection set - the number of regions already
347     //          under lien for the YoungEvacuationReserve)
348     //
349 
350     // The possibly revised values are also consulted by the ShenandoahPacer when it establishes pacing parameters
351     // for evacuation and update-refs.
352 
353   }
354 
355   {
356     ShenandoahGCPhase phase(concurrent ? ShenandoahPhaseTimings::final_rebuild_freeset :
357                             ShenandoahPhaseTimings::degen_gc_final_rebuild_freeset);
358     ShenandoahHeapLocker locker(heap->lock());
359     heap->free_set()->rebuild();
360   }
361 }
362 
363 bool ShenandoahGeneration::is_bitmap_clear() {
364   ShenandoahHeap* heap = ShenandoahHeap::heap();
365   ShenandoahMarkingContext* context = heap->marking_context();
366   size_t num_regions = heap->num_regions();
367   for (size_t idx = 0; idx < num_regions; idx++) {
368     ShenandoahHeapRegion* r = heap->get_region(idx);
369     if (contains(r) && (r->affiliation() != FREE)) {
370       if (heap->is_bitmap_slice_committed(r) && (context->top_at_mark_start(r) > r->bottom()) &&
371           !context->is_bitmap_clear_range(r->bottom(), r->end())) {
372         return false;
373       }
374     }
375   }
376   return true;
377 }
378 
379 bool ShenandoahGeneration::is_mark_complete() {
380   return _is_marking_complete.is_set();
381 }
382 
383 void ShenandoahGeneration::set_mark_complete() {
384   _is_marking_complete.set();
385 }
386 
387 void ShenandoahGeneration::set_mark_incomplete() {
388   _is_marking_complete.unset();
389 }
390 
391 ShenandoahMarkingContext* ShenandoahGeneration::complete_marking_context() {
392   assert(is_mark_complete(), "Marking must be completed.");
393   return ShenandoahHeap::heap()->marking_context();
394 }
395 
396 void ShenandoahGeneration::cancel_marking() {
397   log_info(gc)("Cancel marking: %s", name());
398   if (is_concurrent_mark_in_progress()) {
399     set_mark_incomplete();
400   }
401   _task_queues->clear();
402   ref_processor()->abandon_partial_discovery();
403   set_concurrent_mark_in_progress(false);
404 }
405 
406 ShenandoahGeneration::ShenandoahGeneration(GenerationMode generation_mode,
407                                            uint max_workers,
408                                            size_t max_capacity,
409                                            size_t soft_max_capacity) :
410   _generation_mode(generation_mode),
411   _task_queues(new ShenandoahObjToScanQueueSet(max_workers)),
412   _ref_processor(new ShenandoahReferenceProcessor(MAX2(max_workers, 1U))),
413   _affiliated_region_count(0), _used(0), _bytes_allocated_since_gc_start(0),
414   _max_capacity(max_capacity), _soft_max_capacity(soft_max_capacity),
415   _adjusted_capacity(soft_max_capacity), _heuristics(nullptr) {
416   _is_marking_complete.set();
417   assert(max_workers > 0, "At least one queue");
418   for (uint i = 0; i < max_workers; ++i) {
419     ShenandoahObjToScanQueue* task_queue = new ShenandoahObjToScanQueue();
420     _task_queues->register_queue(i, task_queue);
421   }
422 }
423 
424 ShenandoahGeneration::~ShenandoahGeneration() {
425   for (uint i = 0; i < _task_queues->size(); ++i) {
426     ShenandoahObjToScanQueue* q = _task_queues->queue(i);
427     delete q;
428   }
429   delete _task_queues;
430 }
431 
432 void ShenandoahGeneration::reserve_task_queues(uint workers) {
433   _task_queues->reserve(workers);
434 }
435 
436 ShenandoahObjToScanQueueSet* ShenandoahGeneration::old_gen_task_queues() const {
437   return nullptr;
438 }
439 
440 void ShenandoahGeneration::scan_remembered_set() {
441   assert(generation_mode() == YOUNG, "Should only scan remembered set for young generation.");
442 
443   ShenandoahHeap* const heap = ShenandoahHeap::heap();
444   uint nworkers = heap->workers()->active_workers();
445   reserve_task_queues(nworkers);
446 
447   ShenandoahReferenceProcessor* rp = ref_processor();
448   ShenandoahRegionIterator regions;
449   ShenandoahScanRememberedTask task(task_queues(), old_gen_task_queues(), rp, &regions);
450   heap->workers()->run_task(&task);
451 }
452 
453 void ShenandoahGeneration::increment_affiliated_region_count() {
454   _affiliated_region_count++;
455 }
456 
457 void ShenandoahGeneration::decrement_affiliated_region_count() {
458   _affiliated_region_count--;
459 }
460 
461 void ShenandoahGeneration::clear_used() {
462   assert(ShenandoahSafepoint::is_at_shenandoah_safepoint(), "must be at a safepoint");
463   // Do this atomically to assure visibility to other threads, even though these other threads may be idle "right now"..
464   Atomic::store(&_used, (size_t)0);
465 }
466 
467 void ShenandoahGeneration::increase_used(size_t bytes) {
468   Atomic::add(&_used, bytes);
469 }
470 
471 void ShenandoahGeneration::decrease_used(size_t bytes) {
472   assert(_used >= bytes, "cannot reduce bytes used by generation below zero");
473   Atomic::sub(&_used, bytes);
474 }
475 
476 size_t ShenandoahGeneration::used_regions() const {
477   return _affiliated_region_count;
478 }
479 
480 size_t ShenandoahGeneration::free_unaffiliated_regions() const {
481   size_t result = soft_max_capacity() / ShenandoahHeapRegion::region_size_bytes();
482   if (_affiliated_region_count > result) {
483     result = 0;                 // If old-gen is loaning regions to young-gen, affiliated regions may exceed capacity temporarily.
484   } else {
485     result -= _affiliated_region_count;
486   }
487   return result;
488 }
489 
490 size_t ShenandoahGeneration::used_regions_size() const {
491   return _affiliated_region_count * ShenandoahHeapRegion::region_size_bytes();
492 }
493 
494 size_t ShenandoahGeneration::available() const {
495   size_t in_use = used();
496   size_t soft_capacity = soft_max_capacity();
497   return in_use > soft_capacity ? 0 : soft_capacity - in_use;
498 }
499 
500 size_t ShenandoahGeneration::adjust_available(intptr_t adjustment) {
501   _adjusted_capacity = soft_max_capacity() + adjustment;
502   return _adjusted_capacity;
503 }
504 
505 size_t ShenandoahGeneration::unadjust_available() {
506   _adjusted_capacity = soft_max_capacity();
507   return _adjusted_capacity;
508 }
509 
510 size_t ShenandoahGeneration::adjusted_available() const {
511   size_t in_use = used();
512   size_t capacity = _adjusted_capacity;
513   return in_use > capacity ? 0 : capacity - in_use;
514 }