/*

 * Copyright (c) 2001, 2010, 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.

 *

 */

// A "G1CollectedHeap" is an implementation of a java heap for HotSpot.

// It uses the "Garbage First" heap organization and algorithm, which

// may combine concurrent marking with parallel, incremental compaction of

// heap subsets that will yield large amounts of garbage.

class HeapRegion;

class HeapRegionSeq;

class PermanentGenerationSpec;

class GenerationSpec;

class OopsInHeapRegionClosure;

class G1ScanHeapEvacClosure;

class ObjectClosure;

class SpaceClosure;

class CompactibleSpaceClosure;

class Space;

class G1CollectorPolicy;

class GenRemSet;

class G1RemSet;

class HeapRegionRemSetIterator;

class ConcurrentMark;

class ConcurrentMarkThread;

class ConcurrentG1Refine;

class ConcurrentZFThread;

typedef OverflowTaskQueue<StarTask>         RefToScanQueue;

typedef GenericTaskQueueSet<RefToScanQueue> RefToScanQueueSet;

typedef int RegionIdx_t;   // needs to hold [ 0..max_regions() )

typedef int CardIdx_t;     // needs to hold [ 0..CardsPerRegion )

enum G1GCThreadGroups {

  G1CRGroup = 0,

  G1ZFGroup = 1,

  G1CMGroup = 2,

  G1CLGroup = 3

};

enum GCAllocPurpose {

  GCAllocForTenured,

  GCAllocForSurvived,

  GCAllocPurposeCount

};

class YoungList : public CHeapObj {

private:

  G1CollectedHeap* _g1h;

  HeapRegion* _head;

  HeapRegion* _survivor_head;

  HeapRegion* _survivor_tail;

  HeapRegion* _curr;

  size_t      _length;

  size_t      _survivor_length;

  size_t      _last_sampled_rs_lengths;

  size_t      _sampled_rs_lengths;

  void         empty_list(HeapRegion* list);

public:

  YoungList(G1CollectedHeap* g1h);

  void         push_region(HeapRegion* hr);

  void         add_survivor_region(HeapRegion* hr);

  void         empty_list();

  bool         is_empty() { return _length == 0; }

  size_t       length() { return _length; }

  size_t       survivor_length() { return _survivor_length; }

  void rs_length_sampling_init();

  bool rs_length_sampling_more();

  void rs_length_sampling_next();

  void reset_sampled_info() {

    _last_sampled_rs_lengths =   0;

  }

  size_t sampled_rs_lengths() { return _last_sampled_rs_lengths; }

  // for development purposes

  void reset_auxilary_lists();

  void clear() { _head = NULL; _length = 0; }

  void clear_survivors() {

    _survivor_head    = NULL;

    _survivor_tail    = NULL;

    _survivor_length  = 0;

  }

  HeapRegion* first_region() { return _head; }

  HeapRegion* first_survivor_region() { return _survivor_head; }

  HeapRegion* last_survivor_region() { return _survivor_tail; }

  // debugging

  bool          check_list_well_formed();

  bool          check_list_empty(bool check_sample = true);

  void          print();

};

class RefineCardTableEntryClosure;

class G1CollectedHeap : public SharedHeap {

  friend class VM_G1CollectForAllocation;

  friend class VM_GenCollectForPermanentAllocation;

  friend class VM_G1CollectFull;

  friend class VM_G1IncCollectionPause;

  friend class VMStructs;

  // Closures used in implementation.

  friend class G1ParCopyHelper;

  friend class G1IsAliveClosure;

  friend class G1EvacuateFollowersClosure;

  friend class G1ParScanThreadState;

  friend class G1ParScanClosureSuper;

  friend class G1ParEvacuateFollowersClosure;

  friend class G1ParTask;

  friend class G1FreeGarbageRegionClosure;

  friend class RefineCardTableEntryClosure;

  friend class G1PrepareCompactClosure;

  friend class RegionSorter;

  friend class CountRCClosure;

  friend class EvacPopObjClosure;

  friend class G1ParCleanupCTTask;

  // Other related classes.

  friend class G1MarkSweep;

private:

  // The one and only G1CollectedHeap, so static functions can find it.

  static G1CollectedHeap* _g1h;

  static size_t _humongous_object_threshold_in_words;

  // Storage for the G1 heap (excludes the permanent generation).

  VirtualSpace _g1_storage;

  MemRegion    _g1_reserved;

  // The part of _g1_storage that is currently committed.

  MemRegion _g1_committed;

  // The maximum part of _g1_storage that has ever been committed.

