/*

 * Copyright (c) 2001, 2016, 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/concurrentG1Refine.hpp"

#include "gc/g1/concurrentMarkThread.inline.hpp"

#include "gc/g1/g1Analytics.hpp"

#include "gc/g1/g1CollectedHeap.inline.hpp"

#include "gc/g1/g1CollectionSet.hpp"

#include "gc/g1/g1ConcurrentMark.hpp"

#include "gc/g1/g1IHOPControl.hpp"

#include "gc/g1/g1GCPhaseTimes.hpp"

#include "gc/g1/g1Policy.hpp"

#include "gc/g1/g1YoungGenSizer.hpp"

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

#include "gc/g1/heapRegionRemSet.hpp"

#include "gc/shared/gcPolicyCounters.hpp"

#include "runtime/arguments.hpp"

#include "runtime/java.hpp"

#include "runtime/mutexLocker.hpp"

#include "utilities/debug.hpp"

#include "utilities/pair.hpp"

G1Policy::G1Policy() :

  _predictor(G1ConfidencePercent / 100.0),

  _analytics(new G1Analytics(&_predictor)),

  _policy_counters(new GCPolicyCounters("GarbageFirst", 1, 3)),

G1Policy::~G1Policy() {

  delete _ihop_control;

}

G1CollectorState* G1Policy::collector_state() const { return _g1->collector_state(); }

  assert(Heap_lock->owned_by_self(), "Locking discipline.");

    _young_list_fixed_length = _young_gen_sizer.min_desired_young_length();

  }

  _young_gen_sizer.adjust_max_new_size(_g1->max_regions());

  _free_regions_at_end_of_collection = _g1->num_free_regions();

  update_young_list_max_and_target_length();

  // We may immediately start allocating regions and placing them on the

  // collection set list. Initialize the per-collection set info

  _collection_set->start_incremental_building();

}

void G1Policy::note_gc_start() {

  phase_times()->note_gc_start();

}

bool G1Policy::predict_will_fit(uint young_length,

                                double base_time_ms,

                                uint base_free_regions,

                                double target_pause_time_ms) const {

  if (young_length >= base_free_regions) {

    // end condition 1: not enough space for the young regions

    return false;

  }

  double accum_surv_rate = accum_yg_surv_rate_pred((int) young_length - 1);

  size_t bytes_to_copy =

               (size_t) (accum_surv_rate * (double) HeapRegion::GrainBytes);

  double copy_time_ms = _analytics->predict_object_copy_time_ms(bytes_to_copy,

                                                                collector_state()->during_concurrent_mark());

  double young_other_time_ms = _analytics->predict_young_other_time_ms(young_length);

  double pause_time_ms = base_time_ms + copy_time_ms + young_other_time_ms;

  if (pause_time_ms > target_pause_time_ms) {

    // end condition 2: prediction is over the target pause time

    return false;

  }

  size_t free_bytes = (base_free_regions - young_length) * HeapRegion::GrainBytes;

  // When copying, we will likely need more bytes free than is live in the region.

  // Add some safety margin to factor in the confidence of our guess, and the

  // natural expected waste.

  // (100.0 / G1ConfidencePercent) is a scale factor that expresses the uncertainty

  // of the calculation: the lower the confidence, the more headroom.

  // (100 + TargetPLABWastePct) represents the increase in expected bytes during

  // copying due to anticipated waste in the PLABs.

  double safety_factor = (100.0 / G1ConfidencePercent) * (100 + TargetPLABWastePct) / 100.0;

  size_t expected_bytes_to_copy = (size_t)(safety_factor * bytes_to_copy);

  if (expected_bytes_to_copy > free_bytes) {

    // end condition 3: out-of-space

    return false;

  }

  // success!

  return true;

}

void G1Policy::record_new_heap_size(uint new_number_of_regions) {

  // re-calculate the necessary reserve

  double reserve_regions_d = (double) new_number_of_regions * _reserve_factor;

  // We use ceiling so that if reserve_regions_d is > 0.0 (but

  // smaller than 1.0) we'll get 1.

  _reserve_regions = (uint) ceil(reserve_regions_d);

  _young_gen_sizer.heap_size_changed(new_number_of_regions);

  _ihop_control->update_target_occupancy(new_number_of_regions * HeapRegion::GrainBytes);

}

uint G1Policy::calculate_young_list_desired_min_length(uint base_min_length) const {

  uint desired_min_length = 0;

  if (adaptive_young_list_length()) {

    if (_analytics->num_alloc_rate_ms() > 3) {

      double now_sec = os::elapsedTime();

      double when_ms = _mmu_tracker->when_max_gc_sec(now_sec) * 1000.0;

      double alloc_rate_ms = _analytics->predict_alloc_rate_ms();

      desired_min_length = (uint) ceil(alloc_rate_ms * when_ms);

    } else {

      // otherwise we don't have enough info to make the prediction

    }

  }

  desired_min_length += base_min_length;

  // make sure we don't go below any user-defined minimum bound

  return MAX2(_young_gen_sizer.min_desired_young_length(), desired_min_length);

}

uint G1Policy::calculate_young_list_desired_max_length() const {

  // Here, we might want to also take into account any additional

  // constraints (i.e., user-defined minimum bound). Currently, we

  // effectively don't set this bound.

  return _young_gen_sizer.max_desired_young_length();

}

uint G1Policy::update_young_list_max_and_target_length() {

  return update_young_list_max_and_target_length(_analytics->predict_rs_lengths());

}

uint G1Policy::update_young_list_max_and_target_length(size_t rs_lengths) {

  uint unbounded_target_length = update_young_list_target_length(rs_lengths);

  update_max_gc_locker_expansion();

  return unbounded_target_length;

}

uint G1Policy::update_young_list_target_length(size_t rs_lengths) {

  YoungTargetLengths young_lengths = young_list_target_lengths(rs_lengths);

  _young_list_target_length = young_lengths.first;

  return young_lengths.second;

}

G1Policy::YoungTargetLengths G1Policy::young_list_target_lengths(size_t rs_lengths) const {

  YoungTargetLengths result;

  // Calculate the absolute and desired min bounds first.

  // This is how many young regions we already have (currently: the survivors).

  const uint base_min_length = _g1->young_list()->survivor_length();

  uint desired_min_length = calculate_young_list_desired_min_length(base_min_length);

  // This is the absolute minimum young length. Ensure that we

  // will at least have one eden region available for allocation.

  uint absolute_min_length = base_min_length + MAX2(_g1->young_list()->eden_length(), (uint)1);

  // If we shrank the young list target it should not shrink below the current size.

  desired_min_length = MAX2(desired_min_length, absolute_min_length);

  // Calculate the absolute and desired max bounds.

  uint desired_max_length = calculate_young_list_desired_max_length();

  uint young_list_target_length = 0;

  if (adaptive_young_list_length()) {

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

      young_list_target_length =

                        calculate_young_list_target_length(rs_lengths,

                                                           base_min_length,

                                                           desired_min_length,

                                                           desired_max_length);

    } else {

      // Don't calculate anything and let the code below bound it to

      // the desired_min_length, i.e., do the next GC as soon as

      // possible to maximize how many old regions we can add to it.

    }

  } else {

    // The user asked for a fixed young gen so we'll fix the young gen

    // whether the next GC is young or mixed.

    young_list_target_length = _young_list_fixed_length;

  }

  result.second = young_list_target_length;

  // We will try our best not to "eat" into the reserve.

  uint absolute_max_length = 0;

  if (_free_regions_at_end_of_collection > _reserve_regions) {

    absolute_max_length = _free_regions_at_end_of_collection - _reserve_regions;

  }

  if (desired_max_length > absolute_max_length) {

    desired_max_length = absolute_max_length;

  }

  // Make sure we don't go over the desired max length, nor under the

  // desired min length. In case they clash, desired_min_length wins

  // which is why that test is second.

  if (young_list_target_length > desired_max_length) {

    young_list_target_length = desired_max_length;

  }

  if (young_list_target_length < desired_min_length) {

    young_list_target_length = desired_min_length;

  }

  assert(young_list_target_length > base_min_length,

         "we should be able to allocate at least one eden region");

  assert(young_list_target_length >= absolute_min_length, "post-condition");

  result.first = young_list_target_length;

  return result;

}

uint

G1Policy::calculate_young_list_target_length(size_t rs_lengths,

                                             uint base_min_length,

                                             uint desired_min_length,

                                             uint desired_max_length) const {

  assert(adaptive_young_list_length(), "pre-condition");

  assert(collector_state()->gcs_are_young(), "only call this for young GCs");

  // In case some edge-condition makes the desired max length too small...

  if (desired_max_length <= desired_min_length) {

    return desired_min_length;

  }

  // We'll adjust min_young_length and max_young_length not to include

  // the already allocated young regions (i.e., so they reflect the

  // min and max eden regions we'll allocate). The base_min_length

  // will be reflected in the predictions by the

  // survivor_regions_evac_time prediction.

  assert(desired_min_length > base_min_length, "invariant");

  uint min_young_length = desired_min_length - base_min_length;

  assert(desired_max_length > base_min_length, "invariant");

  uint max_young_length = desired_max_length - base_min_length;

  double target_pause_time_ms = _mmu_tracker->max_gc_time() * 1000.0;

  double survivor_regions_evac_time = predict_survivor_regions_evac_time();

  size_t pending_cards = _analytics->predict_pending_cards();

  size_t adj_rs_lengths = rs_lengths + _analytics->predict_rs_length_diff();

  size_t scanned_cards = _analytics->predict_card_num(adj_rs_lengths, /* gcs_are_young */ true);

  double base_time_ms =

    predict_base_elapsed_time_ms(pending_cards, scanned_cards) +

    survivor_regions_evac_time;

  uint available_free_regions = _free_regions_at_end_of_collection;

  uint base_free_regions = 0;

  if (available_free_regions > _reserve_regions) {

    base_free_regions = available_free_regions - _reserve_regions;

  }

  // Here, we will make sure that the shortest young length that

  // makes sense fits within the target pause time.

  if (predict_will_fit(min_young_length, base_time_ms,

                       base_free_regions, target_pause_time_ms)) {

    // The shortest young length will fit into the target pause time;

    // we'll now check whether the absolute maximum number of young

    // regions will fit in the target pause time. If not, we'll do

    // a binary search between min_young_length and max_young_length.

    if (predict_will_fit(max_young_length, base_time_ms,

                         base_free_regions, target_pause_time_ms)) {

      // The maximum young length will fit into the target pause time.

      // We are done so set min young length to the maximum length (as

      // the result is assumed to be returned in min_young_length).

      min_young_length = max_young_length;

    } else {

      // The maximum possible number of young regions will not fit within

      // the target pause time so we'll search for the optimal

      // length. The loop invariants are:

      //

      // min_young_length < max_young_length

      // min_young_length is known to fit into the target pause time

      // max_young_length is known not to fit into the target pause time

      //

      // Going into the loop we know the above hold as we've just

      // checked them. Every time around the loop we check whether

      // the middle value between min_young_length and

      // max_young_length fits into the target pause time. If it

      // does, it becomes the new min. If it doesn't, it becomes

      // the new max. This way we maintain the loop invariants.

      assert(min_young_length < max_young_length, "invariant");

      uint diff = (max_young_length - min_young_length) / 2;

      while (diff > 0) {

        uint young_length = min_young_length + diff;

        if (predict_will_fit(young_length, base_time_ms,

                             base_free_regions, target_pause_time_ms)) {

          min_young_length = young_length;

        } else {

          max_young_length = young_length;

        }

        assert(min_young_length <  max_young_length, "invariant");

        diff = (max_young_length - min_young_length) / 2;

      }

      // The results is min_young_length which, according to the

      // loop invariants, should fit within the target pause time.

      // These are the post-conditions of the binary search above:

      assert(min_young_length < max_young_length,

             "otherwise we should have discovered that max_young_length "

             "fits into the pause target and not done the binary search");

      assert(predict_will_fit(min_young_length, base_time_ms,

                              base_free_regions, target_pause_time_ms),

             "min_young_length, the result of the binary search, should "

             "fit into the pause target");

      assert(!predict_will_fit(min_young_length + 1, base_time_ms,

                               base_free_regions, target_pause_time_ms),

             "min_young_length, the result of the binary search, should be "

             "optimal, so no larger length should fit into the pause target");

    }

  } else {

    // Even the minimum length doesn't fit into the pause time

    // target, return it as the result nevertheless.

  }

  return base_min_length + min_young_length;

}

