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