/*

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

 *

 */

#ifndef SHARE_VM_GC_IMPLEMENTATION_G1_G1COLLECTEDHEAP_HPP

#define SHARE_VM_GC_IMPLEMENTATION_G1_G1COLLECTEDHEAP_HPP

#include "gc_implementation/g1/concurrentMark.hpp"

#include "gc_implementation/g1/g1AllocRegion.hpp"

#include "gc_implementation/g1/g1HRPrinter.hpp"

#include "gc_implementation/g1/g1RemSet.hpp"

#include "gc_implementation/g1/g1MonitoringSupport.hpp"

#include "gc_implementation/g1/heapRegionSeq.hpp"

#include "gc_implementation/g1/heapRegionSets.hpp"

#include "gc_implementation/shared/hSpaceCounters.hpp"

#include "gc_implementation/shared/parGCAllocBuffer.hpp"

#include "memory/barrierSet.hpp"

#include "memory/memRegion.hpp"

#include "memory/sharedHeap.hpp"

#include "utilities/stack.hpp"

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

class GenerationSpec;

class OopsInHeapRegionClosure;

class G1KlassScanClosure;

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

typedef OverflowTaskQueue<StarTask, mtGC>         RefToScanQueue;

typedef GenericTaskQueueSet<RefToScanQueue, mtGC> RefToScanQueueSet;

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

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

enum GCAllocPurpose {

  GCAllocForTenured,

  GCAllocForSurvived,

  GCAllocPurposeCount

};

class YoungList : public CHeapObj<mtGC> {

private:

  G1CollectedHeap* _g1h;

  HeapRegion* _head;

  HeapRegion* _survivor_head;

  HeapRegion* _survivor_tail;

  HeapRegion* _curr;

  uint        _length;

  uint        _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; }

  uint         length() { return _length; }

  uint         survivor_length() { return _survivor_length; }

  // Currently we do not keep track of the used byte sum for the

  // young list and the survivors and it'd be quite a lot of work to

  // do so. When we'll eventually replace the young list with

  // instances of HeapRegionLinkedList we'll get that for free. So,

  // we'll report the more accurate information then.

  size_t       eden_used_bytes() {

    assert(length() >= survivor_length(), "invariant");

    return (size_t) (length() - survivor_length()) * HeapRegion::GrainBytes;

  }

  size_t       survivor_used_bytes() {

    return (size_t) survivor_length() * HeapRegion::GrainBytes;

  }

  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 MutatorAllocRegion : public G1AllocRegion {

protected:

  virtual HeapRegion* allocate_new_region(size_t word_size, bool force);

  virtual void retire_region(HeapRegion* alloc_region, size_t allocated_bytes);

public:

  MutatorAllocRegion()

    : G1AllocRegion("Mutator Alloc Region", false /* bot_updates */) { }

};

// The G1 STW is alive closure.

// An instance is embedded into the G1CH and used as the

// (optional) _is_alive_non_header closure in the STW

// reference processor. It is also extensively used during

// refence processing during STW evacuation pauses.

class G1STWIsAliveClosure: public BoolObjectClosure {

  G1CollectedHeap* _g1;

public:

  G1STWIsAliveClosure(G1CollectedHeap* g1) : _g1(g1) {}

  void do_object(oop p) { assert(false, "Do not call."); }

  bool do_object_b(oop p);

};

class SurvivorGCAllocRegion : public G1AllocRegion {

protected:

  virtual HeapRegion* allocate_new_region(size_t word_size, bool force);

  virtual void retire_region(HeapRegion* alloc_region, size_t allocated_bytes);

public:

  SurvivorGCAllocRegion()

  : G1AllocRegion("Survivor GC Alloc Region", false /* bot_updates */) { }

};

class OldGCAllocRegion : public G1AllocRegion {

protected:

  virtual HeapRegion* allocate_new_region(size_t word_size, bool force);

  virtual void retire_region(HeapRegion* alloc_region, size_t allocated_bytes);

public:

  OldGCAllocRegion()

  : G1AllocRegion("Old GC Alloc Region", true /* bot_updates */) { }

};

class RefineCardTableEntryClosure;

class G1CollectedHeap : public SharedHeap {

  friend class VM_G1CollectForAllocation;

  friend class VM_G1CollectFull;

  friend class VM_G1IncCollectionPause;

  friend class VMStructs;

  friend class MutatorAllocRegion;

  friend class SurvivorGCAllocRegion;

  friend class OldGCAllocRegion;