double G1Policy::predict_survivor_regions_evac_time() const {

  double survivor_regions_evac_time = 0.0;

  for (HeapRegion * r = _g1->young_list()->first_survivor_region();

       r != NULL && r != _g1->young_list()->last_survivor_region()->get_next_young_region();

       r = r->get_next_young_region()) {

    survivor_regions_evac_time += predict_region_elapsed_time_ms(r, collector_state()->gcs_are_young());

  }

  return survivor_regions_evac_time;

}

void G1Policy::revise_young_list_target_length_if_necessary(size_t rs_lengths) {

  guarantee( adaptive_young_list_length(), "should not call this otherwise" );

  if (rs_lengths > _rs_lengths_prediction) {

    // add 10% to avoid having to recalculate often

    size_t rs_lengths_prediction = rs_lengths * 1100 / 1000;

    update_rs_lengths_prediction(rs_lengths_prediction);

    update_young_list_max_and_target_length(rs_lengths_prediction);

  }

}

void G1Policy::update_rs_lengths_prediction() {

  update_rs_lengths_prediction(_analytics->predict_rs_lengths());

}

void G1Policy::update_rs_lengths_prediction(size_t prediction) {

  if (collector_state()->gcs_are_young() && adaptive_young_list_length()) {

    _rs_lengths_prediction = prediction;

  }

}

