1 /*
   2  * Copyright (c) 2004, 2018, 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/shared/adaptiveSizePolicy.hpp"
  27 #include "gc/shared/gcCause.hpp"
  28 #include "gc/shared/gcUtil.inline.hpp"
  29 #include "logging/log.hpp"
  30 #include "runtime/timer.hpp"
  31 
  32 elapsedTimer AdaptiveSizePolicy::_minor_timer;
  33 elapsedTimer AdaptiveSizePolicy::_major_timer;
  34 
  35 // The throughput goal is implemented as
  36 //      _throughput_goal = 1 - ( 1 / (1 + gc_cost_ratio))
  37 // gc_cost_ratio is the ratio
  38 //      application cost / gc cost
  39 // For example a gc_cost_ratio of 4 translates into a
  40 // throughput goal of .80
  41 
  42 AdaptiveSizePolicy::AdaptiveSizePolicy(size_t init_eden_size,
  43                                        size_t init_promo_size,
  44                                        size_t init_survivor_size,
  45                                        double gc_pause_goal_sec,
  46                                        uint gc_cost_ratio) :
  47     _throughput_goal(1.0 - double(1.0 / (1.0 + (double) gc_cost_ratio))),
  48     _eden_size(init_eden_size),
  49     _promo_size(init_promo_size),
  50     _survivor_size(init_survivor_size),
  51     _latest_minor_mutator_interval_seconds(0),
  52     _threshold_tolerance_percent(1.0 + ThresholdTolerance/100.0),
  53     _gc_pause_goal_sec(gc_pause_goal_sec),
  54     _young_gen_change_for_minor_throughput(0),
  55     _old_gen_change_for_major_throughput(0) {
  56   _avg_minor_pause    =
  57     new AdaptivePaddedAverage(AdaptiveTimeWeight, PausePadding);
  58   _avg_minor_interval = new AdaptiveWeightedAverage(AdaptiveTimeWeight);
  59   _avg_minor_gc_cost  = new AdaptiveWeightedAverage(AdaptiveTimeWeight);
  60   _avg_major_gc_cost  = new AdaptiveWeightedAverage(AdaptiveTimeWeight);
  61 
  62   _avg_young_live     = new AdaptiveWeightedAverage(AdaptiveSizePolicyWeight);
  63   _avg_old_live       = new AdaptiveWeightedAverage(AdaptiveSizePolicyWeight);
  64   _avg_eden_live      = new AdaptiveWeightedAverage(AdaptiveSizePolicyWeight);
  65 
  66   _avg_survived       = new AdaptivePaddedAverage(AdaptiveSizePolicyWeight,
  67                                                   SurvivorPadding);
  68   _avg_pretenured     = new AdaptivePaddedNoZeroDevAverage(
  69                                                   AdaptiveSizePolicyWeight,
  70                                                   SurvivorPadding);
  71 
  72   _minor_pause_old_estimator =
  73     new LinearLeastSquareFit(AdaptiveSizePolicyWeight);
  74   _minor_pause_young_estimator =
  75     new LinearLeastSquareFit(AdaptiveSizePolicyWeight);
  76   _minor_collection_estimator =
  77     new LinearLeastSquareFit(AdaptiveSizePolicyWeight);
  78   _major_collection_estimator =
  79     new LinearLeastSquareFit(AdaptiveSizePolicyWeight);
  80 
  81   // Start the timers
  82   _minor_timer.start();
  83 
  84   _young_gen_policy_is_ready = false;
  85 }
  86 
  87 bool AdaptiveSizePolicy::tenuring_threshold_change() const {
  88   return decrement_tenuring_threshold_for_gc_cost() ||
  89          increment_tenuring_threshold_for_gc_cost() ||
  90          decrement_tenuring_threshold_for_survivor_limit();
  91 }
  92 
  93 void AdaptiveSizePolicy::minor_collection_begin() {
  94   // Update the interval time
  95   _minor_timer.stop();
  96   // Save most recent collection time
  97   _latest_minor_mutator_interval_seconds = _minor_timer.seconds();
  98   _minor_timer.reset();
  99   _minor_timer.start();
 100 }
 101 
 102 void AdaptiveSizePolicy::update_minor_pause_young_estimator(
 103     double minor_pause_in_ms) {
 104   double eden_size_in_mbytes = ((double)_eden_size)/((double)M);
 105   _minor_pause_young_estimator->update(eden_size_in_mbytes,
 106     minor_pause_in_ms);
 107 }
 108 
 109 void AdaptiveSizePolicy::minor_collection_end(GCCause::Cause gc_cause) {
 110   // Update the pause time.
 111   _minor_timer.stop();
 112 
 113   if (!GCCause::is_user_requested_gc(gc_cause) ||
 114       UseAdaptiveSizePolicyWithSystemGC) {
 115     double minor_pause_in_seconds = _minor_timer.seconds();
 116     double minor_pause_in_ms = minor_pause_in_seconds * MILLIUNITS;
 117 
 118     // Sample for performance counter
 119     _avg_minor_pause->sample(minor_pause_in_seconds);
 120 
 121     // Cost of collection (unit-less)
 122     double collection_cost = 0.0;
 123     if ((_latest_minor_mutator_interval_seconds > 0.0) &&
 124         (minor_pause_in_seconds > 0.0)) {
 125       double interval_in_seconds =
 126         _latest_minor_mutator_interval_seconds + minor_pause_in_seconds;
 127       collection_cost =
 128         minor_pause_in_seconds / interval_in_seconds;
 129       _avg_minor_gc_cost->sample(collection_cost);
 130       // Sample for performance counter
 131       _avg_minor_interval->sample(interval_in_seconds);
 132     }
 133 
 134     // The policy does not have enough data until at least some
 135     // young collections have been done.
 136     _young_gen_policy_is_ready =
 137       (_avg_minor_gc_cost->count() >= AdaptiveSizePolicyReadyThreshold);
 138 
 139     // Calculate variables used to estimate pause time vs. gen sizes
 140     double eden_size_in_mbytes = ((double)_eden_size) / ((double)M);
 141     update_minor_pause_young_estimator(minor_pause_in_ms);
 142     update_minor_pause_old_estimator(minor_pause_in_ms);
 143 
 144     log_trace(gc, ergo)("AdaptiveSizePolicy::minor_collection_end: minor gc cost: %f  average: %f",
 145                         collection_cost, _avg_minor_gc_cost->average());
 146     log_trace(gc, ergo)("  minor pause: %f minor period %f",
 147                         minor_pause_in_ms, _latest_minor_mutator_interval_seconds * MILLIUNITS);
 148 
 149     // Calculate variable used to estimate collection cost vs. gen sizes
 150     assert(collection_cost >= 0.0, "Expected to be non-negative");
 151     _minor_collection_estimator->update(eden_size_in_mbytes, collection_cost);
 152   }
 153 
 154   // Interval times use this timer to measure the mutator time.
 155   // Reset the timer after the GC pause.
 156   _minor_timer.reset();
 157   _minor_timer.start();
 158 }
 159 
 160 size_t AdaptiveSizePolicy::eden_increment(size_t cur_eden, uint percent_change) {
 161   size_t eden_heap_delta;
 162   eden_heap_delta = cur_eden / 100 * percent_change;
 163   return eden_heap_delta;
 164 }
 165 
 166 size_t AdaptiveSizePolicy::eden_increment(size_t cur_eden) {
 167   return eden_increment(cur_eden, YoungGenerationSizeIncrement);
 168 }
 169 
 170 size_t AdaptiveSizePolicy::eden_decrement(size_t cur_eden) {
 171   size_t eden_heap_delta = eden_increment(cur_eden) /
 172     AdaptiveSizeDecrementScaleFactor;
 173   return eden_heap_delta;
 174 }
 175 
 176 size_t AdaptiveSizePolicy::promo_increment(size_t cur_promo, uint percent_change) {
 177   size_t promo_heap_delta;
 178   promo_heap_delta = cur_promo / 100 * percent_change;
 179   return promo_heap_delta;
 180 }
 181 
 182 size_t AdaptiveSizePolicy::promo_increment(size_t cur_promo) {
 183   return promo_increment(cur_promo, TenuredGenerationSizeIncrement);
 184 }
 185 
 186 size_t AdaptiveSizePolicy::promo_decrement(size_t cur_promo) {
 187   size_t promo_heap_delta = promo_increment(cur_promo);
 188   promo_heap_delta = promo_heap_delta / AdaptiveSizeDecrementScaleFactor;
 189   return promo_heap_delta;
 190 }
 191 
 192 double AdaptiveSizePolicy::time_since_major_gc() const {
 193   _major_timer.stop();
 194   double result = _major_timer.seconds();
 195   _major_timer.start();
 196   return result;
 197 }
 198 
 199 // Linear decay of major gc cost
 200 double AdaptiveSizePolicy::decaying_major_gc_cost() const {
 201   double major_interval = major_gc_interval_average_for_decay();
 202   double major_gc_cost_average = major_gc_cost();
 203   double decayed_major_gc_cost = major_gc_cost_average;
 204   if(time_since_major_gc() > 0.0) {
 205     decayed_major_gc_cost = major_gc_cost() *
 206       (((double) AdaptiveSizeMajorGCDecayTimeScale) * major_interval)
 207       / time_since_major_gc();
 208   }
 209 
 210   // The decayed cost should always be smaller than the
 211   // average cost but the vagaries of finite arithmetic could
 212   // produce a larger value in decayed_major_gc_cost so protect
 213   // against that.
 214   return MIN2(major_gc_cost_average, decayed_major_gc_cost);
 215 }
 216 
 217 // Use a value of the major gc cost that has been decayed
 218 // by the factor
 219 //
 220 //      average-interval-between-major-gc * AdaptiveSizeMajorGCDecayTimeScale /
 221 //        time-since-last-major-gc
 222 //
 223 // if the average-interval-between-major-gc * AdaptiveSizeMajorGCDecayTimeScale
 224 // is less than time-since-last-major-gc.
 225 //
 226 // In cases where there are initial major gc's that
 227 // are of a relatively high cost but no later major
 228 // gc's, the total gc cost can remain high because
 229 // the major gc cost remains unchanged (since there are no major
 230 // gc's).  In such a situation the value of the unchanging
 231 // major gc cost can keep the mutator throughput below
 232 // the goal when in fact the major gc cost is becoming diminishingly
 233 // small.  Use the decaying gc cost only to decide whether to
 234 // adjust for throughput.  Using it also to determine the adjustment
 235 // to be made for throughput also seems reasonable but there is
 236 // no test case to use to decide if it is the right thing to do
 237 // don't do it yet.
 238 
 239 double AdaptiveSizePolicy::decaying_gc_cost() const {
 240   double decayed_major_gc_cost = major_gc_cost();
 241   double avg_major_interval = major_gc_interval_average_for_decay();
 242   if (UseAdaptiveSizeDecayMajorGCCost &&
 243       (AdaptiveSizeMajorGCDecayTimeScale > 0) &&
 244       (avg_major_interval > 0.00)) {
 245     double time_since_last_major_gc = time_since_major_gc();
 246 
 247     // Decay the major gc cost?
 248     if (time_since_last_major_gc >
 249         ((double) AdaptiveSizeMajorGCDecayTimeScale) * avg_major_interval) {
 250 
 251       // Decay using the time-since-last-major-gc
 252       decayed_major_gc_cost = decaying_major_gc_cost();
 253       log_trace(gc, ergo)("decaying_gc_cost: major interval average: %f  time since last major gc: %f",
 254                     avg_major_interval, time_since_last_major_gc);
 255       log_trace(gc, ergo)("  major gc cost: %f  decayed major gc cost: %f",
 256                     major_gc_cost(), decayed_major_gc_cost);
 257     }
 258   }
 259   double result = MIN2(1.0, decayed_major_gc_cost + minor_gc_cost());
 260   return result;
 261 }
 262 
 263 
 264 void AdaptiveSizePolicy::clear_generation_free_space_flags() {
 265   set_change_young_gen_for_min_pauses(0);
 266   set_change_old_gen_for_maj_pauses(0);
 267 
 268   set_change_old_gen_for_throughput(0);
 269   set_change_young_gen_for_throughput(0);
 270   set_decrease_for_footprint(0);
 271   set_decide_at_full_gc(0);
 272 }
 273 
 274 class AdaptiveSizePolicyTimeOverheadTester: public GCOverheadTester {
 275   double _gc_cost;
 276 
 277  public:
 278   AdaptiveSizePolicyTimeOverheadTester(double gc_cost) : _gc_cost(gc_cost) {}
 279 
 280   bool is_exceeded() {
 281     // Note that the gc time limit test only works for the collections
 282     // of the young gen + tenured gen and not for collections of the
 283     // permanent gen.  That is because the calculation of the space
 284     // freed by the collection is the free space in the young gen +
 285     // tenured gen.
 286     return _gc_cost > (GCTimeLimit / 100.0);
 287   }
 288 };
 289 
 290 class AdaptiveSizePolicySpaceOverheadTester: public GCOverheadTester {
 291   size_t _eden_live;
 292   size_t _max_old_gen_size;
 293   size_t _max_eden_size;
 294   size_t _promo_size;
 295   double _avg_eden_live;
 296   double _avg_old_live;
 297 
 298  public:
 299   AdaptiveSizePolicySpaceOverheadTester(size_t eden_live,
 300                                         size_t max_old_gen_size,
 301                                         size_t max_eden_size,
 302                                         size_t promo_size,
 303                                         double avg_eden_live,
 304                                         double avg_old_live) :
 305     _eden_live(eden_live),
 306     _max_old_gen_size(max_old_gen_size),
 307     _max_eden_size(max_eden_size),
 308     _promo_size(promo_size),
 309     _avg_eden_live(avg_eden_live),
 310     _avg_old_live(avg_old_live) {}
 311 
 312   bool is_exceeded() {
 313     // _max_eden_size is the upper limit on the size of eden based on
 314     // the maximum size of the young generation and the sizes
 315     // of the survivor space.
 316     // The question being asked is whether the space being recovered by
 317     // a collection is low.
 318     // free_in_eden is the free space in eden after a collection and
 319     // free_in_old_gen is the free space in the old generation after
 320     // a collection.
 321     //
 322     // Use the minimum of the current value of the live in eden
 323     // or the average of the live in eden.
 324     // If the current value drops quickly, that should be taken
 325     // into account (i.e., don't trigger if the amount of free
 326     // space has suddenly jumped up).  If the current is much
 327     // higher than the average, use the average since it represents
 328     // the longer term behavior.
 329     const size_t live_in_eden =
 330       MIN2(_eden_live, (size_t)_avg_eden_live);
 331     const size_t free_in_eden = _max_eden_size > live_in_eden ?
 332       _max_eden_size - live_in_eden : 0;
 333     const size_t free_in_old_gen = (size_t)(_max_old_gen_size - _avg_old_live);
 334     const size_t total_free_limit = free_in_old_gen + free_in_eden;
 335     const size_t total_mem = _max_old_gen_size + _max_eden_size;
 336     const double free_limit_ratio = GCHeapFreeLimit / 100.0;
 337     const double mem_free_limit = total_mem * free_limit_ratio;
 338     const double mem_free_old_limit = _max_old_gen_size * free_limit_ratio;
 339     const double mem_free_eden_limit = _max_eden_size * free_limit_ratio;
 340     size_t promo_limit = (size_t)(_max_old_gen_size - _avg_old_live);
 341     // But don't force a promo size below the current promo size. Otherwise,
 342     // the promo size will shrink for no good reason.
 343     promo_limit = MAX2(promo_limit, _promo_size);
 344 
 345     log_trace(gc, ergo)(
 346           "AdaptiveSizePolicySpaceOverheadTester::is_exceeded:"
 347           " promo_limit: " SIZE_FORMAT
 348           " max_eden_size: " SIZE_FORMAT
 349           " total_free_limit: " SIZE_FORMAT
 350           " max_old_gen_size: " SIZE_FORMAT
 351           " max_eden_size: " SIZE_FORMAT
 352           " mem_free_limit: " SIZE_FORMAT,
 353           promo_limit, _max_eden_size, total_free_limit,
 354           _max_old_gen_size, _max_eden_size,
 355           (size_t)mem_free_limit);
 356 
 357     return free_in_old_gen < (size_t)mem_free_old_limit &&
 358            free_in_eden < (size_t)mem_free_eden_limit;
 359   }
 360 };
 361 
 362 void AdaptiveSizePolicy::check_gc_overhead_limit(
 363                                           size_t eden_live,
 364                                           size_t max_old_gen_size,
 365                                           size_t max_eden_size,
 366                                           bool   is_full_gc,
 367                                           GCCause::Cause gc_cause,
 368                                           SoftRefPolicy* soft_ref_policy) {
 369 
 370   AdaptiveSizePolicyTimeOverheadTester time_overhead(gc_cost());
 371   AdaptiveSizePolicySpaceOverheadTester space_overhead(eden_live,
 372                                                        max_old_gen_size,
 373                                                        max_eden_size,
 374                                                        _promo_size,
 375                                                        avg_eden_live()->average(),
 376                                                        avg_old_live()->average());
 377   _overhead_checker.check_gc_overhead_limit(&time_overhead,
 378                                             &space_overhead,
 379                                             is_full_gc,
 380                                             gc_cause,
 381                                             soft_ref_policy);
 382 }
 383 // Printing
 384 
 385 bool AdaptiveSizePolicy::print() const {
 386   assert(UseAdaptiveSizePolicy, "UseAdaptiveSizePolicy need to be enabled.");
 387 
 388   if (!log_is_enabled(Debug, gc, ergo)) {
 389     return false;
 390   }
 391 
 392   // Print goal for which action is needed.
 393   char* action = NULL;
 394   bool change_for_pause = false;
 395   if ((change_old_gen_for_maj_pauses() ==
 396          decrease_old_gen_for_maj_pauses_true) ||
 397       (change_young_gen_for_min_pauses() ==
 398          decrease_young_gen_for_min_pauses_true)) {
 399     action = (char*) " *** pause time goal ***";
 400     change_for_pause = true;
 401   } else if ((change_old_gen_for_throughput() ==
 402                increase_old_gen_for_throughput_true) ||
 403             (change_young_gen_for_throughput() ==
 404                increase_young_gen_for_througput_true)) {
 405     action = (char*) " *** throughput goal ***";
 406   } else if (decrease_for_footprint()) {
 407     action = (char*) " *** reduced footprint ***";
 408   } else {
 409     // No actions were taken.  This can legitimately be the
 410     // situation if not enough data has been gathered to make
 411     // decisions.
 412     return false;
 413   }
 414 
 415   // Pauses
 416   // Currently the size of the old gen is only adjusted to
 417   // change the major pause times.
 418   char* young_gen_action = NULL;
 419   char* tenured_gen_action = NULL;
 420 
 421   char* shrink_msg = (char*) "(attempted to shrink)";
 422   char* grow_msg = (char*) "(attempted to grow)";
 423   char* no_change_msg = (char*) "(no change)";
 424   if (change_young_gen_for_min_pauses() ==
 425       decrease_young_gen_for_min_pauses_true) {
 426     young_gen_action = shrink_msg;
 427   } else if (change_for_pause) {
 428     young_gen_action = no_change_msg;
 429   }
 430 
 431   if (change_old_gen_for_maj_pauses() == decrease_old_gen_for_maj_pauses_true) {
 432     tenured_gen_action = shrink_msg;
 433   } else if (change_for_pause) {
 434     tenured_gen_action = no_change_msg;
 435   }
 436 
 437   // Throughput
 438   if (change_old_gen_for_throughput() == increase_old_gen_for_throughput_true) {
 439     assert(change_young_gen_for_throughput() ==
 440            increase_young_gen_for_througput_true,
 441            "Both generations should be growing");
 442     young_gen_action = grow_msg;
 443     tenured_gen_action = grow_msg;
 444   } else if (change_young_gen_for_throughput() ==
 445              increase_young_gen_for_througput_true) {
 446     // Only the young generation may grow at start up (before
 447     // enough full collections have been done to grow the old generation).
 448     young_gen_action = grow_msg;
 449     tenured_gen_action = no_change_msg;
 450   }
 451 
 452   // Minimum footprint
 453   if (decrease_for_footprint() != 0) {
 454     young_gen_action = shrink_msg;
 455     tenured_gen_action = shrink_msg;
 456   }
 457 
 458   log_debug(gc, ergo)("UseAdaptiveSizePolicy actions to meet %s", action);
 459   log_debug(gc, ergo)("                       GC overhead (%%)");
 460   log_debug(gc, ergo)("    Young generation:     %7.2f\t  %s",
 461                       100.0 * avg_minor_gc_cost()->average(), young_gen_action);
 462   log_debug(gc, ergo)("    Tenured generation:   %7.2f\t  %s",
 463                       100.0 * avg_major_gc_cost()->average(), tenured_gen_action);
 464   return true;
 465 }
 466 
 467 void AdaptiveSizePolicy::print_tenuring_threshold( uint new_tenuring_threshold_arg) const {
 468   // Tenuring threshold
 469   if (decrement_tenuring_threshold_for_survivor_limit()) {
 470     log_debug(gc, ergo)("Tenuring threshold: (attempted to decrease to avoid survivor space overflow) = %u", new_tenuring_threshold_arg);
 471   } else if (decrement_tenuring_threshold_for_gc_cost()) {
 472     log_debug(gc, ergo)("Tenuring threshold: (attempted to decrease to balance GC costs) = %u", new_tenuring_threshold_arg);
 473   } else if (increment_tenuring_threshold_for_gc_cost()) {
 474     log_debug(gc, ergo)("Tenuring threshold: (attempted to increase to balance GC costs) = %u", new_tenuring_threshold_arg);
 475   } else {
 476     assert(!tenuring_threshold_change(), "(no change was attempted)");
 477   }
 478 }