/*

 * Copyright 2001-2009 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.

 *

 */

// ConcurrentMarkSweepGeneration is in support of a concurrent

// mark-sweep old generation in the Detlefs-Printezis--Boehm-Demers-Schenker

// style. We assume, for now, that this generation is always the

// seniormost generation (modulo the PermGeneration), and for simplicity

// in the first implementation, that this generation is a single compactible

// space. Neither of these restrictions appears essential, and will be

// relaxed in the future when more time is available to implement the

// greater generality (and there's a need for it).

//

// Concurrent mode failures are currently handled by

// means of a sliding mark-compact.

class CMSAdaptiveSizePolicy;

class CMSConcMarkingTask;

class CMSGCAdaptivePolicyCounters;

class ConcurrentMarkSweepGeneration;

class ConcurrentMarkSweepPolicy;

class ConcurrentMarkSweepThread;

class CompactibleFreeListSpace;

class FreeChunk;

class PromotionInfo;

class ScanMarkedObjectsAgainCarefullyClosure;

// A generic CMS bit map. It's the basis for both the CMS marking bit map

// as well as for the mod union table (in each case only a subset of the

// methods are used). This is essentially a wrapper around the BitMap class,

// with one bit per (1<<_shifter) HeapWords. (i.e. for the marking bit map,

// we have _shifter == 0. and for the mod union table we have

// shifter == CardTableModRefBS::card_shift - LogHeapWordSize.)

// XXX 64-bit issues in BitMap?

class CMSBitMap VALUE_OBJ_CLASS_SPEC {

  friend class VMStructs;

  HeapWord* _bmStartWord;   // base address of range covered by map

  size_t    _bmWordSize;    // map size (in #HeapWords covered)

  const int _shifter;       // shifts to convert HeapWord to bit position

  VirtualSpace _virtual_space; // underlying the bit map

  BitMap    _bm;            // the bit map itself

 public:

  Mutex* const _lock;       // mutex protecting _bm;

 public:

  // constructor

  CMSBitMap(int shifter, int mutex_rank, const char* mutex_name);

  // allocates the actual storage for the map

  bool allocate(MemRegion mr);

  // field getter

  Mutex* lock() const { return _lock; }

  // locking verifier convenience function

  void assert_locked() const PRODUCT_RETURN;

  // inquiries

  HeapWord* startWord()   const { return _bmStartWord; }

  size_t    sizeInWords() const { return _bmWordSize;  }

  size_t    sizeInBits()  const { return _bm.size();   }

  // the following is one past the last word in space

  HeapWord* endWord()     const { return _bmStartWord + _bmWordSize; }

  // reading marks

  bool isMarked(HeapWord* addr) const;

  bool par_isMarked(HeapWord* addr) const; // do not lock checks

  bool isUnmarked(HeapWord* addr) const;

  bool isAllClear() const;

  // writing marks

  void mark(HeapWord* addr);

  // For marking by parallel GC threads;

  // returns true if we did, false if another thread did

  bool par_mark(HeapWord* addr);

  void mark_range(MemRegion mr);

  void par_mark_range(MemRegion mr);

  void mark_large_range(MemRegion mr);

  void par_mark_large_range(MemRegion mr);

  void par_clear(HeapWord* addr); // For unmarking by parallel GC threads.

  void clear_range(MemRegion mr);

  void par_clear_range(MemRegion mr);

  void clear_large_range(MemRegion mr);

  void par_clear_large_range(MemRegion mr);

  void clear_all();

  void clear_all_incrementally();  // Not yet implemented!!

  NOT_PRODUCT(

    // checks the memory region for validity

    void region_invariant(MemRegion mr);

  )

  // iteration

  void iterate(BitMapClosure* cl) {

    _bm.iterate(cl);

  }

  void iterate(BitMapClosure* cl, HeapWord* left, HeapWord* right);

  void dirty_range_iterate_clear(MemRegionClosure* cl);

  void dirty_range_iterate_clear(MemRegion mr, MemRegionClosure* cl);

  // auxiliary support for iteration

  HeapWord* getNextMarkedWordAddress(HeapWord* addr) const;

  HeapWord* getNextMarkedWordAddress(HeapWord* start_addr,

                                            HeapWord* end_addr) const;

  HeapWord* getNextUnmarkedWordAddress(HeapWord* addr) const;

  HeapWord* getNextUnmarkedWordAddress(HeapWord* start_addr,

                                              HeapWord* end_addr) const;

  MemRegion getAndClearMarkedRegion(HeapWord* addr);

