/*

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

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

#include "gc/g1/g1CollectionSet.hpp"

#include "gc/g1/g1ConcurrentMark.hpp"

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

#include "gc/g1/g1ConcurrentRefine.hpp"

#include "gc/g1/g1HotCardCache.hpp"

#include "gc/g1/g1IHOPControl.hpp"

#include "gc/g1/g1GCPhaseTimes.hpp"

#include "gc/g1/g1Policy.hpp"

#include "gc/g1/g1SurvivorRegions.hpp"

#include "gc/g1/g1YoungGenSizer.hpp"

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

#include "gc/g1/heapRegionRemSet.hpp"

#include "gc/shared/gcPolicyCounters.hpp"

#include "logging/logStream.hpp"

#include "runtime/arguments.hpp"

#include "runtime/java.hpp"

#include "runtime/mutexLocker.hpp"

#include "utilities/debug.hpp"

#include "utilities/growableArray.hpp"

#include "utilities/pair.hpp"

G1Policy::G1Policy(STWGCTimer* gc_timer) :

  _predictor(G1ConfidencePercent / 100.0),

  _analytics(new G1Analytics(&_predictor)),

  _remset_tracker(),

  _mmu_tracker(new G1MMUTrackerQueue(GCPauseIntervalMillis / 1000.0, MaxGCPauseMillis / 1000.0)),

  _ihop_control(create_ihop_control(&_predictor)),

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

  _young_list_fixed_length(0),

  _short_lived_surv_rate_group(new SurvRateGroup()),

  _survivor_surv_rate_group(new SurvRateGroup()),

  _reserve_factor((double) G1ReservePercent / 100.0),

  _reserve_regions(0),

  _rs_lengths_prediction(0),

  _bytes_allocated_in_old_since_last_gc(0),

  _initial_mark_to_mixed(),

  _collection_set(NULL),

  _g1h(NULL),

  _phase_times(new G1GCPhaseTimes(gc_timer, ParallelGCThreads)),

  _tenuring_threshold(MaxTenuringThreshold),

  _max_survivor_regions(0),

  _survivors_age_table(true),

  _collection_pause_end_millis(os::javaTimeNanos() / NANOSECS_PER_MILLISEC) {

}

G1Policy::~G1Policy() {

  delete _ihop_control;

}

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

void G1Policy::init(G1CollectedHeap* g1h, G1CollectionSet* collection_set) {

  _g1h = g1h;

  _collection_set = collection_set;

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

  if (!adaptive_young_list_length()) {

    _young_list_fixed_length = _young_gen_sizer.min_desired_young_length();

  }

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

  _free_regions_at_end_of_collection = _g1h->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();

}

class G1YoungLengthPredictor {

  const bool _during_cm;

  const double _base_time_ms;

  const double _base_free_regions;

  const double _target_pause_time_ms;

  const G1Policy* const _policy;

 public:

  G1YoungLengthPredictor(bool during_cm,

                         double base_time_ms,

                         double base_free_regions,

                         double target_pause_time_ms,

                         const G1Policy* policy) :

    _during_cm(during_cm),

    _base_time_ms(base_time_ms),

    _base_free_regions(base_free_regions),

    _target_pause_time_ms(target_pause_time_ms),

    _policy(policy) {}

  bool will_fit(uint young_length) const {

    if (young_length >= _base_free_regions) {

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

      return false;

    }

    const double accum_surv_rate = _policy->accum_yg_surv_rate_pred((int) young_length - 1);

    const size_t bytes_to_copy =

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

    const double copy_time_ms =

      _policy->analytics()->predict_object_copy_time_ms(bytes_to_copy, _during_cm);

    const double young_other_time_ms = _policy->analytics()->predict_young_other_time_ms(young_length);

    const 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;

    }

    const 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.

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

    const 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 = _g1h->survivor_regions_count();

  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(_g1h->eden_regions_count(), (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()->in_young_only_phase()) {

      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()->in_young_only_phase(), "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;

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

  const double survivor_regions_evac_time = predict_survivor_regions_evac_time();

  const size_t pending_cards = _analytics->predict_pending_cards();

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

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

  const double base_time_ms =

    predict_base_elapsed_time_ms(pending_cards, scanned_cards) +

    survivor_regions_evac_time;

  const uint available_free_regions = _free_regions_at_end_of_collection;

  const uint base_free_regions =

    available_free_regions > _reserve_regions ? available_free_regions - _reserve_regions : 0;

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

  // makes sense fits within the target pause time.

  G1YoungLengthPredictor p(collector_state()->mark_or_rebuild_in_progress(),

                           base_time_ms,

                           base_free_regions,

                           target_pause_time_ms,

                           this);

  if (p.will_fit(min_young_length)) {

    // 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 (p.will_fit(max_young_length)) {

      // 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 (p.will_fit(young_length)) {

          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(p.will_fit(min_young_length),

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

             "fit into the pause target");

      assert(!p.will_fit(min_young_length + 1),

             "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;

  const GrowableArray<HeapRegion*>* survivor_regions = _g1h->survivor()->regions();

  for (GrowableArrayIterator<HeapRegion*> it = survivor_regions->begin();

       it != survivor_regions->end();

       ++it) {

    survivor_regions_evac_time += predict_region_elapsed_time_ms(*it, collector_state()->in_young_only_phase());

  }

  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()->in_young_only_phase() && adaptive_young_list_length()) {

    _rs_lengths_prediction = prediction;

  }

}

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_in_young_only_phase(false);

  collector_state()->set_in_full_gc(true);

  cset_chooser()->clear();

}

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_in_full_gc(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_in_young_only_phase(true);

  collector_state()->set_in_young_gc_before_mixed(false);

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

  collector_state()->set_in_initial_mark_gc(false);

  collector_state()->set_mark_or_rebuild_in_progress(false);

  collector_state()->set_clearing_next_bitmap(false);

  _short_lived_surv_rate_group->start_adding_regions();

  // also call this on any additional surv rate groups

  _free_regions_at_end_of_collection = _g1h->num_free_regions();

  // Reset survivors SurvRateGroup.

  _survivor_surv_rate_group->reset();

  update_young_list_max_and_target_length();

  update_rs_lengths_prediction();

  _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(_g1h->used() == _g1h->recalculate_used(),

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

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

  phase_times()->record_cur_collection_start_sec(start_time_sec);

  _pending_cards = _g1h->pending_card_num();

  _collection_set->reset_bytes_used_before();

  _bytes_copied_during_gc = 0;

  // do that for any other surv rate groups

  _short_lived_surv_rate_group->stop_adding_regions();

  _survivors_age_table.clear();

  assert(_g1h->collection_set()->verify_young_ages(), "region age verification failed");

}

void G1Policy::record_concurrent_mark_init_end(double mark_init_elapsed_time_ms) {

  assert(!collector_state()->initiate_conc_mark_if_possible(), "we should have cleared it by now");

  collector_state()->set_in_initial_mark_gc(false);

}

void G1Policy::record_concurrent_mark_remark_start() {

  _mark_remark_start_sec = os::elapsedTime();

}

void G1Policy::record_concurrent_mark_remark_end() {

  double end_time_sec = os::elapsedTime();

  double elapsed_time_ms = (end_time_sec - _mark_remark_start_sec)*1000.0;

  _analytics->report_concurrent_mark_remark_times_ms(elapsed_time_ms);

  _analytics->append_prev_collection_pause_end_ms(elapsed_time_ms);

  record_pause(Remark, _mark_remark_start_sec, end_time_sec);

}

void G1Policy::record_concurrent_mark_cleanup_start() {

  _mark_cleanup_start_sec = os::elapsedTime();

}

double G1Policy::average_time_ms(G1GCPhaseTimes::GCParPhases phase) const {

  return phase_times()->average_time_ms(phase);

}

double G1Policy::young_other_time_ms() const {

  return phase_times()->young_cset_choice_time_ms() +

         phase_times()->average_time_ms(G1GCPhaseTimes::YoungFreeCSet);

}