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