/*

 * 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/_concurrentMarkSweepGeneration.cpp.incl"

// statics

CMSCollector* ConcurrentMarkSweepGeneration::_collector = NULL;

bool          CMSCollector::_full_gc_requested          = false;

//////////////////////////////////////////////////////////////////

// In support of CMS/VM thread synchronization

//////////////////////////////////////////////////////////////////

// We split use of the CGC_lock into 2 "levels".

// The low-level locking is of the usual CGC_lock monitor. We introduce

// a higher level "token" (hereafter "CMS token") built on top of the

// low level monitor (hereafter "CGC lock").

// The token-passing protocol gives priority to the VM thread. The

// CMS-lock doesn't provide any fairness guarantees, but clients

// should ensure that it is only held for very short, bounded

// durations.

//

// When either of the CMS thread or the VM thread is involved in

// collection operations during which it does not want the other

// thread to interfere, it obtains the CMS token.

//

// If either thread tries to get the token while the other has

// it, that thread waits. However, if the VM thread and CMS thread

// both want the token, then the VM thread gets priority while the

// CMS thread waits. This ensures, for instance, that the "concurrent"

// phases of the CMS thread's work do not block out the VM thread

// for long periods of time as the CMS thread continues to hog

// the token. (See bug 4616232).

//

// The baton-passing functions are, however, controlled by the

// flags _foregroundGCShouldWait and _foregroundGCIsActive,

// and here the low-level CMS lock, not the high level token,

// ensures mutual exclusion.

//

// Two important conditions that we have to satisfy:

// 1. if a thread does a low-level wait on the CMS lock, then it

//    relinquishes the CMS token if it were holding that token

//    when it acquired the low-level CMS lock.

// 2. any low-level notifications on the low-level lock

//    should only be sent when a thread has relinquished the token.

//

// In the absence of either property, we'd have potential deadlock.

//

// We protect each of the CMS (concurrent and sequential) phases

// with the CMS _token_, not the CMS _lock_.

//

// The only code protected by CMS lock is the token acquisition code

// itself, see ConcurrentMarkSweepThread::[de]synchronize(), and the

// baton-passing code.

//

// Unfortunately, i couldn't come up with a good abstraction to factor and

// hide the naked CGC_lock manipulation in the baton-passing code

// further below. That's something we should try to do. Also, the proof

// of correctness of this 2-level locking scheme is far from obvious,

// and potentially quite slippery. We have an uneasy supsicion, for instance,

// that there may be a theoretical possibility of delay/starvation in the

// low-level lock/wait/notify scheme used for the baton-passing because of

// potential intereference with the priority scheme embodied in the

// CMS-token-passing protocol. See related comments at a CGC_lock->wait()

// invocation further below and marked with "XXX 20011219YSR".

// Indeed, as we note elsewhere, this may become yet more slippery

// in the presence of multiple CMS and/or multiple VM threads. XXX

class CMSTokenSync: public StackObj {

 private:

  bool _is_cms_thread;

 public:

  CMSTokenSync(bool is_cms_thread):

    _is_cms_thread(is_cms_thread) {

    assert(is_cms_thread == Thread::current()->is_ConcurrentGC_thread(),

           "Incorrect argument to constructor");

    ConcurrentMarkSweepThread::synchronize(_is_cms_thread);

  }

  ~CMSTokenSync() {

    assert(_is_cms_thread ?

             ConcurrentMarkSweepThread::cms_thread_has_cms_token() :

             ConcurrentMarkSweepThread::vm_thread_has_cms_token(),

          "Incorrect state");

    ConcurrentMarkSweepThread::desynchronize(_is_cms_thread);

  }

};

// Convenience class that does a CMSTokenSync, and then acquires

// upto three locks.

class CMSTokenSyncWithLocks: public CMSTokenSync {

 private:

  // Note: locks are acquired in textual declaration order

  // and released in the opposite order

  MutexLockerEx _locker1, _locker2, _locker3;

 public:

  CMSTokenSyncWithLocks(bool is_cms_thread, Mutex* mutex1,

                        Mutex* mutex2 = NULL, Mutex* mutex3 = NULL):

    CMSTokenSync(is_cms_thread),

    _locker1(mutex1, Mutex::_no_safepoint_check_flag),

    _locker2(mutex2, Mutex::_no_safepoint_check_flag),

    _locker3(mutex3, Mutex::_no_safepoint_check_flag)

  { }

};

// Wrapper class to temporarily disable icms during a foreground cms collection.

class ICMSDisabler: public StackObj {

 public:

  // The ctor disables icms and wakes up the thread so it notices the change;

  // the dtor re-enables icms.  Note that the CMSCollector methods will check

  // CMSIncrementalMode.

  ICMSDisabler()  { CMSCollector::disable_icms(); CMSCollector::start_icms(); }

  ~ICMSDisabler() { CMSCollector::enable_icms(); }

};

//////////////////////////////////////////////////////////////////

//  Concurrent Mark-Sweep Generation /////////////////////////////

//////////////////////////////////////////////////////////////////

NOT_PRODUCT(CompactibleFreeListSpace* debug_cms_space;)

// This struct contains per-thread things necessary to support parallel

// young-gen collection.

class CMSParGCThreadState: public CHeapObj {

 public:

  CFLS_LAB lab;

  PromotionInfo promo;

  // Constructor.

  CMSParGCThreadState(CompactibleFreeListSpace* cfls) : lab(cfls) {

    promo.setSpace(cfls);

  }

};

ConcurrentMarkSweepGeneration::ConcurrentMarkSweepGeneration(

     ReservedSpace rs, size_t initial_byte_size, int level,

     CardTableRS* ct, bool use_adaptive_freelists,

     FreeBlockDictionary::DictionaryChoice dictionaryChoice) :

  CardGeneration(rs, initial_byte_size, level, ct),

  _dilatation_factor(((double)MinChunkSize)/((double)(oopDesc::header_size()))),

  _debug_collection_type(Concurrent_collection_type)

{

  HeapWord* bottom = (HeapWord*) _virtual_space.low();

  HeapWord* end    = (HeapWord*) _virtual_space.high();

  _direct_allocated_words = 0;

  NOT_PRODUCT(

    _numObjectsPromoted = 0;

    _numWordsPromoted = 0;

    _numObjectsAllocated = 0;

    _numWordsAllocated = 0;

  )

  _cmsSpace = new CompactibleFreeListSpace(_bts, MemRegion(bottom, end),

                                           use_adaptive_freelists,

                                           dictionaryChoice);

  NOT_PRODUCT(debug_cms_space = _cmsSpace;)

  if (_cmsSpace == NULL) {

    vm_exit_during_initialization(

      "CompactibleFreeListSpace allocation failure");

  }

  _cmsSpace->_gen = this;

  _gc_stats = new CMSGCStats();

  // Verify the assumption that FreeChunk::_prev and OopDesc::_klass

  // offsets match. The ability to tell free chunks from objects

  // depends on this property.

  debug_only(

    FreeChunk* junk = NULL;

    assert(UseCompressedOops ||

           junk->prev_addr() == (void*)(oop(junk)->klass_addr()),

           "Offset of FreeChunk::_prev within FreeChunk must match"

           "  that of OopDesc::_klass within OopDesc");

  )

  if (ParallelGCThreads > 0) {

    typedef CMSParGCThreadState* CMSParGCThreadStatePtr;

    _par_gc_thread_states =

      NEW_C_HEAP_ARRAY(CMSParGCThreadStatePtr, ParallelGCThreads);

    if (_par_gc_thread_states == NULL) {

      vm_exit_during_initialization("Could not allocate par gc structs");

    }

    for (uint i = 0; i < ParallelGCThreads; i++) {

      _par_gc_thread_states[i] = new CMSParGCThreadState(cmsSpace());

      if (_par_gc_thread_states[i] == NULL) {

        vm_exit_during_initialization("Could not allocate par gc structs");

      }

    }

  } else {

    _par_gc_thread_states = NULL;

  }

  _incremental_collection_failed = false;

  // The "dilatation_factor" is the expansion that can occur on

  // account of the fact that the minimum object size in the CMS

  // generation may be larger than that in, say, a contiguous young

  //  generation.

  // Ideally, in the calculation below, we'd compute the dilatation

  // factor as: MinChunkSize/(promoting_gen's min object size)

  // Since we do not have such a general query interface for the

  // promoting generation, we'll instead just use the mimimum

  // object size (which today is a header's worth of space);

  // note that all arithmetic is in units of HeapWords.

  assert(MinChunkSize >= oopDesc::header_size(), "just checking");

  assert(_dilatation_factor >= 1.0, "from previous assert");

}

// The field "_initiating_occupancy" represents the occupancy percentage

// at which we trigger a new collection cycle.  Unless explicitly specified

// via CMSInitiating[Perm]OccupancyFraction (argument "io" below), it

// is calculated by:

//

//   Let "f" be MinHeapFreeRatio in

//

//    _intiating_occupancy = 100-f +

//                           f * (CMSTrigger[Perm]Ratio/100)

//   where CMSTrigger[Perm]Ratio is the argument "tr" below.

//

// That is, if we assume the heap is at its desired maximum occupancy at the

// end of a collection, we let CMSTrigger[Perm]Ratio of the (purported) free

// space be allocated before initiating a new collection cycle.

//

void ConcurrentMarkSweepGeneration::init_initiating_occupancy(intx io, intx tr) {

  assert(io <= 100 && tr >= 0 && tr <= 100, "Check the arguments");

  if (io >= 0) {

    _initiating_occupancy = (double)io / 100.0;

  } else {

    _initiating_occupancy = ((100 - MinHeapFreeRatio) +

                             (double)(tr * MinHeapFreeRatio) / 100.0)

                            / 100.0;

  }

}

void ConcurrentMarkSweepGeneration::ref_processor_init() {

  assert(collector() != NULL, "no collector");

  collector()->ref_processor_init();

}

void CMSCollector::ref_processor_init() {

  if (_ref_processor == NULL) {

    // Allocate and initialize a reference processor

    _ref_processor = ReferenceProcessor::create_ref_processor(

        _span,                               // span

        _cmsGen->refs_discovery_is_atomic(), // atomic_discovery

        _cmsGen->refs_discovery_is_mt(),     // mt_discovery

        &_is_alive_closure,

        ParallelGCThreads,

        ParallelRefProcEnabled);

    // Initialize the _ref_processor field of CMSGen

    _cmsGen->set_ref_processor(_ref_processor);

    // Allocate a dummy ref processor for perm gen.

    ReferenceProcessor* rp2 = new ReferenceProcessor();

    if (rp2 == NULL) {

      vm_exit_during_initialization("Could not allocate ReferenceProcessor object");

    }

    _permGen->set_ref_processor(rp2);

  }

}

CMSAdaptiveSizePolicy* CMSCollector::size_policy() {

  GenCollectedHeap* gch = GenCollectedHeap::heap();

  assert(gch->kind() == CollectedHeap::GenCollectedHeap,

    "Wrong type of heap");

  CMSAdaptiveSizePolicy* sp = (CMSAdaptiveSizePolicy*)

    gch->gen_policy()->size_policy();

  assert(sp->is_gc_cms_adaptive_size_policy(),

    "Wrong type of size policy");

  return sp;

}

CMSGCAdaptivePolicyCounters* CMSCollector::gc_adaptive_policy_counters() {

  CMSGCAdaptivePolicyCounters* results =

    (CMSGCAdaptivePolicyCounters*) collector_policy()->counters();

  assert(

    results->kind() == GCPolicyCounters::CMSGCAdaptivePolicyCountersKind,

    "Wrong gc policy counter kind");

  return results;

}

void ConcurrentMarkSweepGeneration::initialize_performance_counters() {

  const char* gen_name = "old";

  // Generation Counters - generation 1, 1 subspace

  _gen_counters = new GenerationCounters(gen_name, 1, 1, &_virtual_space);

  _space_counters = new GSpaceCounters(gen_name, 0,

                                       _virtual_space.reserved_size(),

                                       this, _gen_counters);

}

CMSStats::CMSStats(ConcurrentMarkSweepGeneration* cms_gen, unsigned int alpha):

  _cms_gen(cms_gen)

{

  assert(alpha <= 100, "bad value");

  _saved_alpha = alpha;

  // Initialize the alphas to the bootstrap value of 100.

  _gc0_alpha = _cms_alpha = 100;

  _cms_begin_time.update();

  _cms_end_time.update();

  _gc0_duration = 0.0;

  _gc0_period = 0.0;

  _gc0_promoted = 0;

  _cms_duration = 0.0;

  _cms_period = 0.0;

  _cms_allocated = 0;

  _cms_used_at_gc0_begin = 0;

  _cms_used_at_gc0_end = 0;

  _allow_duty_cycle_reduction = false;

  _valid_bits = 0;

  _icms_duty_cycle = CMSIncrementalDutyCycle;

}

// If promotion failure handling is on use

// the padded average size of the promotion for each

// young generation collection.

double CMSStats::time_until_cms_gen_full() const {

  size_t cms_free = _cms_gen->cmsSpace()->free();

  GenCollectedHeap* gch = GenCollectedHeap::heap();

  size_t expected_promotion = gch->get_gen(0)->capacity();

  if (HandlePromotionFailure) {

    expected_promotion = MIN2(

        (size_t) _cms_gen->gc_stats()->avg_promoted()->padded_average(),

        expected_promotion);

  }

  if (cms_free > expected_promotion) {

    // Start a cms collection if there isn't enough space to promote

    // for the next minor collection.  Use the padded average as

    // a safety factor.

    cms_free -= expected_promotion;

    // Adjust by the safety factor.

    double cms_free_dbl = (double)cms_free;

    cms_free_dbl = cms_free_dbl * (100.0 - CMSIncrementalSafetyFactor) / 100.0;

    if (PrintGCDetails && Verbose) {

      gclog_or_tty->print_cr("CMSStats::time_until_cms_gen_full: cms_free "

        SIZE_FORMAT " expected_promotion " SIZE_FORMAT,

        cms_free, expected_promotion);

      gclog_or_tty->print_cr("  cms_free_dbl %f cms_consumption_rate %f",

        cms_free_dbl, cms_consumption_rate() + 1.0);

    }

    // Add 1 in case the consumption rate goes to zero.

    return cms_free_dbl / (cms_consumption_rate() + 1.0);

  }

  return 0.0;

}

// Compare the duration of the cms collection to the

// time remaining before the cms generation is empty.

// Note that the time from the start of the cms collection

// to the start of the cms sweep (less than the total

// duration of the cms collection) can be used.  This

// has been tried and some applications experienced

// promotion failures early in execution.  This was

// possibly because the averages were not accurate

// enough at the beginning.

double CMSStats::time_until_cms_start() const {

  // We add "gc0_period" to the "work" calculation

  // below because this query is done (mostly) at the

  // end of a scavenge, so we need to conservatively

  // account for that much possible delay

  // in the query so as to avoid concurrent mode failures

  // due to starting the collection just a wee bit too

  // late.

  double work = cms_duration() + gc0_period();

  double deadline = time_until_cms_gen_full();

  if (work > deadline) {

    if (Verbose && PrintGCDetails) {

      gclog_or_tty->print(

        " CMSCollector: collect because of anticipated promotion "

        "before full %3.7f + %3.7f > %3.7f ", cms_duration(),

        gc0_period(), time_until_cms_gen_full());

    }

    return 0.0;

  }

  return work - deadline;

}

// Return a duty cycle based on old_duty_cycle and new_duty_cycle, limiting the

// amount of change to prevent wild oscillation.

unsigned int CMSStats::icms_damped_duty_cycle(unsigned int old_duty_cycle,

                                              unsigned int new_duty_cycle) {

  assert(old_duty_cycle <= 100, "bad input value");

  assert(new_duty_cycle <= 100, "bad input value");

  // Note:  use subtraction with caution since it may underflow (values are

  // unsigned).  Addition is safe since we're in the range 0-100.

  unsigned int damped_duty_cycle = new_duty_cycle;

  if (new_duty_cycle < old_duty_cycle) {

    const unsigned int largest_delta = MAX2(old_duty_cycle / 4, 5U);

    if (new_duty_cycle + largest_delta < old_duty_cycle) {

      damped_duty_cycle = old_duty_cycle - largest_delta;

    }

  } else if (new_duty_cycle > old_duty_cycle) {

    const unsigned int largest_delta = MAX2(old_duty_cycle / 4, 15U);

    if (new_duty_cycle > old_duty_cycle + largest_delta) {

      damped_duty_cycle = MIN2(old_duty_cycle + largest_delta, 100U);

    }

  }

  assert(damped_duty_cycle <= 100, "invalid duty cycle computed");

  if (CMSTraceIncrementalPacing) {

    gclog_or_tty->print(" [icms_damped_duty_cycle(%d,%d) = %d] ",

                           old_duty_cycle, new_duty_cycle, damped_duty_cycle);

  }

  return damped_duty_cycle;

}

unsigned int CMSStats::icms_update_duty_cycle_impl() {

  assert(CMSIncrementalPacing && valid(),

         "should be handled in icms_update_duty_cycle()");

  double cms_time_so_far = cms_timer().seconds();

  double scaled_duration = cms_duration_per_mb() * _cms_used_at_gc0_end / M;

  double scaled_duration_remaining = fabsd(scaled_duration - cms_time_so_far);

  // Avoid division by 0.

  double time_until_full = MAX2(time_until_cms_gen_full(), 0.01);

  double duty_cycle_dbl = 100.0 * scaled_duration_remaining / time_until_full;

  unsigned int new_duty_cycle = MIN2((unsigned int)duty_cycle_dbl, 100U);

  if (new_duty_cycle > _icms_duty_cycle) {

    // Avoid very small duty cycles (1 or 2); 0 is allowed.

    if (new_duty_cycle > 2) {

      _icms_duty_cycle = icms_damped_duty_cycle(_icms_duty_cycle,

                                                new_duty_cycle);

    }

  } else if (_allow_duty_cycle_reduction) {

    // The duty cycle is reduced only once per cms cycle (see record_cms_end()).

    new_duty_cycle = icms_damped_duty_cycle(_icms_duty_cycle, new_duty_cycle);

    // Respect the minimum duty cycle.

    unsigned int min_duty_cycle = (unsigned int)CMSIncrementalDutyCycleMin;

    _icms_duty_cycle = MAX2(new_duty_cycle, min_duty_cycle);

  }

  if (PrintGCDetails || CMSTraceIncrementalPacing) {

    gclog_or_tty->print(" icms_dc=%d ", _icms_duty_cycle);

  }

  _allow_duty_cycle_reduction = false;

  return _icms_duty_cycle;

}

#ifndef PRODUCT

void CMSStats::print_on(outputStream *st) const {

  st->print(" gc0_alpha=%d,cms_alpha=%d", _gc0_alpha, _cms_alpha);

  st->print(",gc0_dur=%g,gc0_per=%g,gc0_promo=" SIZE_FORMAT,

               gc0_duration(), gc0_period(), gc0_promoted());

  st->print(",cms_dur=%g,cms_dur_per_mb=%g,cms_per=%g,cms_alloc=" SIZE_FORMAT,

            cms_duration(), cms_duration_per_mb(),

            cms_period(), cms_allocated());

  st->print(",cms_since_beg=%g,cms_since_end=%g",

            cms_time_since_begin(), cms_time_since_end());

  st->print(",cms_used_beg=" SIZE_FORMAT ",cms_used_end=" SIZE_FORMAT,

            _cms_used_at_gc0_begin, _cms_used_at_gc0_end);

  if (CMSIncrementalMode) {

    st->print(",dc=%d", icms_duty_cycle());

  }

  if (valid()) {

    st->print(",promo_rate=%g,cms_alloc_rate=%g",

              promotion_rate(), cms_allocation_rate());

    st->print(",cms_consumption_rate=%g,time_until_full=%g",

              cms_consumption_rate(), time_until_cms_gen_full());

  }

  st->print(" ");

}

#endif // #ifndef PRODUCT

CMSCollector::CollectorState CMSCollector::_collectorState =

                             CMSCollector::Idling;

bool CMSCollector::_foregroundGCIsActive = false;

bool CMSCollector::_foregroundGCShouldWait = false;

CMSCollector::CMSCollector(ConcurrentMarkSweepGeneration* cmsGen,

                           ConcurrentMarkSweepGeneration* permGen,

                           CardTableRS*                   ct,

                           ConcurrentMarkSweepPolicy*     cp):

  _cmsGen(cmsGen),

  _permGen(permGen),

  _ct(ct),

  _ref_processor(NULL),    // will be set later

  _conc_workers(NULL),     // may be set later

  _abort_preclean(false),

  _start_sampling(false),

  _between_prologue_and_epilogue(false),

  _markBitMap(0, Mutex::leaf + 1, "CMS_markBitMap_lock"),

  _perm_gen_verify_bit_map(0, -1 /* no mutex */, "No_lock"),

  _modUnionTable((CardTableModRefBS::card_shift - LogHeapWordSize),

                 -1 /* lock-free */, "No_lock" /* dummy */),

  _modUnionClosure(&_modUnionTable),

  _modUnionClosurePar(&_modUnionTable),

  // Adjust my span to cover old (cms) gen and perm gen

  _span(cmsGen->reserved()._union(permGen->reserved())),

  // Construct the is_alive_closure with _span & markBitMap