/*

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

#include "gc_implementation/g1/concurrentMark.hpp"

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

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

#include "gc_implementation/g1/g1CollectorPolicy.hpp"

#include "gc_implementation/g1/heapRegionRemSet.hpp"

#include "gc_implementation/shared/gcPolicyCounters.hpp"

#include "runtime/arguments.hpp"

#include "runtime/java.hpp"

#include "runtime/mutexLocker.hpp"

#include "utilities/debug.hpp"

#define PREDICTIONS_VERBOSE 0

// <NEW PREDICTION>

// 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 fully_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

};

// </NEW PREDICTION>

G1CollectorPolicy::G1CollectorPolicy() :

  _parallel_gc_threads(G1CollectedHeap::use_parallel_gc_threads()

    ? ParallelGCThreads : 1),

  _n_pauses(0),

  _recent_CH_strong_roots_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_G1_strong_roots_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_evac_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_pause_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_rs_sizes(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_gc_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _all_pause_times_ms(new NumberSeq()),

  _stop_world_start(0.0),

  _all_stop_world_times_ms(new NumberSeq()),

  _all_yield_times_ms(new NumberSeq()),

  _all_mod_union_times_ms(new NumberSeq()),

  _summary(new Summary()),

#ifndef PRODUCT

  _cur_clear_ct_time_ms(0.0),

  _min_clear_cc_time_ms(-1.0),

  _max_clear_cc_time_ms(-1.0),

  _cur_clear_cc_time_ms(0.0),

  _cum_clear_cc_time_ms(0.0),

  _num_cc_clears(0L),

#endif

  _region_num_young(0),

  _region_num_tenured(0),

  _prev_region_num_young(0),

  _prev_region_num_tenured(0),

  _aux_num(10),

  _all_aux_times_ms(new NumberSeq[_aux_num]),

  _cur_aux_start_times_ms(new double[_aux_num]),

  _cur_aux_times_ms(new double[_aux_num]),

  _cur_aux_times_set(new bool[_aux_num]),

  _concurrent_mark_init_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _concurrent_mark_remark_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _concurrent_mark_cleanup_times_ms(new TruncatedSeq(NumPrevPausesForHeuristics)),

  // <NEW PREDICTION>

  _alloc_rate_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _prev_collection_pause_end_ms(0.0),

  _pending_card_diff_seq(new TruncatedSeq(TruncatedSeqLength)),

  _rs_length_diff_seq(new TruncatedSeq(TruncatedSeqLength)),

  _cost_per_card_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _fully_young_cards_per_entry_ratio_seq(new TruncatedSeq(TruncatedSeqLength)),

  _partially_young_cards_per_entry_ratio_seq(

                                         new TruncatedSeq(TruncatedSeqLength)),

  _cost_per_entry_ms_seq(new TruncatedSeq(TruncatedSeqLength)),

  _partially_young_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)),

  _scanned_cards_seq(new TruncatedSeq(TruncatedSeqLength)),

  _rs_lengths_seq(new TruncatedSeq(TruncatedSeqLength)),

  _pause_time_target_ms((double) MaxGCPauseMillis),

  // </NEW PREDICTION>

  _in_young_gc_mode(false),

  _full_young_gcs(true),

  _full_young_pause_num(0),

  _partial_young_pause_num(0),

  _during_marking(false),

  _in_marking_window(false),

  _in_marking_window_im(false),

  _known_garbage_ratio(0.0),

  _known_garbage_bytes(0),

  _young_gc_eff_seq(new TruncatedSeq(TruncatedSeqLength)),

   _recent_prev_end_times_for_all_gcs_sec(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_CS_bytes_used_before(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_CS_bytes_surviving(new TruncatedSeq(NumPrevPausesForHeuristics)),

  _recent_avg_pause_time_ratio(0.0),

  _num_markings(0),

  _n_marks(0),

  _n_pauses_at_mark_end(0),

  _all_full_gc_times_ms(new NumberSeq()),

  // G1PausesBtwnConcMark defaults to -1

  // so the hack is to do the cast  QQQ FIXME

  _pauses_btwn_concurrent_mark((size_t)G1PausesBtwnConcMark),

  _n_marks_since_last_pause(0),

  _initiate_conc_mark_if_possible(false),

  _during_initial_mark_pause(false),

  _should_revert_to_full_young_gcs(false),

  _last_full_young_gc(false),

  _prev_collection_pause_used_at_end_bytes(0),

  _collection_set(NULL),

  _collection_set_size(0),

  _collection_set_bytes_used_before(0),

  // Incremental CSet attributes

  _inc_cset_build_state(Inactive),

  _inc_cset_head(NULL),

  _inc_cset_tail(NULL),

  _inc_cset_size(0),

  _inc_cset_young_index(0),

  _inc_cset_bytes_used_before(0),

  _inc_cset_max_finger(NULL),

  _inc_cset_recorded_young_bytes(0),

  _inc_cset_recorded_rs_lengths(0),

  _inc_cset_predicted_elapsed_time_ms(0.0),

  _inc_cset_predicted_bytes_to_copy(0),

#ifdef _MSC_VER // the use of 'this' below gets a warning, make it go away

#pragma warning( disable:4355 ) // 'this' : used in base member initializer list

#endif // _MSC_VER

  _short_lived_surv_rate_group(new SurvRateGroup(this, "Short Lived",

                                                 G1YoungSurvRateNumRegionsSummary)),

  _survivor_surv_rate_group(new SurvRateGroup(this, "Survivor",

                                              G1YoungSurvRateNumRegionsSummary)),

  // 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)

{

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

  HeapRegion::setup_heap_region_size(Arguments::min_heap_size());

  HeapRegionRemSet::setup_remset_size();

  // Verify PLAB sizes

  const uint region_size = HeapRegion::GrainWords;

  if (YoungPLABSize > region_size || OldPLABSize > region_size) {

    char buffer[128];

    jio_snprintf(buffer, sizeof(buffer), "%sPLABSize should be at most %u",

                 OldPLABSize > region_size ? "Old" : "Young", region_size);

    vm_exit_during_initialization(buffer);

  }

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

  _prev_collection_pause_end_ms = os::elapsedTime() * 1000.0;

  _par_last_gc_worker_start_times_ms = new double[_parallel_gc_threads];

  _par_last_ext_root_scan_times_ms = new double[_parallel_gc_threads];

  _par_last_mark_stack_scan_times_ms = new double[_parallel_gc_threads];

  _par_last_update_rs_times_ms = new double[_parallel_gc_threads];

  _par_last_update_rs_processed_buffers = new double[_parallel_gc_threads];

  _par_last_scan_rs_times_ms = new double[_parallel_gc_threads];

  _par_last_obj_copy_times_ms = new double[_parallel_gc_threads];

  _par_last_termination_times_ms = new double[_parallel_gc_threads];

  _par_last_termination_attempts = new double[_parallel_gc_threads];

  _par_last_gc_worker_end_times_ms = new double[_parallel_gc_threads];

  // start conservatively

  _expensive_region_limit_ms = 0.5 * (double) MaxGCPauseMillis;

  // <NEW PREDICTION>

  int index;

  if (ParallelGCThreads == 0)

    index = 0;

  else if (ParallelGCThreads > 8)

    index = 7;

  else

    index = ParallelGCThreads - 1;

  _pending_card_diff_seq->add(0.0);

  _rs_length_diff_seq->add(rs_length_diff_defaults[index]);

  _cost_per_card_ms_seq->add(cost_per_card_ms_defaults[index]);

  _fully_young_cards_per_entry_ratio_seq->add(

                            fully_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]);

  // </NEW PREDICTION>

  // 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);

  _sigma = (double) G1ConfidencePercent / 100.0;

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

  _concurrent_mark_init_times_ms->add(0.05);

  _concurrent_mark_remark_times_ms->add(0.05);

  _concurrent_mark_cleanup_times_ms->add(0.20);

  _tenuring_threshold = MaxTenuringThreshold;

  // if G1FixedSurvivorSpaceSize is 0 which means the size is not

  // fixed, then _max_survivor_regions will be calculated at

  // calculate_young_list_target_length during initialization

  _max_survivor_regions = G1FixedSurvivorSpaceSize / HeapRegion::GrainBytes;

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

  initialize_all();

}

// Increment "i", mod "len"

static void inc_mod(int& i, int len) {

  i++; if (i == len) i = 0;

}

void G1CollectorPolicy::initialize_flags() {

  set_min_alignment(HeapRegion::GrainBytes);

  set_max_alignment(GenRemSet::max_alignment_constraint(rem_set_name()));

  if (SurvivorRatio < 1) {

    vm_exit_during_initialization("Invalid survivor ratio specified");

  }

  CollectorPolicy::initialize_flags();

}

// The easiest way to deal with the parsing of the NewSize /

// MaxNewSize / etc. parameteres is to re-use the code in the

// TwoGenerationCollectorPolicy class. This is similar to what

// ParallelScavenge does with its GenerationSizer class (see

// ParallelScavengeHeap::initialize()). We might change this in the

// future, but it's a good start.

class G1YoungGenSizer : public TwoGenerationCollectorPolicy {

  size_t size_to_region_num(size_t byte_size) {

    return MAX2((size_t) 1, byte_size / HeapRegion::GrainBytes);

  }

public:

  G1YoungGenSizer() {

    initialize_flags();

    initialize_size_info();

  }

  size_t min_young_region_num() {

    return size_to_region_num(_min_gen0_size);

  }

  size_t initial_young_region_num() {

    return size_to_region_num(_initial_gen0_size);

  }

  size_t max_young_region_num() {

    return size_to_region_num(_max_gen0_size);

  }

};

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 (G1Gen) {

    _in_young_gc_mode = true;

    G1YoungGenSizer sizer;

    size_t initial_region_num = sizer.initial_young_region_num();

    if (UseAdaptiveSizePolicy) {

      set_adaptive_young_list_length(true);

      _young_list_fixed_length = 0;

    } else {

      set_adaptive_young_list_length(false);

      _young_list_fixed_length = initial_region_num;

    }

    _free_regions_at_end_of_collection = _g1->free_regions();

    calculate_young_list_min_length();

    guarantee( _young_list_min_length == 0, "invariant, not enough info" );

    calculate_young_list_target_length();

  } else {

     _young_list_fixed_length = 0;

    _in_young_gc_mode = false;

  }

  // 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, 2 + G1Gen);

}

void G1CollectorPolicy::calculate_young_list_min_length() {

  _young_list_min_length = 0;

  if (!adaptive_young_list_length())

    return;

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

    size_t min_regions = (size_t) ceil(alloc_rate_ms * when_ms);

    size_t current_region_num = _g1->young_list()->length();

    _young_list_min_length = min_regions + current_region_num;

  }

}

void G1CollectorPolicy::calculate_young_list_target_length() {

  if (adaptive_young_list_length()) {

    size_t rs_lengths = (size_t) get_new_prediction(_rs_lengths_seq);

    calculate_young_list_target_length(rs_lengths);

  } else {

    if (full_young_gcs())

      _young_list_target_length = _young_list_fixed_length;

    else

      _young_list_target_length = _young_list_fixed_length / 2;

  }

  // Make sure we allow the application to allocate at least one

  // region before we need to do a collection again.

  size_t min_length = _g1->young_list()->length() + 1;

  _young_list_target_length = MAX2(_young_list_target_length, min_length);

  calculate_max_gc_locker_expansion();

  calculate_survivors_policy();

}

void G1CollectorPolicy::calculate_young_list_target_length(size_t rs_lengths) {

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

  guarantee( !_in_marking_window || !_last_full_young_gc, "invariant" );

  double start_time_sec = os::elapsedTime();

  size_t min_reserve_perc = MAX2((size_t)2, (size_t)G1ReservePercent);

  min_reserve_perc = MIN2((size_t) 50, min_reserve_perc);

  size_t reserve_regions =

    (size_t) ((double) min_reserve_perc * (double) _g1->n_regions() / 100.0);

  if (full_young_gcs() && _free_regions_at_end_of_collection > 0) {

    // we are in fully-young mode and there are free regions in the heap

    double survivor_regions_evac_time =

        predict_survivor_regions_evac_time();

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

    size_t pending_cards = (size_t) get_new_prediction(_pending_cards_seq);

    size_t adj_rs_lengths = rs_lengths + predict_rs_length_diff();

    size_t scanned_cards = predict_young_card_num(adj_rs_lengths);

    double base_time_ms = predict_base_elapsed_time_ms(pending_cards, scanned_cards)

                          + survivor_regions_evac_time;