1 /*

     2  * Copyright (c) 2016, Oracle 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 #include "gc/g1/g1CollectedHeap.hpp"

    27 #include "gc/g1/g1CollectionSet.hpp"

    28 #include "gc/g1/g1CollectorPolicy.hpp"

    29 #include "gc/g1/g1CollectorState.hpp"

    30 #include "gc/g1/heapRegion.inline.hpp"

    31 #include "gc/g1/heapRegionRemSet.hpp"

    32 #include "gc/g1/heapRegionSet.hpp"

    33 #include "utilities/debug.hpp"

    34 

    35 G1CollectorState* G1CollectionSet::collector_state() {

    36   return _g1->collector_state();

    37 }

    38 

    39 G1GCPhaseTimes* G1CollectionSet::phase_times() {

    40   return _policy->phase_times();

    41 }

    42 

    43 CollectionSetChooser* G1CollectionSet::cset_chooser() {

    44   return _cset_chooser;

    45 }

    46 

    47 double G1CollectionSet::predict_region_elapsed_time_ms(HeapRegion* hr) {

    48   return _policy->predict_region_elapsed_time_ms(hr, collector_state()->gcs_are_young());

    49 }

    50 

    51 

    52 G1CollectionSet::G1CollectionSet(G1CollectedHeap* g1h) :

    53   _g1(g1h),

    54   _policy(NULL),

    55   _cset_chooser(new CollectionSetChooser()),

    56   _eden_region_length(0),

    57   _survivor_region_length(0),

    58   _old_region_length(0),

    59 

    60   _head(NULL),

    61   _bytes_used_before(0),

    62   _recorded_rs_lengths(0),

    63   // Incremental CSet attributes

    64   _inc_build_state(Inactive),

    65   _inc_head(NULL),

    66   _inc_tail(NULL),

    67   _inc_bytes_used_before(0),

    68   _inc_recorded_rs_lengths(0),

    69   _inc_recorded_rs_lengths_diffs(0),

    70   _inc_predicted_elapsed_time_ms(0.0),

    71   _inc_predicted_elapsed_time_ms_diffs(0.0) {}

    72 

    73 G1CollectionSet::~G1CollectionSet() {

    74   delete _cset_chooser;

    75 }

    76 

    77 void G1CollectionSet::init_region_lengths(uint eden_cset_region_length,

    78                                           uint survivor_cset_region_length) {

    79   _eden_region_length     = eden_cset_region_length;

    80   _survivor_region_length = survivor_cset_region_length;

    81   _old_region_length      = 0;

    82 }

    83 

    84 void G1CollectionSet::set_recorded_rs_lengths(size_t rs_lengths) {

    85   _recorded_rs_lengths = rs_lengths;

    86 }

    87 

    88 // Add the heap region at the head of the non-incremental collection set

    89 void G1CollectionSet::add_old_region(HeapRegion* hr) {

    90   assert(_inc_build_state == Active, "Precondition");

    91   assert(hr->is_old(), "the region should be old");

    92 

    93   assert(!hr->in_collection_set(), "should not already be in the CSet");

    94   _g1->register_old_region_with_cset(hr);

    95   hr->set_next_in_collection_set(_head);

    96   _head = hr;

    97   _bytes_used_before += hr->used();

    98   size_t rs_length = hr->rem_set()->occupied();

    99   _recorded_rs_lengths += rs_length;

   100   _old_region_length += 1;

   101 }

   102 

   103 // Initialize the per-collection-set information

   104 void G1CollectionSet::start_incremental_building() {

   105   assert(_inc_build_state == Inactive, "Precondition");

   106 

   107   _inc_head = NULL;

   108   _inc_tail = NULL;

   109   _inc_bytes_used_before = 0;

   110 

   111   _inc_recorded_rs_lengths = 0;

   112   _inc_recorded_rs_lengths_diffs = 0;

   113   _inc_predicted_elapsed_time_ms = 0.0;

   114   _inc_predicted_elapsed_time_ms_diffs = 0.0;

   115   _inc_build_state = Active;

   116 }

   117 

   118 void G1CollectionSet::finalize_incremental_building() {

   119   assert(_inc_build_state == Active, "Precondition");

   120   assert(SafepointSynchronize::is_at_safepoint(), "should be at a safepoint");

   121 

   122   // The two "main" fields, _inc_recorded_rs_lengths and

   123   // _inc_predicted_elapsed_time_ms, are updated by the thread

   124   // that adds a new region to the CSet. Further updates by the

   125   // concurrent refinement thread that samples the young RSet lengths

   126   // are accumulated in the *_diffs fields. Here we add the diffs to

   127   // the "main" fields.

   128 

   129   if (_inc_recorded_rs_lengths_diffs >= 0) {

   130     _inc_recorded_rs_lengths += _inc_recorded_rs_lengths_diffs;

   131   } else {

   132     // This is defensive. The diff should in theory be always positive

   133     // as RSets can only grow between GCs. However, given that we

   134     // sample their size concurrently with other threads updating them

   135     // it's possible that we might get the wrong size back, which

   136     // could make the calculations somewhat inaccurate.

   137     size_t diffs = (size_t) (-_inc_recorded_rs_lengths_diffs);

   138     if (_inc_recorded_rs_lengths >= diffs) {

   139       _inc_recorded_rs_lengths -= diffs;

   140     } else {

   141       _inc_recorded_rs_lengths = 0;

   142     }

   143   }

   144   _inc_predicted_elapsed_time_ms += _inc_predicted_elapsed_time_ms_diffs;

   145 

   146   _inc_recorded_rs_lengths_diffs = 0;

   147   _inc_predicted_elapsed_time_ms_diffs = 0.0;

   148 }

   149 

   150 void G1CollectionSet::update_young_region_prediction(HeapRegion* hr,

   151                                                      size_t new_rs_length) {

   152   // Update the CSet information that is dependent on the new RS length

   153   assert(hr->is_young(), "Precondition");

   154   assert(!SafepointSynchronize::is_at_safepoint(), "should not be at a safepoint");

   155 

   156   // We could have updated _inc_recorded_rs_lengths and

   157   // _inc_predicted_elapsed_time_ms directly but we'd need to do

   158   // that atomically, as this code is executed by a concurrent

   159   // refinement thread, potentially concurrently with a mutator thread

   160   // allocating a new region and also updating the same fields. To

   161   // avoid the atomic operations we accumulate these updates on two

   162   // separate fields (*_diffs) and we'll just add them to the "main"

   163   // fields at the start of a GC.

   164 

   165   ssize_t old_rs_length = (ssize_t) hr->recorded_rs_length();

   166   ssize_t rs_lengths_diff = (ssize_t) new_rs_length - old_rs_length;

   167   _inc_recorded_rs_lengths_diffs += rs_lengths_diff;

   168 

   169   double old_elapsed_time_ms = hr->predicted_elapsed_time_ms();

   170   double new_region_elapsed_time_ms = predict_region_elapsed_time_ms(hr);

   171   double elapsed_ms_diff = new_region_elapsed_time_ms - old_elapsed_time_ms;

   172   _inc_predicted_elapsed_time_ms_diffs += elapsed_ms_diff;

   173 

   174   hr->set_recorded_rs_length(new_rs_length);

   175   hr->set_predicted_elapsed_time_ms(new_region_elapsed_time_ms);

   176 }

   177 

   178 void G1CollectionSet::add_young_region_common(HeapRegion* hr) {

   179   assert(hr->is_young(), "invariant");

   180   assert(hr->young_index_in_cset() > -1, "should have already been set");

   181   assert(_inc_build_state == Active, "Precondition");

   182 

   183   // This routine is used when:

   184   // * adding survivor regions to the incremental cset at the end of an

   185   //   evacuation pause or

   186   // * adding the current allocation region to the incremental cset

   187   //   when it is retired.

   188   // Therefore this routine may be called at a safepoint by the

   189   // VM thread, or in-between safepoints by mutator threads (when

   190   // retiring the current allocation region)

   191   // We need to clear and set the cached recorded/cached collection set

   192   // information in the heap region here (before the region gets added

   193   // to the collection set). An individual heap region's cached values

   194   // are calculated, aggregated with the policy collection set info,

   195   // and cached in the heap region here (initially) and (subsequently)

   196   // by the Young List sampling code.

   197 

   198   size_t rs_length = hr->rem_set()->occupied();

   199   double region_elapsed_time_ms = predict_region_elapsed_time_ms(hr);

   200 

   201   // Cache the values we have added to the aggregated information

   202   // in the heap region in case we have to remove this region from

   203   // the incremental collection set, or it is updated by the

   204   // rset sampling code

   205   hr->set_recorded_rs_length(rs_length);

   206   hr->set_predicted_elapsed_time_ms(region_elapsed_time_ms);

   207 

   208   size_t used_bytes = hr->used();

   209   _inc_recorded_rs_lengths += rs_length;

   210   _inc_predicted_elapsed_time_ms += region_elapsed_time_ms;

   211   _inc_bytes_used_before += used_bytes;

   212 

   213   assert(!hr->in_collection_set(), "invariant");

   214   _g1->register_young_region_with_cset(hr);

   215   assert(hr->next_in_collection_set() == NULL, "invariant");

   216 }

   217 

   218 // Add the region at the RHS of the incremental cset

   219 void G1CollectionSet::add_survivor_regions(HeapRegion* hr) {

   220   // We should only ever be appending survivors at the end of a pause

   221   assert(hr->is_survivor(), "Logic");

   222 

   223   // Do the 'common' stuff

   224   add_young_region_common(hr);

   225 

   226   // Now add the region at the right hand side

   227   if (_inc_tail == NULL) {

   228     assert(_inc_head == NULL, "invariant");

   229     _inc_head = hr;

   230   } else {

   231     _inc_tail->set_next_in_collection_set(hr);

   232   }

   233   _inc_tail = hr;

   234 }

   235 

   236 // Add the region to the LHS of the incremental cset

   237 void G1CollectionSet::add_eden_region(HeapRegion* hr) {

   238   // Survivors should be added to the RHS at the end of a pause

   239   assert(hr->is_eden(), "Logic");

   240 

   241   // Do the 'common' stuff

   242   add_young_region_common(hr);

   243 

   244   // Add the region at the left hand side

   245   hr->set_next_in_collection_set(_inc_head);

   246   if (_inc_head == NULL) {

   247     assert(_inc_tail == NULL, "Invariant");

   248     _inc_tail = hr;

   249   }

   250   _inc_head = hr;

   251 }

   252 

   253 #ifndef PRODUCT

   254 void G1CollectionSet::print(HeapRegion* list_head, outputStream* st) {

   255   assert(list_head == inc_head() || list_head == head(), "must be");

   256 

   257   st->print_cr("\nCollection_set:");

   258   HeapRegion* csr = list_head;

   259   while (csr != NULL) {

   260     HeapRegion* next = csr->next_in_collection_set();

   261     assert(csr->in_collection_set(), "bad CS");

   262     st->print_cr("  " HR_FORMAT ", P: " PTR_FORMAT "N: " PTR_FORMAT ", age: %4d",

   263                  HR_FORMAT_PARAMS(csr),

   264                  p2i(csr->prev_top_at_mark_start()), p2i(csr->next_top_at_mark_start()),

   265                  csr->age_in_surv_rate_group_cond());

   266     csr = next;

   267   }

   268 }

   269 #endif // !PRODUCT

   270 

   271 double G1CollectionSet::finalize_young_part(double target_pause_time_ms) {

   272   double young_start_time_sec = os::elapsedTime();

   273 

   274   YoungList* young_list = _g1->young_list();

   275   finalize_incremental_building();

   276 

   277   guarantee(target_pause_time_ms > 0.0,

   278             "target_pause_time_ms = %1.6lf should be positive", target_pause_time_ms);

   279   guarantee(_head == NULL, "Precondition");

   280 

   281   size_t pending_cards = _policy->pending_cards();

   282   double base_time_ms = _policy->predict_base_elapsed_time_ms(pending_cards);

   283   double time_remaining_ms = MAX2(target_pause_time_ms - base_time_ms, 0.0);

   284 

   285   log_trace(gc, ergo, cset)("Start choosing CSet. pending cards: " SIZE_FORMAT " predicted base time: %1.2fms remaining time: %1.2fms target pause time: %1.2fms",

   286                             pending_cards, base_time_ms, time_remaining_ms, target_pause_time_ms);

   287 

   288   collector_state()->set_last_gc_was_young(collector_state()->gcs_are_young());

   289 

   290   // The young list is laid with the survivor regions from the previous

   291   // pause are appended to the RHS of the young list, i.e.

   292   //   [Newly Young Regions ++ Survivors from last pause].

   293 

   294   uint survivor_region_length = young_list->survivor_length();

   295   uint eden_region_length = young_list->eden_length();

   296   init_region_lengths(eden_region_length, survivor_region_length);

   297 

   298   HeapRegion* hr = young_list->first_survivor_region();

   299   while (hr != NULL) {

   300     assert(hr->is_survivor(), "badly formed young list");

   301     // There is a convention that all the young regions in the CSet

   302     // are tagged as "eden", so we do this for the survivors here. We

   303     // use the special set_eden_pre_gc() as it doesn't check that the

   304     // region is free (which is not the case here).

   305     hr->set_eden_pre_gc();

   306     hr = hr->get_next_young_region();

   307   }

   308 

   309   // Clear the fields that point to the survivor list - they are all young now.

   310   young_list->clear_survivors();

   311 

   312   _head = _inc_head;

   313   _bytes_used_before = _inc_bytes_used_before;

   314   time_remaining_ms = MAX2(time_remaining_ms - _inc_predicted_elapsed_time_ms, 0.0);

   315 

   316   log_trace(gc, ergo, cset)("Add young regions to CSet. eden: %u regions, survivors: %u regions, predicted young region time: %1.2fms, target pause time: %1.2fms",

   317                             eden_region_length, survivor_region_length, _inc_predicted_elapsed_time_ms, target_pause_time_ms);

   318 

   319   // The number of recorded young regions is the incremental

   320   // collection set's current size

   321   set_recorded_rs_lengths(_inc_recorded_rs_lengths);

   322 

   323   double young_end_time_sec = os::elapsedTime();

   324   phase_times()->record_young_cset_choice_time_ms((young_end_time_sec - young_start_time_sec) * 1000.0);

   325 

   326   return time_remaining_ms;

   327 }

   328 

   329 void G1CollectionSet::finalize_old_part(double time_remaining_ms) {

   330   double non_young_start_time_sec = os::elapsedTime();

   331   double predicted_old_time_ms = 0.0;

   332 

   333   if (!collector_state()->gcs_are_young()) {

   334     cset_chooser()->verify();

   335     const uint min_old_cset_length = _policy->calc_min_old_cset_length();

   336     const uint max_old_cset_length = _policy->calc_max_old_cset_length();

   337 

   338     uint expensive_region_num = 0;

   339     bool check_time_remaining = _policy->adaptive_young_list_length();

   340 

   341     HeapRegion* hr = cset_chooser()->peek();

   342     while (hr != NULL) {

   343       if (old_region_length() >= max_old_cset_length) {

   344         // Added maximum number of old regions to the CSet.

   345         log_debug(gc, ergo, cset)("Finish adding old regions to CSet (old CSet region num reached max). old %u regions, max %u regions",

   346                                   old_region_length(), max_old_cset_length);

   347         break;

   348       }

   349 

   350       // Stop adding regions if the remaining reclaimable space is

   351       // not above G1HeapWastePercent.

   352       size_t reclaimable_bytes = cset_chooser()->remaining_reclaimable_bytes();

   353       double reclaimable_perc = _policy->reclaimable_bytes_perc(reclaimable_bytes);

   354       double threshold = (double) G1HeapWastePercent;

   355       if (reclaimable_perc <= threshold) {

   356         // We've added enough old regions that the amount of uncollected

   357         // reclaimable space is at or below the waste threshold. Stop

   358         // adding old regions to the CSet.

   359         log_debug(gc, ergo, cset)("Finish adding old regions to CSet (reclaimable percentage not over threshold). "

   360                                   "old %u regions, max %u regions, reclaimable: " SIZE_FORMAT "B (%1.2f%%) threshold: " UINTX_FORMAT "%%",

   361                                   old_region_length(), max_old_cset_length, reclaimable_bytes, reclaimable_perc, G1HeapWastePercent);

   362         break;

   363       }

   364 

   365       double predicted_time_ms = predict_region_elapsed_time_ms(hr);

   366       if (check_time_remaining) {

   367         if (predicted_time_ms > time_remaining_ms) {

   368           // Too expensive for the current CSet.

   369 

   370           if (old_region_length() >= min_old_cset_length) {

   371             // We have added the minimum number of old regions to the CSet,

   372             // we are done with this CSet.

   373             log_debug(gc, ergo, cset)("Finish adding old regions to CSet (predicted time is too high). "

   374                                       "predicted time: %1.2fms, remaining time: %1.2fms old %u regions, min %u regions",

   375                                       predicted_time_ms, time_remaining_ms, old_region_length(), min_old_cset_length);

   376             break;

   377           }

   378 

   379           // We'll add it anyway given that we haven't reached the

   380           // minimum number of old regions.

   381           expensive_region_num += 1;

   382         }

   383       } else {

   384         if (old_region_length() >= min_old_cset_length) {

   385           // In the non-auto-tuning case, we'll finish adding regions

   386           // to the CSet if we reach the minimum.

   387 

   388           log_debug(gc, ergo, cset)("Finish adding old regions to CSet (old CSet region num reached min). old %u regions, min %u regions",

   389                                     old_region_length(), min_old_cset_length);

   390           break;

   391         }

   392       }

   393 

   394       // We will add this region to the CSet.

   395       time_remaining_ms = MAX2(time_remaining_ms - predicted_time_ms, 0.0);

   396       predicted_old_time_ms += predicted_time_ms;

   397       cset_chooser()->pop(); // already have region via peek()

   398       _g1->old_set_remove(hr);

   399       add_old_region(hr);

   400 

   401       hr = cset_chooser()->peek();

   402     }

   403     if (hr == NULL) {

   404       log_debug(gc, ergo, cset)("Finish adding old regions to CSet (candidate old regions not available)");

   405     }

   406 

   407     if (expensive_region_num > 0) {

   408       // We print the information once here at the end, predicated on

   409       // whether we added any apparently expensive regions or not, to

   410       // avoid generating output per region.

   411       log_debug(gc, ergo, cset)("Added expensive regions to CSet (old CSet region num not reached min)."

   412                                 "old: %u regions, expensive: %u regions, min: %u regions, remaining time: %1.2fms",

   413                                 old_region_length(), expensive_region_num, min_old_cset_length, time_remaining_ms);

   414     }

   415 

   416     cset_chooser()->verify();

   417   }

   418 

   419   stop_incremental_building();

   420 

   421   log_debug(gc, ergo, cset)("Finish choosing CSet. old: %u regions, predicted old region time: %1.2fms, time remaining: %1.2f",

   422                             old_region_length(), predicted_old_time_ms, time_remaining_ms);

   423 

   424   double non_young_end_time_sec = os::elapsedTime();

   425   phase_times()->record_non_young_cset_choice_time_ms((non_young_end_time_sec - non_young_start_time_sec) * 1000.0);

   426 }