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