  // Closures used in implementation.

  template <bool do_gen_barrier, G1Barrier barrier, bool do_mark_object>

  friend class G1ParCopyClosure;

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

  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.

  VirtualSpace _g1_storage;

  MemRegion    _g1_reserved;

  // The part of _g1_storage that is currently committed.

  MemRegion _g1_committed;

  // The master free list. It will satisfy all new region allocations.

  MasterFreeRegionList      _free_list;

  // The secondary free list which contains regions that have been

  // freed up during the cleanup process. This will be appended to the

  // master free list when appropriate.

  SecondaryFreeRegionList   _secondary_free_list;

  // It keeps track of the old regions.

  MasterOldRegionSet        _old_set;

  // It keeps track of the humongous regions.

  MasterHumongousRegionSet  _humongous_set;

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

  uint _expansion_regions;

  // The block offset table for the G1 heap.

  G1BlockOffsetSharedArray* _bot_shared;

  // Tears down the region sets / lists so that they are empty and the

  // regions on the heap do not belong to a region set / list. The

  // only exception is the humongous set which we leave unaltered. If

  // free_list_only is true, it will only tear down the master free

  // list. It is called before a Full GC (free_list_only == false) or

  // before heap shrinking (free_list_only == true).

  void tear_down_region_sets(bool free_list_only);

  // Rebuilds the region sets / lists so that they are repopulated to

  // reflect the contents of the heap. The only exception is the

  // humongous set which was not torn down in the first place. If

  // free_list_only is true, it will only rebuild the master free

  // list. It is called after a Full GC (free_list_only == false) or

  // after heap shrinking (free_list_only == true).

  void rebuild_region_sets(bool free_list_only);

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

  HeapRegionSeq _hrs;

  // Alloc region used to satisfy mutator allocation requests.

  MutatorAllocRegion _mutator_alloc_region;

  // Alloc region used to satisfy allocation requests by the GC for

  // survivor objects.

  SurvivorGCAllocRegion _survivor_gc_alloc_region;

  // PLAB sizing policy for survivors.

  PLABStats _survivor_plab_stats;

  // Alloc region used to satisfy allocation requests by the GC for

  // old objects.

  OldGCAllocRegion _old_gc_alloc_region;

  // PLAB sizing policy for tenured objects.

  PLABStats _old_plab_stats;

  PLABStats* stats_for_purpose(GCAllocPurpose purpose) {

    PLABStats* stats = NULL;

    switch (purpose) {

    case GCAllocForSurvived:

      stats = &_survivor_plab_stats;

      break;

    case GCAllocForTenured:

      stats = &_old_plab_stats;

      break;

    default:

      assert(false, "unrecognized GCAllocPurpose");

    }

    return stats;

  }

  // The last old region we allocated to during the last GC.

  // Typically, it is not full so we should re-use it during the next GC.

  HeapRegion* _retained_old_gc_alloc_region;

  // It specifies whether we should attempt to expand the heap after a

  // region allocation failure. If heap expansion fails we set this to

  // false so that we don't re-attempt the heap expansion (it's likely

  // that subsequent expansion attempts will also fail if one fails).

  // Currently, it is only consulted during GC and it's reset at the

  // start of each GC.

  bool _expand_heap_after_alloc_failure;

  // It resets the mutator alloc region before new allocations can take place.

  void init_mutator_alloc_region();

  // It releases the mutator alloc region.

  void release_mutator_alloc_region();

  // It initializes the GC alloc regions at the start of a GC.

  void init_gc_alloc_regions();

  // It releases the GC alloc regions at the end of a GC.

  void release_gc_alloc_regions(uint no_of_gc_workers);

  // It does any cleanup that needs to be done on the GC alloc regions

  // before a Full GC.

  void abandon_gc_alloc_regions();

  // Helper for monitoring and management support.

  G1MonitoringSupport* _g1mm;

  // Determines PLAB size for a particular allocation purpose.

  size_t desired_plab_sz(GCAllocPurpose purpose);

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

  uint _in_cset_fast_test_length;

  volatile unsigned _gc_time_stamp;

  size_t* _surviving_young_words;

  G1HRPrinter _hr_printer;

  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.

  // (c) cause == _g1_humongous_allocation

  bool should_do_concurrent_full_gc(GCCause::Cause cause);

  // Keeps track of how many "old marking cycles" (i.e., Full GCs or

  // concurrent cycles) we have started.

  volatile unsigned int _old_marking_cycles_started;

