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