/*

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

 *

 */

#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/g1RemSet.hpp"

#include "gc_implementation/g1/heapRegion.hpp"

#include "gc_implementation/parNew/parGCAllocBuffer.hpp"

#include "memory/barrierSet.hpp"

#include "memory/memRegion.hpp"

#include "memory/sharedHeap.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 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;

  // 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 %slocked, %sat a safepoint",                        \

          (__extra_message),                                                  \

          (!Heap_lock->owned_by_self()) ? "NOT " : "",                        \

          (!SafepointSynchronize::is_at_safepoint()) ? "NOT " : "")

#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()                                  \

  do {                                                                        \

    assert(Heap_lock->owned_by_self() ||                                      \

                                     SafepointSynchronize::is_at_safepoint(), \

           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()                                                 \

  do {                                                                        \

    assert(SafepointSynchronize::is_at_safepoint(),                           \

           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:

  // 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* humongous_obj_allocate(size_t word_size);

  // The following two methods, allocate_new_tlab() and

  // mem_allocate(), are the two main entry points from the runtime

  // into the G1's allocation routines. They have the following

  // assumptions:

  //

  // * They should both be called outside safepoints.

  //

  // * They should both be called without holding the Heap_lock.

  //

  // * All allocation requests for new TLABs should go to

  //   allocate_new_tlab().

  //

  // * All non-TLAB allocation requests should go to mem_allocate()

  //   and mem_allocate() should never be called with is_tlab == true.

  //

  // * If the GC locker is active we currently stall until we can

  //   allocate a new young region. This will be changed in the

  //   near future (see CR 6994056).

  //

  // * If either call cannot satisfy the allocation request using the

  //   current allocating region, they will try to get a new one. If

  //   this fails, they will attempt to do an evacuation pause and

  //   retry the allocation.

  //

  // * If all allocation attempts fail, even after trying to schedule

  //   an evacuation pause, allocate_new_tlab() will return NULL,

  //   whereas mem_allocate() will attempt a heap expansion and/or

  //   schedule a Full GC.

  //

  // * We do not allow humongous-sized TLABs. So, allocate_new_tlab

  //   should never be called with word_size being humongous. All

  //   humongous allocation requests should go to mem_allocate() which

  //   will satisfy them with a special path.

  virtual HeapWord* allocate_new_tlab(size_t word_size);

  virtual HeapWord* mem_allocate(size_t word_size,

                                 bool   is_noref,

                                 bool   is_tlab, /* expected to be false */

                                 bool*  gc_overhead_limit_was_exceeded);

  // The following methods, allocate_from_cur_allocation_region(),

  // attempt_allocation(), replace_cur_alloc_region_and_allocate(),

  // attempt_allocation_slow(), and attempt_allocation_humongous()

  // have very awkward pre- and post-conditions with respect to

  // locking:

  //

  // If they are called outside a safepoint they assume the caller

  // holds the Heap_lock when it calls them. However, on exit they

  // will release the Heap_lock if they return a non-NULL result, but

  // keep holding the Heap_lock if they return a NULL result. The

  // reason for this is that we need to dirty the cards that span

  // allocated blocks on young regions to avoid having to take the

  // slow path of the write barrier (for performance reasons we don't

  // update RSets for references whose source is a young region, so we

  // don't need to look at dirty cards on young regions). But, doing

  // this card dirtying while holding the Heap_lock can be a

  // scalability bottleneck, especially given that some allocation

  // requests might be of non-trivial size (and the larger the region

  // size is, the fewer allocations requests will be considered

  // humongous, as the humongous size limit is a fraction of the

  // region size). So, when one of these calls succeeds in allocating

  // a block it does the card dirtying after it releases the Heap_lock

  // which is why it will return without holding it.

  //

  // The above assymetry is the reason why locking / unlocking is done

  // explicitly (i.e., with Heap_lock->lock() and

  // Heap_lock->unlocked()) instead of using MutexLocker and

  // MutexUnlocker objects. The latter would ensure that the lock is

  // unlocked / re-locked at every possible exit out of the basic

  // block. However, we only want that action to happen in selected

  // places.

  //

  // Further, if the above methods are called during a safepoint, then

  // naturally there's no assumption about the Heap_lock being held or

  // there's no attempt to unlock it. The parameter at_safepoint

  // indicates whether the call is made during a safepoint or not (as

  // an optimization, to avoid reading the global flag with

  // SafepointSynchronize::is_at_safepoint()).

  //

  // The methods share these parameters:

  //

  // * word_size     : the size of the allocation request in words

  // * at_safepoint  : whether the call is done at a safepoint; this

  //                   also determines whether a GC is permitted

  //                   (at_safepoint == false) or not (at_safepoint == true)

  // * do_dirtying   : whether the method should dirty the allocated

  //                   block before returning

  //

  // They all return either the address of the block, if they

  // successfully manage to allocate it, or NULL.

  // It tries to satisfy an allocation request out of the current

  // allocating region, which is passed as a parameter. It assumes

  // that the caller has checked that the current allocating region is

  // not NULL. Given that the caller has to check the current

  // allocating region for at least NULL, it might as well pass it as

  // the first parameter so that the method doesn't have to read it

  // from the _cur_alloc_region field again.

  inline HeapWord* allocate_from_cur_alloc_region(HeapRegion* cur_alloc_region,

                                                  size_t word_size);

  // It attempts to allocate out of the current alloc region. If that

  // fails, it retires the current alloc region (if there is one),

  // tries to get a new one and retries the allocation.

  inline HeapWord* attempt_allocation(size_t word_size);

  // It assumes that the current alloc region has been retired and

  // tries to allocate a new one. If it's successful, it performs the

  // allocation out of the new current alloc region and updates

  // _cur_alloc_region. Normally, it would try to allocate a new

  // region if the young gen is not full, unless can_expand is true in

  // which case it would always try to allocate a new region.

  HeapWord* replace_cur_alloc_region_and_allocate(size_t word_size,

                                                  bool at_safepoint,

                                                  bool do_dirtying,

                                                  bool can_expand);