1 /*
   2  * Copyright (c) 2001, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "classfile/metadataOnStackMark.hpp"
  27 #include "classfile/symbolTable.hpp"
  28 #include "code/codeCache.hpp"
  29 #include "gc/g1/concurrentMark.inline.hpp"
  30 #include "gc/g1/concurrentMarkThread.inline.hpp"
  31 #include "gc/g1/g1CollectedHeap.inline.hpp"
  32 #include "gc/g1/g1CollectorPolicy.hpp"
  33 #include "gc/g1/g1CollectorState.hpp"
  34 #include "gc/g1/g1OopClosures.inline.hpp"
  35 #include "gc/g1/g1RemSet.hpp"
  36 #include "gc/g1/g1StringDedup.hpp"
  37 #include "gc/g1/heapRegion.inline.hpp"
  38 #include "gc/g1/heapRegionManager.inline.hpp"
  39 #include "gc/g1/heapRegionRemSet.hpp"
  40 #include "gc/g1/heapRegionSet.inline.hpp"
  41 #include "gc/g1/suspendibleThreadSet.hpp"
  42 #include "gc/shared/gcId.hpp"
  43 #include "gc/shared/gcTimer.hpp"
  44 #include "gc/shared/gcTrace.hpp"
  45 #include "gc/shared/gcTraceTime.hpp"
  46 #include "gc/shared/genOopClosures.inline.hpp"
  47 #include "gc/shared/referencePolicy.hpp"
  48 #include "gc/shared/strongRootsScope.hpp"
  49 #include "gc/shared/taskqueue.inline.hpp"
  50 #include "gc/shared/vmGCOperations.hpp"
  51 #include "logging/log.hpp"
  52 #include "memory/allocation.hpp"
  53 #include "memory/resourceArea.hpp"
  54 #include "oops/oop.inline.hpp"
  55 #include "runtime/atomic.inline.hpp"
  56 #include "runtime/handles.inline.hpp"
  57 #include "runtime/java.hpp"
  58 #include "runtime/prefetch.inline.hpp"
  59 #include "services/memTracker.hpp"
  60 
  61 // Concurrent marking bit map wrapper
  62 
  63 CMBitMapRO::CMBitMapRO(int shifter) :
  64   _bm(),
  65   _shifter(shifter) {
  66   _bmStartWord = 0;
  67   _bmWordSize = 0;
  68 }
  69 
  70 HeapWord* CMBitMapRO::getNextMarkedWordAddress(const HeapWord* addr,
  71                                                const HeapWord* limit) const {
  72   // First we must round addr *up* to a possible object boundary.
  73   addr = (HeapWord*)align_size_up((intptr_t)addr,
  74                                   HeapWordSize << _shifter);
  75   size_t addrOffset = heapWordToOffset(addr);
  76   if (limit == NULL) {
  77     limit = _bmStartWord + _bmWordSize;
  78   }
  79   size_t limitOffset = heapWordToOffset(limit);
  80   size_t nextOffset = _bm.get_next_one_offset(addrOffset, limitOffset);
  81   HeapWord* nextAddr = offsetToHeapWord(nextOffset);
  82   assert(nextAddr >= addr, "get_next_one postcondition");
  83   assert(nextAddr == limit || isMarked(nextAddr),
  84          "get_next_one postcondition");
  85   return nextAddr;
  86 }
  87 
  88 HeapWord* CMBitMapRO::getNextUnmarkedWordAddress(const HeapWord* addr,
  89                                                  const HeapWord* limit) const {
  90   size_t addrOffset = heapWordToOffset(addr);
  91   if (limit == NULL) {
  92     limit = _bmStartWord + _bmWordSize;
  93   }
  94   size_t limitOffset = heapWordToOffset(limit);
  95   size_t nextOffset = _bm.get_next_zero_offset(addrOffset, limitOffset);
  96   HeapWord* nextAddr = offsetToHeapWord(nextOffset);
  97   assert(nextAddr >= addr, "get_next_one postcondition");
  98   assert(nextAddr == limit || !isMarked(nextAddr),
  99          "get_next_one postcondition");
 100   return nextAddr;
 101 }
 102 
 103 int CMBitMapRO::heapWordDiffToOffsetDiff(size_t diff) const {
 104   assert((diff & ((1 << _shifter) - 1)) == 0, "argument check");
 105   return (int) (diff >> _shifter);
 106 }
 107 
 108 #ifndef PRODUCT
 109 bool CMBitMapRO::covers(MemRegion heap_rs) const {
 110   // assert(_bm.map() == _virtual_space.low(), "map inconsistency");
 111   assert(((size_t)_bm.size() * ((size_t)1 << _shifter)) == _bmWordSize,
 112          "size inconsistency");
 113   return _bmStartWord == (HeapWord*)(heap_rs.start()) &&
 114          _bmWordSize  == heap_rs.word_size();
 115 }
 116 #endif
 117 
 118 void CMBitMapRO::print_on_error(outputStream* st, const char* prefix) const {
 119   _bm.print_on_error(st, prefix);
 120 }
 121 
 122 size_t CMBitMap::compute_size(size_t heap_size) {
 123   return ReservedSpace::allocation_align_size_up(heap_size / mark_distance());
 124 }
 125 
 126 size_t CMBitMap::mark_distance() {
 127   return MinObjAlignmentInBytes * BitsPerByte;
 128 }
 129 
 130 void CMBitMap::initialize(MemRegion heap, G1RegionToSpaceMapper* storage) {
 131   _bmStartWord = heap.start();
 132   _bmWordSize = heap.word_size();
 133 
 134   _bm.set_map((BitMap::bm_word_t*) storage->reserved().start());
 135   _bm.set_size(_bmWordSize >> _shifter);
 136 
 137   storage->set_mapping_changed_listener(&_listener);
 138 }
 139 
 140 void CMBitMapMappingChangedListener::on_commit(uint start_region, size_t num_regions, bool zero_filled) {
 141   if (zero_filled) {
 142     return;
 143   }
 144   // We need to clear the bitmap on commit, removing any existing information.
 145   MemRegion mr(G1CollectedHeap::heap()->bottom_addr_for_region(start_region), num_regions * HeapRegion::GrainWords);
 146   _bm->clearRange(mr);
 147 }
 148 
 149 // Closure used for clearing the given mark bitmap.
 150 class ClearBitmapHRClosure : public HeapRegionClosure {
 151  private:
 152   ConcurrentMark* _cm;
 153   CMBitMap* _bitmap;
 154   bool _may_yield;      // The closure may yield during iteration. If yielded, abort the iteration.
 155  public:
 156   ClearBitmapHRClosure(ConcurrentMark* cm, CMBitMap* bitmap, bool may_yield) : HeapRegionClosure(), _cm(cm), _bitmap(bitmap), _may_yield(may_yield) {
 157     assert(!may_yield || cm != NULL, "CM must be non-NULL if this closure is expected to yield.");
 158   }
 159 
 160   virtual bool doHeapRegion(HeapRegion* r) {
 161     size_t const chunk_size_in_words = M / HeapWordSize;
 162 
 163     HeapWord* cur = r->bottom();
 164     HeapWord* const end = r->end();
 165 
 166     while (cur < end) {
 167       MemRegion mr(cur, MIN2(cur + chunk_size_in_words, end));
 168       _bitmap->clearRange(mr);
 169 
 170       cur += chunk_size_in_words;
 171 
 172       // Abort iteration if after yielding the marking has been aborted.
 173       if (_may_yield && _cm->do_yield_check() && _cm->has_aborted()) {
 174         return true;
 175       }
 176       // Repeat the asserts from before the start of the closure. We will do them
 177       // as asserts here to minimize their overhead on the product. However, we
 178       // will have them as guarantees at the beginning / end of the bitmap
 179       // clearing to get some checking in the product.
 180       assert(!_may_yield || _cm->cmThread()->during_cycle(), "invariant");
 181       assert(!_may_yield || !G1CollectedHeap::heap()->collector_state()->mark_in_progress(), "invariant");
 182     }
 183 
 184     return false;
 185   }
 186 };
 187 
 188 class ParClearNextMarkBitmapTask : public AbstractGangTask {
 189   ClearBitmapHRClosure* _cl;
 190   HeapRegionClaimer     _hrclaimer;
 191   bool                  _suspendible; // If the task is suspendible, workers must join the STS.
 192 
 193 public:
 194   ParClearNextMarkBitmapTask(ClearBitmapHRClosure *cl, uint n_workers, bool suspendible) :
 195       _cl(cl), _suspendible(suspendible), AbstractGangTask("Parallel Clear Bitmap Task"), _hrclaimer(n_workers) {}
 196 
 197   void work(uint worker_id) {
 198     SuspendibleThreadSetJoiner sts_join(_suspendible);
 199     G1CollectedHeap::heap()->heap_region_par_iterate(_cl, worker_id, &_hrclaimer, true);
 200   }
 201 };
 202 
 203 void CMBitMap::clearAll() {
 204   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 205   ClearBitmapHRClosure cl(NULL, this, false /* may_yield */);
 206   uint n_workers = g1h->workers()->active_workers();
 207   ParClearNextMarkBitmapTask task(&cl, n_workers, false);
 208   g1h->workers()->run_task(&task);
 209   guarantee(cl.complete(), "Must have completed iteration.");
 210   return;
 211 }
 212 
 213 void CMBitMap::markRange(MemRegion mr) {
 214   mr.intersection(MemRegion(_bmStartWord, _bmWordSize));
 215   assert(!mr.is_empty(), "unexpected empty region");
 216   assert((offsetToHeapWord(heapWordToOffset(mr.end())) ==
 217           ((HeapWord *) mr.end())),
 218          "markRange memory region end is not card aligned");
 219   // convert address range into offset range
 220   _bm.at_put_range(heapWordToOffset(mr.start()),
 221                    heapWordToOffset(mr.end()), true);
 222 }
 223 
 224 void CMBitMap::clearRange(MemRegion mr) {
 225   mr.intersection(MemRegion(_bmStartWord, _bmWordSize));
 226   assert(!mr.is_empty(), "unexpected empty region");
 227   // convert address range into offset range
 228   _bm.at_put_range(heapWordToOffset(mr.start()),
 229                    heapWordToOffset(mr.end()), false);
 230 }
 231 
 232 MemRegion CMBitMap::getAndClearMarkedRegion(HeapWord* addr,
 233                                             HeapWord* end_addr) {
 234   HeapWord* start = getNextMarkedWordAddress(addr);
 235   start = MIN2(start, end_addr);
 236   HeapWord* end   = getNextUnmarkedWordAddress(start);
 237   end = MIN2(end, end_addr);
 238   assert(start <= end, "Consistency check");
 239   MemRegion mr(start, end);
 240   if (!mr.is_empty()) {
 241     clearRange(mr);
 242   }
 243   return mr;
 244 }
 245 
 246 CMMarkStack::CMMarkStack(ConcurrentMark* cm) :
 247   _base(NULL), _cm(cm)
 248 {}
 249 
 250 bool CMMarkStack::allocate(size_t capacity) {
 251   // allocate a stack of the requisite depth
 252   ReservedSpace rs(ReservedSpace::allocation_align_size_up(capacity * sizeof(oop)));
 253   if (!rs.is_reserved()) {
 254     warning("ConcurrentMark MarkStack allocation failure");
 255     return false;
 256   }
 257   MemTracker::record_virtual_memory_type((address)rs.base(), mtGC);
 258   if (!_virtual_space.initialize(rs, rs.size())) {
 259     warning("ConcurrentMark MarkStack backing store failure");
 260     // Release the virtual memory reserved for the marking stack
 261     rs.release();
 262     return false;
 263   }
 264   assert(_virtual_space.committed_size() == rs.size(),
 265          "Didn't reserve backing store for all of ConcurrentMark stack?");
 266   _base = (oop*) _virtual_space.low();
 267   setEmpty();
 268   _capacity = (jint) capacity;
 269   _saved_index = -1;
 270   _should_expand = false;
 271   return true;
 272 }
 273 
 274 void CMMarkStack::expand() {
 275   // Called, during remark, if we've overflown the marking stack during marking.
 276   assert(isEmpty(), "stack should been emptied while handling overflow");
 277   assert(_capacity <= (jint) MarkStackSizeMax, "stack bigger than permitted");
 278   // Clear expansion flag
 279   _should_expand = false;
 280   if (_capacity == (jint) MarkStackSizeMax) {
 281     log_trace(gc)("(benign) Can't expand marking stack capacity, at max size limit");
 282     return;
 283   }
 284   // Double capacity if possible
 285   jint new_capacity = MIN2(_capacity*2, (jint) MarkStackSizeMax);
 286   // Do not give up existing stack until we have managed to
 287   // get the double capacity that we desired.
 288   ReservedSpace rs(ReservedSpace::allocation_align_size_up(new_capacity *
 289                                                            sizeof(oop)));
 290   if (rs.is_reserved()) {
 291     // Release the backing store associated with old stack
 292     _virtual_space.release();
 293     // Reinitialize virtual space for new stack
 294     if (!_virtual_space.initialize(rs, rs.size())) {
 295       fatal("Not enough swap for expanded marking stack capacity");
 296     }
 297     _base = (oop*)(_virtual_space.low());
 298     _index = 0;
 299     _capacity = new_capacity;
 300   } else {
 301     // Failed to double capacity, continue;
 302     log_trace(gc)("(benign) Failed to expand marking stack capacity from " SIZE_FORMAT "K to " SIZE_FORMAT "K",
 303                   _capacity / K, new_capacity / K);
 304   }
 305 }
 306 
 307 void CMMarkStack::set_should_expand() {
 308   // If we're resetting the marking state because of an
 309   // marking stack overflow, record that we should, if
 310   // possible, expand the stack.
 311   _should_expand = _cm->has_overflown();
 312 }
 313 
 314 CMMarkStack::~CMMarkStack() {
 315   if (_base != NULL) {
 316     _base = NULL;
 317     _virtual_space.release();
 318   }
 319 }
 320 
 321 void CMMarkStack::par_push_arr(oop* ptr_arr, int n) {
 322   MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);
 323   jint start = _index;
 324   jint next_index = start + n;
 325   if (next_index > _capacity) {
 326     _overflow = true;
 327     return;
 328   }
 329   // Otherwise.
 330   _index = next_index;
 331   for (int i = 0; i < n; i++) {
 332     int ind = start + i;
 333     assert(ind < _capacity, "By overflow test above.");
 334     _base[ind] = ptr_arr[i];
 335   }
 336 }
 337 
 338 bool CMMarkStack::par_pop_arr(oop* ptr_arr, int max, int* n) {
 339   MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);
 340   jint index = _index;
 341   if (index == 0) {
 342     *n = 0;
 343     return false;
 344   } else {
 345     int k = MIN2(max, index);
 346     jint  new_ind = index - k;
 347     for (int j = 0; j < k; j++) {
 348       ptr_arr[j] = _base[new_ind + j];
 349     }
 350     _index = new_ind;
 351     *n = k;
 352     return true;
 353   }
 354 }
 355 
 356 void CMMarkStack::note_start_of_gc() {
 357   assert(_saved_index == -1,
 358          "note_start_of_gc()/end_of_gc() bracketed incorrectly");
 359   _saved_index = _index;
 360 }
 361 
 362 void CMMarkStack::note_end_of_gc() {
 363   // This is intentionally a guarantee, instead of an assert. If we
 364   // accidentally add something to the mark stack during GC, it
 365   // will be a correctness issue so it's better if we crash. we'll
 366   // only check this once per GC anyway, so it won't be a performance
 367   // issue in any way.
 368   guarantee(_saved_index == _index,
 369             "saved index: %d index: %d", _saved_index, _index);
 370   _saved_index = -1;
 371 }
 372 
 373 CMRootRegions::CMRootRegions() :
 374   _young_list(NULL), _cm(NULL), _scan_in_progress(false),
 375   _should_abort(false),  _next_survivor(NULL) { }
 376 
 377 void CMRootRegions::init(G1CollectedHeap* g1h, ConcurrentMark* cm) {
 378   _young_list = g1h->young_list();
 379   _cm = cm;
 380 }
 381 
 382 void CMRootRegions::prepare_for_scan() {
 383   assert(!scan_in_progress(), "pre-condition");
 384 
 385   // Currently, only survivors can be root regions.
 386   assert(_next_survivor == NULL, "pre-condition");
 387   _next_survivor = _young_list->first_survivor_region();
 388   _scan_in_progress = (_next_survivor != NULL);
 389   _should_abort = false;
 390 }
 391 
 392 HeapRegion* CMRootRegions::claim_next() {
 393   if (_should_abort) {
 394     // If someone has set the should_abort flag, we return NULL to
 395     // force the caller to bail out of their loop.
 396     return NULL;
 397   }
 398 
 399   // Currently, only survivors can be root regions.
 400   HeapRegion* res = _next_survivor;
 401   if (res != NULL) {
 402     MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);
 403     // Read it again in case it changed while we were waiting for the lock.
 404     res = _next_survivor;
 405     if (res != NULL) {
 406       if (res == _young_list->last_survivor_region()) {
 407         // We just claimed the last survivor so store NULL to indicate
 408         // that we're done.
 409         _next_survivor = NULL;
 410       } else {
 411         _next_survivor = res->get_next_young_region();
 412       }
 413     } else {
 414       // Someone else claimed the last survivor while we were trying
 415       // to take the lock so nothing else to do.
 416     }
 417   }
 418   assert(res == NULL || res->is_survivor(), "post-condition");
 419 
 420   return res;
 421 }
 422 
 423 void CMRootRegions::scan_finished() {
 424   assert(scan_in_progress(), "pre-condition");
 425 
 426   // Currently, only survivors can be root regions.
 427   if (!_should_abort) {
 428     assert(_next_survivor == NULL, "we should have claimed all survivors");
 429   }
 430   _next_survivor = NULL;
 431 
 432   {
 433     MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);
 434     _scan_in_progress = false;
 435     RootRegionScan_lock->notify_all();
 436   }
 437 }
 438 
 439 bool CMRootRegions::wait_until_scan_finished() {
 440   if (!scan_in_progress()) return false;
 441 
 442   {
 443     MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);
 444     while (scan_in_progress()) {
 445       RootRegionScan_lock->wait(Mutex::_no_safepoint_check_flag);
 446     }
 447   }
 448   return true;
 449 }
 450 
 451 uint ConcurrentMark::scale_parallel_threads(uint n_par_threads) {
 452   return MAX2((n_par_threads + 2) / 4, 1U);
 453 }
 454 
 455 ConcurrentMark::ConcurrentMark(G1CollectedHeap* g1h, G1RegionToSpaceMapper* prev_bitmap_storage, G1RegionToSpaceMapper* next_bitmap_storage) :
 456   _g1h(g1h),
 457   _markBitMap1(),
 458   _markBitMap2(),
 459   _parallel_marking_threads(0),
 460   _max_parallel_marking_threads(0),
 461   _sleep_factor(0.0),
 462   _marking_task_overhead(1.0),
 463   _cleanup_sleep_factor(0.0),
 464   _cleanup_task_overhead(1.0),
 465   _cleanup_list("Cleanup List"),
 466   _region_bm((BitMap::idx_t)(g1h->max_regions()), false /* in_resource_area*/),
 467   _card_bm((g1h->reserved_region().byte_size() + CardTableModRefBS::card_size - 1) >>
 468             CardTableModRefBS::card_shift,
 469             false /* in_resource_area*/),
 470 
 471   _prevMarkBitMap(&_markBitMap1),
 472   _nextMarkBitMap(&_markBitMap2),
 473 
 474   _markStack(this),
 475   // _finger set in set_non_marking_state
 476 
 477   _max_worker_id(ParallelGCThreads),
 478   // _active_tasks set in set_non_marking_state
 479   // _tasks set inside the constructor
 480   _task_queues(new CMTaskQueueSet((int) _max_worker_id)),
 481   _terminator(ParallelTaskTerminator((int) _max_worker_id, _task_queues)),
 482 
 483   _has_overflown(false),
 484   _concurrent(false),
 485   _has_aborted(false),
 486   _restart_for_overflow(false),
 487   _concurrent_marking_in_progress(false),
 488 
 489   // _verbose_level set below
 490 
 491   _init_times(),
 492   _remark_times(), _remark_mark_times(), _remark_weak_ref_times(),
 493   _cleanup_times(),
 494   _total_counting_time(0.0),
 495   _total_rs_scrub_time(0.0),
 496 
 497   _parallel_workers(NULL),
 498 
 499   _count_card_bitmaps(NULL),
 500   _count_marked_bytes(NULL),
 501   _completed_initialization(false) {
 502 
 503   _markBitMap1.initialize(g1h->reserved_region(), prev_bitmap_storage);
 504   _markBitMap2.initialize(g1h->reserved_region(), next_bitmap_storage);
 505 
 506   // Create & start a ConcurrentMark thread.
 507   _cmThread = new ConcurrentMarkThread(this);
 508   assert(cmThread() != NULL, "CM Thread should have been created");
 509   assert(cmThread()->cm() != NULL, "CM Thread should refer to this cm");
 510   if (_cmThread->osthread() == NULL) {
 511       vm_shutdown_during_initialization("Could not create ConcurrentMarkThread");
 512   }
 513 
 514   assert(CGC_lock != NULL, "Where's the CGC_lock?");
 515   assert(_markBitMap1.covers(g1h->reserved_region()), "_markBitMap1 inconsistency");
 516   assert(_markBitMap2.covers(g1h->reserved_region()), "_markBitMap2 inconsistency");
 517 
 518   SATBMarkQueueSet& satb_qs = JavaThread::satb_mark_queue_set();
 519   satb_qs.set_buffer_size(G1SATBBufferSize);
 520 
 521   _root_regions.init(_g1h, this);
 522 
 523   if (ConcGCThreads > ParallelGCThreads) {
 524     warning("Can't have more ConcGCThreads (%u) "
 525             "than ParallelGCThreads (%u).",
 526             ConcGCThreads, ParallelGCThreads);
 527     return;
 528   }
 529   if (!FLAG_IS_DEFAULT(ConcGCThreads) && ConcGCThreads > 0) {
 530     // Note: ConcGCThreads has precedence over G1MarkingOverheadPercent
 531     // if both are set
 532     _sleep_factor             = 0.0;
 533     _marking_task_overhead    = 1.0;
 534   } else if (G1MarkingOverheadPercent > 0) {
 535     // We will calculate the number of parallel marking threads based
 536     // on a target overhead with respect to the soft real-time goal
 537     double marking_overhead = (double) G1MarkingOverheadPercent / 100.0;
 538     double overall_cm_overhead =
 539       (double) MaxGCPauseMillis * marking_overhead /
 540       (double) GCPauseIntervalMillis;
 541     double cpu_ratio = 1.0 / (double) os::processor_count();
 542     double marking_thread_num = ceil(overall_cm_overhead / cpu_ratio);
 543     double marking_task_overhead =
 544       overall_cm_overhead / marking_thread_num *
 545                                               (double) os::processor_count();
 546     double sleep_factor =
 547                        (1.0 - marking_task_overhead) / marking_task_overhead;
 548 
 549     FLAG_SET_ERGO(uint, ConcGCThreads, (uint) marking_thread_num);
 550     _sleep_factor             = sleep_factor;
 551     _marking_task_overhead    = marking_task_overhead;
 552   } else {
 553     // Calculate the number of parallel marking threads by scaling
 554     // the number of parallel GC threads.
 555     uint marking_thread_num = scale_parallel_threads(ParallelGCThreads);
 556     FLAG_SET_ERGO(uint, ConcGCThreads, marking_thread_num);
 557     _sleep_factor             = 0.0;
 558     _marking_task_overhead    = 1.0;
 559   }
 560 
 561   assert(ConcGCThreads > 0, "Should have been set");
 562   _parallel_marking_threads = ConcGCThreads;
 563   _max_parallel_marking_threads = _parallel_marking_threads;
 564 
 565   if (parallel_marking_threads() > 1) {
 566     _cleanup_task_overhead = 1.0;
 567   } else {
 568     _cleanup_task_overhead = marking_task_overhead();
 569   }
 570   _cleanup_sleep_factor =
 571                    (1.0 - cleanup_task_overhead()) / cleanup_task_overhead();
 572 
 573   _parallel_workers = new WorkGang("G1 Marker",
 574        _max_parallel_marking_threads, false, true);
 575   if (_parallel_workers == NULL) {
 576     vm_exit_during_initialization("Failed necessary allocation.");
 577   } else {
 578     _parallel_workers->initialize_workers();
 579   }
 580 
 581   if (FLAG_IS_DEFAULT(MarkStackSize)) {
 582     size_t mark_stack_size =
 583       MIN2(MarkStackSizeMax,
 584           MAX2(MarkStackSize, (size_t) (parallel_marking_threads() * TASKQUEUE_SIZE)));
 585     // Verify that the calculated value for MarkStackSize is in range.
 586     // It would be nice to use the private utility routine from Arguments.
 587     if (!(mark_stack_size >= 1 && mark_stack_size <= MarkStackSizeMax)) {
 588       warning("Invalid value calculated for MarkStackSize (" SIZE_FORMAT "): "
 589               "must be between 1 and " SIZE_FORMAT,
 590               mark_stack_size, MarkStackSizeMax);
 591       return;
 592     }
 593     FLAG_SET_ERGO(size_t, MarkStackSize, mark_stack_size);
 594   } else {
 595     // Verify MarkStackSize is in range.
 596     if (FLAG_IS_CMDLINE(MarkStackSize)) {
 597       if (FLAG_IS_DEFAULT(MarkStackSizeMax)) {
 598         if (!(MarkStackSize >= 1 && MarkStackSize <= MarkStackSizeMax)) {
 599           warning("Invalid value specified for MarkStackSize (" SIZE_FORMAT "): "
 600                   "must be between 1 and " SIZE_FORMAT,
 601                   MarkStackSize, MarkStackSizeMax);
 602           return;
 603         }
 604       } else if (FLAG_IS_CMDLINE(MarkStackSizeMax)) {
 605         if (!(MarkStackSize >= 1 && MarkStackSize <= MarkStackSizeMax)) {
 606           warning("Invalid value specified for MarkStackSize (" SIZE_FORMAT ")"
 607                   " or for MarkStackSizeMax (" SIZE_FORMAT ")",
 608                   MarkStackSize, MarkStackSizeMax);
 609           return;
 610         }
 611       }
 612     }
 613   }
 614 
 615   if (!_markStack.allocate(MarkStackSize)) {
 616     warning("Failed to allocate CM marking stack");
 617     return;
 618   }
 619 
 620   _tasks = NEW_C_HEAP_ARRAY(CMTask*, _max_worker_id, mtGC);
 621   _accum_task_vtime = NEW_C_HEAP_ARRAY(double, _max_worker_id, mtGC);
 622 
 623   _count_card_bitmaps = NEW_C_HEAP_ARRAY(BitMap,  _max_worker_id, mtGC);
 624   _count_marked_bytes = NEW_C_HEAP_ARRAY(size_t*, _max_worker_id, mtGC);
 625 
 626   BitMap::idx_t card_bm_size = _card_bm.size();
 627 
 628   // so that the assertion in MarkingTaskQueue::task_queue doesn't fail
 629   _active_tasks = _max_worker_id;
 630 
 631   uint max_regions = _g1h->max_regions();
 632   for (uint i = 0; i < _max_worker_id; ++i) {
 633     CMTaskQueue* task_queue = new CMTaskQueue();
 634     task_queue->initialize();
 635     _task_queues->register_queue(i, task_queue);
 636 
 637     _count_card_bitmaps[i] = BitMap(card_bm_size, false);
 638     _count_marked_bytes[i] = NEW_C_HEAP_ARRAY(size_t, max_regions, mtGC);
 639 
 640     _tasks[i] = new CMTask(i, this,
 641                            _count_marked_bytes[i],
 642                            &_count_card_bitmaps[i],
 643                            task_queue, _task_queues);
 644 
 645     _accum_task_vtime[i] = 0.0;
 646   }
 647 
 648   // Calculate the card number for the bottom of the heap. Used
 649   // in biasing indexes into the accounting card bitmaps.
 650   _heap_bottom_card_num =
 651     intptr_t(uintptr_t(_g1h->reserved_region().start()) >>
 652                                 CardTableModRefBS::card_shift);
 653 
 654   // Clear all the liveness counting data
 655   clear_all_count_data();
 656 
 657   // so that the call below can read a sensible value
 658   _heap_start = g1h->reserved_region().start();
 659   set_non_marking_state();
 660   _completed_initialization = true;
 661 }
 662 
 663 void ConcurrentMark::reset() {
 664   // Starting values for these two. This should be called in a STW
 665   // phase.
 666   MemRegion reserved = _g1h->g1_reserved();
 667   _heap_start = reserved.start();
 668   _heap_end   = reserved.end();
 669 
 670   // Separated the asserts so that we know which one fires.
 671   assert(_heap_start != NULL, "heap bounds should look ok");
 672   assert(_heap_end != NULL, "heap bounds should look ok");
 673   assert(_heap_start < _heap_end, "heap bounds should look ok");
 674 
 675   // Reset all the marking data structures and any necessary flags
 676   reset_marking_state();
 677 
 678   // We do reset all of them, since different phases will use
 679   // different number of active threads. So, it's easiest to have all
 680   // of them ready.
 681   for (uint i = 0; i < _max_worker_id; ++i) {
 682     _tasks[i]->reset(_nextMarkBitMap);
 683   }
 684 
 685   // we need this to make sure that the flag is on during the evac
 686   // pause with initial mark piggy-backed
 687   set_concurrent_marking_in_progress();
 688 }
 689 
 690 
 691 void ConcurrentMark::reset_marking_state(bool clear_overflow) {
 692   _markStack.set_should_expand();
 693   _markStack.setEmpty();        // Also clears the _markStack overflow flag
 694   if (clear_overflow) {
 695     clear_has_overflown();
 696   } else {
 697     assert(has_overflown(), "pre-condition");
 698   }
 699   _finger = _heap_start;
 700 
 701   for (uint i = 0; i < _max_worker_id; ++i) {
 702     CMTaskQueue* queue = _task_queues->queue(i);
 703     queue->set_empty();
 704   }
 705 }
 706 
 707 void ConcurrentMark::set_concurrency(uint active_tasks) {
 708   assert(active_tasks <= _max_worker_id, "we should not have more");
 709 
 710   _active_tasks = active_tasks;
 711   // Need to update the three data structures below according to the
 712   // number of active threads for this phase.
 713   _terminator   = ParallelTaskTerminator((int) active_tasks, _task_queues);
 714   _first_overflow_barrier_sync.set_n_workers((int) active_tasks);
 715   _second_overflow_barrier_sync.set_n_workers((int) active_tasks);
 716 }
 717 
 718 void ConcurrentMark::set_concurrency_and_phase(uint active_tasks, bool concurrent) {
 719   set_concurrency(active_tasks);
 720 
 721   _concurrent = concurrent;
 722   // We propagate this to all tasks, not just the active ones.
 723   for (uint i = 0; i < _max_worker_id; ++i)
 724     _tasks[i]->set_concurrent(concurrent);
 725 
 726   if (concurrent) {
 727     set_concurrent_marking_in_progress();
 728   } else {
 729     // We currently assume that the concurrent flag has been set to
 730     // false before we start remark. At this point we should also be
 731     // in a STW phase.
 732     assert(!concurrent_marking_in_progress(), "invariant");
 733     assert(out_of_regions(),
 734            "only way to get here: _finger: " PTR_FORMAT ", _heap_end: " PTR_FORMAT,
 735            p2i(_finger), p2i(_heap_end));
 736   }
 737 }
 738 
 739 void ConcurrentMark::set_non_marking_state() {
 740   // We set the global marking state to some default values when we're
 741   // not doing marking.
 742   reset_marking_state();
 743   _active_tasks = 0;
 744   clear_concurrent_marking_in_progress();
 745 }
 746 
 747 ConcurrentMark::~ConcurrentMark() {
 748   // The ConcurrentMark instance is never freed.
 749   ShouldNotReachHere();
 750 }
 751 
 752 void ConcurrentMark::clearNextBitmap() {
 753   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 754 
 755   // Make sure that the concurrent mark thread looks to still be in
 756   // the current cycle.
 757   guarantee(cmThread()->during_cycle(), "invariant");
 758 
 759   // We are finishing up the current cycle by clearing the next
 760   // marking bitmap and getting it ready for the next cycle. During
 761   // this time no other cycle can start. So, let's make sure that this
 762   // is the case.
 763   guarantee(!g1h->collector_state()->mark_in_progress(), "invariant");
 764 
 765   ClearBitmapHRClosure cl(this, _nextMarkBitMap, true /* may_yield */);
 766   ParClearNextMarkBitmapTask task(&cl, parallel_marking_threads(), true);
 767   _parallel_workers->run_task(&task);
 768 
 769   // Clear the liveness counting data. If the marking has been aborted, the abort()
 770   // call already did that.
 771   if (cl.complete()) {
 772     clear_all_count_data();
 773   }
 774 
 775   // Repeat the asserts from above.
 776   guarantee(cmThread()->during_cycle(), "invariant");
 777   guarantee(!g1h->collector_state()->mark_in_progress(), "invariant");
 778 }
 779 
 780 class CheckBitmapClearHRClosure : public HeapRegionClosure {
 781   CMBitMap* _bitmap;
 782   bool _error;
 783  public:
 784   CheckBitmapClearHRClosure(CMBitMap* bitmap) : _bitmap(bitmap) {
 785   }
 786 
 787   virtual bool doHeapRegion(HeapRegion* r) {
 788     // This closure can be called concurrently to the mutator, so we must make sure
 789     // that the result of the getNextMarkedWordAddress() call is compared to the
 790     // value passed to it as limit to detect any found bits.
 791     // We can use the region's orig_end() for the limit and the comparison value
 792     // as it always contains the "real" end of the region that never changes and
 793     // has no side effects.
 794     // Due to the latter, there can also be no problem with the compiler generating
 795     // reloads of the orig_end() call.
 796     HeapWord* end = r->orig_end();
 797     return _bitmap->getNextMarkedWordAddress(r->bottom(), end) != end;
 798   }
 799 };
 800 
 801 bool ConcurrentMark::nextMarkBitmapIsClear() {
 802   CheckBitmapClearHRClosure cl(_nextMarkBitMap);
 803   _g1h->heap_region_iterate(&cl);
 804   return cl.complete();
 805 }
 806 
 807 class NoteStartOfMarkHRClosure: public HeapRegionClosure {
 808 public:
 809   bool doHeapRegion(HeapRegion* r) {
 810     if (!r->is_continues_humongous()) {
 811       r->note_start_of_marking();
 812     }
 813     return false;
 814   }
 815 };
 816 
 817 void ConcurrentMark::checkpointRootsInitialPre() {
 818   G1CollectedHeap*   g1h = G1CollectedHeap::heap();
 819   G1CollectorPolicy* g1p = g1h->g1_policy();
 820 
 821   _has_aborted = false;
 822 
 823   // Initialize marking structures. This has to be done in a STW phase.
 824   reset();
 825 
 826   // For each region note start of marking.
 827   NoteStartOfMarkHRClosure startcl;
 828   g1h->heap_region_iterate(&startcl);
 829 }
 830 
 831 
 832 void ConcurrentMark::checkpointRootsInitialPost() {
 833   G1CollectedHeap*   g1h = G1CollectedHeap::heap();
 834 
 835   // If we force an overflow during remark, the remark operation will
 836   // actually abort and we'll restart concurrent marking. If we always
 837   // force an overflow during remark we'll never actually complete the
 838   // marking phase. So, we initialize this here, at the start of the
 839   // cycle, so that at the remaining overflow number will decrease at
 840   // every remark and we'll eventually not need to cause one.
 841   force_overflow_stw()->init();
 842 
 843   // Start Concurrent Marking weak-reference discovery.
 844   ReferenceProcessor* rp = g1h->ref_processor_cm();
 845   // enable ("weak") refs discovery
 846   rp->enable_discovery();
 847   rp->setup_policy(false); // snapshot the soft ref policy to be used in this cycle
 848 
 849   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();
 850   // This is the start of  the marking cycle, we're expected all
 851   // threads to have SATB queues with active set to false.
 852   satb_mq_set.set_active_all_threads(true, /* new active value */
 853                                      false /* expected_active */);
 854 
 855   _root_regions.prepare_for_scan();
 856 
 857   // update_g1_committed() will be called at the end of an evac pause
 858   // when marking is on. So, it's also called at the end of the
 859   // initial-mark pause to update the heap end, if the heap expands
 860   // during it. No need to call it here.
 861 }
 862 
 863 /*
 864  * Notice that in the next two methods, we actually leave the STS
 865  * during the barrier sync and join it immediately afterwards. If we
 866  * do not do this, the following deadlock can occur: one thread could
 867  * be in the barrier sync code, waiting for the other thread to also
 868  * sync up, whereas another one could be trying to yield, while also
 869  * waiting for the other threads to sync up too.
 870  *
 871  * Note, however, that this code is also used during remark and in
 872  * this case we should not attempt to leave / enter the STS, otherwise
 873  * we'll either hit an assert (debug / fastdebug) or deadlock
 874  * (product). So we should only leave / enter the STS if we are
 875  * operating concurrently.
 876  *
 877  * Because the thread that does the sync barrier has left the STS, it
 878  * is possible to be suspended for a Full GC or an evacuation pause
 879  * could occur. This is actually safe, since the entering the sync
 880  * barrier is one of the last things do_marking_step() does, and it
 881  * doesn't manipulate any data structures afterwards.
 882  */
 883 
 884 void ConcurrentMark::enter_first_sync_barrier(uint worker_id) {
 885   bool barrier_aborted;
 886   {
 887     SuspendibleThreadSetLeaver sts_leave(concurrent());
 888     barrier_aborted = !_first_overflow_barrier_sync.enter();
 889   }
 890 
 891   // at this point everyone should have synced up and not be doing any
 892   // more work
 893 
 894   if (barrier_aborted) {
 895     // If the barrier aborted we ignore the overflow condition and
 896     // just abort the whole marking phase as quickly as possible.
 897     return;
 898   }
 899 
 900   // If we're executing the concurrent phase of marking, reset the marking
 901   // state; otherwise the marking state is reset after reference processing,
 902   // during the remark pause.
 903   // If we reset here as a result of an overflow during the remark we will
 904   // see assertion failures from any subsequent set_concurrency_and_phase()
 905   // calls.
 906   if (concurrent()) {
 907     // let the task associated with with worker 0 do this
 908     if (worker_id == 0) {
 909       // task 0 is responsible for clearing the global data structures
 910       // We should be here because of an overflow. During STW we should
 911       // not clear the overflow flag since we rely on it being true when
 912       // we exit this method to abort the pause and restart concurrent
 913       // marking.
 914       reset_marking_state(true /* clear_overflow */);
 915       force_overflow()->update();
 916 
 917       log_info(gc)("GC concurrent-mark-reset-for-overflow");
 918     }
 919   }
 920 
 921   // after this, each task should reset its own data structures then
 922   // then go into the second barrier
 923 }
 924 
 925 void ConcurrentMark::enter_second_sync_barrier(uint worker_id) {
 926   SuspendibleThreadSetLeaver sts_leave(concurrent());
 927   _second_overflow_barrier_sync.enter();
 928 
 929   // at this point everything should be re-initialized and ready to go
 930 }
 931 
 932 #ifndef PRODUCT
 933 void ForceOverflowSettings::init() {
 934   _num_remaining = G1ConcMarkForceOverflow;
 935   _force = false;
 936   update();
 937 }
 938 
 939 void ForceOverflowSettings::update() {
 940   if (_num_remaining > 0) {
 941     _num_remaining -= 1;
 942     _force = true;
 943   } else {
 944     _force = false;
 945   }
 946 }
 947 
 948 bool ForceOverflowSettings::should_force() {
 949   if (_force) {
 950     _force = false;
 951     return true;
 952   } else {
 953     return false;
 954   }
 955 }
 956 #endif // !PRODUCT
 957 
 958 class CMConcurrentMarkingTask: public AbstractGangTask {
 959 private:
 960   ConcurrentMark*       _cm;
 961   ConcurrentMarkThread* _cmt;
 962 
 963 public:
 964   void work(uint worker_id) {
 965     assert(Thread::current()->is_ConcurrentGC_thread(),
 966            "this should only be done by a conc GC thread");
 967     ResourceMark rm;
 968 
 969     double start_vtime = os::elapsedVTime();
 970 
 971     {
 972       SuspendibleThreadSetJoiner sts_join;
 973 
 974       assert(worker_id < _cm->active_tasks(), "invariant");
 975       CMTask* the_task = _cm->task(worker_id);
 976       the_task->record_start_time();
 977       if (!_cm->has_aborted()) {
 978         do {
 979           double start_vtime_sec = os::elapsedVTime();
 980           double mark_step_duration_ms = G1ConcMarkStepDurationMillis;
 981 
 982           the_task->do_marking_step(mark_step_duration_ms,
 983                                     true  /* do_termination */,
 984                                     false /* is_serial*/);
 985 
 986           double end_vtime_sec = os::elapsedVTime();
 987           double elapsed_vtime_sec = end_vtime_sec - start_vtime_sec;
 988           _cm->clear_has_overflown();
 989 
 990           _cm->do_yield_check(worker_id);
 991 
 992           jlong sleep_time_ms;
 993           if (!_cm->has_aborted() && the_task->has_aborted()) {
 994             sleep_time_ms =
 995               (jlong) (elapsed_vtime_sec * _cm->sleep_factor() * 1000.0);
 996             {
 997               SuspendibleThreadSetLeaver sts_leave;
 998               os::sleep(Thread::current(), sleep_time_ms, false);
 999             }
1000           }
1001         } while (!_cm->has_aborted() && the_task->has_aborted());
1002       }
1003       the_task->record_end_time();
1004       guarantee(!the_task->has_aborted() || _cm->has_aborted(), "invariant");
1005     }
1006 
1007     double end_vtime = os::elapsedVTime();
1008     _cm->update_accum_task_vtime(worker_id, end_vtime - start_vtime);
1009   }
1010 
1011   CMConcurrentMarkingTask(ConcurrentMark* cm,
1012                           ConcurrentMarkThread* cmt) :
1013       AbstractGangTask("Concurrent Mark"), _cm(cm), _cmt(cmt) { }
1014 
1015   ~CMConcurrentMarkingTask() { }
1016 };
1017 
1018 // Calculates the number of active workers for a concurrent
1019 // phase.
1020 uint ConcurrentMark::calc_parallel_marking_threads() {
1021   uint n_conc_workers = 0;
1022   if (!UseDynamicNumberOfGCThreads ||
1023       (!FLAG_IS_DEFAULT(ConcGCThreads) &&
1024        !ForceDynamicNumberOfGCThreads)) {
1025     n_conc_workers = max_parallel_marking_threads();
1026   } else {
1027     n_conc_workers =
1028       AdaptiveSizePolicy::calc_default_active_workers(
1029                                    max_parallel_marking_threads(),
1030                                    1, /* Minimum workers */
1031                                    parallel_marking_threads(),
1032                                    Threads::number_of_non_daemon_threads());
1033     // Don't scale down "n_conc_workers" by scale_parallel_threads() because
1034     // that scaling has already gone into "_max_parallel_marking_threads".
1035   }
1036   assert(n_conc_workers > 0, "Always need at least 1");
1037   return n_conc_workers;
1038 }
1039 
1040 void ConcurrentMark::scanRootRegion(HeapRegion* hr, uint worker_id) {
1041   // Currently, only survivors can be root regions.
1042   assert(hr->next_top_at_mark_start() == hr->bottom(), "invariant");
1043   G1RootRegionScanClosure cl(_g1h, this, worker_id);
1044 
1045   const uintx interval = PrefetchScanIntervalInBytes;
1046   HeapWord* curr = hr->bottom();
1047   const HeapWord* end = hr->top();
1048   while (curr < end) {
1049     Prefetch::read(curr, interval);
1050     oop obj = oop(curr);
1051     int size = obj->oop_iterate_size(&cl);
1052     assert(size == obj->size(), "sanity");
1053     curr += size;
1054   }
1055 }
1056 
1057 class CMRootRegionScanTask : public AbstractGangTask {
1058 private:
1059   ConcurrentMark* _cm;
1060 
1061 public:
1062   CMRootRegionScanTask(ConcurrentMark* cm) :
1063     AbstractGangTask("Root Region Scan"), _cm(cm) { }
1064 
1065   void work(uint worker_id) {
1066     assert(Thread::current()->is_ConcurrentGC_thread(),
1067            "this should only be done by a conc GC thread");
1068 
1069     CMRootRegions* root_regions = _cm->root_regions();
1070     HeapRegion* hr = root_regions->claim_next();
1071     while (hr != NULL) {
1072       _cm->scanRootRegion(hr, worker_id);
1073       hr = root_regions->claim_next();
1074     }
1075   }
1076 };
1077 
1078 void ConcurrentMark::scanRootRegions() {
1079   double scan_start = os::elapsedTime();
1080 
1081   // Start of concurrent marking.
1082   ClassLoaderDataGraph::clear_claimed_marks();
1083 
1084   // scan_in_progress() will have been set to true only if there was
1085   // at least one root region to scan. So, if it's false, we
1086   // should not attempt to do any further work.
1087   if (root_regions()->scan_in_progress()) {
1088     log_info(gc)("GC concurrent-root-region-scan-start");
1089 
1090     _parallel_marking_threads = calc_parallel_marking_threads();
1091     assert(parallel_marking_threads() <= max_parallel_marking_threads(),
1092            "Maximum number of marking threads exceeded");
1093     uint active_workers = MAX2(1U, parallel_marking_threads());
1094 
1095     CMRootRegionScanTask task(this);
1096     _parallel_workers->set_active_workers(active_workers);
1097     _parallel_workers->run_task(&task);
1098 
1099     log_info(gc)("GC concurrent-root-region-scan-end, %1.7lf secs", os::elapsedTime() - scan_start);
1100 
1101     // It's possible that has_aborted() is true here without actually
1102     // aborting the survivor scan earlier. This is OK as it's
1103     // mainly used for sanity checking.
1104     root_regions()->scan_finished();
1105   }
1106 }
1107 
1108 void ConcurrentMark::markFromRoots() {
1109   // we might be tempted to assert that:
1110   // assert(asynch == !SafepointSynchronize::is_at_safepoint(),
1111   //        "inconsistent argument?");
1112   // However that wouldn't be right, because it's possible that
1113   // a safepoint is indeed in progress as a younger generation
1114   // stop-the-world GC happens even as we mark in this generation.
1115 
1116   _restart_for_overflow = false;
1117   force_overflow_conc()->init();
1118 
1119   // _g1h has _n_par_threads
1120   _parallel_marking_threads = calc_parallel_marking_threads();
1121   assert(parallel_marking_threads() <= max_parallel_marking_threads(),
1122     "Maximum number of marking threads exceeded");
1123 
1124   uint active_workers = MAX2(1U, parallel_marking_threads());
1125   assert(active_workers > 0, "Should have been set");
1126 
1127   // Parallel task terminator is set in "set_concurrency_and_phase()"
1128   set_concurrency_and_phase(active_workers, true /* concurrent */);
1129 
1130   CMConcurrentMarkingTask markingTask(this, cmThread());
1131   _parallel_workers->set_active_workers(active_workers);
1132   _parallel_workers->run_task(&markingTask);
1133   print_stats();
1134 }
1135 
1136 void ConcurrentMark::checkpointRootsFinal(bool clear_all_soft_refs) {
1137   // world is stopped at this checkpoint
1138   assert(SafepointSynchronize::is_at_safepoint(),
1139          "world should be stopped");
1140 
1141   G1CollectedHeap* g1h = G1CollectedHeap::heap();
1142 
1143   // If a full collection has happened, we shouldn't do this.
1144   if (has_aborted()) {
1145     g1h->collector_state()->set_mark_in_progress(false); // So bitmap clearing isn't confused
1146     return;
1147   }
1148 
1149   SvcGCMarker sgcm(SvcGCMarker::OTHER);
1150 
1151   if (VerifyDuringGC) {
1152     HandleMark hm;  // handle scope
1153     g1h->prepare_for_verify();
1154     Universe::verify(VerifyOption_G1UsePrevMarking, "During GC (before)");
1155   }
1156   g1h->check_bitmaps("Remark Start");
1157 
1158   G1CollectorPolicy* g1p = g1h->g1_policy();
1159   g1p->record_concurrent_mark_remark_start();
1160 
1161   double start = os::elapsedTime();
1162 
1163   checkpointRootsFinalWork();
1164 
1165   double mark_work_end = os::elapsedTime();
1166 
1167   weakRefsWork(clear_all_soft_refs);
1168 
1169   if (has_overflown()) {
1170     // Oops.  We overflowed.  Restart concurrent marking.
1171     _restart_for_overflow = true;
1172     log_develop(gc)("Remark led to restart for overflow.");
1173 
1174     // Verify the heap w.r.t. the previous marking bitmap.
1175     if (VerifyDuringGC) {
1176       HandleMark hm;  // handle scope
1177       g1h->prepare_for_verify();
1178       Universe::verify(VerifyOption_G1UsePrevMarking, "During GC (overflow)");
1179     }
1180 
1181     // Clear the marking state because we will be restarting
1182     // marking due to overflowing the global mark stack.
1183     reset_marking_state();
1184   } else {
1185     {
1186       GCTraceTime(Debug, gc) trace("GC aggregate-data", g1h->gc_timer_cm());
1187 
1188       // Aggregate the per-task counting data that we have accumulated
1189       // while marking.
1190       aggregate_count_data();
1191     }
1192 
1193     SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();
1194     // We're done with marking.
1195     // This is the end of  the marking cycle, we're expected all
1196     // threads to have SATB queues with active set to true.
1197     satb_mq_set.set_active_all_threads(false, /* new active value */
1198                                        true /* expected_active */);
1199 
1200     if (VerifyDuringGC) {
1201       HandleMark hm;  // handle scope
1202       g1h->prepare_for_verify();
1203       Universe::verify(VerifyOption_G1UseNextMarking, "During GC (after)");
1204     }
1205     g1h->check_bitmaps("Remark End");
1206     assert(!restart_for_overflow(), "sanity");
1207     // Completely reset the marking state since marking completed
1208     set_non_marking_state();
1209   }
1210 
1211   // Expand the marking stack, if we have to and if we can.
1212   if (_markStack.should_expand()) {
1213     _markStack.expand();
1214   }
1215 
1216   // Statistics
1217   double now = os::elapsedTime();
1218   _remark_mark_times.add((mark_work_end - start) * 1000.0);
1219   _remark_weak_ref_times.add((now - mark_work_end) * 1000.0);
1220   _remark_times.add((now - start) * 1000.0);
1221 
1222   g1p->record_concurrent_mark_remark_end();
1223 
1224   G1CMIsAliveClosure is_alive(g1h);
1225   g1h->gc_tracer_cm()->report_object_count_after_gc(&is_alive);
1226 }
1227 
1228 // Base class of the closures that finalize and verify the
1229 // liveness counting data.
1230 class CMCountDataClosureBase: public HeapRegionClosure {
1231 protected:
1232   G1CollectedHeap* _g1h;
1233   ConcurrentMark* _cm;
1234   CardTableModRefBS* _ct_bs;
1235 
1236   BitMap* _region_bm;
1237   BitMap* _card_bm;
1238 
1239   // Takes a region that's not empty (i.e., it has at least one
1240   // live object in it and sets its corresponding bit on the region
1241   // bitmap to 1. If the region is "starts humongous" it will also set
1242   // to 1 the bits on the region bitmap that correspond to its
1243   // associated "continues humongous" regions.
1244   void set_bit_for_region(HeapRegion* hr) {
1245     assert(!hr->is_continues_humongous(), "should have filtered those out");
1246 
1247     BitMap::idx_t index = (BitMap::idx_t) hr->hrm_index();
1248     if (!hr->is_starts_humongous()) {
1249       // Normal (non-humongous) case: just set the bit.
1250       _region_bm->par_at_put(index, true);
1251     } else {
1252       // Starts humongous case: calculate how many regions are part of
1253       // this humongous region and then set the bit range.
1254       BitMap::idx_t end_index = (BitMap::idx_t) hr->last_hc_index();
1255       _region_bm->par_at_put_range(index, end_index, true);
1256     }
1257   }
1258 
1259 public:
1260   CMCountDataClosureBase(G1CollectedHeap* g1h,
1261                          BitMap* region_bm, BitMap* card_bm):
1262     _g1h(g1h), _cm(g1h->concurrent_mark()),
1263     _ct_bs(barrier_set_cast<CardTableModRefBS>(g1h->barrier_set())),
1264     _region_bm(region_bm), _card_bm(card_bm) { }
1265 };
1266 
1267 // Closure that calculates the # live objects per region. Used
1268 // for verification purposes during the cleanup pause.
1269 class CalcLiveObjectsClosure: public CMCountDataClosureBase {
1270   CMBitMapRO* _bm;
1271   size_t _region_marked_bytes;
1272 
1273 public:
1274   CalcLiveObjectsClosure(CMBitMapRO *bm, G1CollectedHeap* g1h,
1275                          BitMap* region_bm, BitMap* card_bm) :
1276     CMCountDataClosureBase(g1h, region_bm, card_bm),
1277     _bm(bm), _region_marked_bytes(0) { }
1278 
1279   bool doHeapRegion(HeapRegion* hr) {
1280 
1281     if (hr->is_continues_humongous()) {
1282       // We will ignore these here and process them when their
1283       // associated "starts humongous" region is processed (see
1284       // set_bit_for_heap_region()). Note that we cannot rely on their
1285       // associated "starts humongous" region to have their bit set to
1286       // 1 since, due to the region chunking in the parallel region
1287       // iteration, a "continues humongous" region might be visited
1288       // before its associated "starts humongous".
1289       return false;
1290     }
1291 
1292     HeapWord* ntams = hr->next_top_at_mark_start();
1293     HeapWord* start = hr->bottom();
1294 
1295     assert(start <= hr->end() && start <= ntams && ntams <= hr->end(),
1296            "Preconditions not met - "
1297            "start: " PTR_FORMAT ", ntams: " PTR_FORMAT ", end: " PTR_FORMAT,
1298            p2i(start), p2i(ntams), p2i(hr->end()));
1299 
1300     // Find the first marked object at or after "start".
1301     start = _bm->getNextMarkedWordAddress(start, ntams);
1302 
1303     size_t marked_bytes = 0;
1304 
1305     while (start < ntams) {
1306       oop obj = oop(start);
1307       int obj_sz = obj->size();
1308       HeapWord* obj_end = start + obj_sz;
1309 
1310       BitMap::idx_t start_idx = _cm->card_bitmap_index_for(start);
1311       BitMap::idx_t end_idx = _cm->card_bitmap_index_for(obj_end);
1312 
1313       // Note: if we're looking at the last region in heap - obj_end
1314       // could be actually just beyond the end of the heap; end_idx
1315       // will then correspond to a (non-existent) card that is also
1316       // just beyond the heap.
1317       if (_g1h->is_in_g1_reserved(obj_end) && !_ct_bs->is_card_aligned(obj_end)) {
1318         // end of object is not card aligned - increment to cover
1319         // all the cards spanned by the object
1320         end_idx += 1;
1321       }
1322 
1323       // Set the bits in the card BM for the cards spanned by this object.
1324       _cm->set_card_bitmap_range(_card_bm, start_idx, end_idx, true /* is_par */);
1325 
1326       // Add the size of this object to the number of marked bytes.
1327       marked_bytes += (size_t)obj_sz * HeapWordSize;
1328 
1329       // Find the next marked object after this one.
1330       start = _bm->getNextMarkedWordAddress(obj_end, ntams);
1331     }
1332 
1333     // Mark the allocated-since-marking portion...
1334     HeapWord* top = hr->top();
1335     if (ntams < top) {
1336       BitMap::idx_t start_idx = _cm->card_bitmap_index_for(ntams);
1337       BitMap::idx_t end_idx = _cm->card_bitmap_index_for(top);
1338 
1339       // Note: if we're looking at the last region in heap - top
1340       // could be actually just beyond the end of the heap; end_idx
1341       // will then correspond to a (non-existent) card that is also
1342       // just beyond the heap.
1343       if (_g1h->is_in_g1_reserved(top) && !_ct_bs->is_card_aligned(top)) {
1344         // end of object is not card aligned - increment to cover
1345         // all the cards spanned by the object
1346         end_idx += 1;
1347       }
1348       _cm->set_card_bitmap_range(_card_bm, start_idx, end_idx, true /* is_par */);
1349 
1350       // This definitely means the region has live objects.
1351       set_bit_for_region(hr);
1352     }
1353 
1354     // Update the live region bitmap.
1355     if (marked_bytes > 0) {
1356       set_bit_for_region(hr);
1357     }
1358 
1359     // Set the marked bytes for the current region so that
1360     // it can be queried by a calling verification routine
1361     _region_marked_bytes = marked_bytes;
1362 
1363     return false;
1364   }
1365 
1366   size_t region_marked_bytes() const { return _region_marked_bytes; }
1367 };
1368 
1369 // Heap region closure used for verifying the counting data
1370 // that was accumulated concurrently and aggregated during
1371 // the remark pause. This closure is applied to the heap
1372 // regions during the STW cleanup pause.
1373 
1374 class VerifyLiveObjectDataHRClosure: public HeapRegionClosure {
1375   G1CollectedHeap* _g1h;
1376   ConcurrentMark* _cm;
1377   CalcLiveObjectsClosure _calc_cl;
1378   BitMap* _region_bm;   // Region BM to be verified
1379   BitMap* _card_bm;     // Card BM to be verified
1380 
1381   BitMap* _exp_region_bm; // Expected Region BM values
1382   BitMap* _exp_card_bm;   // Expected card BM values
1383 
1384   int _failures;
1385 
1386 public:
1387   VerifyLiveObjectDataHRClosure(G1CollectedHeap* g1h,
1388                                 BitMap* region_bm,
1389                                 BitMap* card_bm,
1390                                 BitMap* exp_region_bm,
1391                                 BitMap* exp_card_bm) :
1392     _g1h(g1h), _cm(g1h->concurrent_mark()),
1393     _calc_cl(_cm->nextMarkBitMap(), g1h, exp_region_bm, exp_card_bm),
1394     _region_bm(region_bm), _card_bm(card_bm),
1395     _exp_region_bm(exp_region_bm), _exp_card_bm(exp_card_bm),
1396     _failures(0) { }
1397 
1398   int failures() const { return _failures; }
1399 
1400   bool doHeapRegion(HeapRegion* hr) {
1401     if (hr->is_continues_humongous()) {
1402       // We will ignore these here and process them when their
1403       // associated "starts humongous" region is processed (see
1404       // set_bit_for_heap_region()). Note that we cannot rely on their
1405       // associated "starts humongous" region to have their bit set to
1406       // 1 since, due to the region chunking in the parallel region
1407       // iteration, a "continues humongous" region might be visited
1408       // before its associated "starts humongous".
1409       return false;
1410     }
1411 
1412     int failures = 0;
1413 
1414     // Call the CalcLiveObjectsClosure to walk the marking bitmap for
1415     // this region and set the corresponding bits in the expected region
1416     // and card bitmaps.
1417     bool res = _calc_cl.doHeapRegion(hr);
1418     assert(res == false, "should be continuing");
1419 
1420     // Verify the marked bytes for this region.
1421     size_t exp_marked_bytes = _calc_cl.region_marked_bytes();
1422     size_t act_marked_bytes = hr->next_marked_bytes();
1423 
1424     // We're not OK if expected marked bytes > actual marked bytes. It means
1425     // we have missed accounting some objects during the actual marking.
1426     if (exp_marked_bytes > act_marked_bytes) {
1427       failures += 1;
1428     }
1429 
1430     // Verify the bit, for this region, in the actual and expected
1431     // (which was just calculated) region bit maps.
1432     // We're not OK if the bit in the calculated expected region
1433     // bitmap is set and the bit in the actual region bitmap is not.
1434     BitMap::idx_t index = (BitMap::idx_t) hr->hrm_index();
1435 
1436     bool expected = _exp_region_bm->at(index);
1437     bool actual = _region_bm->at(index);
1438     if (expected && !actual) {
1439       failures += 1;
1440     }
1441 
1442     // Verify that the card bit maps for the cards spanned by the current
1443     // region match. We have an error if we have a set bit in the expected
1444     // bit map and the corresponding bit in the actual bitmap is not set.
1445 
1446     BitMap::idx_t start_idx = _cm->card_bitmap_index_for(hr->bottom());
1447     BitMap::idx_t end_idx = _cm->card_bitmap_index_for(hr->top());
1448 
1449     for (BitMap::idx_t i = start_idx; i < end_idx; i+=1) {
1450       expected = _exp_card_bm->at(i);
1451       actual = _card_bm->at(i);
1452 
1453       if (expected && !actual) {
1454         failures += 1;
1455       }
1456     }
1457 
1458     _failures += failures;
1459 
1460     // We could stop iteration over the heap when we
1461     // find the first violating region by returning true.
1462     return false;
1463   }
1464 };
1465 
1466 class G1ParVerifyFinalCountTask: public AbstractGangTask {
1467 protected:
1468   G1CollectedHeap* _g1h;
1469   ConcurrentMark* _cm;
1470   BitMap* _actual_region_bm;
1471   BitMap* _actual_card_bm;
1472 
1473   uint    _n_workers;
1474 
1475   BitMap* _expected_region_bm;
1476   BitMap* _expected_card_bm;
1477 
1478   int  _failures;
1479 
1480   HeapRegionClaimer _hrclaimer;
1481 
1482 public:
1483   G1ParVerifyFinalCountTask(G1CollectedHeap* g1h,
1484                             BitMap* region_bm, BitMap* card_bm,
1485                             BitMap* expected_region_bm, BitMap* expected_card_bm)
1486     : AbstractGangTask("G1 verify final counting"),
1487       _g1h(g1h), _cm(_g1h->concurrent_mark()),
1488       _actual_region_bm(region_bm), _actual_card_bm(card_bm),
1489       _expected_region_bm(expected_region_bm), _expected_card_bm(expected_card_bm),
1490       _failures(0),
1491       _n_workers(_g1h->workers()->active_workers()), _hrclaimer(_n_workers) {
1492     assert(VerifyDuringGC, "don't call this otherwise");
1493     assert(_expected_card_bm->size() == _actual_card_bm->size(), "sanity");
1494     assert(_expected_region_bm->size() == _actual_region_bm->size(), "sanity");
1495   }
1496 
1497   void work(uint worker_id) {
1498     assert(worker_id < _n_workers, "invariant");
1499 
1500     VerifyLiveObjectDataHRClosure verify_cl(_g1h,
1501                                             _actual_region_bm, _actual_card_bm,
1502                                             _expected_region_bm,
1503                                             _expected_card_bm);
1504 
1505     _g1h->heap_region_par_iterate(&verify_cl, worker_id, &_hrclaimer);
1506 
1507     Atomic::add(verify_cl.failures(), &_failures);
1508   }
1509 
1510   int failures() const { return _failures; }
1511 };
1512 
1513 // Closure that finalizes the liveness counting data.
1514 // Used during the cleanup pause.
1515 // Sets the bits corresponding to the interval [NTAMS, top]
1516 // (which contains the implicitly live objects) in the
1517 // card liveness bitmap. Also sets the bit for each region,
1518 // containing live data, in the region liveness bitmap.
1519 
1520 class FinalCountDataUpdateClosure: public CMCountDataClosureBase {
1521  public:
1522   FinalCountDataUpdateClosure(G1CollectedHeap* g1h,
1523                               BitMap* region_bm,
1524                               BitMap* card_bm) :
1525     CMCountDataClosureBase(g1h, region_bm, card_bm) { }
1526 
1527   bool doHeapRegion(HeapRegion* hr) {
1528 
1529     if (hr->is_continues_humongous()) {
1530       // We will ignore these here and process them when their
1531       // associated "starts humongous" region is processed (see
1532       // set_bit_for_heap_region()). Note that we cannot rely on their
1533       // associated "starts humongous" region to have their bit set to
1534       // 1 since, due to the region chunking in the parallel region
1535       // iteration, a "continues humongous" region might be visited
1536       // before its associated "starts humongous".
1537       return false;
1538     }
1539 
1540     HeapWord* ntams = hr->next_top_at_mark_start();
1541     HeapWord* top   = hr->top();
1542 
1543     assert(hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions.");
1544 
1545     // Mark the allocated-since-marking portion...
1546     if (ntams < top) {
1547       // This definitely means the region has live objects.
1548       set_bit_for_region(hr);
1549 
1550       // Now set the bits in the card bitmap for [ntams, top)
1551       BitMap::idx_t start_idx = _cm->card_bitmap_index_for(ntams);
1552       BitMap::idx_t end_idx = _cm->card_bitmap_index_for(top);
1553 
1554       // Note: if we're looking at the last region in heap - top
1555       // could be actually just beyond the end of the heap; end_idx
1556       // will then correspond to a (non-existent) card that is also
1557       // just beyond the heap.
1558       if (_g1h->is_in_g1_reserved(top) && !_ct_bs->is_card_aligned(top)) {
1559         // end of object is not card aligned - increment to cover
1560         // all the cards spanned by the object
1561         end_idx += 1;
1562       }
1563 
1564       assert(end_idx <= _card_bm->size(),
1565              "oob: end_idx=  " SIZE_FORMAT ", bitmap size= " SIZE_FORMAT,
1566              end_idx, _card_bm->size());
1567       assert(start_idx < _card_bm->size(),
1568              "oob: start_idx=  " SIZE_FORMAT ", bitmap size= " SIZE_FORMAT,
1569              start_idx, _card_bm->size());
1570 
1571       _cm->set_card_bitmap_range(_card_bm, start_idx, end_idx, true /* is_par */);
1572     }
1573 
1574     // Set the bit for the region if it contains live data
1575     if (hr->next_marked_bytes() > 0) {
1576       set_bit_for_region(hr);
1577     }
1578 
1579     return false;
1580   }
1581 };
1582 
1583 class G1ParFinalCountTask: public AbstractGangTask {
1584 protected:
1585   G1CollectedHeap* _g1h;
1586   ConcurrentMark* _cm;
1587   BitMap* _actual_region_bm;
1588   BitMap* _actual_card_bm;
1589 
1590   uint    _n_workers;
1591   HeapRegionClaimer _hrclaimer;
1592 
1593 public:
1594   G1ParFinalCountTask(G1CollectedHeap* g1h, BitMap* region_bm, BitMap* card_bm)
1595     : AbstractGangTask("G1 final counting"),
1596       _g1h(g1h), _cm(_g1h->concurrent_mark()),
1597       _actual_region_bm(region_bm), _actual_card_bm(card_bm),
1598       _n_workers(_g1h->workers()->active_workers()), _hrclaimer(_n_workers) {
1599   }
1600 
1601   void work(uint worker_id) {
1602     assert(worker_id < _n_workers, "invariant");
1603 
1604     FinalCountDataUpdateClosure final_update_cl(_g1h,
1605                                                 _actual_region_bm,
1606                                                 _actual_card_bm);
1607 
1608     _g1h->heap_region_par_iterate(&final_update_cl, worker_id, &_hrclaimer);
1609   }
1610 };
1611 
1612 class G1NoteEndOfConcMarkClosure : public HeapRegionClosure {
1613   G1CollectedHeap* _g1;
1614   size_t _freed_bytes;
1615   FreeRegionList* _local_cleanup_list;
1616   HeapRegionSetCount _old_regions_removed;
1617   HeapRegionSetCount _humongous_regions_removed;
1618   HRRSCleanupTask* _hrrs_cleanup_task;
1619 
1620 public:
1621   G1NoteEndOfConcMarkClosure(G1CollectedHeap* g1,
1622                              FreeRegionList* local_cleanup_list,
1623                              HRRSCleanupTask* hrrs_cleanup_task) :
1624     _g1(g1),
1625     _freed_bytes(0),
1626     _local_cleanup_list(local_cleanup_list),
1627     _old_regions_removed(),
1628     _humongous_regions_removed(),
1629     _hrrs_cleanup_task(hrrs_cleanup_task) { }
1630 
1631   size_t freed_bytes() { return _freed_bytes; }
1632   const HeapRegionSetCount& old_regions_removed() { return _old_regions_removed; }
1633   const HeapRegionSetCount& humongous_regions_removed() { return _humongous_regions_removed; }
1634 
1635   bool doHeapRegion(HeapRegion *hr) {
1636     if (hr->is_continues_humongous() || hr->is_archive()) {
1637       return false;
1638     }
1639     // We use a claim value of zero here because all regions
1640     // were claimed with value 1 in the FinalCount task.
1641     _g1->reset_gc_time_stamps(hr);
1642     hr->note_end_of_marking();
1643 
1644     if (hr->used() > 0 && hr->max_live_bytes() == 0 && !hr->is_young()) {
1645       _freed_bytes += hr->used();
1646       hr->set_containing_set(NULL);
1647       if (hr->is_humongous()) {
1648         assert(hr->is_starts_humongous(), "we should only see starts humongous");
1649         _humongous_regions_removed.increment(1u, hr->capacity());
1650         _g1->free_humongous_region(hr, _local_cleanup_list, true);
1651       } else {
1652         _old_regions_removed.increment(1u, hr->capacity());
1653         _g1->free_region(hr, _local_cleanup_list, true);
1654       }
1655     } else {
1656       hr->rem_set()->do_cleanup_work(_hrrs_cleanup_task);
1657     }
1658 
1659     return false;
1660   }
1661 };
1662 
1663 class G1ParNoteEndTask: public AbstractGangTask {
1664   friend class G1NoteEndOfConcMarkClosure;
1665 
1666 protected:
1667   G1CollectedHeap* _g1h;
1668   FreeRegionList* _cleanup_list;
1669   HeapRegionClaimer _hrclaimer;
1670 
1671 public:
1672   G1ParNoteEndTask(G1CollectedHeap* g1h, FreeRegionList* cleanup_list, uint n_workers) :
1673       AbstractGangTask("G1 note end"), _g1h(g1h), _cleanup_list(cleanup_list), _hrclaimer(n_workers) {
1674   }
1675 
1676   void work(uint worker_id) {
1677     FreeRegionList local_cleanup_list("Local Cleanup List");
1678     HRRSCleanupTask hrrs_cleanup_task;
1679     G1NoteEndOfConcMarkClosure g1_note_end(_g1h, &local_cleanup_list,
1680                                            &hrrs_cleanup_task);
1681     _g1h->heap_region_par_iterate(&g1_note_end, worker_id, &_hrclaimer);
1682     assert(g1_note_end.complete(), "Shouldn't have yielded!");
1683 
1684     // Now update the lists
1685     _g1h->remove_from_old_sets(g1_note_end.old_regions_removed(), g1_note_end.humongous_regions_removed());
1686     {
1687       MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);
1688       _g1h->decrement_summary_bytes(g1_note_end.freed_bytes());
1689 
1690       // If we iterate over the global cleanup list at the end of
1691       // cleanup to do this printing we will not guarantee to only
1692       // generate output for the newly-reclaimed regions (the list
1693       // might not be empty at the beginning of cleanup; we might
1694       // still be working on its previous contents). So we do the
1695       // printing here, before we append the new regions to the global
1696       // cleanup list.
1697 
1698       G1HRPrinter* hr_printer = _g1h->hr_printer();
1699       if (hr_printer->is_active()) {
1700         FreeRegionListIterator iter(&local_cleanup_list);
1701         while (iter.more_available()) {
1702           HeapRegion* hr = iter.get_next();
1703           hr_printer->cleanup(hr);
1704         }
1705       }
1706 
1707       _cleanup_list->add_ordered(&local_cleanup_list);
1708       assert(local_cleanup_list.is_empty(), "post-condition");
1709 
1710       HeapRegionRemSet::finish_cleanup_task(&hrrs_cleanup_task);
1711     }
1712   }
1713 };
1714 
1715 class G1ParScrubRemSetTask: public AbstractGangTask {
1716 protected:
1717   G1RemSet* _g1rs;
1718   BitMap* _region_bm;
1719   BitMap* _card_bm;
1720   HeapRegionClaimer _hrclaimer;
1721 
1722 public:
1723   G1ParScrubRemSetTask(G1CollectedHeap* g1h, BitMap* region_bm, BitMap* card_bm, uint n_workers) :
1724       AbstractGangTask("G1 ScrubRS"), _g1rs(g1h->g1_rem_set()), _region_bm(region_bm), _card_bm(card_bm), _hrclaimer(n_workers) {
1725   }
1726 
1727   void work(uint worker_id) {
1728     _g1rs->scrub(_region_bm, _card_bm, worker_id, &_hrclaimer);
1729   }
1730 
1731 };
1732 
1733 void ConcurrentMark::cleanup() {
1734   // world is stopped at this checkpoint
1735   assert(SafepointSynchronize::is_at_safepoint(),
1736          "world should be stopped");
1737   G1CollectedHeap* g1h = G1CollectedHeap::heap();
1738 
1739   // If a full collection has happened, we shouldn't do this.
1740   if (has_aborted()) {
1741     g1h->collector_state()->set_mark_in_progress(false); // So bitmap clearing isn't confused
1742     return;
1743   }
1744 
1745   g1h->verify_region_sets_optional();
1746 
1747   if (VerifyDuringGC) {
1748     HandleMark hm;  // handle scope
1749     g1h->prepare_for_verify();
1750     Universe::verify(VerifyOption_G1UsePrevMarking, "During GC (before)");
1751   }
1752   g1h->check_bitmaps("Cleanup Start");
1753 
1754   G1CollectorPolicy* g1p = g1h->g1_policy();
1755   g1p->record_concurrent_mark_cleanup_start();
1756 
1757   double start = os::elapsedTime();
1758 
1759   HeapRegionRemSet::reset_for_cleanup_tasks();
1760 
1761   // Do counting once more with the world stopped for good measure.
1762   G1ParFinalCountTask g1_par_count_task(g1h, &_region_bm, &_card_bm);
1763 
1764   g1h->workers()->run_task(&g1_par_count_task);
1765 
1766   if (VerifyDuringGC) {
1767     // Verify that the counting data accumulated during marking matches
1768     // that calculated by walking the marking bitmap.
1769 
1770     // Bitmaps to hold expected values
1771     BitMap expected_region_bm(_region_bm.size(), true);
1772     BitMap expected_card_bm(_card_bm.size(), true);
1773 
1774     G1ParVerifyFinalCountTask g1_par_verify_task(g1h,
1775                                                  &_region_bm,
1776                                                  &_card_bm,
1777                                                  &expected_region_bm,
1778                                                  &expected_card_bm);
1779 
1780     g1h->workers()->run_task(&g1_par_verify_task);
1781 
1782     guarantee(g1_par_verify_task.failures() == 0, "Unexpected accounting failures");
1783   }
1784 
1785   size_t start_used_bytes = g1h->used();
1786   g1h->collector_state()->set_mark_in_progress(false);
1787 
1788   double count_end = os::elapsedTime();
1789   double this_final_counting_time = (count_end - start);
1790   _total_counting_time += this_final_counting_time;
1791 
1792   if (Log<LOG_TAGS(gc, liveness)>::is_trace()) {
1793     G1PrintRegionLivenessInfoClosure cl("Post-Marking");
1794     _g1h->heap_region_iterate(&cl);
1795   }
1796 
1797   // Install newly created mark bitMap as "prev".
1798   swapMarkBitMaps();
1799 
1800   g1h->reset_gc_time_stamp();
1801 
1802   uint n_workers = _g1h->workers()->active_workers();
1803 
1804   // Note end of marking in all heap regions.
1805   G1ParNoteEndTask g1_par_note_end_task(g1h, &_cleanup_list, n_workers);
1806   g1h->workers()->run_task(&g1_par_note_end_task);
1807   g1h->check_gc_time_stamps();
1808 
1809   if (!cleanup_list_is_empty()) {
1810     // The cleanup list is not empty, so we'll have to process it
1811     // concurrently. Notify anyone else that might be wanting free
1812     // regions that there will be more free regions coming soon.
1813     g1h->set_free_regions_coming();
1814   }
1815 
1816   // call below, since it affects the metric by which we sort the heap
1817   // regions.
1818   if (G1ScrubRemSets) {
1819     double rs_scrub_start = os::elapsedTime();
1820     G1ParScrubRemSetTask g1_par_scrub_rs_task(g1h, &_region_bm, &_card_bm, n_workers);
1821     g1h->workers()->run_task(&g1_par_scrub_rs_task);
1822 
1823     double rs_scrub_end = os::elapsedTime();
1824     double this_rs_scrub_time = (rs_scrub_end - rs_scrub_start);
1825     _total_rs_scrub_time += this_rs_scrub_time;
1826   }
1827 
1828   // this will also free any regions totally full of garbage objects,
1829   // and sort the regions.
1830   g1h->g1_policy()->record_concurrent_mark_cleanup_end();
1831 
1832   // Statistics.
1833   double end = os::elapsedTime();
1834   _cleanup_times.add((end - start) * 1000.0);
1835 
1836   // Clean up will have freed any regions completely full of garbage.
1837   // Update the soft reference policy with the new heap occupancy.
1838   Universe::update_heap_info_at_gc();
1839 
1840   if (VerifyDuringGC) {
1841     HandleMark hm;  // handle scope
1842     g1h->prepare_for_verify();
1843     Universe::verify(VerifyOption_G1UsePrevMarking, "During GC (after)");
1844   }
1845 
1846   g1h->check_bitmaps("Cleanup End");
1847 
1848   g1h->verify_region_sets_optional();
1849 
1850   // We need to make this be a "collection" so any collection pause that
1851   // races with it goes around and waits for completeCleanup to finish.
1852   g1h->increment_total_collections();
1853 
1854   // Clean out dead classes and update Metaspace sizes.
1855   if (ClassUnloadingWithConcurrentMark) {
1856     ClassLoaderDataGraph::purge();
1857   }
1858   MetaspaceGC::compute_new_size();
1859 
1860   // We reclaimed old regions so we should calculate the sizes to make
1861   // sure we update the old gen/space data.
1862   g1h->g1mm()->update_sizes();
1863   g1h->allocation_context_stats().update_after_mark();
1864 
1865   g1h->trace_heap_after_concurrent_cycle();
1866 }
1867 
1868 void ConcurrentMark::completeCleanup() {
1869   if (has_aborted()) return;
1870 
1871   G1CollectedHeap* g1h = G1CollectedHeap::heap();
1872 
1873   _cleanup_list.verify_optional();
1874   FreeRegionList tmp_free_list("Tmp Free List");
1875 
1876   log_develop(gc, freelist)("G1ConcRegionFreeing [complete cleanup] : "
1877                             "cleanup list has %u entries",
1878                             _cleanup_list.length());
1879 
1880   // No one else should be accessing the _cleanup_list at this point,
1881   // so it is not necessary to take any locks
1882   while (!_cleanup_list.is_empty()) {
1883     HeapRegion* hr = _cleanup_list.remove_region(true /* from_head */);
1884     assert(hr != NULL, "Got NULL from a non-empty list");
1885     hr->par_clear();
1886     tmp_free_list.add_ordered(hr);
1887 
1888     // Instead of adding one region at a time to the secondary_free_list,
1889     // we accumulate them in the local list and move them a few at a
1890     // time. This also cuts down on the number of notify_all() calls
1891     // we do during this process. We'll also append the local list when
1892     // _cleanup_list is empty (which means we just removed the last
1893     // region from the _cleanup_list).
1894     if ((tmp_free_list.length() % G1SecondaryFreeListAppendLength == 0) ||
1895         _cleanup_list.is_empty()) {
1896       log_develop(gc, freelist)("G1ConcRegionFreeing [complete cleanup] : "
1897                                 "appending %u entries to the secondary_free_list, "
1898                                 "cleanup list still has %u entries",
1899                                 tmp_free_list.length(),
1900                                 _cleanup_list.length());
1901 
1902       {
1903         MutexLockerEx x(SecondaryFreeList_lock, Mutex::_no_safepoint_check_flag);
1904         g1h->secondary_free_list_add(&tmp_free_list);
1905         SecondaryFreeList_lock->notify_all();
1906       }
1907 #ifndef PRODUCT
1908       if (G1StressConcRegionFreeing) {
1909         for (uintx i = 0; i < G1StressConcRegionFreeingDelayMillis; ++i) {
1910           os::sleep(Thread::current(), (jlong) 1, false);
1911         }
1912       }
1913 #endif
1914     }
1915   }
1916   assert(tmp_free_list.is_empty(), "post-condition");
1917 }
1918 
1919 // Supporting Object and Oop closures for reference discovery
1920 // and processing in during marking
1921 
1922 bool G1CMIsAliveClosure::do_object_b(oop obj) {
1923   HeapWord* addr = (HeapWord*)obj;
1924   return addr != NULL &&
1925          (!_g1->is_in_g1_reserved(addr) || !_g1->is_obj_ill(obj));
1926 }
1927 
1928 // 'Keep Alive' oop closure used by both serial parallel reference processing.
1929 // Uses the CMTask associated with a worker thread (for serial reference
1930 // processing the CMTask for worker 0 is used) to preserve (mark) and
1931 // trace referent objects.
1932 //
1933 // Using the CMTask and embedded local queues avoids having the worker
1934 // threads operating on the global mark stack. This reduces the risk
1935 // of overflowing the stack - which we would rather avoid at this late
1936 // state. Also using the tasks' local queues removes the potential
1937 // of the workers interfering with each other that could occur if
1938 // operating on the global stack.
1939 
1940 class G1CMKeepAliveAndDrainClosure: public OopClosure {
1941   ConcurrentMark* _cm;
1942   CMTask*         _task;
1943   int             _ref_counter_limit;
1944   int             _ref_counter;
1945   bool            _is_serial;
1946  public:
1947   G1CMKeepAliveAndDrainClosure(ConcurrentMark* cm, CMTask* task, bool is_serial) :
1948     _cm(cm), _task(task), _is_serial(is_serial),
1949     _ref_counter_limit(G1RefProcDrainInterval) {
1950     assert(_ref_counter_limit > 0, "sanity");
1951     assert(!_is_serial || _task->worker_id() == 0, "only task 0 for serial code");
1952     _ref_counter = _ref_counter_limit;
1953   }
1954 
1955   virtual void do_oop(narrowOop* p) { do_oop_work(p); }
1956   virtual void do_oop(      oop* p) { do_oop_work(p); }
1957 
1958   template <class T> void do_oop_work(T* p) {
1959     if (!_cm->has_overflown()) {
1960       oop obj = oopDesc::load_decode_heap_oop(p);
1961       _task->deal_with_reference(obj);
1962       _ref_counter--;
1963 
1964       if (_ref_counter == 0) {
1965         // We have dealt with _ref_counter_limit references, pushing them
1966         // and objects reachable from them on to the local stack (and
1967         // possibly the global stack). Call CMTask::do_marking_step() to
1968         // process these entries.
1969         //
1970         // We call CMTask::do_marking_step() in a loop, which we'll exit if
1971         // there's nothing more to do (i.e. we're done with the entries that
1972         // were pushed as a result of the CMTask::deal_with_reference() calls
1973         // above) or we overflow.
1974         //
1975         // Note: CMTask::do_marking_step() can set the CMTask::has_aborted()
1976         // flag while there may still be some work to do. (See the comment at
1977         // the beginning of CMTask::do_marking_step() for those conditions -
1978         // one of which is reaching the specified time target.) It is only
1979         // when CMTask::do_marking_step() returns without setting the
1980         // has_aborted() flag that the marking step has completed.
1981         do {
1982           double mark_step_duration_ms = G1ConcMarkStepDurationMillis;
1983           _task->do_marking_step(mark_step_duration_ms,
1984                                  false      /* do_termination */,
1985                                  _is_serial);
1986         } while (_task->has_aborted() && !_cm->has_overflown());
1987         _ref_counter = _ref_counter_limit;
1988       }
1989     }
1990   }
1991 };
1992 
1993 // 'Drain' oop closure used by both serial and parallel reference processing.
1994 // Uses the CMTask associated with a given worker thread (for serial
1995 // reference processing the CMtask for worker 0 is used). Calls the
1996 // do_marking_step routine, with an unbelievably large timeout value,
1997 // to drain the marking data structures of the remaining entries
1998 // added by the 'keep alive' oop closure above.
1999 
2000 class G1CMDrainMarkingStackClosure: public VoidClosure {
2001   ConcurrentMark* _cm;
2002   CMTask*         _task;
2003   bool            _is_serial;
2004  public:
2005   G1CMDrainMarkingStackClosure(ConcurrentMark* cm, CMTask* task, bool is_serial) :
2006     _cm(cm), _task(task), _is_serial(is_serial) {
2007     assert(!_is_serial || _task->worker_id() == 0, "only task 0 for serial code");
2008   }
2009 
2010   void do_void() {
2011     do {
2012       // We call CMTask::do_marking_step() to completely drain the local
2013       // and global marking stacks of entries pushed by the 'keep alive'
2014       // oop closure (an instance of G1CMKeepAliveAndDrainClosure above).
2015       //
2016       // CMTask::do_marking_step() is called in a loop, which we'll exit
2017       // if there's nothing more to do (i.e. we've completely drained the
2018       // entries that were pushed as a a result of applying the 'keep alive'
2019       // closure to the entries on the discovered ref lists) or we overflow
2020       // the global marking stack.
2021       //
2022       // Note: CMTask::do_marking_step() can set the CMTask::has_aborted()
2023       // flag while there may still be some work to do. (See the comment at
2024       // the beginning of CMTask::do_marking_step() for those conditions -
2025       // one of which is reaching the specified time target.) It is only
2026       // when CMTask::do_marking_step() returns without setting the
2027       // has_aborted() flag that the marking step has completed.
2028 
2029       _task->do_marking_step(1000000000.0 /* something very large */,
2030                              true         /* do_termination */,
2031                              _is_serial);
2032     } while (_task->has_aborted() && !_cm->has_overflown());
2033   }
2034 };
2035 
2036 // Implementation of AbstractRefProcTaskExecutor for parallel
2037 // reference processing at the end of G1 concurrent marking
2038 
2039 class G1CMRefProcTaskExecutor: public AbstractRefProcTaskExecutor {
2040 private:
2041   G1CollectedHeap* _g1h;
2042   ConcurrentMark*  _cm;
2043   WorkGang*        _workers;
2044   uint             _active_workers;
2045 
2046 public:
2047   G1CMRefProcTaskExecutor(G1CollectedHeap* g1h,
2048                           ConcurrentMark* cm,
2049                           WorkGang* workers,
2050                           uint n_workers) :
2051     _g1h(g1h), _cm(cm),
2052     _workers(workers), _active_workers(n_workers) { }
2053 
2054   // Executes the given task using concurrent marking worker threads.
2055   virtual void execute(ProcessTask& task);
2056   virtual void execute(EnqueueTask& task);
2057 };
2058 
2059 class G1CMRefProcTaskProxy: public AbstractGangTask {
2060   typedef AbstractRefProcTaskExecutor::ProcessTask ProcessTask;
2061   ProcessTask&     _proc_task;
2062   G1CollectedHeap* _g1h;
2063   ConcurrentMark*  _cm;
2064 
2065 public:
2066   G1CMRefProcTaskProxy(ProcessTask& proc_task,
2067                      G1CollectedHeap* g1h,
2068                      ConcurrentMark* cm) :
2069     AbstractGangTask("Process reference objects in parallel"),
2070     _proc_task(proc_task), _g1h(g1h), _cm(cm) {
2071     ReferenceProcessor* rp = _g1h->ref_processor_cm();
2072     assert(rp->processing_is_mt(), "shouldn't be here otherwise");
2073   }
2074 
2075   virtual void work(uint worker_id) {
2076     ResourceMark rm;
2077     HandleMark hm;
2078     CMTask* task = _cm->task(worker_id);
2079     G1CMIsAliveClosure g1_is_alive(_g1h);
2080     G1CMKeepAliveAndDrainClosure g1_par_keep_alive(_cm, task, false /* is_serial */);
2081     G1CMDrainMarkingStackClosure g1_par_drain(_cm, task, false /* is_serial */);
2082 
2083     _proc_task.work(worker_id, g1_is_alive, g1_par_keep_alive, g1_par_drain);
2084   }
2085 };
2086 
2087 void G1CMRefProcTaskExecutor::execute(ProcessTask& proc_task) {
2088   assert(_workers != NULL, "Need parallel worker threads.");
2089   assert(_g1h->ref_processor_cm()->processing_is_mt(), "processing is not MT");
2090 
2091   G1CMRefProcTaskProxy proc_task_proxy(proc_task, _g1h, _cm);
2092 
2093   // We need to reset the concurrency level before each
2094   // proxy task execution, so that the termination protocol
2095   // and overflow handling in CMTask::do_marking_step() knows
2096   // how many workers to wait for.
2097   _cm->set_concurrency(_active_workers);
2098   _workers->run_task(&proc_task_proxy);
2099 }
2100 
2101 class G1CMRefEnqueueTaskProxy: public AbstractGangTask {
2102   typedef AbstractRefProcTaskExecutor::EnqueueTask EnqueueTask;
2103   EnqueueTask& _enq_task;
2104 
2105 public:
2106   G1CMRefEnqueueTaskProxy(EnqueueTask& enq_task) :
2107     AbstractGangTask("Enqueue reference objects in parallel"),
2108     _enq_task(enq_task) { }
2109 
2110   virtual void work(uint worker_id) {
2111     _enq_task.work(worker_id);
2112   }
2113 };
2114 
2115 void G1CMRefProcTaskExecutor::execute(EnqueueTask& enq_task) {
2116   assert(_workers != NULL, "Need parallel worker threads.");
2117   assert(_g1h->ref_processor_cm()->processing_is_mt(), "processing is not MT");
2118 
2119   G1CMRefEnqueueTaskProxy enq_task_proxy(enq_task);
2120 
2121   // Not strictly necessary but...
2122   //
2123   // We need to reset the concurrency level before each
2124   // proxy task execution, so that the termination protocol
2125   // and overflow handling in CMTask::do_marking_step() knows
2126   // how many workers to wait for.
2127   _cm->set_concurrency(_active_workers);
2128   _workers->run_task(&enq_task_proxy);
2129 }
2130 
2131 void ConcurrentMark::weakRefsWorkParallelPart(BoolObjectClosure* is_alive, bool purged_classes) {
2132   G1CollectedHeap::heap()->parallel_cleaning(is_alive, true, true, purged_classes);
2133 }
2134 
2135 void ConcurrentMark::weakRefsWork(bool clear_all_soft_refs) {
2136   if (has_overflown()) {
2137     // Skip processing the discovered references if we have
2138     // overflown the global marking stack. Reference objects
2139     // only get discovered once so it is OK to not
2140     // de-populate the discovered reference lists. We could have,
2141     // but the only benefit would be that, when marking restarts,
2142     // less reference objects are discovered.
2143     return;
2144   }
2145 
2146   ResourceMark rm;
2147   HandleMark   hm;
2148 
2149   G1CollectedHeap* g1h = G1CollectedHeap::heap();
2150 
2151   // Is alive closure.
2152   G1CMIsAliveClosure g1_is_alive(g1h);
2153 
2154   // Inner scope to exclude the cleaning of the string and symbol
2155   // tables from the displayed time.
2156   {
2157     GCTraceTime(Debug, gc) trace("GC ref-proc", g1h->gc_timer_cm());
2158 
2159     ReferenceProcessor* rp = g1h->ref_processor_cm();
2160 
2161     // See the comment in G1CollectedHeap::ref_processing_init()
2162     // about how reference processing currently works in G1.
2163 
2164     // Set the soft reference policy
2165     rp->setup_policy(clear_all_soft_refs);
2166     assert(_markStack.isEmpty(), "mark stack should be empty");
2167 
2168     // Instances of the 'Keep Alive' and 'Complete GC' closures used
2169     // in serial reference processing. Note these closures are also
2170     // used for serially processing (by the the current thread) the
2171     // JNI references during parallel reference processing.
2172     //
2173     // These closures do not need to synchronize with the worker
2174     // threads involved in parallel reference processing as these
2175     // instances are executed serially by the current thread (e.g.
2176     // reference processing is not multi-threaded and is thus
2177     // performed by the current thread instead of a gang worker).
2178     //
2179     // The gang tasks involved in parallel reference processing create
2180     // their own instances of these closures, which do their own
2181     // synchronization among themselves.
2182     G1CMKeepAliveAndDrainClosure g1_keep_alive(this, task(0), true /* is_serial */);
2183     G1CMDrainMarkingStackClosure g1_drain_mark_stack(this, task(0), true /* is_serial */);
2184 
2185     // We need at least one active thread. If reference processing
2186     // is not multi-threaded we use the current (VMThread) thread,
2187     // otherwise we use the work gang from the G1CollectedHeap and
2188     // we utilize all the worker threads we can.
2189     bool processing_is_mt = rp->processing_is_mt();
2190     uint active_workers = (processing_is_mt ? g1h->workers()->active_workers() : 1U);
2191     active_workers = MAX2(MIN2(active_workers, _max_worker_id), 1U);
2192 
2193     // Parallel processing task executor.
2194     G1CMRefProcTaskExecutor par_task_executor(g1h, this,
2195                                               g1h->workers(), active_workers);
2196     AbstractRefProcTaskExecutor* executor = (processing_is_mt ? &par_task_executor : NULL);
2197 
2198     // Set the concurrency level. The phase was already set prior to
2199     // executing the remark task.
2200     set_concurrency(active_workers);
2201 
2202     // Set the degree of MT processing here.  If the discovery was done MT,
2203     // the number of threads involved during discovery could differ from
2204     // the number of active workers.  This is OK as long as the discovered
2205     // Reference lists are balanced (see balance_all_queues() and balance_queues()).
2206     rp->set_active_mt_degree(active_workers);
2207 
2208     // Process the weak references.
2209     const ReferenceProcessorStats& stats =
2210         rp->process_discovered_references(&g1_is_alive,
2211                                           &g1_keep_alive,
2212                                           &g1_drain_mark_stack,
2213                                           executor,
2214                                           g1h->gc_timer_cm());
2215     g1h->gc_tracer_cm()->report_gc_reference_stats(stats);
2216 
2217     // The do_oop work routines of the keep_alive and drain_marking_stack
2218     // oop closures will set the has_overflown flag if we overflow the
2219     // global marking stack.
2220 
2221     assert(_markStack.overflow() || _markStack.isEmpty(),
2222             "mark stack should be empty (unless it overflowed)");
2223 
2224     if (_markStack.overflow()) {
2225       // This should have been done already when we tried to push an
2226       // entry on to the global mark stack. But let's do it again.
2227       set_has_overflown();
2228     }
2229 
2230     assert(rp->num_q() == active_workers, "why not");
2231 
2232     rp->enqueue_discovered_references(executor);
2233 
2234     rp->verify_no_references_recorded();
2235     assert(!rp->discovery_enabled(), "Post condition");
2236   }
2237 
2238   if (has_overflown()) {
2239     // We can not trust g1_is_alive if the marking stack overflowed
2240     return;
2241   }
2242 
2243   assert(_markStack.isEmpty(), "Marking should have completed");
2244 
2245   // Unload Klasses, String, Symbols, Code Cache, etc.
2246   {
2247     GCTraceTime(Debug, gc) trace("Unloading", g1h->gc_timer_cm());
2248 
2249     if (ClassUnloadingWithConcurrentMark) {
2250       bool purged_classes;
2251 
2252       {
2253         GCTraceTime(Trace, gc) trace("System Dictionary Unloading", g1h->gc_timer_cm());
2254         purged_classes = SystemDictionary::do_unloading(&g1_is_alive, false /* Defer klass cleaning */);
2255       }
2256 
2257       {
2258         GCTraceTime(Trace, gc) trace("Parallel Unloading", g1h->gc_timer_cm());
2259         weakRefsWorkParallelPart(&g1_is_alive, purged_classes);
2260       }
2261     }
2262 
2263     if (G1StringDedup::is_enabled()) {
2264       GCTraceTime(Trace, gc) trace("String Deduplication Unlink", g1h->gc_timer_cm());
2265       G1StringDedup::unlink(&g1_is_alive);
2266     }
2267   }
2268 }
2269 
2270 void ConcurrentMark::swapMarkBitMaps() {
2271   CMBitMapRO* temp = _prevMarkBitMap;
2272   _prevMarkBitMap  = (CMBitMapRO*)_nextMarkBitMap;
2273   _nextMarkBitMap  = (CMBitMap*)  temp;
2274 }
2275 
2276 // Closure for marking entries in SATB buffers.
2277 class CMSATBBufferClosure : public SATBBufferClosure {
2278 private:
2279   CMTask* _task;
2280   G1CollectedHeap* _g1h;
2281 
2282   // This is very similar to CMTask::deal_with_reference, but with
2283   // more relaxed requirements for the argument, so this must be more
2284   // circumspect about treating the argument as an object.
2285   void do_entry(void* entry) const {
2286     _task->increment_refs_reached();
2287     HeapRegion* hr = _g1h->heap_region_containing_raw(entry);
2288     if (entry < hr->next_top_at_mark_start()) {
2289       // Until we get here, we don't know whether entry refers to a valid
2290       // object; it could instead have been a stale reference.
2291       oop obj = static_cast<oop>(entry);
2292       assert(obj->is_oop(true /* ignore mark word */),
2293              "Invalid oop in SATB buffer: " PTR_FORMAT, p2i(obj));
2294       _task->make_reference_grey(obj, hr);
2295     }
2296   }
2297 
2298 public:
2299   CMSATBBufferClosure(CMTask* task, G1CollectedHeap* g1h)
2300     : _task(task), _g1h(g1h) { }
2301 
2302   virtual void do_buffer(void** buffer, size_t size) {
2303     for (size_t i = 0; i < size; ++i) {
2304       do_entry(buffer[i]);
2305     }
2306   }
2307 };
2308 
2309 class G1RemarkThreadsClosure : public ThreadClosure {
2310   CMSATBBufferClosure _cm_satb_cl;
2311   G1CMOopClosure _cm_cl;
2312   MarkingCodeBlobClosure _code_cl;
2313   int _thread_parity;
2314 
2315  public:
2316   G1RemarkThreadsClosure(G1CollectedHeap* g1h, CMTask* task) :
2317     _cm_satb_cl(task, g1h),
2318     _cm_cl(g1h, g1h->concurrent_mark(), task),
2319     _code_cl(&_cm_cl, !CodeBlobToOopClosure::FixRelocations),
2320     _thread_parity(Threads::thread_claim_parity()) {}
2321 
2322   void do_thread(Thread* thread) {
2323     if (thread->is_Java_thread()) {
2324       if (thread->claim_oops_do(true, _thread_parity)) {
2325         JavaThread* jt = (JavaThread*)thread;
2326 
2327         // In theory it should not be neccessary to explicitly walk the nmethods to find roots for concurrent marking
2328         // however the liveness of oops reachable from nmethods have very complex lifecycles:
2329         // * Alive if on the stack of an executing method
2330         // * Weakly reachable otherwise
2331         // Some objects reachable from nmethods, such as the class loader (or klass_holder) of the receiver should be
2332         // live by the SATB invariant but other oops recorded in nmethods may behave differently.
2333         jt->nmethods_do(&_code_cl);
2334 
2335         jt->satb_mark_queue().apply_closure_and_empty(&_cm_satb_cl);
2336       }
2337     } else if (thread->is_VM_thread()) {
2338       if (thread->claim_oops_do(true, _thread_parity)) {
2339         JavaThread::satb_mark_queue_set().shared_satb_queue()->apply_closure_and_empty(&_cm_satb_cl);
2340       }
2341     }
2342   }
2343 };
2344 
2345 class CMRemarkTask: public AbstractGangTask {
2346 private:
2347   ConcurrentMark* _cm;
2348 public:
2349   void work(uint worker_id) {
2350     // Since all available tasks are actually started, we should
2351     // only proceed if we're supposed to be active.
2352     if (worker_id < _cm->active_tasks()) {
2353       CMTask* task = _cm->task(worker_id);
2354       task->record_start_time();
2355       {
2356         ResourceMark rm;
2357         HandleMark hm;
2358 
2359         G1RemarkThreadsClosure threads_f(G1CollectedHeap::heap(), task);
2360         Threads::threads_do(&threads_f);
2361       }
2362 
2363       do {
2364         task->do_marking_step(1000000000.0 /* something very large */,
2365                               true         /* do_termination       */,
2366                               false        /* is_serial            */);
2367       } while (task->has_aborted() && !_cm->has_overflown());
2368       // If we overflow, then we do not want to restart. We instead
2369       // want to abort remark and do concurrent marking again.
2370       task->record_end_time();
2371     }
2372   }
2373 
2374   CMRemarkTask(ConcurrentMark* cm, uint active_workers) :
2375     AbstractGangTask("Par Remark"), _cm(cm) {
2376     _cm->terminator()->reset_for_reuse(active_workers);
2377   }
2378 };
2379 
2380 void ConcurrentMark::checkpointRootsFinalWork() {
2381   ResourceMark rm;
2382   HandleMark   hm;
2383   G1CollectedHeap* g1h = G1CollectedHeap::heap();
2384 
2385   GCTraceTime(Debug, gc) trace("Finalize Marking", g1h->gc_timer_cm());
2386 
2387   g1h->ensure_parsability(false);
2388 
2389   // this is remark, so we'll use up all active threads
2390   uint active_workers = g1h->workers()->active_workers();
2391   set_concurrency_and_phase(active_workers, false /* concurrent */);
2392   // Leave _parallel_marking_threads at it's
2393   // value originally calculated in the ConcurrentMark
2394   // constructor and pass values of the active workers
2395   // through the gang in the task.
2396 
2397   {
2398     StrongRootsScope srs(active_workers);
2399 
2400     CMRemarkTask remarkTask(this, active_workers);
2401     // We will start all available threads, even if we decide that the
2402     // active_workers will be fewer. The extra ones will just bail out
2403     // immediately.
2404     g1h->workers()->run_task(&remarkTask);
2405   }
2406 
2407   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();
2408   guarantee(has_overflown() ||
2409             satb_mq_set.completed_buffers_num() == 0,
2410             "Invariant: has_overflown = %s, num buffers = %d",
2411             BOOL_TO_STR(has_overflown()),
2412             satb_mq_set.completed_buffers_num());
2413 
2414   print_stats();
2415 }
2416 
2417 void ConcurrentMark::clearRangePrevBitmap(MemRegion mr) {
2418   // Note we are overriding the read-only view of the prev map here, via
2419   // the cast.
2420   ((CMBitMap*)_prevMarkBitMap)->clearRange(mr);
2421 }
2422 
2423 void ConcurrentMark::clearRangeNextBitmap(MemRegion mr) {
2424   _nextMarkBitMap->clearRange(mr);
2425 }
2426 
2427 HeapRegion*
2428 ConcurrentMark::claim_region(uint worker_id) {
2429   // "checkpoint" the finger
2430   HeapWord* finger = _finger;
2431 
2432   // _heap_end will not change underneath our feet; it only changes at
2433   // yield points.
2434   while (finger < _heap_end) {
2435     assert(_g1h->is_in_g1_reserved(finger), "invariant");
2436 
2437     // Note on how this code handles humongous regions. In the
2438     // normal case the finger will reach the start of a "starts
2439     // humongous" (SH) region. Its end will either be the end of the
2440     // last "continues humongous" (CH) region in the sequence, or the
2441     // standard end of the SH region (if the SH is the only region in
2442     // the sequence). That way claim_region() will skip over the CH
2443     // regions. However, there is a subtle race between a CM thread
2444     // executing this method and a mutator thread doing a humongous
2445     // object allocation. The two are not mutually exclusive as the CM
2446     // thread does not need to hold the Heap_lock when it gets
2447     // here. So there is a chance that claim_region() will come across
2448     // a free region that's in the progress of becoming a SH or a CH
2449     // region. In the former case, it will either
2450     //   a) Miss the update to the region's end, in which case it will
2451     //      visit every subsequent CH region, will find their bitmaps
2452     //      empty, and do nothing, or
2453     //   b) Will observe the update of the region's end (in which case
2454     //      it will skip the subsequent CH regions).
2455     // If it comes across a region that suddenly becomes CH, the
2456     // scenario will be similar to b). So, the race between
2457     // claim_region() and a humongous object allocation might force us
2458     // to do a bit of unnecessary work (due to some unnecessary bitmap
2459     // iterations) but it should not introduce and correctness issues.
2460     HeapRegion* curr_region = _g1h->heap_region_containing_raw(finger);
2461 
2462     // Above heap_region_containing_raw may return NULL as we always scan claim
2463     // until the end of the heap. In this case, just jump to the next region.
2464     HeapWord* end = curr_region != NULL ? curr_region->end() : finger + HeapRegion::GrainWords;
2465 
2466     // Is the gap between reading the finger and doing the CAS too long?
2467     HeapWord* res = (HeapWord*) Atomic::cmpxchg_ptr(end, &_finger, finger);
2468     if (res == finger && curr_region != NULL) {
2469       // we succeeded
2470       HeapWord*   bottom        = curr_region->bottom();
2471       HeapWord*   limit         = curr_region->next_top_at_mark_start();
2472 
2473       // notice that _finger == end cannot be guaranteed here since,
2474       // someone else might have moved the finger even further
2475       assert(_finger >= end, "the finger should have moved forward");
2476 
2477       if (limit > bottom) {
2478         return curr_region;
2479       } else {
2480         assert(limit == bottom,
2481                "the region limit should be at bottom");
2482         // we return NULL and the caller should try calling
2483         // claim_region() again.
2484         return NULL;
2485       }
2486     } else {
2487       assert(_finger > finger, "the finger should have moved forward");
2488       // read it again
2489       finger = _finger;
2490     }
2491   }
2492 
2493   return NULL;
2494 }
2495 
2496 #ifndef PRODUCT
2497 class VerifyNoCSetOops VALUE_OBJ_CLASS_SPEC {
2498 private:
2499   G1CollectedHeap* _g1h;
2500   const char* _phase;
2501   int _info;
2502 
2503 public:
2504   VerifyNoCSetOops(const char* phase, int info = -1) :
2505     _g1h(G1CollectedHeap::heap()),
2506     _phase(phase),
2507     _info(info)
2508   { }
2509 
2510   void operator()(oop obj) const {
2511     guarantee(obj->is_oop(),
2512               "Non-oop " PTR_FORMAT ", phase: %s, info: %d",
2513               p2i(obj), _phase, _info);
2514     guarantee(!_g1h->obj_in_cs(obj),
2515               "obj: " PTR_FORMAT " in CSet, phase: %s, info: %d",
2516               p2i(obj), _phase, _info);
2517   }
2518 };
2519 
2520 void ConcurrentMark::verify_no_cset_oops() {
2521   assert(SafepointSynchronize::is_at_safepoint(), "should be at a safepoint");
2522   if (!G1CollectedHeap::heap()->collector_state()->mark_in_progress()) {
2523     return;
2524   }
2525 
2526   // Verify entries on the global mark stack
2527   _markStack.iterate(VerifyNoCSetOops("Stack"));
2528 
2529   // Verify entries on the task queues
2530   for (uint i = 0; i < _max_worker_id; ++i) {
2531     CMTaskQueue* queue = _task_queues->queue(i);
2532     queue->iterate(VerifyNoCSetOops("Queue", i));
2533   }
2534 
2535   // Verify the global finger
2536   HeapWord* global_finger = finger();
2537   if (global_finger != NULL && global_finger < _heap_end) {
2538     // The global finger always points to a heap region boundary. We
2539     // use heap_region_containing_raw() to get the containing region
2540     // given that the global finger could be pointing to a free region
2541     // which subsequently becomes continues humongous. If that
2542     // happens, heap_region_containing() will return the bottom of the
2543     // corresponding starts humongous region and the check below will
2544     // not hold any more.
2545     // Since we always iterate over all regions, we might get a NULL HeapRegion
2546     // here.
2547     HeapRegion* global_hr = _g1h->heap_region_containing_raw(global_finger);
2548     guarantee(global_hr == NULL || global_finger == global_hr->bottom(),
2549               "global finger: " PTR_FORMAT " region: " HR_FORMAT,
2550               p2i(global_finger), HR_FORMAT_PARAMS(global_hr));
2551   }
2552 
2553   // Verify the task fingers
2554   assert(parallel_marking_threads() <= _max_worker_id, "sanity");
2555   for (uint i = 0; i < parallel_marking_threads(); ++i) {
2556     CMTask* task = _tasks[i];
2557     HeapWord* task_finger = task->finger();
2558     if (task_finger != NULL && task_finger < _heap_end) {
2559       // See above note on the global finger verification.
2560       HeapRegion* task_hr = _g1h->heap_region_containing_raw(task_finger);
2561       guarantee(task_hr == NULL || task_finger == task_hr->bottom() ||
2562                 !task_hr->in_collection_set(),
2563                 "task finger: " PTR_FORMAT " region: " HR_FORMAT,
2564                 p2i(task_finger), HR_FORMAT_PARAMS(task_hr));
2565     }
2566   }
2567 }
2568 #endif // PRODUCT
2569 
2570 // Aggregate the counting data that was constructed concurrently
2571 // with marking.
2572 class AggregateCountDataHRClosure: public HeapRegionClosure {
2573   G1CollectedHeap* _g1h;
2574   ConcurrentMark* _cm;
2575   CardTableModRefBS* _ct_bs;
2576   BitMap* _cm_card_bm;
2577   uint _max_worker_id;
2578 
2579  public:
2580   AggregateCountDataHRClosure(G1CollectedHeap* g1h,
2581                               BitMap* cm_card_bm,
2582                               uint max_worker_id) :
2583     _g1h(g1h), _cm(g1h->concurrent_mark()),
2584     _ct_bs(barrier_set_cast<CardTableModRefBS>(g1h->barrier_set())),
2585     _cm_card_bm(cm_card_bm), _max_worker_id(max_worker_id) { }
2586 
2587   bool doHeapRegion(HeapRegion* hr) {
2588     if (hr->is_continues_humongous()) {
2589       // We will ignore these here and process them when their
2590       // associated "starts humongous" region is processed.
2591       // Note that we cannot rely on their associated
2592       // "starts humongous" region to have their bit set to 1
2593       // since, due to the region chunking in the parallel region
2594       // iteration, a "continues humongous" region might be visited
2595       // before its associated "starts humongous".
2596       return false;
2597     }
2598 
2599     HeapWord* start = hr->bottom();
2600     HeapWord* limit = hr->next_top_at_mark_start();
2601     HeapWord* end = hr->end();
2602 
2603     assert(start <= limit && limit <= hr->top() && hr->top() <= hr->end(),
2604            "Preconditions not met - "
2605            "start: " PTR_FORMAT ", limit: " PTR_FORMAT ", "
2606            "top: " PTR_FORMAT ", end: " PTR_FORMAT,
2607            p2i(start), p2i(limit), p2i(hr->top()), p2i(hr->end()));
2608 
2609     assert(hr->next_marked_bytes() == 0, "Precondition");
2610 
2611     if (start == limit) {
2612       // NTAMS of this region has not been set so nothing to do.
2613       return false;
2614     }
2615 
2616     // 'start' should be in the heap.
2617     assert(_g1h->is_in_g1_reserved(start) && _ct_bs->is_card_aligned(start), "sanity");
2618     // 'end' *may* be just beyond the end of the heap (if hr is the last region)
2619     assert(!_g1h->is_in_g1_reserved(end) || _ct_bs->is_card_aligned(end), "sanity");
2620 
2621     BitMap::idx_t start_idx = _cm->card_bitmap_index_for(start);
2622     BitMap::idx_t limit_idx = _cm->card_bitmap_index_for(limit);
2623     BitMap::idx_t end_idx = _cm->card_bitmap_index_for(end);
2624 
2625     // If ntams is not card aligned then we bump card bitmap index
2626     // for limit so that we get the all the cards spanned by
2627     // the object ending at ntams.
2628     // Note: if this is the last region in the heap then ntams
2629     // could be actually just beyond the end of the the heap;
2630     // limit_idx will then  correspond to a (non-existent) card
2631     // that is also outside the heap.
2632     if (_g1h->is_in_g1_reserved(limit) && !_ct_bs->is_card_aligned(limit)) {
2633       limit_idx += 1;
2634     }
2635 
2636     assert(limit_idx <= end_idx, "or else use atomics");
2637 
2638     // Aggregate the "stripe" in the count data associated with hr.
2639     uint hrm_index = hr->hrm_index();
2640     size_t marked_bytes = 0;
2641 
2642     for (uint i = 0; i < _max_worker_id; i += 1) {
2643       size_t* marked_bytes_array = _cm->count_marked_bytes_array_for(i);
2644       BitMap* task_card_bm = _cm->count_card_bitmap_for(i);
2645 
2646       // Fetch the marked_bytes in this region for task i and
2647       // add it to the running total for this region.
2648       marked_bytes += marked_bytes_array[hrm_index];
2649 
2650       // Now union the bitmaps[0,max_worker_id)[start_idx..limit_idx)
2651       // into the global card bitmap.
2652       BitMap::idx_t scan_idx = task_card_bm->get_next_one_offset(start_idx, limit_idx);
2653 
2654       while (scan_idx < limit_idx) {
2655         assert(task_card_bm->at(scan_idx) == true, "should be");
2656         _cm_card_bm->set_bit(scan_idx);
2657         assert(_cm_card_bm->at(scan_idx) == true, "should be");
2658 
2659         // BitMap::get_next_one_offset() can handle the case when
2660         // its left_offset parameter is greater than its right_offset
2661         // parameter. It does, however, have an early exit if
2662         // left_offset == right_offset. So let's limit the value
2663         // passed in for left offset here.
2664         BitMap::idx_t next_idx = MIN2(scan_idx + 1, limit_idx);
2665         scan_idx = task_card_bm->get_next_one_offset(next_idx, limit_idx);
2666       }
2667     }
2668 
2669     // Update the marked bytes for this region.
2670     hr->add_to_marked_bytes(marked_bytes);
2671 
2672     // Next heap region
2673     return false;
2674   }
2675 };
2676 
2677 class G1AggregateCountDataTask: public AbstractGangTask {
2678 protected:
2679   G1CollectedHeap* _g1h;
2680   ConcurrentMark* _cm;
2681   BitMap* _cm_card_bm;
2682   uint _max_worker_id;
2683   uint _active_workers;
2684   HeapRegionClaimer _hrclaimer;
2685 
2686 public:
2687   G1AggregateCountDataTask(G1CollectedHeap* g1h,
2688                            ConcurrentMark* cm,
2689                            BitMap* cm_card_bm,
2690                            uint max_worker_id,
2691                            uint n_workers) :
2692       AbstractGangTask("Count Aggregation"),
2693       _g1h(g1h), _cm(cm), _cm_card_bm(cm_card_bm),
2694       _max_worker_id(max_worker_id),
2695       _active_workers(n_workers),
2696       _hrclaimer(_active_workers) {
2697   }
2698 
2699   void work(uint worker_id) {
2700     AggregateCountDataHRClosure cl(_g1h, _cm_card_bm, _max_worker_id);
2701 
2702     _g1h->heap_region_par_iterate(&cl, worker_id, &_hrclaimer);
2703   }
2704 };
2705 
2706 
2707 void ConcurrentMark::aggregate_count_data() {
2708   uint n_workers = _g1h->workers()->active_workers();
2709 
2710   G1AggregateCountDataTask g1_par_agg_task(_g1h, this, &_card_bm,
2711                                            _max_worker_id, n_workers);
2712 
2713   _g1h->workers()->run_task(&g1_par_agg_task);
2714 }
2715 
2716 // Clear the per-worker arrays used to store the per-region counting data
2717 void ConcurrentMark::clear_all_count_data() {
2718   // Clear the global card bitmap - it will be filled during
2719   // liveness count aggregation (during remark) and the
2720   // final counting task.
2721   _card_bm.clear();
2722 
2723   // Clear the global region bitmap - it will be filled as part
2724   // of the final counting task.
2725   _region_bm.clear();
2726 
2727   uint max_regions = _g1h->max_regions();
2728   assert(_max_worker_id > 0, "uninitialized");
2729 
2730   for (uint i = 0; i < _max_worker_id; i += 1) {
2731     BitMap* task_card_bm = count_card_bitmap_for(i);
2732     size_t* marked_bytes_array = count_marked_bytes_array_for(i);
2733 
2734     assert(task_card_bm->size() == _card_bm.size(), "size mismatch");
2735     assert(marked_bytes_array != NULL, "uninitialized");
2736 
2737     memset(marked_bytes_array, 0, (size_t) max_regions * sizeof(size_t));
2738     task_card_bm->clear();
2739   }
2740 }
2741 
2742 void ConcurrentMark::print_stats() {
2743   LogHandle(gc, stats) log;
2744   if (!log.is_debug()) {
2745     return;
2746   }
2747   log.debug("---------------------------------------------------------------------");
2748   for (size_t i = 0; i < _active_tasks; ++i) {
2749     _tasks[i]->print_stats();
2750     log.debug("---------------------------------------------------------------------");
2751   }
2752 }
2753 
2754 // abandon current marking iteration due to a Full GC
2755 void ConcurrentMark::abort() {
2756   if (!cmThread()->during_cycle() || _has_aborted) {
2757     // We haven't started a concurrent cycle or we have already aborted it. No need to do anything.
2758     return;
2759   }
2760 
2761   // Clear all marks in the next bitmap for the next marking cycle. This will allow us to skip the next
2762   // concurrent bitmap clearing.
2763   _nextMarkBitMap->clearAll();
2764 
2765   // Note we cannot clear the previous marking bitmap here
2766   // since VerifyDuringGC verifies the objects marked during
2767   // a full GC against the previous bitmap.
2768 
2769   // Clear the liveness counting data
2770   clear_all_count_data();
2771   // Empty mark stack
2772   reset_marking_state();
2773   for (uint i = 0; i < _max_worker_id; ++i) {
2774     _tasks[i]->clear_region_fields();
2775   }
2776   _first_overflow_barrier_sync.abort();
2777   _second_overflow_barrier_sync.abort();
2778   _has_aborted = true;
2779 
2780   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();
2781   satb_mq_set.abandon_partial_marking();
2782   // This can be called either during or outside marking, we'll read
2783   // the expected_active value from the SATB queue set.
2784   satb_mq_set.set_active_all_threads(
2785                                  false, /* new active value */
2786                                  satb_mq_set.is_active() /* expected_active */);
2787 
2788   _g1h->trace_heap_after_concurrent_cycle();
2789   _g1h->register_concurrent_cycle_end();
2790 }
2791 
2792 static void print_ms_time_info(const char* prefix, const char* name,
2793                                NumberSeq& ns) {
2794   log_trace(gc, marking, stats, exit)("%s%5d %12s: total time = %8.2f s (avg = %8.2f ms).",
2795                                       prefix, ns.num(), name, ns.sum()/1000.0, ns.avg());
2796   if (ns.num() > 0) {
2797     log_trace(gc, marking, stats, exit)("%s         [std. dev = %8.2f ms, max = %8.2f ms]",
2798                                         prefix, ns.sd(), ns.maximum());
2799   }
2800 }
2801 
2802 void ConcurrentMark::print_summary_info() {
2803   LogHandle(gc, marking, stats, exit) log;
2804   if (!log.is_trace()) {
2805     return;
2806   }
2807 
2808   log.trace(" Concurrent marking:");
2809   print_ms_time_info("  ", "init marks", _init_times);
2810   print_ms_time_info("  ", "remarks", _remark_times);
2811   {
2812     print_ms_time_info("     ", "final marks", _remark_mark_times);
2813     print_ms_time_info("     ", "weak refs", _remark_weak_ref_times);
2814 
2815   }
2816   print_ms_time_info("  ", "cleanups", _cleanup_times);
2817   log.trace("    Final counting total time = %8.2f s (avg = %8.2f ms).",
2818             _total_counting_time, (_cleanup_times.num() > 0 ? _total_counting_time * 1000.0 / (double)_cleanup_times.num() : 0.0));
2819   if (G1ScrubRemSets) {
2820     log.trace("    RS scrub total time = %8.2f s (avg = %8.2f ms).",
2821               _total_rs_scrub_time, (_cleanup_times.num() > 0 ? _total_rs_scrub_time * 1000.0 / (double)_cleanup_times.num() : 0.0));
2822   }
2823   log.trace("  Total stop_world time = %8.2f s.",
2824             (_init_times.sum() + _remark_times.sum() + _cleanup_times.sum())/1000.0);
2825   log.trace("  Total concurrent time = %8.2f s (%8.2f s marking).",
2826             cmThread()->vtime_accum(), cmThread()->vtime_mark_accum());
2827 }
2828 
2829 void ConcurrentMark::print_worker_threads_on(outputStream* st) const {
2830   _parallel_workers->print_worker_threads_on(st);
2831 }
2832 
2833 void ConcurrentMark::print_on_error(outputStream* st) const {
2834   st->print_cr("Marking Bits (Prev, Next): (CMBitMap*) " PTR_FORMAT ", (CMBitMap*) " PTR_FORMAT,
2835       p2i(_prevMarkBitMap), p2i(_nextMarkBitMap));
2836   _prevMarkBitMap->print_on_error(st, " Prev Bits: ");
2837   _nextMarkBitMap->print_on_error(st, " Next Bits: ");
2838 }
2839 
2840 // We take a break if someone is trying to stop the world.
2841 bool ConcurrentMark::do_yield_check(uint worker_id) {
2842   if (SuspendibleThreadSet::should_yield()) {
2843     if (worker_id == 0) {
2844       _g1h->g1_policy()->record_concurrent_pause();
2845     }
2846     SuspendibleThreadSet::yield();
2847     return true;
2848   } else {
2849     return false;
2850   }
2851 }
2852 
2853 // Closure for iteration over bitmaps
2854 class CMBitMapClosure : public BitMapClosure {
2855 private:
2856   // the bitmap that is being iterated over
2857   CMBitMap*                   _nextMarkBitMap;
2858   ConcurrentMark*             _cm;
2859   CMTask*                     _task;
2860 
2861 public:
2862   CMBitMapClosure(CMTask *task, ConcurrentMark* cm, CMBitMap* nextMarkBitMap) :
2863     _task(task), _cm(cm), _nextMarkBitMap(nextMarkBitMap) { }
2864 
2865   bool do_bit(size_t offset) {
2866     HeapWord* addr = _nextMarkBitMap->offsetToHeapWord(offset);
2867     assert(_nextMarkBitMap->isMarked(addr), "invariant");
2868     assert( addr < _cm->finger(), "invariant");
2869     assert(addr >= _task->finger(), "invariant");
2870 
2871     // We move that task's local finger along.
2872     _task->move_finger_to(addr);
2873 
2874     _task->scan_object(oop(addr));
2875     // we only partially drain the local queue and global stack
2876     _task->drain_local_queue(true);
2877     _task->drain_global_stack(true);
2878 
2879     // if the has_aborted flag has been raised, we need to bail out of
2880     // the iteration
2881     return !_task->has_aborted();
2882   }
2883 };
2884 
2885 static ReferenceProcessor* get_cm_oop_closure_ref_processor(G1CollectedHeap* g1h) {
2886   ReferenceProcessor* result = NULL;
2887   if (G1UseConcMarkReferenceProcessing) {
2888     result = g1h->ref_processor_cm();
2889     assert(result != NULL, "should not be NULL");
2890   }
2891   return result;
2892 }
2893 
2894 G1CMOopClosure::G1CMOopClosure(G1CollectedHeap* g1h,
2895                                ConcurrentMark* cm,
2896                                CMTask* task)
2897   : MetadataAwareOopClosure(get_cm_oop_closure_ref_processor(g1h)),
2898     _g1h(g1h), _cm(cm), _task(task)
2899 { }
2900 
2901 void CMTask::setup_for_region(HeapRegion* hr) {
2902   assert(hr != NULL,
2903         "claim_region() should have filtered out NULL regions");
2904   assert(!hr->is_continues_humongous(),
2905         "claim_region() should have filtered out continues humongous regions");
2906   _curr_region  = hr;
2907   _finger       = hr->bottom();
2908   update_region_limit();
2909 }
2910 
2911 void CMTask::update_region_limit() {
2912   HeapRegion* hr            = _curr_region;
2913   HeapWord* bottom          = hr->bottom();
2914   HeapWord* limit           = hr->next_top_at_mark_start();
2915 
2916   if (limit == bottom) {
2917     // The region was collected underneath our feet.
2918     // We set the finger to bottom to ensure that the bitmap
2919     // iteration that will follow this will not do anything.
2920     // (this is not a condition that holds when we set the region up,
2921     // as the region is not supposed to be empty in the first place)
2922     _finger = bottom;
2923   } else if (limit >= _region_limit) {
2924     assert(limit >= _finger, "peace of mind");
2925   } else {
2926     assert(limit < _region_limit, "only way to get here");
2927     // This can happen under some pretty unusual circumstances.  An
2928     // evacuation pause empties the region underneath our feet (NTAMS
2929     // at bottom). We then do some allocation in the region (NTAMS
2930     // stays at bottom), followed by the region being used as a GC
2931     // alloc region (NTAMS will move to top() and the objects
2932     // originally below it will be grayed). All objects now marked in
2933     // the region are explicitly grayed, if below the global finger,
2934     // and we do not need in fact to scan anything else. So, we simply
2935     // set _finger to be limit to ensure that the bitmap iteration
2936     // doesn't do anything.
2937     _finger = limit;
2938   }
2939 
2940   _region_limit = limit;
2941 }
2942 
2943 void CMTask::giveup_current_region() {
2944   assert(_curr_region != NULL, "invariant");
2945   clear_region_fields();
2946 }
2947 
2948 void CMTask::clear_region_fields() {
2949   // Values for these three fields that indicate that we're not
2950   // holding on to a region.
2951   _curr_region   = NULL;
2952   _finger        = NULL;
2953   _region_limit  = NULL;
2954 }
2955 
2956 void CMTask::set_cm_oop_closure(G1CMOopClosure* cm_oop_closure) {
2957   if (cm_oop_closure == NULL) {
2958     assert(_cm_oop_closure != NULL, "invariant");
2959   } else {
2960     assert(_cm_oop_closure == NULL, "invariant");
2961   }
2962   _cm_oop_closure = cm_oop_closure;
2963 }
2964 
2965 void CMTask::reset(CMBitMap* nextMarkBitMap) {
2966   guarantee(nextMarkBitMap != NULL, "invariant");
2967   _nextMarkBitMap                = nextMarkBitMap;
2968   clear_region_fields();
2969 
2970   _calls                         = 0;
2971   _elapsed_time_ms               = 0.0;
2972   _termination_time_ms           = 0.0;
2973   _termination_start_time_ms     = 0.0;
2974 }
2975 
2976 bool CMTask::should_exit_termination() {
2977   regular_clock_call();
2978   // This is called when we are in the termination protocol. We should
2979   // quit if, for some reason, this task wants to abort or the global
2980   // stack is not empty (this means that we can get work from it).
2981   return !_cm->mark_stack_empty() || has_aborted();
2982 }
2983 
2984 void CMTask::reached_limit() {
2985   assert(_words_scanned >= _words_scanned_limit ||
2986          _refs_reached >= _refs_reached_limit ,
2987          "shouldn't have been called otherwise");
2988   regular_clock_call();
2989 }
2990 
2991 void CMTask::regular_clock_call() {
2992   if (has_aborted()) return;
2993 
2994   // First, we need to recalculate the words scanned and refs reached
2995   // limits for the next clock call.
2996   recalculate_limits();
2997 
2998   // During the regular clock call we do the following
2999 
3000   // (1) If an overflow has been flagged, then we abort.
3001   if (_cm->has_overflown()) {
3002     set_has_aborted();
3003     return;
3004   }
3005 
3006   // If we are not concurrent (i.e. we're doing remark) we don't need
3007   // to check anything else. The other steps are only needed during
3008   // the concurrent marking phase.
3009   if (!concurrent()) return;
3010 
3011   // (2) If marking has been aborted for Full GC, then we also abort.
3012   if (_cm->has_aborted()) {
3013     set_has_aborted();
3014     return;
3015   }
3016 
3017   double curr_time_ms = os::elapsedVTime() * 1000.0;
3018 
3019   // (4) We check whether we should yield. If we have to, then we abort.
3020   if (SuspendibleThreadSet::should_yield()) {
3021     // We should yield. To do this we abort the task. The caller is
3022     // responsible for yielding.
3023     set_has_aborted();
3024     return;
3025   }
3026 
3027   // (5) We check whether we've reached our time quota. If we have,
3028   // then we abort.
3029   double elapsed_time_ms = curr_time_ms - _start_time_ms;
3030   if (elapsed_time_ms > _time_target_ms) {
3031     set_has_aborted();
3032     _has_timed_out = true;
3033     return;
3034   }
3035 
3036   // (6) Finally, we check whether there are enough completed STAB
3037   // buffers available for processing. If there are, we abort.
3038   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();
3039   if (!_draining_satb_buffers && satb_mq_set.process_completed_buffers()) {
3040     // we do need to process SATB buffers, we'll abort and restart
3041     // the marking task to do so
3042     set_has_aborted();
3043     return;
3044   }
3045 }
3046 
3047 void CMTask::recalculate_limits() {
3048   _real_words_scanned_limit = _words_scanned + words_scanned_period;
3049   _words_scanned_limit      = _real_words_scanned_limit;
3050 
3051   _real_refs_reached_limit  = _refs_reached  + refs_reached_period;
3052   _refs_reached_limit       = _real_refs_reached_limit;
3053 }
3054 
3055 void CMTask::decrease_limits() {
3056   // This is called when we believe that we're going to do an infrequent
3057   // operation which will increase the per byte scanned cost (i.e. move
3058   // entries to/from the global stack). It basically tries to decrease the
3059   // scanning limit so that the clock is called earlier.
3060 
3061   _words_scanned_limit = _real_words_scanned_limit -
3062     3 * words_scanned_period / 4;
3063   _refs_reached_limit  = _real_refs_reached_limit -
3064     3 * refs_reached_period / 4;
3065 }
3066 
3067 void CMTask::move_entries_to_global_stack() {
3068   // local array where we'll store the entries that will be popped
3069   // from the local queue
3070   oop buffer[global_stack_transfer_size];
3071 
3072   int n = 0;
3073   oop obj;
3074   while (n < global_stack_transfer_size && _task_queue->pop_local(obj)) {
3075     buffer[n] = obj;
3076     ++n;
3077   }
3078 
3079   if (n > 0) {
3080     // we popped at least one entry from the local queue
3081 
3082     if (!_cm->mark_stack_push(buffer, n)) {
3083       set_has_aborted();
3084     }
3085   }
3086 
3087   // this operation was quite expensive, so decrease the limits
3088   decrease_limits();
3089 }
3090 
3091 void CMTask::get_entries_from_global_stack() {
3092   // local array where we'll store the entries that will be popped
3093   // from the global stack.
3094   oop buffer[global_stack_transfer_size];
3095   int n;
3096   _cm->mark_stack_pop(buffer, global_stack_transfer_size, &n);
3097   assert(n <= global_stack_transfer_size,
3098          "we should not pop more than the given limit");
3099   if (n > 0) {
3100     // yes, we did actually pop at least one entry
3101     for (int i = 0; i < n; ++i) {
3102       bool success = _task_queue->push(buffer[i]);
3103       // We only call this when the local queue is empty or under a
3104       // given target limit. So, we do not expect this push to fail.
3105       assert(success, "invariant");
3106     }
3107   }
3108 
3109   // this operation was quite expensive, so decrease the limits
3110   decrease_limits();
3111 }
3112 
3113 void CMTask::drain_local_queue(bool partially) {
3114   if (has_aborted()) return;
3115 
3116   // Decide what the target size is, depending whether we're going to
3117   // drain it partially (so that other tasks can steal if they run out
3118   // of things to do) or totally (at the very end).
3119   size_t target_size;
3120   if (partially) {
3121     target_size = MIN2((size_t)_task_queue->max_elems()/3, GCDrainStackTargetSize);
3122   } else {
3123     target_size = 0;
3124   }
3125 
3126   if (_task_queue->size() > target_size) {
3127     oop obj;
3128     bool ret = _task_queue->pop_local(obj);
3129     while (ret) {
3130       assert(_g1h->is_in_g1_reserved((HeapWord*) obj), "invariant" );
3131       assert(!_g1h->is_on_master_free_list(
3132                   _g1h->heap_region_containing((HeapWord*) obj)), "invariant");
3133 
3134       scan_object(obj);
3135 
3136       if (_task_queue->size() <= target_size || has_aborted()) {
3137         ret = false;
3138       } else {
3139         ret = _task_queue->pop_local(obj);
3140       }
3141     }
3142   }
3143 }
3144 
3145 void CMTask::drain_global_stack(bool partially) {
3146   if (has_aborted()) return;
3147 
3148   // We have a policy to drain the local queue before we attempt to
3149   // drain the global stack.
3150   assert(partially || _task_queue->size() == 0, "invariant");
3151 
3152   // Decide what the target size is, depending whether we're going to
3153   // drain it partially (so that other tasks can steal if they run out
3154   // of things to do) or totally (at the very end).  Notice that,
3155   // because we move entries from the global stack in chunks or
3156   // because another task might be doing the same, we might in fact
3157   // drop below the target. But, this is not a problem.
3158   size_t target_size;
3159   if (partially) {
3160     target_size = _cm->partial_mark_stack_size_target();
3161   } else {
3162     target_size = 0;
3163   }
3164 
3165   if (_cm->mark_stack_size() > target_size) {
3166     while (!has_aborted() && _cm->mark_stack_size() > target_size) {
3167       get_entries_from_global_stack();
3168       drain_local_queue(partially);
3169     }
3170   }
3171 }
3172 
3173 // SATB Queue has several assumptions on whether to call the par or
3174 // non-par versions of the methods. this is why some of the code is
3175 // replicated. We should really get rid of the single-threaded version
3176 // of the code to simplify things.
3177 void CMTask::drain_satb_buffers() {
3178   if (has_aborted()) return;
3179 
3180   // We set this so that the regular clock knows that we're in the
3181   // middle of draining buffers and doesn't set the abort flag when it
3182   // notices that SATB buffers are available for draining. It'd be
3183   // very counter productive if it did that. :-)
3184   _draining_satb_buffers = true;
3185 
3186   CMSATBBufferClosure satb_cl(this, _g1h);
3187   SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set();
3188 
3189   // This keeps claiming and applying the closure to completed buffers
3190   // until we run out of buffers or we need to abort.
3191   while (!has_aborted() &&
3192          satb_mq_set.apply_closure_to_completed_buffer(&satb_cl)) {
3193     regular_clock_call();
3194   }
3195 
3196   _draining_satb_buffers = false;
3197 
3198   assert(has_aborted() ||
3199          concurrent() ||
3200          satb_mq_set.completed_buffers_num() == 0, "invariant");
3201 
3202   // again, this was a potentially expensive operation, decrease the
3203   // limits to get the regular clock call early
3204   decrease_limits();
3205 }
3206 
3207 void CMTask::print_stats() {
3208   log_debug(gc, stats)("Marking Stats, task = %u, calls = %d",
3209                        _worker_id, _calls);
3210   log_debug(gc, stats)("  Elapsed time = %1.2lfms, Termination time = %1.2lfms",
3211                        _elapsed_time_ms, _termination_time_ms);
3212   log_debug(gc, stats)("  Step Times (cum): num = %d, avg = %1.2lfms, sd = %1.2lfms",
3213                        _step_times_ms.num(), _step_times_ms.avg(),
3214                        _step_times_ms.sd());
3215   log_debug(gc, stats)("                    max = %1.2lfms, total = %1.2lfms",
3216                        _step_times_ms.maximum(), _step_times_ms.sum());
3217 }
3218 
3219 bool ConcurrentMark::try_stealing(uint worker_id, int* hash_seed, oop& obj) {
3220   return _task_queues->steal(worker_id, hash_seed, obj);
3221 }
3222 
3223 /*****************************************************************************
3224 
3225     The do_marking_step(time_target_ms, ...) method is the building
3226     block of the parallel marking framework. It can be called in parallel
3227     with other invocations of do_marking_step() on different tasks
3228     (but only one per task, obviously) and concurrently with the
3229     mutator threads, or during remark, hence it eliminates the need
3230     for two versions of the code. When called during remark, it will
3231     pick up from where the task left off during the concurrent marking
3232     phase. Interestingly, tasks are also claimable during evacuation
3233     pauses too, since do_marking_step() ensures that it aborts before
3234     it needs to yield.
3235 
3236     The data structures that it uses to do marking work are the
3237     following:
3238 
3239       (1) Marking Bitmap. If there are gray objects that appear only
3240       on the bitmap (this happens either when dealing with an overflow
3241       or when the initial marking phase has simply marked the roots
3242       and didn't push them on the stack), then tasks claim heap
3243       regions whose bitmap they then scan to find gray objects. A
3244       global finger indicates where the end of the last claimed region
3245       is. A local finger indicates how far into the region a task has
3246       scanned. The two fingers are used to determine how to gray an
3247       object (i.e. whether simply marking it is OK, as it will be
3248       visited by a task in the future, or whether it needs to be also
3249       pushed on a stack).
3250 
3251       (2) Local Queue. The local queue of the task which is accessed
3252       reasonably efficiently by the task. Other tasks can steal from
3253       it when they run out of work. Throughout the marking phase, a
3254       task attempts to keep its local queue short but not totally
3255       empty, so that entries are available for stealing by other
3256       tasks. Only when there is no more work, a task will totally
3257       drain its local queue.
3258 
3259       (3) Global Mark Stack. This handles local queue overflow. During
3260       marking only sets of entries are moved between it and the local
3261       queues, as access to it requires a mutex and more fine-grain
3262       interaction with it which might cause contention. If it
3263       overflows, then the marking phase should restart and iterate
3264       over the bitmap to identify gray objects. Throughout the marking
3265       phase, tasks attempt to keep the global mark stack at a small
3266       length but not totally empty, so that entries are available for
3267       popping by other tasks. Only when there is no more work, tasks
3268       will totally drain the global mark stack.
3269 
3270       (4) SATB Buffer Queue. This is where completed SATB buffers are
3271       made available. Buffers are regularly removed from this queue
3272       and scanned for roots, so that the queue doesn't get too
3273       long. During remark, all completed buffers are processed, as
3274       well as the filled in parts of any uncompleted buffers.
3275 
3276     The do_marking_step() method tries to abort when the time target
3277     has been reached. There are a few other cases when the
3278     do_marking_step() method also aborts:
3279 
3280       (1) When the marking phase has been aborted (after a Full GC).
3281 
3282       (2) When a global overflow (on the global stack) has been
3283       triggered. Before the task aborts, it will actually sync up with
3284       the other tasks to ensure that all the marking data structures
3285       (local queues, stacks, fingers etc.)  are re-initialized so that
3286       when do_marking_step() completes, the marking phase can
3287       immediately restart.
3288 
3289       (3) When enough completed SATB buffers are available. The
3290       do_marking_step() method only tries to drain SATB buffers right
3291       at the beginning. So, if enough buffers are available, the
3292       marking step aborts and the SATB buffers are processed at
3293       the beginning of the next invocation.
3294 
3295       (4) To yield. when we have to yield then we abort and yield
3296       right at the end of do_marking_step(). This saves us from a lot
3297       of hassle as, by yielding we might allow a Full GC. If this
3298       happens then objects will be compacted underneath our feet, the
3299       heap might shrink, etc. We save checking for this by just
3300       aborting and doing the yield right at the end.
3301 
3302     From the above it follows that the do_marking_step() method should
3303     be called in a loop (or, otherwise, regularly) until it completes.
3304 
3305     If a marking step completes without its has_aborted() flag being
3306     true, it means it has completed the current marking phase (and
3307     also all other marking tasks have done so and have all synced up).
3308 
3309     A method called regular_clock_call() is invoked "regularly" (in
3310     sub ms intervals) throughout marking. It is this clock method that
3311     checks all the abort conditions which were mentioned above and
3312     decides when the task should abort. A work-based scheme is used to
3313     trigger this clock method: when the number of object words the
3314     marking phase has scanned or the number of references the marking
3315     phase has visited reach a given limit. Additional invocations to
3316     the method clock have been planted in a few other strategic places
3317     too. The initial reason for the clock method was to avoid calling
3318     vtime too regularly, as it is quite expensive. So, once it was in
3319     place, it was natural to piggy-back all the other conditions on it
3320     too and not constantly check them throughout the code.
3321 
3322     If do_termination is true then do_marking_step will enter its
3323     termination protocol.
3324 
3325     The value of is_serial must be true when do_marking_step is being
3326     called serially (i.e. by the VMThread) and do_marking_step should
3327     skip any synchronization in the termination and overflow code.
3328     Examples include the serial remark code and the serial reference
3329     processing closures.
3330 
3331     The value of is_serial must be false when do_marking_step is
3332     being called by any of the worker threads in a work gang.
3333     Examples include the concurrent marking code (CMMarkingTask),
3334     the MT remark code, and the MT reference processing closures.
3335 
3336  *****************************************************************************/
3337 
3338 void CMTask::do_marking_step(double time_target_ms,
3339                              bool do_termination,
3340                              bool is_serial) {
3341   assert(time_target_ms >= 1.0, "minimum granularity is 1ms");
3342   assert(concurrent() == _cm->concurrent(), "they should be the same");
3343 
3344   G1CollectorPolicy* g1_policy = _g1h->g1_policy();
3345   assert(_task_queues != NULL, "invariant");
3346   assert(_task_queue != NULL, "invariant");
3347   assert(_task_queues->queue(_worker_id) == _task_queue, "invariant");
3348 
3349   assert(!_claimed,
3350          "only one thread should claim this task at any one time");
3351 
3352   // OK, this doesn't safeguard again all possible scenarios, as it is
3353   // possible for two threads to set the _claimed flag at the same
3354   // time. But it is only for debugging purposes anyway and it will
3355   // catch most problems.
3356   _claimed = true;
3357 
3358   _start_time_ms = os::elapsedVTime() * 1000.0;
3359 
3360   // If do_stealing is true then do_marking_step will attempt to
3361   // steal work from the other CMTasks. It only makes sense to
3362   // enable stealing when the termination protocol is enabled
3363   // and do_marking_step() is not being called serially.
3364   bool do_stealing = do_termination && !is_serial;
3365 
3366   double diff_prediction_ms = _g1h->g1_policy()->predictor().get_new_prediction(&_marking_step_diffs_ms);
3367   _time_target_ms = time_target_ms - diff_prediction_ms;
3368 
3369   // set up the variables that are used in the work-based scheme to
3370   // call the regular clock method
3371   _words_scanned = 0;
3372   _refs_reached  = 0;
3373   recalculate_limits();
3374 
3375   // clear all flags
3376   clear_has_aborted();
3377   _has_timed_out = false;
3378   _draining_satb_buffers = false;
3379 
3380   ++_calls;
3381 
3382   // Set up the bitmap and oop closures. Anything that uses them is
3383   // eventually called from this method, so it is OK to allocate these
3384   // statically.
3385   CMBitMapClosure bitmap_closure(this, _cm, _nextMarkBitMap);
3386   G1CMOopClosure  cm_oop_closure(_g1h, _cm, this);
3387   set_cm_oop_closure(&cm_oop_closure);
3388 
3389   if (_cm->has_overflown()) {
3390     // This can happen if the mark stack overflows during a GC pause
3391     // and this task, after a yield point, restarts. We have to abort
3392     // as we need to get into the overflow protocol which happens
3393     // right at the end of this task.
3394     set_has_aborted();
3395   }
3396 
3397   // First drain any available SATB buffers. After this, we will not
3398   // look at SATB buffers before the next invocation of this method.
3399   // If enough completed SATB buffers are queued up, the regular clock
3400   // will abort this task so that it restarts.
3401   drain_satb_buffers();
3402   // ...then partially drain the local queue and the global stack
3403   drain_local_queue(true);
3404   drain_global_stack(true);
3405 
3406   do {
3407     if (!has_aborted() && _curr_region != NULL) {
3408       // This means that we're already holding on to a region.
3409       assert(_finger != NULL, "if region is not NULL, then the finger "
3410              "should not be NULL either");
3411 
3412       // We might have restarted this task after an evacuation pause
3413       // which might have evacuated the region we're holding on to
3414       // underneath our feet. Let's read its limit again to make sure
3415       // that we do not iterate over a region of the heap that
3416       // contains garbage (update_region_limit() will also move
3417       // _finger to the start of the region if it is found empty).
3418       update_region_limit();
3419       // We will start from _finger not from the start of the region,
3420       // as we might be restarting this task after aborting half-way
3421       // through scanning this region. In this case, _finger points to
3422       // the address where we last found a marked object. If this is a
3423       // fresh region, _finger points to start().
3424       MemRegion mr = MemRegion(_finger, _region_limit);
3425 
3426       assert(!_curr_region->is_humongous() || mr.start() == _curr_region->bottom(),
3427              "humongous regions should go around loop once only");
3428 
3429       // Some special cases:
3430       // If the memory region is empty, we can just give up the region.
3431       // If the current region is humongous then we only need to check
3432       // the bitmap for the bit associated with the start of the object,
3433       // scan the object if it's live, and give up the region.
3434       // Otherwise, let's iterate over the bitmap of the part of the region
3435       // that is left.
3436       // If the iteration is successful, give up the region.
3437       if (mr.is_empty()) {
3438         giveup_current_region();
3439         regular_clock_call();
3440       } else if (_curr_region->is_humongous() && mr.start() == _curr_region->bottom()) {
3441         if (_nextMarkBitMap->isMarked(mr.start())) {
3442           // The object is marked - apply the closure
3443           BitMap::idx_t offset = _nextMarkBitMap->heapWordToOffset(mr.start());
3444           bitmap_closure.do_bit(offset);
3445         }
3446         // Even if this task aborted while scanning the humongous object
3447         // we can (and should) give up the current region.
3448         giveup_current_region();
3449         regular_clock_call();
3450       } else if (_nextMarkBitMap->iterate(&bitmap_closure, mr)) {
3451         giveup_current_region();
3452         regular_clock_call();
3453       } else {
3454         assert(has_aborted(), "currently the only way to do so");
3455         // The only way to abort the bitmap iteration is to return
3456         // false from the do_bit() method. However, inside the
3457         // do_bit() method we move the _finger to point to the
3458         // object currently being looked at. So, if we bail out, we
3459         // have definitely set _finger to something non-null.
3460         assert(_finger != NULL, "invariant");
3461 
3462         // Region iteration was actually aborted. So now _finger
3463         // points to the address of the object we last scanned. If we
3464         // leave it there, when we restart this task, we will rescan
3465         // the object. It is easy to avoid this. We move the finger by
3466         // enough to point to the next possible object header (the
3467         // bitmap knows by how much we need to move it as it knows its
3468         // granularity).
3469         assert(_finger < _region_limit, "invariant");
3470         HeapWord* new_finger = _nextMarkBitMap->nextObject(_finger);
3471         // Check if bitmap iteration was aborted while scanning the last object
3472         if (new_finger >= _region_limit) {
3473           giveup_current_region();
3474         } else {
3475           move_finger_to(new_finger);
3476         }
3477       }
3478     }
3479     // At this point we have either completed iterating over the
3480     // region we were holding on to, or we have aborted.
3481 
3482     // We then partially drain the local queue and the global stack.
3483     // (Do we really need this?)
3484     drain_local_queue(true);
3485     drain_global_stack(true);
3486 
3487     // Read the note on the claim_region() method on why it might
3488     // return NULL with potentially more regions available for
3489     // claiming and why we have to check out_of_regions() to determine
3490     // whether we're done or not.
3491     while (!has_aborted() && _curr_region == NULL && !_cm->out_of_regions()) {
3492       // We are going to try to claim a new region. We should have
3493       // given up on the previous one.
3494       // Separated the asserts so that we know which one fires.
3495       assert(_curr_region  == NULL, "invariant");
3496       assert(_finger       == NULL, "invariant");
3497       assert(_region_limit == NULL, "invariant");
3498       HeapRegion* claimed_region = _cm->claim_region(_worker_id);
3499       if (claimed_region != NULL) {
3500         // Yes, we managed to claim one
3501         setup_for_region(claimed_region);
3502         assert(_curr_region == claimed_region, "invariant");
3503       }
3504       // It is important to call the regular clock here. It might take
3505       // a while to claim a region if, for example, we hit a large
3506       // block of empty regions. So we need to call the regular clock
3507       // method once round the loop to make sure it's called
3508       // frequently enough.
3509       regular_clock_call();
3510     }
3511 
3512     if (!has_aborted() && _curr_region == NULL) {
3513       assert(_cm->out_of_regions(),
3514              "at this point we should be out of regions");
3515     }
3516   } while ( _curr_region != NULL && !has_aborted());
3517 
3518   if (!has_aborted()) {
3519     // We cannot check whether the global stack is empty, since other
3520     // tasks might be pushing objects to it concurrently.
3521     assert(_cm->out_of_regions(),
3522            "at this point we should be out of regions");
3523     // Try to reduce the number of available SATB buffers so that
3524     // remark has less work to do.
3525     drain_satb_buffers();
3526   }
3527 
3528   // Since we've done everything else, we can now totally drain the
3529   // local queue and global stack.
3530   drain_local_queue(false);
3531   drain_global_stack(false);
3532 
3533   // Attempt at work stealing from other task's queues.
3534   if (do_stealing && !has_aborted()) {
3535     // We have not aborted. This means that we have finished all that
3536     // we could. Let's try to do some stealing...
3537 
3538     // We cannot check whether the global stack is empty, since other
3539     // tasks might be pushing objects to it concurrently.
3540     assert(_cm->out_of_regions() && _task_queue->size() == 0,
3541            "only way to reach here");
3542     while (!has_aborted()) {
3543       oop obj;
3544       if (_cm->try_stealing(_worker_id, &_hash_seed, obj)) {
3545         assert(_nextMarkBitMap->isMarked((HeapWord*) obj),
3546                "any stolen object should be marked");
3547         scan_object(obj);
3548 
3549         // And since we're towards the end, let's totally drain the
3550         // local queue and global stack.
3551         drain_local_queue(false);
3552         drain_global_stack(false);
3553       } else {
3554         break;
3555       }
3556     }
3557   }
3558 
3559   // If we are about to wrap up and go into termination, check if we
3560   // should raise the overflow flag.
3561   if (do_termination && !has_aborted()) {
3562     if (_cm->force_overflow()->should_force()) {
3563       _cm->set_has_overflown();
3564       regular_clock_call();
3565     }
3566   }
3567 
3568   // We still haven't aborted. Now, let's try to get into the
3569   // termination protocol.
3570   if (do_termination && !has_aborted()) {
3571     // We cannot check whether the global stack is empty, since other
3572     // tasks might be concurrently pushing objects on it.
3573     // Separated the asserts so that we know which one fires.
3574     assert(_cm->out_of_regions(), "only way to reach here");
3575     assert(_task_queue->size() == 0, "only way to reach here");
3576     _termination_start_time_ms = os::elapsedVTime() * 1000.0;
3577 
3578     // The CMTask class also extends the TerminatorTerminator class,
3579     // hence its should_exit_termination() method will also decide
3580     // whether to exit the termination protocol or not.
3581     bool finished = (is_serial ||
3582                      _cm->terminator()->offer_termination(this));
3583     double termination_end_time_ms = os::elapsedVTime() * 1000.0;
3584     _termination_time_ms +=
3585       termination_end_time_ms - _termination_start_time_ms;
3586 
3587     if (finished) {
3588       // We're all done.
3589 
3590       if (_worker_id == 0) {
3591         // let's allow task 0 to do this
3592         if (concurrent()) {
3593           assert(_cm->concurrent_marking_in_progress(), "invariant");
3594           // we need to set this to false before the next
3595           // safepoint. This way we ensure that the marking phase
3596           // doesn't observe any more heap expansions.
3597           _cm->clear_concurrent_marking_in_progress();
3598         }
3599       }
3600 
3601       // We can now guarantee that the global stack is empty, since
3602       // all other tasks have finished. We separated the guarantees so
3603       // that, if a condition is false, we can immediately find out
3604       // which one.
3605       guarantee(_cm->out_of_regions(), "only way to reach here");
3606       guarantee(_cm->mark_stack_empty(), "only way to reach here");
3607       guarantee(_task_queue->size() == 0, "only way to reach here");
3608       guarantee(!_cm->has_overflown(), "only way to reach here");
3609       guarantee(!_cm->mark_stack_overflow(), "only way to reach here");
3610     } else {
3611       // Apparently there's more work to do. Let's abort this task. It
3612       // will restart it and we can hopefully find more things to do.
3613       set_has_aborted();
3614     }
3615   }
3616 
3617   // Mainly for debugging purposes to make sure that a pointer to the
3618   // closure which was statically allocated in this frame doesn't
3619   // escape it by accident.
3620   set_cm_oop_closure(NULL);
3621   double end_time_ms = os::elapsedVTime() * 1000.0;
3622   double elapsed_time_ms = end_time_ms - _start_time_ms;
3623   // Update the step history.
3624   _step_times_ms.add(elapsed_time_ms);
3625 
3626   if (has_aborted()) {
3627     // The task was aborted for some reason.
3628     if (_has_timed_out) {
3629       double diff_ms = elapsed_time_ms - _time_target_ms;
3630       // Keep statistics of how well we did with respect to hitting
3631       // our target only if we actually timed out (if we aborted for
3632       // other reasons, then the results might get skewed).
3633       _marking_step_diffs_ms.add(diff_ms);
3634     }
3635 
3636     if (_cm->has_overflown()) {
3637       // This is the interesting one. We aborted because a global
3638       // overflow was raised. This means we have to restart the
3639       // marking phase and start iterating over regions. However, in
3640       // order to do this we have to make sure that all tasks stop
3641       // what they are doing and re-initialize in a safe manner. We
3642       // will achieve this with the use of two barrier sync points.
3643 
3644       if (!is_serial) {
3645         // We only need to enter the sync barrier if being called
3646         // from a parallel context
3647         _cm->enter_first_sync_barrier(_worker_id);
3648 
3649         // When we exit this sync barrier we know that all tasks have
3650         // stopped doing marking work. So, it's now safe to
3651         // re-initialize our data structures. At the end of this method,
3652         // task 0 will clear the global data structures.
3653       }
3654 
3655       // We clear the local state of this task...
3656       clear_region_fields();
3657 
3658       if (!is_serial) {
3659         // ...and enter the second barrier.
3660         _cm->enter_second_sync_barrier(_worker_id);
3661       }
3662       // At this point, if we're during the concurrent phase of
3663       // marking, everything has been re-initialized and we're
3664       // ready to restart.
3665     }
3666   }
3667 
3668   _claimed = false;
3669 }
3670 
3671 CMTask::CMTask(uint worker_id,
3672                ConcurrentMark* cm,
3673                size_t* marked_bytes,
3674                BitMap* card_bm,
3675                CMTaskQueue* task_queue,
3676                CMTaskQueueSet* task_queues)
3677   : _g1h(G1CollectedHeap::heap()),
3678     _worker_id(worker_id), _cm(cm),
3679     _claimed(false),
3680     _nextMarkBitMap(NULL), _hash_seed(17),
3681     _task_queue(task_queue),
3682     _task_queues(task_queues),
3683     _cm_oop_closure(NULL),
3684     _marked_bytes_array(marked_bytes),
3685     _card_bm(card_bm) {
3686   guarantee(task_queue != NULL, "invariant");
3687   guarantee(task_queues != NULL, "invariant");
3688 
3689   _marking_step_diffs_ms.add(0.5);
3690 }
3691 
3692 // These are formatting macros that are used below to ensure
3693 // consistent formatting. The *_H_* versions are used to format the
3694 // header for a particular value and they should be kept consistent
3695 // with the corresponding macro. Also note that most of the macros add
3696 // the necessary white space (as a prefix) which makes them a bit
3697 // easier to compose.
3698 
3699 // All the output lines are prefixed with this string to be able to
3700 // identify them easily in a large log file.
3701 #define G1PPRL_LINE_PREFIX            "###"
3702 
3703 #define G1PPRL_ADDR_BASE_FORMAT    " " PTR_FORMAT "-" PTR_FORMAT
3704 #ifdef _LP64
3705 #define G1PPRL_ADDR_BASE_H_FORMAT  " %37s"
3706 #else // _LP64
3707 #define G1PPRL_ADDR_BASE_H_FORMAT  " %21s"
3708 #endif // _LP64
3709 
3710 // For per-region info
3711 #define G1PPRL_TYPE_FORMAT            "   %-4s"
3712 #define G1PPRL_TYPE_H_FORMAT          "   %4s"
3713 #define G1PPRL_BYTE_FORMAT            "  " SIZE_FORMAT_W(9)
3714 #define G1PPRL_BYTE_H_FORMAT          "  %9s"
3715 #define G1PPRL_DOUBLE_FORMAT          "  %14.1f"
3716 #define G1PPRL_DOUBLE_H_FORMAT        "  %14s"
3717 
3718 // For summary info
3719 #define G1PPRL_SUM_ADDR_FORMAT(tag)    "  " tag ":" G1PPRL_ADDR_BASE_FORMAT
3720 #define G1PPRL_SUM_BYTE_FORMAT(tag)    "  " tag ": " SIZE_FORMAT
3721 #define G1PPRL_SUM_MB_FORMAT(tag)      "  " tag ": %1.2f MB"
3722 #define G1PPRL_SUM_MB_PERC_FORMAT(tag) G1PPRL_SUM_MB_FORMAT(tag) " / %1.2f %%"
3723 
3724 G1PrintRegionLivenessInfoClosure::
3725 G1PrintRegionLivenessInfoClosure(const char* phase_name)
3726   : _total_used_bytes(0), _total_capacity_bytes(0),
3727     _total_prev_live_bytes(0), _total_next_live_bytes(0),
3728     _hum_used_bytes(0), _hum_capacity_bytes(0),
3729     _hum_prev_live_bytes(0), _hum_next_live_bytes(0),
3730     _total_remset_bytes(0), _total_strong_code_roots_bytes(0) {
3731   G1CollectedHeap* g1h = G1CollectedHeap::heap();
3732   MemRegion g1_reserved = g1h->g1_reserved();
3733   double now = os::elapsedTime();
3734 
3735   // Print the header of the output.
3736   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX" PHASE %s @ %1.3f", phase_name, now);
3737   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX" HEAP"
3738                           G1PPRL_SUM_ADDR_FORMAT("reserved")
3739                           G1PPRL_SUM_BYTE_FORMAT("region-size"),
3740                           p2i(g1_reserved.start()), p2i(g1_reserved.end()),
3741                           HeapRegion::GrainBytes);
3742   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX);
3743   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX
3744                           G1PPRL_TYPE_H_FORMAT
3745                           G1PPRL_ADDR_BASE_H_FORMAT
3746                           G1PPRL_BYTE_H_FORMAT
3747                           G1PPRL_BYTE_H_FORMAT
3748                           G1PPRL_BYTE_H_FORMAT
3749                           G1PPRL_DOUBLE_H_FORMAT
3750                           G1PPRL_BYTE_H_FORMAT
3751                           G1PPRL_BYTE_H_FORMAT,
3752                           "type", "address-range",
3753                           "used", "prev-live", "next-live", "gc-eff",
3754                           "remset", "code-roots");
3755   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX
3756                           G1PPRL_TYPE_H_FORMAT
3757                           G1PPRL_ADDR_BASE_H_FORMAT
3758                           G1PPRL_BYTE_H_FORMAT
3759                           G1PPRL_BYTE_H_FORMAT
3760                           G1PPRL_BYTE_H_FORMAT
3761                           G1PPRL_DOUBLE_H_FORMAT
3762                           G1PPRL_BYTE_H_FORMAT
3763                           G1PPRL_BYTE_H_FORMAT,
3764                           "", "",
3765                           "(bytes)", "(bytes)", "(bytes)", "(bytes/ms)",
3766                           "(bytes)", "(bytes)");
3767 }
3768 
3769 // It takes as a parameter a reference to one of the _hum_* fields, it
3770 // deduces the corresponding value for a region in a humongous region
3771 // series (either the region size, or what's left if the _hum_* field
3772 // is < the region size), and updates the _hum_* field accordingly.
3773 size_t G1PrintRegionLivenessInfoClosure::get_hum_bytes(size_t* hum_bytes) {
3774   size_t bytes = 0;
3775   // The > 0 check is to deal with the prev and next live bytes which
3776   // could be 0.
3777   if (*hum_bytes > 0) {
3778     bytes = MIN2(HeapRegion::GrainBytes, *hum_bytes);
3779     *hum_bytes -= bytes;
3780   }
3781   return bytes;
3782 }
3783 
3784 // It deduces the values for a region in a humongous region series
3785 // from the _hum_* fields and updates those accordingly. It assumes
3786 // that that _hum_* fields have already been set up from the "starts
3787 // humongous" region and we visit the regions in address order.
3788 void G1PrintRegionLivenessInfoClosure::get_hum_bytes(size_t* used_bytes,
3789                                                      size_t* capacity_bytes,
3790                                                      size_t* prev_live_bytes,
3791                                                      size_t* next_live_bytes) {
3792   assert(_hum_used_bytes > 0 && _hum_capacity_bytes > 0, "pre-condition");
3793   *used_bytes      = get_hum_bytes(&_hum_used_bytes);
3794   *capacity_bytes  = get_hum_bytes(&_hum_capacity_bytes);
3795   *prev_live_bytes = get_hum_bytes(&_hum_prev_live_bytes);
3796   *next_live_bytes = get_hum_bytes(&_hum_next_live_bytes);
3797 }
3798 
3799 bool G1PrintRegionLivenessInfoClosure::doHeapRegion(HeapRegion* r) {
3800   const char* type       = r->get_type_str();
3801   HeapWord* bottom       = r->bottom();
3802   HeapWord* end          = r->end();
3803   size_t capacity_bytes  = r->capacity();
3804   size_t used_bytes      = r->used();
3805   size_t prev_live_bytes = r->live_bytes();
3806   size_t next_live_bytes = r->next_live_bytes();
3807   double gc_eff          = r->gc_efficiency();
3808   size_t remset_bytes    = r->rem_set()->mem_size();
3809   size_t strong_code_roots_bytes = r->rem_set()->strong_code_roots_mem_size();
3810 
3811   if (r->is_starts_humongous()) {
3812     assert(_hum_used_bytes == 0 && _hum_capacity_bytes == 0 &&
3813            _hum_prev_live_bytes == 0 && _hum_next_live_bytes == 0,
3814            "they should have been zeroed after the last time we used them");
3815     // Set up the _hum_* fields.
3816     _hum_capacity_bytes  = capacity_bytes;
3817     _hum_used_bytes      = used_bytes;
3818     _hum_prev_live_bytes = prev_live_bytes;
3819     _hum_next_live_bytes = next_live_bytes;
3820     get_hum_bytes(&used_bytes, &capacity_bytes,
3821                   &prev_live_bytes, &next_live_bytes);
3822     end = bottom + HeapRegion::GrainWords;
3823   } else if (r->is_continues_humongous()) {
3824     get_hum_bytes(&used_bytes, &capacity_bytes,
3825                   &prev_live_bytes, &next_live_bytes);
3826     assert(end == bottom + HeapRegion::GrainWords, "invariant");
3827   }
3828 
3829   _total_used_bytes      += used_bytes;
3830   _total_capacity_bytes  += capacity_bytes;
3831   _total_prev_live_bytes += prev_live_bytes;
3832   _total_next_live_bytes += next_live_bytes;
3833   _total_remset_bytes    += remset_bytes;
3834   _total_strong_code_roots_bytes += strong_code_roots_bytes;
3835 
3836   // Print a line for this particular region.
3837   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX
3838                           G1PPRL_TYPE_FORMAT
3839                           G1PPRL_ADDR_BASE_FORMAT
3840                           G1PPRL_BYTE_FORMAT
3841                           G1PPRL_BYTE_FORMAT
3842                           G1PPRL_BYTE_FORMAT
3843                           G1PPRL_DOUBLE_FORMAT
3844                           G1PPRL_BYTE_FORMAT
3845                           G1PPRL_BYTE_FORMAT,
3846                           type, p2i(bottom), p2i(end),
3847                           used_bytes, prev_live_bytes, next_live_bytes, gc_eff,
3848                           remset_bytes, strong_code_roots_bytes);
3849 
3850   return false;
3851 }
3852 
3853 G1PrintRegionLivenessInfoClosure::~G1PrintRegionLivenessInfoClosure() {
3854   // add static memory usages to remembered set sizes
3855   _total_remset_bytes += HeapRegionRemSet::fl_mem_size() + HeapRegionRemSet::static_mem_size();
3856   // Print the footer of the output.
3857   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX);
3858   log_trace(gc, liveness)(G1PPRL_LINE_PREFIX
3859                          " SUMMARY"
3860                          G1PPRL_SUM_MB_FORMAT("capacity")
3861                          G1PPRL_SUM_MB_PERC_FORMAT("used")
3862                          G1PPRL_SUM_MB_PERC_FORMAT("prev-live")
3863                          G1PPRL_SUM_MB_PERC_FORMAT("next-live")
3864                          G1PPRL_SUM_MB_FORMAT("remset")
3865                          G1PPRL_SUM_MB_FORMAT("code-roots"),
3866                          bytes_to_mb(_total_capacity_bytes),
3867                          bytes_to_mb(_total_used_bytes),
3868                          perc(_total_used_bytes, _total_capacity_bytes),
3869                          bytes_to_mb(_total_prev_live_bytes),
3870                          perc(_total_prev_live_bytes, _total_capacity_bytes),
3871                          bytes_to_mb(_total_next_live_bytes),
3872                          perc(_total_next_live_bytes, _total_capacity_bytes),
3873                          bytes_to_mb(_total_remset_bytes),
3874                          bytes_to_mb(_total_strong_code_roots_bytes));
3875 }