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

 /*

  * Copyright (c) 2001, 2014, 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 "code/codeCache.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 "gc_implementation/shared/gcTimer.hpp"

 #include "gc_implementation/shared/gcTrace.hpp"

 #include "gc_implementation/shared/gcTraceTime.hpp"

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

 #include "runtime/prefetch.inline.hpp"

 #include "services/memTracker.hpp"

 // Concurrent marking bit map wrapper

 CMBitMapRO::CMBitMapRO(int shifter) :

   _bm(),

   _shifter(shifter) {

   _bmStartWord = 0;

   _bmWordSize = 0;

 }

 HeapWord* CMBitMapRO::getNextMarkedWordAddress(const HeapWord* addr,

                                                const 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(const HeapWord* addr,

                                                  const 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 heap_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*)(heap_rs.base()) &&

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

 }

 #endif

 void CMBitMapRO::print_on_error(outputStream* st, const char* prefix) const {

   _bm.print_on_error(st, prefix);

 }

 bool CMBitMap::allocate(ReservedSpace heap_rs) {

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

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

   ReservedSpace brs(ReservedSpace::allocation_align_size_up(

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

   if (!brs.is_reserved()) {

     warning("ConcurrentMark marking bit map allocation failure");

     return false;

   }

   MemTracker::record_virtual_memory_type((address)brs.base(), mtGC);

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

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

   if (!_virtual_space.initialize(brs, brs.size())) {

     warning("ConcurrentMark marking bit map backing store failure");

     return false;

   }

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

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

   _bm.set_map((BitMap::bm_word_t*)_virtual_space.low());

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

          _bmWordSize, "inconsistency in bit map sizing");

   _bm.set_size(_bmWordSize >> _shifter);

   return true;

 }

 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

 {}

 bool CMMarkStack::allocate(size_t capacity) {

   // allocate a stack of the requisite depth

   ReservedSpace rs(ReservedSpace::allocation_align_size_up(capacity * sizeof(oop)));

   if (!rs.is_reserved()) {

     warning("ConcurrentMark MarkStack allocation failure");

     return false;

   }

   MemTracker::record_virtual_memory_type((address)rs.base(), mtGC);

   if (!_virtual_space.initialize(rs, rs.size())) {

     warning("ConcurrentMark MarkStack backing store failure");

     // Release the virtual memory reserved for the marking stack

     rs.release();

     return false;

   }

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

          "Didn't reserve backing store for all of ConcurrentMark stack?");

   _base = (oop*) _virtual_space.low();

   setEmpty();

   _capacity = (jint) capacity;

   _saved_index = -1;

   _should_expand = false;

   NOT_PRODUCT(_max_depth = 0);

   return true;

 }

 void CMMarkStack::expand() {

   // Called, during remark, if we've overflown the marking stack during marking.

   assert(isEmpty(), "stack should been emptied while handling overflow");

   assert(_capacity <= (jint) MarkStackSizeMax, "stack bigger than permitted");

   // Clear expansion flag

   _should_expand = false;

   if (_capacity == (jint) MarkStackSizeMax) {

     if (PrintGCDetails && Verbose) {

       gclog_or_tty->print_cr(" (benign) Can't expand marking stack capacity, at max size limit");

     }

     return;

   }

   // Double capacity if possible

   jint new_capacity = MIN2(_capacity*2, (jint) MarkStackSizeMax);

   // Do not give up existing stack until we have managed to

   // get the double capacity that we desired.

   ReservedSpace rs(ReservedSpace::allocation_align_size_up(new_capacity *

                                                            sizeof(oop)));

   if (rs.is_reserved()) {

     // Release the backing store associated with old stack

     _virtual_space.release();

     // Reinitialize virtual space for new stack

     if (!_virtual_space.initialize(rs, rs.size())) {

       fatal("Not enough swap for expanded marking stack capacity");

     }

     _base = (oop*)(_virtual_space.low());

     _index = 0;

     _capacity = new_capacity;

   } else {

     if (PrintGCDetails && Verbose) {

       // Failed to double capacity, continue;

       gclog_or_tty->print(" (benign) Failed to expand marking stack capacity from "

                           SIZE_FORMAT"K to " SIZE_FORMAT"K",

                           _capacity / K, new_capacity / K);

     }

   }

 }

 void CMMarkStack::set_should_expand() {

   // If we're resetting the marking state because of an

   // marking stack overflow, record that we should, if

   // possible, expand the stack.

   _should_expand = _cm->has_overflown();

 }

 CMMarkStack::~CMMarkStack() {

   if (_base != NULL) {

     _base = NULL;

     _virtual_space.release();

   }

 }

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

   }

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

 }

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

 }

 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(G1CollectedHeap* g1h, ReservedSpace heap_rs) :

   _g1h(g1h),

   _markBitMap1(log2_intptr(MinObjAlignment)),

   _markBitMap2(log2_intptr(MinObjAlignment)),

   _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)(g1h->max_regions()), false /* in_resource_area*/),

   _card_bm((heap_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_worker_id(MAX2((uint)ParallelGCThreads, 1U)),

   // _active_tasks set in set_non_marking_state

   // _tasks set inside the constructor

   _task_queues(new CMTaskQueueSet((int) _max_worker_id)),

   _terminator(ParallelTaskTerminator((int) _max_worker_id, _task_queues)),

   _has_overflown(false),

   _concurrent(false),

   _has_aborted(false),

   _aborted_gc_id(GCId::undefined()),

   _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),

   _completed_initialization(false) {

   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 = " INTPTR_FORMAT, p2i(_heap_start), p2i(_heap_end));

   }

   if (!_markBitMap1.allocate(heap_rs)) {

     warning("Failed to allocate first CM bit map");

     return;

   }

   if (!_markBitMap2.allocate(heap_rs)) {

     warning("Failed to allocate second CM bit map");

     return;

   }

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

   if (_cmThread->osthread() == NULL) {

       vm_shutdown_during_initialization("Could not create ConcurrentMarkThread");

   }

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

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

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

   SATBMarkQueueSet& satb_qs = JavaThread::satb_mark_queue_set();

   satb_qs.set_buffer_size(G1SATBBufferSize);

   _root_regions.init(_g1h, this);

   if (ConcGCThreads > ParallelGCThreads) {

     warning("Can't have more ConcGCThreads (" UINTX_FORMAT ") "

             "than ParallelGCThreads (" UINTX_FORMAT ").",

             ConcGCThreads, ParallelGCThreads);

     return;

   }

   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 (!FLAG_IS_DEFAULT(ConcGCThreads) && ConcGCThreads > 0) {

       // Note: ConcGCThreads has precedence over G1MarkingOverheadPercent

       // if both are set

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

       FLAG_SET_ERGO(uintx, ConcGCThreads, (uint) marking_thread_num);

       _sleep_factor             = sleep_factor;

       _marking_task_overhead    = marking_task_overhead;

     } else {

       // Calculate the number of parallel marking threads by scaling

       // the number of parallel GC threads.

       uint marking_thread_num = scale_parallel_threads((uint) ParallelGCThreads);

       FLAG_SET_ERGO(uintx, ConcGCThreads, marking_thread_num);

       _sleep_factor             = 0.0;

       _marking_task_overhead    = 1.0;

     }

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

     _parallel_marking_threads = (uint) ConcGCThreads;

     _max_parallel_marking_threads = _parallel_marking_threads;

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

     }

   }

   if (FLAG_IS_DEFAULT(MarkStackSize)) {

     uintx mark_stack_size =

       MIN2(MarkStackSizeMax,

           MAX2(MarkStackSize, (uintx) (parallel_marking_threads() * TASKQUEUE_SIZE)));

     // Verify that the calculated value for MarkStackSize is in range.

     // It would be nice to use the private utility routine from Arguments.

     if (!(mark_stack_size >= 1 && mark_stack_size <= MarkStackSizeMax)) {

       warning("Invalid value calculated for MarkStackSize (" UINTX_FORMAT "): "

               "must be between " UINTX_FORMAT " and " UINTX_FORMAT,

               mark_stack_size, (uintx) 1, MarkStackSizeMax);

       return;

     }

     FLAG_SET_ERGO(uintx, MarkStackSize, mark_stack_size);

   } else {

     // Verify MarkStackSize is in range.

     if (FLAG_IS_CMDLINE(MarkStackSize)) {

       if (FLAG_IS_DEFAULT(MarkStackSizeMax)) {

         if (!(MarkStackSize >= 1 && MarkStackSize <= MarkStackSizeMax)) {

           warning("Invalid value specified for MarkStackSize (" UINTX_FORMAT "): "

                   "must be between " UINTX_FORMAT " and " UINTX_FORMAT,

                   MarkStackSize, (uintx) 1, MarkStackSizeMax);

           return;

         }

       } else if (FLAG_IS_CMDLINE(MarkStackSizeMax)) {

         if (!(MarkStackSize >= 1 && MarkStackSize <= MarkStackSizeMax)) {

           warning("Invalid value specified for MarkStackSize (" UINTX_FORMAT ")"

                   " or for MarkStackSizeMax (" UINTX_FORMAT ")",

                   MarkStackSize, MarkStackSizeMax);

           return;

         }

       }

     }

   }

   if (!_markStack.allocate(MarkStackSize)) {

     warning("Failed to allocate CM marking stack");

     return;

   }

   _tasks = NEW_C_HEAP_ARRAY(CMTask*, _max_worker_id, mtGC);

   _accum_task_vtime = NEW_C_HEAP_ARRAY(double, _max_worker_id, mtGC);

   _count_card_bitmaps = NEW_C_HEAP_ARRAY(BitMap,  _max_worker_id, mtGC);

   _count_marked_bytes = NEW_C_HEAP_ARRAY(size_t*, _max_worker_id, mtGC);

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

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

   _active_tasks = _max_worker_id;

   size_t max_regions = (size_t) _g1h->max_regions();

   for (uint i = 0; i < _max_worker_id; ++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, max_regions, mtGC);

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

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

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

   set_non_marking_state();

   _completed_initialization = true;

 }

 void ConcurrentMark::update_heap_boundaries(MemRegion bounds, 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;

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

   HeapWord* new_end = bounds.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

   reset_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 (uint i = 0; i < _max_worker_id; ++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::reset_marking_state(bool clear_overflow) {

   _markStack.set_should_expand();

   _markStack.setEmpty();        // Also clears the _markStack overflow flag

   if (clear_overflow) {

     clear_has_overflown();

   } else {

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

   }

   _finger = _heap_start;

   for (uint i = 0; i < _max_worker_id; ++i) {

     CMTaskQueue* queue = _task_queues->queue(i);

     queue->set_empty();

   }

 }

 void ConcurrentMark::set_concurrency(uint active_tasks) {

   assert(active_tasks <= _max_worker_id, "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);

 }

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

   set_concurrency(active_tasks);

   _concurrent = concurrent;

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

   for (uint i = 0; i < _max_worker_id; ++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(out_of_regions(),

            err_msg("only way to get here: _finger: "PTR_FORMAT", _heap_end: "PTR_FORMAT,

                    p2i(_finger), p2i(_heap_end)));

     update_heap_boundaries(_g1h->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.

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

 }

 bool ConcurrentMark::nextMarkBitmapIsClear() {

   return _nextMarkBitMap->getNextMarkedWordAddress(_heap_start, _heap_end) == _heap_end;

 }

 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(uint worker_id) {

   if (verbose_low()) {

     gclog_or_tty->print_cr("[%u] entering first barrier", worker_id);

   }

   if (concurrent()) {

     SuspendibleThreadSet::leave();

   }

   bool barrier_aborted = !_first_overflow_barrier_sync.enter();

   if (concurrent()) {

     SuspendibleThreadSet::join();

   }

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

   // more work

   if (verbose_low()) {

     if (barrier_aborted) {

       gclog_or_tty->print_cr("[%u] aborted first barrier", worker_id);

     } else {

       gclog_or_tty->print_cr("[%u] leaving first barrier", worker_id);

     }

   }

   if (barrier_aborted) {

     // If the barrier aborted we ignore the overflow condition and

     // just abort the whole marking phase as quickly as possible.

     return;

   }

   // If we're executing the concurrent phase of marking, reset the marking

   // state; otherwise the marking state is reset after reference processing,

   // during the remark pause.

   // If we reset here as a result of an overflow during the remark we will

   // see assertion failures from any subsequent set_concurrency_and_phase()

   // calls.

   if (concurrent()) {

     // let the task associated with with worker 0 do this

     if (worker_id == 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.

       reset_marking_state(true /* clear_overflow */);

       force_overflow()->update();

       if (G1Log::fine()) {

         gclog_or_tty->gclog_stamp(concurrent_gc_id());

         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(uint worker_id) {

   if (verbose_low()) {

     gclog_or_tty->print_cr("[%u] entering second barrier", worker_id);

   }

   if (concurrent()) {

     SuspendibleThreadSet::leave();

   }

   bool barrier_aborted = !_second_overflow_barrier_sync.enter();

   if (concurrent()) {

     SuspendibleThreadSet::join();

   }

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

   if (verbose_low()) {

     if (barrier_aborted) {

       gclog_or_tty->print_cr("[%u] aborted second barrier", worker_id);

     } else {

       gclog_or_tty->print_cr("[%u] leaving second barrier", worker_id);

     }

   }

 }

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

     SuspendibleThreadSet::join();

     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_termination */,

                                   false /* is_serial*/);

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

           SuspendibleThreadSet::leave();

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

           SuspendibleThreadSet::join();

         }

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

     SuspendibleThreadSet::leave();

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

   // Start of concurrent marking.

   ClassLoaderDataGraph::clear_claimed_marks();

   // 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 (use_parallel_marking_threads()) {

       _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_concurrency_and_phase()"

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

   CMConcurrentMarkingTask markingTask(this, cmThread());

   if (use_parallel_marking_threads()) {

     _parallel_workers->set_active_workers((int)active_workers);

     // Don't set _n_par_threads because it affects MT in process_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

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

     Universe::verify(VerifyOption_G1UsePrevMarking,

                      " VerifyDuringGC:(before)");

   }

   g1h->check_bitmaps("Remark Start");

   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;

     if (G1TraceMarkStackOverflow) {

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

     }

     // Verify the heap w.r.t. the previous marking bitmap.

     if (VerifyDuringGC) {

       HandleMark hm;  // handle scope

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

       Universe::verify(VerifyOption_G1UsePrevMarking,

                        " VerifyDuringGC:(overflow)");

     }

     // Clear the marking state because we will be restarting

     // marking due to overflowing the global mark stack.

     reset_marking_state();

   } 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

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

       Universe::verify(VerifyOption_G1UseNextMarking,

                        " VerifyDuringGC:(after)");

     }

     g1h->check_bitmaps("Remark End");

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

     // Completely reset the marking state since marking completed

     set_non_marking_state();

   }

   // Expand the marking stack, if we have to and if we can.

   if (_markStack.should_expand()) {

     _markStack.expand();

   }

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

   G1CMIsAliveClosure is_alive(g1h);

   g1h->gc_tracer_cm()->report_object_count_after_gc(&is_alive);

 }

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

 // liveness counting data.

 class CMCountDataClosureBase: public HeapRegionClosure {

 protected:

   G1CollectedHeap* _g1h;

   ConcurrentMark* _cm;

   CardTableModRefBS* _ct_bs;

   BitMap* _region_bm;

   BitMap* _card_bm;

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

       BitMap::idx_t end_index = (BitMap::idx_t) hr->last_hc_index();

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

     }

   }

 public:

   CMCountDataClosureBase(G1CollectedHeap* g1h,

                          BitMap* region_bm, BitMap* card_bm):

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

     _ct_bs((CardTableModRefBS*) (g1h->barrier_set())),

     _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, G1CollectedHeap* g1h,

                          BitMap* region_bm, BitMap* card_bm) :

     CMCountDataClosureBase(g1h, 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* ntams = hr->next_top_at_mark_start();

     HeapWord* start = hr->bottom();

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

            err_msg("Preconditions not met - "

                    "start: "PTR_FORMAT", ntams: "PTR_FORMAT", end: "PTR_FORMAT,

                    p2i(start), p2i(ntams), p2i(hr->end())));

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

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

     size_t marked_bytes = 0;

     while (start < ntams) {

       oop obj = oop(start);

       int obj_sz = obj->size();

       HeapWord* obj_end = start + obj_sz;

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

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

       // Note: if we're looking at the last region in heap - obj_end

       // could be actually just beyond the end of the heap; end_idx

       // will then correspond to a (non-existent) card that is also

       // just beyond the heap.

       if (_g1h->is_in_g1_reserved(obj_end) && !_ct_bs->is_card_aligned(obj_end)) {

         // end of object is not card aligned - increment to cover

         // all the cards spanned by the object

         end_idx += 1;

       }

       // Set the bits in the card BM for the cards spanned by this object.

       _cm->set_card_bitmap_range(_card_bm, start_idx, end_idx, true /* is_par */);

       // 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_end, ntams);

     }

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

     HeapWord* top = hr->top();

     if (ntams < top) {

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

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

       // Note: if we're looking at the last region in heap - top

       // could be actually just beyond the end of the heap; end_idx

       // will then correspond to a (non-existent) card that is also

       // just beyond the heap.

       if (_g1h->is_in_g1_reserved(top) && !_ct_bs->is_card_aligned(top)) {

         // end of object is not card aligned - increment to cover

         // all the cards spanned by the object

         end_idx += 1;

       }

       _cm->set_card_bitmap_range(_card_bm, start_idx, end_idx, true /* is_par */);

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

   G1CollectedHeap* _g1h;

   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(G1CollectedHeap* g1h,

                                 BitMap* region_bm,

                                 BitMap* card_bm,

                                 BitMap* exp_region_bm,

                                 BitMap* exp_card_bm,

                                 bool verbose) :

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

     _calc_cl(_cm->nextMarkBitMap(), g1h, 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), p2i(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(_g1h,

                                             _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(G1CollectedHeap* g1h,

                               BitMap* region_bm,

                               BitMap* card_bm) :

     CMCountDataClosureBase(g1h, 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 in the card bitmap for [ntams, top)

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

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

       // Note: if we're looking at the last region in heap - top

       // could be actually just beyond the end of the heap; end_idx

       // will then correspond to a (non-existent) card that is also

       // just beyond the heap.

       if (_g1h->is_in_g1_reserved(top) && !_ct_bs->is_card_aligned(top)) {

         // end of object is not card aligned - increment to cover

         // all the cards spanned by the object

         end_idx += 1;

       }

       assert(end_idx <= _card_bm->size(),

              err_msg("oob: end_idx=  "SIZE_FORMAT", bitmap size= "SIZE_FORMAT,

                      end_idx, _card_bm->size()));

       assert(start_idx < _card_bm->size(),

              err_msg("oob: start_idx=  "SIZE_FORMAT", bitmap size= "SIZE_FORMAT,

                      start_idx, _card_bm->size()));

       _cm->set_card_bitmap_range(_card_bm, start_idx, end_idx, true /* is_par */);

     }

     // 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(_g1h,

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

   size_t _max_live_bytes;

   uint _regions_claimed;

   size_t _freed_bytes;

   FreeRegionList* _local_cleanup_list;

   HeapRegionSetCount _old_regions_removed;

   HeapRegionSetCount _humongous_regions_removed;

   HRRSCleanupTask* _hrrs_cleanup_task;

   double _claimed_region_time;

   double _max_region_time;

 public:

   G1NoteEndOfConcMarkClosure(G1CollectedHeap* g1,

                              FreeRegionList* local_cleanup_list,

                              HRRSCleanupTask* hrrs_cleanup_task) :

     _g1(g1),

     _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_regions_removed(),

     _humongous_regions_removed(),

     _hrrs_cleanup_task(hrrs_cleanup_task) { }

   size_t freed_bytes() { return _freed_bytes; }

   const HeapRegionSetCount& old_regions_removed() { return _old_regions_removed; }

   const HeapRegionSetCount& humongous_regions_removed() { return _humongous_regions_removed; }

   bool doHeapRegion(HeapRegion *hr) {

     if (hr->continuesHumongous()) {

       return false;

     }

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

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

     _g1->reset_gc_time_stamps(hr);

     double start = os::elapsedTime();

     _regions_claimed++;

     hr->note_end_of_marking();

     _max_live_bytes += hr->max_live_bytes();

     if (hr->used() > 0 && hr->max_live_bytes() == 0 && !hr->is_young()) {

       _freed_bytes += hr->used();

       hr->set_containing_set(NULL);

       if (hr->isHumongous()) {

         assert(hr->startsHumongous(), "we should only see starts humongous");

         _humongous_regions_removed.increment(1u, hr->capacity());

         _g1->free_humongous_region(hr, _local_cleanup_list, true);

       } else {

         _old_regions_removed.increment(1u, hr->capacity());

         _g1->free_region(hr, _local_cleanup_list, true);

       }

     } else {

       hr->rem_set()->do_cleanup_work(_hrrs_cleanup_task);

     }

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

     HRRSCleanupTask hrrs_cleanup_task;

     G1NoteEndOfConcMarkClosure g1_note_end(_g1h, &local_cleanup_list,

                                            &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->remove_from_old_sets(g1_note_end.old_regions_removed(), g1_note_end.humongous_regions_removed());

     {

       MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

       _g1h->decrement_summary_bytes(g1_note_end.freed_bytes());

       _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()) {

         FreeRegionListIterator iter(&local_cleanup_list);

         while (iter.more_available()) {

           HeapRegion* hr = iter.get_next();

           hr_printer->cleanup(hr);

         }

       }

       _cleanup_list->add_ordered(&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;

   }

   g1h->verify_region_sets_optional();

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

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

     Universe::verify(VerifyOption_G1UsePrevMarking,

                      " VerifyDuringGC:(before)");

   }

   g1h->check_bitmaps("Cleanup Start");

   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(), true);

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

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

   }

   g1h->check_gc_time_stamps();

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

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

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

     Universe::verify(VerifyOption_G1UsePrevMarking,

                      " VerifyDuringGC:(after)");

   }

   g1h->check_bitmaps("Cleanup End");

   g1h->verify_region_sets_optional();

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

   // Clean out dead classes and update Metaspace sizes.

   if (ClassUnloadingWithConcurrentMark) {

     ClassLoaderDataGraph::purge();

   }

   MetaspaceGC::compute_new_size();

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

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

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

   g1h->trace_heap_after_concurrent_cycle();

 }

 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_region(true /* from_head */);

     assert(hr != NULL, "Got NULL from a non-empty list");

     hr->par_clear();

     tmp_free_list.add_ordered(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(&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");

 }

 // Supporting Object and Oop closures for reference discovery

 // and processing in during marking

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

 }

 // 'Keep Alive' oop closure used by both serial parallel reference processing.

 // Uses the CMTask associated with a worker thread (for serial reference

 // processing the CMTask for worker 0 is used) to preserve (mark) and

 // trace referent objects.

 //

 // Using the CMTask and embedded local queues avoids having the worker

 // threads operating on the global mark stack. This reduces the risk

 // of overflowing the stack - which we would rather avoid at this late

 // state. Also using the tasks' local queues removes the potential

 // of the workers interfering with each other that could occur if

 // operating on the global stack.

 class G1CMKeepAliveAndDrainClosure: public OopClosure {

   ConcurrentMark* _cm;

   CMTask*         _task;

   int             _ref_counter_limit;

   int             _ref_counter;

   bool            _is_serial;

  public:

   G1CMKeepAliveAndDrainClosure(ConcurrentMark* cm, CMTask* task, bool is_serial) :

     _cm(cm), _task(task), _is_serial(is_serial),

     _ref_counter_limit(G1RefProcDrainInterval) {

     assert(_ref_counter_limit > 0, "sanity");

     assert(!_is_serial || _task->worker_id() == 0, "only task 0 for serial code");

     _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[%u] we're looking at location "

                                "*"PTR_FORMAT" = "PTR_FORMAT,

                                _task->worker_id(), p2i(p), p2i((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 CMTask::do_marking_step() to

         // process these entries.

         //

         // We call CMTask::do_marking_step() in a loop, which we'll exit if

         // there's nothing more to do (i.e. we're done with the entries that

         // were pushed as a result of the CMTask::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 step has completed.

         do {

           double mark_step_duration_ms = G1ConcMarkStepDurationMillis;

           _task->do_marking_step(mark_step_duration_ms,

                                  false      /* do_termination */,

                                  _is_serial);

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

         _ref_counter = _ref_counter_limit;

       }

     } else {

       if (_cm->verbose_high()) {

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

       }

     }

   }

 };

 // 'Drain' oop closure used by both serial and parallel reference processing.

 // Uses the CMTask associated with a given worker thread (for serial

 // reference processing the CMtask for worker 0 is used). Calls the

 // do_marking_step routine, with an unbelievably large timeout value,

 // to drain the marking data structures of the remaining entries

 // added by the 'keep alive' oop closure above.

 class G1CMDrainMarkingStackClosure: public VoidClosure {

   ConcurrentMark* _cm;

   CMTask*         _task;

   bool            _is_serial;

  public:

   G1CMDrainMarkingStackClosure(ConcurrentMark* cm, CMTask* task, bool is_serial) :

     _cm(cm), _task(task), _is_serial(is_serial) {

     assert(!_is_serial || _task->worker_id() == 0, "only task 0 for serial code");

   }

   void do_void() {

     do {

       if (_cm->verbose_high()) {

         gclog_or_tty->print_cr("\t[%u] Drain: Calling do_marking_step - serial: %s",

                                _task->worker_id(), BOOL_TO_STR(_is_serial));

       }

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

       // and global marking stacks of entries pushed by the 'keep alive'

       // oop closure (an instance of G1CMKeepAliveAndDrainClosure above).

       //

       // CMTask::do_marking_step() 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 a result of applying the 'keep alive'

       // closure to the entries on the discovered ref lists) 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 step has completed.

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

                              true         /* do_termination */,

                              _is_serial);

     } 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) {

     ReferenceProcessor* rp = _g1h->ref_processor_cm();

     assert(rp->processing_is_mt(), "shouldn't be here otherwise");

   }

   virtual void work(uint worker_id) {

     ResourceMark rm;

     HandleMark hm;

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

     G1CMIsAliveClosure g1_is_alive(_g1h);

     G1CMKeepAliveAndDrainClosure g1_par_keep_alive(_cm, task, false /* is_serial */);

     G1CMDrainMarkingStackClosure g1_par_drain(_cm, task, false /* is_serial */);

     _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.");

   assert(_g1h->ref_processor_cm()->processing_is_mt(), "processing is not MT");

   G1CMRefProcTaskProxy proc_task_proxy(proc_task, _g1h, _cm);

   // We need to reset the concurrency level before each

   // proxy task execution, so that the termination protocol

   // and overflow handling in CMTask::do_marking_step() knows

   // how many workers to wait for.

   _cm->set_concurrency(_active_workers);

   _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.");

   assert(_g1h->ref_processor_cm()->processing_is_mt(), "processing is not MT");

   G1CMRefEnqueueTaskProxy enq_task_proxy(enq_task);

   // Not strictly necessary but...

   //

   // We need to reset the concurrency level before each

   // proxy task execution, so that the termination protocol

   // and overflow handling in CMTask::do_marking_step() knows

   // how many workers to wait for.

   _cm->set_concurrency(_active_workers);

   _g1h->set_par_threads(_active_workers);

   _workers->run_task(&enq_task_proxy);

   _g1h->set_par_threads(0);

 }

 void ConcurrentMark::weakRefsWorkParallelPart(BoolObjectClosure* is_alive, bool purged_classes) {

   G1CollectedHeap::heap()->parallel_cleaning(is_alive, true, true, purged_classes);

 }

 // Helper class to get rid of some boilerplate code.

 class G1RemarkGCTraceTime : public GCTraceTime {

   static bool doit_and_prepend(bool doit) {

     if (doit) {

       gclog_or_tty->put(' ');

     }

     return doit;

   }

  public:

   G1RemarkGCTraceTime(const char* title, bool doit)

     : GCTraceTime(title, doit_and_prepend(doit), false, G1CollectedHeap::heap()->gc_timer_cm(),

         G1CollectedHeap::heap()->concurrent_mark()->concurrent_gc_id()) {

   }

 };

 void ConcurrentMark::weakRefsWork(bool clear_all_soft_refs) {

   if (has_overflown()) {

     // Skip processing the discovered references if we have

     // overflown the global marking stack. Reference objects

     // only get discovered once so it is OK to not

     // de-populate the discovered reference lists. We could have,

     // but the only benefit would be that, when marking restarts,

     // less reference objects are discovered.

     return;

   }

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

     }

     GCTraceTime t("GC ref-proc", G1Log::finer(), false, g1h->gc_timer_cm(), concurrent_gc_id());

     ReferenceProcessor* rp = g1h->ref_processor_cm();

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

     // about how reference processing currently works in G1.

     // Set the soft reference policy

     rp->setup_policy(clear_all_soft_refs);

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

     // Instances of the 'Keep Alive' and 'Complete GC' closures used

     // in serial reference processing. Note these closures are also

     // used for serially processing (by the the current thread) the

     // JNI references during parallel reference processing.

     //

     // These closures do not need to synchronize with the worker

     // threads involved in parallel reference processing as these

     // instances are executed serially by the current thread (e.g.

     // reference processing is not multi-threaded and is thus

     // performed by the current thread instead of a gang worker).

     //

     // The gang tasks involved in parallel reference procssing create

     // their own instances of these closures, which do their own

     // synchronization among themselves.

     G1CMKeepAliveAndDrainClosure g1_keep_alive(this, task(0), true /* is_serial */);

     G1CMDrainMarkingStackClosure g1_drain_mark_stack(this, task(0), true /* is_serial */);

     // We need at least one active thread. If reference processing

     // is not multi-threaded we use the current (VMThread) thread,

     // otherwise we use the work gang from the G1CollectedHeap and

     // we utilize all the worker threads we can.

     bool processing_is_mt = rp->processing_is_mt() && g1h->workers() != NULL;

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

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

     // Parallel processing task executor.

     G1CMRefProcTaskExecutor par_task_executor(g1h, this,

                                               g1h->workers(), active_workers);

     AbstractRefProcTaskExecutor* executor = (processing_is_mt ? &par_task_executor : NULL);

     // Set the concurrency level. The phase was already set prior to

     // executing the remark task.

     set_concurrency(active_workers);

     // Set the degree of MT processing here.  If the discovery was done MT,

     // the number of threads involved during discovery could differ from

     // the number of active workers.  This is OK as long as the discovered

     // Reference lists are balanced (see balance_all_queues() and balance_queues()).

     rp->set_active_mt_degree(active_workers);

     // Process the weak references.

     const ReferenceProcessorStats& stats =

         rp->process_discovered_references(&g1_is_alive,

                                           &g1_keep_alive,

                                           &g1_drain_mark_stack,

                                           executor,

                                           g1h->gc_timer_cm(),

                                           concurrent_gc_id());

     g1h->gc_tracer_cm()->report_gc_reference_stats(stats);

     // The do_oop work routines of the keep_alive and drain_marking_stack

     // oop closures will set the has_overflown flag if we overflow the

     // global marking stack.

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

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

     if (_markStack.overflow()) {

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

     }

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

     rp->enqueue_discovered_references(executor);

     rp->verify_no_references_recorded();

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

   }

   if (has_overflown()) {

     // We can not trust g1_is_alive if the marking stack overflowed

     return;

   }

   assert(_markStack.isEmpty(), "Marking should have completed");

   // Unload Klasses, String, Symbols, Code Cache, etc.

   {

     G1RemarkGCTraceTime trace("Unloading", G1Log::finer());

     if (ClassUnloadingWithConcurrentMark) {

       bool purged_classes;

       {

         G1RemarkGCTraceTime trace("System Dictionary Unloading", G1Log::finest());

         purged_classes = SystemDictionary::do_unloading(&g1_is_alive);

       }

       {

         G1RemarkGCTraceTime trace("Parallel Unloading", G1Log::finest());

         weakRefsWorkParallelPart(&g1_is_alive, purged_classes);

       }

     }

     if (G1StringDedup::is_enabled()) {

       G1RemarkGCTraceTime trace("String Deduplication Unlink", G1Log::finest());

       G1StringDedup::unlink(&g1_is_alive);

     }

   }

 }

 void ConcurrentMark::swapMarkBitMaps() {

   CMBitMapRO* temp = _prevMarkBitMap;

   _prevMarkBitMap  = (CMBitMapRO*)_nextMarkBitMap;

   _nextMarkBitMap  = (CMBitMap*)  temp;

 }

 class CMObjectClosure;

 // Closure for iterating over objects, currently only used for

 // processing SATB buffers.

 class CMObjectClosure : public ObjectClosure {

 private:

   CMTask* _task;

 public:

   void do_object(oop obj) {

     _task->deal_with_reference(obj);

   }

   CMObjectClosure(CMTask* task) : _task(task) { }

 };