1 /* 2 * Copyright (c) 2017, Red Hat, Inc. and/or its affiliates. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. 7 * 8 * This code is distributed in the hope that it will be useful, but WITHOUT 9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 11 * version 2 for more details (a copy is included in the LICENSE file that 12 * accompanied this code). 13 * 14 * You should have received a copy of the GNU General Public License version 15 * 2 along with this work; if not, write to the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 17 * 18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 19 * or visit www.oracle.com if you need additional information or have any 20 * questions. 21 * 22 */ 23 24 #include "precompiled.hpp" 25 26 #include "gc/shared/gcTraceTime.inline.hpp" 27 #include "gc/shared/workgroup.hpp" 28 #include "gc/shared/taskqueue.inline.hpp" 29 #include "gc/shenandoah/shenandoahBarrierSet.hpp" 30 #include "gc/shenandoah/shenandoahCollectionSet.hpp" 31 #include "gc/shenandoah/shenandoahCollectorPolicy.hpp" 32 #include "gc/shenandoah/shenandoahConnectionMatrix.inline.hpp" 33 #include "gc/shenandoah/shenandoahFreeSet.hpp" 34 #include "gc/shenandoah/shenandoahPhaseTimings.hpp" 35 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp" 36 #include "gc/shenandoah/shenandoahHeap.hpp" 37 #include "gc/shenandoah/shenandoahHeap.inline.hpp" 38 #include "gc/shenandoah/shenandoahOopClosures.inline.hpp" 39 #include "gc/shenandoah/shenandoahPartialGC.hpp" 40 #include "gc/shenandoah/shenandoahRootProcessor.hpp" 41 #include "gc/shenandoah/shenandoahStringDedup.hpp" 42 #include "gc/shenandoah/shenandoahTaskqueue.hpp" 43 #include "gc/shenandoah/shenandoahUtils.hpp" 44 #include "gc/shenandoah/shenandoahVerifier.hpp" 45 #include "gc/shenandoah/shenandoahWorkGroup.hpp" 46 #include "gc/shenandoah/shenandoahWorkerPolicy.hpp" 47 48 #include "memory/iterator.hpp" 49 #include "runtime/safepoint.hpp" 50 51 class ShenandoahPartialEvacuateUpdateRootsClosure : public OopClosure { 52 ShenandoahPartialGC* _partial_gc; 53 Thread* _thread; 54 ShenandoahObjToScanQueue* _queue; 55 private: 56 template <class T> 57 void do_oop_work(T* p) { _partial_gc->process_oop<T, false>(p, _thread, _queue); } 58 public: 59 ShenandoahPartialEvacuateUpdateRootsClosure(ShenandoahObjToScanQueue* q) : 60 _partial_gc(ShenandoahHeap::heap()->partial_gc()), 61 _thread(Thread::current()), _queue(q) {} 62 void do_oop(oop* p) { 63 assert(! ShenandoahHeap::heap()->is_in_reserved(p), "sanity"); 64 do_oop_work(p); 65 } 66 void do_oop(narrowOop* p) { do_oop_work(p); } 67 }; 68 69 class ShenandoahPartialSATBBufferClosure : public SATBBufferClosure { 70 private: 71 ShenandoahObjToScanQueue* _queue; 72 ShenandoahPartialGC* _partial_gc; 73 Thread* _thread; 74 public: 75 ShenandoahPartialSATBBufferClosure(ShenandoahObjToScanQueue* q) : 76 _queue(q), _partial_gc(ShenandoahHeap::heap()->partial_gc()), _thread(Thread::current()) { } 77 78 void do_buffer(void** buffer, size_t size) { 79 for (size_t i = 0; i < size; ++i) { 80 oop* p = (oop*) &buffer[i]; 81 oop obj = oopDesc::load_heap_oop(p); 82 _queue->push(obj); 83 } 84 } 85 }; 86 87 class ShenandoahPartialSATBThreadsClosure : public ThreadClosure { 88 ShenandoahPartialSATBBufferClosure* _satb_cl; 89 int _thread_parity; 90 91 public: 92 ShenandoahPartialSATBThreadsClosure(ShenandoahPartialSATBBufferClosure* satb_cl) : 93 _satb_cl(satb_cl), 94 _thread_parity(Threads::thread_claim_parity()) {} 95 96 void do_thread(Thread* thread) { 97 if (thread->is_Java_thread()) { 98 if (thread->claim_oops_do(true, _thread_parity)) { 99 JavaThread* jt = (JavaThread*)thread; 100 jt->satb_mark_queue().apply_closure_and_empty(_satb_cl); 101 } 102 } else if (thread->is_VM_thread()) { 103 if (thread->claim_oops_do(true, _thread_parity)) { 104 JavaThread::satb_mark_queue_set().shared_satb_queue()->apply_closure_and_empty(_satb_cl); 105 } 106 } 107 } 108 }; 109 110 class ShenandoahInitPartialCollectionTask : public AbstractGangTask { 111 private: 112 ShenandoahRootProcessor* _rp; 113 ShenandoahHeap* _heap; 114 public: 115 ShenandoahInitPartialCollectionTask(ShenandoahRootProcessor* rp) : 116 AbstractGangTask("Shenandoah Init Partial Collection"), 117 _rp(rp), 118 _heap(ShenandoahHeap::heap()) {} 119 120 void work(uint worker_id) { 121 ShenandoahObjToScanQueueSet* queues = _heap->partial_gc()->task_queues(); 122 ShenandoahObjToScanQueue* q = queues->queue(worker_id); 123 124 // Step 1: Process ordinary GC roots. 125 { 126 ShenandoahPartialEvacuateUpdateRootsClosure roots_cl(q); 127 CLDToOopClosure cld_cl(&roots_cl); 128 MarkingCodeBlobClosure code_cl(&roots_cl, CodeBlobToOopClosure::FixRelocations); 129 _rp->process_all_roots(&roots_cl, &roots_cl, &cld_cl, &code_cl, worker_id); 130 } 131 } 132 }; 133 134 class ShenandoahConcurrentPartialCollectionTask : public AbstractGangTask { 135 private: 136 ParallelTaskTerminator* _terminator; 137 ShenandoahHeapRegionSet* _root_regions; 138 ShenandoahHeap* _heap; 139 public: 140 ShenandoahConcurrentPartialCollectionTask(ParallelTaskTerminator* terminator, 141 ShenandoahHeapRegionSet* root_regions) : 142 AbstractGangTask("Shenandoah Concurrent Partial Collection"), 143 _terminator(terminator), _root_regions(root_regions), 144 _heap(ShenandoahHeap::heap()) {} 145 146 void work(uint worker_id) { 147 ShenandoahPartialGC* partial_gc = _heap->partial_gc(); 148 ShenandoahObjToScanQueueSet* queues = partial_gc->task_queues(); 149 ShenandoahObjToScanQueue* q = queues->queue(worker_id); 150 151 if (partial_gc->check_and_handle_cancelled_gc(_terminator)) return; 152 153 ShenandoahPartialEvacuateUpdateHeapClosure cl(q); 154 155 // Step 2: Process all root regions. 156 { 157 ShenandoahHeapRegion* r = _root_regions->claim_next(); 158 while (r != NULL) { 159 assert(r->is_root(), "must be root region"); 160 _heap->marked_object_oop_safe_iterate(r, &cl); 161 if (partial_gc->check_and_handle_cancelled_gc(_terminator)) return; 162 r = _root_regions->claim_next(); 163 } 164 } 165 if (partial_gc->check_and_handle_cancelled_gc(_terminator)) return; 166 167 // Step 3: Drain all outstanding work in queues. 168 partial_gc->main_loop<true>(worker_id, _terminator); 169 } 170 }; 171 172 class ShenandoahFinalPartialCollectionTask : public AbstractGangTask { 173 private: 174 ParallelTaskTerminator* _terminator; 175 ShenandoahHeap* _heap; 176 public: 177 ShenandoahFinalPartialCollectionTask(ParallelTaskTerminator* terminator) : 178 AbstractGangTask("Shenandoah Final Partial Collection"), 179 _terminator(terminator), 180 _heap(ShenandoahHeap::heap()) {} 181 182 void work(uint worker_id) { 183 ShenandoahPartialGC* partial_gc = _heap->partial_gc(); 184 185 ShenandoahObjToScanQueueSet* queues = partial_gc->task_queues(); 186 ShenandoahObjToScanQueue* q = queues->queue(worker_id); 187 188 // Drain outstanding SATB queues. 189 { 190 ShenandoahPartialSATBBufferClosure satb_cl(q); 191 // Process remaining finished SATB buffers. 192 SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set(); 193 while (satb_mq_set.apply_closure_to_completed_buffer(&satb_cl)); 194 // Process remaining threads SATB buffers. 195 ShenandoahPartialSATBThreadsClosure tc(&satb_cl); 196 Threads::threads_do(&tc); 197 } 198 199 // Finally drain all outstanding work in queues. 200 partial_gc->main_loop<false>(worker_id, _terminator); 201 202 } 203 }; 204 205 class ShenandoahPartialCollectionCleanupTask : public AbstractGangTask { 206 private: 207 ShenandoahHeap* _heap; 208 public: 209 ShenandoahPartialCollectionCleanupTask() : 210 AbstractGangTask("Shenandoah Partial Collection Cleanup"), 211 _heap(ShenandoahHeap::heap()) { 212 _heap->collection_set()->clear_current_index(); 213 } 214 215 void work(uint worker_id) { 216 ShenandoahCollectionSet* cset = _heap->collection_set(); 217 ShenandoahHeapRegion* r = cset->claim_next(); 218 while (r != NULL) { 219 HeapWord* bottom = r->bottom(); 220 HeapWord* top = _heap->complete_top_at_mark_start(r->bottom()); 221 if (top > bottom) { 222 _heap->complete_mark_bit_map()->clear_range_large(MemRegion(bottom, top)); 223 } 224 r = cset->claim_next(); 225 } 226 } 227 228 }; 229 230 ShenandoahPartialGC::ShenandoahPartialGC(ShenandoahHeap* heap, size_t num_regions) : 231 _heap(heap), 232 _matrix(heap->connection_matrix()), 233 _root_regions(new ShenandoahHeapRegionSet(num_regions)), 234 _task_queues(new ShenandoahObjToScanQueueSet(heap->max_workers())), 235 _has_work(false) { 236 237 assert(_matrix != NULL, "need matrix"); 238 239 uint num_queues = heap->max_workers(); 240 for (uint i = 0; i < num_queues; ++i) { 241 ShenandoahObjToScanQueue* task_queue = new ShenandoahObjToScanQueue(); 242 task_queue->initialize(); 243 _task_queues->register_queue(i, task_queue); 244 } 245 246 from_idxs = NEW_C_HEAP_ARRAY(size_t, ShenandoahPartialInboundThreshold, mtGC); 247 } 248 249 ShenandoahPartialGC::~ShenandoahPartialGC() { 250 FREE_C_HEAP_ARRAY(size_t, from_idxs); 251 } 252 253 bool ShenandoahPartialGC::prepare() { 254 _heap->collection_set()->clear(); 255 assert(_heap->collection_set()->count() == 0, "collection set not clear"); 256 257 _heap->ensure_parsability(true); 258 259 ShenandoahConnectionMatrix* matrix = _heap->connection_matrix(); 260 261 if (UseShenandoahMatrix && PrintShenandoahMatrix) { 262 LogTarget(Info, gc) lt; 263 LogStream ls(lt); 264 _heap->connection_matrix()->print_on(&ls); 265 } 266 267 ShenandoahHeapRegionSet* regions = _heap->regions(); 268 ShenandoahCollectionSet* collection_set = _heap->collection_set(); 269 size_t num_regions = _heap->num_regions(); 270 271 // First pass: reset all roots 272 for (uint to_idx = 0; to_idx < num_regions; to_idx++) { 273 ShenandoahHeapRegion* r = regions->get(to_idx); 274 r->set_root(false); 275 } 276 277 // Second pass: find collection set, and mark root candidates 278 _heap->shenandoahPolicy()->choose_collection_set(collection_set, true); 279 280 // Shortcut: no cset, bail 281 size_t num_cset = collection_set->count(); 282 283 if (num_cset == 0) { 284 log_info(gc, ergo)("No regions with fewer inbound connections than threshold (" UINTX_FORMAT ")", 285 ShenandoahPartialInboundThreshold); 286 return false; 287 } 288 289 // Final pass: rebuild free set and region set. 290 ShenandoahFreeSet* _free_regions = _heap->free_regions(); 291 _root_regions->clear(); 292 _free_regions->clear(); 293 294 assert(_root_regions->count() == 0, "must be cleared"); 295 296 for (uint from_idx = 0; from_idx < num_regions; from_idx++) { 297 ShenandoahHeapRegion* r = regions->get(from_idx); 298 if (r->is_alloc_allowed()) { 299 _free_regions->add_region(r); 300 } 301 if (r->is_root() && !r->in_collection_set()) { 302 _root_regions->add_region(r); 303 matrix->clear_region_outbound(from_idx); 304 305 // Since root region can be allocated at, we should bound the scans 306 // in it at current top. Otherwise, one thread may evacuate objects 307 // to that root region, while another would try to scan newly evac'ed 308 // objects under the race. 309 r->set_concurrent_iteration_safe_limit(r->top()); 310 } 311 } 312 313 log_info(gc,ergo)("Got "SIZE_FORMAT" collection set regions, "SIZE_FORMAT" root regions", 314 collection_set->count(), _root_regions->count()); 315 316 return true; 317 } 318 319 void ShenandoahPartialGC::init_partial_collection() { 320 assert(SafepointSynchronize::is_at_safepoint(), "STW partial GC"); 321 ShenandoahWorkerScope partial_gc_scope(_heap->workers(), ShenandoahWorkerPolicy::calc_workers_for_stw_partial()); 322 323 _heap->set_alloc_seq_gc_start(); 324 325 ShenandoahGCSession session; 326 327 GCTraceTime(Info, gc) time("Pause Init Partial", _heap->gc_timer(), GCCause::_no_gc, true); 328 329 _heap->set_concurrent_partial_in_progress(true); 330 331 if (ShenandoahVerify) { 332 _heap->verifier()->verify_before_partial(); 333 } 334 335 { 336 ShenandoahGCPhase phase_prepare(ShenandoahPhaseTimings::partial_gc_prepare); 337 ShenandoahHeapLocker lock(_heap->lock()); 338 _has_work = prepare(); 339 } 340 341 if (!_has_work) { 342 reset(); 343 return; 344 } 345 346 { 347 ShenandoahGCPhase phase_work(ShenandoahPhaseTimings::init_partial_gc_work); 348 assert(_task_queues->is_empty(), "queues must be empty after partial GC"); 349 350 #if defined(COMPILER2) || INCLUDE_JVMCI 351 DerivedPointerTable::clear(); 352 #endif 353 354 { 355 uint nworkers = _heap->workers()->active_workers(); 356 ShenandoahRootProcessor rp(_heap, nworkers, ShenandoahPhaseTimings::init_partial_gc_work); 357 358 if (UseShenandoahOWST) { 359 ShenandoahTaskTerminator terminator(nworkers, task_queues()); 360 ShenandoahInitPartialCollectionTask partial_task(&rp); 361 _heap->workers()->run_task(&partial_task); 362 } else { 363 ParallelTaskTerminator terminator(nworkers, task_queues()); 364 ShenandoahInitPartialCollectionTask partial_task(&rp); 365 _heap->workers()->run_task(&partial_task); 366 } 367 } 368 369 #if defined(COMPILER2) || INCLUDE_JVMCI 370 DerivedPointerTable::update_pointers(); 371 #endif 372 if (_heap->cancelled_concgc()) { 373 _task_queues->clear(); 374 } 375 } 376 } 377 378 template <bool DO_SATB> 379 void ShenandoahPartialGC::main_loop(uint worker_id, ParallelTaskTerminator* terminator) { 380 ShenandoahObjToScanQueueSet* queues = task_queues(); 381 ShenandoahObjToScanQueue* q = queues->queue(worker_id); 382 383 uintx stride = ShenandoahMarkLoopStride; 384 ShenandoahPartialEvacuateUpdateHeapClosure cl(q); 385 ShenandoahMarkTask task; 386 387 // Process outstanding queues, if any. 388 q = queues->claim_next(); 389 while (q != NULL) { 390 if (_heap->check_cancelled_concgc_and_yield()) { 391 ShenandoahCancelledTerminatorTerminator tt; 392 while (!terminator->offer_termination(&tt)); 393 return; 394 } 395 396 for (uint i = 0; i < stride; i++) { 397 if (q->pop_buffer(task) || 398 q->pop_local(task) || 399 q->pop_overflow(task)) { 400 oop obj = task.obj(); 401 assert(!oopDesc::is_null(obj), "must not be null"); 402 obj->oop_iterate(&cl); 403 } else { 404 assert(q->is_empty(), "Must be empty"); 405 q = queues->claim_next(); 406 break; 407 } 408 } 409 } 410 411 // Normal loop. 412 q = queues->queue(worker_id); 413 ShenandoahPartialSATBBufferClosure satb_cl(q); 414 SATBMarkQueueSet& satb_mq_set = JavaThread::satb_mark_queue_set(); 415 416 int seed = 17; 417 418 while (true) { 419 if (check_and_handle_cancelled_gc(terminator)) return; 420 421 for (uint i = 0; i < stride; i++) { 422 if ((q->pop_buffer(task) || 423 q->pop_local(task) || 424 q->pop_overflow(task) || 425 (DO_SATB && satb_mq_set.apply_closure_to_completed_buffer(&satb_cl) && q->pop_buffer(task)) || 426 queues->steal(worker_id, &seed, task))) { 427 oop obj = task.obj(); 428 assert(!oopDesc::is_null(obj), "must not be null"); 429 obj->oop_iterate(&cl); 430 } else { 431 if (terminator->offer_termination()) return; 432 } 433 } 434 } 435 } 436 437 bool ShenandoahPartialGC::check_and_handle_cancelled_gc(ParallelTaskTerminator* terminator) { 438 if (_heap->cancelled_concgc()) { 439 ShenandoahCancelledTerminatorTerminator tt; 440 while (! terminator->offer_termination(&tt)); 441 return true; 442 } 443 return false; 444 } 445 446 void ShenandoahPartialGC::concurrent_partial_collection() { 447 448 ShenandoahWorkerScope partial_gc_scope(_heap->workers(), ShenandoahWorkerPolicy::calc_workers_for_conc_partial()); 449 450 ShenandoahGCPhase phase_work(ShenandoahPhaseTimings::conc_partial); 451 if (_has_work && !_heap->cancelled_concgc()) { 452 uint nworkers = _heap->workers()->active_workers(); 453 task_queues()->reserve(nworkers); 454 if (UseShenandoahOWST) { 455 ShenandoahTaskTerminator terminator(nworkers, task_queues()); 456 ShenandoahConcurrentPartialCollectionTask partial_task(&terminator, _root_regions); 457 _heap->workers()->run_task(&partial_task); 458 } else { 459 ParallelTaskTerminator terminator(nworkers, task_queues()); 460 ShenandoahConcurrentPartialCollectionTask partial_task(&terminator, _root_regions); 461 _heap->workers()->run_task(&partial_task); 462 } 463 } 464 465 if (_heap->cancelled_concgc()) { 466 _task_queues->clear(); 467 } 468 assert(_task_queues->is_empty(), "queues must be empty after partial GC"); 469 } 470 471 void ShenandoahPartialGC::final_partial_collection() { 472 ShenandoahWorkerScope partial_gc_scope(_heap->workers(), ShenandoahWorkerPolicy::calc_workers_for_stw_partial()); 473 ShenandoahGCSession session; 474 GCTraceTime(Info, gc) time("Pause Final Partial", _heap->gc_timer(), GCCause::_no_gc, true); 475 if (_has_work && ! _heap->cancelled_concgc()) { 476 { 477 ShenandoahGCPhase phase_work(ShenandoahPhaseTimings::final_partial_gc_work); 478 uint nworkers = _heap->workers()->active_workers(); 479 task_queues()->reserve(nworkers); 480 481 StrongRootsScope scope(nworkers); 482 if (UseShenandoahOWST) { 483 ShenandoahTaskTerminator terminator(nworkers, task_queues()); 484 ShenandoahFinalPartialCollectionTask partial_task(&terminator); 485 _heap->workers()->run_task(&partial_task); 486 } else { 487 ParallelTaskTerminator terminator(nworkers, task_queues()); 488 ShenandoahFinalPartialCollectionTask partial_task(&terminator); 489 _heap->workers()->run_task(&partial_task); 490 } 491 492 if (_heap->cancelled_concgc()) { 493 _task_queues->clear(); 494 } 495 assert(_task_queues->is_empty(), "queues must be empty after partial GC"); 496 } 497 _heap->concurrentMark()->update_roots(ShenandoahPhaseTimings::full_gc_roots); 498 499 if (ShenandoahStringDedup::is_enabled()) { 500 ShenandoahGCPhase update_str_dedup_table(ShenandoahPhaseTimings::partial_gc_update_str_dedup_table); 501 ShenandoahStringDedup::parallel_partial_update_or_unlink(); 502 } 503 504 { 505 ShenandoahGCPhase phase_recycle(ShenandoahPhaseTimings::partial_gc_recycle); 506 507 ShenandoahCollectionSet* cset = _heap->collection_set(); 508 509 { 510 ShenandoahHeapLocker lock(_heap->lock()); 511 512 ShenandoahPartialCollectionCleanupTask cleanup; 513 _heap->workers()->run_task(&cleanup); 514 515 // Trash everything when bitmaps are cleared. 516 cset->clear_current_index(); 517 ShenandoahHeapRegion* r; 518 while((r = cset->next()) != NULL) { 519 r->make_trash(); 520 } 521 522 reset(); 523 } 524 } 525 526 if (ShenandoahVerify && ! _heap->cancelled_concgc()) { 527 _heap->verifier()->verify_after_partial(); 528 } 529 } else { 530 // Fixup roots to make them consistent 531 _heap->fixup_roots(); 532 } 533 534 _heap->set_concurrent_partial_in_progress(false); 535 536 } 537 538 void ShenandoahPartialGC::reset() { 539 _heap->collection_set()->clear(); 540 541 _root_regions->clear_current_index(); 542 ShenandoahHeapRegion* r; 543 while((r = _root_regions->claim_next()) != NULL) { 544 r->set_root(false); 545 } 546 _root_regions->clear(); 547 } 548 549 ShenandoahObjToScanQueueSet* ShenandoahPartialGC::task_queues() { 550 return _task_queues; 551 }