#ifndef PRODUCT

bool G1Policy::verify_young_ages() {

  HeapRegion* head = _g1->young_list()->first_region();

  return

    verify_young_ages(head, _short_lived_surv_rate_group);

  // also call verify_young_ages on any additional surv rate groups

}

bool G1Policy::verify_young_ages(HeapRegion* head, SurvRateGroup *surv_rate_group) {

  guarantee( surv_rate_group != NULL, "pre-condition" );

  const char* name = surv_rate_group->name();

  bool ret = true;

  int prev_age = -1;

  for (HeapRegion* curr = head;

       curr != NULL;

       curr = curr->get_next_young_region()) {

    SurvRateGroup* group = curr->surv_rate_group();

    if (group == NULL && !curr->is_survivor()) {

      log_error(gc, verify)("## %s: encountered NULL surv_rate_group", name);

      ret = false;

    }

    if (surv_rate_group == group) {

      int age = curr->age_in_surv_rate_group();

      if (age < 0) {

        log_error(gc, verify)("## %s: encountered negative age", name);

        ret = false;

      }

      if (age <= prev_age) {

        log_error(gc, verify)("## %s: region ages are not strictly increasing (%d, %d)", name, age, prev_age);

        ret = false;

      }

      prev_age = age;

    }

  }

  return ret;

}