  MemRegion _g1_max_committed;

  // The number of regions that are completely free.

  size_t _free_regions;

  // The number of regions we could create by expansion.

  size_t _expansion_regions;

  // Return the number of free regions in the heap (by direct counting.)

  size_t count_free_regions();

  // Return the number of free regions on the free and unclean lists.

  size_t count_free_regions_list();

  // The block offset table for the G1 heap.

  G1BlockOffsetSharedArray* _bot_shared;

  // Move all of the regions off the free lists, then rebuild those free

  // lists, before and after full GC.

  void tear_down_region_lists();

  void rebuild_region_lists();

  // This sets all non-empty regions to need zero-fill (which they will if

  // they are empty after full collection.)

  void set_used_regions_to_need_zero_fill();

  // The sequence of all heap regions in the heap.

  HeapRegionSeq* _hrs;

  // The region from which normal-sized objects are currently being

  // allocated.  May be NULL.

  HeapRegion* _cur_alloc_region;

  // Postcondition: cur_alloc_region == NULL.

  void abandon_cur_alloc_region();

  void abandon_gc_alloc_regions();

  // The to-space memory regions into which objects are being copied during

  // a GC.

  HeapRegion* _gc_alloc_regions[GCAllocPurposeCount];

  size_t _gc_alloc_region_counts[GCAllocPurposeCount];

  // These are the regions, one per GCAllocPurpose, that are half-full

  // at the end of a collection and that we want to reuse during the

  // next collection.

  HeapRegion* _retained_gc_alloc_regions[GCAllocPurposeCount];

  // This specifies whether we will keep the last half-full region at

  // the end of a collection so that it can be reused during the next

  // collection (this is specified per GCAllocPurpose)

  bool _retain_gc_alloc_region[GCAllocPurposeCount];

  // A list of the regions that have been set to be alloc regions in the

  // current collection.

  HeapRegion* _gc_alloc_region_list;

  // Determines PLAB size for a particular allocation purpose.

  static size_t desired_plab_sz(GCAllocPurpose purpose);

  // When called by par thread, require par_alloc_during_gc_lock() to be held.

  void push_gc_alloc_region(HeapRegion* hr);

  // This should only be called single-threaded.  Undeclares all GC alloc

  // regions.

  void forget_alloc_region_list();

  // Should be used to set an alloc region, because there's other

  // associated bookkeeping.

  void set_gc_alloc_region(int purpose, HeapRegion* r);

  // Check well-formedness of alloc region list.

  bool check_gc_alloc_regions();

  // Outside of GC pauses, the number of bytes used in all regions other

  // than the current allocation region.

  size_t _summary_bytes_used;

  // This is used for a quick test on whether a reference points into

  // the collection set or not. Basically, we have an array, with one

  // byte per region, and that byte denotes whether the corresponding

  // region is in the collection set or not. The entry corresponding

  // the bottom of the heap, i.e., region 0, is pointed to by

  // _in_cset_fast_test_base.  The _in_cset_fast_test field has been

  // biased so that it actually points to address 0 of the address

  // space, to make the test as fast as possible (we can simply shift

  // the address to address into it, instead of having to subtract the

  // bottom of the heap from the address before shifting it; basically

  // it works in the same way the card table works).

  bool* _in_cset_fast_test;

  // The allocated array used for the fast test on whether a reference

  // points into the collection set or not. This field is also used to

  // free the array.

  bool* _in_cset_fast_test_base;

  // The length of the _in_cset_fast_test_base array.

  size_t _in_cset_fast_test_length;

  volatile unsigned _gc_time_stamp;

  size_t* _surviving_young_words;

  void setup_surviving_young_words();

  void update_surviving_young_words(size_t* surv_young_words);

  void cleanup_surviving_young_words();

  // It decides whether an explicit GC should start a concurrent cycle

  // instead of doing a STW GC. Currently, a concurrent cycle is

  // explicitly started if:

  // (a) cause == _gc_locker and +GCLockerInvokesConcurrent, or

  // (b) cause == _java_lang_system_gc and +ExplicitGCInvokesConcurrent.

  bool should_do_concurrent_full_gc(GCCause::Cause cause);

  // Keeps track of how many "full collections" (i.e., Full GCs or

  // concurrent cycles) we have completed. The number of them we have

  // started is maintained in _total_full_collections in CollectedHeap.

  volatile unsigned int _full_collections_completed;

protected:

  // Returns "true" iff none of the gc alloc regions have any allocations

  // since the last call to "save_marks".

