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

 /*

  * Copyright 2001-2009 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

  * CA 95054 USA or visit www.sun.com if you need additional information or

  * have any questions.

  *

  */

 #include "incls/_precompiled.incl"

 #include "incls/_concurrentMark.cpp.incl"

 //

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

   // QQQQ cast ...

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

   // QQQQ cast ...

   _capacity = (jint) size;

 }

 CMRegionStack::~CMRegionStack() {

   if (_base != NULL) FREE_C_HEAP_ARRAY(oop, _base);

 }

 void CMRegionStack::push(MemRegion mr) {

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

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

       return;

     }

     // Otherwise, we need to try again.

   }

 }

 MemRegion CMRegionStack::pop() {

   while (true) {

     // Otherwise...

     jint index = _index;

     if (index == 0) {

       return MemRegion();

     }

     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.

   }

 }

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

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

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

   int size = (int) MAX2(ParallelGCThreads, (size_t)1);

   _par_cleanup_thread_state = NEW_C_HEAP_ARRAY(ParCleanupThreadState*, size);

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

     _par_cleanup_thread_state[i] = new ParCleanupThreadState;

   }

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

     vm_exit_during_initialization("Can't have more ParallelMarkingThreads "

                                   "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 (ParallelMarkingThreads > 0) {

       // notice that ParallelMarkingThreads overwrites G1MarkingOverheadPercent

       // if both are set

       _parallel_marking_threads = ParallelMarkingThreads;

       _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 WorkGang("G1 Parallel Marking Threads",

                                      (int) parallel_marking_threads(), false, true);

     if (_parallel_workers == NULL)

       vm_exit_during_initialization("Failed necessary allocation.");

   }

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

   int size = (int) MAX2(ParallelGCThreads, (size_t)1);

   for (int i = 0; i < size; i++) delete _par_cleanup_thread_state[i];

   FREE_C_HEAP_ARRAY(ParCleanupThreadState*,

                     _par_cleanup_thread_state);

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

    guarantee(!G1CollectedHeap::heap()->mark_in_progress(), "Precondition.");

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

    }

 }

 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;

   if (G1PrintReachableAtInitialMark) {

     print_reachable(true, "before");

   }

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

   reset();

 }

 class CMMarkRootsClosure: public OopsInGenClosure {

 private:

   ConcurrentMark*  _cm;

   G1CollectedHeap* _g1h;

   bool             _do_barrier;

 public:

   CMMarkRootsClosure(ConcurrentMark* cm,

                      G1CollectedHeap* g1h,

                      bool do_barrier) : _cm(cm), _g1h(g1h),

                                         _do_barrier(do_barrier) { }

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

     T heap_oop = oopDesc::load_heap_oop(p);

     if (!oopDesc::is_null(heap_oop)) {

       oop obj = oopDesc::decode_heap_oop_not_null(heap_oop);

       assert(obj->is_oop() || obj->mark() == NULL,

              "expected an oop, possibly with mark word displaced");

       HeapWord* addr = (HeapWord*)obj;

       if (_g1h->is_in_g1_reserved(addr)) {

         _cm->grayRoot(obj);

       }

     }

     if (_do_barrier) {

       assert(!_g1h->is_in_g1_reserved(p),

              "Should be called on external roots");

       do_barrier(p);

     }

   }

 };

 void ConcurrentMark::checkpointRootsInitialPost() {

   G1CollectedHeap*   g1h = G1CollectedHeap::heap();

   // For each region note start of marking.

   NoteStartOfMarkHRClosure startcl;

   g1h->heap_region_iterate(&startcl);

   // Start weak-reference discovery.

   ReferenceProcessor* rp = g1h->ref_processor();

   rp->verify_no_references_recorded();

   rp->enable_discovery(); // enable ("weak") refs discovery

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

   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

   satb_mq_set.set_active_all_threads(true);

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

 }

 // Checkpoint the roots into this generation from outside

 // this generation. [Note this initial checkpoint need only

 // be approximate -- we'll do a catch up phase subsequently.]

 void ConcurrentMark::checkpointRootsInitial() {

   assert(SafepointSynchronize::is_at_safepoint(), "world should be stopped");

   G1CollectedHeap* g1h = G1CollectedHeap::heap();

   double start = os::elapsedTime();

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

   g1p->record_concurrent_mark_init_start();

   checkpointRootsInitialPre();

   // YSR: when concurrent precleaning is in place, we'll

   // need to clear the cached card table here

   ResourceMark rm;

   HandleMark  hm;

   g1h->ensure_parsability(false);

   g1h->perm_gen()->save_marks();

   CMMarkRootsClosure notOlder(this, g1h, false);

   CMMarkRootsClosure older(this, g1h, true);

   g1h->set_marking_started();

   g1h->rem_set()->prepare_for_younger_refs_iterate(false);

   g1h->process_strong_roots(true,    // activate StrongRootsScope

                             false,   // fake perm gen collection

                             SharedHeap::SO_AllClasses,

                             &notOlder, // Regular roots

                             NULL,     // do not visit active blobs

                             &older    // Perm Gen Roots

                             );

   checkpointRootsInitialPost();

   // Statistics.

   double end = os::elapsedTime();

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

   g1p->record_concurrent_mark_init_end();

 }

 /*

    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, this then 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.

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

   ConcurrentGCThread::stsLeave();

   _first_overflow_barrier_sync.enter();

   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

     clear_marking_state();

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

   ConcurrentGCThread::stsLeave();

   _second_overflow_barrier_sync.enter();

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

 }

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

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

         the_task->do_marking_step(10.0);

         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;

   set_phase(MAX2((size_t) 1, parallel_marking_threads()), true);

   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;

   }

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

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

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

     Universe::verify(true, false, true);

   }

   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 {

     // We're done with marking.

     JavaThread::satb_mark_queue_set().set_active_all_threads(false);

     if (VerifyDuringGC) {

       HandleMark hm;  // handle scope

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

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

       Universe::heap()->verify(/* allow_dirty */      true,

                                /* silent */           false,

                                /* use_prev_marking */ false);

     }

   }

 #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 (ParallelGCThreads > 0) {

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

   size_t _cleared_h_regions;

   size_t _freed_regions;

   UncleanRegionList* _unclean_region_list;

   double _claimed_region_time;

   double _max_region_time;

 public:

   G1NoteEndOfConcMarkClosure(G1CollectedHeap* g1,

                              UncleanRegionList* list,

                              int worker_num);

   size_t freed_bytes() { return _freed_bytes; }

   size_t cleared_h_regions() { return _cleared_h_regions; }

   size_t freed_regions() { return  _freed_regions; }

   UncleanRegionList* unclean_region_list() {

     return _unclean_region_list;

   }

   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;

   ConcurrentMark::ParCleanupThreadState** _par_cleanup_thread_state;

 public:

   G1ParNoteEndTask(G1CollectedHeap* g1h,

                    ConcurrentMark::ParCleanupThreadState**

                    par_cleanup_thread_state) :

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

     _max_live_bytes(0), _freed_bytes(0),

     _par_cleanup_thread_state(par_cleanup_thread_state)

   {}

   void work(int i) {

     double start = os::elapsedTime();

     G1NoteEndOfConcMarkClosure g1_note_end(_g1h,

                                            &_par_cleanup_thread_state[i]->list,

                                            i);

     if (ParallelGCThreads > 0) {

       _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 finish up freeing the current thread's regions.

     _g1h->finish_free_region_work(g1_note_end.freed_bytes(),

                                   g1_note_end.cleared_h_regions(),

                                   0, NULL);

     {

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

     }

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

       _g1rs->scrub_par(_region_bm, _card_bm, i,

                        HeapRegion::ScrubRemSetClaimValue);

     } else {

       _g1rs->scrub(_region_bm, _card_bm);

     }

   }

 };

 G1NoteEndOfConcMarkClosure::

 G1NoteEndOfConcMarkClosure(G1CollectedHeap* g1,

                            UncleanRegionList* list,

                            int worker_num)

   : _g1(g1), _worker_num(worker_num),

     _max_live_bytes(0), _regions_claimed(0),

     _freed_bytes(0), _cleared_h_regions(0), _freed_regions(0),

     _claimed_region_time(0.0), _max_region_time(0.0),

     _unclean_region_list(list)

 {}

 bool G1NoteEndOfConcMarkClosure::doHeapRegion(HeapRegion *r) {

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

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

   r->reset_gc_time_stamp();

   if (!r->continuesHumongous()) {

     double start = os::elapsedTime();

     _regions_claimed++;

     r->note_end_of_marking();

     _max_live_bytes += r->max_live_bytes();

     _g1->free_region_if_totally_empty_work(r,

                                            _freed_bytes,

                                            _cleared_h_regions,

                                            _freed_regions,

                                            _unclean_region_list,

                                            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;

   }

   if (VerifyDuringGC) {

     HandleMark hm;  // handle scope

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

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

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

                      /* silent       */ false,

                      /* prev marking */ true);

   }

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

   g1p->record_concurrent_mark_cleanup_start();

   double start = os::elapsedTime();

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

   G1ParFinalCountTask g1_par_count_task(g1h, nextMarkBitMap(),

                                         &_region_bm, &_card_bm);

   if (ParallelGCThreads > 0) {

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

 #if 0

   gclog_or_tty->print_cr("used %1.2lf, live %1.2lf, garbage %1.2lf",

                          (double) g1_par_count_task.used_bytes() / (double) (1024 * 1024),

                          (double) g1_par_count_task.live_bytes() / (double) (1024 * 1024),

                          (double) known_garbage_bytes / (double) (1024 * 1024));

 #endif // 0

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

   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;

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

   if (ParallelGCThreads > 0) {

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

   }

   g1h->set_unclean_regions_coming(true);

   double note_end_end = os::elapsedTime();

   // Tell the mutators that there might be unclean regions coming...

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

       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(

                         g1_par_note_end_task.freed_bytes(),

                         g1_par_note_end_task.max_live_bytes());

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

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

                      /* prev marking */ true);

   }

 }

 void ConcurrentMark::completeCleanup() {

   // A full collection intervened.

   if (has_aborted()) return;

   int first = 0;

   int last = (int)MAX2(ParallelGCThreads, (size_t)1);

   for (int t = 0; t < last; t++) {

     UncleanRegionList* list = &_par_cleanup_thread_state[t]->list;

     assert(list->well_formed(), "Inv");

     HeapRegion* hd = list->hd();

     while (hd != NULL) {

       // Now finish up the other stuff.

       hd->rem_set()->clear();

       HeapRegion* next_hd = hd->next_from_unclean_list();

       (void)list->pop();

       assert(list->hd() == next_hd, "how not?");

       _g1h->put_region_on_unclean_list(hd);

       if (!hd->isHumongous()) {

         // Add this to the _free_regions count by 1.

         _g1h->finish_free_region_work(0, 0, 1, NULL);

       }

       hd = list->hd();

       assert(hd == next_hd, "how not?");

     }

   }

 }

 class G1CMIsAliveClosure: public BoolObjectClosure {

   G1CollectedHeap* _g1;

  public:

   G1CMIsAliveClosure(G1CollectedHeap* g1) :

     _g1(g1)

   {}

   void do_object(oop obj) {

     assert(false, "not to be invoked");

   }

   bool 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 thisOop = oopDesc::load_decode_heap_oop(p);

     HeapWord* addr = (HeapWord*)thisOop;

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

       _bitMap->mark(addr);

       _cm->mark_stack_push(thisOop);

     }

   }

 };

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

   }

 };

 void ConcurrentMark::weakRefsWork(bool clear_all_soft_refs) {

   ResourceMark rm;

   HandleMark   hm;

   G1CollectedHeap* g1h   = G1CollectedHeap::heap();

   ReferenceProcessor* rp = g1h->ref_processor();

   // Process weak references.

   rp->setup_policy(clear_all_soft_refs);

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

   G1CMIsAliveClosure   g1IsAliveClosure  (g1h);

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

   G1CMDrainMarkingStackClosure

     g1DrainMarkingStackClosure(nextMarkBitMap(), &_markStack,

                                &g1KeepAliveClosure);

   // XXXYYY  Also: copy the parallel ref processing code from CMS.

   rp->process_discovered_references(&g1IsAliveClosure,

                                     &g1KeepAliveClosure,

                                     &g1DrainMarkingStackClosure,

                                     NULL);

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

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

   if (_markStack.overflow()) {

     set_has_overflown();

   }

   rp->enqueue_discovered_references();

   rp->verify_no_references_recorded();

   assert(!rp->discovery_enabled(), "should have been disabled");

   // Now clean up stale oops in SymbolTable and StringTable

   SymbolTable::unlink(&g1IsAliveClosure);

   StringTable::unlink(&g1IsAliveClosure);

 }

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

       } 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 (ParallelGCThreads > 0) {

     G1CollectedHeap::StrongRootsScope srs(g1h);

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

     int active_workers = ParallelGCThreads;

     set_phase(active_workers, false);

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

     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 (!restart_for_overflow())

     set_non_marking_state();

 #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 ReachablePrinterOopClosure: public OopClosure {

 private:

   G1CollectedHeap* _g1h;

   CMBitMapRO*      _bitmap;

   outputStream*    _out;

   bool             _use_prev_marking;

 public:

   ReachablePrinterOopClosure(CMBitMapRO*   bitmap,

                              outputStream* out,

                              bool          use_prev_marking) :

     _g1h(G1CollectedHeap::heap()),

     _bitmap(bitmap), _out(out), _use_prev_marking(use_prev_marking) { }

   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 (!_g1h->is_in_g1_reserved(obj))

       str = "outside G1 reserved";

     else {

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

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

       bool over_tams = false;

       if (_use_prev_marking) {

         over_tams = hr->obj_allocated_since_prev_marking(obj);

       } else {

         over_tams = hr->obj_allocated_since_next_marking(obj);

       }

       if (over_tams) {

         str = "over TAMS";

         if (_bitmap->isMarked((HeapWord*) obj)) {

           str2 = " AND MARKED";

         }

       } else if (_bitmap->isMarked((HeapWord*) obj)) {

         str = "marked";

       } else {

         str = "#### NOT MARKED ####";

       }

     }

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

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

   }

 };

 class ReachablePrinterClosure: public BitMapClosure {

 private:

   CMBitMapRO*   _bitmap;

   outputStream* _out;

   bool          _use_prev_marking;

 public:

   ReachablePrinterClosure(CMBitMapRO*   bitmap,

                           outputStream* out,

                           bool          use_prev_marking) :

     _bitmap(bitmap), _out(out), _use_prev_marking(use_prev_marking) { }

   bool do_bit(size_t offset) {

     HeapWord* addr = _bitmap->offsetToHeapWord(offset);

     ReachablePrinterOopClosure oopCl(_bitmap, _out, _use_prev_marking);

     _out->print_cr("  obj "PTR_FORMAT", offset %10d (marked)", addr, offset);

     oop(addr)->oop_iterate(&oopCl);

     _out->print_cr("");

     return true;

   }

 };

 class ObjInRegionReachablePrinterClosure : public ObjectClosure {

 private:

   CMBitMapRO*   _bitmap;

   outputStream* _out;

   bool          _use_prev_marking;

 public:

   ObjInRegionReachablePrinterClosure(CMBitMapRO*   bitmap,

                                      outputStream* out,

                                      bool          use_prev_marking) :

     _bitmap(bitmap), _out(out), _use_prev_marking(use_prev_marking) { }

   void do_object(oop o) {

     ReachablePrinterOopClosure oopCl(_bitmap, _out, _use_prev_marking);

     _out->print_cr("  obj "PTR_FORMAT" (over TAMS)", (void*) o);

     o->oop_iterate(&oopCl);

     _out->print_cr("");

   }

 };

 class RegionReachablePrinterClosure : public HeapRegionClosure {

 private:

   CMBitMapRO*   _bitmap;

   outputStream* _out;

   bool          _use_prev_marking;

 public:

   bool doHeapRegion(HeapRegion* hr) {

     HeapWord* b = hr->bottom();

     HeapWord* e = hr->end();

     HeapWord* t = hr->top();

     HeapWord* p = NULL;

     if (_use_prev_marking) {

       p = hr->prev_top_at_mark_start();

     } else {

       p = hr->next_top_at_mark_start();

     }

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

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

     _out->print_cr("");

     ObjInRegionReachablePrinterClosure ocl(_bitmap, _out, _use_prev_marking);

     hr->object_iterate_mem_careful(MemRegion(p, t), &ocl);

     return false;

   }

   RegionReachablePrinterClosure(CMBitMapRO*   bitmap,

                                 outputStream* out,

                                 bool          use_prev_marking) :

     _bitmap(bitmap), _out(out), _use_prev_marking(use_prev_marking) { }

 };

 void ConcurrentMark::print_reachable(bool use_prev_marking, const char* str) {

   gclog_or_tty->print_cr("== Doing reachable object 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;

   CMBitMapRO* bitmap = NULL;

   if (use_prev_marking) {

     bitmap = _prevMarkBitMap;

   } else {

     bitmap = _nextMarkBitMap;

   }

   out->print_cr("-- USING %s", (use_prev_marking) ? "PTAMS" : "NTAMS");

   out->cr();

   RegionReachablePrinterClosure rcl(bitmap, out, use_prev_marking);

   out->print_cr("--- ITERATING OVER REGIONS WITH TAMS < TOP");

   out->cr();

   _g1h->heap_region_iterate(&rcl);

   out->cr();

   ReachablePrinterClosure cl(bitmap, out, use_prev_marking);

   out->print_cr("--- ITERATING OVER MARKED OBJECTS ON THE BITMAP");

   out->cr();

   bitmap->iterate(&cl);

   out->cr();

   gclog_or_tty->print_cr("  done");

 }

 #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, "is_in_g1_reserved should ensure this");

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

     if (_g1h->is_obj_ill(obj, hr)) {

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

   HeapWord* addr = (HeapWord*)p;

   assert(addr >= _nextMarkBitMap->startWord() ||

          addr < _nextMarkBitMap->endWord(), "in a region");

   _nextMarkBitMap->clear(addr);

 }

 void ConcurrentMark::clearRangeBothMaps(MemRegion mr) {

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

   // the cast.

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

   _nextMarkBitMap->clearRange(mr);

 }

 HeapRegion*

 ConcurrentMark::claim_region(int task_num) {

   // "checkpoint" the finger

   HeapWord* finger = _finger;

   // _heap_end will not change underneath our feet; it only changes at

   // yield points.

   while (finger < _heap_end) {

     assert(_g1h->is_in_g1_reserved(finger), "invariant");

     // is the gap between reading the finger and doing the CAS too long?

     HeapRegion* curr_region   = _g1h->heap_region_containing(finger);

     HeapWord*   bottom        = curr_region->bottom();

     HeapWord*   end           = curr_region->end();

     HeapWord*   limit         = curr_region->next_top_at_mark_start();

     if (verbose_low())

       gclog_or_tty->print_cr("[%d] curr_region = "PTR_FORMAT" "

                              "["PTR_FORMAT", "PTR_FORMAT"), "

                              "limit = "PTR_FORMAT,

                              task_num, curr_region, bottom, end, limit);

     HeapWord* res =

       (HeapWord*) Atomic::cmpxchg_ptr(end, &_finger, finger);

     if (res == finger) {

       // we succeeded

       // notice that _finger == end cannot be guaranteed here since,

       // someone else might have moved the finger even further

       assert(_finger >= end, "the finger should have moved forward");

       if (verbose_low())

         gclog_or_tty->print_cr("[%d] we were successful with region = "

                                PTR_FORMAT, task_num, curr_region);

       if (limit > bottom) {

         if (verbose_low())

           gclog_or_tty->print_cr("[%d] region "PTR_FORMAT" is not empty, "

                                  "returning it ", task_num, curr_region);

         return curr_region;

       } else {

         assert(limit == bottom,

                "the region limit should be at bottom");

         if (verbose_low())

           gclog_or_tty->print_cr("[%d] region "PTR_FORMAT" is empty, "

                                  "returning NULL", task_num, curr_region);

         // we return NULL and the caller should try calling

         // claim_region() again.

         return NULL;

       }

     } else {

       assert(_finger > finger, "the finger should have moved forward");

       if (verbose_low())

         gclog_or_tty->print_cr("[%d] somebody else moved the finger, "

                                "global finger = "PTR_FORMAT", "

                                "our finger = "PTR_FORMAT,

                                task_num, _finger, finger);

       // read it again

       finger = _finger;

     }

   }

   return NULL;

 }

 void ConcurrentMark::oops_do(OopClosure* cl) {

   if (_markStack.size() > 0 && verbose_low())

     gclog_or_tty->print_cr("[global] scanning the global marking stack, "

                            "size = %d", _markStack.size());

   // we first iterate over the contents of the mark stack...

   _markStack.oops_do(cl);

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

     OopTaskQueue* queue = _task_queues->queue((int)i);

     if (queue->size() > 0 && verbose_low())

       gclog_or_tty->print_cr("[global] scanning task queue of task %d, "

                              "size = %d", i, queue->size());

     // ...then over the contents of the all the task queues.

     queue->oops_do(cl);

   }

   // finally, invalidate any entries that in the region stack that

   // point into the collection set

   if (_regionStack.invalidate_entries_into_cset()) {

     // otherwise, any gray objects copied during the evacuation pause

     // might not be visited.

     assert(_should_gray_objects, "invariant");

   }

 }

 void ConcurrentMark::clear_marking_state() {

   _markStack.setEmpty();

   _markStack.clear_overflow();

   _regionStack.setEmpty();

   _regionStack.clear_overflow();

   clear_has_overflown();

   _finger = _heap_start;

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

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

     queue->set_empty();

   }

 }

 void ConcurrentMark::print_stats() {

   if (verbose_stats()) {

     gclog_or_tty->print_cr("---------------------------------------------------------------------");

     for (size_t i = 0; i < _active_tasks; ++i) {

       _tasks[i]->print_stats();

       gclog_or_tty->print_cr("---------------------------------------------------------------------");

     }

   }

 }

 class CSMarkOopClosure: public OopClosure {

   friend class CSMarkBitMapClosure;

   G1CollectedHeap* _g1h;

   CMBitMap*        _bm;

   ConcurrentMark*  _cm;

   oop*             _ms;

   jint*            _array_ind_stack;

   int              _ms_size;

   int              _ms_ind;

   int              _array_increment;

   bool push(oop obj, int arr_ind = 0) {

     if (_ms_ind == _ms_size) {

       gclog_or_tty->print_cr("Mark stack is full.");

       return false;

     }

     _ms[_ms_ind] = obj;

     if (obj->is_objArray()) _array_ind_stack[_ms_ind] = arr_ind;

     _ms_ind++;

     return true;

   }

   oop pop() {

     if (_ms_ind == 0) return NULL;

     else {

       _ms_ind--;

       return _ms[_ms_ind];

     }

   }

   template <class T> bool drain() {

     while (_ms_ind > 0) {

       oop obj = pop();

       assert(obj != NULL, "Since index was non-zero.");

       if (obj->is_objArray()) {

         jint arr_ind = _array_ind_stack[_ms_ind];

         objArrayOop aobj = objArrayOop(obj);

         jint len = aobj->length();

         jint next_arr_ind = arr_ind + _array_increment;

         if (next_arr_ind < len) {

           push(obj, next_arr_ind);

         }

         // Now process this portion of this one.

         int lim = MIN2(next_arr_ind, len);

         for (int j = arr_ind; j < lim; j++) {

           do_oop(aobj->objArrayOopDesc::obj_at_addr<T>(j));

         }

       } else {

         obj->oop_iterate(this);

       }

       if (abort()) return false;

     }

     return true;

   }

 public:

   CSMarkOopClosure(ConcurrentMark* cm, int ms_size) :

     _g1h(G1CollectedHeap::heap()),

     _cm(cm),

     _bm(cm->nextMarkBitMap()),

     _ms_size(ms_size), _ms_ind(0),

     _ms(NEW_C_HEAP_ARRAY(oop, ms_size)),

     _array_ind_stack(NEW_C_HEAP_ARRAY(jint, ms_size)),

     _array_increment(MAX2(ms_size/8, 16))

   {}

   ~CSMarkOopClosure() {

     FREE_C_HEAP_ARRAY(oop, _ms);

     FREE_C_HEAP_ARRAY(jint, _array_ind_stack);

   }

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

     T heap_oop = oopDesc::load_heap_oop(p);

     if (oopDesc::is_null(heap_oop)) return;

     oop obj = oopDesc::decode_heap_oop_not_null(heap_oop);

     if (obj->is_forwarded()) {

       // If the object has already been forwarded, we have to make sure

       // that it's marked.  So follow the forwarding pointer.  Note that

       // this does the right thing for self-forwarding pointers in the

       // evacuation failure case.

       obj = obj->forwardee();

     }

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

     if (hr != NULL) {

       if (hr->in_collection_set()) {

         if (_g1h->is_obj_ill(obj)) {

           _bm->mark((HeapWord*)obj);

           if (!push(obj)) {

             gclog_or_tty->print_cr("Setting abort in CSMarkOopClosure because push failed.");

             set_abort();

           }

         }

       } else {

         // Outside the collection set; we need to gray it

         _cm->deal_with_reference(obj);

       }

     }

   }

 };

 class CSMarkBitMapClosure: public BitMapClosure {

   G1CollectedHeap* _g1h;

   CMBitMap*        _bitMap;

   ConcurrentMark*  _cm;

   CSMarkOopClosure _oop_cl;

 public:

   CSMarkBitMapClosure(ConcurrentMark* cm, int ms_size) :

     _g1h(G1CollectedHeap::heap()),

     _bitMap(cm->nextMarkBitMap()),

     _oop_cl(cm, ms_size)

   {}

   ~CSMarkBitMapClosure() {}

   bool do_bit(size_t offset) {

     // convert offset into a HeapWord*

     HeapWord* addr = _bitMap->offsetToHeapWord(offset);

     assert(_bitMap->endWord() && addr < _bitMap->endWord(),

            "address out of range");

     assert(_bitMap->isMarked(addr), "tautology");

     oop obj = oop(addr);

     if (!obj->is_forwarded()) {

       if (!_oop_cl.push(obj)) return false;

       if (UseCompressedOops) {

         if (!_oop_cl.drain<narrowOop>()) return false;

       } else {

         if (!_oop_cl.drain<oop>()) return false;

       }

     }

     // Otherwise...

     return true;

   }

 };

 class CompleteMarkingInCSHRClosure: public HeapRegionClosure {

   CMBitMap* _bm;

   CSMarkBitMapClosure _bit_cl;

   enum SomePrivateConstants {

     MSSize = 1000

   };

   bool _completed;

 public:

   CompleteMarkingInCSHRClosure(ConcurrentMark* cm) :

     _bm(cm->nextMarkBitMap()),

     _bit_cl(cm, MSSize),

     _completed(true)

   {}

   ~CompleteMarkingInCSHRClosure() {}

   bool doHeapRegion(HeapRegion* r) {

     if (!r->evacuation_failed()) {

       MemRegion mr = MemRegion(r->bottom(), r->next_top_at_mark_start());

       if (!mr.is_empty()) {

         if (!_bm->iterate(&_bit_cl, mr)) {

           _completed = false;

           return true;

         }

       }

     }

     return false;

   }

   bool completed() { return _completed; }

 };

 class ClearMarksInHRClosure: public HeapRegionClosure {

   CMBitMap* _bm;

 public:

   ClearMarksInHRClosure(CMBitMap* bm): _bm(bm) { }

   bool doHeapRegion(HeapRegion* r) {

     if (!r->used_region().is_empty() && !r->evacuation_failed()) {

       MemRegion usedMR = r->used_region();

       _bm->clearRange(r->used_region());

     }

     return false;

   }

 };

 void ConcurrentMark::complete_marking_in_collection_set() {

   G1CollectedHeap* g1h =  G1CollectedHeap::heap();

   if (!g1h->mark_in_progress()) {

     g1h->g1_policy()->record_mark_closure_time(0.0);

     return;

   }

   int i = 1;

   double start = os::elapsedTime();

   while (true) {

     i++;

     CompleteMarkingInCSHRClosure cmplt(this);

     g1h->collection_set_iterate(&cmplt);

     if (cmplt.completed()) break;

   }

   double end_time = os::elapsedTime();

   double elapsed_time_ms = (end_time - start) * 1000.0;

   g1h->g1_policy()->record_mark_closure_time(elapsed_time_ms);

   if (PrintGCDetails) {

     gclog_or_tty->print_cr("Mark closure took %5.2f ms.", elapsed_time_ms);

   }

   ClearMarksInHRClosure clr(nextMarkBitMap());

   g1h->collection_set_iterate(&clr);

 }

 // The next two methods deal with the following optimisation. Some

 // objects are gray by being marked and located above the finger. If

 // they are copied, during an evacuation pause, below the finger then

 // the need to be pushed on the stack. The observation is that, if

 // there are no regions in the collection set located above the

 // finger, then the above cannot happen, hence we do not need to

 // explicitly gray any objects when copying them to below the

 // finger. The global stack will be scanned to ensure that, if it

 // points to objects being copied, it will update their

 // location. There is a tricky situation with the gray objects in

 // region stack that are being coped, however. See the comment in

 // newCSet().

 void ConcurrentMark::newCSet() {

   if (!concurrent_marking_in_progress())

     // nothing to do if marking is not in progress

     return;

   // find what the lowest finger is among the global and local fingers

   _min_finger = _finger;

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

     CMTask* task = _tasks[i];

     HeapWord* task_finger = task->finger();

     if (task_finger != NULL && task_finger < _min_finger)

       _min_finger = task_finger;

   }

   _should_gray_objects = false;

   // This fixes a very subtle and fustrating bug. It might be the case

   // that, during en evacuation pause, heap regions that contain

   // objects that are gray (by being in regions contained in the

   // region stack) are included in the collection set. Since such gray

   // objects will be moved, and because it's not easy to redirect

   // region stack entries to point to a new location (because objects

   // in one region might be scattered to multiple regions after they

   // are copied), one option is to ensure that all marked objects

   // copied during a pause are pushed on the stack. Notice, however,

   // that this problem can only happen when the region stack is not

   // empty during an evacuation pause. So, we make the fix a bit less

   // conservative and ensure that regions are pushed on the stack,

   // irrespective whether all collection set regions are below the

   // finger, if the region stack is not empty. This is expected to be

   // a rare case, so I don't think it's necessary to be smarted about it.

   if (!region_stack_empty())

     _should_gray_objects = true;

 }

 void ConcurrentMark::registerCSetRegion(HeapRegion* hr) {

   if (!concurrent_marking_in_progress())

     return;

   HeapWord* region_end = hr->end();

   if (region_end > _min_finger)

     _should_gray_objects = true;

 }

 // abandon current marking iteration due to a Full GC

 void ConcurrentMark::abort() {

   // Clear all marks to force marking thread to do nothing

   _nextMarkBitMap->clearAll();

   // Empty mark stack

   clear_marking_state();

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

     _tasks[i]->clear_region_fields();

   _has_aborted = true;

   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();

   satb_mq_set.abandon_partial_marking();

   satb_mq_set.set_active_all_threads(false);

 }

 static void print_ms_time_info(const char* prefix, const char* name,

                                NumberSeq& ns) {

   gclog_or_tty->print_cr("%s%5d %12s: total time = %8.2f s (avg = %8.2f ms).",

                          prefix, ns.num(), name, ns.sum()/1000.0, ns.avg());

   if (ns.num() > 0) {

     gclog_or_tty->print_cr("%s         [std. dev = %8.2f ms, max = %8.2f ms]",

                            prefix, ns.sd(), ns.maximum());

   }

 }

 void ConcurrentMark::print_summary_info() {

   gclog_or_tty->print_cr(" Concurrent marking:");

   print_ms_time_info("  ", "init marks", _init_times);

   print_ms_time_info("  ", "remarks", _remark_times);

   {

     print_ms_time_info("     ", "final marks", _remark_mark_times);

     print_ms_time_info("     ", "weak refs", _remark_weak_ref_times);

   }

   print_ms_time_info("  ", "cleanups", _cleanup_times);

   gclog_or_tty->print_cr("    Final counting total time = %8.2f s (avg = %8.2f ms).",

                          _total_counting_time,

                          (_cleanup_times.num() > 0 ? _total_counting_time * 1000.0 /

                           (double)_cleanup_times.num()

                          : 0.0));

   if (G1ScrubRemSets) {

     gclog_or_tty->print_cr("    RS scrub total time = %8.2f s (avg = %8.2f ms).",

                            _total_rs_scrub_time,

                            (_cleanup_times.num() > 0 ? _total_rs_scrub_time * 1000.0 /

                             (double)_cleanup_times.num()

                            : 0.0));

   }

   gclog_or_tty->print_cr("  Total stop_world time = %8.2f s.",

                          (_init_times.sum() + _remark_times.sum() +

                           _cleanup_times.sum())/1000.0);

   gclog_or_tty->print_cr("  Total concurrent time = %8.2f s "

                 "(%8.2f s marking, %8.2f s counting).",

                 cmThread()->vtime_accum(),

                 cmThread()->vtime_mark_accum(),

                 cmThread()->vtime_count_accum());

 }

 void ConcurrentMark::print_worker_threads_on(outputStream* st) const {

   _parallel_workers->print_worker_threads_on(st);

 }

 // Closures

 // XXX: there seems to be a lot of code  duplication here;

 // should refactor and consolidate the shared code.

 // This closure is used to mark refs into the CMS generation in

 // the CMS bit map. Called at the first checkpoint.