1 /* 2 * Copyright (c) 2021, Amazon.com, Inc. or its affiliates. All rights reserved. 3 * 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 * 24 */ 25 26 #ifndef SHARE_GC_SHENANDOAH_SHENANDOAHSCANREMEMBEREDINLINE_HPP 27 #define SHARE_GC_SHENANDOAH_SHENANDOAHSCANREMEMBEREDINLINE_HPP 28 29 #include "memory/iterator.hpp" 30 #include "oops/oop.hpp" 31 #include "oops/objArrayOop.hpp" 32 #include "gc/shared/collectorCounters.hpp" 33 #include "gc/shenandoah/shenandoahCardStats.hpp" 34 #include "gc/shenandoah/shenandoahCardTable.hpp" 35 #include "gc/shenandoah/shenandoahHeap.hpp" 36 #include "gc/shenandoah/shenandoahHeapRegion.hpp" 37 #include "gc/shenandoah/shenandoahScanRemembered.hpp" 38 39 inline size_t 40 ShenandoahDirectCardMarkRememberedSet::last_valid_index() { 41 return _card_table->last_valid_index(); 42 } 43 44 inline size_t 45 ShenandoahDirectCardMarkRememberedSet::total_cards() { 46 return _total_card_count; 47 } 48 49 inline size_t 50 ShenandoahDirectCardMarkRememberedSet::card_index_for_addr(HeapWord *p) { 51 return _card_table->index_for(p); 52 } 53 54 inline HeapWord * 55 ShenandoahDirectCardMarkRememberedSet::addr_for_card_index(size_t card_index) { 56 return _whole_heap_base + CardTable::card_size_in_words() * card_index; 57 } 58 59 inline bool 60 ShenandoahDirectCardMarkRememberedSet::is_write_card_dirty(size_t card_index) { 61 uint8_t *bp = &(_card_table->write_byte_map())[card_index]; 62 return (bp[0] == CardTable::dirty_card_val()); 63 } 64 65 inline bool 66 ShenandoahDirectCardMarkRememberedSet::is_card_dirty(size_t card_index) { 67 uint8_t *bp = &(_card_table->read_byte_map())[card_index]; 68 return (bp[0] == CardTable::dirty_card_val()); 69 } 70 71 inline void 72 ShenandoahDirectCardMarkRememberedSet::mark_card_as_dirty(size_t card_index) { 73 uint8_t *bp = &(_card_table->write_byte_map())[card_index]; 74 bp[0] = CardTable::dirty_card_val(); 75 } 76 77 inline void 78 ShenandoahDirectCardMarkRememberedSet::mark_range_as_dirty(size_t card_index, size_t num_cards) { 79 uint8_t *bp = &(_card_table->write_byte_map())[card_index]; 80 while (num_cards-- > 0) { 81 *bp++ = CardTable::dirty_card_val(); 82 } 83 } 84 85 inline void 86 ShenandoahDirectCardMarkRememberedSet::mark_card_as_clean(size_t card_index) { 87 uint8_t *bp = &(_card_table->write_byte_map())[card_index]; 88 bp[0] = CardTable::clean_card_val(); 89 } 90 91 inline void 92 ShenandoahDirectCardMarkRememberedSet::mark_range_as_clean(size_t card_index, size_t num_cards) { 93 uint8_t *bp = &(_card_table->write_byte_map())[card_index]; 94 while (num_cards-- > 0) { 95 *bp++ = CardTable::clean_card_val(); 96 } 97 } 98 99 inline bool 100 ShenandoahDirectCardMarkRememberedSet::is_card_dirty(HeapWord *p) { 101 size_t index = card_index_for_addr(p); 102 uint8_t *bp = &(_card_table->read_byte_map())[index]; 103 return (bp[0] == CardTable::dirty_card_val()); 104 } 105 106 inline void 107 ShenandoahDirectCardMarkRememberedSet::mark_card_as_dirty(HeapWord *p) { 108 size_t index = card_index_for_addr(p); 109 uint8_t *bp = &(_card_table->write_byte_map())[index]; 110 bp[0] = CardTable::dirty_card_val(); 111 } 112 113 inline void 114 ShenandoahDirectCardMarkRememberedSet::mark_range_as_dirty(HeapWord *p, size_t num_heap_words) { 115 uint8_t *bp = &(_card_table->write_byte_map_base())[uintptr_t(p) >> _card_shift]; 116 uint8_t *end_bp = &(_card_table->write_byte_map_base())[uintptr_t(p + num_heap_words) >> _card_shift]; 117 // If (p + num_heap_words) is not aligned on card boundary, we also need to dirty last card. 118 if (((unsigned long long) (p + num_heap_words)) & (CardTable::card_size() - 1)) { 119 end_bp++; 120 } 121 while (bp < end_bp) { 122 *bp++ = CardTable::dirty_card_val(); 123 } 124 } 125 126 inline void 127 ShenandoahDirectCardMarkRememberedSet::mark_card_as_clean(HeapWord *p) { 128 size_t index = card_index_for_addr(p); 129 uint8_t *bp = &(_card_table->write_byte_map())[index]; 130 bp[0] = CardTable::clean_card_val(); 131 } 132 133 inline void 134 ShenandoahDirectCardMarkRememberedSet::mark_read_card_as_clean(size_t index) { 135 uint8_t *bp = &(_card_table->read_byte_map())[index]; 136 bp[0] = CardTable::clean_card_val(); 137 } 138 139 inline void 140 ShenandoahDirectCardMarkRememberedSet::mark_range_as_clean(HeapWord *p, size_t num_heap_words) { 141 uint8_t *bp = &(_card_table->write_byte_map_base())[uintptr_t(p) >> _card_shift]; 142 uint8_t *end_bp = &(_card_table->write_byte_map_base())[uintptr_t(p + num_heap_words) >> _card_shift]; 143 // If (p + num_heap_words) is not aligned on card boundary, we also need to clean last card. 144 if (((unsigned long long) (p + num_heap_words)) & (CardTable::card_size() - 1)) { 145 end_bp++; 146 } 147 while (bp < end_bp) { 148 *bp++ = CardTable::clean_card_val(); 149 } 150 } 151 152 inline size_t 153 ShenandoahDirectCardMarkRememberedSet::cluster_count() { 154 return _cluster_count; 155 } 156 157 // No lock required because arguments align with card boundaries. 158 template<typename RememberedSet> 159 inline void 160 ShenandoahCardCluster<RememberedSet>::reset_object_range(HeapWord* from, HeapWord* to) { 161 assert(((((unsigned long long) from) & (CardTable::card_size() - 1)) == 0) && 162 ((((unsigned long long) to) & (CardTable::card_size() - 1)) == 0), 163 "reset_object_range bounds must align with card boundaries"); 164 size_t card_at_start = _rs->card_index_for_addr(from); 165 size_t num_cards = (to - from) / CardTable::card_size_in_words(); 166 167 for (size_t i = 0; i < num_cards; i++) { 168 object_starts[card_at_start + i].short_word = 0; 169 } 170 } 171 172 // Assume only one thread at a time registers objects pertaining to 173 // each card-table entry's range of memory. 174 template<typename RememberedSet> 175 inline void 176 ShenandoahCardCluster<RememberedSet>::register_object(HeapWord* address) { 177 shenandoah_assert_heaplocked(); 178 179 register_object_wo_lock(address); 180 } 181 182 template<typename RememberedSet> 183 inline void 184 ShenandoahCardCluster<RememberedSet>::register_object_wo_lock(HeapWord* address) { 185 size_t card_at_start = _rs->card_index_for_addr(address); 186 HeapWord *card_start_address = _rs->addr_for_card_index(card_at_start); 187 uint8_t offset_in_card = address - card_start_address; 188 189 if (!has_object(card_at_start)) { 190 set_has_object_bit(card_at_start); 191 set_first_start(card_at_start, offset_in_card); 192 set_last_start(card_at_start, offset_in_card); 193 } else { 194 if (offset_in_card < get_first_start(card_at_start)) 195 set_first_start(card_at_start, offset_in_card); 196 if (offset_in_card > get_last_start(card_at_start)) 197 set_last_start(card_at_start, offset_in_card); 198 } 199 } 200 201 template<typename RememberedSet> 202 inline void 203 ShenandoahCardCluster<RememberedSet>::coalesce_objects(HeapWord* address, size_t length_in_words) { 204 205 size_t card_at_start = _rs->card_index_for_addr(address); 206 HeapWord *card_start_address = _rs->addr_for_card_index(card_at_start); 207 size_t card_at_end = card_at_start + ((address + length_in_words) - card_start_address) / CardTable::card_size_in_words(); 208 209 if (card_at_start == card_at_end) { 210 // There are no changes to the get_first_start array. Either get_first_start(card_at_start) returns this coalesced object, 211 // or it returns an object that precedes the coalesced object. 212 if (card_start_address + get_last_start(card_at_start) < address + length_in_words) { 213 uint8_t coalesced_offset = static_cast<uint8_t>(address - card_start_address); 214 // The object that used to be the last object starting within this card is being subsumed within the coalesced 215 // object. Since we always coalesce entire objects, this condition only occurs if the last object ends before or at 216 // the end of the card's memory range and there is no object following this object. In this case, adjust last_start 217 // to represent the start of the coalesced range. 218 set_last_start(card_at_start, coalesced_offset); 219 } 220 // Else, no changes to last_starts information. Either get_last_start(card_at_start) returns the object that immediately 221 // follows the coalesced object, or it returns an object that follows the object immediately following the coalesced object. 222 } else { 223 uint8_t coalesced_offset = static_cast<uint8_t>(address - card_start_address); 224 if (get_last_start(card_at_start) > coalesced_offset) { 225 // Existing last start is being coalesced, create new last start 226 set_last_start(card_at_start, coalesced_offset); 227 } 228 // otherwise, get_last_start(card_at_start) must equal coalesced_offset 229 230 // All the cards between first and last get cleared. 231 for (size_t i = card_at_start + 1; i < card_at_end; i++) { 232 clear_has_object_bit(i); 233 } 234 235 uint8_t follow_offset = static_cast<uint8_t>((address + length_in_words) - _rs->addr_for_card_index(card_at_end)); 236 if (has_object(card_at_end) && (get_first_start(card_at_end) < follow_offset)) { 237 // It may be that after coalescing within this last card's memory range, the last card 238 // no longer holds an object. 239 if (get_last_start(card_at_end) >= follow_offset) { 240 set_first_start(card_at_end, follow_offset); 241 } else { 242 // last_start is being coalesced so this card no longer has any objects. 243 clear_has_object_bit(card_at_end); 244 } 245 } 246 // else 247 // card_at_end did not have an object, so it still does not have an object, or 248 // card_at_end had an object that starts after the coalesced object, so no changes required for card_at_end 249 250 } 251 } 252 253 254 template<typename RememberedSet> 255 inline size_t 256 ShenandoahCardCluster<RememberedSet>::get_first_start(size_t card_index) { 257 assert(has_object(card_index), "Can't get first start because no object starts here"); 258 return object_starts[card_index].offsets.first & FirstStartBits; 259 } 260 261 template<typename RememberedSet> 262 inline size_t 263 ShenandoahCardCluster<RememberedSet>::get_last_start(size_t card_index) { 264 assert(has_object(card_index), "Can't get last start because no object starts here"); 265 return object_starts[card_index].offsets.last; 266 } 267 268 template<typename RememberedSet> 269 inline size_t 270 ShenandoahScanRemembered<RememberedSet>::last_valid_index() { return _rs->last_valid_index(); } 271 272 template<typename RememberedSet> 273 inline size_t 274 ShenandoahScanRemembered<RememberedSet>::total_cards() { return _rs->total_cards(); } 275 276 template<typename RememberedSet> 277 inline size_t 278 ShenandoahScanRemembered<RememberedSet>::card_index_for_addr(HeapWord *p) { return _rs->card_index_for_addr(p); }; 279 280 template<typename RememberedSet> 281 inline HeapWord * 282 ShenandoahScanRemembered<RememberedSet>::addr_for_card_index(size_t card_index) { return _rs->addr_for_card_index(card_index); } 283 284 template<typename RememberedSet> 285 inline bool 286 ShenandoahScanRemembered<RememberedSet>::is_card_dirty(size_t card_index) { return _rs->is_card_dirty(card_index); } 287 288 template<typename RememberedSet> 289 inline void 290 ShenandoahScanRemembered<RememberedSet>::mark_card_as_dirty(size_t card_index) { _rs->mark_card_as_dirty(card_index); } 291 292 template<typename RememberedSet> 293 inline void 294 ShenandoahScanRemembered<RememberedSet>::mark_range_as_dirty(size_t card_index, size_t num_cards) { _rs->mark_range_as_dirty(card_index, num_cards); } 295 296 template<typename RememberedSet> 297 inline void 298 ShenandoahScanRemembered<RememberedSet>::mark_card_as_clean(size_t card_index) { _rs->mark_card_as_clean(card_index); } 299 300 template<typename RememberedSet> 301 inline void 302 ShenandoahScanRemembered<RememberedSet>::mark_range_as_clean(size_t card_index, size_t num_cards) { _rs->mark_range_as_clean(card_index, num_cards); } 303 304 template<typename RememberedSet> 305 inline bool 306 ShenandoahScanRemembered<RememberedSet>::is_card_dirty(HeapWord *p) { return _rs->is_card_dirty(p); } 307 308 template<typename RememberedSet> 309 inline void 310 ShenandoahScanRemembered<RememberedSet>::mark_card_as_dirty(HeapWord *p) { _rs->mark_card_as_dirty(p); } 311 312 template<typename RememberedSet> 313 inline void 314 ShenandoahScanRemembered<RememberedSet>::mark_range_as_dirty(HeapWord *p, size_t num_heap_words) { _rs->mark_range_as_dirty(p, num_heap_words); } 315 316 template<typename RememberedSet> 317 inline void 318 ShenandoahScanRemembered<RememberedSet>::mark_card_as_clean(HeapWord *p) { _rs->mark_card_as_clean(p); } 319 320 template<typename RememberedSet> 321 inline void 322 ShenandoahScanRemembered<RememberedSet>:: mark_range_as_clean(HeapWord *p, size_t num_heap_words) { _rs->mark_range_as_clean(p, num_heap_words); } 323 324 template<typename RememberedSet> 325 inline size_t 326 ShenandoahScanRemembered<RememberedSet>::cluster_count() { return _rs->cluster_count(); } 327 328 template<typename RememberedSet> 329 inline void 330 ShenandoahScanRemembered<RememberedSet>::reset_object_range(HeapWord *from, HeapWord *to) { 331 _scc->reset_object_range(from, to); 332 } 333 334 template<typename RememberedSet> 335 inline void 336 ShenandoahScanRemembered<RememberedSet>::register_object(HeapWord *addr) { 337 _scc->register_object(addr); 338 } 339 340 template<typename RememberedSet> 341 inline void 342 ShenandoahScanRemembered<RememberedSet>::register_object_wo_lock(HeapWord *addr) { 343 _scc->register_object_wo_lock(addr); 344 } 345 346 template <typename RememberedSet> 347 inline bool 348 ShenandoahScanRemembered<RememberedSet>::verify_registration(HeapWord* address, ShenandoahMarkingContext* ctx) { 349 350 size_t index = card_index_for_addr(address); 351 if (!_scc->has_object(index)) { 352 return false; 353 } 354 HeapWord* base_addr = addr_for_card_index(index); 355 size_t offset = _scc->get_first_start(index); 356 ShenandoahHeap* heap = ShenandoahHeap::heap(); 357 358 // Verify that I can find this object within its enclosing card by scanning forward from first_start. 359 while (base_addr + offset < address) { 360 oop obj = cast_to_oop(base_addr + offset); 361 if (!ctx || ctx->is_marked(obj)) { 362 offset += obj->size(); 363 } else { 364 // If this object is not live, don't trust its size(); all objects above tams are live. 365 ShenandoahHeapRegion* r = heap->heap_region_containing(obj); 366 HeapWord* tams = ctx->top_at_mark_start(r); 367 offset = ctx->get_next_marked_addr(base_addr + offset, tams) - base_addr; 368 } 369 } 370 if (base_addr + offset != address){ 371 return false; 372 } 373 374 // At this point, offset represents object whose registration we are verifying. We know that at least this object resides 375 // within this card's memory. 376 377 // Make sure that last_offset is properly set for the enclosing card, but we can't verify this for 378 // candidate collection-set regions during mixed evacuations, so disable this check in general 379 // during mixed evacuations. 380 381 ShenandoahHeapRegion* r = heap->heap_region_containing(base_addr + offset); 382 size_t max_offset = r->top() - base_addr; 383 if (max_offset > CardTable::card_size_in_words()) { 384 max_offset = CardTable::card_size_in_words(); 385 } 386 size_t prev_offset; 387 if (!ctx) { 388 do { 389 oop obj = cast_to_oop(base_addr + offset); 390 prev_offset = offset; 391 offset += obj->size(); 392 } while (offset < max_offset); 393 if (_scc->get_last_start(index) != prev_offset) { 394 return false; 395 } 396 397 // base + offset represents address of first object that starts on following card, if there is one. 398 399 // Notes: base_addr is addr_for_card_index(index) 400 // base_addr + offset is end of the object we are verifying 401 // cannot use card_index_for_addr(base_addr + offset) because it asserts arg < end of whole heap 402 size_t end_card_index = index + offset / CardTable::card_size_in_words(); 403 404 if (end_card_index > index && end_card_index <= _rs->last_valid_index()) { 405 // If there is a following object registered on the next card, it should begin where this object ends. 406 if (_scc->has_object(end_card_index) && 407 ((addr_for_card_index(end_card_index) + _scc->get_first_start(end_card_index)) != (base_addr + offset))) { 408 return false; 409 } 410 } 411 412 // Assure that no other objects are registered "inside" of this one. 413 for (index++; index < end_card_index; index++) { 414 if (_scc->has_object(index)) { 415 return false; 416 } 417 } 418 } else { 419 // This is a mixed evacuation or a global collect: rely on mark bits to identify which objects need to be properly registered 420 assert(!ShenandoahHeap::heap()->is_concurrent_old_mark_in_progress(), "Cannot rely on mark context here."); 421 // If the object reaching or spanning the end of this card's memory is marked, then last_offset for this card 422 // should represent this object. Otherwise, last_offset is a don't care. 423 ShenandoahHeapRegion* region = heap->heap_region_containing(base_addr + offset); 424 HeapWord* tams = ctx->top_at_mark_start(region); 425 oop last_obj = nullptr; 426 do { 427 oop obj = cast_to_oop(base_addr + offset); 428 if (ctx->is_marked(obj)) { 429 prev_offset = offset; 430 offset += obj->size(); 431 last_obj = obj; 432 } else { 433 offset = ctx->get_next_marked_addr(base_addr + offset, tams) - base_addr; 434 // If there are no marked objects remaining in this region, offset equals tams - base_addr. If this offset is 435 // greater than max_offset, we will immediately exit this loop. Otherwise, the next iteration of the loop will 436 // treat the object at offset as marked and live (because address >= tams) and we will continue iterating object 437 // by consulting the size() fields of each. 438 } 439 } while (offset < max_offset); 440 if (last_obj != nullptr && prev_offset + last_obj->size() >= max_offset) { 441 // last marked object extends beyond end of card 442 if (_scc->get_last_start(index) != prev_offset) { 443 return false; 444 } 445 // otherwise, the value of _scc->get_last_start(index) is a don't care because it represents a dead object and we 446 // cannot verify its context 447 } 448 } 449 return true; 450 } 451 452 template<typename RememberedSet> 453 inline void 454 ShenandoahScanRemembered<RememberedSet>::coalesce_objects(HeapWord *addr, size_t length_in_words) { 455 _scc->coalesce_objects(addr, length_in_words); 456 } 457 458 template<typename RememberedSet> 459 inline void 460 ShenandoahScanRemembered<RememberedSet>::mark_range_as_empty(HeapWord *addr, size_t length_in_words) { 461 _rs->mark_range_as_clean(addr, length_in_words); 462 _scc->clear_objects_in_range(addr, length_in_words); 463 } 464 465 template<typename RememberedSet> 466 template <typename ClosureType> 467 inline void ShenandoahScanRemembered<RememberedSet>::process_clusters(size_t first_cluster, size_t count, HeapWord *end_of_range, 468 ClosureType *cl, bool is_concurrent, uint worker_id) { 469 process_clusters(first_cluster, count, end_of_range, cl, false, is_concurrent, worker_id); 470 } 471 472 // Process all objects starting within count clusters beginning with first_cluster for which the start address is 473 // less than end_of_range. For any non-array object whose header lies on a dirty card, scan the entire object, 474 // even if its end reaches beyond end_of_range. Object arrays, on the other hand,s are precisely dirtied and only 475 // the portions of the array on dirty cards need to be scanned. 476 // 477 // Do not CANCEL within process_clusters. It is assumed that if a worker thread accepts responsbility for processing 478 // a chunk of work, it will finish the work it starts. Otherwise, the chunk of work will be lost in the transition to 479 // degenerated execution. 480 template<typename RememberedSet> 481 template <typename ClosureType> 482 void ShenandoahScanRemembered<RememberedSet>::process_clusters(size_t first_cluster, size_t count, HeapWord *end_of_range, 483 ClosureType *cl, bool write_table, bool is_concurrent, uint worker_id) { 484 485 // Unlike traditional Shenandoah marking, the old-gen resident objects that are examined as part of the remembered set are not 486 // always themselves marked. Each such object will be scanned exactly once. Any young-gen objects referenced from the remembered 487 // set will be marked and then subsequently scanned. 488 489 // If old-gen evacuation is active, then MarkingContext for old-gen heap regions is valid. We use the MarkingContext 490 // bits to determine which objects within a DIRTY card need to be scanned. This is necessary because old-gen heap 491 // regions that are in the candidate collection set have not been coalesced and filled. Thus, these heap regions 492 // may contain zombie objects. Zombie objects are known to be dead, but have not yet been "collected". Scanning 493 // zombie objects is unsafe because the Klass pointer is not reliable, objects referenced from a zombie may have been 494 // collected (if dead), or relocated (if live), or if dead but not yet collected, we don't want to "revive" them 495 // by marking them (when marking) or evacuating them (when updating refereces). 496 497 ShenandoahHeap* heap = ShenandoahHeap::heap(); 498 ShenandoahMarkingContext* ctx; 499 500 if (heap->is_old_bitmap_stable()) { 501 ctx = heap->marking_context(); 502 } else { 503 ctx = nullptr; 504 } 505 506 size_t cur_cluster = first_cluster; 507 size_t cur_count = count; 508 size_t card_index = cur_cluster * ShenandoahCardCluster<RememberedSet>::CardsPerCluster; 509 HeapWord* start_of_range = _rs->addr_for_card_index(card_index); 510 ShenandoahHeapRegion* r = heap->heap_region_containing(start_of_range); 511 assert(end_of_range <= r->top(), "process_clusters() examines one region at a time"); 512 513 NOT_PRODUCT(ShenandoahCardStats stats(ShenandoahCardCluster<RememberedSet>::CardsPerCluster, card_stats(worker_id));) 514 515 while (cur_count-- > 0) { 516 // TODO: do we want to check cancellation in inner loop, on every card processed? That would be more responsive, 517 // but require more overhead for checking. 518 card_index = cur_cluster * ShenandoahCardCluster<RememberedSet>::CardsPerCluster; 519 size_t end_card_index = card_index + ShenandoahCardCluster<RememberedSet>::CardsPerCluster; 520 cur_cluster++; 521 size_t next_card_index = 0; 522 523 assert(stats.is_clean(), "Error"); 524 while (card_index < end_card_index) { // TODO: understand why end_of_range is needed. 525 if (_rs->addr_for_card_index(card_index) > end_of_range) { 526 cur_count = 0; 527 card_index = end_card_index; 528 break; 529 } 530 bool is_dirty = (write_table)? is_write_card_dirty(card_index): is_card_dirty(card_index); 531 bool has_object = _scc->has_object(card_index); 532 NOT_PRODUCT(stats.increment_card_cnt(is_dirty);) 533 if (is_dirty) { 534 size_t prev_card_index = card_index; 535 if (has_object) { 536 // Scan all objects that start within this card region. 537 size_t start_offset = _scc->get_first_start(card_index); 538 HeapWord *p = _rs->addr_for_card_index(card_index); 539 HeapWord *card_start = p; 540 HeapWord *endp = p + CardTable::card_size_in_words(); 541 assert(!r->is_humongous(), "Process humongous regions elsewhere"); 542 543 if (endp > end_of_range) { 544 endp = end_of_range; 545 next_card_index = end_card_index; 546 } else { 547 // endp either points to start of next card region, or to the next object that needs to be scanned, which may 548 // reside in some successor card region. 549 550 // Can't use _scc->card_index_for_addr(endp) here because it crashes with assertion 551 // failure if endp points to end of heap. 552 next_card_index = card_index + (endp - card_start) / CardTable::card_size_in_words(); 553 } 554 555 p += start_offset; 556 while (p < endp) { 557 oop obj = cast_to_oop(p); 558 NOT_PRODUCT(stats.increment_obj_cnt(is_dirty);) 559 560 // ctx->is_marked() returns true if mark bit set or if obj above TAMS. 561 if (!ctx || ctx->is_marked(obj)) { 562 // Future TODO: 563 // For improved efficiency, we might want to give special handling of obj->is_objArray(). In 564 // particular, in that case, we might want to divide the effort for scanning of a very long object array 565 // between multiple threads. Also, skip parts of the array that are not marked as dirty. 566 if (obj->is_objArray()) { 567 objArrayOop array = objArrayOop(obj); 568 int len = array->length(); 569 array->oop_iterate_range(cl, 0, len); 570 NOT_PRODUCT(stats.increment_scan_cnt(is_dirty);) 571 } else if (obj->is_instance()) { 572 obj->oop_iterate(cl); 573 NOT_PRODUCT(stats.increment_scan_cnt(is_dirty);) 574 } else { 575 // Case 3: Primitive array. Do nothing, no oops there. We use the same 576 // performance tweak TypeArrayKlass::oop_oop_iterate_impl is using: 577 // We skip iterating over the klass pointer since we know that 578 // Universe::TypeArrayKlass never moves. 579 assert (obj->is_typeArray(), "should be type array"); 580 } 581 p += obj->size(); 582 } else { 583 // This object is not marked so we don't scan it. Containing region r is initialized above. 584 HeapWord* tams = ctx->top_at_mark_start(r); 585 if (p >= tams) { 586 p += obj->size(); 587 } else { 588 p = ctx->get_next_marked_addr(p, tams); 589 } 590 } 591 } 592 if (p > endp) { 593 card_index = card_index + (p - card_start) / CardTable::card_size_in_words(); 594 } else { // p == endp 595 card_index = next_card_index; 596 } 597 } else { 598 // Card is dirty but has no object. Card will have been scanned during scan of a previous cluster. 599 card_index++; 600 } 601 } else { 602 if (has_object) { 603 // Card is clean but has object. 604 // Scan the last object that starts within this card memory if it spans at least one dirty card within this cluster 605 // or if it reaches into the next cluster. 606 size_t start_offset = _scc->get_last_start(card_index); 607 HeapWord *card_start = _rs->addr_for_card_index(card_index); 608 HeapWord *p = card_start + start_offset; 609 oop obj = cast_to_oop(p); 610 611 size_t last_card; 612 if (!ctx || ctx->is_marked(obj)) { 613 HeapWord *nextp = p + obj->size(); 614 NOT_PRODUCT(stats.increment_obj_cnt(is_dirty);) 615 616 // Can't use _scc->card_index_for_addr(endp) here because it crashes with assertion 617 // failure if nextp points to end of heap. Must also not attempt to read past last 618 // valid index for card table. 619 last_card = card_index + (nextp - card_start) / CardTable::card_size_in_words(); 620 last_card = MIN2(last_card, last_valid_index()); 621 622 bool reaches_next_cluster = (last_card > end_card_index); 623 bool spans_dirty_within_this_cluster = false; 624 625 if (!reaches_next_cluster) { 626 for (size_t span_card = card_index+1; span_card <= last_card; span_card++) { 627 if ((write_table)? _rs->is_write_card_dirty(span_card): _rs->is_card_dirty(span_card)) { 628 spans_dirty_within_this_cluster = true; 629 break; 630 } 631 } 632 } 633 634 // TODO: only iterate over this object if it spans dirty within this cluster or within following clusters. 635 // Code as written is known not to examine a zombie object because either the object is marked, or we are 636 // not using the mark-context to differentiate objects, so the object is known to have been coalesced and 637 // filled if it is not "live". 638 639 if (reaches_next_cluster || spans_dirty_within_this_cluster) { 640 if (obj->is_objArray()) { 641 objArrayOop array = objArrayOop(obj); 642 int len = array->length(); 643 array->oop_iterate_range(cl, 0, len); 644 NOT_PRODUCT(stats.increment_scan_cnt(is_dirty);) 645 } else if (obj->is_instance()) { 646 obj->oop_iterate(cl); 647 NOT_PRODUCT(stats.increment_scan_cnt(is_dirty);) 648 } else { 649 // Case 3: Primitive array. Do nothing, no oops there. We use the same 650 // performance tweak TypeArrayKlass::oop_oop_iterate_impl is using: 651 // We skip iterating over the klass pointer since we know that 652 // Universe::TypeArrayKlass never moves. 653 assert (obj->is_typeArray(), "should be type array"); 654 } 655 } 656 } else { 657 // The object that spans end of this clean card is not marked, so no need to scan it or its 658 // unmarked neighbors. Containing region r is initialized above. 659 HeapWord* tams = ctx->top_at_mark_start(r); 660 HeapWord* nextp; 661 if (p >= tams) { 662 nextp = p + obj->size(); 663 } else { 664 nextp = ctx->get_next_marked_addr(p, tams); 665 } 666 last_card = card_index + (nextp - card_start) / CardTable::card_size_in_words(); 667 } 668 // Increment card_index to account for the spanning object, even if we didn't scan it. 669 card_index = (last_card > card_index)? last_card: card_index + 1; 670 } else { 671 // Card is clean and has no object. No need to clean this card. 672 card_index++; 673 } 674 } 675 } // end of a range of cards in current cluster 676 NOT_PRODUCT(stats.update_run(true /* record */);) 677 } // end of all clusters 678 } 679 680 // Given that this range of clusters is known to span a humongous object spanned by region r, scan the 681 // portion of the humongous object that corresponds to the specified range. 682 template<typename RememberedSet> 683 template <typename ClosureType> 684 inline void 685 ShenandoahScanRemembered<RememberedSet>::process_humongous_clusters(ShenandoahHeapRegion* r, size_t first_cluster, size_t count, 686 HeapWord *end_of_range, ClosureType *cl, bool write_table, 687 bool is_concurrent) { 688 ShenandoahHeapRegion* start_region = r->humongous_start_region(); 689 HeapWord* p = start_region->bottom(); 690 oop obj = cast_to_oop(p); 691 assert(r->is_humongous(), "Only process humongous regions here"); 692 assert(start_region->is_humongous_start(), "Should be start of humongous region"); 693 assert(p + obj->size() >= end_of_range, "Humongous object ends before range ends"); 694 695 size_t first_card_index = first_cluster * ShenandoahCardCluster<RememberedSet>::CardsPerCluster; 696 HeapWord* first_cluster_addr = _rs->addr_for_card_index(first_card_index); 697 size_t spanned_words = count * ShenandoahCardCluster<RememberedSet>::CardsPerCluster * CardTable::card_size_in_words(); 698 start_region->oop_iterate_humongous_slice(cl, true, first_cluster_addr, spanned_words, write_table, is_concurrent); 699 } 700 701 template<typename RememberedSet> 702 template <typename ClosureType> 703 inline void 704 ShenandoahScanRemembered<RememberedSet>::process_region_slice(ShenandoahHeapRegion *region, size_t start_offset, size_t clusters, 705 HeapWord *end_of_range, ClosureType *cl, bool use_write_table, 706 bool is_concurrent, uint worker_id) { 707 HeapWord *start_of_range = region->bottom() + start_offset; 708 size_t cluster_size = 709 CardTable::card_size_in_words() * ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster; 710 size_t words = clusters * cluster_size; 711 size_t start_cluster_no = cluster_for_addr(start_of_range); 712 assert(addr_for_cluster(start_cluster_no) == start_of_range, "process_region_slice range must align on cluster boundary"); 713 714 // region->end() represents the end of memory spanned by this region, but not all of this 715 // memory is eligible to be scanned because some of this memory has not yet been allocated. 716 // 717 // region->top() represents the end of allocated memory within this region. Any addresses 718 // beyond region->top() should not be scanned as that memory does not hold valid objects. 719 720 if (use_write_table) { 721 // This is update-refs servicing. 722 if (end_of_range > region->get_update_watermark()) { 723 end_of_range = region->get_update_watermark(); 724 } 725 } else { 726 // This is concurrent mark servicing. Note that TAMS for this region is TAMS at start of old-gen 727 // collection. Here, we need to scan up to TAMS for most recently initiated young-gen collection. 728 // Since all LABs are retired at init mark, and since replacement LABs are allocated lazily, and since no 729 // promotions occur until evacuation phase, TAMS for most recent young-gen is same as top(). 730 if (end_of_range > region->top()) { 731 end_of_range = region->top(); 732 } 733 } 734 735 log_debug(gc)("Remembered set scan processing Region " SIZE_FORMAT ", from " PTR_FORMAT " to " PTR_FORMAT ", using %s table", 736 region->index(), p2i(start_of_range), p2i(end_of_range), 737 use_write_table? "read/write (updating)": "read (marking)"); 738 739 // Note that end_of_range may point to the middle of a cluster because region->top() or region->get_update_watermark() may 740 // be less than start_of_range + words. 741 742 // We want to assure that our process_clusters() request spans all relevant clusters. Note that each cluster 743 // processed will avoid processing beyond end_of_range. 744 745 // Note that any object that starts between start_of_range and end_of_range, including humongous objects, will 746 // be fully processed by process_clusters, even though the object may reach beyond end_of_range. 747 748 // If I am assigned to process a range that starts beyond end_of_range (top or update-watermark), we have no work to do. 749 750 if (start_of_range < end_of_range) { 751 if (region->is_humongous()) { 752 ShenandoahHeapRegion* start_region = region->humongous_start_region(); 753 process_humongous_clusters(start_region, start_cluster_no, clusters, end_of_range, cl, use_write_table, is_concurrent); 754 } else { 755 process_clusters(start_cluster_no, clusters, end_of_range, cl, use_write_table, is_concurrent, worker_id); 756 } 757 } 758 } 759 760 template<typename RememberedSet> 761 inline size_t 762 ShenandoahScanRemembered<RememberedSet>::cluster_for_addr(HeapWordImpl **addr) { 763 size_t card_index = _rs->card_index_for_addr(addr); 764 size_t result = card_index / ShenandoahCardCluster<RememberedSet>::CardsPerCluster; 765 return result; 766 } 767 768 template<typename RememberedSet> 769 inline HeapWord* 770 ShenandoahScanRemembered<RememberedSet>::addr_for_cluster(size_t cluster_no) { 771 size_t card_index = cluster_no * ShenandoahCardCluster<RememberedSet>::CardsPerCluster; 772 return addr_for_card_index(card_index); 773 } 774 775 // This is used only for debug verification so don't worry about making the scan parallel. 776 template<typename RememberedSet> 777 void ShenandoahScanRemembered<RememberedSet>::roots_do(OopIterateClosure* cl) { 778 ShenandoahHeap* heap = ShenandoahHeap::heap(); 779 for (size_t i = 0, n = heap->num_regions(); i < n; ++i) { 780 ShenandoahHeapRegion* region = heap->get_region(i); 781 if (region->is_old() && region->is_active() && !region->is_cset()) { 782 HeapWord* start_of_range = region->bottom(); 783 HeapWord* end_of_range = region->top(); 784 size_t start_cluster_no = cluster_for_addr(start_of_range); 785 size_t num_heapwords = end_of_range - start_of_range; 786 unsigned int cluster_size = CardTable::card_size_in_words() * 787 ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster; 788 size_t num_clusters = (size_t) ((num_heapwords - 1 + cluster_size) / cluster_size); 789 790 // Remembered set scanner 791 if (region->is_humongous()) { 792 process_humongous_clusters(region->humongous_start_region(), start_cluster_no, num_clusters, end_of_range, cl, 793 false /* is_write_table */, false /* is_concurrent */); 794 } else { 795 process_clusters(start_cluster_no, num_clusters, end_of_range, cl, false /* is_concurrent */, 0); 796 } 797 } 798 } 799 } 800 801 #ifndef PRODUCT 802 // Log given card stats 803 template<typename RememberedSet> 804 inline void ShenandoahScanRemembered<RememberedSet>::log_card_stats(HdrSeq* stats) { 805 for (int i = 0; i < MAX_CARD_STAT_TYPE; i++) { 806 log_info(gc, remset)("%18s: [ %8.2f %8.2f %8.2f %8.2f %8.2f ]", 807 _card_stats_name[i], 808 stats[i].percentile(0), stats[i].percentile(25), 809 stats[i].percentile(50), stats[i].percentile(75), 810 stats[i].maximum()); 811 } 812 } 813 814 // Log card stats for all nworkers for a specific phase t 815 template<typename RememberedSet> 816 void ShenandoahScanRemembered<RememberedSet>::log_card_stats(uint nworkers, CardStatLogType t) { 817 assert(ShenandoahEnableCardStats, "Do not call"); 818 HdrSeq* cum_stats = card_stats_for_phase(t); 819 log_info(gc, remset)("%s", _card_stat_log_type[t]); 820 for (uint i = 0; i < nworkers; i++) { 821 log_worker_card_stats(i, cum_stats); 822 } 823 824 // Every so often, log the cumulative global stats 825 if (++_card_stats_log_counter[t] >= ShenandoahCardStatsLogInterval) { 826 _card_stats_log_counter[t] = 0; 827 log_info(gc, remset)("Cumulative stats"); 828 log_card_stats(cum_stats); 829 } 830 } 831 832 // Log card stats for given worker_id, & clear them after merging into given cumulative stats 833 template<typename RememberedSet> 834 void ShenandoahScanRemembered<RememberedSet>::log_worker_card_stats(uint worker_id, HdrSeq* cum_stats) { 835 assert(ShenandoahEnableCardStats, "Do not call"); 836 837 HdrSeq* worker_card_stats = card_stats(worker_id); 838 log_info(gc, remset)("Worker %u Card Stats: ", worker_id); 839 log_card_stats(worker_card_stats); 840 // Merge worker stats into the cumulative stats & clear worker stats 841 merge_worker_card_stats_cumulative(worker_card_stats, cum_stats); 842 } 843 844 template<typename RememberedSet> 845 void ShenandoahScanRemembered<RememberedSet>::merge_worker_card_stats_cumulative( 846 HdrSeq* worker_stats, HdrSeq* cum_stats) { 847 for (int i = 0; i < MAX_CARD_STAT_TYPE; i++) { 848 worker_stats[i].merge(cum_stats[i]); 849 } 850 } 851 #endif 852 853 inline bool ShenandoahRegionChunkIterator::has_next() const { 854 return _index < _total_chunks; 855 } 856 857 inline bool ShenandoahRegionChunkIterator::next(struct ShenandoahRegionChunk *assignment) { 858 if (_index > _total_chunks) { 859 return false; 860 } 861 size_t new_index = Atomic::add(&_index, (size_t) 1, memory_order_relaxed); 862 if (new_index > _total_chunks) { 863 return false; 864 } 865 // convert to zero-based indexing 866 new_index--; 867 868 size_t group_no; 869 for (group_no = 0; new_index >= _group_entries[group_no]; group_no++) 870 ; 871 872 assert(group_no < _num_groups, "Cannot have group no greater or equal to _num_groups"); 873 874 // All size computations measured in HeapWord 875 size_t region_size_words = ShenandoahHeapRegion::region_size_words(); 876 size_t group_region_index = _region_index[group_no]; 877 size_t group_region_offset = _group_offset[group_no]; 878 879 size_t index_within_group = (group_no == 0)? new_index: new_index - _group_entries[group_no - 1]; 880 size_t group_chunk_size = _group_chunk_size[group_no]; 881 size_t offset_of_this_chunk = group_region_offset + index_within_group * group_chunk_size; 882 size_t regions_spanned_by_chunk_offset = offset_of_this_chunk / region_size_words; 883 size_t offset_within_region = offset_of_this_chunk % region_size_words; 884 885 size_t region_index = group_region_index + regions_spanned_by_chunk_offset; 886 887 assignment->_r = _heap->get_region(region_index); 888 assignment->_chunk_offset = offset_within_region; 889 assignment->_chunk_size = group_chunk_size; 890 return true; 891 } 892 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHSCANREMEMBEREDINLINE_HPP