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