  MemRegion getAndClearMarkedRegion(HeapWord* start_addr,

                                           HeapWord* end_addr);

  // conversion utilities

  HeapWord* offsetToHeapWord(size_t offset) const;

  size_t    heapWordToOffset(HeapWord* addr) const;

  size_t    heapWordDiffToOffsetDiff(size_t diff) const;

  // debugging

  // is this address range covered by the bit-map?

  NOT_PRODUCT(

    bool covers(MemRegion mr) const;

    bool covers(HeapWord* start, size_t size = 0) const;

  )

  void verifyNoOneBitsInRange(HeapWord* left, HeapWord* right) PRODUCT_RETURN;

};

// Represents a marking stack used by the CMS collector.

// Ideally this should be GrowableArray<> just like MSC's marking stack(s).

class CMSMarkStack: public CHeapObj  {

  //

  friend class CMSCollector;   // to get at expasion stats further below

  //

  VirtualSpace _virtual_space;  // space for the stack

  oop*   _base;      // bottom of stack

  size_t _index;     // one more than last occupied index

  size_t _capacity;  // max #elements

  Mutex  _par_lock;  // an advisory lock used in case of parallel access

  NOT_PRODUCT(size_t _max_depth;)  // max depth plumbed during run

 protected:

  size_t _hit_limit;      // we hit max stack size limit

  size_t _failed_double;  // we failed expansion before hitting limit

 public:

  CMSMarkStack():

    _par_lock(Mutex::event, "CMSMarkStack._par_lock", true),

    _hit_limit(0),

    _failed_double(0) {}

  bool allocate(size_t size);

  size_t capacity() const { return _capacity; }

  oop pop() {

    if (!isEmpty()) {

      return _base[--_index] ;

    }

    return NULL;

  }

  bool push(oop ptr) {

    if (isFull()) {

      return false;

    } else {

      _base[_index++] = ptr;

      NOT_PRODUCT(_max_depth = MAX2(_max_depth, _index));

      return true;

    }

  }

  bool isEmpty() const { return _index == 0; }

  bool isFull()  const {

    assert(_index <= _capacity, "buffer overflow");

    return _index == _capacity;

  }

  size_t length() { return _index; }

  // "Parallel versions" of some of the above

  oop par_pop() {

    // lock and pop

    MutexLockerEx x(&_par_lock, Mutex::_no_safepoint_check_flag);

    return pop();

  }

  bool par_push(oop ptr) {

    // lock and push

    MutexLockerEx x(&_par_lock, Mutex::_no_safepoint_check_flag);

    return push(ptr);

  }

  // Forcibly reset the stack, losing all of its contents.

  void reset() {

    _index = 0;

  }

  // Expand the stack, typically in response to an overflow condition

  void expand();

  // Compute the least valued stack element.

  oop least_value(HeapWord* low) {

     oop least = (oop)low;

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

       least = MIN2(least, _base[i]);

     }

     return least;

  }

  // Exposed here to allow stack expansion in || case

  Mutex* par_lock() { return &_par_lock; }

};

class CardTableRS;

class CMSParGCThreadState;

class ModUnionClosure: public MemRegionClosure {

 protected:

  CMSBitMap* _t;

 public:

  ModUnionClosure(CMSBitMap* t): _t(t) { }

  void do_MemRegion(MemRegion mr);

};

class ModUnionClosurePar: public ModUnionClosure {

 public:

  ModUnionClosurePar(CMSBitMap* t): ModUnionClosure(t) { }

  void do_MemRegion(MemRegion mr);

};

// Survivor Chunk Array in support of parallelization of

// Survivor Space rescan.

class ChunkArray: public CHeapObj {

  size_t _index;

  size_t _capacity;

  HeapWord** _array;   // storage for array

 public:

  ChunkArray() : _index(0), _capacity(0), _array(NULL) {}

  ChunkArray(HeapWord** a, size_t c):

    _index(0), _capacity(c), _array(a) {}

  HeapWord** array() { return _array; }

  void set_array(HeapWord** a) { _array = a; }

  size_t capacity() { return _capacity; }

  void set_capacity(size_t c) { _capacity = c; }

  size_t end() {

    assert(_index < capacity(), "_index out of bounds");

    return _index;

  }  // exclusive

  HeapWord* nth(size_t n) {

    assert(n < end(), "Out of bounds access");

    return _array[n];

  }

  void reset() {

    _index = 0;

  }

