/*

 * Copyright 2001-2008 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_g1CollectorPolicy.cpp.incl"

#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

};

static double cost_per_scan_only_region_ms_defaults[] = {

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

};

// 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((ParallelGCThreads > 0) ? 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()),

  _non_pop_summary(new NonPopSummary()),

  _pop_summary(new PopSummary()),

  _non_pop_abandoned_summary(new NonPopAbandonedSummary()),

  _pop_abandoned_summary(new PopAbandonedSummary()),

  _cur_clear_ct_time_ms(0.0),

  _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]),

  _pop_compute_rc_start(0.0),

  _pop_evac_start(0.0),

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

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

  _cost_per_scan_only_region_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) G1MaxPauseTimeMS),

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

  _target_pause_time_ms(-1.0),

   _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()),

  _conc_refine_enabled(0),

  _conc_refine_zero_traversals(0),

  _conc_refine_max_traversals(0),

  _conc_refine_current_delta(G1ConcRefineInitialDelta),

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

  _conc_mark_initiated(false),

  _should_initiate_conc_mark(false),

  _should_revert_to_full_young_gcs(false),

  _last_full_young_gc(false),

  _prev_collection_pause_used_at_end_bytes(0),

  _collection_set(NULL),

#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

{

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

  _prev_collection_pause_end_ms = os::elapsedTime() * 1000.0;

  _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_scan_only_times_ms = new double[_parallel_gc_threads];

  _par_last_scan_only_regions_scanned = new double[_parallel_gc_threads];

  _par_last_update_rs_start_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_start_times_ms = new double[_parallel_gc_threads];

  _par_last_scan_rs_times_ms = new double[_parallel_gc_threads];

  _par_last_scan_new_refs_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];

  // we store the data from the first pass during popularity pauses

  _pop_par_last_update_rs_start_times_ms = new double[_parallel_gc_threads];

  _pop_par_last_update_rs_times_ms = new double[_parallel_gc_threads];

  _pop_par_last_update_rs_processed_buffers = new double[_parallel_gc_threads];

  _pop_par_last_scan_rs_start_times_ms = new double[_parallel_gc_threads];

  _pop_par_last_scan_rs_times_ms = new double[_parallel_gc_threads];

  _pop_par_last_closure_app_times_ms = new double[_parallel_gc_threads];

  // start conservatively

  _expensive_region_limit_ms = 0.5 * (double) G1MaxPauseTimeMS;

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

  _cost_per_scan_only_region_ms_seq->add(

                                 cost_per_scan_only_region_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>

  double time_slice  = (double) G1TimeSliceMS / 1000.0;

  double max_gc_time = (double) G1MaxPauseTimeMS / 1000.0;

  guarantee(max_gc_time < time_slice,

            "Max GC time should not be greater than the time slice");

  _mmu_tracker = new G1MMUTrackerQueue(time_slice, max_gc_time);

  _sigma = (double) G1ConfidencePerc / 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;

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

  CollectorPolicy::initialize_flags();

}

void G1CollectorPolicy::init() {

  // Set aside an initial future to_space.

  _g1 = G1CollectedHeap::heap();

  size_t regions = Universe::heap()->capacity() / HeapRegion::GrainBytes;

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

  if (G1SteadyStateUsed < 50) {

    vm_exit_during_initialization("G1SteadyStateUsed must be at least 50%.");

  }

  if (UseConcMarkSweepGC) {

    vm_exit_during_initialization("-XX:+UseG1GC is incompatible with "

                                  "-XX:+UseConcMarkSweepGC.");

  }

  if (G1Gen) {

    _in_young_gc_mode = true;

    if (G1YoungGenSize == 0) {

      set_adaptive_young_list_length(true);

      _young_list_fixed_length = 0;

    } else {

      set_adaptive_young_list_length(false);

      _young_list_fixed_length = (G1YoungGenSize / HeapRegion::GrainBytes);

    }

     _free_regions_at_end_of_collection = _g1->free_regions();

     _scan_only_regions_at_end_of_collection = 0;

     calculate_young_list_min_length();

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

     calculate_young_list_target_config();

   } else {

     _young_list_fixed_length = 0;

    _in_young_gc_mode = false;

  }

}

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

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

    int current_region_num = (int) _g1->young_list_length();

    _young_list_min_length = min_regions + current_region_num;

  }

}

void G1CollectorPolicy::calculate_young_list_target_config() {

  if (adaptive_young_list_length()) {

    size_t rs_lengths = (size_t) get_new_prediction(_rs_lengths_seq);

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

    _young_list_target_length = MAX2(_young_list_target_length, (size_t)1);

    size_t so_length = calculate_optimal_so_length(_young_list_target_length);

    guarantee( so_length < _young_list_target_length, "invariant" );

    _young_list_so_prefix_length = so_length;

  }

}

// This method calculate the optimal scan-only set for a fixed young

// gen size. I couldn't work out how to reuse the more elaborate one,

// i.e. calculate_young_list_target_config(rs_length), as the loops are

// fundamentally different (the other one finds a config for different

// S-O lengths, whereas here we need to do the opposite).

size_t G1CollectorPolicy::calculate_optimal_so_length(

                                                    size_t young_list_length) {

  if (!G1UseScanOnlyPrefix)

    return 0;

  if (_all_pause_times_ms->num() < 3) {

    // we won't use a scan-only set at the beginning to allow the rest

    // of the predictors to warm up

    return 0;

  }

  if (_cost_per_scan_only_region_ms_seq->num() < 3) {

    // then, we'll only set the S-O set to 1 for a little bit of time,

    // to get enough information on the scanning cost

    return 1;

  }

  size_t pending_cards = (size_t) get_new_prediction(_pending_cards_seq);

  size_t rs_lengths = (size_t) get_new_prediction(_rs_lengths_seq);

  size_t adj_rs_lengths = rs_lengths + predict_rs_length_diff();

  size_t scanned_cards;

  if (full_young_gcs())

    scanned_cards = predict_young_card_num(adj_rs_lengths);

  else

    scanned_cards = predict_non_young_card_num(adj_rs_lengths);

  double base_time_ms = predict_base_elapsed_time_ms(pending_cards,

                                                     scanned_cards);

  size_t so_length = 0;

  double max_gc_eff = 0.0;

  for (size_t i = 0; i < young_list_length; ++i) {

    double gc_eff = 0.0;

    double pause_time_ms = 0.0;

    predict_gc_eff(young_list_length, i, base_time_ms,

                   &gc_eff, &pause_time_ms);

    if (gc_eff > max_gc_eff) {

      max_gc_eff = gc_eff;

      so_length = i;

    }

  }

  // set it to 95% of the optimal to make sure we sample the "area"

  // around the optimal length to get up-to-date survival rate data

  return so_length * 950 / 1000;

}

// This is a really cool piece of code! It finds the best

// target configuration (young length / scan-only prefix length) so

// that GC efficiency is maximized and that we also meet a pause

// time. It's a triple nested loop. These loops are explained below

// from the inside-out :-)

//

// (a) The innermost loop will try to find the optimal young length

// for a fixed S-O length. It uses a binary search to speed up the

// process. We assume that, for a fixed S-O length, as we add more

// young regions to the CSet, the GC efficiency will only go up (I'll

// skip the proof). So, using a binary search to optimize this process

// makes perfect sense.

//

// (b) The middle loop will fix the S-O length before calling the

// innermost one. It will vary it between two parameters, increasing

// it by a given increment.

//

// (c) The outermost loop will call the middle loop three times.

//   (1) The first time it will explore all possible S-O length values

//   from 0 to as large as it can get, using a coarse increment (to

//   quickly "home in" to where the optimal seems to be).

//   (2) The second time it will explore the values around the optimal

//   that was found by the first iteration using a fine increment.

//   (3) Once the optimal config has been determined by the second

//   iteration, we'll redo the calculation, but setting the S-O length

//   to 95% of the optimal to make sure we sample the "area"

//   around the optimal length to get up-to-date survival rate data

//

// Termination conditions for the iterations are several: the pause

// time is over the limit, we do not have enough to-space, etc.

void G1CollectorPolicy::calculate_young_list_target_config(size_t rs_lengths) {

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

  double start_time_sec = os::elapsedTime();

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

  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

    size_t min_so_length = 0;

    size_t max_so_length = 0;

    if (G1UseScanOnlyPrefix) {

      if (_all_pause_times_ms->num() < 3) {

        // we won't use a scan-only set at the beginning to allow the rest

        // of the predictors to warm up

        min_so_length = 0;

        max_so_length = 0;

      } else if (_cost_per_scan_only_region_ms_seq->num() < 3) {

        // then, we'll only set the S-O set to 1 for a little bit of time,

        // to get enough information on the scanning cost

        min_so_length = 1;

        max_so_length = 1;

      } else if (_in_marking_window || _last_full_young_gc) {

        // no S-O prefix during a marking phase either, as at the end

        // of the marking phase we'll have to use a very small young

        // length target to fill up the rest of the CSet with

        // non-young regions and, if we have lots of scan-only regions

        // left-over, we will not be able to add any more non-young

        // regions.

        min_so_length = 0;

        max_so_length = 0;

      } else {

        // this is the common case; we'll never reach the maximum, we

        // one of the end conditions will fire well before that

        // (hopefully!)

        min_so_length = 0;

        max_so_length = _free_regions_at_end_of_collection - 1;

      }

    } else {

      // no S-O prefix, as the switch is not set, but we still need to

      // do one iteration to calculate the best young target that

      // meets the pause time; this way we reuse the same code instead

      // of replicating it

      min_so_length = 0;

      max_so_length = 0;

    }

    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;

    if (full_young_gcs())

      scanned_cards = predict_young_card_num(adj_rs_lengths);

    else

      scanned_cards = predict_non_young_card_num(adj_rs_lengths);

    // calculate this once, so that we don't have to recalculate it in

    // the innermost loop

    double base_time_ms = predict_base_elapsed_time_ms(pending_cards,

                                                       scanned_cards);

    // the result

    size_t final_young_length = 0;

    size_t final_so_length = 0;

    double final_gc_eff = 0.0;

    // we'll also keep track of how many times we go into the inner loop

    // this is for profiling reasons

    size_t calculations = 0;

    // this determines which of the three iterations the outer loop is in

    typedef enum {

      pass_type_coarse,

      pass_type_fine,

      pass_type_final

    } pass_type_t;

    // range of the outer loop's iteration

    size_t from_so_length   = min_so_length;

    size_t to_so_length     = max_so_length;

    guarantee( from_so_length <= to_so_length, "invariant" );

    // this will keep the S-O length that's found by the second

    // iteration of the outer loop; we'll keep it just in case the third

    // iteration fails to find something

    size_t fine_so_length   = 0;

    // the increment step for the coarse (first) iteration