  bool all_alloc_regions_no_allocs_since_save_marks();

  // Perform finalization stuff on all allocation regions.

  void retire_all_alloc_regions();

  // The number of regions allocated to hold humongous objects.

  int         _num_humongous_regions;

  YoungList*  _young_list;

  // The current policy object for the collector.

  G1CollectorPolicy* _g1_policy;

  // Parallel allocation lock to protect the current allocation region.

  Mutex  _par_alloc_during_gc_lock;

  Mutex* par_alloc_during_gc_lock() { return &_par_alloc_during_gc_lock; }

  // If possible/desirable, allocate a new HeapRegion for normal object

  // allocation sufficient for an allocation of the given "word_size".

  // If "do_expand" is true, will attempt to expand the heap if necessary

  // to to satisfy the request.  If "zero_filled" is true, requires a

  // zero-filled region.

  // (Returning NULL will trigger a GC.)

  virtual HeapRegion* newAllocRegion_work(size_t word_size,

                                          bool do_expand,

                                          bool zero_filled);

  virtual HeapRegion* newAllocRegion(size_t word_size,

                                     bool zero_filled = true) {

    return newAllocRegion_work(word_size, false, zero_filled);

  }

  virtual HeapRegion* newAllocRegionWithExpansion(int purpose,

                                                  size_t word_size,

                                                  bool zero_filled = true);

  // Attempt to allocate an object of the given (very large) "word_size".

  // Returns "NULL" on failure.

  virtual HeapWord* humongousObjAllocate(size_t word_size);

  // If possible, allocate a block of the given word_size, else return "NULL".

  // Returning NULL will trigger GC or heap expansion.

  // These two methods have rather awkward pre- and

  // post-conditions. If they are called outside a safepoint, then

  // they assume that the caller is holding the heap lock. Upon return

  // they release the heap lock, if they are returning a non-NULL

  // value. attempt_allocation_slow() also dirties the cards of a

  // newly-allocated young region after it releases the heap

  // lock. This change in interface was the neatest way to achieve

  // this card dirtying without affecting mem_allocate(), which is a

  // more frequently called method. We tried two or three different

  // approaches, but they were even more hacky.

  HeapWord* attempt_allocation(size_t word_size,

                               bool permit_collection_pause = true);

  HeapWord* attempt_allocation_slow(size_t word_size,

                                    bool permit_collection_pause = true);

  // Allocate blocks during garbage collection. Will ensure an

  // allocation region, either by picking one or expanding the

  // heap, and then allocate a block of the given size. The block

  // may not be a humongous - it must fit into a single heap region.

  HeapWord* allocate_during_gc(GCAllocPurpose purpose, size_t word_size);

  HeapWord* par_allocate_during_gc(GCAllocPurpose purpose, size_t word_size);

  HeapWord* allocate_during_gc_slow(GCAllocPurpose purpose,

                                    HeapRegion*    alloc_region,

                                    bool           par,

                                    size_t         word_size);

  // Ensure that no further allocations can happen in "r", bearing in mind

  // that parallel threads might be attempting allocations.

  void par_allocate_remaining_space(HeapRegion* r);

  // Retires an allocation region when it is full or at the end of a

  // GC pause.

  void  retire_alloc_region(HeapRegion* alloc_region, bool par);

  // - if explicit_gc is true, the GC is for a System.gc() or a heap

  // inspection request and should collect the entire heap

  // - if clear_all_soft_refs is true, all soft references are cleared

  // during the GC

  // - if explicit_gc is false, word_size describes the allocation that

  // the GC should attempt (at least) to satisfy

  void do_collection(bool explicit_gc,

                     bool clear_all_soft_refs,

                     size_t word_size);

  // Callback from VM_G1CollectFull operation.

  // Perform a full collection.

  void do_full_collection(bool clear_all_soft_refs);

  // Resize the heap if necessary after a full collection.  If this is

  // after a collect-for allocation, "word_size" is the allocation size,

  // and will be considered part of the used portion of the heap.

  void resize_if_necessary_after_full_collection(size_t word_size);

  // Callback from VM_G1CollectForAllocation operation.

  // This function does everything necessary/possible to satisfy a

  // failed allocation request (including collection, expansion, etc.)

  HeapWord* satisfy_failed_allocation(size_t word_size);

  // Attempting to expand the heap sufficiently

  // to support an allocation of the given "word_size".  If

  // successful, perform the allocation and return the address of the

  // allocated block, or else "NULL".

  virtual HeapWord* expand_and_allocate(size_t word_size);

public:

