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/shenandoahCardTable.hpp"
 34 #include "gc/shenandoah/shenandoahHeap.hpp"
 35 #include "gc/shenandoah/shenandoahHeapRegion.hpp"
 36 #include "gc/shenandoah/shenandoahScanRemembered.hpp"
 37 
 38 inline size_t
 39 ShenandoahDirectCardMarkRememberedSet::total_cards() {
 40   return _total_card_count;
 41 }
 42 
 43 inline size_t
 44 ShenandoahDirectCardMarkRememberedSet::card_index_for_addr(HeapWord *p) {
 45   return _card_table->index_for(p);
 46 }
 47 
 48 inline HeapWord *
 49 ShenandoahDirectCardMarkRememberedSet::addr_for_card_index(size_t card_index) {
 50   return _whole_heap_base + CardTable::card_size_in_words * card_index;
 51 }
 52 
 53 inline bool
 54 ShenandoahDirectCardMarkRememberedSet::is_write_card_dirty(size_t card_index) {
 55   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 56   return (bp[0] == CardTable::dirty_card_val());
 57 }
 58 
 59 inline bool
 60 ShenandoahDirectCardMarkRememberedSet::is_card_dirty(size_t card_index) {
 61   uint8_t *bp = &(_card_table->read_byte_map())[card_index];
 62   return (bp[0] == CardTable::dirty_card_val());
 63 }
 64 
 65 inline void
 66 ShenandoahDirectCardMarkRememberedSet::mark_card_as_dirty(size_t card_index) {
 67   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 68   bp[0] = CardTable::dirty_card_val();
 69 }
 70 
 71 inline void
 72 ShenandoahDirectCardMarkRememberedSet::mark_range_as_dirty(size_t card_index, size_t num_cards) {
 73   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 74   while (num_cards-- > 0) {
 75     *bp++ = CardTable::dirty_card_val();
 76   }
 77 }
 78 
 79 inline void
 80 ShenandoahDirectCardMarkRememberedSet::mark_card_as_clean(size_t card_index) {
 81   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 82   bp[0] = CardTable::clean_card_val();
 83 }
 84 
 85 inline void
 86 ShenandoahDirectCardMarkRememberedSet::mark_range_as_clean(size_t card_index, size_t num_cards) {
 87   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 88   while (num_cards-- > 0) {
 89     *bp++ = CardTable::clean_card_val();
 90   }
 91 }
 92 
 93 inline void
 94 ShenandoahDirectCardMarkRememberedSet::mark_overreach_card_as_dirty(size_t card_index) {
 95   uint8_t *bp = &_overreach_map[card_index];
 96   bp[0] = CardTable::dirty_card_val();
 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 void
153 ShenandoahDirectCardMarkRememberedSet::mark_overreach_card_as_dirty(void *p) {
154   uint8_t *bp = &_overreach_map_base[uintptr_t(p) >> _card_shift];
155   bp[0] = CardTable::dirty_card_val();
156 }
157 
158 inline size_t
159 ShenandoahDirectCardMarkRememberedSet::cluster_count() {
160   return _cluster_count;
161 }
162 
163 // No lock required because arguments align with card boundaries.
164 template<typename RememberedSet>
165 inline void
166 ShenandoahCardCluster<RememberedSet>::reset_object_range(HeapWord* from, HeapWord* to) {
167   assert(((((unsigned long long) from) & (CardTable::card_size - 1)) == 0) &&
168          ((((unsigned long long) to) & (CardTable::card_size - 1)) == 0),
169          "reset_object_range bounds must align with card boundaries");
170   size_t card_at_start = _rs->card_index_for_addr(from);
171   size_t num_cards = (to - from) / CardTable::card_size_in_words;
172 
173   for (size_t i = 0; i < num_cards; i++) {
174     object_starts[card_at_start + i] = 0;
175   }
176 }
177 
178 // Assume only one thread at a time registers objects pertaining to
179 // each card-table entry's range of memory.
180 template<typename RememberedSet>
181 inline void
182 ShenandoahCardCluster<RememberedSet>::register_object(HeapWord* address) {
183   shenandoah_assert_heaplocked();
184   register_object_wo_lock(address);
185 }
186 
187 template<typename RememberedSet>
188 inline void
189 ShenandoahCardCluster<RememberedSet>::register_object_wo_lock(HeapWord* address) {
190   size_t card_at_start = _rs->card_index_for_addr(address);
191   HeapWord *card_start_address = _rs->addr_for_card_index(card_at_start);
192   uint8_t offset_in_card = address - card_start_address;
193 
194   if ((object_starts[card_at_start] & ObjectStartsInCardRegion) == 0) {
195     set_has_object_bit(card_at_start);
196     set_first_start(card_at_start, offset_in_card);
197     set_last_start(card_at_start, offset_in_card);
198   } else {
199     if (offset_in_card < get_first_start(card_at_start))
200       set_first_start(card_at_start, offset_in_card);
201     if (offset_in_card > get_last_start(card_at_start))
202       set_last_start(card_at_start, offset_in_card);
203   }
204 }
205 
206 template<typename RememberedSet>
207 inline void
208 ShenandoahCardCluster<RememberedSet>::coalesce_objects(HeapWord* address, size_t length_in_words) {
209 
210   size_t card_at_start = _rs->card_index_for_addr(address);
211   HeapWord *card_start_address = _rs->addr_for_card_index(card_at_start);
212   size_t card_at_end = card_at_start + ((address + length_in_words) - card_start_address) / CardTable::card_size_in_words;
213 
214   if (card_at_start == card_at_end) {
215     // No changes to object_starts array.  Either:
216     //  get_first_start(card_at_start) returns this coalesced object,
217     //    or it returns an object that precedes the coalesced object.
218     //  get_last_start(card_at_start) returns the object that immediately follows the coalesced object,
219     //    or it returns an object that comes after the object immediately following the coalesced object.
220   } else {
221     uint8_t coalesced_offset = static_cast<uint8_t>(address - card_start_address);
222     if (get_last_start(card_at_start) > coalesced_offset) {
223       // Existing last start is being coalesced, create new last start
224       set_last_start(card_at_start, coalesced_offset);
225     }
226     // otherwise, get_last_start(card_at_start) must equal coalesced_offset
227 
228     // All the cards between first and last get cleared.
229     for (size_t i = card_at_start + 1; i < card_at_end; i++) {
230       clear_has_object_bit(i);
231     }
232 
233     uint8_t follow_offset = static_cast<uint8_t>((address + length_in_words) - _rs->addr_for_card_index(card_at_end));
234     if (has_object(card_at_end) && (get_first_start(card_at_end) < follow_offset)) {
235       // It may be that after coalescing within this last card's memory range, the last card
236       // no longer holds an object.
237       if (get_last_start(card_at_end) >= follow_offset) {
238         set_first_start(card_at_end, follow_offset);
239       } else {
240         // last_start is being coalesced so this card no longer has any objects.
241         clear_has_object_bit(card_at_end);
242       }
243     }
244     // else
245     //  card_at_end did not have an object, so it still does not have an object, or
246     //  card_at_end had an object that starts after the coalesced object, so no changes required for card_at_end
247 
248   }
249 }
250 
251 
252 template<typename RememberedSet>
253 inline bool
254 ShenandoahCardCluster<RememberedSet>::has_object(size_t card_index) {
255   return object_starts[card_index] & ObjectStartsInCardRegion;
256 }
257 
258 template<typename RememberedSet>
259 inline size_t
260 ShenandoahCardCluster<RememberedSet>::get_first_start(size_t card_index) {
261   assert(object_starts[card_index] & ObjectStartsInCardRegion, "Can't get first start because no object starts here");
262   return (object_starts[card_index] & FirstStartBits) >> FirstStartShift;
263 }
264 
265 template<typename RememberedSet>
266 inline size_t
267 ShenandoahCardCluster<RememberedSet>::get_last_start(size_t card_index) {
268   assert(object_starts[card_index] & ObjectStartsInCardRegion, "Can't get last start because no objects starts here");
269   return (object_starts[card_index] & LastStartBits) >> LastStartShift;
270 }
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 void
306 ShenandoahScanRemembered<RememberedSet>:: mark_overreach_card_as_dirty(size_t card_index) { _rs->mark_overreach_card_as_dirty(card_index); }
307 
308 template<typename RememberedSet>
309 inline bool
310 ShenandoahScanRemembered<RememberedSet>::is_card_dirty(HeapWord *p) { return _rs->is_card_dirty(p); }
311 
312 template<typename RememberedSet>
313 inline void
314 ShenandoahScanRemembered<RememberedSet>::mark_card_as_dirty(HeapWord *p) { _rs->mark_card_as_dirty(p); }
315 
316 template<typename RememberedSet>
317 inline void
318 ShenandoahScanRemembered<RememberedSet>::mark_range_as_dirty(HeapWord *p, size_t num_heap_words) { _rs->mark_range_as_dirty(p, num_heap_words); }
319 
320 template<typename RememberedSet>
321 inline void
322 ShenandoahScanRemembered<RememberedSet>::mark_card_as_clean(HeapWord *p) { _rs->mark_card_as_clean(p); }
323 
324 template<typename RememberedSet>
325 inline void
326 ShenandoahScanRemembered<RememberedSet>:: mark_range_as_clean(HeapWord *p, size_t num_heap_words) { _rs->mark_range_as_clean(p, num_heap_words); }
327 
328 template<typename RememberedSet>
329 inline void
330 ShenandoahScanRemembered<RememberedSet>::mark_overreach_card_as_dirty(void *p) { _rs->mark_overreach_card_as_dirty(p); }
331 
332 template<typename RememberedSet>
333 inline size_t
334 ShenandoahScanRemembered<RememberedSet>::cluster_count() { return _rs->cluster_count(); }
335 
336 template<typename RememberedSet>
337 inline void
338 ShenandoahScanRemembered<RememberedSet>::initialize_overreach(size_t first_cluster, size_t count) { _rs->initialize_overreach(first_cluster, count); }
339 
340 template<typename RememberedSet>
341 inline void
342 ShenandoahScanRemembered<RememberedSet>::merge_overreach(size_t first_cluster, size_t count) { _rs->merge_overreach(first_cluster, count); }
343 
344 template<typename RememberedSet>
345 inline void
346 ShenandoahScanRemembered<RememberedSet>::reset_object_range(HeapWord *from, HeapWord *to) {
347   _scc->reset_object_range(from, to);
348 }
349 
350 template<typename RememberedSet>
351 inline void
352 ShenandoahScanRemembered<RememberedSet>::register_object(HeapWord *addr) {
353   _scc->register_object(addr);
354 }
355 
356 template<typename RememberedSet>
357 inline void
358 ShenandoahScanRemembered<RememberedSet>::register_object_wo_lock(HeapWord *addr) {
359   _scc->register_object_wo_lock(addr);
360 }
361 
362 template <typename RememberedSet>
363 inline bool
364 ShenandoahScanRemembered<RememberedSet>::verify_registration(HeapWord* address, ShenandoahMarkingContext* ctx) {
365 
366   size_t index = card_index_for_addr(address);
367   if (!_scc->has_object(index)) {
368     return false;
369   }
370   HeapWord* base_addr = addr_for_card_index(index);
371   size_t offset = _scc->get_first_start(index);
372   ShenandoahHeap* heap = ShenandoahHeap::heap();
373 
374   // Verify that I can find this object within its enclosing card by scanning forward from first_start.
375   while (base_addr + offset < address) {
376     oop obj = cast_to_oop(base_addr + offset);
377     if (!ctx || ctx->is_marked(obj)) {
378       offset += obj->size();
379     } else {
380       // If this object is not live, don't trust its size(); all objects above tams are live.
381       ShenandoahHeapRegion* r = heap->heap_region_containing(obj);
382       HeapWord* tams = ctx->top_at_mark_start(r);
383       offset = ctx->get_next_marked_addr(base_addr + offset, tams) - base_addr;
384     }
385   }
386   if (base_addr + offset != address){
387     return false;
388   }
389 
390   // At this point, offset represents object whose registration we are verifying.  We know that at least this object resides
391   // within this card's memory.
392 
393   // Make sure that last_offset is properly set for the enclosing card, but we can't verify this for
394   // candidate collection-set regions during mixed evacuations, so disable this check in general
395   // during mixed evacuations.
396 
397   ShenandoahHeapRegion* r = heap->heap_region_containing(base_addr + offset);
398   size_t max_offset = r->top() - base_addr;
399   if (max_offset > CardTable::card_size_in_words) {
400     max_offset = CardTable::card_size_in_words;
401   }
402   size_t prev_offset;
403   if (!ctx) {
404     do {
405       oop obj = cast_to_oop(base_addr + offset);
406       prev_offset = offset;
407       offset += obj->size();
408     } while (offset < max_offset);
409     if (_scc->get_last_start(index) != prev_offset) {
410       return false;
411     }
412 
413     // base + offset represents address of first object that starts on following card, if there is one.
414 
415     // Notes: base_addr is addr_for_card_index(index)
416     //        base_addr + offset is end of the object we are verifying
417     //        cannot use card_index_for_addr(base_addr + offset) because it asserts arg < end of whole heap
418     size_t end_card_index = index + offset / CardTable::card_size_in_words;
419 
420     if (end_card_index > index) {
421       // If there is a following object registered on the next card, it should begin where this object ends.
422       if ((base_addr + offset < _rs->whole_heap_end()) && _scc->has_object(end_card_index) &&
423           ((addr_for_card_index(end_card_index) + _scc->get_first_start(end_card_index)) != (base_addr + offset))) {
424         return false;
425       }
426     }
427 
428     // Assure that no other objects are registered "inside" of this one.
429     for (index++; index < end_card_index; index++) {
430       if (_scc->has_object(index)) {
431         return false;
432       }
433     }
434   } else {
435     // This is a mixed evacuation or a global collect: rely on mark bits to identify which objects need to be properly registered
436     assert(!ShenandoahHeap::heap()->is_concurrent_old_mark_in_progress(), "Cannot rely on mark context here.");
437     // If the object reaching or spanning the end of this card's memory is marked, then last_offset for this card
438     // should represent this object.  Otherwise, last_offset is a don't care.
439     ShenandoahHeapRegion* region = heap->heap_region_containing(base_addr + offset);
440     HeapWord* tams = ctx->top_at_mark_start(region);
441     do {
442       prev_offset = offset;
443       oop obj = cast_to_oop(base_addr + offset);
444       if (ctx->is_marked(obj)) {
445         offset += obj->size();
446       } else {
447         offset = ctx->get_next_marked_addr(base_addr + offset, tams) - base_addr;
448         // offset will be zero if no objects are marked in this card.
449       }
450     } while (offset > 0 && offset < max_offset);
451     oop last_obj = cast_to_oop(base_addr + prev_offset);
452     if (prev_offset + last_obj->size() >= max_offset) {
453       if (_scc->get_last_start(index) != prev_offset) {
454         return false;
455       }
456       // otherwise, the value of _scc->get_last_start(index) is a don't care because it represents a dead object and we
457       // cannot verify its context
458     }
459   }
460   return true;
461 }
462 
463 template<typename RememberedSet>
464 inline void
465 ShenandoahScanRemembered<RememberedSet>::coalesce_objects(HeapWord *addr, size_t length_in_words) {
466   _scc->coalesce_objects(addr, length_in_words);
467 }
468 
469 template<typename RememberedSet>
470 inline void
471 ShenandoahScanRemembered<RememberedSet>::mark_range_as_empty(HeapWord *addr, size_t length_in_words) {
472   _rs->mark_range_as_clean(addr, length_in_words);
473   _scc->clear_objects_in_range(addr, length_in_words);
474 }
475 
476 template<typename RememberedSet>
477 template <typename ClosureType>
478 inline void
479 ShenandoahScanRemembered<RememberedSet>::process_clusters(size_t first_cluster, size_t count, HeapWord *end_of_range,
480                                                           ClosureType *cl) {
481   process_clusters(first_cluster, count, end_of_range, cl, false);
482 }
483 
484 // Process all objects starting within count clusters beginning with first_cluster for which the start address is
485 // less than end_of_range.  For any such object, process the complete object, even if its end reaches beyond
486 // end_of_range.
487 template<typename RememberedSet>
488 template <typename ClosureType>
489 inline void
490 ShenandoahScanRemembered<RememberedSet>::process_clusters(size_t first_cluster, size_t count, HeapWord *end_of_range,
491                                                           ClosureType *cl, bool write_table) {
492 
493   // Unlike traditional Shenandoah marking, the old-gen resident objects that are examined as part of the remembered set are not
494   // themselves marked.  Each such object will be scanned only once.  Any young-gen objects referenced from the remembered set will
495   // be marked and then subsequently scanned.
496 
497   // If old-gen evacuation is active, then MarkingContext for old-gen heap regions is valid.  We use the MarkingContext
498   // bits to determine which objects within a DIRTY card need to be scanned.  This is necessary because old-gen heap
499   // regions which are in the candidate collection set have not been coalesced and filled.  Thus, these heap regions
500   // may contain zombie objects.  Zombie objects are known to be dead, but have not yet been "collected".  Scanning
501   // zombie objects is unsafe because the Klass pointer is not reliable, objects referenced from a zombie may have been
502   // collected and their memory repurposed, and because zombie objects might refer to objects that are themselves dead.
503 
504   ShenandoahHeap* heap = ShenandoahHeap::heap();
505   ShenandoahMarkingContext* ctx;
506 
507   if (heap->doing_mixed_evacuations() || heap->is_concurrent_prep_for_mixed_evacuation_in_progress()) {
508     ctx = heap->marking_context();
509   } else {
510     ctx = nullptr;
511   }
512 
513   HeapWord* end_of_clusters = _rs->addr_for_card_index(first_cluster)
514     + count * ShenandoahCardCluster<RememberedSet>::CardsPerCluster * CardTable::card_size_in_words;
515   while (count-- > 0) {
516     size_t card_index = first_cluster * ShenandoahCardCluster<RememberedSet>::CardsPerCluster;
517     size_t end_card_index = card_index + ShenandoahCardCluster<RememberedSet>::CardsPerCluster;
518     first_cluster++;
519     size_t next_card_index = 0;
520     while (card_index < end_card_index) {
521       bool is_dirty = (write_table)? is_write_card_dirty(card_index): is_card_dirty(card_index);
522       bool has_object = _scc->has_object(card_index);
523       if (is_dirty) {
524         size_t prev_card_index = card_index;
525         if (has_object) {
526           // Scan all objects that start within this card region.
527           size_t start_offset = _scc->get_first_start(card_index);
528           HeapWord *p = _rs->addr_for_card_index(card_index);
529           HeapWord *card_start = p;
530           HeapWord *endp = p + CardTable::card_size_in_words;
531           if (endp > end_of_range) {
532             endp = end_of_range;
533             next_card_index = end_card_index;
534           } else {
535             // endp either points to start of next card region, or to the next object that needs to be scanned, which may
536             // reside in some successor card region.
537 
538             // Can't use _scc->card_index_for_addr(endp) here because it crashes with assertion
539             // failure if endp points to end of heap.
540             next_card_index = card_index + (endp - card_start) / CardTable::card_size_in_words;
541           }
542 
543           p += start_offset;
544           while (p < endp) {
545             oop obj = cast_to_oop(p);
546 
547             // ctx->is_marked() returns true if mark bit set or if obj above TAMS.
548             if (!ctx || ctx->is_marked(obj)) {
549               // Future TODO:
550               // For improved efficiency, we might want to give special handling of obj->is_objArray().  In
551               // particular, in that case, we might want to divide the effort for scanning of a very long object array
552               // between multiple threads.  Also, skip parts of the array that are not marked as dirty.
553               if (obj->is_objArray()) {
554                 objArrayOop array = objArrayOop(obj);
555                 int len = array->length();
556                 array->oop_iterate_range(cl, 0, len);
557               } else if (obj->is_instance()) {
558                 obj->oop_iterate(cl);
559               } else {
560                 // Case 3: Primitive array. Do nothing, no oops there. We use the same
561                 // performance tweak TypeArrayKlass::oop_oop_iterate_impl is using:
562                 // We skip iterating over the klass pointer since we know that
563                 // Universe::TypeArrayKlass never moves.
564                 assert (obj->is_typeArray(), "should be type array");
565               }
566               p += obj->size();
567             } else {
568               // This object is not marked so we don't scan it.
569               ShenandoahHeapRegion* r = heap->heap_region_containing(p);
570               HeapWord* tams = ctx->top_at_mark_start(r);
571               if (p >= tams) {
572                 p += obj->size();
573               } else {
574                 p = ctx->get_next_marked_addr(p, tams);
575               }
576             }
577           }
578           if (p > endp) {
579             card_index = card_index + (p - card_start) / CardTable::card_size_in_words;
580           } else {                  // p == endp
581             card_index = next_card_index;
582           }
583         } else {
584           // Card is dirty but has no object.  Card will have been scanned during scan of a previous cluster.
585           card_index++;
586         }
587       } else if (has_object) {
588         // Card is clean but has object.
589 
590         // Scan the last object that starts within this card memory if it spans at least one dirty card within this cluster
591         // or if it reaches into the next cluster.
592         size_t start_offset = _scc->get_last_start(card_index);
593         HeapWord *card_start = _rs->addr_for_card_index(card_index);
594         HeapWord *p = card_start + start_offset;
595         oop obj = cast_to_oop(p);
596 
597         size_t last_card;
598         if (!ctx || ctx->is_marked(obj)) {
599           HeapWord *nextp = p + obj->size();
600 
601           // Can't use _scc->card_index_for_addr(endp) here because it crashes with assertion
602           // failure if nextp points to end of heap.
603           last_card = card_index + (nextp - card_start) / CardTable::card_size_in_words;
604 
605           bool reaches_next_cluster = (last_card > end_card_index);
606           bool spans_dirty_within_this_cluster = false;
607 
608           if (!reaches_next_cluster) {
609             size_t span_card;
610             for (span_card = card_index+1; span_card <= last_card; span_card++)
611               if ((write_table)? _rs->is_write_card_dirty(span_card): _rs->is_card_dirty(span_card)) {
612                 spans_dirty_within_this_cluster = true;
613                 break;
614               }
615           }
616 
617           if (reaches_next_cluster || spans_dirty_within_this_cluster) {
618             if (obj->is_objArray()) {
619               objArrayOop array = objArrayOop(obj);
620               int len = array->length();
621               array->oop_iterate_range(cl, 0, len);
622             } else if (obj->is_instance()) {
623               obj->oop_iterate(cl);
624             } else {
625               // Case 3: Primitive array. Do nothing, no oops there. We use the same
626               // performance tweak TypeArrayKlass::oop_oop_iterate_impl is using:
627               // We skip iterating over the klass pointer since we know that
628               // Universe::TypeArrayKlass never moves.
629               assert (obj->is_typeArray(), "should be type array");
630             }
631           }
632         } else {
633           // The object that spans end of this clean card is not marked, so no need to scan it or its
634           // unmarked neighbors.
635           ShenandoahHeapRegion* r = heap->heap_region_containing(p);
636           HeapWord* tams = ctx->top_at_mark_start(r);
637           HeapWord* nextp;
638           if (p >= tams) {
639             nextp = p + obj->size();
640           } else {
641             nextp = ctx->get_next_marked_addr(p, tams);
642           }
643           last_card = card_index + (nextp - card_start) / CardTable::card_size_in_words;
644         }
645         // Increment card_index to account for the spanning object, even if we didn't scan it.
646         card_index = (last_card > card_index)? last_card: card_index + 1;
647       } else {
648         // Card is clean and has no object.  No need to clean this card.
649         card_index++;
650       }
651     }
652   }
653 }
654 
655 template<typename RememberedSet>
656 template <typename ClosureType>
657 inline void
658 ShenandoahScanRemembered<RememberedSet>::process_region(ShenandoahHeapRegion *region, ClosureType *cl) {
659   process_region(region, cl, false);
660 }
661 
662 template<typename RememberedSet>
663 template <typename ClosureType>
664 inline void
665 ShenandoahScanRemembered<RememberedSet>::process_region(ShenandoahHeapRegion *region, ClosureType *cl, bool use_write_table) {
666   HeapWord *start_of_range = region->bottom();
667   size_t start_cluster_no = cluster_for_addr(start_of_range);
668 
669   // region->end() represents the end of memory spanned by this region, but not all of this
670   //   memory is eligible to be scanned because some of this memory has not yet been allocated.
671   //
672   // region->top() represents the end of allocated memory within this region.  Any addresses
673   //   beyond region->top() should not be scanned as that memory does not hold valid objects.
674 
675   HeapWord *end_of_range;
676   if (use_write_table) {
677     // This is update-refs servicing.
678     end_of_range = region->get_update_watermark();
679   } else {
680     // This is concurrent mark servicing.  Note that TAMS for this region is TAMS at start of old-gen
681     // collection.  Here, we need to scan up to TAMS for most recently initiated young-gen collection.
682     // Since all LABs are retired at init mark, and since replacement LABs are allocated lazily, and since no
683     // promotions occur until evacuation phase, TAMS for most recent young-gen is same as top().
684     end_of_range = region->top();
685   }
686 
687   log_debug(gc)("Remembered set scan processing Region " SIZE_FORMAT ", from " PTR_FORMAT " to " PTR_FORMAT ", using %s table",
688                 region->index(), p2i(region->bottom()), p2i(end_of_range),
689                 use_write_table? "read/write (updating)": "read (marking)");
690   // end_of_range may point to the middle of a cluster because region->top() may be different than region->end().
691   // We want to assure that our process_clusters() request spans all relevant clusters.  Note that each cluster
692   // processed will avoid processing beyond end_of_range.
693 
694   // Note that any object that starts between start_of_range and end_of_range, including humongous objects, will
695   // be fully processed by process_clusters, even though the object may reach beyond end_of_range.
696   size_t num_heapwords = end_of_range - start_of_range;
697   unsigned int cluster_size = CardTable::card_size_in_words * ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
698   size_t num_clusters = (size_t) ((num_heapwords - 1 + cluster_size) / cluster_size);
699 
700   if (!region->is_humongous_continuation()) {
701     // Remembered set scanner
702     process_clusters(start_cluster_no, num_clusters, end_of_range, cl, use_write_table);
703   }
704 }
705 
706 template<typename RememberedSet>
707 inline size_t
708 ShenandoahScanRemembered<RememberedSet>::cluster_for_addr(HeapWordImpl **addr) {
709   size_t card_index = _rs->card_index_for_addr(addr);
710   size_t result = card_index / ShenandoahCardCluster<RememberedSet>::CardsPerCluster;
711   return result;
712 }
713 
714 // This is used only for debug verification so don't worry about making the scan parallel.
715 template<typename RememberedSet>
716 inline void ShenandoahScanRemembered<RememberedSet>::roots_do(OopIterateClosure* cl) {
717   ShenandoahHeap* heap = ShenandoahHeap::heap();
718   for (size_t i = 0, n = heap->num_regions(); i < n; ++i) {
719     ShenandoahHeapRegion* region = heap->get_region(i);
720     if (region->is_old() && region->is_active() && !region->is_cset()) {
721       HeapWord* start_of_range = region->bottom();
722       HeapWord* end_of_range = region->top();
723       size_t start_cluster_no = cluster_for_addr(start_of_range);
724       size_t num_heapwords = end_of_range - start_of_range;
725       unsigned int cluster_size = CardTable::card_size_in_words *
726                                   ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
727       size_t num_clusters = (size_t) ((num_heapwords - 1 + cluster_size) / cluster_size);
728 
729       // Remembered set scanner
730       process_clusters(start_cluster_no, num_clusters, end_of_range, cl);
731     }
732   }
733 }
734 
735 #endif   // SHARE_GC_SHENANDOAH_SHENANDOAHSCANREMEMBEREDINLINE_HPP