1 /* 2 * Copyright (c) 2015, 2023, 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/shared/gc_globals.hpp" 26 #include "gc/shared/suspendibleThreadSet.hpp" 27 #include "gc/z/zAbort.inline.hpp" 28 #include "gc/z/zAddress.inline.hpp" 29 #include "gc/z/zAllocator.inline.hpp" 30 #include "gc/z/zBarrier.inline.hpp" 31 #include "gc/z/zCollectedHeap.hpp" 32 #include "gc/z/zForwarding.inline.hpp" 33 #include "gc/z/zGeneration.inline.hpp" 34 #include "gc/z/zHeap.inline.hpp" 35 #include "gc/z/zIndexDistributor.inline.hpp" 36 #include "gc/z/zIterator.inline.hpp" 37 #include "gc/z/zPage.inline.hpp" 38 #include "gc/z/zPageAge.hpp" 39 #include "gc/z/zRelocate.hpp" 40 #include "gc/z/zRelocationSet.inline.hpp" 41 #include "gc/z/zRootsIterator.hpp" 42 #include "gc/z/zStackWatermark.hpp" 43 #include "gc/z/zStat.hpp" 44 #include "gc/z/zTask.hpp" 45 #include "gc/z/zUncoloredRoot.inline.hpp" 46 #include "gc/z/zVerify.hpp" 47 #include "gc/z/zWorkers.hpp" 48 #include "prims/jvmtiTagMap.hpp" 49 #include "runtime/atomic.hpp" 50 #include "utilities/debug.hpp" 51 52 static const ZStatCriticalPhase ZCriticalPhaseRelocationStall("Relocation Stall"); 53 static const ZStatSubPhase ZSubPhaseConcurrentRelocateRememberedSetFlipPromotedYoung("Concurrent Relocate Remset FP", ZGenerationId::young); 54 55 static uintptr_t forwarding_index(ZForwarding* forwarding, zoffset from_offset) { 56 return (from_offset - forwarding->start()) >> forwarding->object_alignment_shift(); 57 } 58 59 static zaddress forwarding_find(ZForwarding* forwarding, zoffset from_offset, ZForwardingCursor* cursor) { 60 const uintptr_t from_index = forwarding_index(forwarding, from_offset); 61 const ZForwardingEntry entry = forwarding->find(from_index, cursor); 62 return entry.populated() ? ZOffset::address(to_zoffset(entry.to_offset())) : zaddress::null; 63 } 64 65 static zaddress forwarding_find(ZForwarding* forwarding, zaddress_unsafe from_addr, ZForwardingCursor* cursor) { 66 return forwarding_find(forwarding, ZAddress::offset(from_addr), cursor); 67 } 68 69 static zaddress forwarding_find(ZForwarding* forwarding, zaddress from_addr, ZForwardingCursor* cursor) { 70 return forwarding_find(forwarding, ZAddress::offset(from_addr), cursor); 71 } 72 73 static zaddress forwarding_insert(ZForwarding* forwarding, zoffset from_offset, zaddress to_addr, ZForwardingCursor* cursor) { 74 const uintptr_t from_index = forwarding_index(forwarding, from_offset); 75 const zoffset to_offset = ZAddress::offset(to_addr); 76 const zoffset to_offset_final = forwarding->insert(from_index, to_offset, cursor); 77 return ZOffset::address(to_offset_final); 78 } 79 80 static zaddress forwarding_insert(ZForwarding* forwarding, zaddress from_addr, zaddress to_addr, ZForwardingCursor* cursor) { 81 return forwarding_insert(forwarding, ZAddress::offset(from_addr), to_addr, cursor); 82 } 83 84 ZRelocateQueue::ZRelocateQueue() 85 : _lock(), 86 _queue(), 87 _nworkers(0), 88 _nsynchronized(0), 89 _synchronize(false), 90 _needs_attention(0) {} 91 92 bool ZRelocateQueue::needs_attention() const { 93 return Atomic::load(&_needs_attention) != 0; 94 } 95 96 void ZRelocateQueue::inc_needs_attention() { 97 const int needs_attention = Atomic::add(&_needs_attention, 1); 98 assert(needs_attention == 1 || needs_attention == 2, "Invalid state"); 99 } 100 101 void ZRelocateQueue::dec_needs_attention() { 102 const int needs_attention = Atomic::sub(&_needs_attention, 1); 103 assert(needs_attention == 0 || needs_attention == 1, "Invalid state"); 104 } 105 106 void ZRelocateQueue::join(uint nworkers) { 107 assert(nworkers != 0, "Must request at least one worker"); 108 assert(_nworkers == 0, "Invalid state"); 109 assert(_nsynchronized == 0, "Invalid state"); 110 111 log_debug(gc, reloc)("Joining workers: %u", nworkers); 112 113 _nworkers = nworkers; 114 } 115 116 void ZRelocateQueue::resize_workers(uint nworkers) { 117 assert(nworkers != 0, "Must request at least one worker"); 118 assert(_nworkers == 0, "Invalid state"); 119 assert(_nsynchronized == 0, "Invalid state"); 120 121 log_debug(gc, reloc)("Resize workers: %u", nworkers); 122 123 ZLocker<ZConditionLock> locker(&_lock); 124 _nworkers = nworkers; 125 } 126 127 void ZRelocateQueue::leave() { 128 ZLocker<ZConditionLock> locker(&_lock); 129 _nworkers--; 130 131 assert(_nsynchronized <= _nworkers, "_nsynchronized: %u _nworkers: %u", _nsynchronized, _nworkers); 132 133 log_debug(gc, reloc)("Leaving workers: left: %u _synchronize: %d _nsynchronized: %u", _nworkers, _synchronize, _nsynchronized); 134 135 // Prune done forwardings 136 const bool forwardings_done = prune(); 137 138 // Check if all workers synchronized 139 const bool last_synchronized = _synchronize && _nworkers == _nsynchronized; 140 141 if (forwardings_done || last_synchronized) { 142 _lock.notify_all(); 143 } 144 } 145 146 void ZRelocateQueue::add_and_wait(ZForwarding* forwarding) { 147 ZStatTimer timer(ZCriticalPhaseRelocationStall); 148 ZLocker<ZConditionLock> locker(&_lock); 149 150 if (forwarding->is_done()) { 151 return; 152 } 153 154 _queue.append(forwarding); 155 if (_queue.length() == 1) { 156 // Queue became non-empty 157 inc_needs_attention(); 158 _lock.notify_all(); 159 } 160 161 while (!forwarding->is_done()) { 162 _lock.wait(); 163 } 164 } 165 166 bool ZRelocateQueue::prune() { 167 if (_queue.is_empty()) { 168 return false; 169 } 170 171 bool done = false; 172 173 for (int i = 0; i < _queue.length();) { 174 const ZForwarding* const forwarding = _queue.at(i); 175 if (forwarding->is_done()) { 176 done = true; 177 178 _queue.delete_at(i); 179 } else { 180 i++; 181 } 182 } 183 184 if (_queue.is_empty()) { 185 dec_needs_attention(); 186 } 187 188 return done; 189 } 190 191 ZForwarding* ZRelocateQueue::prune_and_claim() { 192 if (prune()) { 193 _lock.notify_all(); 194 } 195 196 for (int i = 0; i < _queue.length(); i++) { 197 ZForwarding* const forwarding = _queue.at(i); 198 if (forwarding->claim()) { 199 return forwarding; 200 } 201 } 202 203 return nullptr; 204 } 205 206 class ZRelocateQueueSynchronizeThread { 207 private: 208 ZRelocateQueue* const _queue; 209 210 public: 211 ZRelocateQueueSynchronizeThread(ZRelocateQueue* queue) 212 : _queue(queue) { 213 _queue->synchronize_thread(); 214 } 215 216 ~ZRelocateQueueSynchronizeThread() { 217 _queue->desynchronize_thread(); 218 } 219 }; 220 221 void ZRelocateQueue::synchronize_thread() { 222 _nsynchronized++; 223 224 log_debug(gc, reloc)("Synchronize worker _nsynchronized %u", _nsynchronized); 225 226 assert(_nsynchronized <= _nworkers, "_nsynchronized: %u _nworkers: %u", _nsynchronized, _nworkers); 227 if (_nsynchronized == _nworkers) { 228 // All workers synchronized 229 _lock.notify_all(); 230 } 231 } 232 233 void ZRelocateQueue::desynchronize_thread() { 234 _nsynchronized--; 235 236 log_debug(gc, reloc)("Desynchronize worker _nsynchronized %u", _nsynchronized); 237 238 assert(_nsynchronized < _nworkers, "_nsynchronized: %u _nworkers: %u", _nsynchronized, _nworkers); 239 } 240 241 ZForwarding* ZRelocateQueue::synchronize_poll() { 242 // Fast path avoids locking 243 if (!needs_attention()) { 244 return nullptr; 245 } 246 247 // Slow path to get the next forwarding and/or synchronize 248 ZLocker<ZConditionLock> locker(&_lock); 249 250 { 251 ZForwarding* const forwarding = prune_and_claim(); 252 if (forwarding != nullptr) { 253 // Don't become synchronized while there are elements in the queue 254 return forwarding; 255 } 256 } 257 258 if (!_synchronize) { 259 return nullptr; 260 } 261 262 ZRelocateQueueSynchronizeThread rqst(this); 263 264 do { 265 _lock.wait(); 266 267 ZForwarding* const forwarding = prune_and_claim(); 268 if (forwarding != nullptr) { 269 return forwarding; 270 } 271 } while (_synchronize); 272 273 return nullptr; 274 } 275 276 void ZRelocateQueue::clear() { 277 assert(_nworkers == 0, "Invalid state"); 278 279 if (_queue.is_empty()) { 280 return; 281 } 282 283 ZArrayIterator<ZForwarding*> iter(&_queue); 284 for (ZForwarding* forwarding; iter.next(&forwarding);) { 285 assert(forwarding->is_done(), "All should be done"); 286 } 287 288 assert(false, "Clear was not empty"); 289 290 _queue.clear(); 291 dec_needs_attention(); 292 } 293 294 void ZRelocateQueue::synchronize() { 295 ZLocker<ZConditionLock> locker(&_lock); 296 _synchronize = true; 297 298 inc_needs_attention(); 299 300 log_debug(gc, reloc)("Synchronize all workers 1 _nworkers: %u _nsynchronized: %u", _nworkers, _nsynchronized); 301 302 while (_nworkers != _nsynchronized) { 303 _lock.wait(); 304 log_debug(gc, reloc)("Synchronize all workers 2 _nworkers: %u _nsynchronized: %u", _nworkers, _nsynchronized); 305 } 306 } 307 308 void ZRelocateQueue::desynchronize() { 309 ZLocker<ZConditionLock> locker(&_lock); 310 _synchronize = false; 311 312 log_debug(gc, reloc)("Desynchronize all workers _nworkers: %u _nsynchronized: %u", _nworkers, _nsynchronized); 313 314 assert(_nsynchronized <= _nworkers, "_nsynchronized: %u _nworkers: %u", _nsynchronized, _nworkers); 315 316 dec_needs_attention(); 317 318 _lock.notify_all(); 319 } 320 321 ZRelocate::ZRelocate(ZGeneration* generation) 322 : _generation(generation), 323 _queue() {} 324 325 ZWorkers* ZRelocate::workers() const { 326 return _generation->workers(); 327 } 328 329 void ZRelocate::start() { 330 _queue.join(workers()->active_workers()); 331 } 332 333 void ZRelocate::add_remset(volatile zpointer* p) { 334 ZGeneration::young()->remember(p); 335 } 336 337 static zaddress relocate_object_inner(ZForwarding* forwarding, zaddress from_addr, ZForwardingCursor* cursor) { 338 assert(ZHeap::heap()->is_object_live(from_addr), "Should be live"); 339 340 // Allocate object 341 const size_t size = ZUtils::object_size(from_addr); 342 343 ZAllocatorForRelocation* allocator = ZAllocator::relocation(forwarding->to_age()); 344 345 const zaddress to_addr = allocator->alloc_object(size); 346 347 if (is_null(to_addr)) { 348 // Allocation failed 349 return zaddress::null; 350 } 351 352 // Copy object 353 ZUtils::object_copy_disjoint(from_addr, to_addr, size); 354 355 // Insert forwarding 356 const zaddress to_addr_final = forwarding_insert(forwarding, from_addr, to_addr, cursor); 357 358 if (to_addr_final != to_addr) { 359 // Already relocated, try undo allocation 360 allocator->undo_alloc_object(to_addr, size); 361 } 362 363 return to_addr_final; 364 } 365 366 zaddress ZRelocate::relocate_object(ZForwarding* forwarding, zaddress_unsafe from_addr) { 367 ZForwardingCursor cursor; 368 369 // Lookup forwarding 370 zaddress to_addr = forwarding_find(forwarding, from_addr, &cursor); 371 if (!is_null(to_addr)) { 372 // Already relocated 373 return to_addr; 374 } 375 376 // Relocate object 377 if (forwarding->retain_page(&_queue)) { 378 assert(_generation->is_phase_relocate(), "Must be"); 379 to_addr = relocate_object_inner(forwarding, safe(from_addr), &cursor); 380 forwarding->release_page(); 381 382 if (!is_null(to_addr)) { 383 // Success 384 return to_addr; 385 } 386 387 // Failed to relocate object. Signal and wait for a worker thread to 388 // complete relocation of this page, and then forward the object. 389 _queue.add_and_wait(forwarding); 390 } 391 392 // Forward object 393 return forward_object(forwarding, from_addr); 394 } 395 396 zaddress ZRelocate::forward_object(ZForwarding* forwarding, zaddress_unsafe from_addr) { 397 ZForwardingCursor cursor; 398 const zaddress to_addr = forwarding_find(forwarding, from_addr, &cursor); 399 assert(!is_null(to_addr), "Should be forwarded: " PTR_FORMAT, untype(from_addr)); 400 return to_addr; 401 } 402 403 static ZPage* alloc_page(ZAllocatorForRelocation* allocator, ZPageType type, size_t size) { 404 if (ZStressRelocateInPlace) { 405 // Simulate failure to allocate a new page. This will 406 // cause the page being relocated to be relocated in-place. 407 return nullptr; 408 } 409 410 ZAllocationFlags flags; 411 flags.set_non_blocking(); 412 flags.set_gc_relocation(); 413 414 return allocator->alloc_page_for_relocation(type, size, flags); 415 } 416 417 static void retire_target_page(ZGeneration* generation, ZPage* page) { 418 if (generation->is_young() && page->is_old()) { 419 generation->increase_promoted(page->used()); 420 } else { 421 generation->increase_compacted(page->used()); 422 } 423 424 // Free target page if it is empty. We can end up with an empty target 425 // page if we allocated a new target page, and then lost the race to 426 // relocate the remaining objects, leaving the target page empty when 427 // relocation completed. 428 if (page->used() == 0) { 429 ZHeap::heap()->free_page(page); 430 } 431 } 432 433 class ZRelocateSmallAllocator { 434 private: 435 ZGeneration* const _generation; 436 volatile size_t _in_place_count; 437 438 public: 439 ZRelocateSmallAllocator(ZGeneration* generation) 440 : _generation(generation), 441 _in_place_count(0) {} 442 443 ZPage* alloc_and_retire_target_page(ZForwarding* forwarding, ZPage* target) { 444 ZAllocatorForRelocation* const allocator = ZAllocator::relocation(forwarding->to_age()); 445 ZPage* const page = alloc_page(allocator, forwarding->type(), forwarding->size()); 446 if (page == nullptr) { 447 Atomic::inc(&_in_place_count); 448 } 449 450 if (target != nullptr) { 451 // Retire the old target page 452 retire_target_page(_generation, target); 453 } 454 455 return page; 456 } 457 458 void share_target_page(ZPage* page) { 459 // Does nothing 460 } 461 462 void free_target_page(ZPage* page) { 463 if (page != nullptr) { 464 retire_target_page(_generation, page); 465 } 466 } 467 468 zaddress alloc_object(ZPage* page, size_t size) const { 469 return (page != nullptr) ? page->alloc_object(size) : zaddress::null; 470 } 471 472 void undo_alloc_object(ZPage* page, zaddress addr, size_t size) const { 473 page->undo_alloc_object(addr, size); 474 } 475 476 const size_t in_place_count() const { 477 return _in_place_count; 478 } 479 }; 480 481 class ZRelocateMediumAllocator { 482 private: 483 ZGeneration* const _generation; 484 ZConditionLock _lock; 485 ZPage* _shared[ZAllocator::_relocation_allocators]; 486 bool _in_place; 487 volatile size_t _in_place_count; 488 489 public: 490 ZRelocateMediumAllocator(ZGeneration* generation) 491 : _generation(generation), 492 _lock(), 493 _shared(), 494 _in_place(false), 495 _in_place_count(0) {} 496 497 ~ZRelocateMediumAllocator() { 498 for (uint i = 0; i < ZAllocator::_relocation_allocators; ++i) { 499 if (_shared[i] != nullptr) { 500 retire_target_page(_generation, _shared[i]); 501 } 502 } 503 } 504 505 ZPage* shared(ZPageAge age) { 506 return _shared[static_cast<uint>(age) - 1]; 507 } 508 509 void set_shared(ZPageAge age, ZPage* page) { 510 _shared[static_cast<uint>(age) - 1] = page; 511 } 512 513 ZPage* alloc_and_retire_target_page(ZForwarding* forwarding, ZPage* target) { 514 ZLocker<ZConditionLock> locker(&_lock); 515 516 // Wait for any ongoing in-place relocation to complete 517 while (_in_place) { 518 _lock.wait(); 519 } 520 521 // Allocate a new page only if the shared page is the same as the 522 // current target page. The shared page will be different from the 523 // current target page if another thread shared a page, or allocated 524 // a new page. 525 const ZPageAge to_age = forwarding->to_age(); 526 if (shared(to_age) == target) { 527 ZAllocatorForRelocation* const allocator = ZAllocator::relocation(forwarding->to_age()); 528 ZPage* const to_page = alloc_page(allocator, forwarding->type(), forwarding->size()); 529 set_shared(to_age, to_page); 530 if (to_page == nullptr) { 531 Atomic::inc(&_in_place_count); 532 _in_place = true; 533 } 534 535 // This thread is responsible for retiring the shared target page 536 if (target != nullptr) { 537 retire_target_page(_generation, target); 538 } 539 } 540 541 return shared(to_age); 542 } 543 544 void share_target_page(ZPage* page) { 545 const ZPageAge age = page->age(); 546 547 ZLocker<ZConditionLock> locker(&_lock); 548 assert(_in_place, "Invalid state"); 549 assert(shared(age) == nullptr, "Invalid state"); 550 assert(page != nullptr, "Invalid page"); 551 552 set_shared(age, page); 553 _in_place = false; 554 555 _lock.notify_all(); 556 } 557 558 void free_target_page(ZPage* page) { 559 // Does nothing 560 } 561 562 zaddress alloc_object(ZPage* page, size_t size) const { 563 return (page != nullptr) ? page->alloc_object_atomic(size) : zaddress::null; 564 } 565 566 void undo_alloc_object(ZPage* page, zaddress addr, size_t size) const { 567 page->undo_alloc_object_atomic(addr, size); 568 } 569 570 const size_t in_place_count() const { 571 return _in_place_count; 572 } 573 }; 574 575 template <typename Allocator> 576 class ZRelocateWork : public StackObj { 577 private: 578 Allocator* const _allocator; 579 ZForwarding* _forwarding; 580 ZPage* _target[ZAllocator::_relocation_allocators]; 581 ZGeneration* const _generation; 582 size_t _other_promoted; 583 size_t _other_compacted; 584 585 ZPage* target(ZPageAge age) { 586 return _target[static_cast<uint>(age) - 1]; 587 } 588 589 void set_target(ZPageAge age, ZPage* page) { 590 _target[static_cast<uint>(age) - 1] = page; 591 } 592 593 size_t object_alignment() const { 594 return (size_t)1 << _forwarding->object_alignment_shift(); 595 } 596 597 void increase_other_forwarded(size_t unaligned_object_size) { 598 const size_t aligned_size = align_up(unaligned_object_size, object_alignment()); 599 if (_forwarding->is_promotion()) { 600 _other_promoted += aligned_size; 601 } else { 602 _other_compacted += aligned_size; 603 } 604 } 605 606 zaddress try_relocate_object_inner(zaddress from_addr) { 607 ZForwardingCursor cursor; 608 609 ZPage* const to_page = target(_forwarding->to_age()); 610 611 // Lookup forwarding 612 { 613 const zaddress to_addr = forwarding_find(_forwarding, from_addr, &cursor); 614 if (!is_null(to_addr)) { 615 // Already relocated 616 const size_t size = ZUtils::object_size(to_addr); 617 increase_other_forwarded(size); 618 return to_addr; 619 } 620 } 621 622 // Allocate object 623 const size_t size = ZUtils::object_size(from_addr); 624 const zaddress allocated_addr = _allocator->alloc_object(to_page, size); 625 if (is_null(allocated_addr)) { 626 // Allocation failed 627 return zaddress::null; 628 } 629 630 // Copy object. Use conjoint copying if we are relocating 631 // in-place and the new object overlaps with the old object. 632 if (_forwarding->in_place_relocation() && allocated_addr + size > from_addr) { 633 ZUtils::object_copy_conjoint(from_addr, allocated_addr, size); 634 } else { 635 ZUtils::object_copy_disjoint(from_addr, allocated_addr, size); 636 } 637 638 // Insert forwarding 639 const zaddress to_addr = forwarding_insert(_forwarding, from_addr, allocated_addr, &cursor); 640 if (to_addr != allocated_addr) { 641 // Already relocated, undo allocation 642 _allocator->undo_alloc_object(to_page, to_addr, size); 643 increase_other_forwarded(size); 644 } 645 646 return to_addr; 647 } 648 649 void update_remset_old_to_old(zaddress from_addr, zaddress to_addr) const { 650 // Old-to-old relocation - move existing remset bits 651 652 // If this is called for an in-place relocated page, then this code has the 653 // responsibility to clear the old remset bits. Extra care is needed because: 654 // 655 // 1) The to-object copy can overlap with the from-object copy 656 // 2) Remset bits of old objects need to be cleared 657 // 658 // A watermark is used to keep track of how far the old remset bits have been removed. 659 660 const bool in_place = _forwarding->in_place_relocation(); 661 ZPage* const from_page = _forwarding->page(); 662 const uintptr_t from_local_offset = from_page->local_offset(from_addr); 663 664 // Note: even with in-place relocation, the to_page could be another page 665 ZPage* const to_page = ZHeap::heap()->page(to_addr); 666 667 // Uses _relaxed version to handle that in-place relocation resets _top 668 assert(ZHeap::heap()->is_in_page_relaxed(from_page, from_addr), "Must be"); 669 assert(to_page->is_in(to_addr), "Must be"); 670 671 672 // Read the size from the to-object, since the from-object 673 // could have been overwritten during in-place relocation. 674 const size_t size = ZUtils::object_size(to_addr); 675 676 // If a young generation collection started while the old generation 677 // relocated objects, the remember set bits were flipped from "current" 678 // to "previous". 679 // 680 // We need to select the correct remembered sets bitmap to ensure that the 681 // old remset bits are found. 682 // 683 // Note that if the young generation marking (remset scanning) finishes 684 // before the old generation relocation has relocated this page, then the 685 // young generation will visit this page's previous remembered set bits and 686 // moved them over to the current bitmap. 687 // 688 // If the young generation runs multiple cycles while the old generation is 689 // relocating, then the first cycle will have consume the the old remset, 690 // bits and moved associated objects to a new old page. The old relocation 691 // could find either the the two bitmaps. So, either it will find the original 692 // remset bits for the page, or it will find an empty bitmap for the page. It 693 // doesn't matter for correctness, because the young generation marking has 694 // already taken care of the bits. 695 696 const bool active_remset_is_current = ZGeneration::old()->active_remset_is_current(); 697 698 // When in-place relocation is done and the old remset bits are located in 699 // the bitmap that is going to be used for the new remset bits, then we 700 // need to clear the old bits before the new bits are inserted. 701 const bool iterate_current_remset = active_remset_is_current && !in_place; 702 703 BitMap::Iterator iter = iterate_current_remset 704 ? from_page->remset_iterator_limited_current(from_local_offset, size) 705 : from_page->remset_iterator_limited_previous(from_local_offset, size); 706 707 for (BitMap::idx_t field_bit : iter) { 708 const uintptr_t field_local_offset = ZRememberedSet::to_offset(field_bit); 709 710 // Add remset entry in the to-page 711 const uintptr_t offset = field_local_offset - from_local_offset; 712 const zaddress to_field = to_addr + offset; 713 log_trace(gc, reloc)("Remember: from: " PTR_FORMAT " to: " PTR_FORMAT " current: %d marking: %d page: " PTR_FORMAT " remset: " PTR_FORMAT, 714 untype(from_page->start() + field_local_offset), untype(to_field), active_remset_is_current, ZGeneration::young()->is_phase_mark(), p2i(to_page), p2i(to_page->remset_current())); 715 716 volatile zpointer* const p = (volatile zpointer*)to_field; 717 718 if (ZGeneration::young()->is_phase_mark()) { 719 // Young generation remembered set scanning needs to know about this 720 // field. It will take responsibility to add a new remember set entry if needed. 721 _forwarding->relocated_remembered_fields_register(p); 722 } else { 723 to_page->remember(p); 724 if (in_place) { 725 assert(to_page->is_remembered(p), "p: " PTR_FORMAT, p2i(p)); 726 } 727 } 728 } 729 } 730 731 static bool add_remset_if_young(volatile zpointer* p, zaddress addr) { 732 if (ZHeap::heap()->is_young(addr)) { 733 ZRelocate::add_remset(p); 734 return true; 735 } 736 737 return false; 738 } 739 740 static void update_remset_promoted_filter_and_remap_per_field(volatile zpointer* p) { 741 const zpointer ptr = Atomic::load(p); 742 743 assert(ZPointer::is_old_load_good(ptr), "Should be at least old load good: " PTR_FORMAT, untype(ptr)); 744 745 if (ZPointer::is_store_good(ptr)) { 746 // Already has a remset entry 747 return; 748 } 749 750 if (ZPointer::is_load_good(ptr)) { 751 if (!is_null_any(ptr)) { 752 const zaddress addr = ZPointer::uncolor(ptr); 753 add_remset_if_young(p, addr); 754 } 755 // No need to remap it is already load good 756 return; 757 } 758 759 if (is_null_any(ptr)) { 760 // Eagerly remap to skip adding a remset entry just to get deferred remapping 761 ZBarrier::remap_young_relocated(p, ptr); 762 return; 763 } 764 765 const zaddress_unsafe addr_unsafe = ZPointer::uncolor_unsafe(ptr); 766 ZForwarding* const forwarding = ZGeneration::young()->forwarding(addr_unsafe); 767 768 if (forwarding == nullptr) { 769 // Object isn't being relocated 770 const zaddress addr = safe(addr_unsafe); 771 if (!add_remset_if_young(p, addr)) { 772 // Not young - eagerly remap to skip adding a remset entry just to get deferred remapping 773 ZBarrier::remap_young_relocated(p, ptr); 774 } 775 return; 776 } 777 778 const zaddress addr = forwarding->find(addr_unsafe); 779 780 if (!is_null(addr)) { 781 // Object has already been relocated 782 if (!add_remset_if_young(p, addr)) { 783 // Not young - eagerly remap to skip adding a remset entry just to get deferred remapping 784 ZBarrier::remap_young_relocated(p, ptr); 785 } 786 return; 787 } 788 789 // Object has not been relocated yet 790 // Don't want to eagerly relocate objects, so just add a remset 791 ZRelocate::add_remset(p); 792 return; 793 } 794 795 void update_remset_promoted(zaddress to_addr) const { 796 ZIterator::basic_oop_iterate(to_oop(to_addr), update_remset_promoted_filter_and_remap_per_field); 797 } 798 799 void update_remset_for_fields(zaddress from_addr, zaddress to_addr) const { 800 if (_forwarding->to_age() != ZPageAge::old) { 801 // No remembered set in young pages 802 return; 803 } 804 805 // Need to deal with remset when moving objects to the old generation 806 if (_forwarding->from_age() == ZPageAge::old) { 807 update_remset_old_to_old(from_addr, to_addr); 808 return; 809 } 810 811 // Normal promotion 812 update_remset_promoted(to_addr); 813 } 814 815 bool try_relocate_object(zaddress from_addr) { 816 const zaddress to_addr = try_relocate_object_inner(from_addr); 817 818 if (is_null(to_addr)) { 819 return false; 820 } 821 822 update_remset_for_fields(from_addr, to_addr); 823 824 return true; 825 } 826 827 void start_in_place_relocation_prepare_remset(ZPage* from_page) { 828 if (_forwarding->from_age() != ZPageAge::old) { 829 // Only old pages have use remset bits 830 return; 831 } 832 833 if (ZGeneration::old()->active_remset_is_current()) { 834 // We want to iterate over and clear the remset bits of the from-space page, 835 // and insert current bits in the to-space page. However, with in-place 836 // relocation, the from-space and to-space pages are the same. Clearing 837 // is destructive, and is difficult to perform before or during the iteration. 838 // However, clearing of the current bits has to be done before exposing the 839 // to-space objects in the forwarding table. 840 // 841 // To solve this tricky dependency problem, we start by stashing away the 842 // current bits in the previous bits, and clearing the current bits 843 // (implemented by swapping the bits). This way, the current bits are 844 // cleared before copying the objects (like a normal to-space page), 845 // and the previous bits are representing a copy of the current bits 846 // of the from-space page, and are used for iteration. 847 from_page->swap_remset_bitmaps(); 848 } 849 } 850 851 ZPage* start_in_place_relocation(zoffset relocated_watermark) { 852 _forwarding->in_place_relocation_claim_page(); 853 _forwarding->in_place_relocation_start(relocated_watermark); 854 855 ZPage* const from_page = _forwarding->page(); 856 857 const ZPageAge to_age = _forwarding->to_age(); 858 const bool promotion = _forwarding->is_promotion(); 859 860 // Promotions happen through a new cloned page 861 ZPage* const to_page = promotion ? from_page->clone_limited() : from_page; 862 to_page->reset(to_age, ZPageResetType::InPlaceRelocation); 863 864 // Clear remset bits for all objects that were relocated 865 // before this page became an in-place relocated page. 866 start_in_place_relocation_prepare_remset(from_page); 867 868 if (promotion) { 869 // Register the the promotion 870 ZGeneration::young()->in_place_relocate_promote(from_page, to_page); 871 ZGeneration::young()->register_in_place_relocate_promoted(from_page); 872 } 873 874 return to_page; 875 } 876 877 void relocate_object(oop obj) { 878 const zaddress addr = to_zaddress(obj); 879 assert(ZHeap::heap()->is_object_live(addr), "Should be live"); 880 881 while (!try_relocate_object(addr)) { 882 // Allocate a new target page, or if that fails, use the page being 883 // relocated as the new target, which will cause it to be relocated 884 // in-place. 885 const ZPageAge to_age = _forwarding->to_age(); 886 ZPage* to_page = _allocator->alloc_and_retire_target_page(_forwarding, target(to_age)); 887 set_target(to_age, to_page); 888 if (to_page != nullptr) { 889 continue; 890 } 891 892 // Start in-place relocation to block other threads from accessing 893 // the page, or its forwarding table, until it has been released 894 // (relocation completed). 895 to_page = start_in_place_relocation(ZAddress::offset(addr)); 896 set_target(to_age, to_page); 897 } 898 } 899 900 public: 901 ZRelocateWork(Allocator* allocator, ZGeneration* generation) 902 : _allocator(allocator), 903 _forwarding(nullptr), 904 _target(), 905 _generation(generation), 906 _other_promoted(0), 907 _other_compacted(0) {} 908 909 ~ZRelocateWork() { 910 for (uint i = 0; i < ZAllocator::_relocation_allocators; ++i) { 911 _allocator->free_target_page(_target[i]); 912 } 913 // Report statistics on-behalf of non-worker threads 914 _generation->increase_promoted(_other_promoted); 915 _generation->increase_compacted(_other_compacted); 916 } 917 918 bool active_remset_is_current() const { 919 // Normal old-to-old relocation can treat the from-page remset as a 920 // read-only copy, and then copy over the appropriate remset bits to the 921 // cleared to-page's 'current' remset bitmap. 922 // 923 // In-place relocation is more complicated. Since, the same page is both 924 // a from-page and a to-page, we need to remove the old remset bits, and 925 // add remset bits that corresponds to the new locations of the relocated 926 // objects. 927 // 928 // Depending on how long ago (in terms of number of young GC's and the 929 // current young GC's phase), the page was allocated, the active 930 // remembered set will be in either the 'current' or 'previous' bitmap. 931 // 932 // If the active bits are in the 'previous' bitmap, we know that the 933 // 'current' bitmap was cleared at some earlier point in time, and we can 934 // simply set new bits in 'current' bitmap, and later when relocation has 935 // read all the old remset bits, we could just clear the 'previous' remset 936 // bitmap. 937 // 938 // If, on the other hand, the active bits are in the 'current' bitmap, then 939 // that bitmap will be used to both read the old remset bits, and the 940 // destination for the remset bits that we copy when an object is copied 941 // to it's new location within the page. We need to *carefully* remove all 942 // all old remset bits, without clearing out the newly set bits. 943 return ZGeneration::old()->active_remset_is_current(); 944 } 945 946 void clear_remset_before_reuse(ZPage* page, bool in_place) { 947 if (_forwarding->from_age() != ZPageAge::old) { 948 // No remset bits 949 return; 950 } 951 952 if (in_place) { 953 // Clear 'previous' remset bits. For in-place relocated pages, the previous 954 // remset bits are always used, even when active_remset_is_current(). 955 page->clear_remset_previous(); 956 957 return; 958 } 959 960 // Normal relocate 961 962 // Clear active remset bits 963 if (active_remset_is_current()) { 964 page->clear_remset_current(); 965 } else { 966 page->clear_remset_previous(); 967 } 968 969 // Verify that inactive remset bits are all cleared 970 if (active_remset_is_current()) { 971 page->verify_remset_cleared_previous(); 972 } else { 973 page->verify_remset_cleared_current(); 974 } 975 } 976 977 void finish_in_place_relocation() { 978 // We are done with the from_space copy of the page 979 _forwarding->in_place_relocation_finish(); 980 } 981 982 void do_forwarding(ZForwarding* forwarding) { 983 _forwarding = forwarding; 984 985 _forwarding->page()->log_msg(" (relocate page)"); 986 987 ZVerify::before_relocation(_forwarding); 988 989 // Relocate objects 990 _forwarding->object_iterate([&](oop obj) { relocate_object(obj); }); 991 992 ZVerify::after_relocation(_forwarding); 993 994 // Verify 995 if (ZVerifyForwarding) { 996 _forwarding->verify(); 997 } 998 999 _generation->increase_freed(_forwarding->page()->size()); 1000 1001 // Deal with in-place relocation 1002 const bool in_place = _forwarding->in_place_relocation(); 1003 if (in_place) { 1004 finish_in_place_relocation(); 1005 } 1006 1007 // Old from-space pages need to deal with remset bits 1008 if (_forwarding->from_age() == ZPageAge::old) { 1009 _forwarding->relocated_remembered_fields_after_relocate(); 1010 } 1011 1012 // Release relocated page 1013 _forwarding->release_page(); 1014 1015 if (in_place) { 1016 // Wait for all other threads to call release_page 1017 ZPage* const page = _forwarding->detach_page(); 1018 1019 // Ensure that previous remset bits are cleared 1020 clear_remset_before_reuse(page, true /* in_place */); 1021 1022 page->log_msg(" (relocate page done in-place)"); 1023 1024 // Different pages when promoting 1025 ZPage* const target_page = target(_forwarding->to_age()); 1026 _allocator->share_target_page(target_page); 1027 1028 } else { 1029 // Wait for all other threads to call release_page 1030 ZPage* const page = _forwarding->detach_page(); 1031 1032 // Ensure that all remset bits are cleared 1033 // Note: cleared after detach_page, when we know that 1034 // the young generation isn't scanning the remset. 1035 clear_remset_before_reuse(page, false /* in_place */); 1036 1037 page->log_msg(" (relocate page done normal)"); 1038 1039 // Free page 1040 ZHeap::heap()->free_page(page); 1041 } 1042 } 1043 }; 1044 1045 class ZRelocateStoreBufferInstallBasePointersThreadClosure : public ThreadClosure { 1046 public: 1047 virtual void do_thread(Thread* thread) { 1048 JavaThread* const jt = JavaThread::cast(thread); 1049 ZStoreBarrierBuffer* buffer = ZThreadLocalData::store_barrier_buffer(jt); 1050 buffer->install_base_pointers(); 1051 } 1052 }; 1053 1054 // Installs the object base pointers (object starts), for the fields written 1055 // in the store buffer. The code that searches for the object start uses that 1056 // liveness information stored in the pages. That information is lost when the 1057 // pages have been relocated and then destroyed. 1058 class ZRelocateStoreBufferInstallBasePointersTask : public ZTask { 1059 private: 1060 ZJavaThreadsIterator _threads_iter; 1061 1062 public: 1063 ZRelocateStoreBufferInstallBasePointersTask(ZGeneration* generation) 1064 : ZTask("ZRelocateStoreBufferInstallBasePointersTask"), 1065 _threads_iter(generation->id_optional()) {} 1066 1067 virtual void work() { 1068 ZRelocateStoreBufferInstallBasePointersThreadClosure fix_store_buffer_cl; 1069 _threads_iter.apply(&fix_store_buffer_cl); 1070 } 1071 }; 1072 1073 class ZRelocateTask : public ZRestartableTask { 1074 private: 1075 ZRelocationSetParallelIterator _iter; 1076 ZGeneration* const _generation; 1077 ZRelocateQueue* const _queue; 1078 ZRelocateSmallAllocator _small_allocator; 1079 ZRelocateMediumAllocator _medium_allocator; 1080 1081 public: 1082 ZRelocateTask(ZRelocationSet* relocation_set, ZRelocateQueue* queue) 1083 : ZRestartableTask("ZRelocateTask"), 1084 _iter(relocation_set), 1085 _generation(relocation_set->generation()), 1086 _queue(queue), 1087 _small_allocator(_generation), 1088 _medium_allocator(_generation) {} 1089 1090 ~ZRelocateTask() { 1091 _generation->stat_relocation()->at_relocate_end(_small_allocator.in_place_count(), _medium_allocator.in_place_count()); 1092 } 1093 1094 virtual void work() { 1095 ZRelocateWork<ZRelocateSmallAllocator> small(&_small_allocator, _generation); 1096 ZRelocateWork<ZRelocateMediumAllocator> medium(&_medium_allocator, _generation); 1097 1098 const auto do_forwarding = [&](ZForwarding* forwarding) { 1099 ZPage* const page = forwarding->page(); 1100 if (page->is_small()) { 1101 small.do_forwarding(forwarding); 1102 } else { 1103 medium.do_forwarding(forwarding); 1104 } 1105 1106 // Absolute last thing done while relocating a page. 1107 // 1108 // We don't use the SuspendibleThreadSet when relocating pages. 1109 // Instead the ZRelocateQueue is used as a pseudo STS joiner/leaver. 1110 // 1111 // After the mark_done call a safepointing could be completed and a 1112 // new GC phase could be entered. 1113 forwarding->mark_done(); 1114 }; 1115 1116 const auto claim_and_do_forwarding = [&](ZForwarding* forwarding) { 1117 if (forwarding->claim()) { 1118 do_forwarding(forwarding); 1119 } 1120 }; 1121 1122 const auto do_forwarding_one_from_iter = [&]() { 1123 ZForwarding* forwarding; 1124 1125 if (_iter.next(&forwarding)) { 1126 claim_and_do_forwarding(forwarding); 1127 return true; 1128 } 1129 1130 return false; 1131 }; 1132 1133 for (;;) { 1134 // As long as there are requests in the relocate queue, there are threads 1135 // waiting in a VM state that does not allow them to be blocked. The 1136 // worker thread needs to finish relocate these pages, and allow the 1137 // other threads to continue and proceed to a blocking state. After that, 1138 // the worker threads are allowed to safepoint synchronize. 1139 for (ZForwarding* forwarding; (forwarding = _queue->synchronize_poll()) != nullptr;) { 1140 do_forwarding(forwarding); 1141 } 1142 1143 if (!do_forwarding_one_from_iter()) { 1144 // No more work 1145 break; 1146 } 1147 1148 if (_generation->should_worker_resize()) { 1149 break; 1150 } 1151 } 1152 1153 _queue->leave(); 1154 } 1155 1156 virtual void resize_workers(uint nworkers) { 1157 _queue->resize_workers(nworkers); 1158 } 1159 }; 1160 1161 static void remap_and_maybe_add_remset(volatile zpointer* p) { 1162 const zpointer ptr = Atomic::load(p); 1163 1164 if (ZPointer::is_store_good(ptr)) { 1165 // Already has a remset entry 1166 return; 1167 } 1168 1169 // Remset entries are used for two reasons: 1170 // 1) Young marking old-to-young pointer roots 1171 // 2) Deferred remapping of stale old-to-young pointers 1172 // 1173 // This load barrier will up-front perform the remapping of (2), 1174 // and the code below only has to make sure we register up-to-date 1175 // old-to-young pointers for (1). 1176 const zaddress addr = ZBarrier::load_barrier_on_oop_field_preloaded(p, ptr); 1177 1178 if (is_null(addr)) { 1179 // No need for remset entries for null pointers 1180 return; 1181 } 1182 1183 if (ZHeap::heap()->is_old(addr)) { 1184 // No need for remset entries for pointers to old gen 1185 return; 1186 } 1187 1188 ZRelocate::add_remset(p); 1189 } 1190 1191 class ZRelocateAddRemsetForFlipPromoted : public ZRestartableTask { 1192 private: 1193 ZStatTimerYoung _timer; 1194 ZArrayParallelIterator<ZPage*> _iter; 1195 1196 public: 1197 ZRelocateAddRemsetForFlipPromoted(ZArray<ZPage*>* pages) 1198 : ZRestartableTask("ZRelocateAddRemsetForFlipPromoted"), 1199 _timer(ZSubPhaseConcurrentRelocateRememberedSetFlipPromotedYoung), 1200 _iter(pages) {} 1201 1202 virtual void work() { 1203 SuspendibleThreadSetJoiner sts_joiner; 1204 1205 for (ZPage* page; _iter.next(&page);) { 1206 page->object_iterate([&](oop obj) { 1207 ZIterator::basic_oop_iterate_safe(obj, remap_and_maybe_add_remset); 1208 }); 1209 1210 SuspendibleThreadSet::yield(); 1211 if (ZGeneration::young()->should_worker_resize()) { 1212 return; 1213 } 1214 } 1215 } 1216 }; 1217 1218 void ZRelocate::relocate(ZRelocationSet* relocation_set) { 1219 { 1220 // Install the store buffer's base pointers before the 1221 // relocate task destroys the liveness information in 1222 // the relocated pages. 1223 ZRelocateStoreBufferInstallBasePointersTask buffer_task(_generation); 1224 workers()->run(&buffer_task); 1225 } 1226 1227 { 1228 ZRelocateTask relocate_task(relocation_set, &_queue); 1229 workers()->run(&relocate_task); 1230 } 1231 1232 if (relocation_set->generation()->is_young()) { 1233 ZRelocateAddRemsetForFlipPromoted task(relocation_set->flip_promoted_pages()); 1234 workers()->run(&task); 1235 } 1236 1237 _queue.clear(); 1238 } 1239 1240 ZPageAge ZRelocate::compute_to_age(ZPageAge from_age) { 1241 if (from_age == ZPageAge::old) { 1242 return ZPageAge::old; 1243 } 1244 1245 const uint age = static_cast<uint>(from_age); 1246 if (age >= ZGeneration::young()->tenuring_threshold()) { 1247 return ZPageAge::old; 1248 } 1249 1250 return static_cast<ZPageAge>(age + 1); 1251 } 1252 1253 class ZFlipAgePagesTask : public ZTask { 1254 private: 1255 ZArrayParallelIterator<ZPage*> _iter; 1256 1257 public: 1258 ZFlipAgePagesTask(const ZArray<ZPage*>* pages) 1259 : ZTask("ZPromotePagesTask"), 1260 _iter(pages) {} 1261 1262 virtual void work() { 1263 SuspendibleThreadSetJoiner sts_joiner; 1264 ZArray<ZPage*> promoted_pages; 1265 1266 for (ZPage* prev_page; _iter.next(&prev_page);) { 1267 const ZPageAge from_age = prev_page->age(); 1268 const ZPageAge to_age = ZRelocate::compute_to_age(from_age); 1269 assert(from_age != ZPageAge::old, "invalid age for a young collection"); 1270 1271 // Figure out if this is proper promotion 1272 const bool promotion = to_age == ZPageAge::old; 1273 1274 if (promotion) { 1275 // Before promoting an object (and before relocate start), we must ensure that all 1276 // contained zpointers are store good. The marking code ensures that for non-null 1277 // pointers, but null pointers are ignored. This code ensures that even null pointers 1278 // are made store good, for the promoted objects. 1279 prev_page->object_iterate([&](oop obj) { 1280 ZIterator::basic_oop_iterate_safe(obj, ZBarrier::promote_barrier_on_young_oop_field); 1281 }); 1282 } 1283 1284 // Logging 1285 prev_page->log_msg(promotion ? " (flip promoted)" : " (flip survived)"); 1286 1287 // Setup to-space page 1288 ZPage* const new_page = promotion ? prev_page->clone_limited_promote_flipped() : prev_page; 1289 new_page->reset(to_age, ZPageResetType::FlipAging); 1290 1291 if (promotion) { 1292 ZGeneration::young()->flip_promote(prev_page, new_page); 1293 // Defer promoted page registration times the lock is taken 1294 promoted_pages.push(prev_page); 1295 } 1296 1297 SuspendibleThreadSet::yield(); 1298 } 1299 1300 ZGeneration::young()->register_flip_promoted(promoted_pages); 1301 } 1302 }; 1303 1304 void ZRelocate::flip_age_pages(const ZArray<ZPage*>* pages) { 1305 ZFlipAgePagesTask flip_age_task(pages); 1306 workers()->run(&flip_age_task); 1307 } 1308 1309 void ZRelocate::synchronize() { 1310 _queue.synchronize(); 1311 } 1312 1313 void ZRelocate::desynchronize() { 1314 _queue.desynchronize(); 1315 } 1316 1317 ZRelocateQueue* ZRelocate::queue() { 1318 return &_queue; 1319 }