/*
 * Copyright (c) 2016, 2020, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "precompiled.hpp"
#include "gc/g1/g1_globals.hpp"
#include "gc/g1/g1CollectedHeap.hpp"
#include "gc/g1/g1HeapSizingPolicy.hpp"
#include "gc/g1/g1Analytics.hpp"
#include "logging/log.hpp"
#include "runtime/globals.hpp"
#include "utilities/debug.hpp"
#include "utilities/globalDefinitions.hpp"

G1HeapSizingPolicy* G1HeapSizingPolicy::create(const G1CollectedHeap* g1h, const G1Analytics* analytics) {
  return new G1HeapSizingPolicy(g1h, analytics);
}

G1HeapSizingPolicy::G1HeapSizingPolicy(const G1CollectedHeap* g1h, const G1Analytics* analytics) :
  _g1h(g1h),
  _analytics(analytics),
  _long_term_interval(analytics->number_of_recorded_pause_times()),
  // Bias for expansion at startup; the +1 is to counter the first sample always
  // being 0.0, i.e. lower than any threshold.
  _ratio_exceeds_threshold(MinOverThresholdForExpansion / 2 + 1),
  _recent_pause_ratios(analytics->number_of_recorded_pause_times()),
  _long_term_count(0) {

  assert(_ratio_exceeds_threshold < MinOverThresholdForExpansion,
         "Initial ratio counter value too high.");
  assert(_ratio_exceeds_threshold > -MinOverThresholdForExpansion,
         "Initial ratio counter value too low.");
  assert(MinOverThresholdForExpansion < _long_term_interval,
         "Expansion threshold count must be less than %u", _long_term_interval);
  assert(MinOverThresholdForShrink < _long_term_interval,
         "Shrink threshold count must be less than %u", _long_term_interval);
}

void G1HeapSizingPolicy::reset_ratio_tracking_data() {
  _long_term_count = 0;
  _ratio_exceeds_threshold = 0;
  // Keep the recent gc time ratio data.
}

void G1HeapSizingPolicy::decay_ratio_tracking_data() {
  _long_term_count = 0;
  _ratio_exceeds_threshold /= 2;
  // Keep the recent gc time ratio data.
}

double G1HeapSizingPolicy::scale_with_heap(double pause_time_threshold) {
  double threshold = pause_time_threshold;
  // If the heap is at less than half its maximum size, scale the threshold down,
  // to a limit of 1%. Thus the smaller the heap is, the more likely it is to expand,
  // though the scaling code will likely keep the increase small.
  if (_g1h->capacity() <= _g1h->max_capacity() / 2) {
    threshold *= (double)_g1h->capacity() / (double)(_g1h->max_capacity() / 2);
    threshold = MAX2(threshold, 0.01);
  }

  return threshold;
}

double G1HeapSizingPolicy::scale_resize_ratio_delta(double ratio_delta) {
  // If the delta is small (less than the StartScaleDownAt value), scale the size
  // down linearly, but not by less than MinScaleDownFactor. If the delta is large
  // (greater than the StartScaleUpAt value), scale up, but adding no more than
  // MaxScaleUpFactor times the base size. The scaling will be linear in the range
  // from StartScaleUpAt to (StartScaleUpAt + ScaleUpRange). In other words,
  // ScaleUpRange sets the rate of scaling up.
  double const MinScaleDownFactor = 0.2;
  double const MaxScaleUpFactor = 2.0;

  double const StartScaleDownAt = 1.0;
  double const StartScaleUpAt = 1.5;
  double const ScaleUpRange = 4.0;

  double scale_factor;
  if (ratio_delta < StartScaleDownAt) {
    scale_factor = ratio_delta / StartScaleDownAt;
    scale_factor = MAX2(scale_factor, MinScaleDownFactor);
  } else if (ratio_delta > StartScaleUpAt) {
    scale_factor = 1 + ((ratio_delta - StartScaleUpAt) / ScaleUpRange);
    scale_factor = MIN2(scale_factor, MaxScaleUpFactor);
  }
  log_error(gc)("scaling ratio %1.2f scale %1.2f", ratio_delta, scale_factor);
  return scale_factor;
}

static void log_resize(double short_term_pause_time_ratio,
                       double long_term_pause_time_ratio,
                       double lower_threshold,
                       double upper_threshold,
                       double pause_time_ratio,
                       bool at_limit,
                       ssize_t resize_bytes) {

  log_debug(gc, ergo, heap)("Heap resize: "
                            "short term pause time ratio %1.2f%% long term pause time ratio %1.2f%% "
                            "lower threshold %1.2f%% upper threshold %1.2f%% pause time ratio %1.2f%% "
                            "at limit %s resize by " SSIZE_FORMAT "B",
                            short_term_pause_time_ratio * 100.0,
                            long_term_pause_time_ratio * 100.0,
                            lower_threshold * 100.0,
                            upper_threshold * 100.0,
                            pause_time_ratio * 100.0,
                            BOOL_TO_STR(at_limit),
                            resize_bytes);
}

ssize_t G1HeapSizingPolicy::resize_amount_after_young_gc() {
  assert(GCTimeRatio > 0, "must be");

  double long_term_pause_time_ratio = _analytics->long_term_pause_time_ratio();
  double short_term_pause_time_ratio = _analytics->short_term_pause_time_ratio();

  // Calculate gc time ratio thresholds:
  // - upper threshold, directly based on GCTimeRatio. We do not want to exceed
  // this.
  // - lower threshold, we do not want to go under.
  // - mid threshold, halfway between upper and lower threshold, represents the
  // actual target when resizing the heap.
  const double pause_time_threshold = 1.0 / (1.0 + GCTimeRatio);
  const double min_gc_time_ratio_ratio = G1MinimumPercentOfGCTimeRatio / 100.0;
  double upper_threshold = scale_with_heap(pause_time_threshold);
  double lower_threshold = upper_threshold * min_gc_time_ratio_ratio;

  // Explicitly use GCTimeRatio based threshold to more quickly expand and shrink
  // at smaller heap sizes.
  double mid_threshold = (upper_threshold + lower_threshold) / 2;

  // If the short term GC time ratio exceeds a threshold, increment the occurrence
  // counter.
  if (short_term_pause_time_ratio > upper_threshold) {
    _ratio_exceeds_threshold++;
  } else if (short_term_pause_time_ratio < lower_threshold) {
    _ratio_exceeds_threshold--;
  }
  double ratio_delta = (short_term_pause_time_ratio - mid_threshold) / mid_threshold;
  // Ignore very first sample as it is garbage.
  if (_long_term_count != 0 || _recent_pause_ratios.num() != 0) {
    _recent_pause_ratios.add(ratio_delta);
  }
  _long_term_count++;

  log_trace(gc, ergo, heap)("Heap resize triggers: long term count: %u "
                            "long term interval: %u "
                            "delta: %1.2f "
                            "ratio exceeds threshold count: %d",
                            _long_term_count,
                            _long_term_interval,
                            ratio_delta,
                            _ratio_exceeds_threshold);

  log_debug(gc, ergo, heap)("Heap triggers: pauses-since-start: %u num-prev-pauses-for-heuristics: %u ratio-exceeds-threshold-count: %d",
                            _recent_pause_ratios.num(), _long_term_interval, _ratio_exceeds_threshold);

  // Check if there is a short- or long-term need for resizing, expansion first.
  //
  // Short-term resizing need is detected by exceeding the upper or lower thresholds
  // multiple times, tracked in _ratio_exceeds_threshold. If it contains a large
  // positive or negative (larger than the respective thresholds), we trigger
  // resizing calculation.
  //
  // Slowly occurring long-term changes to the actual gc time ratios are checked
  // only every once a while.
  //
  // The _ratio_exceeds_threshold value is reset after each resize, or slowly
  // decayed if nothing happens.

  ssize_t resize_bytes = 0;

  bool check_long_term_resize = _long_term_count == _long_term_interval;

  if ((_ratio_exceeds_threshold == MinOverThresholdForExpansion) ||
      (check_long_term_resize && (long_term_pause_time_ratio > upper_threshold))) {

    // Short-cut the case when we are already fully expanded.
    if (_g1h->capacity() == _g1h->max_capacity()) {
      log_resize(short_term_pause_time_ratio, long_term_pause_time_ratio,
                 lower_threshold, upper_threshold, pause_time_threshold, true, 0);
      reset_ratio_tracking_data();
      return resize_bytes;
    }

    size_t reserved_bytes = _g1h->max_capacity();
    size_t committed_bytes = _g1h->capacity();
    size_t uncommitted_bytes = reserved_bytes - committed_bytes;
    size_t expand_bytes_via_pct =
      uncommitted_bytes * G1ExpandByPercentOfAvailable / 100;
    size_t min_expand_bytes = MIN2(HeapRegion::GrainBytes, uncommitted_bytes);
    double scale_factor = 1.0;

    // If the current size is less than 1/4 of the Initial heap size, expand
    // by half of the delta between the current and Initial sizes. IE, grow
    // back quickly.
    //
    // Otherwise, take the current size, or G1ExpandByPercentOfAvailable % of
    // the available expansion space, whichever is smaller, as the base
    // expansion size. Then possibly scale this size according to how much the
    // threshold has (on average) been exceeded by.
    if (committed_bytes < InitialHeapSize / 4) {
      resize_bytes = (InitialHeapSize - committed_bytes) / 2;
    } else {
      double ratio_delta = _recent_pause_ratios.avg();
      if (check_long_term_resize) {
        ratio_delta = MAX2(ratio_delta, (long_term_pause_time_ratio - mid_threshold) / mid_threshold);
      }
      log_error(gc)("expand deltas long %1.2f short %1.2f check long term %u", (long_term_pause_time_ratio - mid_threshold) / mid_threshold, _recent_pause_ratios.avg(), check_long_term_resize);
      scale_factor = scale_resize_ratio_delta(fabsd(ratio_delta));

      resize_bytes = MIN2(expand_bytes_via_pct, committed_bytes);
    }

    resize_bytes = static_cast<size_t>(resize_bytes * scale_factor);
 
    // Ensure the expansion size is at least the minimum growth amount
    // and at most the remaining uncommitted byte size.
    resize_bytes = clamp((size_t)resize_bytes, min_expand_bytes, uncommitted_bytes);

    reset_ratio_tracking_data();
  } else if ((_ratio_exceeds_threshold == -MinOverThresholdForShrink) ||
             (check_long_term_resize && (long_term_pause_time_ratio < lower_threshold))) {

    if (_g1h->capacity() == _g1h->min_capacity()) {
      log_resize(short_term_pause_time_ratio, long_term_pause_time_ratio,
                 lower_threshold, upper_threshold, pause_time_threshold, true, 0);
      reset_ratio_tracking_data();
      return resize_bytes;
    }

    // Shrink.
    double ratio_delta = _recent_pause_ratios.avg();
    if (check_long_term_resize) {
      // Intentionally use the max to limit the shrinking a bit.
      ratio_delta = MAX2(ratio_delta, (long_term_pause_time_ratio - mid_threshold) / mid_threshold);
    }
    log_error(gc)("shrink deltas long %1.2f short %1.2f long term %u", (long_term_pause_time_ratio - mid_threshold) / mid_threshold, _recent_pause_ratios.avg(), check_long_term_resize);

    double scale_factor = scale_resize_ratio_delta(fabsd(ratio_delta));
    scale_factor = clamp(scale_factor, 0.0, G1ShrinkByPercentOfAvailable / 100.0);

    // We are at the end of GC, so free regions are at maximum.
    size_t free_regions = _g1h->num_free_regions() * (1 - G1ReservePercent / 100.0);

    resize_bytes = -((double)HeapRegion::GrainBytes * scale_factor * free_regions);

    log_debug(gc)("shrink log: filled_hist %d target ratio: %1.2f%% ratio delta: %1.2f%% scale factor %1.2f%% free_regions " SIZE_FORMAT " resize_bytes " SSIZE_FORMAT,
                  check_long_term_resize, mid_threshold * 100.0, _recent_pause_ratios.avg() * 100.0, scale_factor * 100.0, free_regions, resize_bytes);

    reset_ratio_tracking_data();
  } else if (check_long_term_resize) {
    // A resize has not been triggered, but the long term counter overflowed.
    decay_ratio_tracking_data();
  }

  log_resize(short_term_pause_time_ratio, long_term_pause_time_ratio,
             lower_threshold, upper_threshold, pause_time_threshold,
             false, resize_bytes);

  return resize_bytes;
}

size_t G1HeapSizingPolicy::target_heap_capacity(size_t used_bytes, uintx free_ratio) const {
  const double free_percentage = (double) free_ratio / 100.0;
  const double used_percentage = 1.0 - free_percentage;

  // We have to be careful here as these two calculations can overflow
  // 32-bit size_t's.
  double used_bytes_d = (double) used_bytes;
  double desired_capacity_d = used_bytes_d / used_percentage;
  // Let's make sure that they are both under the max heap size, which
  // by default will make it fit into a size_t.
  double desired_capacity_upper_bound = (double) MaxHeapSize;
  desired_capacity_d = MIN2(desired_capacity_d, desired_capacity_upper_bound);
  // We can now safely turn it into size_t's.
  return (size_t) desired_capacity_d;
}