/*

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

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

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

#include "gc/g1/g1CollectorPolicy.hpp"

#include "gc/g1/g1ErgoVerbose.hpp"

#include "gc/g1/g1GCPhaseTimes.hpp"

#include "gc/g1/g1Log.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"

// Different defaults for different number of GC threads

// They were chosen by running GCOld and SPECjbb on debris with different

//   numbers of GC threads and choosing them based on the results

// all the same

static double rs_length_diff_defaults[] = {

  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0

};

static double cost_per_card_ms_defaults[] = {

  0.01, 0.005, 0.005, 0.003, 0.003, 0.002, 0.002, 0.0015

};

// all the same

static double young_cards_per_entry_ratio_defaults[] = {

  1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0

};

static double cost_per_entry_ms_defaults[] = {

  0.015, 0.01, 0.01, 0.008, 0.008, 0.0055, 0.0055, 0.005

};

static double cost_per_byte_ms_defaults[] = {

  0.00006, 0.00003, 0.00003, 0.000015, 0.000015, 0.00001, 0.00001, 0.000009

};

// these should be pretty consistent

static double constant_other_time_ms_defaults[] = {

  5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0

};

static double young_other_cost_per_region_ms_defaults[] = {

  0.3, 0.2, 0.2, 0.15, 0.15, 0.12, 0.12, 0.1

};

static double non_young_other_cost_per_region_ms_defaults[] = {

  1.0, 0.7, 0.7, 0.5, 0.5, 0.42, 0.42, 0.30

};

G1CollectorPolicy::G1CollectorPolicy() :

  _predictor(G1ConfidencePercent / 100.0),

  _parallel_gc_threads(ParallelGCThreads),

  _recent_gc_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _stop_world_start(0.0),

  _concurrent_mark_remark_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _concurrent_mark_cleanup_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _alloc_rate_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _prev_collection_pause_end_ms(0.0),

  _rs_length_diff_seq(new TruncatedSeq(TruncatedSeqLength)),

  _cost_per_card_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _cost_scan_hcc_seq(new TruncatedSeq(TruncatedSeqLength)),

  _young_cards_per_entry_ratio_seq(new TruncatedSeq(TruncatedSeqLength)),

  _mixed_cards_per_entry_ratio_seq(new TruncatedSeq(TruncatedSeqLength)),

  _cost_per_entry_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _mixed_cost_per_entry_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _cost_per_byte_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _cost_per_byte_ms_during_cm_seq(new TruncatedSeq(TruncatedSeqLength)),

  _constant_other_time_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _young_other_cost_per_region_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _non_young_other_cost_per_region_ms_seq(

                                         new TruncatedSeq(TruncatedSeqLength)),

  _pending_cards_seq(new TruncatedSeq(TruncatedSeqLength)),

  _rs_lengths_seq(new TruncatedSeq(TruncatedSeqLength)),

  _pause_time_target_ms((double) MaxGCPauseMillis),

  _recent_prev_end_times_for_all_gcs_sec(

                                new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_avg_pause_time_ratio(0.0),

  _rs_lengths_prediction(0),

  _max_survivor_regions(0),

  _eden_used_bytes_before_gc(0),

  _survivor_used_bytes_before_gc(0),

  _heap_used_bytes_before_gc(0),

  _metaspace_used_bytes_before_gc(0),

  _eden_capacity_bytes_before_gc(0),

  _heap_capacity_bytes_before_gc(0),

  _eden_cset_region_length(0),

  _survivor_cset_region_length(0),

  _old_cset_region_length(0),

  _collection_set(NULL),

  _collection_set_bytes_used_before(0),

  // Incremental CSet attributes

  _inc_cset_build_state(Inactive),

  _inc_cset_head(NULL),

  _inc_cset_tail(NULL),

  _inc_cset_bytes_used_before(0),

  _inc_cset_max_finger(NULL),

  _inc_cset_recorded_rs_lengths(0),

  _inc_cset_recorded_rs_lengths_diffs(0),

  _inc_cset_predicted_elapsed_time_ms(0.0),

  _inc_cset_predicted_elapsed_time_ms_diffs(0.0),

  // add here any more surv rate groups

  _recorded_survivor_regions(0),

  _recorded_survivor_head(NULL),

  _recorded_survivor_tail(NULL),

  _survivors_age_table(true),

  _gc_overhead_perc(0.0) {

  // SurvRateGroups below must be initialized after the predictor because they

  // indirectly use it through this object passed to their constructor.

  _short_lived_surv_rate_group =

    new SurvRateGroup(&_predictor, "Short Lived", G1YoungSurvRateNumRegionsSummary);

  _survivor_surv_rate_group =

    new SurvRateGroup(&_predictor, "Survivor", G1YoungSurvRateNumRegionsSummary);

  // Set up the region size and associated fields. Given that the

  // policy is created before the heap, we have to set this up here,

  // so it's done as soon as possible.

  // It would have been natural to pass initial_heap_byte_size() and

  // max_heap_byte_size() to setup_heap_region_size() but those have

  // not been set up at this point since they should be aligned with

  // the region size. So, there is a circular dependency here. We base

  // the region size on the heap size, but the heap size should be

  // aligned with the region size. To get around this we use the

  // unaligned values for the heap.

  HeapRegion::setup_heap_region_size(InitialHeapSize, MaxHeapSize);

  HeapRegionRemSet::setup_remset_size();

  G1ErgoVerbose::initialize();

  if (PrintAdaptiveSizePolicy) {

    // Currently, we only use a single switch for all the heuristics.

    G1ErgoVerbose::set_enabled(true);

    // Given that we don't currently have a verboseness level

    // parameter, we'll hardcode this to high. This can be easily

    // changed in the future.

    G1ErgoVerbose::set_level(ErgoHigh);

  } else {

    G1ErgoVerbose::set_enabled(false);

  }

  _recent_prev_end_times_for_all_gcs_sec->add(os::elapsedTime());

  _prev_collection_pause_end_ms = os::elapsedTime() * 1000.0;

  _phase_times = new G1GCPhaseTimes(_parallel_gc_threads);

  int index = MIN2(_parallel_gc_threads - 1, 7);

  _rs_length_diff_seq->add(rs_length_diff_defaults[index]);

  _cost_per_card_ms_seq->add(cost_per_card_ms_defaults[index]);

  _cost_scan_hcc_seq->add(0.0);

  _young_cards_per_entry_ratio_seq->add(

                                  young_cards_per_entry_ratio_defaults[index]);

  _cost_per_entry_ms_seq->add(cost_per_entry_ms_defaults[index]);

  _cost_per_byte_ms_seq->add(cost_per_byte_ms_defaults[index]);

  _constant_other_time_ms_seq->add(constant_other_time_ms_defaults[index]);

  _young_other_cost_per_region_ms_seq->add(

                               young_other_cost_per_region_ms_defaults[index]);

  _non_young_other_cost_per_region_ms_seq->add(

                           non_young_other_cost_per_region_ms_defaults[index]);

  // Below, we might need to calculate the pause time target based on

  // the pause interval. When we do so we are going to give G1 maximum

  // flexibility and allow it to do pauses when it needs to. So, we'll

  // arrange that the pause interval to be pause time target + 1 to

  // ensure that a) the pause time target is maximized with respect to

  // the pause interval and b) we maintain the invariant that pause

  // time target < pause interval. If the user does not want this

  // maximum flexibility, they will have to set the pause interval

  // explicitly.

  // First make sure that, if either parameter is set, its value is

  // reasonable.

  if (!FLAG_IS_DEFAULT(MaxGCPauseMillis)) {

    if (MaxGCPauseMillis < 1) {

      vm_exit_during_initialization("MaxGCPauseMillis should be "

                                    "greater than 0");

    }

  }

  if (!FLAG_IS_DEFAULT(GCPauseIntervalMillis)) {

    if (GCPauseIntervalMillis < 1) {

      vm_exit_during_initialization("GCPauseIntervalMillis should be "

                                    "greater than 0");

    }

  }

  // Then, if the pause time target parameter was not set, set it to

  // the default value.

  if (FLAG_IS_DEFAULT(MaxGCPauseMillis)) {

    if (FLAG_IS_DEFAULT(GCPauseIntervalMillis)) {

      // The default pause time target in G1 is 200ms

      FLAG_SET_DEFAULT(MaxGCPauseMillis, 200);

    } else {

      // We do not allow the pause interval to be set without the

      // pause time target

      vm_exit_during_initialization("GCPauseIntervalMillis cannot be set "

                                    "without setting MaxGCPauseMillis");

    }

  }

  // Then, if the interval parameter was not set, set it according to

  // the pause time target (this will also deal with the case when the

  // pause time target is the default value).

  if (FLAG_IS_DEFAULT(GCPauseIntervalMillis)) {

    FLAG_SET_DEFAULT(GCPauseIntervalMillis, MaxGCPauseMillis + 1);

  }

  // Finally, make sure that the two parameters are consistent.

  if (MaxGCPauseMillis >= GCPauseIntervalMillis) {

    char buffer[256];

    jio_snprintf(buffer, 256,

                 "MaxGCPauseMillis (%u) should be less than "

                 "GCPauseIntervalMillis (%u)",

                 MaxGCPauseMillis, GCPauseIntervalMillis);

    vm_exit_during_initialization(buffer);

  }

  double max_gc_time = (double) MaxGCPauseMillis / 1000.0;

  double time_slice  = (double) GCPauseIntervalMillis / 1000.0;

  _mmu_tracker = new G1MMUTrackerQueue(time_slice, max_gc_time);

  // start conservatively (around 50ms is about right)

  _concurrent_mark_remark_times_ms->add(0.05);

  _concurrent_mark_cleanup_times_ms->add(0.20);

  _tenuring_threshold = MaxTenuringThreshold;

  assert(GCTimeRatio > 0,

         "we should have set it to a default value set_g1_gc_flags() "

         "if a user set it to 0");

  _gc_overhead_perc = 100.0 * (1.0 / (1.0 + GCTimeRatio));

  uintx reserve_perc = G1ReservePercent;

  // Put an artificial ceiling on this so that it's not set to a silly value.

  if (reserve_perc > 50) {

    reserve_perc = 50;

    warning("G1ReservePercent is set to a value that is too large, "

            "it's been updated to " UINTX_FORMAT, reserve_perc);

  }

  _reserve_factor = (double) reserve_perc / 100.0;

  // This will be set when the heap is expanded

  // for the first time during initialization.

  _reserve_regions = 0;

  _collectionSetChooser = new CollectionSetChooser();

}

double G1CollectorPolicy::get_new_prediction(TruncatedSeq const* seq) const {

  return _predictor.get_new_prediction(seq);

}

void G1CollectorPolicy::initialize_alignments() {

  _space_alignment = HeapRegion::GrainBytes;

  size_t card_table_alignment = CardTableRS::ct_max_alignment_constraint();

  size_t page_size = UseLargePages ? os::large_page_size() : os::vm_page_size();

  _heap_alignment = MAX3(card_table_alignment, _space_alignment, page_size);

}

void G1CollectorPolicy::initialize_flags() {

  if (G1HeapRegionSize != HeapRegion::GrainBytes) {

    FLAG_SET_ERGO(size_t, G1HeapRegionSize, HeapRegion::GrainBytes);

  }

  if (SurvivorRatio < 1) {

    vm_exit_during_initialization("Invalid survivor ratio specified");

  }

  CollectorPolicy::initialize_flags();

  _young_gen_sizer = new G1YoungGenSizer(); // Must be after call to initialize_flags

}

void G1CollectorPolicy::post_heap_initialize() {

  uintx max_regions = G1CollectedHeap::heap()->max_regions();

  size_t max_young_size = (size_t)_young_gen_sizer->max_young_length(max_regions) * HeapRegion::GrainBytes;

  if (max_young_size != MaxNewSize) {

    FLAG_SET_ERGO(size_t, MaxNewSize, max_young_size);

  }

}

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

G1YoungGenSizer::G1YoungGenSizer() : _sizer_kind(SizerDefaults), _adaptive_size(true),

        _min_desired_young_length(0), _max_desired_young_length(0) {

  if (FLAG_IS_CMDLINE(NewRatio)) {

    if (FLAG_IS_CMDLINE(NewSize) || FLAG_IS_CMDLINE(MaxNewSize)) {

      warning("-XX:NewSize and -XX:MaxNewSize override -XX:NewRatio");

    } else {

      _sizer_kind = SizerNewRatio;

      _adaptive_size = false;

      return;

    }

  }

  if (NewSize > MaxNewSize) {

    if (FLAG_IS_CMDLINE(MaxNewSize)) {

      warning("NewSize (" SIZE_FORMAT "k) is greater than the MaxNewSize (" SIZE_FORMAT "k). "

              "A new max generation size of " SIZE_FORMAT "k will be used.",

              NewSize/K, MaxNewSize/K, NewSize/K);

    }

    MaxNewSize = NewSize;

  }

  if (FLAG_IS_CMDLINE(NewSize)) {

    _min_desired_young_length = MAX2((uint) (NewSize / HeapRegion::GrainBytes),

                                     1U);

    if (FLAG_IS_CMDLINE(MaxNewSize)) {

      _max_desired_young_length =

                             MAX2((uint) (MaxNewSize / HeapRegion::GrainBytes),

                                  1U);

      _sizer_kind = SizerMaxAndNewSize;

      _adaptive_size = _min_desired_young_length == _max_desired_young_length;

    } else {

      _sizer_kind = SizerNewSizeOnly;

    }

  } else if (FLAG_IS_CMDLINE(MaxNewSize)) {

    _max_desired_young_length =

                             MAX2((uint) (MaxNewSize / HeapRegion::GrainBytes),

                                  1U);

    _sizer_kind = SizerMaxNewSizeOnly;

  }

}

uint G1YoungGenSizer::calculate_default_min_length(uint new_number_of_heap_regions) {

  uint default_value = (new_number_of_heap_regions * G1NewSizePercent) / 100;

  return MAX2(1U, default_value);

}

uint G1YoungGenSizer::calculate_default_max_length(uint new_number_of_heap_regions) {

  uint default_value = (new_number_of_heap_regions * G1MaxNewSizePercent) / 100;

  return MAX2(1U, default_value);

}

void G1YoungGenSizer::recalculate_min_max_young_length(uint number_of_heap_regions, uint* min_young_length, uint* max_young_length) {

  assert(number_of_heap_regions > 0, "Heap must be initialized");

  switch (_sizer_kind) {

    case SizerDefaults:

      *min_young_length = calculate_default_min_length(number_of_heap_regions);

      *max_young_length = calculate_default_max_length(number_of_heap_regions);

      break;

    case SizerNewSizeOnly:

      *max_young_length = calculate_default_max_length(number_of_heap_regions);

      *max_young_length = MAX2(*min_young_length, *max_young_length);

      break;

    case SizerMaxNewSizeOnly:

      *min_young_length = calculate_default_min_length(number_of_heap_regions);

      *min_young_length = MIN2(*min_young_length, *max_young_length);

      break;

    case SizerMaxAndNewSize:

      // Do nothing. Values set on the command line, don't update them at runtime.

      break;

    case SizerNewRatio:

      *min_young_length = number_of_heap_regions / (NewRatio + 1);

      *max_young_length = *min_young_length;

      break;

    default:

      ShouldNotReachHere();

  }

  assert(*min_young_length <= *max_young_length, "Invalid min/max young gen size values");

}

uint G1YoungGenSizer::max_young_length(uint number_of_heap_regions) {

  // We need to pass the desired values because recalculation may not update these

  // values in some cases.

  uint temp = _min_desired_young_length;

  uint result = _max_desired_young_length;

  recalculate_min_max_young_length(number_of_heap_regions, &temp, &result);

  return result;

}

void G1YoungGenSizer::heap_size_changed(uint new_number_of_heap_regions) {

  recalculate_min_max_young_length(new_number_of_heap_regions, &_min_desired_young_length,

          &_max_desired_young_length);

}

void G1CollectorPolicy::init() {

  // Set aside an initial future to_space.

  _g1 = G1CollectedHeap::heap();

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

  initialize_gc_policy_counters();

  if (adaptive_young_list_length()) {

    _young_list_fixed_length = 0;

  } else {

    _young_list_fixed_length = _young_gen_sizer->min_desired_young_length();

  }

  _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

  start_incremental_cset_building();

}

// Create the jstat counters for the policy.

void G1CollectorPolicy::initialize_gc_policy_counters() {

  _gc_policy_counters = new GCPolicyCounters("GarbageFirst", 1, 3);

}

bool G1CollectorPolicy::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 = predict_object_copy_time_ms(bytes_to_copy);

  double young_other_time_ms = 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;

  if ((2.0 /* magic */ * _predictor.sigma()) * bytes_to_copy > free_bytes) {

    // end condition 3: out-of-space (conservatively!)

    return false;

  }

  // success!

  return true;

}

void G1CollectorPolicy::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);

}

uint G1CollectorPolicy::calculate_young_list_desired_min_length(

                                                       uint base_min_length) const {

  uint desired_min_length = 0;

  if (adaptive_young_list_length()) {

    if (_alloc_rate_ms_seq->num() > 3) {

      double now_sec = os::elapsedTime();

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

      double alloc_rate_ms = predict_alloc_rate_ms();

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