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

 /*

  * Copyright (c) 2001, 2011, Oracle and/or its affiliates. All rights reserved.

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

  *

  * This code is free software; you can redistribute it and/or modify it

  * under the terms of the GNU General Public License version 2 only, as

  * published by the Free Software Foundation.

  *

  * This code is distributed in the hope that it will be useful, but WITHOUT

  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

  * version 2 for more details (a copy is included in the LICENSE file that

  * accompanied this code).

  *

  * You should have received a copy of the GNU General Public License version

  * 2 along with this work; if not, write to the Free Software Foundation,

  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

  *

  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

  * or visit www.oracle.com if you need additional information or have any

  * questions.

  *

  */

 #include "precompiled.hpp"

 #include "classfile/symbolTable.hpp"

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

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

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

 #include "gc_implementation/g1/g1CollectorPolicy.hpp"

 #include "gc_implementation/g1/g1ErgoVerbose.hpp"

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

 #include "gc_implementation/g1/g1RemSet.hpp"

 #include "gc_implementation/g1/heapRegionRemSet.hpp"

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

 #include "gc_implementation/shared/vmGCOperations.hpp"

 #include "memory/genOopClosures.inline.hpp"

 #include "memory/referencePolicy.hpp"

 #include "memory/resourceArea.hpp"

 #include "oops/oop.inline.hpp"

 #include "runtime/handles.inline.hpp"

 #include "runtime/java.hpp"

 //

 // CMS Bit Map Wrapper

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

   _bm((uintptr_t*)NULL,0),

   _shifter(shifter) {

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

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

   ReservedSpace brs(ReservedSpace::allocation_align_size_up(

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

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

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

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

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

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

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

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

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

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

          _bmWordSize, "inconsistency in bit map sizing");

   _bm.set_size(_bmWordSize >> _shifter);

 }

 HeapWord* CMBitMapRO::getNextMarkedWordAddress(HeapWord* addr,

                                                HeapWord* limit) const {

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

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

                                   HeapWordSize << _shifter);

   size_t addrOffset = heapWordToOffset(addr);

   if (limit == NULL) {

     limit = _bmStartWord + _bmWordSize;

   }

   size_t limitOffset = heapWordToOffset(limit);

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

   HeapWord* nextAddr = offsetToHeapWord(nextOffset);

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

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

          "get_next_one postcondition");

   return nextAddr;

 }

 HeapWord* CMBitMapRO::getNextUnmarkedWordAddress(HeapWord* addr,

                                                  HeapWord* limit) const {

   size_t addrOffset = heapWordToOffset(addr);

   if (limit == NULL) {

     limit = _bmStartWord + _bmWordSize;

   }

   size_t limitOffset = heapWordToOffset(limit);

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

   HeapWord* nextAddr = offsetToHeapWord(nextOffset);

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

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

          "get_next_one postcondition");

   return nextAddr;

 }

 int CMBitMapRO::heapWordDiffToOffsetDiff(size_t diff) const {

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

   return (int) (diff >> _shifter);

 }

 bool CMBitMapRO::iterate(BitMapClosure* cl, MemRegion mr) {

   HeapWord* left  = MAX2(_bmStartWord, mr.start());

   HeapWord* right = MIN2(_bmStartWord + _bmWordSize, mr.end());

   if (right > left) {

     // Right-open interval [leftOffset, rightOffset).

     return _bm.iterate(cl, heapWordToOffset(left), heapWordToOffset(right));

   } else {

     return true;

   }

 }

 void CMBitMapRO::mostly_disjoint_range_union(BitMap*   from_bitmap,

                                              size_t    from_start_index,

                                              HeapWord* to_start_word,

                                              size_t    word_num) {

   _bm.mostly_disjoint_range_union(from_bitmap,

                                   from_start_index,

                                   heapWordToOffset(to_start_word),

                                   word_num);

 }

 #ifndef PRODUCT

 bool CMBitMapRO::covers(ReservedSpace rs) const {

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

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

          "size inconsistency");

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

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

 }

 #endif

 void CMBitMap::clearAll() {

   _bm.clear();

   return;

 }

 void CMBitMap::markRange(MemRegion mr) {

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

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

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

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

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

   // convert address range into offset range

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

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

 }

 void CMBitMap::clearRange(MemRegion mr) {

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

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

   // convert address range into offset range

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

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

 }

 MemRegion CMBitMap::getAndClearMarkedRegion(HeapWord* addr,

                                             HeapWord* end_addr) {

   HeapWord* start = getNextMarkedWordAddress(addr);

   start = MIN2(start, end_addr);

   HeapWord* end   = getNextUnmarkedWordAddress(start);

   end = MIN2(end, end_addr);

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

   MemRegion mr(start, end);

   if (!mr.is_empty()) {

     clearRange(mr);

   }

   return mr;

 }

 CMMarkStack::CMMarkStack(ConcurrentMark* cm) :

   _base(NULL), _cm(cm)

 #ifdef ASSERT

   , _drain_in_progress(false)

   , _drain_in_progress_yields(false)

 #endif

 {}

 void CMMarkStack::allocate(size_t size) {

   _base = NEW_C_HEAP_ARRAY(oop, size);

   if (_base == NULL) {

     vm_exit_during_initialization("Failed to allocate "

                                   "CM region mark stack");

   }

   _index = 0;

   _capacity = (jint) size;

   _oops_do_bound = -1;

   NOT_PRODUCT(_max_depth = 0);

 }

 CMMarkStack::~CMMarkStack() {

   if (_base != NULL) {

     FREE_C_HEAP_ARRAY(oop, _base);

   }

 }

 void CMMarkStack::par_push(oop ptr) {

   while (true) {

     if (isFull()) {

       _overflow = true;

       return;

     }

     // Otherwise...

     jint index = _index;

     jint next_index = index+1;

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

     if (res == index) {

       _base[index] = ptr;

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

       // doesn't seem necessary.

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

       return;

     }

     // Otherwise, we need to try again.

   }

 }

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

   while (true) {

     if (isFull()) {

       _overflow = true;

       return;

     }

     // Otherwise...

     jint index = _index;

     jint next_index = index + n;

     if (next_index > _capacity) {

       _overflow = true;

       return;

     }

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

     if (res == index) {

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

         int ind = index + i;

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

         _base[ind] = ptr_arr[i];

       }

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

       return;

     }

     // Otherwise, we need to try again.

   }

 }

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

   MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

   jint start = _index;

   jint next_index = start + n;

   if (next_index > _capacity) {

     _overflow = true;

     return;

   }

   // Otherwise.

   _index = next_index;

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

     int ind = start + i;

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

     _base[ind] = ptr_arr[i];

   }

 }

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

   MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

   jint index = _index;

   if (index == 0) {

     *n = 0;

     return false;

   } else {

     int k = MIN2(max, index);

     jint new_ind = index - k;

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

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

     }

     _index = new_ind;

     *n = k;

     return true;

   }

 }

 CMRegionStack::CMRegionStack() : _base(NULL) {}

 void CMRegionStack::allocate(size_t size) {

   _base = NEW_C_HEAP_ARRAY(MemRegion, size);

   if (_base == NULL) {

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

   }

   _index = 0;

   _capacity = (jint) size;

 }

 CMRegionStack::~CMRegionStack() {

   if (_base != NULL) {

     FREE_C_HEAP_ARRAY(oop, _base);

   }

 }

 void CMRegionStack::push_lock_free(MemRegion mr) {

   assert(mr.word_size() > 0, "Precondition");

   while (true) {

     jint index = _index;

     if (index >= _capacity) {

       _overflow = true;

       return;

     }

     // Otherwise...

     jint next_index = index+1;

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

     if (res == index) {

       _base[index] = mr;

       return;

     }

     // Otherwise, we need to try again.

   }

 }

 // Lock-free pop of the region stack. Called during the concurrent

 // marking / remark phases. Should only be called in tandem with

 // other lock-free pops.

 MemRegion CMRegionStack::pop_lock_free() {

   while (true) {

     jint index = _index;

     if (index == 0) {

       return MemRegion();

     }

     // Otherwise...

     jint next_index = index-1;

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

     if (res == index) {

       MemRegion mr = _base[next_index];

       if (mr.start() != NULL) {

         assert(mr.end() != NULL, "invariant");

         assert(mr.word_size() > 0, "invariant");

         return mr;

       } else {

         // that entry was invalidated... let's skip it

         assert(mr.end() == NULL, "invariant");

       }

     }

     // Otherwise, we need to try again.

   }

 }

 #if 0

 // The routines that manipulate the region stack with a lock are

 // not currently used. They should be retained, however, as a

 // diagnostic aid.

 void CMRegionStack::push_with_lock(MemRegion mr) {

   assert(mr.word_size() > 0, "Precondition");

   MutexLockerEx x(CMRegionStack_lock, Mutex::_no_safepoint_check_flag);

   if (isFull()) {

     _overflow = true;

     return;

   }

   _base[_index] = mr;

   _index += 1;

 }

 MemRegion CMRegionStack::pop_with_lock() {

   MutexLockerEx x(CMRegionStack_lock, Mutex::_no_safepoint_check_flag);

   while (true) {

     if (_index == 0) {

       return MemRegion();

     }

     _index -= 1;

     MemRegion mr = _base[_index];

     if (mr.start() != NULL) {

       assert(mr.end() != NULL, "invariant");

       assert(mr.word_size() > 0, "invariant");

       return mr;

     } else {

       // that entry was invalidated... let's skip it

       assert(mr.end() == NULL, "invariant");

     }

   }

 }

 #endif

 bool CMRegionStack::invalidate_entries_into_cset() {

   bool result = false;

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

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

     MemRegion mr = _base[i];

     if (mr.start() != NULL) {

       assert(mr.end() != NULL, "invariant");

       assert(mr.word_size() > 0, "invariant");

       HeapRegion* hr = g1h->heap_region_containing(mr.start());

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

       if (hr->in_collection_set()) {

         // The region points into the collection set

         _base[i] = MemRegion();

         result = true;

       }

     } else {

       // that entry was invalidated... let's skip it

       assert(mr.end() == NULL, "invariant");

     }

   }

   return result;

 }

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

     // iterate over the oops in this oop, marking and pushing

     // the ones in CMS generation.

     newOop->oop_iterate(cl);

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

       res = false;

       break;

     }

   }

   debug_only(_drain_in_progress = false);

   return res;

 }

 void CMMarkStack::oops_do(OopClosure* f) {

   if (_index == 0) return;

   assert(_oops_do_bound != -1 && _oops_do_bound <= _index,

          "Bound must be set.");

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

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

   }

   _oops_do_bound = -1;

 }

 bool ConcurrentMark::not_yet_marked(oop obj) const {

   return (_g1h->is_obj_ill(obj)

           || (_g1h->is_in_permanent(obj)

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

 }

 #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

 ConcurrentMark::ConcurrentMark(ReservedSpace rs,

                                int max_regions) :

   _markBitMap1(rs, MinObjAlignment - 1),

   _markBitMap2(rs, MinObjAlignment - 1),

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

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

            CardTableModRefBS::card_shift,

            false /* in_resource_area*/),

   _prevMarkBitMap(&_markBitMap1),

   _nextMarkBitMap(&_markBitMap2),

   _at_least_one_mark_complete(false),

   _markStack(this),

   _regionStack(),

   // _finger set in set_non_marking_state

   _max_task_num(MAX2(ParallelGCThreads, (size_t)1)),

   // _active_tasks set in set_non_marking_state

   // _tasks set inside the constructor

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

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

   _has_overflown(false),

   _concurrent(false),

   _has_aborted(false),

   _restart_for_overflow(false),

   _concurrent_marking_in_progress(false),

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

   CMVerboseLevel verbose_level = (CMVerboseLevel) G1MarkingVerboseLevel;

   if (verbose_level < no_verbose) {

     verbose_level = no_verbose;

   }

   if (verbose_level > high_verbose) {

     verbose_level = high_verbose;

   }

   _verbose_level = verbose_level;

   if (verbose_low()) {

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

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

   }

   _markStack.allocate(MarkStackSize);

   _regionStack.allocate(G1MarkRegionStackSize);

   // Create & start a ConcurrentMark thread.

   _cmThread = new ConcurrentMarkThread(this);

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

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

   _g1h = G1CollectedHeap::heap();

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

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

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

   SATBMarkQueueSet& satb_qs = JavaThread::satb_mark_queue_set();

   satb_qs.set_buffer_size(G1SATBBufferSize);

   _tasks = NEW_C_HEAP_ARRAY(CMTask*, _max_task_num);

   _accum_task_vtime = NEW_C_HEAP_ARRAY(double, _max_task_num);

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

   _active_tasks = _max_task_num;

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

     CMTaskQueue* task_queue = new CMTaskQueue();

     task_queue->initialize();

     _task_queues->register_queue(i, task_queue);

     _tasks[i] = new CMTask(i, this, task_queue, _task_queues);

     _accum_task_vtime[i] = 0.0;

   }

   if (ConcGCThreads > ParallelGCThreads) {

     vm_exit_during_initialization("Can't have more ConcGCThreads "

                                   "than ParallelGCThreads.");

   }

   if (ParallelGCThreads == 0) {

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

     // spawn any marking threads either

     _parallel_marking_threads =   0;

     _sleep_factor             = 0.0;

     _marking_task_overhead    = 1.0;

   } else {

     if (ConcGCThreads > 0) {

       // notice that ConcGCThreads overwrites G1MarkingOverheadPercent

       // if both are set

       _parallel_marking_threads = ConcGCThreads;

       _sleep_factor             = 0.0;

       _marking_task_overhead    = 1.0;

     } else if (G1MarkingOverheadPercent > 0) {

       // we will calculate the number of parallel marking threads

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

       // goal

       double marking_overhead = (double) G1MarkingOverheadPercent / 100.0;

       double overall_cm_overhead =

         (double) MaxGCPauseMillis * marking_overhead /

         (double) GCPauseIntervalMillis;

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

       double marking_thread_num = ceil(overall_cm_overhead / cpu_ratio);

       double marking_task_overhead =

         overall_cm_overhead / marking_thread_num *

                                                 (double) os::processor_count();

       double sleep_factor =

                          (1.0 - marking_task_overhead) / marking_task_overhead;

       _parallel_marking_threads = (size_t) marking_thread_num;

       _sleep_factor             = sleep_factor;

       _marking_task_overhead    = marking_task_overhead;

     } else {

       _parallel_marking_threads = MAX2((ParallelGCThreads + 2) / 4, (size_t)1);

       _sleep_factor             = 0.0;

       _marking_task_overhead    = 1.0;

     }

     if (parallel_marking_threads() > 1) {

       _cleanup_task_overhead = 1.0;

     } else {

       _cleanup_task_overhead = marking_task_overhead();

     }

     _cleanup_sleep_factor =

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

 #if 0

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

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

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

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

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

 #endif

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

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

          (int) _parallel_marking_threads, false, true);

     if (_parallel_workers == NULL) {

       vm_exit_during_initialization("Failed necessary allocation.");

     } else {

       _parallel_workers->initialize_workers();

     }

   }

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

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

   set_non_marking_state();

 }

 void ConcurrentMark::update_g1_committed(bool force) {

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

   // update _heap_end. This has a subtle and important

   // side-effect. Imagine that two evacuation pauses happen between

   // marking completion and remark. The first one can grow the

   // heap (hence now the finger is below the heap end). Then, the

   // second one could unnecessarily push regions on the region

   // stack. This causes the invariant that the region stack is empty

   // at the beginning of remark to be false. By ensuring that we do

   // not observe heap expansions after marking is complete, then we do

   // not have this problem.

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

   MemRegion committed = _g1h->g1_committed();

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

   HeapWord* new_end = committed.end();

   if (new_end > _heap_end) {

     // The heap has been expanded.

     _heap_end = new_end;

   }

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

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

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

   // do nothing.

 }

 void ConcurrentMark::reset() {

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

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

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

   // inactive.

   MemRegion committed = _g1h->g1_committed();

   _heap_start = committed.start();

   _heap_end   = committed.end();

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

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

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

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

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

   clear_marking_state();

   if (verbose_low()) {

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

   }

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

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

   // of them ready.

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

     _tasks[i]->reset(_nextMarkBitMap);

   }

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

   // pause with initial mark piggy-backed

   set_concurrent_marking_in_progress();

 }

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

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

   _active_tasks = active_tasks;

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

   // number of active threads for this phase.

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

   _first_overflow_barrier_sync.set_n_workers((int) active_tasks);

   _second_overflow_barrier_sync.set_n_workers((int) active_tasks);

   _concurrent = concurrent;

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

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

     _tasks[i]->set_concurrent(concurrent);

   if (concurrent) {

     set_concurrent_marking_in_progress();

   } else {

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

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

     // in a STW phase.

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

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

     update_g1_committed(true);

   }

 }

 void ConcurrentMark::set_non_marking_state() {

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

   // not doing marking.

   clear_marking_state();

   _active_tasks = 0;

   clear_concurrent_marking_in_progress();

 }

 ConcurrentMark::~ConcurrentMark() {

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

     delete _task_queues->queue(i);

     delete _tasks[i];

   }

   delete _task_queues;

   FREE_C_HEAP_ARRAY(CMTask*, _max_task_num);

 }

 // This closure is used to mark refs into the g1 generation

 // from external roots in the CMS bit map.

 // Called at the first checkpoint.

 //

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

   }

   // Repeat the asserts from above.

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

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

 }

 class NoteStartOfMarkHRClosure: public HeapRegionClosure {

 public:

   bool doHeapRegion(HeapRegion* r) {

     if (!r->continuesHumongous()) {

       r->note_start_of_marking(true);

     }

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

 }

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

   // For each region note start of marking.

   NoteStartOfMarkHRClosure startcl;

   g1h->heap_region_iterate(&startcl);

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

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

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

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

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

 }

 /*

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

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

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

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

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

  * waiting for the other threads to sync up too.

  *

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

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

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

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

  * operating concurrently.

  *

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

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

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

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

  * doesn't manipulate any data structures afterwards.

  */

 void ConcurrentMark::enter_first_sync_barrier(int task_num) {

   if (verbose_low()) {

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

   }

   if (concurrent()) {

     ConcurrentGCThread::stsLeave();

   }

   _first_overflow_barrier_sync.enter();

   if (concurrent()) {

     ConcurrentGCThread::stsJoin();

   }

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

   // more work

   if (verbose_low()) {

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

   }

   // let task 0 do this

   if (task_num == 0) {

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

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

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

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

     // marking.

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

     force_overflow()->update();

     if (PrintGC) {

       gclog_or_tty->date_stamp(PrintGCDateStamps);

       gclog_or_tty->stamp(PrintGCTimeStamps);

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

     }

   }

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

   // then go into the second barrier

 }

 void ConcurrentMark::enter_second_sync_barrier(int task_num) {

   if (verbose_low()) {

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

   }

   if (concurrent()) {

     ConcurrentGCThread::stsLeave();

   }

   _second_overflow_barrier_sync.enter();

   if (concurrent()) {

     ConcurrentGCThread::stsJoin();

   }

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

   if (verbose_low()) {

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

   }

 }

 #ifndef PRODUCT

 void ForceOverflowSettings::init() {

   _num_remaining = G1ConcMarkForceOverflow;

   _force = false;

   update();

 }

 void ForceOverflowSettings::update() {

   if (_num_remaining > 0) {

     _num_remaining -= 1;

     _force = true;

   } else {

     _force = false;

   }

 }

 bool ForceOverflowSettings::should_force() {

   if (_force) {

     _force = false;

     return true;

   } else {

     return false;

   }

 }

 #endif // !PRODUCT

 void ConcurrentMark::grayRoot(oop p) {

   HeapWord* addr = (HeapWord*) p;

   // We can't really check against _heap_start and _heap_end, since it

   // is possible during an evacuation pause with piggy-backed

   // initial-mark that the committed space is expanded during the

   // pause without CM observing this change. So the assertions below

   // is a bit conservative; but better than nothing.

   assert(_g1h->g1_committed().contains(addr),

          "address should be within the heap bounds");

   if (!_nextMarkBitMap->isMarked(addr)) {

     _nextMarkBitMap->parMark(addr);

   }

 }

 void ConcurrentMark::grayRegionIfNecessary(MemRegion mr) {

   // The objects on the region have already been marked "in bulk" by

   // the caller. We only need to decide whether to push the region on

   // the region stack or not.

   if (!concurrent_marking_in_progress() || !_should_gray_objects) {

     // We're done with marking and waiting for remark. We do not need to

     // push anything else on the region stack.

     return;

   }

   HeapWord* finger = _finger;

   if (verbose_low()) {

     gclog_or_tty->print_cr("[global] attempting to push "

                            "region ["PTR_FORMAT", "PTR_FORMAT"), finger is at "

                            PTR_FORMAT, mr.start(), mr.end(), finger);

   }

   if (mr.start() < finger) {

     // The finger is always heap region aligned and it is not possible

     // for mr to span heap regions.

     assert(mr.end() <= finger, "invariant");

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

     assert(mr.start() <= mr.end(),

            "region boundaries should fall within the committed space");

     assert(_heap_start <= mr.start(),

            "region boundaries should fall within the committed space");

     assert(mr.end() <= _heap_end,

            "region boundaries should fall within the committed space");

     if (verbose_low()) {

       gclog_or_tty->print_cr("[global] region ["PTR_FORMAT", "PTR_FORMAT") "

                              "below the finger, pushing it",

                              mr.start(), mr.end());

     }

     if (!region_stack_push_lock_free(mr)) {

       if (verbose_low()) {

         gclog_or_tty->print_cr("[global] region stack has overflown.");

       }

     }

   }

 }

 void ConcurrentMark::markAndGrayObjectIfNecessary(oop p) {

   // The object is not marked by the caller. We need to at least mark

   // it and maybe push in on the stack.

   HeapWord* addr = (HeapWord*)p;

   if (!_nextMarkBitMap->isMarked(addr)) {

     // We definitely need to mark it, irrespective whether we bail out

     // because we're done with marking.

     if (_nextMarkBitMap->parMark(addr)) {

       if (!concurrent_marking_in_progress() || !_should_gray_objects) {

         // If we're done with concurrent marking and we're waiting for

         // remark, then we're not pushing anything on the stack.

         return;

       }

       // No OrderAccess:store_load() is needed. It is implicit in the

       // CAS done in parMark(addr) above

       HeapWord* finger = _finger;

       if (addr < finger) {

         if (!mark_stack_push(oop(addr))) {

           if (verbose_low()) {

             gclog_or_tty->print_cr("[global] global stack overflow "

                                    "during parMark");

           }

         }

       }

     }

   }

 }

 class CMConcurrentMarkingTask: public AbstractGangTask {

 private:

   ConcurrentMark*       _cm;

   ConcurrentMarkThread* _cmt;

 public:

   void work(int worker_i) {

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

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

     ResourceMark rm;

     double start_vtime = os::elapsedVTime();

     ConcurrentGCThread::stsJoin();

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

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

     the_task->record_start_time();

     if (!_cm->has_aborted()) {

       do {

         double start_vtime_sec = os::elapsedVTime();

         double start_time_sec = os::elapsedTime();

         double mark_step_duration_ms = G1ConcMarkStepDurationMillis;

         the_task->do_marking_step(mark_step_duration_ms,

                                   true /* do_stealing    */,

                                   true /* do_termination */);

         double end_time_sec = os::elapsedTime();

         double end_vtime_sec = os::elapsedVTime();

         double elapsed_vtime_sec = end_vtime_sec - start_vtime_sec;

         double elapsed_time_sec = end_time_sec - start_time_sec;

         _cm->clear_has_overflown();

         bool ret = _cm->do_yield_check(worker_i);

         jlong sleep_time_ms;

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

           sleep_time_ms =

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

           ConcurrentGCThread::stsLeave();

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

           ConcurrentGCThread::stsJoin();

         }

         double end_time2_sec = os::elapsedTime();

         double elapsed_time2_sec = end_time2_sec - start_time_sec;

 #if 0

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

                                  "overhead %1.4lf",

                                  elapsed_vtime_sec * 1000.0, (double) sleep_time_ms,

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

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

                                  elapsed_time_sec * 1000.0, elapsed_time2_sec * 1000.0);

 #endif

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

     }

     the_task->record_end_time();

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

     ConcurrentGCThread::stsLeave();

     double end_vtime = os::elapsedVTime();

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

   }

   CMConcurrentMarkingTask(ConcurrentMark* cm,

                           ConcurrentMarkThread* cmt) :

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

   ~CMConcurrentMarkingTask() { }

 };

 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;

   size_t active_workers = MAX2((size_t) 1, parallel_marking_threads());

   force_overflow_conc()->init();

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

   CMConcurrentMarkingTask markingTask(this, cmThread());

   if (parallel_marking_threads() > 0) {

     _parallel_workers->run_task(&markingTask);

   } else {

     markingTask.work(0);

   }

   print_stats();

 }

 void ConcurrentMark::checkpointRootsFinal(bool clear_all_soft_refs) {

   // world is stopped at this checkpoint

   assert(SafepointSynchronize::is_at_safepoint(),

          "world should be stopped");

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

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

   if (has_aborted()) {

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

     return;

   }

   SvcGCMarker sgcm(SvcGCMarker::OTHER);

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

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

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

     Universe::verify(/* allow dirty */ true,

                      /* silent      */ false,

                      /* option      */ VerifyOption_G1UsePrevMarking);

   }

   G1CollectorPolicy* g1p = g1h->g1_policy();

   g1p->record_concurrent_mark_remark_start();

   double start = os::elapsedTime();

   checkpointRootsFinalWork();

   double mark_work_end = os::elapsedTime();

   weakRefsWork(clear_all_soft_refs);

   if (has_overflown()) {

     // Oops.  We overflowed.  Restart concurrent marking.

     _restart_for_overflow = true;

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

     clear_has_overflown();

     if (G1TraceMarkStackOverflow) {

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

     }

   } else {

     SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

     // We're done with marking.

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

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

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

                                        true /* expected_active */);

     if (VerifyDuringGC) {

       HandleMark hm;  // handle scope

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

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

       Universe::verify(/* allow dirty */ true,

                        /* silent      */ false,

                        /* option      */ VerifyOption_G1UseNextMarking);

     }

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

   }

   // Reset the marking state if marking completed

   if (!restart_for_overflow()) {

     set_non_marking_state();

   }

 #if VERIFY_OBJS_PROCESSED

   _scan_obj_cl.objs_processed = 0;

   ThreadLocalObjQueue::objs_enqueued = 0;

 #endif

   // Statistics

   double now = os::elapsedTime();

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

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

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

   g1p->record_concurrent_mark_remark_end();

 }

 #define CARD_BM_TEST_MODE 0

 class CalcLiveObjectsClosure: public HeapRegionClosure {

   CMBitMapRO* _bm;

   ConcurrentMark* _cm;

   bool _changed;

   bool _yield;

   size_t _words_done;

   size_t _tot_live;

   size_t _tot_used;

   size_t _regions_done;

   double _start_vtime_sec;

   BitMap* _region_bm;

   BitMap* _card_bm;

   intptr_t _bottom_card_num;

   bool _final;

   void mark_card_num_range(intptr_t start_card_num, intptr_t last_card_num) {

     for (intptr_t i = start_card_num; i <= last_card_num; i++) {

 #if CARD_BM_TEST_MODE

       guarantee(_card_bm->at(i - _bottom_card_num), "Should already be set.");

 #else

       _card_bm->par_at_put(i - _bottom_card_num, 1);

 #endif

     }

   }

 public:

   CalcLiveObjectsClosure(bool final,

                          CMBitMapRO *bm, ConcurrentMark *cm,

                          BitMap* region_bm, BitMap* card_bm) :

     _bm(bm), _cm(cm), _changed(false), _yield(true),

     _words_done(0), _tot_live(0), _tot_used(0),

     _region_bm(region_bm), _card_bm(card_bm),_final(final),

     _regions_done(0), _start_vtime_sec(0.0)

   {

     _bottom_card_num =

       intptr_t(uintptr_t(G1CollectedHeap::heap()->reserved_region().start()) >>

                CardTableModRefBS::card_shift);

   }

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

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

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

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

   // associated "continues humongous" regions.

   void set_bit_for_region(HeapRegion* hr) {

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

     size_t index = hr->hrs_index();

     if (!hr->startsHumongous()) {

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

       _region_bm->par_at_put((BitMap::idx_t) index, true);

     } else {

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

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

       // have been a bit more efficient to look at the object that

       // spans these humongous regions to calculate their number from

       // the object's size. However, it's a good idea to calculate

       // this based on the metadata itself, and not the region

       // contents, so that this code is not aware of what goes into

       // the humongous regions (in case this changes in the future).

       G1CollectedHeap* g1h = G1CollectedHeap::heap();

       size_t end_index = index + 1;

       while (end_index < g1h->n_regions()) {

         HeapRegion* chr = g1h->region_at(end_index);

         if (!chr->continuesHumongous()) break;

         end_index += 1;

       }

       _region_bm->par_at_put_range((BitMap::idx_t) index,

                                    (BitMap::idx_t) end_index, true);

     }

   }

   bool doHeapRegion(HeapRegion* hr) {

     if (!_final && _regions_done == 0) {

       _start_vtime_sec = os::elapsedVTime();

     }

     if (hr->continuesHumongous()) {

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

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

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

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

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

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

       // before its associated "starts humongous".

       return false;

     }

     HeapWord* nextTop = hr->next_top_at_mark_start();

     HeapWord* start   = hr->top_at_conc_mark_count();

     assert(hr->bottom() <= start && start <= hr->end() &&

            hr->bottom() <= nextTop && nextTop <= hr->end() &&

            start <= nextTop,

            "Preconditions.");

     // Otherwise, record the number of word's we'll examine.

     size_t words_done = (nextTop - start);

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

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

     size_t marked_bytes = 0;

     // Below, the term "card num" means the result of shifting an address

     // by the card shift -- address 0 corresponds to card number 0.  One

     // must subtract the card num of the bottom of the heap to obtain a

     // card table index.

     // The first card num of the sequence of live cards currently being

     // constructed.  -1 ==> no sequence.

     intptr_t start_card_num = -1;

     // The last card num of the sequence of live cards currently being

     // constructed.  -1 ==> no sequence.

     intptr_t last_card_num = -1;

     while (start < nextTop) {

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

         // We yielded.  It might be for a full collection, in which case

         // all bets are off; terminate the traversal.

         if (_cm->has_aborted()) {

           _changed = false;

           return true;

         } else {

           // Otherwise, it might be a collection pause, and the region

           // we're looking at might be in the collection set.  We'll

           // abandon this region.

           return false;

         }

       }

       oop obj = oop(start);

       int obj_sz = obj->size();

       // The card num of the start of the current object.

       intptr_t obj_card_num =

         intptr_t(uintptr_t(start) >> CardTableModRefBS::card_shift);

       HeapWord* obj_last = start + obj_sz - 1;

       intptr_t obj_last_card_num =

         intptr_t(uintptr_t(obj_last) >> CardTableModRefBS::card_shift);

       if (obj_card_num != last_card_num) {

         if (start_card_num == -1) {

           assert(last_card_num == -1, "Both or neither.");

           start_card_num = obj_card_num;

         } else {

           assert(last_card_num != -1, "Both or neither.");

           assert(obj_card_num >= last_card_num, "Inv");

           if ((obj_card_num - last_card_num) > 1) {

             // Mark the last run, and start a new one.

             mark_card_num_range(start_card_num, last_card_num);

             start_card_num = obj_card_num;

           }

         }

 #if CARD_BM_TEST_MODE

         /*

         gclog_or_tty->print_cr("Setting bits from %d/%d.",

                                obj_card_num - _bottom_card_num,

                                obj_last_card_num - _bottom_card_num);

         */

         for (intptr_t j = obj_card_num; j <= obj_last_card_num; j++) {

           _card_bm->par_at_put(j - _bottom_card_num, 1);

         }

 #endif

       }

       // In any case, we set the last card num.

       last_card_num = obj_last_card_num;

       marked_bytes += (size_t)obj_sz * HeapWordSize;

       // Find the next marked object after this one.

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

       _changed = true;

     }

     // Handle the last range, if any.

     if (start_card_num != -1) {

       mark_card_num_range(start_card_num, last_card_num);

     }

     if (_final) {

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

       HeapWord* tp = hr->top();

       if (nextTop < tp) {

         start_card_num =

           intptr_t(uintptr_t(nextTop) >> CardTableModRefBS::card_shift);

         last_card_num =

           intptr_t(uintptr_t(tp) >> CardTableModRefBS::card_shift);

         mark_card_num_range(start_card_num, last_card_num);

         // This definitely means the region has live objects.

         set_bit_for_region(hr);

       }

     }

     hr->add_to_marked_bytes(marked_bytes);

     // Update the live region bitmap.

     if (marked_bytes > 0) {

       set_bit_for_region(hr);

     }

     hr->set_top_at_conc_mark_count(nextTop);

     _tot_live += hr->next_live_bytes();

     _tot_used += hr->used();

     _words_done = words_done;

     if (!_final) {

       ++_regions_done;

       if (_regions_done % 10 == 0) {

         double end_vtime_sec = os::elapsedVTime();

         double elapsed_vtime_sec = end_vtime_sec - _start_vtime_sec;

         if (elapsed_vtime_sec > (10.0 / 1000.0)) {

           jlong sleep_time_ms =

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

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

           _start_vtime_sec = end_vtime_sec;

         }

       }

     }

     return false;

   }

   bool changed() { return _changed;  }

   void reset()   { _changed = false; _words_done = 0; }

   void no_yield() { _yield = false; }

   size_t words_done() { return _words_done; }

   size_t tot_live() { return _tot_live; }

   size_t tot_used() { return _tot_used; }

 };

 void ConcurrentMark::calcDesiredRegions() {

   _region_bm.clear();

   _card_bm.clear();

   CalcLiveObjectsClosure calccl(false /*final*/,

                                 nextMarkBitMap(), this,

                                 &_region_bm, &_card_bm);

   G1CollectedHeap *g1h = G1CollectedHeap::heap();

   g1h->heap_region_iterate(&calccl);

   do {

     calccl.reset();

     g1h->heap_region_iterate(&calccl);

   } while (calccl.changed());

 }

 class G1ParFinalCountTask: public AbstractGangTask {

 protected:

   G1CollectedHeap* _g1h;

   CMBitMap* _bm;

   size_t _n_workers;

   size_t *_live_bytes;

   size_t *_used_bytes;

   BitMap* _region_bm;

   BitMap* _card_bm;

 public:

   G1ParFinalCountTask(G1CollectedHeap* g1h, CMBitMap* bm,

                       BitMap* region_bm, BitMap* card_bm)

     : AbstractGangTask("G1 final counting"), _g1h(g1h),

       _bm(bm), _region_bm(region_bm), _card_bm(card_bm) {

     if (ParallelGCThreads > 0) {

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

     } else {

       _n_workers = 1;

     }

     _live_bytes = NEW_C_HEAP_ARRAY(size_t, _n_workers);

     _used_bytes = NEW_C_HEAP_ARRAY(size_t, _n_workers);

   }

   ~G1ParFinalCountTask() {

     FREE_C_HEAP_ARRAY(size_t, _live_bytes);

     FREE_C_HEAP_ARRAY(size_t, _used_bytes);

   }

   void work(int i) {

     CalcLiveObjectsClosure calccl(true /*final*/,

                                   _bm, _g1h->concurrent_mark(),

                                   _region_bm, _card_bm);

     calccl.no_yield();

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       _g1h->heap_region_par_iterate_chunked(&calccl, i,

                                             HeapRegion::FinalCountClaimValue);

     } else {

       _g1h->heap_region_iterate(&calccl);

     }

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

     assert((size_t) i < _n_workers, "invariant");

     _live_bytes[i] = calccl.tot_live();

     _used_bytes[i] = calccl.tot_used();

   }

   size_t live_bytes()  {

     size_t live_bytes = 0;

     for (size_t i = 0; i < _n_workers; ++i)

       live_bytes += _live_bytes[i];

     return live_bytes;

   }

   size_t used_bytes()  {

     size_t used_bytes = 0;

     for (size_t i = 0; i < _n_workers; ++i)

       used_bytes += _used_bytes[i];

     return used_bytes;

   }

 };

 class G1ParNoteEndTask;

 class G1NoteEndOfConcMarkClosure : public HeapRegionClosure {

   G1CollectedHeap* _g1;

   int _worker_num;

   size_t _max_live_bytes;

   size_t _regions_claimed;

   size_t _freed_bytes;

   FreeRegionList* _local_cleanup_list;

   HumongousRegionSet* _humongous_proxy_set;

   HRRSCleanupTask* _hrrs_cleanup_task;

   double _claimed_region_time;

   double _max_region_time;

 public:

   G1NoteEndOfConcMarkClosure(G1CollectedHeap* g1,

                              int worker_num,

                              FreeRegionList* local_cleanup_list,

                              HumongousRegionSet* humongous_proxy_set,

                              HRRSCleanupTask* hrrs_cleanup_task);

   size_t freed_bytes() { return _freed_bytes; }

   bool doHeapRegion(HeapRegion *r);

   size_t max_live_bytes() { return _max_live_bytes; }

   size_t 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(int i) {

     double start = os::elapsedTime();

     FreeRegionList local_cleanup_list("Local Cleanup List");

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

     HRRSCleanupTask hrrs_cleanup_task;

     G1NoteEndOfConcMarkClosure g1_note_end(_g1h, i, &local_cleanup_list,

                                            &humongous_proxy_set,

                                            &hrrs_cleanup_task);

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       _g1h->heap_region_par_iterate_chunked(&g1_note_end, i,

                                             HeapRegion::NoteEndClaimValue);

     } else {

       _g1h->heap_region_iterate(&g1_note_end);

     }

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

     // Now update the lists

     _g1h->update_sets_after_freeing_regions(g1_note_end.freed_bytes(),

                                             NULL /* free_list */,

                                             &humongous_proxy_set,

                                             true /* par */);

     {

       MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

       _max_live_bytes += g1_note_end.max_live_bytes();

       _freed_bytes += g1_note_end.freed_bytes();

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

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

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

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

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

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

       // cleanup list.

       G1HRPrinter* hr_printer = _g1h->hr_printer();

       if (hr_printer->is_active()) {

         HeapRegionLinkedListIterator iter(&local_cleanup_list);

         while (iter.more_available()) {

           HeapRegion* hr = iter.get_next();

           hr_printer->cleanup(hr);

         }

       }

       _cleanup_list->add_as_tail(&local_cleanup_list);

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

       HeapRegionRemSet::finish_cleanup_task(&hrrs_cleanup_task);

     }

     double end = os::elapsedTime();

     if (G1PrintParCleanupStats) {

       gclog_or_tty->print("     Worker thread %d [%8.3f..%8.3f = %8.3f ms] "

                           "claimed %d regions (tot = %8.3f ms, max = %8.3f ms).\n",

                           i, start, end, (end-start)*1000.0,

                           g1_note_end.regions_claimed(),

                           g1_note_end.claimed_region_time_sec()*1000.0,

                           g1_note_end.max_region_time_sec()*1000.0);

     }

   }

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

     if (G1CollectedHeap::use_parallel_gc_threads()) {

       _g1rs->scrub_par(_region_bm, _card_bm, i,

                        HeapRegion::ScrubRemSetClaimValue);

     } else {

       _g1rs->scrub(_region_bm, _card_bm);

     }

   }

 };

 G1NoteEndOfConcMarkClosure::

 G1NoteEndOfConcMarkClosure(G1CollectedHeap* g1,

                            int worker_num,

                            FreeRegionList* local_cleanup_list,

                            HumongousRegionSet* humongous_proxy_set,

                            HRRSCleanupTask* hrrs_cleanup_task)

   : _g1(g1), _worker_num(worker_num),

     _max_live_bytes(0), _regions_claimed(0),

     _freed_bytes(0),

     _claimed_region_time(0.0), _max_region_time(0.0),

     _local_cleanup_list(local_cleanup_list),

     _humongous_proxy_set(humongous_proxy_set),

     _hrrs_cleanup_task(hrrs_cleanup_task) { }

 bool G1NoteEndOfConcMarkClosure::doHeapRegion(HeapRegion *hr) {

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

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

   hr->reset_gc_time_stamp();

   if (!hr->continuesHumongous()) {

     double start = os::elapsedTime();

     _regions_claimed++;

     hr->note_end_of_marking();

     _max_live_bytes += hr->max_live_bytes();

     _g1->free_region_if_empty(hr,

                               &_freed_bytes,

                               _local_cleanup_list,

                               _humongous_proxy_set,

                               _hrrs_cleanup_task,

                               true /* par */);

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

     _claimed_region_time += region_time;

     if (region_time > _max_region_time) {

       _max_region_time = region_time;

     }

   }

   return false;

 }

 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

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

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

     Universe::verify(/* allow dirty */ true,

                      /* silent      */ false,

                      /* option      */ VerifyOption_G1UsePrevMarking);

   }

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

   g1p->record_concurrent_mark_cleanup_start();

   double start = os::elapsedTime();

   HeapRegionRemSet::reset_for_cleanup_tasks();

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

   G1ParFinalCountTask g1_par_count_task(g1h, nextMarkBitMap(),

                                         &_region_bm, &_card_bm);

   if (G1CollectedHeap::use_parallel_gc_threads()) {

     assert(g1h->check_heap_region_claim_values(

                                                HeapRegion::InitialClaimValue),

            "sanity check");

     int n_workers = g1h->workers()->total_workers();

     g1h->set_par_threads(n_workers);

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

     g1h->set_par_threads(0);

     assert(g1h->check_heap_region_claim_values(

                                              HeapRegion::FinalCountClaimValue),

            "sanity check");

   } else {

     g1_par_count_task.work(0);

   }

   size_t known_garbage_bytes =

     g1_par_count_task.used_bytes() - g1_par_count_task.live_bytes();

   g1p->set_known_garbage_bytes(known_garbage_bytes);

   size_t start_used_bytes = g1h->used();

   _at_least_one_mark_complete = true;

   g1h->set_marking_complete();

   ergo_verbose4(ErgoConcCycles,

            "finish cleanup",

            ergo_format_byte("occupancy")

            ergo_format_byte("capacity")

            ergo_format_byte_perc("known garbage"),

            start_used_bytes, g1h->capacity(),

            known_garbage_bytes,

            ((double) known_garbage_bytes / (double) g1h->capacity()) * 100.0);

   double count_end = os::elapsedTime();

   double this_final_counting_time = (count_end - start);

   if (G1PrintParCleanupStats) {

     gclog_or_tty->print_cr("Cleanup:");

     gclog_or_tty->print_cr("  Finalize counting: %8.3f ms",

                            this_final_counting_time*1000.0);

   }

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

   double note_end_start = os::elapsedTime();

   G1ParNoteEndTask g1_par_note_end_task(g1h, &_cleanup_list);

   if (G1CollectedHeap::use_parallel_gc_threads()) {

     int n_workers = g1h->workers()->total_workers();

     g1h->set_par_threads(n_workers);

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

     g1h->set_par_threads(0);

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

            "sanity check");

   } else {

     g1_par_note_end_task.work(0);

   }

   if (!cleanup_list_is_empty()) {

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

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

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

     g1h->set_free_regions_coming();

   }

   double note_end_end = os::elapsedTime();

   if (G1PrintParCleanupStats) {

     gclog_or_tty->print_cr("  note end of marking: %8.3f ms.",

                            (note_end_end - note_end_start)*1000.0);

   }

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

       int n_workers = g1h->workers()->total_workers();

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

   // Statistics.

   double end = os::elapsedTime();

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

   // G1CollectedHeap::heap()->print();

   // gclog_or_tty->print_cr("HEAP GC TIME STAMP : %d",

   // G1CollectedHeap::heap()->get_gc_time_stamp());

   if (PrintGC || PrintGCDetails) {

     g1h->print_size_transition(gclog_or_tty,

                                start_used_bytes,

                                g1h->used(),

                                g1h->capacity());

   }

   size_t cleaned_up_bytes = start_used_bytes - g1h->used();

   g1p->decrease_known_garbage_bytes(cleaned_up_bytes);

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

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

   Universe::update_heap_info_at_gc();

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

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

   g1h->increment_total_collections();

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

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

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

     Universe::verify(/* allow dirty */ true,

                      /* silent      */ false,

                      /* option      */ VerifyOption_G1UsePrevMarking);

   }

   g1h->verify_region_sets_optional();

 }

 void ConcurrentMark::completeCleanup() {

   if (has_aborted()) return;

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   _cleanup_list.verify_optional();

   FreeRegionList tmp_free_list("Tmp Free List");

   if (G1ConcRegionFreeingVerbose) {

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

                            "cleanup list has "SIZE_FORMAT" entries",

                            _cleanup_list.length());

   }

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

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

   while (!_cleanup_list.is_empty()) {

     HeapRegion* hr = _cleanup_list.remove_head();

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

     hr->par_clear();

     tmp_free_list.add_as_tail(hr);

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

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

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

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

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

     // region from the _cleanup_list).

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

         _cleanup_list.is_empty()) {

       if (G1ConcRegionFreeingVerbose) {

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

                                "appending "SIZE_FORMAT" entries to the "

                                "secondary_free_list, clean list still has "

                                SIZE_FORMAT" entries",

                                tmp_free_list.length(),

                                _cleanup_list.length());

       }

       {

         MutexLockerEx x(SecondaryFreeList_lock, Mutex::_no_safepoint_check_flag);

         g1h->secondary_free_list_add_as_tail(&tmp_free_list);

         SecondaryFreeList_lock->notify_all();

       }

       if (G1StressConcRegionFreeing) {

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

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

         }

       }

     }

   }

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

 }

 // Support closures for reference procssing in G1

 bool G1CMIsAliveClosure::do_object_b(oop obj) {

   HeapWord* addr = (HeapWord*)obj;

   return addr != NULL &&

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

 }

 class G1CMKeepAliveClosure: public OopClosure {

   G1CollectedHeap* _g1;

   ConcurrentMark*  _cm;

   CMBitMap*        _bitMap;

  public:

   G1CMKeepAliveClosure(G1CollectedHeap* g1, ConcurrentMark* cm,

                        CMBitMap* bitMap) :

     _g1(g1), _cm(cm),

     _bitMap(bitMap) {}

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

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

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

     oop obj = oopDesc::load_decode_heap_oop(p);

     HeapWord* addr = (HeapWord*)obj;

     if (_cm->verbose_high()) {

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

                              "*"PTR_FORMAT" = "PTR_FORMAT,

                              p, (void*) obj);

     }

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

       _bitMap->mark(addr);

       _cm->mark_stack_push(obj);

     }

   }

 };

 class G1CMDrainMarkingStackClosure: public VoidClosure {

   CMMarkStack*                  _markStack;

   CMBitMap*                     _bitMap;

   G1CMKeepAliveClosure*         _oopClosure;

  public:

   G1CMDrainMarkingStackClosure(CMBitMap* bitMap, CMMarkStack* markStack,

                                G1CMKeepAliveClosure* oopClosure) :

     _bitMap(bitMap),

     _markStack(markStack),

     _oopClosure(oopClosure)

   {}

   void do_void() {

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

   }

 };

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

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

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

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

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

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

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

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

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

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

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

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

 // avoids that potential interference.

 class G1CMParKeepAliveAndDrainClosure: public OopClosure {

   ConcurrentMark*  _cm;

   CMTask*          _task;

   CMBitMap*        _bitMap;

   int              _ref_counter_limit;

   int              _ref_counter;

  public:

   G1CMParKeepAliveAndDrainClosure(ConcurrentMark* cm,

                                   CMTask* task,

                                   CMBitMap* bitMap) :

     _cm(cm), _task(task), _bitMap(bitMap),

     _ref_counter_limit(G1RefProcDrainInterval)

   {

     assert(_ref_counter_limit > 0, "sanity");

     _ref_counter = _ref_counter_limit;

   }

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

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

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

     if (!_cm->has_overflown()) {

       oop obj = oopDesc::load_decode_heap_oop(p);

       if (_cm->verbose_high()) {

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

                                "*"PTR_FORMAT" = "PTR_FORMAT,

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

       }

       _task->deal_with_reference(obj);

       _ref_counter--;

       if (_ref_counter == 0) {

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

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

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

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

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

         // calls above) or we overflow.

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

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

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

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

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

         // that the marking has completed.

         do {

           double mark_step_duration_ms = G1ConcMarkStepDurationMillis;

           _task->do_marking_step(mark_step_duration_ms,

                                  false /* do_stealing    */,

                                  false /* do_termination */);

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

         _ref_counter = _ref_counter_limit;

       }

     } else {

       if (_cm->verbose_high()) {

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

       }

     }

   }

 };

 class G1CMParDrainMarkingStackClosure: public VoidClosure {

   ConcurrentMark* _cm;

   CMTask* _task;

  public:

   G1CMParDrainMarkingStackClosure(ConcurrentMark* cm, CMTask* task) :

     _cm(cm), _task(task)

   {}

   void do_void() {

     do {

       if (_cm->verbose_high()) {

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

                                _task->task_id());

       }

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

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

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

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

       // G1CMParKeepAliveAndDrainClosure to the entries on the discovered ref

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

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

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

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

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

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

       // that the marking has completed.

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

                              true /* do_stealing    */,

                              true /* do_termination */);

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

   }

 };

 // Implementation of AbstractRefProcTaskExecutor for parallel

 // reference processing at the end of G1 concurrent marking

 class G1CMRefProcTaskExecutor: public AbstractRefProcTaskExecutor {

 private:

   G1CollectedHeap* _g1h;

   ConcurrentMark*  _cm;

   CMBitMap*        _bitmap;

   WorkGang*        _workers;

   int              _active_workers;

 public:

   G1CMRefProcTaskExecutor(G1CollectedHeap* g1h,

                         ConcurrentMark* cm,

                         CMBitMap* bitmap,

                         WorkGang* workers,

                         int n_workers) :

     _g1h(g1h), _cm(cm), _bitmap(bitmap),

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

   CMBitMap*        _bitmap;

 public:

   G1CMRefProcTaskProxy(ProcessTask& proc_task,

                      G1CollectedHeap* g1h,

                      ConcurrentMark* cm,

                      CMBitMap* bitmap) :

     AbstractGangTask("Process reference objects in parallel"),

     _proc_task(proc_task), _g1h(g1h), _cm(cm), _bitmap(bitmap)

   {}

   virtual void work(int i) {

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

     G1CMIsAliveClosure g1_is_alive(_g1h);

     G1CMParKeepAliveAndDrainClosure g1_par_keep_alive(_cm, marking_task, _bitmap);

     G1CMParDrainMarkingStackClosure g1_par_drain(_cm, marking_task);

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

   }

 };

 void G1CMRefProcTaskExecutor::execute(ProcessTask& proc_task) {

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

   G1CMRefProcTaskProxy proc_task_proxy(proc_task, _g1h, _cm, _bitmap);

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

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

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

   _g1h->set_par_threads(_active_workers);

   _workers->run_task(&proc_task_proxy);

   _g1h->set_par_threads(0);

 }

 class G1CMRefEnqueueTaskProxy: public AbstractGangTask {

   typedef AbstractRefProcTaskExecutor::EnqueueTask EnqueueTask;

   EnqueueTask& _enq_task;

 public:

   G1CMRefEnqueueTaskProxy(EnqueueTask& enq_task) :

     AbstractGangTask("Enqueue reference objects in parallel"),

     _enq_task(enq_task)

   { }

   virtual void work(int i) {

     _enq_task.work(i);

   }

 };

 void G1CMRefProcTaskExecutor::execute(EnqueueTask& enq_task) {

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

   G1CMRefEnqueueTaskProxy enq_task_proxy(enq_task);

   _g1h->set_par_threads(_active_workers);

   _workers->run_task(&enq_task_proxy);

   _g1h->set_par_threads(0);

 }

 void ConcurrentMark::weakRefsWork(bool clear_all_soft_refs) {

   ResourceMark rm;

   HandleMark   hm;

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   // Is alive closure.

   G1CMIsAliveClosure g1_is_alive(g1h);

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

   // tables from the displayed time.

   {

     bool verbose = PrintGC && PrintGCDetails;

     if (verbose) {

       gclog_or_tty->put(' ');

     }

     TraceTime t("GC ref-proc", verbose, false, gclog_or_tty);

     ReferenceProcessor* rp = g1h->ref_processor_cm();

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

     // about how reference processing currently works in G1.

     // Process weak references.

     rp->setup_policy(clear_all_soft_refs);

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

     G1CMKeepAliveClosure g1_keep_alive(g1h, this, nextMarkBitMap());

     G1CMDrainMarkingStackClosure

       g1_drain_mark_stack(nextMarkBitMap(), &_markStack, &g1_keep_alive);

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

     // the worker threads.

     int active_workers = g1h->workers() ? g1h->workers()->total_workers() : 1;

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

     G1CMRefProcTaskExecutor par_task_executor(g1h, this, nextMarkBitMap(),

                                               g1h->workers(), active_workers);

     if (rp->processing_is_mt()) {

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

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

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

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

       // balance_all_queues() and balance_queues()).

       rp->set_active_mt_degree(active_workers);

       rp->process_discovered_references(&g1_is_alive,

                                       &g1_keep_alive,

                                       &g1_drain_mark_stack,

                                       &par_task_executor);

       // The work routines of the parallel keep_alive and drain_marking_stack

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

       // stack.

     } else {

       rp->process_discovered_references(&g1_is_alive,

                                         &g1_keep_alive,

                                         &g1_drain_mark_stack,

                                         NULL);

     }

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

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

     if (_markStack.overflow()) {

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

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

       set_has_overflown();

     }

     if (rp->processing_is_mt()) {

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

       rp->enqueue_discovered_references(&par_task_executor);

     } else {

       rp->enqueue_discovered_references();

     }

     rp->verify_no_references_recorded();

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

   }

   // Now clean up stale oops in StringTable

   StringTable::unlink(&g1_is_alive);

   // Clean up unreferenced symbols in symbol table.

   SymbolTable::unlink();

 }

 void ConcurrentMark::swapMarkBitMaps() {

   CMBitMapRO* temp = _prevMarkBitMap;

   _prevMarkBitMap  = (CMBitMapRO*)_nextMarkBitMap;

   _nextMarkBitMap  = (CMBitMap*)  temp;

 }

 class CMRemarkTask: public AbstractGangTask {

 private:

   ConcurrentMark *_cm;

 public:

   void work(int worker_i) {

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

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

     if ((size_t)worker_i < _cm->active_tasks()) {

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

       task->record_start_time();

       do {

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

                               true /* do_stealing    */,

                               true /* do_termination */);

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

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

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

       task->record_end_time();

     }

   }

   CMRemarkTask(ConcurrentMark* cm) :

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

 };

 void ConcurrentMark::checkpointRootsFinalWork() {

   ResourceMark rm;

   HandleMark   hm;

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   g1h->ensure_parsability(false);

   if (G1CollectedHeap::use_parallel_gc_threads()) {

     G1CollectedHeap::StrongRootsScope srs(g1h);

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

     int active_workers = ParallelGCThreads;

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

     CMRemarkTask remarkTask(this);

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

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

     // immediately.

     int n_workers = g1h->workers()->total_workers();

     g1h->set_par_threads(n_workers);

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

     g1h->set_par_threads(0);

   } else {

     G1CollectedHeap::StrongRootsScope srs(g1h);

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

     int active_workers = 1;

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

     CMRemarkTask remarkTask(this);

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

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

     // immediately.

     remarkTask.work(0);

   }

   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

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

   print_stats();

 #if VERIFY_OBJS_PROCESSED

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

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

                            _scan_obj_cl.objs_processed,

                            ThreadLocalObjQueue::objs_enqueued);

     guarantee(_scan_obj_cl.objs_processed ==

               ThreadLocalObjQueue::objs_enqueued,

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

   }

 #endif

 }

 #ifndef PRODUCT

 class PrintReachableOopClosure: public OopClosure {

 private:

   G1CollectedHeap* _g1h;

   outputStream*    _out;

   VerifyOption     _vo;

   bool             _all;

 public:

   PrintReachableOopClosure(outputStream* out,

                            VerifyOption  vo,

                            bool          all) :

     _g1h(G1CollectedHeap::heap()),

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

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

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

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

     oop         obj = oopDesc::load_decode_heap_oop(p);

     const char* str = NULL;

     const char* str2 = "";

     if (obj == NULL) {

       str = "";

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

       str = " O";

     } else {

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

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

       bool over_tams = false;

       bool marked = false;

       switch (_vo) {

         case VerifyOption_G1UsePrevMarking:

           over_tams = hr->obj_allocated_since_prev_marking(obj);

           marked = _g1h->isMarkedPrev(obj);

           break;

         case VerifyOption_G1UseNextMarking:

           over_tams = hr->obj_allocated_since_next_marking(obj);

           marked = _g1h->isMarkedNext(obj);

           break;

         case VerifyOption_G1UseMarkWord:

           marked = obj->is_gc_marked();

           break;

         default:

           ShouldNotReachHere();

       }

       if (over_tams) {

         str = " >";

         if (marked) {

           str2 = " AND MARKED";

         }

       } else if (marked) {

         str = " M";

       } else {

         str = " NOT";

       }

     }

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

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

   }

 };

 class PrintReachableObjectClosure : public ObjectClosure {

 private:

   G1CollectedHeap* _g1h;

   outputStream*    _out;

   VerifyOption     _vo;

   bool             _all;

   HeapRegion*      _hr;

 public:

   PrintReachableObjectClosure(outputStream* out,

                               VerifyOption  vo,

                               bool          all,

                               HeapRegion*   hr) :

     _g1h(G1CollectedHeap::heap()),

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

   void do_object(oop o) {

     bool over_tams = false;

     bool marked = false;

     switch (_vo) {

       case VerifyOption_G1UsePrevMarking:

         over_tams = _hr->obj_allocated_since_prev_marking(o);

         marked = _g1h->isMarkedPrev(o);

         break;

       case VerifyOption_G1UseNextMarking:

         over_tams = _hr->obj_allocated_since_next_marking(o);

         marked = _g1h->isMarkedNext(o);

         break;

       case VerifyOption_G1UseMarkWord:

         marked = o->is_gc_marked();

         break;

       default:

         ShouldNotReachHere();

     }

     bool print_it = _all || over_tams || marked;

     if (print_it) {

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

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

       PrintReachableOopClosure oopCl(_out, _vo, _all);

       o->oop_iterate(&oopCl);

     }

   }

 };

 class PrintReachableRegionClosure : public HeapRegionClosure {

 private:

   outputStream* _out;

   VerifyOption  _vo;

   bool          _all;

 public:

   bool doHeapRegion(HeapRegion* hr) {

     HeapWord* b = hr->bottom();

     HeapWord* e = hr->end();

     HeapWord* t = hr->top();

     HeapWord* p = NULL;

     switch (_vo) {

       case VerifyOption_G1UsePrevMarking:

         p = hr->prev_top_at_mark_start();

         break;

       case VerifyOption_G1UseNextMarking:

         p = hr->next_top_at_mark_start();

         break;

       case VerifyOption_G1UseMarkWord:

         // When we are verifying marking using the mark word

         // TAMS has no relevance.

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

         break;

       default:

         ShouldNotReachHere();

     }

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

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

     _out->cr();

     HeapWord* from = b;

     HeapWord* to   = t;

     if (to > from) {

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

       _out->cr();

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

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

       _out->cr();

     }

     return false;

   }

   PrintReachableRegionClosure(outputStream* out,

                               VerifyOption  vo,

                               bool          all) :

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

 };

 static const char* verify_option_to_tams(VerifyOption vo) {

   switch (vo) {

     case VerifyOption_G1UsePrevMarking:

       return "PTAMS";

     case VerifyOption_G1UseNextMarking:

       return "NTAMS";

     default:

       return "NONE";

   }

 }

 void ConcurrentMark::print_reachable(const char* str,

                                      VerifyOption vo,

                                      bool all) {

   gclog_or_tty->cr();

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

   if (G1PrintReachableBaseFile == NULL) {

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

     return;

   }

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

       (JVM_MAXPATHLEN - 1)) {

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

     return;

   }

   char file_name[JVM_MAXPATHLEN];

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

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

   fileStream fout(file_name);

   if (!fout.is_open()) {

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

     return;

   }

   outputStream* out = &fout;

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

   out->cr();

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

   out->cr();

   PrintReachableRegionClosure rcl(out, vo, all);

   _g1h->heap_region_iterate(&rcl);

   out->cr();

   gclog_or_tty->print_cr("  done");

   gclog_or_tty->flush();

 }

 #endif // PRODUCT

 // This note is for drainAllSATBBuffers and the code in between.

 // In the future we could reuse a task to do this work during an

 // evacuation pause (since now tasks are not active and can be claimed

 // during an evacuation pause). This was a late change to the code and

 // is currently not being taken advantage of.

 class CMGlobalObjectClosure : public ObjectClosure {

 private:

   ConcurrentMark* _cm;

 public:

   void do_object(oop obj) {

     _cm->deal_with_reference(obj);

   }

   CMGlobalObjectClosure(ConcurrentMark* cm) : _cm(cm) { }

 };

 void ConcurrentMark::deal_with_reference(oop obj) {

   if (verbose_high()) {

     gclog_or_tty->print_cr("[global] we're dealing with reference "PTR_FORMAT,

                            (void*) obj);

   }

   HeapWord* objAddr = (HeapWord*) obj;

   assert(obj->is_oop_or_null(true /* ignore mark word */), "Error");

   if (_g1h->is_in_g1_reserved(objAddr)) {

     assert(obj != NULL, "null check is implicit");

     if (!_nextMarkBitMap->isMarked(objAddr)) {

       // Only get the containing region if the object is not marked on the

       // bitmap (otherwise, it's a waste of time since we won't do

       // anything with it).

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

       if (!hr->obj_allocated_since_next_marking(obj)) {

         if (verbose_high()) {

           gclog_or_tty->print_cr("[global] "PTR_FORMAT" is not considered "

                                  "marked", (void*) obj);

         }

         // we need to mark it first

         if (_nextMarkBitMap->parMark(objAddr)) {

           // No OrderAccess:store_load() is needed. It is implicit in the

           // CAS done in parMark(objAddr) above

           HeapWord* finger = _finger;

           if (objAddr < finger) {

             if (verbose_high()) {

               gclog_or_tty->print_cr("[global] below the global finger "

                                      "("PTR_FORMAT"), pushing it", finger);

             }

             if (!mark_stack_push(obj)) {

               if (verbose_low()) {

                 gclog_or_tty->print_cr("[global] global stack overflow during "

                                        "deal_with_reference");

               }

             }

           }

         }

       }

     }

   }

 }

 void ConcurrentMark::drainAllSATBBuffers() {

   CMGlobalObjectClosure oc(this);

   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

   satb_mq_set.set_closure(&oc);

   while (satb_mq_set.apply_closure_to_completed_buffer()) {

     if (verbose_medium()) {

       gclog_or_tty->print_cr("[global] processed an SATB buffer");

     }

   }

   // no need to check whether we should do this, as this is only

   // called during an evacuation pause

   satb_mq_set.iterate_closure_all_threads();

   satb_mq_set.set_closure(NULL);

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

 }

 void ConcurrentMark::markPrev(oop p) {

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

   // the cast.

   ((CMBitMap*)_prevMarkBitMap)->mark((HeapWord*)p);

 }

 void ConcurrentMark::clear(oop p) {

   assert(p != NULL && p->is_oop(), "expected an oop");