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::last_valid_index() {
 40   return _card_table->last_valid_index();
 41 }
 42 
 43 inline size_t
 44 ShenandoahDirectCardMarkRememberedSet::total_cards() {
 45   return _total_card_count;
 46 }
 47 
 48 inline size_t
 49 ShenandoahDirectCardMarkRememberedSet::card_index_for_addr(HeapWord *p) {
 50   return _card_table->index_for(p);
 51 }
 52 
 53 inline HeapWord *
 54 ShenandoahDirectCardMarkRememberedSet::addr_for_card_index(size_t card_index) {
 55   return _whole_heap_base + CardTable::card_size_in_words() * card_index;
 56 }
 57 
 58 inline bool
 59 ShenandoahDirectCardMarkRememberedSet::is_write_card_dirty(size_t card_index) {
 60   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 61   return (bp[0] == CardTable::dirty_card_val());
 62 }
 63 
 64 inline bool
 65 ShenandoahDirectCardMarkRememberedSet::is_card_dirty(size_t card_index) {
 66   uint8_t *bp = &(_card_table->read_byte_map())[card_index];
 67   return (bp[0] == CardTable::dirty_card_val());
 68 }
 69 
 70 inline void
 71 ShenandoahDirectCardMarkRememberedSet::mark_card_as_dirty(size_t card_index) {
 72   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 73   bp[0] = CardTable::dirty_card_val();
 74 }
 75 
 76 inline void
 77 ShenandoahDirectCardMarkRememberedSet::mark_range_as_dirty(size_t card_index, size_t num_cards) {
 78   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 79   while (num_cards-- > 0) {
 80     *bp++ = CardTable::dirty_card_val();
 81   }
 82 }
 83 
 84 inline void
 85 ShenandoahDirectCardMarkRememberedSet::mark_card_as_clean(size_t card_index) {
 86   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 87   bp[0] = CardTable::clean_card_val();
 88 }
 89 
 90 inline void
 91 ShenandoahDirectCardMarkRememberedSet::mark_range_as_clean(size_t card_index, size_t num_cards) {
 92   uint8_t *bp = &(_card_table->write_byte_map())[card_index];
 93   while (num_cards-- > 0) {
 94     *bp++ = CardTable::clean_card_val();
 95   }
 96 }
 97 
 98 inline bool
 99 ShenandoahDirectCardMarkRememberedSet::is_card_dirty(HeapWord *p) {
100   size_t index = card_index_for_addr(p);
101   uint8_t *bp = &(_card_table->read_byte_map())[index];
102   return (bp[0] == CardTable::dirty_card_val());
103 }
104 
105 inline void
106 ShenandoahDirectCardMarkRememberedSet::mark_card_as_dirty(HeapWord *p) {
107   size_t index = card_index_for_addr(p);
108   uint8_t *bp = &(_card_table->write_byte_map())[index];
109   bp[0] = CardTable::dirty_card_val();
110 }
111 
112 inline void
113 ShenandoahDirectCardMarkRememberedSet::mark_range_as_dirty(HeapWord *p, size_t num_heap_words) {
114   uint8_t *bp = &(_card_table->write_byte_map_base())[uintptr_t(p) >> _card_shift];
115   uint8_t *end_bp = &(_card_table->write_byte_map_base())[uintptr_t(p + num_heap_words) >> _card_shift];
116   // If (p + num_heap_words) is not aligned on card boundary, we also need to dirty last card.
117   if (((unsigned long long) (p + num_heap_words)) & (CardTable::card_size() - 1)) {
118     end_bp++;
119   }
120   while (bp < end_bp) {
121     *bp++ = CardTable::dirty_card_val();
122   }
123 }
124 
125 inline void
126 ShenandoahDirectCardMarkRememberedSet::mark_card_as_clean(HeapWord *p) {
127   size_t index = card_index_for_addr(p);
128   uint8_t *bp = &(_card_table->write_byte_map())[index];
129   bp[0] = CardTable::clean_card_val();
130 }
131 
132 inline void
133 ShenandoahDirectCardMarkRememberedSet::mark_read_card_as_clean(size_t index) {
134   uint8_t *bp = &(_card_table->read_byte_map())[index];
135   bp[0] = CardTable::clean_card_val();
136 }
137 
138 inline void
139 ShenandoahDirectCardMarkRememberedSet::mark_range_as_clean(HeapWord *p, size_t num_heap_words) {
140   uint8_t *bp = &(_card_table->write_byte_map_base())[uintptr_t(p) >> _card_shift];
141   uint8_t *end_bp = &(_card_table->write_byte_map_base())[uintptr_t(p + num_heap_words) >> _card_shift];
142   // If (p + num_heap_words) is not aligned on card boundary, we also need to clean last card.
143   if (((unsigned long long) (p + num_heap_words)) & (CardTable::card_size() - 1)) {
144     end_bp++;
145   }
146   while (bp < end_bp) {
147     *bp++ = CardTable::clean_card_val();
148   }
149 }
150 
151 inline size_t
152 ShenandoahDirectCardMarkRememberedSet::cluster_count() {
153   return _cluster_count;
154 }
155 
156 // No lock required because arguments align with card boundaries.
157 template<typename RememberedSet>
158 inline void
159 ShenandoahCardCluster<RememberedSet>::reset_object_range(HeapWord* from, HeapWord* to) {
160   assert(((((unsigned long long) from) & (CardTable::card_size() - 1)) == 0) &&
161          ((((unsigned long long) to) & (CardTable::card_size() - 1)) == 0),
162          "reset_object_range bounds must align with card boundaries");
163   size_t card_at_start = _rs->card_index_for_addr(from);
164   size_t num_cards = (to - from) / CardTable::card_size_in_words();
165 
166   for (size_t i = 0; i < num_cards; i++) {
167     object_starts[card_at_start + i].short_word = 0;
168   }
169 }
170 
171 // Assume only one thread at a time registers objects pertaining to
172 // each card-table entry's range of memory.
173 template<typename RememberedSet>
174 inline void
175 ShenandoahCardCluster<RememberedSet>::register_object(HeapWord* address) {
176   shenandoah_assert_heaplocked();
177 
178   register_object_wo_lock(address);
179 }
180 
181 template<typename RememberedSet>
182 inline void
183 ShenandoahCardCluster<RememberedSet>::register_object_wo_lock(HeapWord* address) {
184   size_t card_at_start = _rs->card_index_for_addr(address);
185   HeapWord *card_start_address = _rs->addr_for_card_index(card_at_start);
186   uint8_t offset_in_card = address - card_start_address;
187 
188   if (!has_object(card_at_start)) {
189     set_has_object_bit(card_at_start);
190     set_first_start(card_at_start, offset_in_card);
191     set_last_start(card_at_start, offset_in_card);
192   } else {
193     if (offset_in_card < get_first_start(card_at_start))
194       set_first_start(card_at_start, offset_in_card);
195     if (offset_in_card > get_last_start(card_at_start))
196       set_last_start(card_at_start, offset_in_card);
197   }
198 }
199 
200 template<typename RememberedSet>
201 inline void
202 ShenandoahCardCluster<RememberedSet>::coalesce_objects(HeapWord* address, size_t length_in_words) {
203 
204   size_t card_at_start = _rs->card_index_for_addr(address);
205   HeapWord *card_start_address = _rs->addr_for_card_index(card_at_start);
206   size_t card_at_end = card_at_start + ((address + length_in_words) - card_start_address) / CardTable::card_size_in_words();
207 
208   if (card_at_start == card_at_end) {
209     // There are no changes to the get_first_start array.  Either get_first_start(card_at_start) returns this coalesced object,
210     // or it returns an object that precedes the coalesced object.
211     if (card_start_address + get_last_start(card_at_start) < address + length_in_words) {
212       uint8_t coalesced_offset = static_cast<uint8_t>(address - card_start_address);
213       // The object that used to be the last object starting within this card is being subsumed within the coalesced
214       // object.  Since we always coalesce entire objects, this condition only occurs if the last object ends before or at
215       // the end of the card's memory range and there is no object following this object.  In this case, adjust last_start
216       // to represent the start of the coalesced range.
217       set_last_start(card_at_start, coalesced_offset);
218     }
219     // Else, no changes to last_starts information.  Either get_last_start(card_at_start) returns the object that immediately
220     // follows the coalesced object, or it returns an object that follows the object immediately following the coalesced object.
221   } else {
222     uint8_t coalesced_offset = static_cast<uint8_t>(address - card_start_address);
223     if (get_last_start(card_at_start) > coalesced_offset) {
224       // Existing last start is being coalesced, create new last start
225       set_last_start(card_at_start, coalesced_offset);
226     }
227     // otherwise, get_last_start(card_at_start) must equal coalesced_offset
228 
229     // All the cards between first and last get cleared.
230     for (size_t i = card_at_start + 1; i < card_at_end; i++) {
231       clear_has_object_bit(i);
232     }
233 
234     uint8_t follow_offset = static_cast<uint8_t>((address + length_in_words) - _rs->addr_for_card_index(card_at_end));
235     if (has_object(card_at_end) && (get_first_start(card_at_end) < follow_offset)) {
236       // It may be that after coalescing within this last card's memory range, the last card
237       // no longer holds an object.
238       if (get_last_start(card_at_end) >= follow_offset) {
239         set_first_start(card_at_end, follow_offset);
240       } else {
241         // last_start is being coalesced so this card no longer has any objects.
242         clear_has_object_bit(card_at_end);
243       }
244     }
245     // else
246     //  card_at_end did not have an object, so it still does not have an object, or
247     //  card_at_end had an object that starts after the coalesced object, so no changes required for card_at_end
248 
249   }
250 }
251 
252 
253 template<typename RememberedSet>
254 inline size_t
255 ShenandoahCardCluster<RememberedSet>::get_first_start(size_t card_index) {
256   assert(has_object(card_index), "Can't get first start because no object starts here");
257   return object_starts[card_index].offsets.first & FirstStartBits;
258 }
259 
260 template<typename RememberedSet>
261 inline size_t
262 ShenandoahCardCluster<RememberedSet>::get_last_start(size_t card_index) {
263   assert(has_object(card_index), "Can't get last start because no object starts here");
264   return object_starts[card_index].offsets.last;
265 }
266 
267 template<typename RememberedSet>
268 inline size_t
269 ShenandoahScanRemembered<RememberedSet>::last_valid_index() { return _rs->last_valid_index(); }
270 
271 template<typename RememberedSet>
272 inline size_t
273 ShenandoahScanRemembered<RememberedSet>::total_cards() { return _rs->total_cards(); }
274 
275 template<typename RememberedSet>
276 inline size_t
277 ShenandoahScanRemembered<RememberedSet>::card_index_for_addr(HeapWord *p) { return _rs->card_index_for_addr(p); };
278 
279 template<typename RememberedSet>
280 inline HeapWord *
281 ShenandoahScanRemembered<RememberedSet>::addr_for_card_index(size_t card_index) { return _rs->addr_for_card_index(card_index); }
282 
283 template<typename RememberedSet>
284 inline bool
285 ShenandoahScanRemembered<RememberedSet>::is_card_dirty(size_t card_index) { return _rs->is_card_dirty(card_index); }
286 
287 template<typename RememberedSet>
288 inline void
289 ShenandoahScanRemembered<RememberedSet>::mark_card_as_dirty(size_t card_index) { _rs->mark_card_as_dirty(card_index); }
290 
291 template<typename RememberedSet>
292 inline void
293 ShenandoahScanRemembered<RememberedSet>::mark_range_as_dirty(size_t card_index, size_t num_cards) { _rs->mark_range_as_dirty(card_index, num_cards); }
294 
295 template<typename RememberedSet>
296 inline void
297 ShenandoahScanRemembered<RememberedSet>::mark_card_as_clean(size_t card_index) { _rs->mark_card_as_clean(card_index); }
298 
299 template<typename RememberedSet>
300 inline void
301 ShenandoahScanRemembered<RememberedSet>::mark_range_as_clean(size_t card_index, size_t num_cards) { _rs->mark_range_as_clean(card_index, num_cards); }
302 
303 template<typename RememberedSet>
304 inline bool
305 ShenandoahScanRemembered<RememberedSet>::is_card_dirty(HeapWord *p) { return _rs->is_card_dirty(p); }
306 
307 template<typename RememberedSet>
308 inline void
309 ShenandoahScanRemembered<RememberedSet>::mark_card_as_dirty(HeapWord *p) { _rs->mark_card_as_dirty(p); }
310 
311 template<typename RememberedSet>
312 inline void
313 ShenandoahScanRemembered<RememberedSet>::mark_range_as_dirty(HeapWord *p, size_t num_heap_words) { _rs->mark_range_as_dirty(p, num_heap_words); }
314 
315 template<typename RememberedSet>
316 inline void
317 ShenandoahScanRemembered<RememberedSet>::mark_card_as_clean(HeapWord *p) { _rs->mark_card_as_clean(p); }
318 
319 template<typename RememberedSet>
320 inline void
321 ShenandoahScanRemembered<RememberedSet>:: mark_range_as_clean(HeapWord *p, size_t num_heap_words) { _rs->mark_range_as_clean(p, num_heap_words); }
322 
323 template<typename RememberedSet>
324 inline size_t
325 ShenandoahScanRemembered<RememberedSet>::cluster_count() { return _rs->cluster_count(); }
326 
327 template<typename RememberedSet>
328 inline void
329 ShenandoahScanRemembered<RememberedSet>::reset_object_range(HeapWord *from, HeapWord *to) {
330   _scc->reset_object_range(from, to);
331 }
332 
333 template<typename RememberedSet>
334 inline void
335 ShenandoahScanRemembered<RememberedSet>::register_object(HeapWord *addr) {
336   _scc->register_object(addr);
337 }
338 
339 template<typename RememberedSet>
340 inline void
341 ShenandoahScanRemembered<RememberedSet>::register_object_wo_lock(HeapWord *addr) {
342   _scc->register_object_wo_lock(addr);
343 }
344 
345 template <typename RememberedSet>
346 inline bool
347 ShenandoahScanRemembered<RememberedSet>::verify_registration(HeapWord* address, ShenandoahMarkingContext* ctx) {
348 
349   size_t index = card_index_for_addr(address);
350   if (!_scc->has_object(index)) {
351     return false;
352   }
353   HeapWord* base_addr = addr_for_card_index(index);
354   size_t offset = _scc->get_first_start(index);
355   ShenandoahHeap* heap = ShenandoahHeap::heap();
356 
357   // Verify that I can find this object within its enclosing card by scanning forward from first_start.
358   while (base_addr + offset < address) {
359     oop obj = cast_to_oop(base_addr + offset);
360     if (!ctx || ctx->is_marked(obj)) {
361       offset += obj->size();
362     } else {
363       // If this object is not live, don't trust its size(); all objects above tams are live.
364       ShenandoahHeapRegion* r = heap->heap_region_containing(obj);
365       HeapWord* tams = ctx->top_at_mark_start(r);
366       offset = ctx->get_next_marked_addr(base_addr + offset, tams) - base_addr;
367     }
368   }
369   if (base_addr + offset != address){
370     return false;
371   }
372 
373   // At this point, offset represents object whose registration we are verifying.  We know that at least this object resides
374   // within this card's memory.
375 
376   // Make sure that last_offset is properly set for the enclosing card, but we can't verify this for
377   // candidate collection-set regions during mixed evacuations, so disable this check in general
378   // during mixed evacuations.
379 
380   ShenandoahHeapRegion* r = heap->heap_region_containing(base_addr + offset);
381   size_t max_offset = r->top() - base_addr;
382   if (max_offset > CardTable::card_size_in_words()) {
383     max_offset = CardTable::card_size_in_words();
384   }
385   size_t prev_offset;
386   if (!ctx) {
387     do {
388       oop obj = cast_to_oop(base_addr + offset);
389       prev_offset = offset;
390       offset += obj->size();
391     } while (offset < max_offset);
392     if (_scc->get_last_start(index) != prev_offset) {
393       return false;
394     }
395 
396     // base + offset represents address of first object that starts on following card, if there is one.
397 
398     // Notes: base_addr is addr_for_card_index(index)
399     //        base_addr + offset is end of the object we are verifying
400     //        cannot use card_index_for_addr(base_addr + offset) because it asserts arg < end of whole heap
401     size_t end_card_index = index + offset / CardTable::card_size_in_words();
402 
403     if (end_card_index > index && end_card_index <= _rs->last_valid_index()) {
404       // If there is a following object registered on the next card, it should begin where this object ends.
405       if (_scc->has_object(end_card_index) &&
406           ((addr_for_card_index(end_card_index) + _scc->get_first_start(end_card_index)) != (base_addr + offset))) {
407         return false;
408       }
409     }
410 
411     // Assure that no other objects are registered "inside" of this one.
412     for (index++; index < end_card_index; index++) {
413       if (_scc->has_object(index)) {
414         return false;
415       }
416     }
417   } else {
418     // This is a mixed evacuation or a global collect: rely on mark bits to identify which objects need to be properly registered
419     assert(!ShenandoahHeap::heap()->is_concurrent_old_mark_in_progress(), "Cannot rely on mark context here.");
420     // If the object reaching or spanning the end of this card's memory is marked, then last_offset for this card
421     // should represent this object.  Otherwise, last_offset is a don't care.
422     ShenandoahHeapRegion* region = heap->heap_region_containing(base_addr + offset);
423     HeapWord* tams = ctx->top_at_mark_start(region);
424     oop last_obj = nullptr;
425     do {
426       oop obj = cast_to_oop(base_addr + offset);
427       if (ctx->is_marked(obj)) {
428         prev_offset = offset;
429         offset += obj->size();
430         last_obj = obj;
431       } else {
432         offset = ctx->get_next_marked_addr(base_addr + offset, tams) - base_addr;
433         // If there are no marked objects remaining in this region, offset equals tams - base_addr.  If this offset is
434         // greater than max_offset, we will immediately exit this loop.  Otherwise, the next iteration of the loop will
435         // treat the object at offset as marked and live (because address >= tams) and we will continue iterating object
436         // by consulting the size() fields of each.
437       }
438     } while (offset < max_offset);
439     if (last_obj != nullptr && prev_offset + last_obj->size() >= max_offset) {
440       // last marked object extends beyond end of card
441       if (_scc->get_last_start(index) != prev_offset) {
442         return false;
443       }
444       // otherwise, the value of _scc->get_last_start(index) is a don't care because it represents a dead object and we
445       // cannot verify its context
446     }
447   }
448   return true;
449 }
450 
451 template<typename RememberedSet>
452 inline void
453 ShenandoahScanRemembered<RememberedSet>::coalesce_objects(HeapWord *addr, size_t length_in_words) {
454   _scc->coalesce_objects(addr, length_in_words);
455 }
456 
457 template<typename RememberedSet>
458 inline void
459 ShenandoahScanRemembered<RememberedSet>::mark_range_as_empty(HeapWord *addr, size_t length_in_words) {
460   _rs->mark_range_as_clean(addr, length_in_words);
461   _scc->clear_objects_in_range(addr, length_in_words);
462 }
463 
464 template<typename RememberedSet>
465 template <typename ClosureType>
466 inline void
467 ShenandoahScanRemembered<RememberedSet>::process_clusters(size_t first_cluster, size_t count, HeapWord *end_of_range,
468                                                           ClosureType *cl, bool is_concurrent) {
469   process_clusters(first_cluster, count, end_of_range, cl, false, is_concurrent);
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 such object, process the complete object, even if its end reaches beyond end_of_range.
474 
475 // Do not CANCEL within process_clusters.  It is assumed that if a worker thread accepts responsbility for processing
476 // a chunk of work, it will finish the work it starts.  Otherwise, the chunk of work will be lost in the transition to
477 // degenerated execution.
478 template<typename RememberedSet>
479 template <typename ClosureType>
480 inline void
481 ShenandoahScanRemembered<RememberedSet>::process_clusters(size_t first_cluster, size_t count, HeapWord *end_of_range,
482                                                           ClosureType *cl, bool write_table, bool is_concurrent) {
483 
484   // Unlike traditional Shenandoah marking, the old-gen resident objects that are examined as part of the remembered set are not
485   // themselves marked.  Each such object will be scanned only once.  Any young-gen objects referenced from the remembered set will
486   // be marked and then subsequently scanned.
487 
488   // If old-gen evacuation is active, then MarkingContext for old-gen heap regions is valid.  We use the MarkingContext
489   // bits to determine which objects within a DIRTY card need to be scanned.  This is necessary because old-gen heap
490   // regions which are in the candidate collection set have not been coalesced and filled.  Thus, these heap regions
491   // may contain zombie objects.  Zombie objects are known to be dead, but have not yet been "collected".  Scanning
492   // zombie objects is unsafe because the Klass pointer is not reliable, objects referenced from a zombie may have been
493   // collected and their memory repurposed, and because zombie objects might refer to objects that are themselves dead.
494 
495   ShenandoahHeap* heap = ShenandoahHeap::heap();
496   ShenandoahMarkingContext* ctx;
497 
498   if (heap->is_old_bitmap_stable()) {
499     ctx = heap->marking_context();
500   } else {
501     ctx = nullptr;
502   }
503 
504   size_t card_index = first_cluster * ShenandoahCardCluster<RememberedSet>::CardsPerCluster;
505   HeapWord *start_of_range = _rs->addr_for_card_index(card_index);
506   ShenandoahHeapRegion* r = heap->heap_region_containing(start_of_range);
507   assert(end_of_range <= r->top(), "process_clusters() examines one region at a time");
508 
509   while (count-- > 0) {
510     // TODO: do we want to check cancellation in inner loop, on every card processed?  That would be more responsive,
511     // but require more overhead for checking.
512     card_index = first_cluster * ShenandoahCardCluster<RememberedSet>::CardsPerCluster;
513     size_t end_card_index = card_index + ShenandoahCardCluster<RememberedSet>::CardsPerCluster;
514     first_cluster++;
515     size_t next_card_index = 0;
516     while (card_index < end_card_index) {
517       if (_rs->addr_for_card_index(card_index) > end_of_range) {
518         count = 0;
519         card_index = end_card_index;
520         break;
521       }
522       bool is_dirty = (write_table)? is_write_card_dirty(card_index): is_card_dirty(card_index);
523       bool has_object = _scc->has_object(card_index);
524       if (is_dirty) {
525         size_t prev_card_index = card_index;
526         if (has_object) {
527           // Scan all objects that start within this card region.
528           size_t start_offset = _scc->get_first_start(card_index);
529           HeapWord *p = _rs->addr_for_card_index(card_index);
530           HeapWord *card_start = p;
531           HeapWord *endp = p + CardTable::card_size_in_words();
532           assert(!r->is_humongous(), "Process humongous regions elsewhere");
533 
534           if (endp > end_of_range) {
535             endp = end_of_range;
536             next_card_index = end_card_index;
537           } else {
538             // endp either points to start of next card region, or to the next object that needs to be scanned, which may
539             // reside in some successor card region.
540 
541             // Can't use _scc->card_index_for_addr(endp) here because it crashes with assertion
542             // failure if endp points to end of heap.
543             next_card_index = card_index + (endp - card_start) / CardTable::card_size_in_words();
544           }
545 
546           p += start_offset;
547           while (p < endp) {
548             oop obj = cast_to_oop(p);
549 
550             // ctx->is_marked() returns true if mark bit set or if obj above TAMS.
551             if (!ctx || ctx->is_marked(obj)) {
552               // Future TODO:
553               // For improved efficiency, we might want to give special handling of obj->is_objArray().  In
554               // particular, in that case, we might want to divide the effort for scanning of a very long object array
555               // between multiple threads.  Also, skip parts of the array that are not marked as dirty.
556               if (obj->is_objArray()) {
557                 objArrayOop array = objArrayOop(obj);
558                 int len = array->length();
559                 array->oop_iterate_range(cl, 0, len);
560               } else if (obj->is_instance()) {
561                 obj->oop_iterate(cl);
562               } else {
563                 // Case 3: Primitive array. Do nothing, no oops there. We use the same
564                 // performance tweak TypeArrayKlass::oop_oop_iterate_impl is using:
565                 // We skip iterating over the klass pointer since we know that
566                 // Universe::TypeArrayKlass never moves.
567                 assert (obj->is_typeArray(), "should be type array");
568               }
569               p += obj->size();
570             } else {
571               // This object is not marked so we don't scan it.  Containing region r is initialized above.
572               HeapWord* tams = ctx->top_at_mark_start(r);
573               if (p >= tams) {
574                 p += obj->size();
575               } else {
576                 p = ctx->get_next_marked_addr(p, tams);
577               }
578             }
579           }
580           if (p > endp) {
581             card_index = card_index + (p - card_start) / CardTable::card_size_in_words();
582           } else {                  // p == endp
583             card_index = next_card_index;
584           }
585         } else {
586           // Card is dirty but has no object.  Card will have been scanned during scan of a previous cluster.
587           card_index++;
588         }
589       } else if (has_object) {
590         // Card is clean but has object.
591 
592         // Scan the last object that starts within this card memory if it spans at least one dirty card within this cluster
593         // or if it reaches into the next cluster.
594         size_t start_offset = _scc->get_last_start(card_index);
595         HeapWord *card_start = _rs->addr_for_card_index(card_index);
596         HeapWord *p = card_start + start_offset;
597         oop obj = cast_to_oop(p);
598 
599         size_t last_card;
600         if (!ctx || ctx->is_marked(obj)) {
601           HeapWord *nextp = p + obj->size();
602 
603           // Can't use _scc->card_index_for_addr(endp) here because it crashes with assertion
604           // failure if nextp points to end of heap.
605           last_card = card_index + (nextp - card_start) / CardTable::card_size_in_words();
606 
607           bool reaches_next_cluster = (last_card > end_card_index);
608           bool spans_dirty_within_this_cluster = false;
609 
610           if (!reaches_next_cluster) {
611             size_t span_card;
612             for (span_card = card_index+1; span_card <= last_card; span_card++)
613               if ((write_table)? _rs->is_write_card_dirty(span_card): _rs->is_card_dirty(span_card)) {
614                 spans_dirty_within_this_cluster = true;
615                 break;
616               }
617           }
618 
619           // TODO: only iterate over this object if it spans dirty within this cluster or within following clusters.
620           // Code as written is known not to examine a zombie object because either the object is marked, or we are
621           // not using the mark-context to differentiate objects, so the object is known to have been coalesced and
622           // filled if it is not "live".
623 
624           if (reaches_next_cluster || spans_dirty_within_this_cluster) {
625             if (obj->is_objArray()) {
626               objArrayOop array = objArrayOop(obj);
627               int len = array->length();
628               array->oop_iterate_range(cl, 0, len);
629             } else if (obj->is_instance()) {
630               obj->oop_iterate(cl);
631             } else {
632               // Case 3: Primitive array. Do nothing, no oops there. We use the same
633               // performance tweak TypeArrayKlass::oop_oop_iterate_impl is using:
634               // We skip iterating over the klass pointer since we know that
635               // Universe::TypeArrayKlass never moves.
636               assert (obj->is_typeArray(), "should be type array");
637             }
638           }
639         } else {
640           // The object that spans end of this clean card is not marked, so no need to scan it or its
641           // unmarked neighbors.  Containing region r is initialized above.
642           HeapWord* tams = ctx->top_at_mark_start(r);
643           HeapWord* nextp;
644           if (p >= tams) {
645             nextp = p + obj->size();
646           } else {
647             nextp = ctx->get_next_marked_addr(p, tams);
648           }
649           last_card = card_index + (nextp - card_start) / CardTable::card_size_in_words();
650         }
651         // Increment card_index to account for the spanning object, even if we didn't scan it.
652         card_index = (last_card > card_index)? last_card: card_index + 1;
653       } else {
654         // Card is clean and has no object.  No need to clean this card.
655         card_index++;
656       }
657     }
658   }
659 }
660 
661 // Given that this range of clusters is known to span a humongous object spanned by region r, scan the
662 // portion of the humongous object that corresponds to the specified range.
663 template<typename RememberedSet>
664 template <typename ClosureType>
665 inline void
666 ShenandoahScanRemembered<RememberedSet>::process_humongous_clusters(ShenandoahHeapRegion* r, size_t first_cluster, size_t count,
667                                                                     HeapWord *end_of_range, ClosureType *cl, bool write_table,
668                                                                     bool is_concurrent) {
669   ShenandoahHeapRegion* start_region = r->humongous_start_region();
670   HeapWord* p = start_region->bottom();
671   oop obj = cast_to_oop(p);
672   assert(r->is_humongous(), "Only process humongous regions here");
673   assert(start_region->is_humongous_start(), "Should be start of humongous region");
674   assert(p + obj->size() >= end_of_range, "Humongous object ends before range ends");
675 
676   size_t first_card_index = first_cluster * ShenandoahCardCluster<RememberedSet>::CardsPerCluster;
677   HeapWord* first_cluster_addr = _rs->addr_for_card_index(first_card_index);
678   size_t spanned_words = count * ShenandoahCardCluster<RememberedSet>::CardsPerCluster * CardTable::card_size_in_words();
679 
680   start_region->oop_iterate_humongous_slice(cl, true, first_cluster_addr, spanned_words, write_table, is_concurrent);
681 }
682 
683 template<typename RememberedSet>
684 template <typename ClosureType>
685 inline void
686 ShenandoahScanRemembered<RememberedSet>::process_region(ShenandoahHeapRegion *region, ClosureType *cl, bool is_concurrent) {
687   process_region(region, cl, false, is_concurrent);
688 }
689 
690 template<typename RememberedSet>
691 template <typename ClosureType>
692 inline void
693 ShenandoahScanRemembered<RememberedSet>::process_region(ShenandoahHeapRegion *region, ClosureType *cl,
694                                                         bool use_write_table, bool is_concurrent) {
695   size_t cluster_size =
696     CardTable::card_size_in_words() * ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
697   size_t clusters = ShenandoahHeapRegion::region_size_words() / cluster_size;
698   process_region_slice(region, 0, clusters, region->end(), cl, use_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) {
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);
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 inline 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 */);
796       }
797     }
798   }
799 }
800 
801 inline bool ShenandoahRegionChunkIterator::has_next() const {
802   return _index < _total_chunks;
803 }
804 
805 inline bool ShenandoahRegionChunkIterator::next(struct ShenandoahRegionChunk *assignment) {
806   if (_index > _total_chunks) {
807     return false;
808   }
809   size_t new_index = Atomic::add(&_index, (size_t) 1, memory_order_relaxed);
810   if (new_index > _total_chunks) {
811     return false;
812   }
813   // convert to zero-based indexing
814   new_index--;
815 
816   size_t group_no = new_index / _group_size;
817   if (group_no + 1 > _num_groups) {
818     group_no = _num_groups - 1;
819   }
820 
821   // All size computations measured in HeapWord
822   size_t region_size_words = ShenandoahHeapRegion::region_size_words();
823   size_t group_region_index = _region_index[group_no];
824   size_t group_region_offset = _group_offset[group_no];
825 
826   size_t index_within_group = new_index - (group_no * _group_size);
827   size_t group_chunk_size = _first_group_chunk_size >> group_no;
828   size_t offset_of_this_chunk = group_region_offset + index_within_group * group_chunk_size;
829   size_t regions_spanned_by_chunk_offset = offset_of_this_chunk / region_size_words;
830   size_t region_index = group_region_index + regions_spanned_by_chunk_offset;
831   size_t offset_within_region = offset_of_this_chunk % region_size_words;
832 
833   assignment->_r = _heap->get_region(region_index);
834   assignment->_chunk_offset = offset_within_region;
835   assignment->_chunk_size = group_chunk_size;
836 
837   return true;
838 }
839 
840 #endif   // SHARE_GC_SHENANDOAH_SHENANDOAHSCANREMEMBEREDINLINE_HPP