  // Keeps track of how many "old marking cycles" (i.e., Full GCs or

  // concurrent cycles) we have completed.

  volatile unsigned int _old_marking_cycles_completed;

  // This is a non-product method that is helpful for testing. It is

  // called at the end of a GC and artificially expands the heap by

  // allocating a number of dead regions. This way we can induce very

  // frequent marking cycles and stress the cleanup / concurrent

  // cleanup code more (as all the regions that will be allocated by

  // this method will be found dead by the marking cycle).

  void allocate_dummy_regions() PRODUCT_RETURN;

  // Clear RSets after a compaction. It also resets the GC time stamps.

  void clear_rsets_post_compaction();

  // If the HR printer is active, dump the state of the regions in the

  // heap after a compaction.

  void print_hrs_post_compaction();

  double verify(bool guard, const char* msg);

  void verify_before_gc();

  void verify_after_gc();

  void log_gc_header();

  void log_gc_footer(double pause_time_sec);

  // These are macros so that, if the assert fires, we get the correct

  // line number, file, etc.

#define heap_locking_asserts_err_msg(_extra_message_)                         \

  err_msg("%s : Heap_lock locked: %s, at safepoint: %s, is VM thread: %s",    \

          (_extra_message_),                                                  \

          BOOL_TO_STR(Heap_lock->owned_by_self()),                            \

          BOOL_TO_STR(SafepointSynchronize::is_at_safepoint()),               \

          BOOL_TO_STR(Thread::current()->is_VM_thread()))

#define assert_heap_locked()                                                  \

  do {                                                                        \

    assert(Heap_lock->owned_by_self(),                                        \

           heap_locking_asserts_err_msg("should be holding the Heap_lock"));  \

  } while (0)

#define assert_heap_locked_or_at_safepoint(_should_be_vm_thread_)             \

  do {                                                                        \

    assert(Heap_lock->owned_by_self() ||                                      \

           (SafepointSynchronize::is_at_safepoint() &&                        \

             ((_should_be_vm_thread_) == Thread::current()->is_VM_thread())), \

           heap_locking_asserts_err_msg("should be holding the Heap_lock or " \

                                        "should be at a safepoint"));         \

  } while (0)

#define assert_heap_locked_and_not_at_safepoint()                             \

  do {                                                                        \

    assert(Heap_lock->owned_by_self() &&                                      \

                                    !SafepointSynchronize::is_at_safepoint(), \

          heap_locking_asserts_err_msg("should be holding the Heap_lock and " \

                                       "should not be at a safepoint"));      \

  } while (0)

#define assert_heap_not_locked()                                              \

  do {                                                                        \

    assert(!Heap_lock->owned_by_self(),                                       \

        heap_locking_asserts_err_msg("should not be holding the Heap_lock")); \

  } while (0)

#define assert_heap_not_locked_and_not_at_safepoint()                         \

  do {                                                                        \

    assert(!Heap_lock->owned_by_self() &&                                     \

                                    !SafepointSynchronize::is_at_safepoint(), \

      heap_locking_asserts_err_msg("should not be holding the Heap_lock and " \

                                   "should not be at a safepoint"));          \

  } while (0)

#define assert_at_safepoint(_should_be_vm_thread_)                            \

  do {                                                                        \

    assert(SafepointSynchronize::is_at_safepoint() &&                         \

              ((_should_be_vm_thread_) == Thread::current()->is_VM_thread()), \

           heap_locking_asserts_err_msg("should be at a safepoint"));         \

  } while (0)

#define assert_not_at_safepoint()                                             \

  do {                                                                        \

    assert(!SafepointSynchronize::is_at_safepoint(),                          \

           heap_locking_asserts_err_msg("should not be at a safepoint"));     \

  } while (0)

protected:

  // The young region list.

  YoungList*  _young_list;

  // The current policy object for the collector.

  G1CollectorPolicy* _g1_policy;

  // This is the second level of trying to allocate a new region. If

  // new_region() didn't find a region on the free_list, this call will

  // check whether there's anything available on the

  // secondary_free_list and/or wait for more regions to appear on

  // that list, if _free_regions_coming is set.

  HeapRegion* new_region_try_secondary_free_list();

  // Try to allocate a single non-humongous HeapRegion sufficient for

  // an allocation of the given word_size. If do_expand is true,

  // attempt to expand the heap if necessary to satisfy the allocation

  // request.

  HeapRegion* new_region(size_t word_size, bool do_expand);

  // Attempt to satisfy a humongous allocation request of the given