1 /* 2 * Copyright (c) 2015, 2018, 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 #include "precompiled.hpp" 25 #include "gc/z/zBarrier.inline.hpp" 26 #include "gc/z/zMark.inline.hpp" 27 #include "gc/z/zMarkCache.inline.hpp" 28 #include "gc/z/zMarkStack.inline.hpp" 29 #include "gc/z/zMarkTerminate.inline.hpp" 30 #include "gc/z/zOopClosures.inline.hpp" 31 #include "gc/z/zPage.hpp" 32 #include "gc/z/zPageTable.inline.hpp" 33 #include "gc/z/zRootsIterator.hpp" 34 #include "gc/z/zStat.hpp" 35 #include "gc/z/zTask.hpp" 36 #include "gc/z/zThread.hpp" 37 #include "gc/z/zUtils.inline.hpp" 38 #include "gc/z/zWorkers.inline.hpp" 39 #include "logging/log.hpp" 40 #include "memory/iterator.inline.hpp" 41 #include "oops/objArrayOop.inline.hpp" 42 #include "oops/oop.inline.hpp" 43 #include "runtime/atomic.hpp" 44 #include "runtime/handshake.hpp" 45 #include "runtime/orderAccess.hpp" 46 #include "runtime/prefetch.inline.hpp" 47 #include "runtime/thread.hpp" 48 #include "utilities/align.hpp" 49 #include "utilities/globalDefinitions.hpp" 50 #include "utilities/ticks.hpp" 51 52 static const ZStatSubPhase ZSubPhaseConcurrentMark("Concurrent Mark"); 53 static const ZStatSubPhase ZSubPhaseConcurrentMarkTryFlush("Concurrent Mark Try Flush"); 54 static const ZStatSubPhase ZSubPhaseConcurrentMarkIdle("Concurrent Mark Idle"); 55 static const ZStatSubPhase ZSubPhaseConcurrentMarkTryTerminate("Concurrent Mark Try Terminate"); 56 static const ZStatSubPhase ZSubPhaseMarkTryComplete("Pause Mark Try Complete"); 57 58 ZMark::ZMark(ZWorkers* workers, ZPageTable* pagetable) : 59 _workers(workers), 60 _pagetable(pagetable), 61 _allocator(), 62 _stripes(), 63 _terminate(), 64 _work_terminateflush(true), 65 _work_nproactiveflush(0), 66 _work_nterminateflush(0), 67 _nproactiveflush(0), 68 _nterminateflush(0), 69 _ntrycomplete(0), 70 _ncontinue(0), 71 _nworkers(0) {} 72 73 bool ZMark::is_initialized() const { 74 return _allocator.is_initialized(); 75 } 76 77 size_t ZMark::calculate_nstripes(uint nworkers) const { 78 // Calculate the number of stripes from the number of workers we use, 79 // where the number of stripes must be a power of two and we want to 80 // have at least one worker per stripe. 81 const size_t nstripes = ZUtils::round_down_power_of_2(nworkers); 82 return MIN2(nstripes, ZMarkStripesMax); 83 } 84 85 void ZMark::prepare_mark() { 86 // Increment global sequence number to invalidate 87 // marking information for all pages. 88 ZGlobalSeqNum++; 89 90 // Reset flush/continue counters 91 _nproactiveflush = 0; 92 _nterminateflush = 0; 93 _ntrycomplete = 0; 94 _ncontinue = 0; 95 96 // Set number of workers to use 97 _nworkers = _workers->nconcurrent(); 98 99 // Set number of mark stripes to use, based on number 100 // of workers we will use in the concurrent mark phase. 101 const size_t nstripes = calculate_nstripes(_nworkers); 102 _stripes.set_nstripes(nstripes); 103 104 // Update statistics 105 ZStatMark::set_at_mark_start(nstripes); 106 107 // Print worker/stripe distribution 108 LogTarget(Debug, gc, marking) log; 109 if (log.is_enabled()) { 110 log.print("Mark Worker/Stripe Distribution"); 111 for (uint worker_id = 0; worker_id < _nworkers; worker_id++) { 112 const ZMarkStripe* const stripe = _stripes.stripe_for_worker(_nworkers, worker_id); 113 const size_t stripe_id = _stripes.stripe_id(stripe); 114 log.print(" Worker %u(%u) -> Stripe " SIZE_FORMAT "(" SIZE_FORMAT ")", 115 worker_id, _nworkers, stripe_id, nstripes); 116 } 117 } 118 } 119 120 class ZMarkRootsTask : public ZTask { 121 private: 122 ZMark* const _mark; 123 ZRootsIterator _roots; 124 125 public: 126 ZMarkRootsTask(ZMark* mark) : 127 ZTask("ZMarkRootsTask"), 128 _mark(mark), 129 _roots() {} 130 131 virtual void work() { 132 ZMarkRootOopClosure cl; 133 _roots.oops_do(&cl); 134 135 // Flush and free worker stacks. Needed here since 136 // the set of workers executing during root scanning 137 // can be different from the set of workers executing 138 // during mark. 139 _mark->flush_and_free(); 140 } 141 }; 142 143 void ZMark::start() { 144 // Verification 145 if (ZVerifyMarking) { 146 verify_all_stacks_empty(); 147 } 148 149 // Prepare for concurrent mark 150 prepare_mark(); 151 152 // Mark roots 153 ZMarkRootsTask task(this); 154 _workers->run_parallel(&task); 155 } 156 157 void ZMark::prepare_work() { 158 assert(_nworkers == _workers->nconcurrent(), "Invalid number of workers"); 159 160 // Set number of active workers 161 _terminate.reset(_nworkers); 162 163 // Reset flush counters 164 _work_nproactiveflush = _work_nterminateflush = 0; 165 _work_terminateflush = true; 166 } 167 168 void ZMark::finish_work() { 169 // Accumulate proactive/terminate flush counters 170 _nproactiveflush += _work_nproactiveflush; 171 _nterminateflush += _work_nterminateflush; 172 } 173 174 bool ZMark::is_array(uintptr_t addr) const { 175 return ZOop::to_oop(addr)->is_objArray(); 176 } 177 178 void ZMark::push_partial_array(uintptr_t addr, size_t size, bool finalizable) { 179 assert(is_aligned(addr, ZMarkPartialArrayMinSize), "Address misaligned"); 180 ZMarkThreadLocalStacks* const stacks = ZThreadLocalData::stacks(Thread::current()); 181 ZMarkStripe* const stripe = _stripes.stripe_for_addr(addr); 182 const uintptr_t offset = ZAddress::offset(addr) >> ZMarkPartialArrayMinSizeShift; 183 const uintptr_t length = size / oopSize; 184 const ZMarkStackEntry entry(offset, length, finalizable); 185 186 log_develop_trace(gc, marking)("Array push partial: " PTR_FORMAT " (" SIZE_FORMAT "), stripe: " SIZE_FORMAT, 187 addr, size, _stripes.stripe_id(stripe)); 188 189 stacks->push(&_allocator, &_stripes, stripe, entry, false /* publish */); 190 } 191 192 void ZMark::follow_small_array(uintptr_t addr, size_t size, bool finalizable) { 193 assert(size <= ZMarkPartialArrayMinSize, "Too large, should be split"); 194 const size_t length = size / oopSize; 195 196 log_develop_trace(gc, marking)("Array follow small: " PTR_FORMAT " (" SIZE_FORMAT ")", addr, size); 197 198 ZBarrier::mark_barrier_on_oop_array((oop*)addr, length, finalizable); 199 } 200 201 void ZMark::follow_large_array(uintptr_t addr, size_t size, bool finalizable) { 202 assert(size <= (size_t)arrayOopDesc::max_array_length(T_OBJECT) * oopSize, "Too large"); 203 assert(size > ZMarkPartialArrayMinSize, "Too small, should not be split"); 204 const uintptr_t start = addr; 205 const uintptr_t end = start + size; 206 207 // Calculate the aligned middle start/end/size, where the middle start 208 // should always be greater than the start (hence the +1 below) to make 209 // sure we always do some follow work, not just split the array into pieces. 210 const uintptr_t middle_start = align_up(start + 1, ZMarkPartialArrayMinSize); 211 const size_t middle_size = align_down(end - middle_start, ZMarkPartialArrayMinSize); 212 const uintptr_t middle_end = middle_start + middle_size; 213 214 log_develop_trace(gc, marking)("Array follow large: " PTR_FORMAT "-" PTR_FORMAT" (" SIZE_FORMAT "), " 215 "middle: " PTR_FORMAT "-" PTR_FORMAT " (" SIZE_FORMAT ")", 216 start, end, size, middle_start, middle_end, middle_size); 217 218 // Push unaligned trailing part 219 if (end > middle_end) { 220 const uintptr_t trailing_addr = middle_end; 221 const size_t trailing_size = end - middle_end; 222 push_partial_array(trailing_addr, trailing_size, finalizable); 223 } 224 225 // Push aligned middle part(s) 226 uintptr_t partial_addr = middle_end; 227 while (partial_addr > middle_start) { 228 const size_t parts = 2; 229 const size_t partial_size = align_up((partial_addr - middle_start) / parts, ZMarkPartialArrayMinSize); 230 partial_addr -= partial_size; 231 push_partial_array(partial_addr, partial_size, finalizable); 232 } 233 234 // Follow leading part 235 assert(start < middle_start, "Miscalculated middle start"); 236 const uintptr_t leading_addr = start; 237 const size_t leading_size = middle_start - start; 238 follow_small_array(leading_addr, leading_size, finalizable); 239 } 240 241 void ZMark::follow_array(uintptr_t addr, size_t size, bool finalizable) { 242 if (size <= ZMarkPartialArrayMinSize) { 243 follow_small_array(addr, size, finalizable); 244 } else { 245 follow_large_array(addr, size, finalizable); 246 } 247 } 248 249 void ZMark::follow_partial_array(ZMarkStackEntry entry, bool finalizable) { 250 const uintptr_t addr = ZAddress::good(entry.partial_array_offset() << ZMarkPartialArrayMinSizeShift); 251 const size_t size = entry.partial_array_length() * oopSize; 252 253 follow_array(addr, size, finalizable); 254 } 255 256 void ZMark::follow_array_object(objArrayOop obj, bool finalizable) { 257 const uintptr_t addr = (uintptr_t)obj->base(); 258 const size_t size = (size_t)obj->length() * oopSize; 259 260 follow_array(addr, size, finalizable); 261 } 262 263 void ZMark::follow_object(oop obj, bool finalizable) { 264 if (finalizable) { 265 ZMarkBarrierOopClosure<true /* finalizable */> cl; 266 obj->oop_iterate(&cl); 267 } else { 268 ZMarkBarrierOopClosure<false /* finalizable */> cl; 269 obj->oop_iterate(&cl); 270 } 271 } 272 273 bool ZMark::try_mark_object(ZMarkCache* cache, uintptr_t addr, bool finalizable) { 274 ZPage* const page = _pagetable->get(addr); 275 if (page->is_allocating()) { 276 // Newly allocated objects are implicitly marked 277 return false; 278 } 279 280 // Try mark object 281 bool inc_live = false; 282 const bool success = page->mark_object(addr, finalizable, inc_live); 283 if (inc_live) { 284 // Update live objects/bytes for page. We use the aligned object 285 // size since that is the actual number of bytes used on the page 286 // and alignment paddings can never be reclaimed. 287 const size_t size = ZUtils::object_size(addr); 288 const size_t aligned_size = align_up(size, page->object_alignment()); 289 cache->inc_live(page, aligned_size); 290 } 291 292 return success; 293 } 294 295 void ZMark::mark_and_follow(ZMarkCache* cache, ZMarkStackEntry entry) { 296 // Decode flags 297 const bool finalizable = entry.finalizable(); 298 const bool partial_array = entry.partial_array(); 299 300 if (partial_array) { 301 follow_partial_array(entry, finalizable); 302 return; 303 } 304 305 // Decode object address 306 const uintptr_t addr = entry.object_address(); 307 308 if (!try_mark_object(cache, addr, finalizable)) { 309 // Already marked 310 return; 311 } 312 313 if (is_array(addr)) { 314 follow_array_object(objArrayOop(ZOop::to_oop(addr)), finalizable); 315 } else { 316 follow_object(ZOop::to_oop(addr), finalizable); 317 } 318 } 319 320 template <typename T> 321 bool ZMark::drain(ZMarkStripe* stripe, ZMarkThreadLocalStacks* stacks, ZMarkCache* cache, T* timeout) { 322 ZMarkStackEntry entry; 323 324 // Drain stripe stacks 325 while (stacks->pop(&_allocator, &_stripes, stripe, entry)) { 326 mark_and_follow(cache, entry); 327 328 // Check timeout 329 if (timeout->has_expired()) { 330 // Timeout 331 return false; 332 } 333 } 334 335 // Success 336 return true; 337 } 338 339 template <typename T> 340 bool ZMark::drain_and_flush(ZMarkStripe* stripe, ZMarkThreadLocalStacks* stacks, ZMarkCache* cache, T* timeout) { 341 const bool success = drain(stripe, stacks, cache, timeout); 342 343 // Flush and publish worker stacks 344 stacks->flush(&_allocator, &_stripes); 345 346 return success; 347 } 348 349 bool ZMark::try_steal(ZMarkStripe* stripe, ZMarkThreadLocalStacks* stacks) { 350 // Try to steal a stack from another stripe 351 for (ZMarkStripe* victim_stripe = _stripes.stripe_next(stripe); 352 victim_stripe != stripe; 353 victim_stripe = _stripes.stripe_next(victim_stripe)) { 354 ZMarkStack* const stack = victim_stripe->steal_stack(); 355 if (stack != NULL) { 356 // Success, install the stolen stack 357 stacks->install(&_stripes, stripe, stack); 358 return true; 359 } 360 } 361 362 // Nothing to steal 363 return false; 364 } 365 366 void ZMark::idle() const { 367 ZStatTimer timer(ZSubPhaseConcurrentMarkIdle); 368 os::naked_short_sleep(1); 369 } 370 371 class ZMarkFlushAndFreeStacksClosure : public ThreadClosure { 372 private: 373 ZMark* const _mark; 374 bool _flushed; 375 376 public: 377 ZMarkFlushAndFreeStacksClosure(ZMark* mark) : 378 _mark(mark), 379 _flushed(false) {} 380 381 void do_thread(Thread* thread) { 382 if (_mark->flush_and_free(thread)) { 383 _flushed = true; 384 } 385 } 386 387 bool flushed() const { 388 return _flushed; 389 } 390 }; 391 392 bool ZMark::flush(bool at_safepoint) { 393 ZMarkFlushAndFreeStacksClosure cl(this); 394 if (at_safepoint) { 395 Threads::threads_do(&cl); 396 } else { 397 Handshake::execute(&cl); 398 } 399 400 // Returns true if more work is available 401 return cl.flushed() || !_stripes.is_empty(); 402 } 403 404 bool ZMark::try_flush(volatile size_t* nflush) { 405 // Only flush if handshakes are enabled 406 if (!ThreadLocalHandshakes) { 407 return false; 408 } 409 410 Atomic::inc(nflush); 411 412 ZStatTimer timer(ZSubPhaseConcurrentMarkTryFlush); 413 return flush(false /* at_safepoint */); 414 } 415 416 bool ZMark::try_proactive_flush() { 417 // Only do proactive flushes from worker 0 418 if (ZThread::worker_id() != 0) { 419 return false; 420 } 421 422 if (Atomic::load(&_work_nproactiveflush) == ZMarkProactiveFlushMax || 423 Atomic::load(&_work_nterminateflush) != 0) { 424 // Limit reached or we're trying to terminate 425 return false; 426 } 427 428 return try_flush(&_work_nproactiveflush); 429 } 430 431 bool ZMark::try_terminate() { 432 ZStatTimer timer(ZSubPhaseConcurrentMarkTryTerminate); 433 434 if (_terminate.enter_stage0()) { 435 // Last thread entered stage 0, flush 436 if (Atomic::load(&_work_terminateflush) && 437 Atomic::load(&_work_nterminateflush) != ZMarkTerminateFlushMax) { 438 // Exit stage 0 to allow other threads to continue marking 439 _terminate.exit_stage0(); 440 441 // Flush before termination 442 if (!try_flush(&_work_nterminateflush)) { 443 // No more work available, skip further flush attempts 444 Atomic::store(false, &_work_terminateflush); 445 } 446 447 // Don't terminate, regardless of whether we successfully 448 // flushed out more work or not. We've already exited 449 // termination stage 0, to allow other threads to continue 450 // marking, so this thread has to return false and also 451 // make another round of attempted marking. 452 return false; 453 } 454 } 455 456 for (;;) { 457 if (_terminate.enter_stage1()) { 458 // Last thread entered stage 1, terminate 459 return true; 460 } 461 462 // Idle to give the other threads 463 // a chance to enter termination. 464 idle(); 465 466 if (!_terminate.try_exit_stage1()) { 467 // All workers in stage 1, terminate 468 return true; 469 } 470 471 if (_terminate.try_exit_stage0()) { 472 // More work available, don't terminate 473 return false; 474 } 475 } 476 } 477 478 class ZMarkNoTimeout : public StackObj { 479 public: 480 bool has_expired() { 481 return false; 482 } 483 }; 484 485 void ZMark::work_without_timeout(ZMarkCache* cache, ZMarkStripe* stripe, ZMarkThreadLocalStacks* stacks) { 486 ZStatTimer timer(ZSubPhaseConcurrentMark); 487 ZMarkNoTimeout no_timeout; 488 489 for (;;) { 490 drain_and_flush(stripe, stacks, cache, &no_timeout); 491 492 if (try_steal(stripe, stacks)) { 493 // Stole work 494 continue; 495 } 496 497 if (try_proactive_flush()) { 498 // Work available 499 continue; 500 } 501 502 if (try_terminate()) { 503 // Terminate 504 break; 505 } 506 } 507 } 508 509 class ZMarkTimeout : public StackObj { 510 private: 511 const Ticks _start; 512 const uint64_t _timeout; 513 const uint64_t _check_interval; 514 uint64_t _check_at; 515 uint64_t _check_count; 516 bool _expired; 517 518 public: 519 ZMarkTimeout(uint64_t timeout_in_millis) : 520 _start(Ticks::now()), 521 _timeout(_start.value() + TimeHelper::millis_to_counter(timeout_in_millis)), 522 _check_interval(200), 523 _check_at(_check_interval), 524 _check_count(0), 525 _expired(false) {} 526 527 ~ZMarkTimeout() { 528 const Tickspan duration = Ticks::now() - _start; 529 log_debug(gc, marking)("Mark With Timeout (%s): %s, " UINT64_FORMAT " oops, %.3fms", 530 ZThread::name(), _expired ? "Expired" : "Completed", 531 _check_count, TimeHelper::counter_to_millis(duration.value())); 532 } 533 534 bool has_expired() { 535 if (++_check_count == _check_at) { 536 _check_at += _check_interval; 537 if ((uint64_t)Ticks::now().value() >= _timeout) { 538 // Timeout 539 _expired = true; 540 } 541 } 542 543 return _expired; 544 } 545 }; 546 547 void ZMark::work_with_timeout(ZMarkCache* cache, ZMarkStripe* stripe, ZMarkThreadLocalStacks* stacks, uint64_t timeout_in_millis) { 548 ZStatTimer timer(ZSubPhaseMarkTryComplete); 549 ZMarkTimeout timeout(timeout_in_millis); 550 551 for (;;) { 552 if (!drain_and_flush(stripe, stacks, cache, &timeout)) { 553 // Timed out 554 break; 555 } 556 557 if (try_steal(stripe, stacks)) { 558 // Stole work 559 continue; 560 } 561 562 // Terminate 563 break; 564 } 565 } 566 567 void ZMark::work(uint64_t timeout_in_millis) { 568 ZMarkCache cache(_stripes.nstripes()); 569 ZMarkStripe* const stripe = _stripes.stripe_for_worker(_nworkers, ZThread::worker_id()); 570 ZMarkThreadLocalStacks* const stacks = ZThreadLocalData::stacks(Thread::current()); 571 572 if (timeout_in_millis == 0) { 573 work_without_timeout(&cache, stripe, stacks); 574 } else { 575 work_with_timeout(&cache, stripe, stacks, timeout_in_millis); 576 } 577 578 // Make sure stacks have been flushed 579 assert(stacks->is_empty(&_stripes), "Should be empty"); 580 581 // Free remaining stacks 582 stacks->free(&_allocator); 583 } 584 585 class ZMarkTask : public ZTask { 586 private: 587 ZMark* const _mark; 588 const uint64_t _timeout_in_millis; 589 590 public: 591 ZMarkTask(ZMark* mark, uint64_t timeout_in_millis = 0) : 592 ZTask("ZMarkTask"), 593 _mark(mark), 594 _timeout_in_millis(timeout_in_millis) { 595 _mark->prepare_work(); 596 } 597 598 ~ZMarkTask() { 599 _mark->finish_work(); 600 } 601 602 virtual void work() { 603 _mark->work(_timeout_in_millis); 604 } 605 }; 606 607 void ZMark::mark() { 608 ZMarkTask task(this); 609 _workers->run_concurrent(&task); 610 } 611 612 bool ZMark::try_complete() { 613 _ntrycomplete++; 614 615 // Use nconcurrent number of worker threads to maintain the 616 // worker/stripe distribution used during concurrent mark. 617 ZMarkTask task(this, ZMarkCompleteTimeout); 618 _workers->run_concurrent(&task); 619 620 // Successful if all stripes are empty 621 return _stripes.is_empty(); 622 } 623 624 bool ZMark::try_end() { 625 // Flush all mark stacks 626 if (!flush(true /* at_safepoint */)) { 627 // Mark completed 628 return true; 629 } 630 631 // Try complete marking by doing a limited 632 // amount of mark work in this phase. 633 return try_complete(); 634 } 635 636 bool ZMark::end() { 637 // Try end marking 638 if (!try_end()) { 639 // Mark not completed 640 _ncontinue++; 641 return false; 642 } 643 644 // Verification 645 if (ZVerifyMarking) { 646 verify_all_stacks_empty(); 647 } 648 649 // Update statistics 650 ZStatMark::set_at_mark_end(_nproactiveflush, _nterminateflush, _ntrycomplete, _ncontinue); 651 652 // Mark completed 653 return true; 654 } 655 656 void ZMark::flush_and_free() { 657 Thread* const thread = Thread::current(); 658 flush_and_free(thread); 659 } 660 661 bool ZMark::flush_and_free(Thread* thread) { 662 ZMarkThreadLocalStacks* const stacks = ZThreadLocalData::stacks(thread); 663 const bool flushed = stacks->flush(&_allocator, &_stripes); 664 stacks->free(&_allocator); 665 return flushed; 666 } 667 668 class ZVerifyMarkStacksEmptyClosure : public ThreadClosure { 669 private: 670 const ZMarkStripeSet* const _stripes; 671 672 public: 673 ZVerifyMarkStacksEmptyClosure(const ZMarkStripeSet* stripes) : 674 _stripes(stripes) {} 675 676 void do_thread(Thread* thread) { 677 ZMarkThreadLocalStacks* const stacks = ZThreadLocalData::stacks(thread); 678 guarantee(stacks->is_empty(_stripes), "Should be empty"); 679 } 680 }; 681 682 void ZMark::verify_all_stacks_empty() const { 683 // Verify thread stacks 684 ZVerifyMarkStacksEmptyClosure cl(&_stripes); 685 Threads::threads_do(&cl); 686 687 // Verify stripe stacks 688 guarantee(_stripes.is_empty(), "Should be empty"); 689 }