/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* 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.
*
*/
#include "gc_implementation/g1/heapRegionSets.hpp"
#include "utilities/taskqueue.hpp"
class G1CollectedHeap;
class CMTask;
// Closure used by CM during concurrent reference discovery
// and reference processing (during remarking) to determine
// if a particular object is alive. It is primarily used
// to determine if referents of discovered reference objects
// are alive. An instance is also embedded into the
// reference processor as the _is_alive_non_header field
public:
}
};
// A generic CM bit map. This is essentially a wrapper around the BitMap
// class, with one bit per (1<<_shifter) HeapWords.
protected:
public:
// constructor
enum { do_yield = true };
// inquiries
// the following is one past the last word in space
// read marks
"outside underlying space?");
}
// iteration
// Return the address corresponding to the next marked bit at or after
// "addr", and before "limit", if "limit" is non-NULL. If there is no
// such bit, returns "limit" if that is non-NULL, or else "endWord()".
// Return the address corresponding to the next unmarked bit at or after
// "addr", and before "limit", if "limit" is non-NULL. If there is no
// such bit, returns "limit" if that is non-NULL, or else "endWord()".
// conversion utilities
// XXX Fix these so that offsets are size_t's...
}
}
}
// debugging
};
public:
// constructor
// write marks
"outside underlying space?");
}
"outside underlying space?");
}
"outside underlying space?");
}
"outside underlying space?");
}
void clearAll();
// Starting at the bit corresponding to "addr" (inclusive), find the next
// "1" bit, if any. This bit starts some run of consecutive "1"'s; find
// the end of this run (stopping at "end_addr"). Return the MemRegion
// covering from the start of the region corresponding to the first bit
// of the run to the end of the region corresponding to the last bit of
// the run. If there is no "1" bit at or after "addr", return an empty
// MemRegion.
};
// Represents a marking stack used by the CM collector.
// Ideally this should be GrowableArray<> just like MSC's marking stack(s).
bool _overflow;
DEBUG_ONLY(bool _drain_in_progress;)
public:
~CMMarkStack();
if (!isEmpty()) {
}
return NULL;
}
// If overflow happens, don't do the push, and record the overflow.
// *Requires* that "ptr" is already marked.
if (isFull()) {
// Record overflow.
_overflow = true;
return;
} else {
}
}
// Non-block impl. Note: concurrency is allowed only with other
// "par_push" operations, not with "pop" or "drain". We would need
// parallel versions of them if such concurrency was desired.
// Pushes the first "n" elements of "ptr_arr" on the stack.
// Non-block impl. Note: concurrency is allowed only with other
// "par_adjoin_arr" or "push" operations, not with "pop" or "drain".
// Pushes the first "n" elements of "ptr_arr" on the stack.
// Locking impl: concurrency is allowed only with
// locking strategy.
// If returns false, the array was empty. Otherwise, removes up to "max"
// elements from the stack, and transfers them to "ptr_arr" in an
// unspecified order. The actual number transferred is given in "n" ("n
// == 0" is deliberately redundant with the return value.) Locking impl:
// operations, which use the same locking strategy.
// Drain the mark stack, applying the given closure to all fields of
// objects on the stack. (That is, continue until the stack is empty,
// even if closure applications add entries to the stack.) The "bm"
// argument, if non-null, may be used to verify that only marked objects
// are on the mark stack. If "yield_after" is "true", then the
// concurrent marker performing the drain offers to yield after
// processing each object. If a yield occurs, stops the drain operation
// and returns false. Otherwise, returns true.
template<class OopClosureClass>
// Record the current index.
void note_start_of_gc();
// Make sure that we have not added any entries to the stack during GC.
void note_end_of_gc();
// iterate over the oops in the mark stack, up to the bound recorded via
// the call above.
void oops_do(OopClosure* f);
};
private:
#ifndef PRODUCT
bool _force;
#endif // !defined(PRODUCT)
public:
bool should_force() PRODUCT_RETURN_( return false; );
};
// this will enable a variety of different statistics per GC task
#define _MARKING_STATS_ 0
// this will enable the higher verbose levels
#define _MARKING_VERBOSE_ 0
#if _MARKING_STATS_
do { \
statement ; \
} while (0)
#else // _MARKING_STATS_
do { \
} while (0)
#endif // _MARKING_STATS_
typedef enum {
class YoungList;
// Root Regions are regions that are not empty at the beginning of a
// marking cycle and which we might collect during an evacuation pause
// while the cycle is active. Given that, during evacuation pauses, we
// do not copy objects that are explicitly marked, what we have to do
// for the root regions is to scan them and mark all objects reachable
// from them. According to the SATB assumptions, we only need to visit
// each object once during marking. So, as long as we finish this scan
// before the next evacuation pause, we can copy the objects from the
// root regions without having to mark them or do anything else to them.
//
// Currently, we only support root region scanning once (at the start
// of the marking cycle) and the root regions are all the survivor
// regions populated during the initial-mark pause.
private:
volatile bool _scan_in_progress;
volatile bool _should_abort;
public:
// We actually do most of the initialization in this method.
// Reset the claiming / scanning of the root regions.
void prepare_for_scan();
// Forces get_next() to return NULL so that the iteration aborts early.
// Return true if the CM thread are actively scanning root regions,
// false otherwise.
// Claim the next root region to scan atomically, or return NULL if
// all have been claimed.
HeapRegion* claim_next();
// Flag that we're done with root region scanning and notify anyone
// who's waiting on it. If aborted is false, assume that all regions
// have been claimed.
void scan_finished();
// If CM threads are still scanning root regions, wait until they
// are done. Return true if we had to wait, false otherwise.
bool wait_until_scan_finished();
};
class ConcurrentMarkThread;
friend class ConcurrentMarkThread;
friend class CMTask;
friend class CMBitMapClosure;
friend class CMGlobalObjectClosure;
friend class CMRemarkTask;
friend class CMConcurrentMarkingTask;
friend class G1ParNoteEndTask;
friend class CalcLiveObjectsClosure;
friend class G1CMRefProcTaskProxy;
friend class G1CMRefProcTaskExecutor;
friend class G1CMKeepAliveAndDrainClosure;
friend class G1CMDrainMarkingStackClosure;
protected:
// threads we're use
// threads we'll ever use
// respect to the work we just did, to
// meet the marking overhead goal
// a single task
// same as the two above, but for the cleanup task
double _cleanup_sleep_factor;
double _cleanup_task_overhead;
// Concurrent marking support structures
// Heap bounds
// Root region tracking and claiming.
// For gray objects
// always points to the end of the
// last claimed region
// marking tasks
// Two sync barriers that are used to synchronise tasks when an
// overflow occurs. The algorithm is the following. All tasks enter
// the first one to ensure that they have all stopped manipulating
// the global data structures. After they exit it, they re-initialise
// their data structures and task 0 re-initialises the global data
// structures. Then, they enter the second sync barrier. This
// ensure, that no task starts doing work before all data
// structures (local and global) have been re-initialised. When they
// exit it, they are free to start working again.
// this is set by any task, when an overflow on the global data
// structures is detected.
volatile bool _has_overflown;
// true: marking is concurrent, false: we're in remark
volatile bool _concurrent;
// set at the end of a Full GC so that marking aborts
volatile bool _has_aborted;
// used when remark aborts due to an overflow to indicate that
// another concurrent marking phase should start
volatile bool _restart_for_overflow;
// This is true from the very start of concurrent marking until the
// point when all the tasks complete their work. It is really used
// to determine the points between the end of concurrent marking and
// time of remark.
volatile bool _concurrent_marking_in_progress;
// verbose level
// All of these times are in ms.
double _total_counting_time;
double _total_rs_scrub_time;
void weakRefsWork(bool clear_all_soft_refs);
void swapMarkBitMaps();
// It resets the global marking data structures, as well as the
// task local ones; should be called during initial mark.
void reset();
// Resets all the marking data structures. Called when we have to restart
// marking or when marking completes (via set_non_marking_state below).
void reset_marking_state(bool clear_overflow = true);
// We do this after we're done with marking so that the marking data
// structures are initialised to a sensible and predictable state.
void set_non_marking_state();
// Called to indicate how many threads are currently active.
// It should be called to indicate which phase we're in (concurrent
// mark or remark) and how many threads are currently active.
// prints all gathered CM-related statistics
void print_stats();
bool cleanup_list_is_empty() {
return _cleanup_list.is_empty();
}
// accessor methods
bool use_parallel_marking_threads() const {
max_parallel_marking_threads(), "sanity");
parallel_marking_threads() > 0,
"parallel workers not set up correctly");
return _parallel_workers != NULL;
}
// It claims the next available region to be scanned by a marking
// task. It might return NULL if the next region is empty or we have
// run out of regions. In the latter case, out_of_regions()
// determines whether we've really run out of regions or the task
// should call claim_region() again. This might seem a bit
// awkward. Originally, the code was written so that claim_region()
// either successfully returned with a non-empty region or there
// were no more regions to be claimed. The problem with this was
// that, in certain circumstances, it iterated over large chunks of
// the heap finding only empty regions and, while it was working, it
// was preventing the calling task to call its regular clock
// method. So, this way, each task will spend very little time in
// claim_region() and is allowed to call the regular clock method
// frequently.
// It determines whether we've run out of regions to scan.
// Returns the task with the given id
"task id not within active bounds");
}
// Returns the task queue with the given id
"task queue id not within active bounds");
}
// Returns the task queue set
// Access / manipulation of the overflow flag which is set to
// indicate that the global stack has overflown
// Methods to enter the two overflow sync barriers
void enter_first_sync_barrier(int task_num);
void enter_second_sync_barrier(int task_num);
return &_force_overflow_conc;
}
return &_force_overflow_stw;
}
if (concurrent()) {
return force_overflow_conc();
} else {
return force_overflow_stw();
}
}
// Live Data Counting data structures...
// These data structures are initialized at the start of
// marking. They are written to while marking is active.
// They are aggregated during remark; the aggregated values
// are then used to populate the _region_bm, _card_bm, and
// the total live bytes, which are then subsequently updated
// during cleanup.
// An array of bitmaps (one bit map per task). Each bitmap
// is used to record the cards spanned by the live objects
// Used to record the number of marked live bytes
// (for each region, by worker thread).
// Card index of the bottom of the G1 heap. Used for biasing indices into
// the card bitmaps.
public:
// Manipulation of the global mark stack.
// Notice that the first mark_stack_push is CAS-based, whereas the
// two below are Mutex-based. This is OK since the first one is only
// called during evacuation pauses and doesn't compete with the
// other two (which are called by the marking tasks during
// concurrent marking or remark).
_markStack.par_push(p);
if (_markStack.overflow()) {
return false;
}
return true;
}
if (_markStack.overflow()) {
return false;
}
return true;
}
}
bool concurrent_marking_in_progress() {
return _concurrent_marking_in_progress;
}
void set_concurrent_marking_in_progress() {
_concurrent_marking_in_progress = true;
}
void clear_concurrent_marking_in_progress() {
_concurrent_marking_in_progress = false;
}
_accum_task_vtime[i] += vtime;
}
double all_task_accum_vtime() {
for (int i = 0; i < (int)_max_task_num; ++i)
ret += _accum_task_vtime[i];
return ret;
}
// Attempts to steal an object from the task queues of other tasks
}
~ConcurrentMark();
// Returns the number of GC threads to be used in a concurrent
// phase based on the number of GC threads being used in a STW
// phase.
// Calculates the number of GC threads to be used in a concurrent phase.
// The following three are interaction between CM and
// G1CollectedHeap
// This notifies CM that a root during initial-mark needs to be
// grayed. It is MT-safe. word_size is the size of the object in
// words. It is passed explicitly as sometimes we cannot calculate
// it from the given object because it might be in an inconsistent
// state (e.g., in to-space and being copied). So the caller is
// responsible for dealing with this issue (e.g., get the size from
// the from-space image when the to-space image might be
// inconsistent) and always passing the size. hr is the region that
// contains the object and it's passed optionally from callers who
// might already have it (no point in recalculating it).
// It iterates over the heap and for each object it comes across it
// will dump the contents of its reference fields, as well as
// liveness information for the object and its referents. The dump
// will be written to a file with the following name:
// G1PrintReachableBaseFile + "." + str.
// vo decides whether the prev (vo == UsePrevMarking), the next
// (vo == UseNextMarking) marking information, or the mark word
// (vo == UseMarkWord) will be used to determine the liveness of
// each object / referent.
// If all is true, all objects in the heap will be dumped, otherwise
// only the live ones. In the dump the following symbols / breviations
// are used:
// M : an explicitly live object (its bitmap bit is set)
// > : an implicitly live object (over tams)
// O : an object outside the G1 heap (typically: in the perm gen)
// NOT : a reference field whose referent is not live
// AND MARKED : indicates that an object is both explicitly and
// implicitly live (it should be one or the other, not both)
void print_reachable(const char* str,
// Clear the next marking bitmap (will be called concurrently).
void clearNextBitmap();
// These two do the work that needs to be done before and after the
// initial root checkpoint. Since this checkpoint can be done at two
// different points (i.e. an explicit pause or piggy-backed on a
// young collection), then it's nice to be able to easily share the
// the post method. TP
void checkpointRootsInitialPre();
void checkpointRootsInitialPost();
// Scan all the root regions and mark everything reachable from
// them.
void scanRootRegions();
// Scan a single root region and mark everything reachable from it.
// Do concurrent phase of marking, to a tentative transitive closure.
void markFromRoots();
void checkpointRootsFinal(bool clear_all_soft_refs);
void checkpointRootsFinalWork();
void cleanup();
void completeCleanup();
// Mark in the previous bitmap. NB: this is usually read-only, so use
// this carefully!
// Clears marks for all objects in the given range, for the prev,
// next, or both bitmaps. NB: the previous bitmap is usually
// read-only, so use this carefully!
// Notify data structures that a GC has started.
void note_start_of_gc() {
}
// Notify data structures that a GC is finished.
void note_end_of_gc() {
}
// Verify that there are no CSet oops on the stacks (taskqueues /
// global mark stack), enqueued SATB buffers, per-thread SATB
// buffers, and fingers (global / per-task). The boolean parameters
// decide which of the above data structures to verify. If marking
// is not in progress, it's a no-op.
void verify_no_cset_oops(bool verify_stacks,
bool verify_enqueued_buffers,
bool verify_thread_buffers,
// It is called at the end of an evacuation pause during marking so
// that CM is notified of where the new end of the heap is. It
// doesn't do anything if concurrent_marking_in_progress() is false,
// unless the force parameter is true.
void update_g1_committed(bool force = false);
}
inline bool not_yet_marked(oop p) const;
// XXX Debug code
bool containing_card_is_marked(void* p);
}
inline bool should_yield();
// Called to abort the marking cycle after a Full GC takes palce.
void abort();
NOT_PRODUCT(void print_finger();)
void print_summary_info();
// The following indicate whether a given verbose level has been
// set. Notice that anything above stats is conditional to
// _MARKING_VERBOSE_ having been set to 1
bool verbose_stats() {
return _verbose_level >= stats_verbose;
}
bool verbose_low() {
}
bool verbose_medium() {
}
bool verbose_high() {
}
// Liveness counting
// Utility routine to set an exclusive range of cards on the given
// card liveness bitmap
bool is_par);
// Returns the card number of the bottom of the G1 heap.
// Used in biasing indices into accounting card bitmaps.
return _heap_bottom_card_num;
}
// Returns the card bitmap for a given task or worker id.
return task_card_bm;
}
// Returns the array containing the marked bytes for each region,
// for the given worker or task id.
return marked_bytes_array;
}
// Returns the index in the liveness accounting card table bitmap
// for the given address
// Counts the size of the given memory region in the the given
// marked_bytes array slot for the given HeapRegion.
// Sets the bits in the given card bitmap that are associated with the
// cards that are spanned by the memory region.
// data structures for the given worker id.
// data structures for the given worker id.
// data structures.
// structures for the given worker id.
// Attempts to mark the given object and, if successful, counts
// Attempts to mark the given object and, if successful, counts
// given worker id.
// Attempts to mark the given object and, if successful, counts
// given worker id.
// Similar to the above routine but we don't know the heap region that
// Similar to the above routine but there are times when we cannot
// safely calculate the size of obj due to races and we, therefore,
// pass the size in as a parameter. It is the caller's reponsibility
// to ensure that the size passed in for obj is valid.
// Unconditionally mark the given object, and unconditinally count
// the object in the counting structures for worker id 0.
// Should *not* be called from parallel code.
// Similar to the above routine but we don't know the heap region that
// Should *not* be called from parallel code.
protected:
// Clear all the per-task bitmaps and arrays used to store the
// counting data.
void clear_all_count_data();
// that was constructed while marking. Also sets
// the amount of marked bytes for each region and
// the top at concurrent mark count.
void aggregate_count_data();
// Verification routine
void verify_count_data();
};
// A class representing a marking task.
private:
enum PrivateConstants {
// the regular clock call is called once the scanned words reaches
// this limit
// the regular clock call is called once the number of visited
// references reaches this limit
// initial value for the hash seed, used in the work stealing code
// how many entries will be transferred between global stack and
// local queues
};
int _task_id;
// the task queue of this task
private:
// the task queue set---needed for stealing
// indicates whether the task has been claimed---this is only for
// debugging purposes
bool _claimed;
// number of calls to this task
int _calls;
// when the virtual timer reaches this time, the marking step should
// exit
double _time_target_ms;
// the start time of the current marking step
double _start_time_ms;
// the oop closure used for iterations over oops
// the region this task is scanning, NULL if we're not scanning any
// the local finger of this task, NULL if we're not scanning a region
// limit of the region this task is scanning, NULL if we're not scanning one
// the number of words this task has scanned
// When _words_scanned reaches this limit, the regular clock is
// called. Notice that this might be decreased under certain
// circumstances (i.e. when we believe that we did an expensive
// operation).
// the initial value of _words_scanned_limit (i.e. what it was
// before it was decreased).
// the number of references this task has visited
// When _refs_reached reaches this limit, the regular clock is
// called. Notice this this might be decreased under certain
// circumstances (i.e. when we believe that we did an expensive
// operation).
// the initial value of _refs_reached_limit (i.e. what it was before
// it was decreased).
// used by the work stealing stuff
int _hash_seed;
// if this is true, then the task has aborted for some reason
bool _has_aborted;
// set when the task aborts because it has met its time quota
bool _has_timed_out;
// true when we're draining SATB buffers; this avoids the task
// aborting due to SATB buffers being available (as we're already
// dealing with them)
bool _draining_satb_buffers;
// number sequence of past step times
// elapsed time of this task
double _elapsed_time_ms;
// termination time of this task
double _termination_time_ms;
// when this task got into the termination protocol
double _termination_start_time_ms;
// true when the task is during a concurrent phase, false when it is
// in the remark phase (so, in the latter case, we do not have to
// check all the things that we have to check during the concurrent
// phase, i.e. SATB buffer availability...)
bool _concurrent;
// Counting data structures. Embedding the task's marked_bytes_array
// and card bitmap into the actual task saves having to go through
// the ConcurrentMark object.
// LOTS of statistics related with this task
#if _MARKING_STATS_
double _interval_start_time_ms;
int _aborted;
int _aborted_overflow;
int _aborted_cm_aborted;
int _aborted_yield;
int _aborted_timed_out;
int _aborted_satb;
int _aborted_termination;
int _steal_attempts;
int _steals;
int _local_pushes;
int _local_pops;
int _local_max_size;
int _objs_scanned;
int _global_pushes;
int _global_pops;
int _global_max_size;
int _global_transfers_to;
int _regions_claimed;
#endif // _MARKING_STATS_
// it updates the local fields after this task has claimed
// a new region to scan
// it brings up-to-date the limit of the region
void update_region_limit();
// called when either the words scanned or the refs visited limit
// has been reached
void reached_limit();
// recalculates the words scanned and refs visited limits
void recalculate_limits();
// decreases the words scanned and refs visited limits when we reach
// an expensive operation
void decrease_limits();
// it checks whether the words scanned or refs visited reached their
// respective limit and calls reached_limit() if they have
void check_limits() {
if (_words_scanned >= _words_scanned_limit ||
}
}
// this is supposed to be called regularly during a marking step as
// it checks a bunch of conditions that might cause the marking step
// to abort
void regular_clock_call();
public:
// It resets the task; it should be called right at the beginning of
// a marking phase.
// it clears all the fields that correspond to a claimed region.
void clear_region_fields();
// The main method of this class which performs a marking step
// trying not to exceed the given duration. However, it might exit
// prematurely, according to some conditions (i.e. SATB buffers are
// available for processing).
void do_marking_step(double target_ms,
bool do_termination,
bool is_serial);
// These two calls start and stop the timer
void record_start_time() {
}
void record_end_time() {
}
// returns the task ID
// From TerminatorTerminator. It determines whether this task should
// exit the termination protocol after it's entered it.
virtual bool should_exit_termination();
// Resets the local region fields after a task has finished scanning a
// region; or when they have become stale as a result of the region
// being evacuated.
void giveup_current_region();
// It grays the object by marking it and, if necessary, pushing it
// on the local queue
// It scans an object and visits its children.
// It pushes an object on the local queue.
void move_entries_to_global_stack();
void get_entries_from_global_stack();
// It pops and scans objects from the local queue. If partially is
// true, then it stops when the queue size is of a given limit. If
// partially is false, then it stops when the queue is empty.
void drain_local_queue(bool partially);
// It moves entries from the global stack to the local queue and
// drains the local queue. If partially is true, then it stops when
// both the global stack and the local queue reach a given size. If
// partially if false, it tries to empty them totally.
void drain_global_stack(bool partially);
// It keeps picking SATB buffers and processing them until no SATB
// buffers are available.
void drain_satb_buffers();
// moves the local finger to a new location
}
// it prints statistics associated with this task
void print_stats();
#if _MARKING_STATS_
#endif // _MARKING_STATS_
};
// Class that's used to to print out per-region liveness
// information. It's currently used at the end of marking and also
// after we sort the old regions at the end of the cleanup operation.
private:
// Accumulators for these values.
// These are set up when we come across a "stars humongous" region
// (as this is where most of this information is stored, not in the
// subsequent "continues humongous" regions). After that, for every
// region in a given humongous region series we deduce the right
// values for it by simply subtracting the appropriate amount from
// these fields. All these values should reach 0 after we've visited
// the last region in the series.
if (total == 0) {
return 0.0;
} else {
}
}
return (double) val / (double) M;
}
// See the .cpp file.
public:
// The header and footer are printed in the constructor and
// destructor respectively.
virtual bool doHeapRegion(HeapRegion* r);
};
#endif // SHARE_VM_GC_IMPLEMENTATION_G1_CONCURRENTMARK_HPP