/*

 * 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.

 *

 */

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

// If want to accumulate detailed statistics on work queues

// turn this on.

#define G1_DETAILED_STATS 0

#if G1_DETAILED_STATS

#  define IF_G1_DETAILED_STATS(code) code

#else

#  define IF_G1_DETAILED_STATS(code)

#endif

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* _scan_only_head;

  HeapRegion* _scan_only_tail;

  size_t      _length;

  size_t      _scan_only_length;

  size_t      _last_sampled_rs_lengths;

  size_t      _sampled_rs_lengths;

  HeapRegion* _curr;

  HeapRegion* _curr_scan_only;

  HeapRegion* _survivor_head;

  HeapRegion* _survivor_tail;

  size_t      _survivor_length;

  void          empty_list(HeapRegion* list);

public:

  YoungList(G1CollectedHeap* g1h);

  void          push_region(HeapRegion* hr);

  void          add_survivor_region(HeapRegion* hr);

  HeapRegion*   pop_region();

  void          empty_list();

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

  size_t        length() { return _length; }

  size_t        scan_only_length() { return _scan_only_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();

  HeapRegion* first_region() { return _head; }

  HeapRegion* first_scan_only_region() { return _scan_only_head; }

  HeapRegion* first_survivor_region() { return _survivor_head; }

  HeapRegion* last_survivor_region() { return _survivor_tail; }

  HeapRegion* par_get_next_scan_only_region() {

    MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

    HeapRegion* ret = _curr_scan_only;

    if (ret != NULL)

      _curr_scan_only = ret->get_next_young_region();

    return ret;

  }

  // debugging

  bool          check_list_well_formed();

  bool          check_list_empty(bool ignore_scan_only_list,

                                 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:

  enum SomePrivateConstants {

    VeryLargeInBytes = HeapRegion::GrainBytes/2,

    VeryLargeInWords = VeryLargeInBytes/HeapWordSize,

    MinHeapDeltaBytes = 10 * HeapRegion::GrainBytes,      // FIXME

    NumAPIs = HeapRegion::MaxAge

  };

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

  static G1CollectedHeap* _g1h;

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

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

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

  // Helper function for two callbacks below.

  // "full", if true, indicates that the GC is for a System.gc() request,

  // and should collect the entire heap.  If "clear_all_soft_refs" is true,

  // all soft references are cleared during the GC.  If "full" is false,

  // "word_size" describes the allocation that the GC should

  // attempt (at least) to satisfy.

  void do_collection(bool full, 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 <= (size_t) 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;

    }

  }

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

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

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

  // After a collection pause, make the regions in the CS into free

  // regions.

  void free_collection_set(HeapRegion* cs_head);

  // Applies "scan_non_heap_roots" to roots outside the heap,

  // "scan_rs" to roots inside the heap (having done "set_region" to

  // indicate the region in which the root resides), and does "scan_perm"

  // (setting the generation to the perm generation.)  If "scan_rs" is

  // NULL, then this step is skipped.  The "worker_i"

  // param is for use with parallel roots processing, and should be

  // the "i" of the calling parallel worker thread's work(i) function.

  // In the sequential case this param will be ignored.

  void g1_process_strong_roots(bool collecting_perm_gen,

                               SharedHeap::ScanningOption so,

                               OopClosure* scan_non_heap_roots,

                               OopsInHeapRegionClosure* scan_rs,

                               OopsInHeapRegionClosure* scan_so,

                               OopsInGenClosure* scan_perm,

                               int worker_i);

  void scan_scan_only_set(OopsInHeapRegionClosure* oc,

                          int worker_i);

  void scan_scan_only_region(HeapRegion* hr,

                             OopsInHeapRegionClosure* oc,

                             int worker_i);

  // Apply "blk" to all the weak roots of the system.  These include

  // JNI weak roots, the code cache, system dictionary, symbol table,

  // string table, and referents of reachable weak refs.

  void g1_process_weak_roots(OopClosure* root_closure,

                             OopClosure* non_root_closure);

  // Invoke "save_marks" on all heap regions.

  void save_marks();

  // Free a heap region.

  void free_region(HeapRegion* hr);

  // A component of "free_region", exposed for 'batching'.

  // All the params after "hr" are out params: the used bytes of the freed

  // region(s), the number of H regions cleared, the number of regions

  // freed, and pointers to the head and tail of a list of freed contig

  // regions, linked throught the "next_on_unclean_list" field.

  void free_region_work(HeapRegion* hr,

                        size_t& pre_used,

                        size_t& cleared_h,