  void record_sample(HeapWord* p, size_t sz) {

    // For now we do not do anything with the size

    if (_index < _capacity) {

      _array[_index++] = p;

    }

  }

};

//

// Timing, allocation and promotion statistics for gc scheduling and incremental

// mode pacing.  Most statistics are exponential averages.

//

class CMSStats VALUE_OBJ_CLASS_SPEC {

 private:

  ConcurrentMarkSweepGeneration* const _cms_gen;   // The cms (old) gen.

  // The following are exponential averages with factor alpha:

  //   avg = (100 - alpha) * avg + alpha * cur_sample

  //

  //   The durations measure:  end_time[n] - start_time[n]

  //   The periods measure:    start_time[n] - start_time[n-1]

  //

  // The cms period and duration include only concurrent collections; time spent

  // in foreground cms collections due to System.gc() or because of a failure to

  // keep up are not included.

  //

  // There are 3 alphas to "bootstrap" the statistics.  The _saved_alpha is the

  // real value, but is used only after the first period.  A value of 100 is

  // used for the first sample so it gets the entire weight.

  unsigned int _saved_alpha; // 0-100

  unsigned int _gc0_alpha;

  unsigned int _cms_alpha;

  double _gc0_duration;

  double _gc0_period;

  size_t _gc0_promoted;         // bytes promoted per gc0

  double _cms_duration;

  double _cms_duration_pre_sweep; // time from initiation to start of sweep

  double _cms_duration_per_mb;

  double _cms_period;

  size_t _cms_allocated;        // bytes of direct allocation per gc0 period

  // Timers.

  elapsedTimer _cms_timer;

  TimeStamp    _gc0_begin_time;

  TimeStamp    _cms_begin_time;

  TimeStamp    _cms_end_time;

  // Snapshots of the amount used in the CMS generation.

  size_t _cms_used_at_gc0_begin;

  size_t _cms_used_at_gc0_end;

  size_t _cms_used_at_cms_begin;

  // Used to prevent the duty cycle from being reduced in the middle of a cms

  // cycle.

  bool _allow_duty_cycle_reduction;

  enum {

    _GC0_VALID = 0x1,

    _CMS_VALID = 0x2,

    _ALL_VALID = _GC0_VALID | _CMS_VALID

  };

  unsigned int _valid_bits;

  unsigned int _icms_duty_cycle;        // icms duty cycle (0-100).

 protected:

  // Return a duty cycle that avoids wild oscillations, by limiting the amount

  // of change between old_duty_cycle and new_duty_cycle (the latter is treated

  // as a recommended value).

  static unsigned int icms_damped_duty_cycle(unsigned int old_duty_cycle,

                                             unsigned int new_duty_cycle);

  unsigned int icms_update_duty_cycle_impl();

 public:

  CMSStats(ConcurrentMarkSweepGeneration* cms_gen,

           unsigned int alpha = CMSExpAvgFactor);

  // Whether or not the statistics contain valid data; higher level statistics

  // cannot be called until this returns true (they require at least one young

  // gen and one cms cycle to have completed).

  bool valid() const;

  // Record statistics.

  void record_gc0_begin();

  void record_gc0_end(size_t cms_gen_bytes_used);

  void record_cms_begin();

  void record_cms_end();

  // Allow management of the cms timer, which must be stopped/started around

  // yield points.

  elapsedTimer& cms_timer()     { return _cms_timer; }

  void start_cms_timer()        { _cms_timer.start(); }

  void stop_cms_timer()         { _cms_timer.stop(); }

  // Basic statistics; units are seconds or bytes.

  double gc0_period() const     { return _gc0_period; }

  double gc0_duration() const   { return _gc0_duration; }

  size_t gc0_promoted() const   { return _gc0_promoted; }

  double cms_period() const          { return _cms_period; }

  double cms_duration() const        { return _cms_duration; }

  double cms_duration_per_mb() const { return _cms_duration_per_mb; }

  size_t cms_allocated() const       { return _cms_allocated; }

  size_t cms_used_at_gc0_end() const { return _cms_used_at_gc0_end;}

  // Seconds since the last background cms cycle began or ended.

  double cms_time_since_begin() const;

  double cms_time_since_end() const;

  // Higher level statistics--caller must check that valid() returns true before

  // calling.

  // Returns bytes promoted per second of wall clock time.

  double promotion_rate() const;

  // Returns bytes directly allocated per second of wall clock time.

  double cms_allocation_rate() const;

  // Rate at which space in the cms generation is being consumed (sum of the

  // above two).

  double cms_consumption_rate() const;

