Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

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

  *

  */

 #include "precompiled.hpp"

 #include "classfile/symbolTable.hpp"

 #include "gc_implementation/g1/concurrentMark.inline.hpp"

 #include "gc_implementation/g1/concurrentMarkThread.inline.hpp"

 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"

 #include "gc_implementation/g1/g1CollectorPolicy.hpp"

 #include "gc_implementation/g1/g1ErgoVerbose.hpp"

 #include "gc_implementation/g1/g1Log.hpp"

 #include "gc_implementation/g1/g1OopClosures.inline.hpp"

 #include "gc_implementation/g1/g1RemSet.hpp"

 #include "gc_implementation/g1/heapRegion.inline.hpp"

 #include "gc_implementation/g1/heapRegionRemSet.hpp"

 #include "gc_implementation/g1/heapRegionSeq.inline.hpp"

 #include "gc_implementation/shared/vmGCOperations.hpp"

 #include "memory/genOopClosures.inline.hpp"

 #include "memory/referencePolicy.hpp"

 #include "memory/resourceArea.hpp"

 #include "oops/oop.inline.hpp"

 #include "runtime/handles.inline.hpp"

 #include "runtime/java.hpp"

 // Concurrent marking bit map wrapper

 CMBitMapRO::CMBitMapRO(ReservedSpace rs, int shifter) :

   _bm((uintptr_t*)NULL,0),

   _shifter(shifter) {

   _bmStartWord = (HeapWord*)(rs.base());

   _bmWordSize  = rs.size()/HeapWordSize;    // rs.size() is in bytes

   ReservedSpace brs(ReservedSpace::allocation_align_size_up(

                      (_bmWordSize >> (_shifter + LogBitsPerByte)) + 1));

   guarantee(brs.is_reserved(), "couldn't allocate concurrent marking bit map");

   // For now we'll just commit all of the bit map up fromt.

   // Later on we'll try to be more parsimonious with swap.

   guarantee(_virtual_space.initialize(brs, brs.size()),

             "couldn't reseve backing store for concurrent marking bit map");

   assert(_virtual_space.committed_size() == brs.size(),

          "didn't reserve backing store for all of concurrent marking bit map?");

   _bm.set_map((uintptr_t*)_virtual_space.low());

   assert(_virtual_space.committed_size() << (_shifter + LogBitsPerByte) >=

          _bmWordSize, "inconsistency in bit map sizing");

   _bm.set_size(_bmWordSize >> _shifter);

 }

 HeapWord* CMBitMapRO::getNextMarkedWordAddress(HeapWord* addr,

                                                HeapWord* limit) const {

   // First we must round addr *up* to a possible object boundary.

   addr = (HeapWord*)align_size_up((intptr_t)addr,

                                   HeapWordSize << _shifter);

   size_t addrOffset = heapWordToOffset(addr);

   if (limit == NULL) {

     limit = _bmStartWord + _bmWordSize;

   }

   size_t limitOffset = heapWordToOffset(limit);

   size_t nextOffset = _bm.get_next_one_offset(addrOffset, limitOffset);

   HeapWord* nextAddr = offsetToHeapWord(nextOffset);

   assert(nextAddr >= addr, "get_next_one postcondition");

   assert(nextAddr == limit || isMarked(nextAddr),

          "get_next_one postcondition");

   return nextAddr;

 }

 HeapWord* CMBitMapRO::getNextUnmarkedWordAddress(HeapWord* addr,

                                                  HeapWord* limit) const {

   size_t addrOffset = heapWordToOffset(addr);

   if (limit == NULL) {

     limit = _bmStartWord + _bmWordSize;

   }

   size_t limitOffset = heapWordToOffset(limit);

   size_t nextOffset = _bm.get_next_zero_offset(addrOffset, limitOffset);

   HeapWord* nextAddr = offsetToHeapWord(nextOffset);

   assert(nextAddr >= addr, "get_next_one postcondition");

   assert(nextAddr == limit || !isMarked(nextAddr),

          "get_next_one postcondition");

   return nextAddr;

 }

 int CMBitMapRO::heapWordDiffToOffsetDiff(size_t diff) const {

   assert((diff & ((1 << _shifter) - 1)) == 0, "argument check");

   return (int) (diff >> _shifter);

 }

 #ifndef PRODUCT

 bool CMBitMapRO::covers(ReservedSpace rs) const {

   // assert(_bm.map() == _virtual_space.low(), "map inconsistency");

   assert(((size_t)_bm.size() * (size_t)(1 << _shifter)) == _bmWordSize,

          "size inconsistency");

   return _bmStartWord == (HeapWord*)(rs.base()) &&

          _bmWordSize  == rs.size()>>LogHeapWordSize;

 }

 #endif

 void CMBitMap::clearAll() {

   _bm.clear();

   return;

 }

 void CMBitMap::markRange(MemRegion mr) {

   mr.intersection(MemRegion(_bmStartWord, _bmWordSize));

   assert(!mr.is_empty(), "unexpected empty region");

   assert((offsetToHeapWord(heapWordToOffset(mr.end())) ==

           ((HeapWord *) mr.end())),

          "markRange memory region end is not card aligned");

   // convert address range into offset range

   _bm.at_put_range(heapWordToOffset(mr.start()),

                    heapWordToOffset(mr.end()), true);

 }

 void CMBitMap::clearRange(MemRegion mr) {

   mr.intersection(MemRegion(_bmStartWord, _bmWordSize));

   assert(!mr.is_empty(), "unexpected empty region");

   // convert address range into offset range

   _bm.at_put_range(heapWordToOffset(mr.start()),

                    heapWordToOffset(mr.end()), false);

 }

 MemRegion CMBitMap::getAndClearMarkedRegion(HeapWord* addr,

                                             HeapWord* end_addr) {

   HeapWord* start = getNextMarkedWordAddress(addr);

   start = MIN2(start, end_addr);

   HeapWord* end   = getNextUnmarkedWordAddress(start);

   end = MIN2(end, end_addr);

   assert(start <= end, "Consistency check");

   MemRegion mr(start, end);

   if (!mr.is_empty()) {

     clearRange(mr);

   }

   return mr;

 }

 CMMarkStack::CMMarkStack(ConcurrentMark* cm) :

   _base(NULL), _cm(cm)

 #ifdef ASSERT

   , _drain_in_progress(false)

   , _drain_in_progress_yields(false)

 #endif

 {}

 void CMMarkStack::allocate(size_t size) {

   _base = NEW_C_HEAP_ARRAY(oop, size);

   if (_base == NULL) {

     vm_exit_during_initialization("Failed to allocate CM region mark stack");

   }

   _index = 0;

   _capacity = (jint) size;

   _saved_index = -1;

   NOT_PRODUCT(_max_depth = 0);

 }

 CMMarkStack::~CMMarkStack() {

   if (_base != NULL) {

     FREE_C_HEAP_ARRAY(oop, _base);

   }

 }

 void CMMarkStack::par_push(oop ptr) {

   while (true) {

     if (isFull()) {

       _overflow = true;

       return;

     }

     // Otherwise...

     jint index = _index;

     jint next_index = index+1;

     jint res = Atomic::cmpxchg(next_index, &_index, index);

     if (res == index) {

       _base[index] = ptr;

       // Note that we don't maintain this atomically.  We could, but it

       // doesn't seem necessary.

       NOT_PRODUCT(_max_depth = MAX2(_max_depth, next_index));

       return;

     }

     // Otherwise, we need to try again.

   }

 }

 void CMMarkStack::par_adjoin_arr(oop* ptr_arr, int n) {

   while (true) {

     if (isFull()) {

       _overflow = true;

       return;

     }

     // Otherwise...

     jint index = _index;

     jint next_index = index + n;

     if (next_index > _capacity) {

       _overflow = true;

       return;

     }

     jint res = Atomic::cmpxchg(next_index, &_index, index);

     if (res == index) {

       for (int i = 0; i < n; i++) {

         int ind = index + i;

         assert(ind < _capacity, "By overflow test above.");

         _base[ind] = ptr_arr[i];

       }

       NOT_PRODUCT(_max_depth = MAX2(_max_depth, next_index));

       return;

     }

     // Otherwise, we need to try again.

   }

 }

 void CMMarkStack::par_push_arr(oop* ptr_arr, int n) {

   MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

   jint start = _index;

   jint next_index = start + n;

   if (next_index > _capacity) {

     _overflow = true;

     return;

   }

   // Otherwise.

   _index = next_index;

   for (int i = 0; i < n; i++) {

     int ind = start + i;

     assert(ind < _capacity, "By overflow test above.");

     _base[ind] = ptr_arr[i];

   }

 }

 bool CMMarkStack::par_pop_arr(oop* ptr_arr, int max, int* n) {

   MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

   jint index = _index;

   if (index == 0) {

     *n = 0;

     return false;

   } else {

     int k = MIN2(max, index);

     jint new_ind = index - k;

     for (int j = 0; j < k; j++) {

       ptr_arr[j] = _base[new_ind + j];

     }

     _index = new_ind;

     *n = k;

     return true;

   }

 }

 template<class OopClosureClass>

 bool CMMarkStack::drain(OopClosureClass* cl, CMBitMap* bm, bool yield_after) {

   assert(!_drain_in_progress || !_drain_in_progress_yields || yield_after

          || SafepointSynchronize::is_at_safepoint(),

          "Drain recursion must be yield-safe.");

   bool res = true;

   debug_only(_drain_in_progress = true);

   debug_only(_drain_in_progress_yields = yield_after);

   while (!isEmpty()) {

     oop newOop = pop();

     assert(G1CollectedHeap::heap()->is_in_reserved(newOop), "Bad pop");

     assert(newOop->is_oop(), "Expected an oop");

     assert(bm == NULL || bm->isMarked((HeapWord*)newOop),

            "only grey objects on this stack");

     newOop->oop_iterate(cl);

     if (yield_after && _cm->do_yield_check()) {

       res = false;

       break;

     }

   }

   debug_only(_drain_in_progress = false);

   return res;

 }

 void CMMarkStack::note_start_of_gc() {

   assert(_saved_index == -1,

          "note_start_of_gc()/end_of_gc() bracketed incorrectly");

   _saved_index = _index;

 }

 void CMMarkStack::note_end_of_gc() {

   // This is intentionally a guarantee, instead of an assert. If we

   // accidentally add something to the mark stack during GC, it

   // will be a correctness issue so it's better if we crash. we'll

   // only check this once per GC anyway, so it won't be a performance

   // issue in any way.

   guarantee(_saved_index == _index,

             err_msg("saved index: %d index: %d", _saved_index, _index));

   _saved_index = -1;

 }

 void CMMarkStack::oops_do(OopClosure* f) {

   assert(_saved_index == _index,

          err_msg("saved index: %d index: %d", _saved_index, _index));

   for (int i = 0; i < _index; i += 1) {

     f->do_oop(&_base[i]);

   }

 }

 bool ConcurrentMark::not_yet_marked(oop obj) const {

   return (_g1h->is_obj_ill(obj)

           || (_g1h->is_in_permanent(obj)

               && !nextMarkBitMap()->isMarked((HeapWord*)obj)));

 }

 CMRootRegions::CMRootRegions() :

   _young_list(NULL), _cm(NULL), _scan_in_progress(false),

   _should_abort(false),  _next_survivor(NULL) { }

 void CMRootRegions::init(G1CollectedHeap* g1h, ConcurrentMark* cm) {

   _young_list = g1h->young_list();

   _cm = cm;

 }

 void CMRootRegions::prepare_for_scan() {

   assert(!scan_in_progress(), "pre-condition");

   // Currently, only survivors can be root regions.

   assert(_next_survivor == NULL, "pre-condition");

   _next_survivor = _young_list->first_survivor_region();

   _scan_in_progress = (_next_survivor != NULL);

   _should_abort = false;

 }

 HeapRegion* CMRootRegions::claim_next() {

   if (_should_abort) {

     // If someone has set the should_abort flag, we return NULL to

     // force the caller to bail out of their loop.

     return NULL;

   }

   // Currently, only survivors can be root regions.

   HeapRegion* res = _next_survivor;

   if (res != NULL) {

     MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);

     // Read it again in case it changed while we were waiting for the lock.

     res = _next_survivor;

     if (res != NULL) {

       if (res == _young_list->last_survivor_region()) {

         // We just claimed the last survivor so store NULL to indicate

         // that we're done.

         _next_survivor = NULL;

       } else {

         _next_survivor = res->get_next_young_region();

       }

     } else {

       // Someone else claimed the last survivor while we were trying

       // to take the lock so nothing else to do.

     }

   }

   assert(res == NULL || res->is_survivor(), "post-condition");

   return res;

 }

 void CMRootRegions::scan_finished() {

   assert(scan_in_progress(), "pre-condition");

   // Currently, only survivors can be root regions.

   if (!_should_abort) {

     assert(_next_survivor == NULL, "we should have claimed all survivors");

   }

   _next_survivor = NULL;

   {

     MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);

     _scan_in_progress = false;

     RootRegionScan_lock->notify_all();

   }

 }

 bool CMRootRegions::wait_until_scan_finished() {

   if (!scan_in_progress()) return false;

   {

     MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);

     while (scan_in_progress()) {

       RootRegionScan_lock->wait(Mutex::_no_safepoint_check_flag);

     }

   }

   return true;

 }

 #ifdef _MSC_VER // the use of 'this' below gets a warning, make it go away

 #pragma warning( disable:4355 ) // 'this' : used in base member initializer list

 #endif // _MSC_VER

 uint ConcurrentMark::scale_parallel_threads(uint n_par_threads) {

   return MAX2((n_par_threads + 2) / 4, 1U);

 }

 ConcurrentMark::ConcurrentMark(ReservedSpace rs, uint max_regions) :

   _markBitMap1(rs, MinObjAlignment - 1),

   _markBitMap2(rs, MinObjAlignment - 1),

   _parallel_marking_threads(0),

   _max_parallel_marking_threads(0),

   _sleep_factor(0.0),

   _marking_task_overhead(1.0),

   _cleanup_sleep_factor(0.0),

   _cleanup_task_overhead(1.0),

   _cleanup_list("Cleanup List"),

   _region_bm((BitMap::idx_t) max_regions, false /* in_resource_area*/),

   _card_bm((rs.size() + CardTableModRefBS::card_size - 1) >>

            CardTableModRefBS::card_shift,

            false /* in_resource_area*/),

   _prevMarkBitMap(&_markBitMap1),

   _nextMarkBitMap(&_markBitMap2),

   _markStack(this),

   // _finger set in set_non_marking_state

   _max_task_num(MAX2((uint)ParallelGCThreads, 1U)),

   // _active_tasks set in set_non_marking_state

   // _tasks set inside the constructor

   _task_queues(new CMTaskQueueSet((int) _max_task_num)),

   _terminator(ParallelTaskTerminator((int) _max_task_num, _task_queues)),

   _has_overflown(false),

   _concurrent(false),

   _has_aborted(false),

   _restart_for_overflow(false),

   _concurrent_marking_in_progress(false),

   // _verbose_level set below

   _init_times(),

   _remark_times(), _remark_mark_times(), _remark_weak_ref_times(),

   _cleanup_times(),

   _total_counting_time(0.0),

   _total_rs_scrub_time(0.0),

   _parallel_workers(NULL),

   _count_card_bitmaps(NULL),

   _count_marked_bytes(NULL) {

   CMVerboseLevel verbose_level = (CMVerboseLevel) G1MarkingVerboseLevel;

   if (verbose_level < no_verbose) {

     verbose_level = no_verbose;

   }

   if (verbose_level > high_verbose) {

     verbose_level = high_verbose;

   }

   _verbose_level = verbose_level;

   if (verbose_low()) {

     gclog_or_tty->print_cr("[global] init, heap start = "PTR_FORMAT", "

                            "heap end = "PTR_FORMAT, _heap_start, _heap_end);

   }

   _markStack.allocate(MarkStackSize);

   // Create & start a ConcurrentMark thread.

   _cmThread = new ConcurrentMarkThread(this);

   assert(cmThread() != NULL, "CM Thread should have been created");

   assert(cmThread()->cm() != NULL, "CM Thread should refer to this cm");

   _g1h = G1CollectedHeap::heap();

   assert(CGC_lock != NULL, "Where's the CGC_lock?");

   assert(_markBitMap1.covers(rs), "_markBitMap1 inconsistency");

   assert(_markBitMap2.covers(rs), "_markBitMap2 inconsistency");

   SATBMarkQueueSet& satb_qs = JavaThread::satb_mark_queue_set();

   satb_qs.set_buffer_size(G1SATBBufferSize);

   _root_regions.init(_g1h, this);

   _tasks = NEW_C_HEAP_ARRAY(CMTask*, _max_task_num);

   _accum_task_vtime = NEW_C_HEAP_ARRAY(double, _max_task_num);

   _count_card_bitmaps = NEW_C_HEAP_ARRAY(BitMap,  _max_task_num);

   _count_marked_bytes = NEW_C_HEAP_ARRAY(size_t*, _max_task_num);

   BitMap::idx_t card_bm_size = _card_bm.size();

   // so that the assertion in MarkingTaskQueue::task_queue doesn't fail

   _active_tasks = _max_task_num;

   for (int i = 0; i < (int) _max_task_num; ++i) {

     CMTaskQueue* task_queue = new CMTaskQueue();

     task_queue->initialize();

     _task_queues->register_queue(i, task_queue);

     _count_card_bitmaps[i] = BitMap(card_bm_size, false);

     _count_marked_bytes[i] = NEW_C_HEAP_ARRAY(size_t, (size_t) max_regions);

     _tasks[i] = new CMTask(i, this,

                            _count_marked_bytes[i],

                            &_count_card_bitmaps[i],

                            task_queue, _task_queues);

     _accum_task_vtime[i] = 0.0;

   }

   // Calculate the card number for the bottom of the heap. Used

   // in biasing indexes into the accounting card bitmaps.

   _heap_bottom_card_num =

     intptr_t(uintptr_t(_g1h->reserved_region().start()) >>

                                 CardTableModRefBS::card_shift);

   // Clear all the liveness counting data

   clear_all_count_data();

   if (ConcGCThreads > ParallelGCThreads) {

     vm_exit_during_initialization("Can't have more ConcGCThreads "

                                   "than ParallelGCThreads.");

   }

   if (ParallelGCThreads == 0) {

     // if we are not running with any parallel GC threads we will not

     // spawn any marking threads either

     _parallel_marking_threads =       0;

     _max_parallel_marking_threads =   0;

     _sleep_factor             =     0.0;

     _marking_task_overhead    =     1.0;

   } else {

     if (ConcGCThreads > 0) {

       // notice that ConcGCThreads overwrites G1MarkingOverheadPercent

       // if both are set

       _parallel_marking_threads = (uint) ConcGCThreads;

       _max_parallel_marking_threads = _parallel_marking_threads;

       _sleep_factor             = 0.0;

       _marking_task_overhead    = 1.0;

     } else if (G1MarkingOverheadPercent > 0) {

       // we will calculate the number of parallel marking threads

       // based on a target overhead with respect to the soft real-time

       // goal

       double marking_overhead = (double) G1MarkingOverheadPercent / 100.0;

       double overall_cm_overhead =

         (double) MaxGCPauseMillis * marking_overhead /

         (double) GCPauseIntervalMillis;

       double cpu_ratio = 1.0 / (double) os::processor_count();

       double marking_thread_num = ceil(overall_cm_overhead / cpu_ratio);

       double marking_task_overhead =

         overall_cm_overhead / marking_thread_num *

                                                 (double) os::processor_count();

       double sleep_factor =

                          (1.0 - marking_task_overhead) / marking_task_overhead;

       _parallel_marking_threads = (uint) marking_thread_num;

       _max_parallel_marking_threads = _parallel_marking_threads;

       _sleep_factor             = sleep_factor;

       _marking_task_overhead    = marking_task_overhead;

     } else {

       _parallel_marking_threads = scale_parallel_threads((uint)ParallelGCThreads);

       _max_parallel_marking_threads = _parallel_marking_threads;

       _sleep_factor             = 0.0;

       _marking_task_overhead    = 1.0;

     }

     if (parallel_marking_threads() > 1) {

       _cleanup_task_overhead = 1.0;

     } else {

       _cleanup_task_overhead = marking_task_overhead();

     }

     _cleanup_sleep_factor =

                      (1.0 - cleanup_task_overhead()) / cleanup_task_overhead();

 #if 0

     gclog_or_tty->print_cr("Marking Threads          %d", parallel_marking_threads());

     gclog_or_tty->print_cr("CM Marking Task Overhead %1.4lf", marking_task_overhead());

     gclog_or_tty->print_cr("CM Sleep Factor          %1.4lf", sleep_factor());

     gclog_or_tty->print_cr("CL Marking Task Overhead %1.4lf", cleanup_task_overhead());

     gclog_or_tty->print_cr("CL Sleep Factor          %1.4lf", cleanup_sleep_factor());

 #endif

     guarantee(parallel_marking_threads() > 0, "peace of mind");

     _parallel_workers = new FlexibleWorkGang("G1 Parallel Marking Threads",

          _max_parallel_marking_threads, false, true);

     if (_parallel_workers == NULL) {

       vm_exit_during_initialization("Failed necessary allocation.");

     } else {

       _parallel_workers->initialize_workers();

     }

   }

   // so that the call below can read a sensible value

   _heap_start = (HeapWord*) rs.base();

   set_non_marking_state();

 }

 void ConcurrentMark::update_g1_committed(bool force) {

   // If concurrent marking is not in progress, then we do not need to

   // update _heap_end.

   if (!concurrent_marking_in_progress() && !force) return;

   MemRegion committed = _g1h->g1_committed();

   assert(committed.start() == _heap_start, "start shouldn't change");

   HeapWord* new_end = committed.end();

   if (new_end > _heap_end) {

     // The heap has been expanded.

     _heap_end = new_end;

   }

   // Notice that the heap can also shrink. However, this only happens

   // during a Full GC (at least currently) and the entire marking

   // phase will bail out and the task will not be restarted. So, let's

   // do nothing.

 }

 void ConcurrentMark::reset() {

   // Starting values for these two. This should be called in a STW

   // phase. CM will be notified of any future g1_committed expansions

   // will be at the end of evacuation pauses, when tasks are

   // inactive.

   MemRegion committed = _g1h->g1_committed();

   _heap_start = committed.start();

   _heap_end   = committed.end();

   // Separated the asserts so that we know which one fires.

   assert(_heap_start != NULL, "heap bounds should look ok");

   assert(_heap_end != NULL, "heap bounds should look ok");

   assert(_heap_start < _heap_end, "heap bounds should look ok");

   // reset all the marking data structures and any necessary flags

   clear_marking_state();

   if (verbose_low()) {

     gclog_or_tty->print_cr("[global] resetting");

   }

   // We do reset all of them, since different phases will use

   // different number of active threads. So, it's easiest to have all

   // of them ready.

   for (int i = 0; i < (int) _max_task_num; ++i) {

     _tasks[i]->reset(_nextMarkBitMap);

   }

   // we need this to make sure that the flag is on during the evac

   // pause with initial mark piggy-backed

   set_concurrent_marking_in_progress();

 }

 void ConcurrentMark::set_phase(uint active_tasks, bool concurrent) {

   assert(active_tasks <= _max_task_num, "we should not have more");

   _active_tasks = active_tasks;

   // Need to update the three data structures below according to the

   // number of active threads for this phase.

   _terminator   = ParallelTaskTerminator((int) active_tasks, _task_queues);

   _first_overflow_barrier_sync.set_n_workers((int) active_tasks);

   _second_overflow_barrier_sync.set_n_workers((int) active_tasks);

   _concurrent = concurrent;

   // We propagate this to all tasks, not just the active ones.

   for (int i = 0; i < (int) _max_task_num; ++i)

     _tasks[i]->set_concurrent(concurrent);

   if (concurrent) {

     set_concurrent_marking_in_progress();

   } else {

     // We currently assume that the concurrent flag has been set to

     // false before we start remark. At this point we should also be

     // in a STW phase.

     assert(!concurrent_marking_in_progress(), "invariant");

     assert(_finger == _heap_end, "only way to get here");

     update_g1_committed(true);

   }

 }

 void ConcurrentMark::set_non_marking_state() {

   // We set the global marking state to some default values when we're

   // not doing marking.

   clear_marking_state();

   _active_tasks = 0;

   clear_concurrent_marking_in_progress();

 }

 ConcurrentMark::~ConcurrentMark() {

   // The ConcurrentMark instance is never freed.

   ShouldNotReachHere();

 }

 void ConcurrentMark::clearNextBitmap() {

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   G1CollectorPolicy* g1p = g1h->g1_policy();

   // Make sure that the concurrent mark thread looks to still be in

   // the current cycle.

   guarantee(cmThread()->during_cycle(), "invariant");

   // We are finishing up the current cycle by clearing the next

   // marking bitmap and getting it ready for the next cycle. During

   // this time no other cycle can start. So, let's make sure that this

   // is the case.

   guarantee(!g1h->mark_in_progress(), "invariant");

   // clear the mark bitmap (no grey objects to start with).

   // We need to do this in chunks and offer to yield in between

   // each chunk.

   HeapWord* start  = _nextMarkBitMap->startWord();

   HeapWord* end    = _nextMarkBitMap->endWord();

   HeapWord* cur    = start;

   size_t chunkSize = M;

   while (cur < end) {

     HeapWord* next = cur + chunkSize;

     if (next > end) {

       next = end;

     }

     MemRegion mr(cur,next);

     _nextMarkBitMap->clearRange(mr);

     cur = next;

     do_yield_check();

     // Repeat the asserts from above. We'll do them as asserts here to

     // minimize their overhead on the product. However, we'll have

     // them as guarantees at the beginning / end of the bitmap

     // clearing to get some checking in the product.

     assert(cmThread()->during_cycle(), "invariant");

     assert(!g1h->mark_in_progress(), "invariant");

   }

   // Clear the liveness counting data

   clear_all_count_data();

   // Repeat the asserts from above.

   guarantee(cmThread()->during_cycle(), "invariant");

   guarantee(!g1h->mark_in_progress(), "invariant");

 }

 class NoteStartOfMarkHRClosure: public HeapRegionClosure {

 public:

   bool doHeapRegion(HeapRegion* r) {

     if (!r->continuesHumongous()) {

       r->note_start_of_marking();

     }

     return false;

   }

 };

 void ConcurrentMark::checkpointRootsInitialPre() {

   G1CollectedHeap*   g1h = G1CollectedHeap::heap();

   G1CollectorPolicy* g1p = g1h->g1_policy();

   _has_aborted = false;

 #ifndef PRODUCT

   if (G1PrintReachableAtInitialMark) {

     print_reachable("at-cycle-start",

                     VerifyOption_G1UsePrevMarking, true /* all */);

   }

 #endif

   // Initialise marking structures. This has to be done in a STW phase.

   reset();

   // For each region note start of marking.

   NoteStartOfMarkHRClosure startcl;

   g1h->heap_region_iterate(&startcl);

 }

 void ConcurrentMark::checkpointRootsInitialPost() {

   G1CollectedHeap*   g1h = G1CollectedHeap::heap();

   // If we force an overflow during remark, the remark operation will

   // actually abort and we'll restart concurrent marking. If we always

   // force an oveflow during remark we'll never actually complete the

   // marking phase. So, we initilize this here, at the start of the

   // cycle, so that at the remaining overflow number will decrease at

   // every remark and we'll eventually not need to cause one.

   force_overflow_stw()->init();

   // Start Concurrent Marking weak-reference discovery.

   ReferenceProcessor* rp = g1h->ref_processor_cm();

   // enable ("weak") refs discovery

   rp->enable_discovery(true /*verify_disabled*/, true /*verify_no_refs*/);

   rp->setup_policy(false); // snapshot the soft ref policy to be used in this cycle

   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

   // This is the start of  the marking cycle, we're expected all

   // threads to have SATB queues with active set to false.

   satb_mq_set.set_active_all_threads(true, /* new active value */

                                      false /* expected_active */);

   _root_regions.prepare_for_scan();

   // update_g1_committed() will be called at the end of an evac pause

   // when marking is on. So, it's also called at the end of the

   // initial-mark pause to update the heap end, if the heap expands

   // during it. No need to call it here.

 }

 /*

  * Notice that in the next two methods, we actually leave the STS

  * during the barrier sync and join it immediately afterwards. If we

  * do not do this, the following deadlock can occur: one thread could

  * be in the barrier sync code, waiting for the other thread to also

  * sync up, whereas another one could be trying to yield, while also

  * waiting for the other threads to sync up too.

  *

  * Note, however, that this code is also used during remark and in

  * this case we should not attempt to leave / enter the STS, otherwise

  * we'll either hit an asseert (debug / fastdebug) or deadlock

  * (product). So we should only leave / enter the STS if we are

  * operating concurrently.

  *

  * Because the thread that does the sync barrier has left the STS, it

  * is possible to be suspended for a Full GC or an evacuation pause

  * could occur. This is actually safe, since the entering the sync

  * barrier is one of the last things do_marking_step() does, and it

  * doesn't manipulate any data structures afterwards.

  */

 void ConcurrentMark::enter_first_sync_barrier(int task_num) {

   if (verbose_low()) {

     gclog_or_tty->print_cr("[%d] entering first barrier", task_num);

   }

   if (concurrent()) {

     ConcurrentGCThread::stsLeave();

   }

   _first_overflow_barrier_sync.enter();

   if (concurrent()) {

     ConcurrentGCThread::stsJoin();

   }

   // at this point everyone should have synced up and not be doing any

   // more work

   if (verbose_low()) {

     gclog_or_tty->print_cr("[%d] leaving first barrier", task_num);

   }

   // let task 0 do this

   if (task_num == 0) {

     // task 0 is responsible for clearing the global data structures

     // We should be here because of an overflow. During STW we should

     // not clear the overflow flag since we rely on it being true when

     // we exit this method to abort the pause and restart concurent

     // marking.

     clear_marking_state(concurrent() /* clear_overflow */);

     force_overflow()->update();

     if (G1Log::fine()) {

       gclog_or_tty->date_stamp(PrintGCDateStamps);

       gclog_or_tty->stamp(PrintGCTimeStamps);

       gclog_or_tty->print_cr("[GC concurrent-mark-reset-for-overflow]");

     }

   }

   // after this, each task should reset its own data structures then

   // then go into the second barrier

 }

 void ConcurrentMark::enter_second_sync_barrier(int task_num) {

   if (verbose_low()) {

     gclog_or_tty->print_cr("[%d] entering second barrier", task_num);

   }

   if (concurrent()) {

     ConcurrentGCThread::stsLeave();

   }

   _second_overflow_barrier_sync.enter();

   if (concurrent()) {

     ConcurrentGCThread::stsJoin();

   }

   // at this point everything should be re-initialised and ready to go

   if (verbose_low()) {

     gclog_or_tty->print_cr("[%d] leaving second barrier", task_num);

   }

 }

 #ifndef PRODUCT

 void ForceOverflowSettings::init() {

   _num_remaining = G1ConcMarkForceOverflow;

   _force = false;

   update();

 }

 void ForceOverflowSettings::update() {

   if (_num_remaining > 0) {

     _num_remaining -= 1;

     _force = true;

   } else {

     _force = false;

   }

 }

 bool ForceOverflowSettings::should_force() {

   if (_force) {

     _force = false;

     return true;

   } else {

     return false;

   }

 }

 #endif // !PRODUCT

 class CMConcurrentMarkingTask: public AbstractGangTask {

 private:

   ConcurrentMark*       _cm;

   ConcurrentMarkThread* _cmt;

 public:

   void work(uint worker_id) {

     assert(Thread::current()->is_ConcurrentGC_thread(),

            "this should only be done by a conc GC thread");

     ResourceMark rm;

     double start_vtime = os::elapsedVTime();

     ConcurrentGCThread::stsJoin();

     assert(worker_id < _cm->active_tasks(), "invariant");

     CMTask* the_task = _cm->task(worker_id);

     the_task->record_start_time();

     if (!_cm->has_aborted()) {

       do {

         double start_vtime_sec = os::elapsedVTime();

         double start_time_sec = os::elapsedTime();

         double mark_step_duration_ms = G1ConcMarkStepDurationMillis;

         the_task->do_marking_step(mark_step_duration_ms,

                                   true /* do_stealing    */,

                                   true /* do_termination */);

         double end_time_sec = os::elapsedTime();

         double end_vtime_sec = os::elapsedVTime();

         double elapsed_vtime_sec = end_vtime_sec - start_vtime_sec;

         double elapsed_time_sec = end_time_sec - start_time_sec;

         _cm->clear_has_overflown();

         bool ret = _cm->do_yield_check(worker_id);

         jlong sleep_time_ms;

         if (!_cm->has_aborted() && the_task->has_aborted()) {

           sleep_time_ms =

             (jlong) (elapsed_vtime_sec * _cm->sleep_factor() * 1000.0);

           ConcurrentGCThread::stsLeave();

           os::sleep(Thread::current(), sleep_time_ms, false);

           ConcurrentGCThread::stsJoin();

         }

         double end_time2_sec = os::elapsedTime();

         double elapsed_time2_sec = end_time2_sec - start_time_sec;

 #if 0

           gclog_or_tty->print_cr("CM: elapsed %1.4lf ms, sleep %1.4lf ms, "

                                  "overhead %1.4lf",

                                  elapsed_vtime_sec * 1000.0, (double) sleep_time_ms,

                                  the_task->conc_overhead(os::elapsedTime()) * 8.0);

           gclog_or_tty->print_cr("elapsed time %1.4lf ms, time 2: %1.4lf ms",

                                  elapsed_time_sec * 1000.0, elapsed_time2_sec * 1000.0);

 #endif

       } while (!_cm->has_aborted() && the_task->has_aborted());

     }

     the_task->record_end_time();

     guarantee(!the_task->has_aborted() || _cm->has_aborted(), "invariant");

     ConcurrentGCThread::stsLeave();

     double end_vtime = os::elapsedVTime();

     _cm->update_accum_task_vtime(worker_id, end_vtime - start_vtime);

   }

   CMConcurrentMarkingTask(ConcurrentMark* cm,

                           ConcurrentMarkThread* cmt) :

       AbstractGangTask("Concurrent Mark"), _cm(cm), _cmt(cmt) { }

   ~CMConcurrentMarkingTask() { }

 };

 // Calculates the number of active workers for a concurrent

 // phase.

 uint ConcurrentMark::calc_parallel_marking_threads() {

   if (G1CollectedHeap::use_parallel_gc_threads()) {

     uint n_conc_workers = 0;

     if (!UseDynamicNumberOfGCThreads ||

         (!FLAG_IS_DEFAULT(ConcGCThreads) &&

          !ForceDynamicNumberOfGCThreads)) {

       n_conc_workers = max_parallel_marking_threads();

     } else {

       n_conc_workers =

         AdaptiveSizePolicy::calc_default_active_workers(

                                      max_parallel_marking_threads(),

                                      1, /* Minimum workers */

                                      parallel_marking_threads(),

                                      Threads::number_of_non_daemon_threads());

       // Don't scale down "n_conc_workers" by scale_parallel_threads() because

       // that scaling has already gone into "_max_parallel_marking_threads".

     }

     assert(n_conc_workers > 0, "Always need at least 1");

     return n_conc_workers;

   }

   // If we are not running with any parallel GC threads we will not

   // have spawned any marking threads either. Hence the number of

   // concurrent workers should be 0.

   return 0;

 }

 void ConcurrentMark::scanRootRegion(HeapRegion* hr, uint worker_id) {

   // Currently, only survivors can be root regions.

   assert(hr->next_top_at_mark_start() == hr->bottom(), "invariant");

   G1RootRegionScanClosure cl(_g1h, this, worker_id);

   const uintx interval = PrefetchScanIntervalInBytes;

   HeapWord* curr = hr->bottom();

   const HeapWord* end = hr->top();

   while (curr < end) {

     Prefetch::read(curr, interval);

     oop obj = oop(curr);

     int size = obj->oop_iterate(&cl);

     assert(size == obj->size(), "sanity");

     curr += size;

   }

 }

 class CMRootRegionScanTask : public AbstractGangTask {

 private:

   ConcurrentMark* _cm;

 public:

   CMRootRegionScanTask(ConcurrentMark* cm) :

     AbstractGangTask("Root Region Scan"), _cm(cm) { }

   void work(uint worker_id) {

     assert(Thread::current()->is_ConcurrentGC_thread(),

            "this should only be done by a conc GC thread");

     CMRootRegions* root_regions = _cm->root_regions();

     HeapRegion* hr = root_regions->claim_next();

     while (hr != NULL) {

       _cm->scanRootRegion(hr, worker_id);

       hr = root_regions->claim_next();

     }

   }

 };

 void ConcurrentMark::scanRootRegions() {

   // scan_in_progress() will have been set to true only if there was

   // at least one root region to scan. So, if it's false, we

   // should not attempt to do any further work.

   if (root_regions()->scan_in_progress()) {

     _parallel_marking_threads = calc_parallel_marking_threads();

     assert(parallel_marking_threads() <= max_parallel_marking_threads(),

            "Maximum number of marking threads exceeded");

     uint active_workers = MAX2(1U, parallel_marking_threads());

     CMRootRegionScanTask task(this);

     if (parallel_marking_threads() > 0) {

       _parallel_workers->set_active_workers((int) active_workers);

       _parallel_workers->run_task(&task);

     } else {

       task.work(0);

     }

     // It's possible that has_aborted() is true here without actually

     // aborting the survivor scan earlier. This is OK as it's

     // mainly used for sanity checking.

     root_regions()->scan_finished();

   }

 }

 void ConcurrentMark::markFromRoots() {

   // we might be tempted to assert that:

   // assert(asynch == !SafepointSynchronize::is_at_safepoint(),

   //        "inconsistent argument?");

   // However that wouldn't be right, because it's possible that

   // a safepoint is indeed in progress as a younger generation

   // stop-the-world GC happens even as we mark in this generation.

   _restart_for_overflow = false;

   force_overflow_conc()->init();

   // _g1h has _n_par_threads

   _parallel_marking_threads = calc_parallel_marking_threads();

   assert(parallel_marking_threads() <= max_parallel_marking_threads(),

     "Maximum number of marking threads exceeded");

   uint active_workers = MAX2(1U, parallel_marking_threads());

   // Parallel task terminator is set in "set_phase()"

   set_phase(active_workers, true /* concurrent */);

   CMConcurrentMarkingTask markingTask(this, cmThread());

   if (parallel_marking_threads() > 0) {

     _parallel_workers->set_active_workers((int)active_workers);

     // Don't set _n_par_threads because it affects MT in proceess_strong_roots()

     // and the decisions on that MT processing is made elsewhere.

     assert(_parallel_workers->active_workers() > 0, "Should have been set");

     _parallel_workers->run_task(&markingTask);

   } else {

     markingTask.work(0);

   }

   print_stats();

 }

 void ConcurrentMark::checkpointRootsFinal(bool clear_all_soft_refs) {

   // world is stopped at this checkpoint

   assert(SafepointSynchronize::is_at_safepoint(),

          "world should be stopped");

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   // If a full collection has happened, we shouldn't do this.

   if (has_aborted()) {

     g1h->set_marking_complete(); // So bitmap clearing isn't confused

     return;

   }

   SvcGCMarker sgcm(SvcGCMarker::OTHER);

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

     gclog_or_tty->print(" VerifyDuringGC:(before)");

     Universe::heap()->prepare_for_verify();

     Universe::verify(/* silent      */ false,

                      /* option      */ VerifyOption_G1UsePrevMarking);

   }

   G1CollectorPolicy* g1p = g1h->g1_policy();

   g1p->record_concurrent_mark_remark_start();

   double start = os::elapsedTime();

   checkpointRootsFinalWork();

   double mark_work_end = os::elapsedTime();

   weakRefsWork(clear_all_soft_refs);

   if (has_overflown()) {

     // Oops.  We overflowed.  Restart concurrent marking.

     _restart_for_overflow = true;

     // Clear the flag. We do not need it any more.

     clear_has_overflown();

     if (G1TraceMarkStackOverflow) {

       gclog_or_tty->print_cr("\nRemark led to restart for overflow.");

     }

   } else {

     // Aggregate the per-task counting data that we have accumulated

     // while marking.

     aggregate_count_data();

     SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

     // We're done with marking.

     // This is the end of  the marking cycle, we're expected all

     // threads to have SATB queues with active set to true.

     satb_mq_set.set_active_all_threads(false, /* new active value */

                                        true /* expected_active */);

     if (VerifyDuringGC) {

       HandleMark hm;  // handle scope

       gclog_or_tty->print(" VerifyDuringGC:(after)");

       Universe::heap()->prepare_for_verify();

       Universe::verify(/* silent      */ false,

                        /* option      */ VerifyOption_G1UseNextMarking);

     }

     assert(!restart_for_overflow(), "sanity");

   }

   // Reset the marking state if marking completed

   if (!restart_for_overflow()) {

     set_non_marking_state();

   }

 #if VERIFY_OBJS_PROCESSED

   _scan_obj_cl.objs_processed = 0;

   ThreadLocalObjQueue::objs_enqueued = 0;

 #endif

   // Statistics

   double now = os::elapsedTime();

   _remark_mark_times.add((mark_work_end - start) * 1000.0);

   _remark_weak_ref_times.add((now - mark_work_end) * 1000.0);

   _remark_times.add((now - start) * 1000.0);

   g1p->record_concurrent_mark_remark_end();

 }

 // Base class of the closures that finalize and verify the

 // liveness counting data.

 class CMCountDataClosureBase: public HeapRegionClosure {

 protected:

   ConcurrentMark* _cm;

   BitMap* _region_bm;

   BitMap* _card_bm;

   void set_card_bitmap_range(BitMap::idx_t start_idx, BitMap::idx_t last_idx) {

     assert(start_idx <= last_idx, "sanity");

     // Set the inclusive bit range [start_idx, last_idx].

     // For small ranges (up to 8 cards) use a simple loop; otherwise

     // use par_at_put_range.

     if ((last_idx - start_idx) < 8) {

       for (BitMap::idx_t i = start_idx; i <= last_idx; i += 1) {

         _card_bm->par_set_bit(i);

       }

     } else {

       assert(last_idx < _card_bm->size(), "sanity");

       // Note BitMap::par_at_put_range() is exclusive.

       _card_bm->par_at_put_range(start_idx, last_idx+1, true);

     }

   }

   // It takes a region that's not empty (i.e., it has at least one

   // live object in it and sets its corresponding bit on the region

   // bitmap to 1. If the region is "starts humongous" it will also set

   // to 1 the bits on the region bitmap that correspond to its

   // associated "continues humongous" regions.

   void set_bit_for_region(HeapRegion* hr) {

     assert(!hr->continuesHumongous(), "should have filtered those out");

     BitMap::idx_t index = (BitMap::idx_t) hr->hrs_index();

     if (!hr->startsHumongous()) {

       // Normal (non-humongous) case: just set the bit.

       _region_bm->par_at_put(index, true);

     } else {

       // Starts humongous case: calculate how many regions are part of

       // this humongous region and then set the bit range.

       G1CollectedHeap* g1h = G1CollectedHeap::heap();

       HeapRegion *last_hr = g1h->heap_region_containing_raw(hr->end() - 1);

       BitMap::idx_t end_index = (BitMap::idx_t) last_hr->hrs_index() + 1;

       _region_bm->par_at_put_range(index, end_index, true);

     }

   }

 public:

   CMCountDataClosureBase(ConcurrentMark *cm,

                          BitMap* region_bm, BitMap* card_bm):

     _cm(cm), _region_bm(region_bm), _card_bm(card_bm) { }

 };

 // Closure that calculates the # live objects per region. Used

 // for verification purposes during the cleanup pause.

 class CalcLiveObjectsClosure: public CMCountDataClosureBase {

   CMBitMapRO* _bm;

   size_t _region_marked_bytes;

 public:

   CalcLiveObjectsClosure(CMBitMapRO *bm, ConcurrentMark *cm,

                          BitMap* region_bm, BitMap* card_bm) :

     CMCountDataClosureBase(cm, region_bm, card_bm),

     _bm(bm), _region_marked_bytes(0) { }

   bool doHeapRegion(HeapRegion* hr) {

     if (hr->continuesHumongous()) {

       // We will ignore these here and process them when their

       // associated "starts humongous" region is processed (see

       // set_bit_for_heap_region()). Note that we cannot rely on their

       // associated "starts humongous" region to have their bit set to

       // 1 since, due to the region chunking in the parallel region

       // iteration, a "continues humongous" region might be visited

       // before its associated "starts humongous".

       return false;

     }

     HeapWord* nextTop = hr->next_top_at_mark_start();

     HeapWord* start   = hr->bottom();

     assert(start <= hr->end() && start <= nextTop && nextTop <= hr->end(),

            err_msg("Preconditions not met - "

                    "start: "PTR_FORMAT", nextTop: "PTR_FORMAT", end: "PTR_FORMAT,

                    start, nextTop, hr->end()));

     // Find the first marked object at or after "start".

     start = _bm->getNextMarkedWordAddress(start, nextTop);

     size_t marked_bytes = 0;

     while (start < nextTop) {

       oop obj = oop(start);

       int obj_sz = obj->size();

       HeapWord* obj_last = start + obj_sz - 1;

       BitMap::idx_t start_idx = _cm->card_bitmap_index_for(start);

       BitMap::idx_t last_idx = _cm->card_bitmap_index_for(obj_last);

       // Set the bits in the card BM for this object (inclusive).

       set_card_bitmap_range(start_idx, last_idx);

       // Add the size of this object to the number of marked bytes.

       marked_bytes += (size_t)obj_sz * HeapWordSize;

       // Find the next marked object after this one.

       start = _bm->getNextMarkedWordAddress(obj_last + 1, nextTop);

     }

     // Mark the allocated-since-marking portion...

     HeapWord* top = hr->top();

     if (nextTop < top) {

       BitMap::idx_t start_idx = _cm->card_bitmap_index_for(nextTop);

       BitMap::idx_t last_idx = _cm->card_bitmap_index_for(top - 1);

       set_card_bitmap_range(start_idx, last_idx);

       // This definitely means the region has live objects.

       set_bit_for_region(hr);

     }

     // Update the live region bitmap.

     if (marked_bytes > 0) {

       set_bit_for_region(hr);

     }

     // Set the marked bytes for the current region so that

     // it can be queried by a calling verificiation routine

     _region_marked_bytes = marked_bytes;

     return false;

   }

   size_t region_marked_bytes() const { return _region_marked_bytes; }

 };

 // Heap region closure used for verifying the counting data

 // that was accumulated concurrently and aggregated during

 // the remark pause. This closure is applied to the heap

 // regions during the STW cleanup pause.

 class VerifyLiveObjectDataHRClosure: public HeapRegionClosure {

   ConcurrentMark* _cm;

   CalcLiveObjectsClosure _calc_cl;

   BitMap* _region_bm;   // Region BM to be verified

   BitMap* _card_bm;     // Card BM to be verified

   bool _verbose;        // verbose output?

   BitMap* _exp_region_bm; // Expected Region BM values

   BitMap* _exp_card_bm;   // Expected card BM values

   int _failures;

 public:

   VerifyLiveObjectDataHRClosure(ConcurrentMark* cm,

                                 BitMap* region_bm,

                                 BitMap* card_bm,

                                 BitMap* exp_region_bm,

                                 BitMap* exp_card_bm,

                                 bool verbose) :

     _cm(cm),

     _calc_cl(_cm->nextMarkBitMap(), _cm, exp_region_bm, exp_card_bm),

     _region_bm(region_bm), _card_bm(card_bm), _verbose(verbose),

     _exp_region_bm(exp_region_bm), _exp_card_bm(exp_card_bm),

     _failures(0) { }

   int failures() const { return _failures; }

   bool doHeapRegion(HeapRegion* hr) {

     if (hr->continuesHumongous()) {

       // We will ignore these here and process them when their

       // associated "starts humongous" region is processed (see

       // set_bit_for_heap_region()). Note that we cannot rely on their

       // associated "starts humongous" region to have their bit set to

       // 1 since, due to the region chunking in the parallel region

       // iteration, a "continues humongous" region might be visited

       // before its associated "starts humongous".

       return false;

     }

     int failures = 0;

     // Call the CalcLiveObjectsClosure to walk the marking bitmap for

     // this region and set the corresponding bits in the expected region

     // and card bitmaps.

     bool res = _calc_cl.doHeapRegion(hr);

     assert(res == false, "should be continuing");

     MutexLockerEx x((_verbose ? ParGCRareEvent_lock : NULL),

                     Mutex::_no_safepoint_check_flag);

     // Verify the marked bytes for this region.

     size_t exp_marked_bytes = _calc_cl.region_marked_bytes();

     size_t act_marked_bytes = hr->next_marked_bytes();

     // We're not OK if expected marked bytes > actual marked bytes. It means

     // we have missed accounting some objects during the actual marking.

     if (exp_marked_bytes > act_marked_bytes) {

       if (_verbose) {

         gclog_or_tty->print_cr("Region %u: marked bytes mismatch: "

                                "expected: " SIZE_FORMAT ", actual: " SIZE_FORMAT,

                                hr->hrs_index(), exp_marked_bytes, act_marked_bytes);

       }

       failures += 1;

     }

     // Verify the bit, for this region, in the actual and expected

     // (which was just calculated) region bit maps.

     // We're not OK if the bit in the calculated expected region

     // bitmap is set and the bit in the actual region bitmap is not.

     BitMap::idx_t index = (BitMap::idx_t) hr->hrs_index();

     bool expected = _exp_region_bm->at(index);

     bool actual = _region_bm->at(index);

     if (expected && !actual) {

       if (_verbose) {

         gclog_or_tty->print_cr("Region %u: region bitmap mismatch: "

                                "expected: %s, actual: %s",

                                hr->hrs_index(),

                                BOOL_TO_STR(expected), BOOL_TO_STR(actual));

       }

       failures += 1;

     }

     // Verify that the card bit maps for the cards spanned by the current

     // region match. We have an error if we have a set bit in the expected

     // bit map and the corresponding bit in the actual bitmap is not set.

     BitMap::idx_t start_idx = _cm->card_bitmap_index_for(hr->bottom());

     BitMap::idx_t end_idx = _cm->card_bitmap_index_for(hr->top());

     for (BitMap::idx_t i = start_idx; i < end_idx; i+=1) {

       expected = _exp_card_bm->at(i);

       actual = _card_bm->at(i);

       if (expected && !actual) {

         if (_verbose) {

           gclog_or_tty->print_cr("Region %u: card bitmap mismatch at " SIZE_FORMAT ": "

                                  "expected: %s, actual: %s",

                                  hr->hrs_index(), i,

                                  BOOL_TO_STR(expected), BOOL_TO_STR(actual));

         }

         failures += 1;

       }

     }

     if (failures > 0 && _verbose)  {

       gclog_or_tty->print_cr("Region " HR_FORMAT ", ntams: " PTR_FORMAT ", "

                              "marked_bytes: calc/actual " SIZE_FORMAT "/" SIZE_FORMAT,

                              HR_FORMAT_PARAMS(hr), hr->next_top_at_mark_start(),

                              _calc_cl.region_marked_bytes(), hr->next_marked_bytes());

     }

     _failures += failures;

     // We could stop iteration over the heap when we

     // find the first violating region by returning true.

     return false;

   }

 };

 class G1ParVerifyFinalCountTask: public AbstractGangTask {

 protected:

   G1CollectedHeap* _g1h;

   ConcurrentMark* _cm;

   BitMap* _actual_region_bm;

   BitMap* _actual_card_bm;

   uint    _n_workers;

   BitMap* _expected_region_bm;

   BitMap* _expected_card_bm;

   int  _failures;

   bool _verbose;

 public:

   G1ParVerifyFinalCountTask(G1CollectedHeap* g1h,

                             BitMap* region_bm, BitMap* card_bm,

                             BitMap* expected_region_bm, BitMap* expected_card_bm)

     : AbstractGangTask("G1 verify final counting"),

       _g1h(g1h), _cm(_g1h->concurrent_mark()),

       _actual_region_bm(region_bm), _actual_card_bm(card_bm),

       _expected_region_bm(expected_region_bm), _expected_card_bm(expected_card_bm),

       _failures(0), _verbose(false),

       _n_workers(0) {

     assert(VerifyDuringGC, "don't call this otherwise");

     // Use the value already set as the number of active threads

     // in the call to run_task().

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       assert( _g1h->workers()->active_workers() > 0,

         "Should have been previously set");

       _n_workers = _g1h->workers()->active_workers();

     } else {

       _n_workers = 1;

     }

     assert(_expected_card_bm->size() == _actual_card_bm->size(), "sanity");

     assert(_expected_region_bm->size() == _actual_region_bm->size(), "sanity");

     _verbose = _cm->verbose_medium();

   }

   void work(uint worker_id) {

     assert(worker_id < _n_workers, "invariant");

     VerifyLiveObjectDataHRClosure verify_cl(_cm,

                                             _actual_region_bm, _actual_card_bm,

                                             _expected_region_bm,

                                             _expected_card_bm,

                                             _verbose);

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       _g1h->heap_region_par_iterate_chunked(&verify_cl,

                                             worker_id,

                                             _n_workers,

                                             HeapRegion::VerifyCountClaimValue);

     } else {

       _g1h->heap_region_iterate(&verify_cl);

     }

     Atomic::add(verify_cl.failures(), &_failures);

   }

   int failures() const { return _failures; }

 };

 // Closure that finalizes the liveness counting data.

 // Used during the cleanup pause.

 // Sets the bits corresponding to the interval [NTAMS, top]

 // (which contains the implicitly live objects) in the

 // card liveness bitmap. Also sets the bit for each region,

 // containing live data, in the region liveness bitmap.

 class FinalCountDataUpdateClosure: public CMCountDataClosureBase {

  public:

   FinalCountDataUpdateClosure(ConcurrentMark* cm,

                               BitMap* region_bm,

                               BitMap* card_bm) :

     CMCountDataClosureBase(cm, region_bm, card_bm) { }

   bool doHeapRegion(HeapRegion* hr) {

     if (hr->continuesHumongous()) {

       // We will ignore these here and process them when their

       // associated "starts humongous" region is processed (see

       // set_bit_for_heap_region()). Note that we cannot rely on their

       // associated "starts humongous" region to have their bit set to

       // 1 since, due to the region chunking in the parallel region

       // iteration, a "continues humongous" region might be visited

       // before its associated "starts humongous".

       return false;

     }

     HeapWord* ntams = hr->next_top_at_mark_start();

     HeapWord* top   = hr->top();

     assert(hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions.");

     // Mark the allocated-since-marking portion...

     if (ntams < top) {

       // This definitely means the region has live objects.

       set_bit_for_region(hr);

     }

     // Now set the bits for [ntams, top]

     BitMap::idx_t start_idx = _cm->card_bitmap_index_for(ntams);

     BitMap::idx_t last_idx = _cm->card_bitmap_index_for(top);

     set_card_bitmap_range(start_idx, last_idx);

     // Set the bit for the region if it contains live data

     if (hr->next_marked_bytes() > 0) {

       set_bit_for_region(hr);

     }

     return false;

   }

 };

 class G1ParFinalCountTask: public AbstractGangTask {

 protected:

   G1CollectedHeap* _g1h;

   ConcurrentMark* _cm;

   BitMap* _actual_region_bm;

   BitMap* _actual_card_bm;

   uint    _n_workers;

 public:

   G1ParFinalCountTask(G1CollectedHeap* g1h, BitMap* region_bm, BitMap* card_bm)

     : AbstractGangTask("G1 final counting"),

       _g1h(g1h), _cm(_g1h->concurrent_mark()),

       _actual_region_bm(region_bm), _actual_card_bm(card_bm),

       _n_workers(0) {

     // Use the value already set as the number of active threads

     // in the call to run_task().

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       assert( _g1h->workers()->active_workers() > 0,

         "Should have been previously set");

       _n_workers = _g1h->workers()->active_workers();

     } else {

       _n_workers = 1;

     }

   }

   void work(uint worker_id) {

     assert(worker_id < _n_workers, "invariant");

     FinalCountDataUpdateClosure final_update_cl(_cm,

                                                 _actual_region_bm,

                                                 _actual_card_bm);

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       _g1h->heap_region_par_iterate_chunked(&final_update_cl,

                                             worker_id,

                                             _n_workers,

                                             HeapRegion::FinalCountClaimValue);

     } else {

       _g1h->heap_region_iterate(&final_update_cl);

     }

   }

 };

 class G1ParNoteEndTask;

 class G1NoteEndOfConcMarkClosure : public HeapRegionClosure {

   G1CollectedHeap* _g1;

   int _worker_num;

   size_t _max_live_bytes;

   uint _regions_claimed;

   size_t _freed_bytes;

   FreeRegionList* _local_cleanup_list;

   OldRegionSet* _old_proxy_set;

   HumongousRegionSet* _humongous_proxy_set;

   HRRSCleanupTask* _hrrs_cleanup_task;

   double _claimed_region_time;

   double _max_region_time;

 public:

   G1NoteEndOfConcMarkClosure(G1CollectedHeap* g1,

                              int worker_num,

                              FreeRegionList* local_cleanup_list,

                              OldRegionSet* old_proxy_set,

                              HumongousRegionSet* humongous_proxy_set,

                              HRRSCleanupTask* hrrs_cleanup_task) :

     _g1(g1), _worker_num(worker_num),

     _max_live_bytes(0), _regions_claimed(0),

     _freed_bytes(0),

     _claimed_region_time(0.0), _max_region_time(0.0),

     _local_cleanup_list(local_cleanup_list),

     _old_proxy_set(old_proxy_set),

     _humongous_proxy_set(humongous_proxy_set),

     _hrrs_cleanup_task(hrrs_cleanup_task) { }

   size_t freed_bytes() { return _freed_bytes; }

   bool doHeapRegion(HeapRegion *hr) {

     // We use a claim value of zero here because all regions

     // were claimed with value 1 in the FinalCount task.

     hr->reset_gc_time_stamp();

     if (!hr->continuesHumongous()) {

       double start = os::elapsedTime();

       _regions_claimed++;

       hr->note_end_of_marking();

       _max_live_bytes += hr->max_live_bytes();

       _g1->free_region_if_empty(hr,

                                 &_freed_bytes,

                                 _local_cleanup_list,

                                 _old_proxy_set,

                                 _humongous_proxy_set,

                                 _hrrs_cleanup_task,

                                 true /* par */);

       double region_time = (os::elapsedTime() - start);

       _claimed_region_time += region_time;

       if (region_time > _max_region_time) {

         _max_region_time = region_time;

       }

     }

     return false;

   }

   size_t max_live_bytes() { return _max_live_bytes; }

   uint regions_claimed() { return _regions_claimed; }

   double claimed_region_time_sec() { return _claimed_region_time; }

   double max_region_time_sec() { return _max_region_time; }

 };

 class G1ParNoteEndTask: public AbstractGangTask {

   friend class G1NoteEndOfConcMarkClosure;

 protected:

   G1CollectedHeap* _g1h;

   size_t _max_live_bytes;

   size_t _freed_bytes;

   FreeRegionList* _cleanup_list;

 public:

   G1ParNoteEndTask(G1CollectedHeap* g1h,

                    FreeRegionList* cleanup_list) :

     AbstractGangTask("G1 note end"), _g1h(g1h),

     _max_live_bytes(0), _freed_bytes(0), _cleanup_list(cleanup_list) { }

   void work(uint worker_id) {

     double start = os::elapsedTime();

     FreeRegionList local_cleanup_list("Local Cleanup List");

     OldRegionSet old_proxy_set("Local Cleanup Old Proxy Set");

     HumongousRegionSet humongous_proxy_set("Local Cleanup Humongous Proxy Set");

     HRRSCleanupTask hrrs_cleanup_task;

     G1NoteEndOfConcMarkClosure g1_note_end(_g1h, worker_id, &local_cleanup_list,

                                            &old_proxy_set,

                                            &humongous_proxy_set,

                                            &hrrs_cleanup_task);

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       _g1h->heap_region_par_iterate_chunked(&g1_note_end, worker_id,

                                             _g1h->workers()->active_workers(),

                                             HeapRegion::NoteEndClaimValue);

     } else {

       _g1h->heap_region_iterate(&g1_note_end);

     }

     assert(g1_note_end.complete(), "Shouldn't have yielded!");

     // Now update the lists

     _g1h->update_sets_after_freeing_regions(g1_note_end.freed_bytes(),

                                             NULL /* free_list */,

                                             &old_proxy_set,

                                             &humongous_proxy_set,

                                             true /* par */);

     {

       MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

       _max_live_bytes += g1_note_end.max_live_bytes();

       _freed_bytes += g1_note_end.freed_bytes();

       // If we iterate over the global cleanup list at the end of

       // cleanup to do this printing we will not guarantee to only

       // generate output for the newly-reclaimed regions (the list

       // might not be empty at the beginning of cleanup; we might

       // still be working on its previous contents). So we do the

       // printing here, before we append the new regions to the global

       // cleanup list.

       G1HRPrinter* hr_printer = _g1h->hr_printer();

       if (hr_printer->is_active()) {

         HeapRegionLinkedListIterator iter(&local_cleanup_list);

         while (iter.more_available()) {

           HeapRegion* hr = iter.get_next();

           hr_printer->cleanup(hr);

         }

       }

       _cleanup_list->add_as_tail(&local_cleanup_list);

       assert(local_cleanup_list.is_empty(), "post-condition");

       HeapRegionRemSet::finish_cleanup_task(&hrrs_cleanup_task);

     }

   }

   size_t max_live_bytes() { return _max_live_bytes; }

   size_t freed_bytes() { return _freed_bytes; }

 };

 class G1ParScrubRemSetTask: public AbstractGangTask {

 protected:

   G1RemSet* _g1rs;

   BitMap* _region_bm;

   BitMap* _card_bm;

 public:

   G1ParScrubRemSetTask(G1CollectedHeap* g1h,

                        BitMap* region_bm, BitMap* card_bm) :

     AbstractGangTask("G1 ScrubRS"), _g1rs(g1h->g1_rem_set()),

     _region_bm(region_bm), _card_bm(card_bm) { }

   void work(uint worker_id) {

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       _g1rs->scrub_par(_region_bm, _card_bm, worker_id,

                        HeapRegion::ScrubRemSetClaimValue);

     } else {

       _g1rs->scrub(_region_bm, _card_bm);

     }

   }

 };

 void ConcurrentMark::cleanup() {

   // world is stopped at this checkpoint

   assert(SafepointSynchronize::is_at_safepoint(),

          "world should be stopped");

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   // If a full collection has happened, we shouldn't do this.

   if (has_aborted()) {

     g1h->set_marking_complete(); // So bitmap clearing isn't confused

     return;

   }

   HRSPhaseSetter x(HRSPhaseCleanup);

   g1h->verify_region_sets_optional();

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

     gclog_or_tty->print(" VerifyDuringGC:(before)");

     Universe::heap()->prepare_for_verify();

     Universe::verify(/* silent      */ false,

                      /* option      */ VerifyOption_G1UsePrevMarking);

   }

   G1CollectorPolicy* g1p = G1CollectedHeap::heap()->g1_policy();

   g1p->record_concurrent_mark_cleanup_start();

   double start = os::elapsedTime();

   HeapRegionRemSet::reset_for_cleanup_tasks();

   uint n_workers;

   // Do counting once more with the world stopped for good measure.

   G1ParFinalCountTask g1_par_count_task(g1h, &_region_bm, &_card_bm);

   if (G1CollectedHeap::use_parallel_gc_threads()) {

    assert(g1h->check_heap_region_claim_values(HeapRegion::InitialClaimValue),

            "sanity check");

     g1h->set_par_threads();

     n_workers = g1h->n_par_threads();

     assert(g1h->n_par_threads() == n_workers,

            "Should not have been reset");

     g1h->workers()->run_task(&g1_par_count_task);

     // Done with the parallel phase so reset to 0.

     g1h->set_par_threads(0);

     assert(g1h->check_heap_region_claim_values(HeapRegion::FinalCountClaimValue),

            "sanity check");

   } else {

     n_workers = 1;

     g1_par_count_task.work(0);

   }

   if (VerifyDuringGC) {

     // Verify that the counting data accumulated during marking matches

     // that calculated by walking the marking bitmap.

     // Bitmaps to hold expected values

     BitMap expected_region_bm(_region_bm.size(), false);

     BitMap expected_card_bm(_card_bm.size(), false);

     G1ParVerifyFinalCountTask g1_par_verify_task(g1h,

                                                  &_region_bm,

                                                  &_card_bm,

                                                  &expected_region_bm,

                                                  &expected_card_bm);

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       g1h->set_par_threads((int)n_workers);

       g1h->workers()->run_task(&g1_par_verify_task);

       // Done with the parallel phase so reset to 0.

       g1h->set_par_threads(0);

       assert(g1h->check_heap_region_claim_values(HeapRegion::VerifyCountClaimValue),

              "sanity check");

     } else {

       g1_par_verify_task.work(0);

     }

     guarantee(g1_par_verify_task.failures() == 0, "Unexpected accounting failures");

   }

   size_t start_used_bytes = g1h->used();

   g1h->set_marking_complete();

   double count_end = os::elapsedTime();

   double this_final_counting_time = (count_end - start);

   _total_counting_time += this_final_counting_time;

   if (G1PrintRegionLivenessInfo) {

     G1PrintRegionLivenessInfoClosure cl(gclog_or_tty, "Post-Marking");

     _g1h->heap_region_iterate(&cl);

   }

   // Install newly created mark bitMap as "prev".

   swapMarkBitMaps();

   g1h->reset_gc_time_stamp();

   // Note end of marking in all heap regions.

   G1ParNoteEndTask g1_par_note_end_task(g1h, &_cleanup_list);

   if (G1CollectedHeap::use_parallel_gc_threads()) {

     g1h->set_par_threads((int)n_workers);

     g1h->workers()->run_task(&g1_par_note_end_task);

     g1h->set_par_threads(0);

     assert(g1h->check_heap_region_claim_values(HeapRegion::NoteEndClaimValue),

            "sanity check");

   } else {

     g1_par_note_end_task.work(0);

   }

   if (!cleanup_list_is_empty()) {

     // The cleanup list is not empty, so we'll have to process it

     // concurrently. Notify anyone else that might be wanting free

     // regions that there will be more free regions coming soon.

     g1h->set_free_regions_coming();

   }

   // call below, since it affects the metric by which we sort the heap

   // regions.

   if (G1ScrubRemSets) {

     double rs_scrub_start = os::elapsedTime();

     G1ParScrubRemSetTask g1_par_scrub_rs_task(g1h, &_region_bm, &_card_bm);

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       g1h->set_par_threads((int)n_workers);

       g1h->workers()->run_task(&g1_par_scrub_rs_task);

       g1h->set_par_threads(0);

       assert(g1h->check_heap_region_claim_values(

                                             HeapRegion::ScrubRemSetClaimValue),

              "sanity check");

     } else {

       g1_par_scrub_rs_task.work(0);

     }

     double rs_scrub_end = os::elapsedTime();

     double this_rs_scrub_time = (rs_scrub_end - rs_scrub_start);

     _total_rs_scrub_time += this_rs_scrub_time;

   }

   // this will also free any regions totally full of garbage objects,

   // and sort the regions.

   g1h->g1_policy()->record_concurrent_mark_cleanup_end((int)n_workers);

   // Statistics.

   double end = os::elapsedTime();

   _cleanup_times.add((end - start) * 1000.0);

   if (G1Log::fine()) {

     g1h->print_size_transition(gclog_or_tty,

                                start_used_bytes,

                                g1h->used(),

                                g1h->capacity());

   }

   // Clean up will have freed any regions completely full of garbage.

   // Update the soft reference policy with the new heap occupancy.

   Universe::update_heap_info_at_gc();

   // We need to make this be a "collection" so any collection pause that

   // races with it goes around and waits for completeCleanup to finish.

   g1h->increment_total_collections();

   // We reclaimed old regions so we should calculate the sizes to make

   // sure we update the old gen/space data.

   g1h->g1mm()->update_sizes();

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

     gclog_or_tty->print(" VerifyDuringGC:(after)");

     Universe::heap()->prepare_for_verify();

     Universe::verify(/* silent      */ false,

                      /* option      */ VerifyOption_G1UsePrevMarking);

   }

   g1h->verify_region_sets_optional();

 }

 void ConcurrentMark::completeCleanup() {

   if (has_aborted()) return;

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   _cleanup_list.verify_optional();

   FreeRegionList tmp_free_list("Tmp Free List");

   if (G1ConcRegionFreeingVerbose) {

     gclog_or_tty->print_cr("G1ConcRegionFreeing [complete cleanup] : "

                            "cleanup list has %u entries",

                            _cleanup_list.length());

   }

   // Noone else should be accessing the _cleanup_list at this point,

   // so it's not necessary to take any locks

   while (!_cleanup_list.is_empty()) {

     HeapRegion* hr = _cleanup_list.remove_head();

     assert(hr != NULL, "the list was not empty");

     hr->par_clear();

     tmp_free_list.add_as_tail(hr);

     // Instead of adding one region at a time to the secondary_free_list,

     // we accumulate them in the local list and move them a few at a

     // time. This also cuts down on the number of notify_all() calls

     // we do during this process. We'll also append the local list when

     // _cleanup_list is empty (which means we just removed the last

     // region from the _cleanup_list).

     if ((tmp_free_list.length() % G1SecondaryFreeListAppendLength == 0) ||

         _cleanup_list.is_empty()) {

       if (G1ConcRegionFreeingVerbose) {

         gclog_or_tty->print_cr("G1ConcRegionFreeing [complete cleanup] : "

                                "appending %u entries to the secondary_free_list, "

                                "cleanup list still has %u entries",

                                tmp_free_list.length(),

                                _cleanup_list.length());

       }

       {

         MutexLockerEx x(SecondaryFreeList_lock, Mutex::_no_safepoint_check_flag);

         g1h->secondary_free_list_add_as_tail(&tmp_free_list);

         SecondaryFreeList_lock->notify_all();

       }

       if (G1StressConcRegionFreeing) {

         for (uintx i = 0; i < G1StressConcRegionFreeingDelayMillis; ++i) {

           os::sleep(Thread::current(), (jlong) 1, false);

         }

       }

     }

   }

   assert(tmp_free_list.is_empty(), "post-condition");

 }

 // Support closures for reference procssing in G1

 bool G1CMIsAliveClosure::do_object_b(oop obj) {

   HeapWord* addr = (HeapWord*)obj;

   return addr != NULL &&

          (!_g1->is_in_g1_reserved(addr) || !_g1->is_obj_ill(obj));

 }

 class G1CMKeepAliveClosure: public OopClosure {

   G1CollectedHeap* _g1;

   ConcurrentMark*  _cm;

  public:

   G1CMKeepAliveClosure(G1CollectedHeap* g1, ConcurrentMark* cm) :

     _g1(g1), _cm(cm) {

     assert(Thread::current()->is_VM_thread(), "otherwise fix worker id");

   }

   virtual void do_oop(narrowOop* p) { do_oop_work(p); }

   virtual void do_oop(      oop* p) { do_oop_work(p); }

   template <class T> void do_oop_work(T* p) {

     oop obj = oopDesc::load_decode_heap_oop(p);

     HeapWord* addr = (HeapWord*)obj;

     if (_cm->verbose_high()) {

       gclog_or_tty->print_cr("\t[0] we're looking at location "

                              "*"PTR_FORMAT" = "PTR_FORMAT,

                              p, (void*) obj);

     }

     if (_g1->is_in_g1_reserved(addr) && _g1->is_obj_ill(obj)) {

       _cm->mark_and_count(obj);

       _cm->mark_stack_push(obj);

     }

   }

 };

 class G1CMDrainMarkingStackClosure: public VoidClosure {

   ConcurrentMark*               _cm;

   CMMarkStack*                  _markStack;

   G1CMKeepAliveClosure*         _oopClosure;

  public:

   G1CMDrainMarkingStackClosure(ConcurrentMark* cm, CMMarkStack* markStack,

                                G1CMKeepAliveClosure* oopClosure) :

     _cm(cm),

     _markStack(markStack),

     _oopClosure(oopClosure) { }

   void do_void() {

     _markStack->drain((OopClosure*)_oopClosure, _cm->nextMarkBitMap(), false);

   }

 };

 // 'Keep Alive' closure used by parallel reference processing.

 // An instance of this closure is used in the parallel reference processing

 // code rather than an instance of G1CMKeepAliveClosure. We could have used

 // the G1CMKeepAliveClosure as it is MT-safe. Also reference objects are

 // placed on to discovered ref lists once so we can mark and push with no

 // need to check whether the object has already been marked. Using the

 // G1CMKeepAliveClosure would mean, however, having all the worker threads

 // operating on the global mark stack. This means that an individual

 // worker would be doing lock-free pushes while it processes its own

 // discovered ref list followed by drain call. If the discovered ref lists

 // are unbalanced then this could cause interference with the other

 // workers. Using a CMTask (and its embedded local data structures)

 // avoids that potential interference.

 class G1CMParKeepAliveAndDrainClosure: public OopClosure {

   ConcurrentMark*  _cm;

   CMTask*          _task;

   int              _ref_counter_limit;

   int              _ref_counter;

  public:

   G1CMParKeepAliveAndDrainClosure(ConcurrentMark* cm, CMTask* task) :

     _cm(cm), _task(task),

     _ref_counter_limit(G1RefProcDrainInterval) {

     assert(_ref_counter_limit > 0, "sanity");

     _ref_counter = _ref_counter_limit;

   }

   virtual void do_oop(narrowOop* p) { do_oop_work(p); }

   virtual void do_oop(      oop* p) { do_oop_work(p); }

   template <class T> void do_oop_work(T* p) {

     if (!_cm->has_overflown()) {

       oop obj = oopDesc::load_decode_heap_oop(p);

       if (_cm->verbose_high()) {

         gclog_or_tty->print_cr("\t[%d] we're looking at location "

                                "*"PTR_FORMAT" = "PTR_FORMAT,

                                _task->task_id(), p, (void*) obj);

       }

       _task->deal_with_reference(obj);

       _ref_counter--;

       if (_ref_counter == 0) {

         // We have dealt with _ref_counter_limit references, pushing them and objects

         // reachable from them on to the local stack (and possibly the global stack).

         // Call do_marking_step() to process these entries. We call the routine in a

         // loop, which we'll exit if there's nothing more to do (i.e. we're done

         // with the entries that we've pushed as a result of the deal_with_reference

         // calls above) or we overflow.

         // Note: CMTask::do_marking_step() can set the CMTask::has_aborted() flag

         // while there may still be some work to do. (See the comment at the

         // beginning of CMTask::do_marking_step() for those conditions - one of which

         // is reaching the specified time target.) It is only when

         // CMTask::do_marking_step() returns without setting the has_aborted() flag

         // that the marking has completed.

         do {

           double mark_step_duration_ms = G1ConcMarkStepDurationMillis;

           _task->do_marking_step(mark_step_duration_ms,

                                  false /* do_stealing    */,

                                  false /* do_termination */);

         } while (_task->has_aborted() && !_cm->has_overflown());

         _ref_counter = _ref_counter_limit;

       }

     } else {

       if (_cm->verbose_high()) {

          gclog_or_tty->print_cr("\t[%d] CM Overflow", _task->task_id());

       }

     }

   }

 };

 class G1CMParDrainMarkingStackClosure: public VoidClosure {

   ConcurrentMark* _cm;

   CMTask* _task;

  public:

   G1CMParDrainMarkingStackClosure(ConcurrentMark* cm, CMTask* task) :

     _cm(cm), _task(task) { }

   void do_void() {

     do {

       if (_cm->verbose_high()) {

         gclog_or_tty->print_cr("\t[%d] Drain: Calling do marking_step",

                                _task->task_id());

       }

       // We call CMTask::do_marking_step() to completely drain the local and

       // global marking stacks. The routine is called in a loop, which we'll

       // exit if there's nothing more to do (i.e. we'completely drained the

       // entries that were pushed as a result of applying the

       // G1CMParKeepAliveAndDrainClosure to the entries on the discovered ref

       // lists above) or we overflow the global marking stack.

       // Note: CMTask::do_marking_step() can set the CMTask::has_aborted() flag

       // while there may still be some work to do. (See the comment at the

       // beginning of CMTask::do_marking_step() for those conditions - one of which

       // is reaching the specified time target.) It is only when

       // CMTask::do_marking_step() returns without setting the has_aborted() flag

       // that the marking has completed.

       _task->do_marking_step(1000000000.0 /* something very large */,

                              true /* do_stealing    */,

                              true /* do_termination */);

     } while (_task->has_aborted() && !_cm->has_overflown());

   }

 };

 // Implementation of AbstractRefProcTaskExecutor for parallel

 // reference processing at the end of G1 concurrent marking

 class G1CMRefProcTaskExecutor: public AbstractRefProcTaskExecutor {

 private:

   G1CollectedHeap* _g1h;

   ConcurrentMark*  _cm;

   WorkGang*        _workers;

   int              _active_workers;

 public:

   G1CMRefProcTaskExecutor(G1CollectedHeap* g1h,

                         ConcurrentMark* cm,

                         WorkGang* workers,

                         int n_workers) :

     _g1h(g1h), _cm(cm),

     _workers(workers), _active_workers(n_workers) { }

   // Executes the given task using concurrent marking worker threads.

   virtual void execute(ProcessTask& task);

   virtual void execute(EnqueueTask& task);

 };

 class G1CMRefProcTaskProxy: public AbstractGangTask {

   typedef AbstractRefProcTaskExecutor::ProcessTask ProcessTask;

   ProcessTask&     _proc_task;

   G1CollectedHeap* _g1h;

   ConcurrentMark*  _cm;

 public:

   G1CMRefProcTaskProxy(ProcessTask& proc_task,

                      G1CollectedHeap* g1h,

                      ConcurrentMark* cm) :

     AbstractGangTask("Process reference objects in parallel"),

     _proc_task(proc_task), _g1h(g1h), _cm(cm) { }

   virtual void work(uint worker_id) {

     CMTask* marking_task = _cm->task(worker_id);

     G1CMIsAliveClosure g1_is_alive(_g1h);

     G1CMParKeepAliveAndDrainClosure g1_par_keep_alive(_cm, marking_task);

     G1CMParDrainMarkingStackClosure g1_par_drain(_cm, marking_task);

     _proc_task.work(worker_id, g1_is_alive, g1_par_keep_alive, g1_par_drain);

   }

 };

 void G1CMRefProcTaskExecutor::execute(ProcessTask& proc_task) {

   assert(_workers != NULL, "Need parallel worker threads.");

   G1CMRefProcTaskProxy proc_task_proxy(proc_task, _g1h, _cm);

   // We need to reset the phase for each task execution so that

   // the termination protocol of CMTask::do_marking_step works.

   _cm->set_phase(_active_workers, false /* concurrent */);

   _g1h->set_par_threads(_active_workers);

   _workers->run_task(&proc_task_proxy);

   _g1h->set_par_threads(0);

 }

 class G1CMRefEnqueueTaskProxy: public AbstractGangTask {

   typedef AbstractRefProcTaskExecutor::EnqueueTask EnqueueTask;

   EnqueueTask& _enq_task;

 public:

   G1CMRefEnqueueTaskProxy(EnqueueTask& enq_task) :

     AbstractGangTask("Enqueue reference objects in parallel"),

     _enq_task(enq_task) { }

   virtual void work(uint worker_id) {

     _enq_task.work(worker_id);

   }

 };

 void G1CMRefProcTaskExecutor::execute(EnqueueTask& enq_task) {

   assert(_workers != NULL, "Need parallel worker threads.");

   G1CMRefEnqueueTaskProxy enq_task_proxy(enq_task);

   _g1h->set_par_threads(_active_workers);

   _workers->run_task(&enq_task_proxy);

   _g1h->set_par_threads(0);

 }

 void ConcurrentMark::weakRefsWork(bool clear_all_soft_refs) {

   ResourceMark rm;

   HandleMark   hm;

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   // Is alive closure.

   G1CMIsAliveClosure g1_is_alive(g1h);

   // Inner scope to exclude the cleaning of the string and symbol

   // tables from the displayed time.

   {

     if (G1Log::finer()) {

       gclog_or_tty->put(' ');

     }

     TraceTime t("GC ref-proc", G1Log::finer(), false, gclog_or_tty);

     ReferenceProcessor* rp = g1h->ref_processor_cm();

     // See the comment in G1CollectedHeap::ref_processing_init()

     // about how reference processing currently works in G1.

     // Process weak references.

     rp->setup_policy(clear_all_soft_refs);

     assert(_markStack.isEmpty(), "mark stack should be empty");

     G1CMKeepAliveClosure g1_keep_alive(g1h, this);

     G1CMDrainMarkingStackClosure

       g1_drain_mark_stack(this, &_markStack, &g1_keep_alive);

     // We use the work gang from the G1CollectedHeap and we utilize all

     // the worker threads.

     uint active_workers = g1h->workers() ? g1h->workers()->active_workers() : 1U;

     active_workers = MAX2(MIN2(active_workers, _max_task_num), 1U);

     G1CMRefProcTaskExecutor par_task_executor(g1h, this,

                                               g1h->workers(), active_workers);

     if (rp->processing_is_mt()) {

       // Set the degree of MT here.  If the discovery is done MT, there

       // may have been a different number of threads doing the discovery

       // and a different number of discovered lists may have Ref objects.

       // That is OK as long as the Reference lists are balanced (see

       // balance_all_queues() and balance_queues()).

       rp->set_active_mt_degree(active_workers);

       rp->process_discovered_references(&g1_is_alive,

                                       &g1_keep_alive,

                                       &g1_drain_mark_stack,

                                       &par_task_executor);

       // The work routines of the parallel keep_alive and drain_marking_stack

       // will set the has_overflown flag if we overflow the global marking

       // stack.

     } else {

       rp->process_discovered_references(&g1_is_alive,

                                         &g1_keep_alive,

                                         &g1_drain_mark_stack,

                                         NULL);

     }

     assert(_markStack.overflow() || _markStack.isEmpty(),

             "mark stack should be empty (unless it overflowed)");

     if (_markStack.overflow()) {

       // Should have been done already when we tried to push an

       // entry on to the global mark stack. But let's do it again.

       set_has_overflown();

     }

     if (rp->processing_is_mt()) {

       assert(rp->num_q() == active_workers, "why not");

       rp->enqueue_discovered_references(&par_task_executor);

     } else {

       rp->enqueue_discovered_references();

     }

     rp->verify_no_references_recorded();

     assert(!rp->discovery_enabled(), "Post condition");

   }

   // Now clean up stale oops in StringTable

   StringTable::unlink(&g1_is_alive);

   // Clean up unreferenced symbols in symbol table.

   SymbolTable::unlink();

 }

 void ConcurrentMark::swapMarkBitMaps() {

   CMBitMapRO* temp = _prevMarkBitMap;

   _prevMarkBitMap  = (CMBitMapRO*)_nextMarkBitMap;

   _nextMarkBitMap  = (CMBitMap*)  temp;

 }

 class CMRemarkTask: public AbstractGangTask {

 private:

   ConcurrentMark *_cm;

 public:

   void work(uint worker_id) {

     // Since all available tasks are actually started, we should

     // only proceed if we're supposed to be actived.

     if (worker_id < _cm->active_tasks()) {

       CMTask* task = _cm->task(worker_id);

       task->record_start_time();

       do {

         task->do_marking_step(1000000000.0 /* something very large */,

                               true /* do_stealing    */,

                               true /* do_termination */);

       } while (task->has_aborted() && !_cm->has_overflown());

       // If we overflow, then we do not want to restart. We instead

       // want to abort remark and do concurrent marking again.

       task->record_end_time();

     }

   }

   CMRemarkTask(ConcurrentMark* cm, int active_workers) :

     AbstractGangTask("Par Remark"), _cm(cm) {

     _cm->terminator()->reset_for_reuse(active_workers);

   }

 };

 void ConcurrentMark::checkpointRootsFinalWork() {

   ResourceMark rm;

   HandleMark   hm;

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   g1h->ensure_parsability(false);

   if (G1CollectedHeap::use_parallel_gc_threads()) {

     G1CollectedHeap::StrongRootsScope srs(g1h);

     // this is remark, so we'll use up all active threads

     uint active_workers = g1h->workers()->active_workers();

     if (active_workers == 0) {

       assert(active_workers > 0, "Should have been set earlier");

       active_workers = (uint) ParallelGCThreads;

       g1h->workers()->set_active_workers(active_workers);

     }

     set_phase(active_workers, false /* concurrent */);

     // Leave _parallel_marking_threads at it's

     // value originally calculated in the ConcurrentMark

     // constructor and pass values of the active workers

     // through the gang in the task.

     CMRemarkTask remarkTask(this, active_workers);

     g1h->set_par_threads(active_workers);

     g1h->workers()->run_task(&remarkTask);

     g1h->set_par_threads(0);

   } else {

     G1CollectedHeap::StrongRootsScope srs(g1h);

     // this is remark, so we'll use up all available threads

     uint active_workers = 1;

     set_phase(active_workers, false /* concurrent */);

     CMRemarkTask remarkTask(this, active_workers);

     // We will start all available threads, even if we decide that the

     // active_workers will be fewer. The extra ones will just bail out

     // immediately.

     remarkTask.work(0);

   }

   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

   guarantee(satb_mq_set.completed_buffers_num() == 0, "invariant");

   print_stats();

 #if VERIFY_OBJS_PROCESSED

   if (_scan_obj_cl.objs_processed != ThreadLocalObjQueue::objs_enqueued) {

     gclog_or_tty->print_cr("Processed = %d, enqueued = %d.",

                            _scan_obj_cl.objs_processed,

                            ThreadLocalObjQueue::objs_enqueued);

     guarantee(_scan_obj_cl.objs_processed ==

               ThreadLocalObjQueue::objs_enqueued,

               "Different number of objs processed and enqueued.");

   }

 #endif

 }

 #ifndef PRODUCT

 class PrintReachableOopClosure: public OopClosure {

 private:

   G1CollectedHeap* _g1h;

   outputStream*    _out;

   VerifyOption     _vo;

   bool             _all;

 public:

   PrintReachableOopClosure(outputStream* out,

                            VerifyOption  vo,

                            bool          all) :

     _g1h(G1CollectedHeap::heap()),

     _out(out), _vo(vo), _all(all) { }

   void do_oop(narrowOop* p) { do_oop_work(p); }

   void do_oop(      oop* p) { do_oop_work(p); }

   template <class T> void do_oop_work(T* p) {

     oop         obj = oopDesc::load_decode_heap_oop(p);

     const char* str = NULL;

     const char* str2 = "";

     if (obj == NULL) {

       str = "";

     } else if (!_g1h->is_in_g1_reserved(obj)) {

       str = " O";

     } else {

       HeapRegion* hr  = _g1h->heap_region_containing(obj);

       guarantee(hr != NULL, "invariant");

       bool over_tams = false;

       bool marked = false;

       switch (_vo) {

         case VerifyOption_G1UsePrevMarking:

           over_tams = hr->obj_allocated_since_prev_marking(obj);

           marked = _g1h->isMarkedPrev(obj);

           break;

         case VerifyOption_G1UseNextMarking:

           over_tams = hr->obj_allocated_since_next_marking(obj);

           marked = _g1h->isMarkedNext(obj);

           break;

         case VerifyOption_G1UseMarkWord:

           marked = obj->is_gc_marked();

           break;

         default:

           ShouldNotReachHere();

       }

       if (over_tams) {

         str = " >";

         if (marked) {

           str2 = " AND MARKED";

         }

       } else if (marked) {

         str = " M";

       } else {

         str = " NOT";

       }

     }

     _out->print_cr("  "PTR_FORMAT": "PTR_FORMAT"%s%s",

                    p, (void*) obj, str, str2);

   }

 };

 class PrintReachableObjectClosure : public ObjectClosure {

 private:

   G1CollectedHeap* _g1h;

   outputStream*    _out;

   VerifyOption     _vo;

   bool             _all;

   HeapRegion*      _hr;

 public:

   PrintReachableObjectClosure(outputStream* out,

                               VerifyOption  vo,

                               bool          all,

                               HeapRegion*   hr) :

     _g1h(G1CollectedHeap::heap()),

     _out(out), _vo(vo), _all(all), _hr(hr) { }

   void do_object(oop o) {

     bool over_tams = false;

     bool marked = false;

     switch (_vo) {

       case VerifyOption_G1UsePrevMarking:

         over_tams = _hr->obj_allocated_since_prev_marking(o);

         marked = _g1h->isMarkedPrev(o);

         break;

       case VerifyOption_G1UseNextMarking:

         over_tams = _hr->obj_allocated_since_next_marking(o);

         marked = _g1h->isMarkedNext(o);

         break;

       case VerifyOption_G1UseMarkWord:

         marked = o->is_gc_marked();

         break;

       default:

         ShouldNotReachHere();

     }

     bool print_it = _all || over_tams || marked;

     if (print_it) {

       _out->print_cr(" "PTR_FORMAT"%s",

                      o, (over_tams) ? " >" : (marked) ? " M" : "");

       PrintReachableOopClosure oopCl(_out, _vo, _all);

       o->oop_iterate(&oopCl);

     }

   }

 };

 class PrintReachableRegionClosure : public HeapRegionClosure {

 private:

   outputStream* _out;

   VerifyOption  _vo;

   bool          _all;

 public:

   bool doHeapRegion(HeapRegion* hr) {

     HeapWord* b = hr->bottom();

     HeapWord* e = hr->end();

     HeapWord* t = hr->top();

     HeapWord* p = NULL;

     switch (_vo) {

       case VerifyOption_G1UsePrevMarking:

         p = hr->prev_top_at_mark_start();

         break;

       case VerifyOption_G1UseNextMarking:

         p = hr->next_top_at_mark_start();

         break;

       case VerifyOption_G1UseMarkWord:

         // When we are verifying marking using the mark word

         // TAMS has no relevance.

         assert(p == NULL, "post-condition");

         break;

       default:

         ShouldNotReachHere();

     }

     _out->print_cr("** ["PTR_FORMAT", "PTR_FORMAT"] top: "PTR_FORMAT" "

                    "TAMS: "PTR_FORMAT, b, e, t, p);

     _out->cr();

     HeapWord* from = b;

     HeapWord* to   = t;

     if (to > from) {

       _out->print_cr("Objects in ["PTR_FORMAT", "PTR_FORMAT"]", from, to);

       _out->cr();

       PrintReachableObjectClosure ocl(_out, _vo, _all, hr);

       hr->object_iterate_mem_careful(MemRegion(from, to), &ocl);

       _out->cr();

     }

     return false;

   }

   PrintReachableRegionClosure(outputStream* out,

                               VerifyOption  vo,

                               bool          all) :

     _out(out), _vo(vo), _all(all) { }

 };

 static const char* verify_option_to_tams(VerifyOption vo) {

   switch (vo) {

     case VerifyOption_G1UsePrevMarking:

       return "PTAMS";

     case VerifyOption_G1UseNextMarking:

       return "NTAMS";

     default:

       return "NONE";

   }

 }

 void ConcurrentMark::print_reachable(const char* str,

                                      VerifyOption vo,

                                      bool all) {

   gclog_or_tty->cr();

   gclog_or_tty->print_cr("== Doing heap dump... ");

   if (G1PrintReachableBaseFile == NULL) {

     gclog_or_tty->print_cr("  #### error: no base file defined");

     return;

   }

   if (strlen(G1PrintReachableBaseFile) + 1 + strlen(str) >

       (JVM_MAXPATHLEN - 1)) {

     gclog_or_tty->print_cr("  #### error: file name too long");

     return;

   }

   char file_name[JVM_MAXPATHLEN];

   sprintf(file_name, "%s.%s", G1PrintReachableBaseFile, str);

   gclog_or_tty->print_cr("  dumping to file %s", file_name);

   fileStream fout(file_name);

   if (!fout.is_open()) {

     gclog_or_tty->print_cr("  #### error: could not open file");

     return;

   }

   outputStream* out = &fout;

   out->print_cr("-- USING %s", verify_option_to_tams(vo));

   out->cr();

   out->print_cr("--- ITERATING OVER REGIONS");

   out->cr();

   PrintReachableRegionClosure rcl(out, vo, all);

   _g1h->heap_region_iterate(&rcl);

   out->cr();

   gclog_or_tty->print_cr("  done");

   gclog_or_tty->flush();

 }

 #endif // PRODUCT

 void ConcurrentMark::clearRangePrevBitmap(MemRegion mr) {

   // Note we are overriding the read-only view of the prev map here, via

   // the cast.

   ((CMBitMap*)_prevMarkBitMap)->clearRange(mr);

 }

 void ConcurrentMark::clearRangeNextBitmap(MemRegion mr) {

   _nextMarkBitMap->clearRange(mr);