  // Expand the garbage-first heap by at least the given size (in bytes!).

  // (Rounds up to a HeapRegion boundary.)

  virtual void expand(size_t expand_bytes);

  // Do anything common to GC's.

  virtual void gc_prologue(bool full);

  virtual void gc_epilogue(bool full);

  // We register a region with the fast "in collection set" test. We

  // simply set to true the array slot corresponding to this region.

  void register_region_with_in_cset_fast_test(HeapRegion* r) {

    assert(_in_cset_fast_test_base != NULL, "sanity");

    assert(r->in_collection_set(), "invariant");

    int index = r->hrs_index();

    assert(0 <= index && (size_t) index < _in_cset_fast_test_length, "invariant");

    assert(!_in_cset_fast_test_base[index], "invariant");

    _in_cset_fast_test_base[index] = true;

  }

  // This is a fast test on whether a reference points into the

  // collection set or not. It does not assume that the reference

  // points into the heap; if it doesn't, it will return false.

  bool in_cset_fast_test(oop obj) {

    assert(_in_cset_fast_test != NULL, "sanity");

    if (_g1_committed.contains((HeapWord*) obj)) {

      // no need to subtract the bottom of the heap from obj,

      // _in_cset_fast_test is biased

      size_t index = ((size_t) obj) >> HeapRegion::LogOfHRGrainBytes;

      bool ret = _in_cset_fast_test[index];

      // let's make sure the result is consistent with what the slower

      // test returns

      assert( ret || !obj_in_cs(obj), "sanity");

      assert(!ret ||  obj_in_cs(obj), "sanity");

      return ret;

    } else {

      return false;

    }

  }

  void clear_cset_fast_test() {

    assert(_in_cset_fast_test_base != NULL, "sanity");

    memset(_in_cset_fast_test_base, false,

        _in_cset_fast_test_length * sizeof(bool));

  }

  // This is called at the end of either a concurrent cycle or a Full

  // GC to update the number of full collections completed. Those two

  // can happen in a nested fashion, i.e., we start a concurrent

  // cycle, a Full GC happens half-way through it which ends first,

  // and then the cycle notices that a Full GC happened and ends

  // too. The outer parameter is a boolean to help us do a bit tighter

  // consistency checking in the method. If outer is false, the caller

  // is the inner caller in the nesting (i.e., the Full GC). If outer

  // is true, the caller is the outer caller in this nesting (i.e.,

  // the concurrent cycle). Further nesting is not currently

  // supported. The end of the this call also notifies the

  // FullGCCount_lock in case a Java thread is waiting for a full GC

  // to happen (e.g., it called System.gc() with

  // +ExplicitGCInvokesConcurrent).

  void increment_full_collections_completed(bool outer);

  unsigned int full_collections_completed() {

    return _full_collections_completed;

  }

protected:

  // Shrink the garbage-first heap by at most the given size (in bytes!).

  // (Rounds down to a HeapRegion boundary.)

  virtual void shrink(size_t expand_bytes);

  void shrink_helper(size_t expand_bytes);

  #if TASKQUEUE_STATS

  static void print_taskqueue_stats_hdr(outputStream* const st = gclog_or_tty);

  void print_taskqueue_stats(outputStream* const st = gclog_or_tty) const;

  void reset_taskqueue_stats();

  #endif // TASKQUEUE_STATS

  // Do an incremental collection: identify a collection set, and evacuate

  // its live objects elsewhere.

  virtual void do_collection_pause();

  // The guts of the incremental collection pause, executed by the vm

  // thread.

  virtual void do_collection_pause_at_safepoint(double target_pause_time_ms);

  // Actually do the work of evacuating the collection set.

  virtual void evacuate_collection_set();

  // If this is an appropriate right time, do a collection pause.

  // The "word_size" argument, if non-zero, indicates the size of an

  // allocation request that is prompting this query.

  void do_collection_pause_if_appropriate(size_t word_size);

  // The g1 remembered set of the heap.

  G1RemSet* _g1_rem_set;

  // And it's mod ref barrier set, used to track updates for the above.

  ModRefBarrierSet* _mr_bs;

  // A set of cards that cover the objects for which the Rsets should be updated

  // concurrently after the collection.

  DirtyCardQueueSet _dirty_card_queue_set;

  // The Heap Region Rem Set Iterator.

  HeapRegionRemSetIterator** _rem_set_iterator;

  // The closure used to refine a single card.

  RefineCardTableEntryClosure* _refine_cte_cl;

  // A function to check the consistency of dirty card logs.

  void check_ct_logs_at_safepoint();