/*

 * Copyright (c) 2001, 2017, 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 "classfile/classLoaderData.hpp"

#include "classfile/stringTable.hpp"

#include "classfile/symbolTable.hpp"

#include "classfile/systemDictionary.hpp"

#include "code/codeCache.hpp"

#include "gc/cms/cmsCollectorPolicy.hpp"

#include "gc/cms/cmsOopClosures.inline.hpp"

#include "gc/cms/compactibleFreeListSpace.hpp"

#include "gc/cms/concurrentMarkSweepGeneration.inline.hpp"

#include "gc/cms/concurrentMarkSweepThread.hpp"

#include "gc/cms/parNewGeneration.hpp"

#include "gc/cms/vmCMSOperations.hpp"

#include "gc/serial/genMarkSweep.hpp"

#include "gc/serial/tenuredGeneration.hpp"

#include "gc/shared/adaptiveSizePolicy.hpp"

#include "gc/shared/cardGeneration.inline.hpp"

#include "gc/shared/cardTableRS.hpp"

#include "gc/shared/collectedHeap.inline.hpp"

#include "gc/shared/collectorCounters.hpp"

#include "gc/shared/collectorPolicy.hpp"

#include "gc/shared/gcLocker.inline.hpp"

#include "gc/shared/gcPolicyCounters.hpp"

#include "gc/shared/gcTimer.hpp"

#include "gc/shared/gcTrace.hpp"

#include "gc/shared/gcTraceTime.inline.hpp"

#include "gc/shared/genCollectedHeap.hpp"

#include "gc/shared/genOopClosures.inline.hpp"

#include "gc/shared/isGCActiveMark.hpp"

#include "gc/shared/referencePolicy.hpp"

#include "gc/shared/strongRootsScope.hpp"

#include "gc/shared/taskqueue.inline.hpp"

#include "logging/log.hpp"

#include "memory/allocation.hpp"

#include "memory/iterator.inline.hpp"

#include "memory/padded.hpp"

#include "memory/resourceArea.hpp"

#include "oops/oop.inline.hpp"

#include "prims/jvmtiExport.hpp"

#include "runtime/atomic.hpp"

#include "runtime/globals_extension.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/java.hpp"

#include "runtime/orderAccess.inline.hpp"

#include "runtime/timer.hpp"

#include "runtime/vmThread.hpp"

#include "services/memoryService.hpp"

#include "services/runtimeService.hpp"

#include "utilities/stack.inline.hpp"

// statics

CMSCollector* ConcurrentMarkSweepGeneration::_collector = NULL;

bool CMSCollector::_full_gc_requested = false;

GCCause::Cause CMSCollector::_full_gc_cause = GCCause::_no_gc;

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

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

  { }

};

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

//  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<mtGC> {

 public:

  CompactibleFreeListSpaceLAB lab;

  PromotionInfo promo;

  // Constructor.

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

    promo.setSpace(cfls);

  }

};

ConcurrentMarkSweepGeneration::ConcurrentMarkSweepGeneration(

     ReservedSpace rs, size_t initial_byte_size, CardTableRS* ct) :

  CardGeneration(rs, initial_byte_size, ct),

  _dilatation_factor(((double)MinChunkSize)/((double)(CollectedHeap::min_fill_size()))),

  _did_compact(false)

{

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

  NOT_PRODUCT(debug_cms_space = _cmsSpace;)

  _cmsSpace->_old_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(UseCompressedClassPointers ||

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

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

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

  )

  _par_gc_thread_states = NEW_C_HEAP_ARRAY(CMSParGCThreadState*, ParallelGCThreads, mtGC);

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

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

  }

  _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 minimum

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

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

  assert(MinChunkSize >= CollectedHeap::min_fill_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 CMSInitiatingOccupancyFraction (argument "io" below), it

// is calculated by:

//

//   Let "f" be MinHeapFreeRatio in

//

//    _initiating_occupancy = 100-f +

//                           f * (CMSTriggerRatio/100)

//   where CMSTriggerRatio 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 CMSTriggerRatio of the (purported) free

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

//

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

  assert(io <= 100 && 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 =

      new ReferenceProcessor(_span,                               // span

                             (ParallelGCThreads > 1) && ParallelRefProcEnabled, // mt processing

                             ParallelGCThreads,                   // mt processing degree

                             _cmsGen->refs_discovery_is_mt(),     // mt discovery

                             MAX2(ConcGCThreads, ParallelGCThreads), // mt discovery degree

                             _cmsGen->refs_discovery_is_atomic(), // discovery is not atomic

                             &_is_alive_closure);                 // closure for liveness info

    // Initialize the _ref_processor field of CMSGen

    _cmsGen->set_ref_processor(_ref_processor);

  }

}

AdaptiveSizePolicy* CMSCollector::size_policy() {

  GenCollectedHeap* gch = GenCollectedHeap::heap();

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

}

void ConcurrentMarkSweepGeneration::initialize_performance_counters() {

  const char* gen_name = "old";

  GenCollectorPolicy* gcp = GenCollectedHeap::heap()->gen_policy();

  // Generation Counters - generation 1, 1 subspace

  _gen_counters = new GenerationCounters(gen_name, 1, 1,

      gcp->min_old_size(), gcp->max_old_size(), &_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;

}

double CMSStats::cms_free_adjustment_factor(size_t free) const {

  // TBD: CR 6909490

  return 1.0;

}

void CMSStats::adjust_cms_free_adjustment_factor(bool fail, size_t free) {

}

// 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 = MIN2(gch->young_gen()->capacity(),

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

  if (cms_free > expected_promotion) {

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

    // for the next young 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;

    double cms_adjustment = (100.0 - CMSIncrementalSafetyFactor) / 100.0;

    // Apply a further correction factor which tries to adjust

    // for recent occurance of concurrent mode failures.

    cms_adjustment = cms_adjustment * cms_free_adjustment_factor(cms_free);

    cms_free_dbl = cms_free_dbl * cms_adjustment;

    log_trace(gc)("CMSStats::time_until_cms_gen_full: cms_free " SIZE_FORMAT " expected_promotion " SIZE_FORMAT,

                  cms_free, expected_promotion);

    log_trace(gc)("  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 a concurrent mode failure occurred recently, we want to be

  // more conservative and halve our expected time_until_cms_gen_full()

  if (work > deadline) {

    log_develop_trace(gc)("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;

}

#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_per=%g,cms_alloc=" SIZE_FORMAT,

            cms_duration(), 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 (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->cr();

}

#endif // #ifndef PRODUCT

CMSCollector::CollectorState CMSCollector::_collectorState =

                             CMSCollector::Idling;

bool CMSCollector::_foregroundGCIsActive = false;

bool CMSCollector::_foregroundGCShouldWait = false;

CMSCollector::CMSCollector(ConcurrentMarkSweepGeneration* cmsGen,

                           CardTableRS*                   ct,

                           ConcurrentMarkSweepPolicy*     cp):

  _cmsGen(cmsGen),

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

  _modUnionTable((CardTableModRefBS::card_shift - LogHeapWordSize),

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

  _modUnionClosurePar(&_modUnionTable),

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

  _span(cmsGen->reserved()),

  // Construct the is_alive_closure with _span & markBitMap

  _is_alive_closure(_span, &_markBitMap),

  _restart_addr(NULL),

  _overflow_list(NULL),

  _stats(cmsGen),

  _eden_chunk_lock(new Mutex(Mutex::leaf + 1, "CMS_eden_chunk_lock", true,

                             //verify that this lock should be acquired with safepoint check.

                             Monitor::_safepoint_check_sometimes)),

  _eden_chunk_array(NULL),     // may be set in ctor body

  _eden_chunk_capacity(0),     // -- ditto --

  _eden_chunk_index(0),        // -- ditto --

  _survivor_plab_array(NULL),  // -- ditto --

  _survivor_chunk_array(NULL), // -- ditto --

  _survivor_chunk_capacity(0), // -- ditto --

  _survivor_chunk_index(0),    // -- ditto --

  _ser_pmc_preclean_ovflw(0),

  _ser_kac_preclean_ovflw(0),

  _ser_pmc_remark_ovflw(0),

  _par_pmc_remark_ovflw(0),

  _ser_kac_ovflw(0),

  _par_kac_ovflw(0),

#ifndef PRODUCT

  _num_par_pushes(0),

#endif

  _collection_count_start(0),

  _verifying(false),

  _verification_mark_bm(0, Mutex::leaf + 1, "CMS_verification_mark_bm_lock"),

  _completed_initialization(false),

  _collector_policy(cp),

  _should_unload_classes(CMSClassUnloadingEnabled),

  _concurrent_cycles_since_last_unload(0),

  _roots_scanning_options(GenCollectedHeap::SO_None),

  _inter_sweep_estimate(CMS_SweepWeight, CMS_SweepPadding),

  _intra_sweep_estimate(CMS_SweepWeight, CMS_SweepPadding),

  _gc_tracer_cm(new (ResourceObj::C_HEAP, mtGC) CMSTracer()),

  _gc_timer_cm(new (ResourceObj::C_HEAP, mtGC) ConcurrentGCTimer()),

  _cms_start_registered(false)

{

  // Now expand the span and allocate the collection support structures

  // (MUT, marking bit map etc.) to cover both generations subject to

  // collection.

  // For use by dirty card to oop closures.

  _cmsGen->cmsSpace()->set_collector(this);

  // Allocate MUT and marking bit map

  {

    MutexLockerEx x(_markBitMap.lock(), Mutex::_no_safepoint_check_flag);

    if (!_markBitMap.allocate(_span)) {

      log_warning(gc)("Failed to allocate CMS Bit Map");

      return;

    }

    assert(_markBitMap.covers(_span), "_markBitMap inconsistency?");

  }

  {

    _modUnionTable.allocate(_span);

    assert(_modUnionTable.covers(_span), "_modUnionTable inconsistency?");

  }