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