#endif // PRODUCT

void G1Policy::record_full_collection_start() {

  _full_collection_start_sec = os::elapsedTime();

  // Release the future to-space so that it is available for compaction into.

  collector_state()->set_full_collection(true);

}

void G1Policy::record_full_collection_end() {

  // Consider this like a collection pause for the purposes of allocation

  // since last pause.

  double end_sec = os::elapsedTime();

  double full_gc_time_sec = end_sec - _full_collection_start_sec;

  double full_gc_time_ms = full_gc_time_sec * 1000.0;

  _analytics->update_recent_gc_times(end_sec, full_gc_time_ms);

  collector_state()->set_full_collection(false);

  // "Nuke" the heuristics that control the young/mixed GC

  // transitions and make sure we start with young GCs after the Full GC.

  collector_state()->set_gcs_are_young(true);

  collector_state()->set_last_young_gc(false);

  collector_state()->set_initiate_conc_mark_if_possible(need_to_start_conc_mark("end of Full GC", 0));

  collector_state()->set_during_initial_mark_pause(false);

  collector_state()->set_in_marking_window(false);

  collector_state()->set_in_marking_window_im(false);

  _short_lived_surv_rate_group->start_adding_regions();

  // also call this on any additional surv rate groups

  _free_regions_at_end_of_collection = _g1->num_free_regions();

  // Reset survivors SurvRateGroup.

  _survivor_surv_rate_group->reset();

  update_young_list_max_and_target_length();

  update_rs_lengths_prediction();

  cset_chooser()->clear();

  _bytes_allocated_in_old_since_last_gc = 0;

  record_pause(FullGC, _full_collection_start_sec, end_sec);

}

void G1Policy::record_collection_pause_start(double start_time_sec) {

  // We only need to do this here as the policy will only be applied

  // to the GC we're about to start. so, no point is calculating this

  // every time we calculate / recalculate the target young length.

  update_survivors_policy();

  assert(_g1->used() == _g1->recalculate_used(),

         "sanity, used: " SIZE_FORMAT " recalculate_used: " SIZE_FORMAT,

         _g1->used(), _g1->recalculate_used());

  phase_times()->record_cur_collection_start_sec(start_time_sec);

  _pending_cards = _g1->pending_card_num();

  _collection_set->reset_bytes_used_before();

  _bytes_copied_during_gc = 0;