  // Returns an estimate of the number of seconds until the cms generation will

  // fill up, assuming no collection work is done.

  double time_until_cms_gen_full() const;

  // Returns an estimate of the number of seconds remaining until

  // the cms generation collection should start.

  double time_until_cms_start() const;

  // End of higher level statistics.

  // Returns the cms incremental mode duty cycle, as a percentage (0-100).

  unsigned int icms_duty_cycle() const { return _icms_duty_cycle; }

  // Update the duty cycle and return the new value.

  unsigned int icms_update_duty_cycle();

  // Debugging.

  void print_on(outputStream* st) const PRODUCT_RETURN;

  void print() const { print_on(gclog_or_tty); }

};

// A closure related to weak references processing which

// we embed in the CMSCollector, since we need to pass

// it to the reference processor for secondary filtering

// of references based on reachability of referent;

// see role of _is_alive_non_header closure in the

// ReferenceProcessor class.

// For objects in the CMS generation, this closure checks

// if the object is "live" (reachable). Used in weak

// reference processing.

class CMSIsAliveClosure: public BoolObjectClosure {

  const MemRegion  _span;

  const CMSBitMap* _bit_map;

  friend class CMSCollector;

 public:

  CMSIsAliveClosure(MemRegion span,

                    CMSBitMap* bit_map):

    _span(span),

    _bit_map(bit_map) {

    assert(!span.is_empty(), "Empty span could spell trouble");

  }

  void do_object(oop obj) {

    assert(false, "not to be invoked");

  }

  bool do_object_b(oop obj);

};

// Implements AbstractRefProcTaskExecutor for CMS.

class CMSRefProcTaskExecutor: public AbstractRefProcTaskExecutor {

public:

  CMSRefProcTaskExecutor(CMSCollector& collector)

    : _collector(collector)

  { }

  // Executes a task using worker threads.

  virtual void execute(ProcessTask& task);

  virtual void execute(EnqueueTask& task);

private:

  CMSCollector& _collector;

};

class CMSCollector: public CHeapObj {

  friend class VMStructs;

  friend class ConcurrentMarkSweepThread;

  friend class ConcurrentMarkSweepGeneration;

  friend class CompactibleFreeListSpace;

  friend class CMSParRemarkTask;

  friend class CMSConcMarkingTask;

  friend class CMSRefProcTaskProxy;

  friend class CMSRefProcTaskExecutor;

  friend class ScanMarkedObjectsAgainCarefullyClosure;  // for sampling eden

  friend class SurvivorSpacePrecleanClosure;            // --- ditto -------

  friend class PushOrMarkClosure;             // to access _restart_addr

  friend class Par_PushOrMarkClosure;             // to access _restart_addr

  friend class MarkFromRootsClosure;          //  -- ditto --

                                              // ... and for clearing cards

  friend class Par_MarkFromRootsClosure;      //  to access _restart_addr

                                              // ... and for clearing cards

  friend class Par_ConcMarkingClosure;        //  to access _restart_addr etc.

  friend class MarkFromRootsVerifyClosure;    // to access _restart_addr

  friend class PushAndMarkVerifyClosure;      //  -- ditto --

  friend class MarkRefsIntoAndScanClosure;    // to access _overflow_list

  friend class PushAndMarkClosure;            //  -- ditto --

  friend class Par_PushAndMarkClosure;        //  -- ditto --

  friend class CMSKeepAliveClosure;           //  -- ditto --

  friend class CMSDrainMarkingStackClosure;   //  -- ditto --

  friend class CMSInnerParMarkAndPushClosure; //  -- ditto --

  NOT_PRODUCT(friend class ScanMarkedObjectsAgainClosure;) //  assertion on _overflow_list

  friend class ReleaseForegroundGC;  // to access _foregroundGCShouldWait

  friend class VM_CMS_Operation;

  friend class VM_CMS_Initial_Mark;

  friend class VM_CMS_Final_Remark;

 private:

  jlong _time_of_last_gc;

  void update_time_of_last_gc(jlong now) {

    _time_of_last_gc = now;

  }

  OopTaskQueueSet* _task_queues;

  // Overflow list of grey objects, threaded through mark-word

  // Manipulated with CAS in the parallel/multi-threaded case.

  oop _overflow_list;

  // The following array-pair keeps track of mark words

  // displaced for accomodating overflow list above.

  // This code will likely be revisited under RFE#4922830.

  GrowableArray<oop>*     _preserved_oop_stack;

  GrowableArray<markOop>* _preserved_mark_stack;