1 /*
2 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25
26 #include "precompiled.hpp"
27
28 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
29 #include "gc/shenandoah/shenandoahOopClosures.inline.hpp"
30 #include "gc/shenandoah/shenandoahReferenceProcessor.hpp"
31 #include "gc/shenandoah/shenandoahScanRemembered.inline.hpp"
32 #include "logging/log.hpp"
33
34 ShenandoahDirectCardMarkRememberedSet::ShenandoahDirectCardMarkRememberedSet(ShenandoahCardTable* card_table, size_t total_card_count) :
35 LogCardValsPerIntPtr(log2i_exact(sizeof(intptr_t)) - log2i_exact(sizeof(CardValue))),
36 LogCardSizeInWords(log2i_exact(CardTable::card_size_in_words())) {
37
38 // Paranoid assert for LogCardsPerIntPtr calculation above
39 assert(sizeof(intptr_t) > sizeof(CardValue), "LogsCardValsPerIntPtr would underflow");
40
41 _heap = ShenandoahHeap::heap();
42 _card_table = card_table;
43 _total_card_count = total_card_count;
44 _cluster_count = total_card_count / ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
45 _card_shift = CardTable::card_shift();
46
47 _byte_map = _card_table->byte_for_index(0);
48
49 _whole_heap_base = _card_table->addr_for(_byte_map);
50 _byte_map_base = _byte_map - (uintptr_t(_whole_heap_base) >> _card_shift);
51
52 assert(total_card_count % ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster == 0, "Invalid card count.");
53 assert(total_card_count > 0, "Card count cannot be zero.");
54 }
55
56 // Merge any dirty values from write table into the read table, while leaving
57 // the write table unchanged.
58 void ShenandoahDirectCardMarkRememberedSet::merge_write_table(HeapWord* start, size_t word_count) {
59 size_t start_index = card_index_for_addr(start);
60 #ifdef ASSERT
61 // avoid querying card_index_for_addr() for an address past end of heap
62 size_t end_index = card_index_for_addr(start + word_count - 1) + 1;
63 #endif
64 assert(start_index % ((size_t)1 << LogCardValsPerIntPtr) == 0, "Expected a multiple of CardValsPerIntPtr");
65 assert(end_index % ((size_t)1 << LogCardValsPerIntPtr) == 0, "Expected a multiple of CardValsPerIntPtr");
66
67 // We'll access in groups of intptr_t worth of card entries
68 intptr_t* const read_table = (intptr_t*) &(_card_table->read_byte_map())[start_index];
69 intptr_t* const write_table = (intptr_t*) &(_card_table->write_byte_map())[start_index];
70
71 // Avoid division, use shift instead
72 assert(word_count % ((size_t)1 << (LogCardSizeInWords + LogCardValsPerIntPtr)) == 0, "Expected a multiple of CardSizeInWords*CardValsPerIntPtr");
73 size_t const num = word_count >> (LogCardSizeInWords + LogCardValsPerIntPtr);
74
75 for (size_t i = 0; i < num; i++) {
76 read_table[i] &= write_table[i];
77 }
78 }
79
80 // Destructively copy the write table to the read table, and clean the write table.
81 void ShenandoahDirectCardMarkRememberedSet::reset_remset(HeapWord* start, size_t word_count) {
82 size_t start_index = card_index_for_addr(start);
83 #ifdef ASSERT
84 // avoid querying card_index_for_addr() for an address past end of heap
85 size_t end_index = card_index_for_addr(start + word_count - 1) + 1;
86 #endif
87 assert(start_index % ((size_t)1 << LogCardValsPerIntPtr) == 0, "Expected a multiple of CardValsPerIntPtr");
88 assert(end_index % ((size_t)1 << LogCardValsPerIntPtr) == 0, "Expected a multiple of CardValsPerIntPtr");
89
90 // We'll access in groups of intptr_t worth of card entries
91 intptr_t* const read_table = (intptr_t*) &(_card_table->read_byte_map())[start_index];
92 intptr_t* const write_table = (intptr_t*) &(_card_table->write_byte_map())[start_index];
93
94 // Avoid division, use shift instead
95 assert(word_count % ((size_t)1 << (LogCardSizeInWords + LogCardValsPerIntPtr)) == 0, "Expected a multiple of CardSizeInWords*CardValsPerIntPtr");
96 size_t const num = word_count >> (LogCardSizeInWords + LogCardValsPerIntPtr);
97
98 for (size_t i = 0; i < num; i++) {
99 read_table[i] = write_table[i];
100 write_table[i] = CardTable::clean_card_row_val();
101 }
102 }
103
104 ShenandoahScanRememberedTask::ShenandoahScanRememberedTask(ShenandoahObjToScanQueueSet* queue_set,
105 ShenandoahObjToScanQueueSet* old_queue_set,
106 ShenandoahReferenceProcessor* rp,
107 ShenandoahRegionChunkIterator* work_list, bool is_concurrent) :
108 WorkerTask("Scan Remembered Set"),
109 _queue_set(queue_set), _old_queue_set(old_queue_set), _rp(rp), _work_list(work_list), _is_concurrent(is_concurrent) {
110 log_info(gc, remset)("Scan remembered set using bitmap: %s", BOOL_TO_STR(ShenandoahHeap::heap()->is_old_bitmap_stable()));
111 }
112
113 void ShenandoahScanRememberedTask::work(uint worker_id) {
114 if (_is_concurrent) {
115 // This sets up a thread local reference to the worker_id which is needed by the weak reference processor.
116 ShenandoahConcurrentWorkerSession worker_session(worker_id);
117 ShenandoahSuspendibleThreadSetJoiner stsj(ShenandoahSuspendibleWorkers);
118 do_work(worker_id);
119 } else {
120 // This sets up a thread local reference to the worker_id which is needed by the weak reference processor.
121 ShenandoahParallelWorkerSession worker_session(worker_id);
122 do_work(worker_id);
123 }
124 }
125
126 void ShenandoahScanRememberedTask::do_work(uint worker_id) {
127 ShenandoahWorkerTimingsTracker x(ShenandoahPhaseTimings::init_scan_rset, ShenandoahPhaseTimings::ScanClusters, worker_id);
128
129 ShenandoahObjToScanQueue* q = _queue_set->queue(worker_id);
130 ShenandoahObjToScanQueue* old = _old_queue_set == nullptr ? nullptr : _old_queue_set->queue(worker_id);
131 ShenandoahMarkRefsClosure<YOUNG> cl(q, _rp, old);
132 ShenandoahHeap* heap = ShenandoahHeap::heap();
133 RememberedScanner* scanner = heap->card_scan();
134
135 // set up thread local closure for shen ref processor
136 _rp->set_mark_closure(worker_id, &cl);
137 struct ShenandoahRegionChunk assignment;
138 while (_work_list->next(&assignment)) {
139 ShenandoahHeapRegion* region = assignment._r;
140 log_debug(gc)("ShenandoahScanRememberedTask::do_work(%u), processing slice of region "
141 SIZE_FORMAT " at offset " SIZE_FORMAT ", size: " SIZE_FORMAT,
142 worker_id, region->index(), assignment._chunk_offset, assignment._chunk_size);
143 if (region->is_old()) {
144 size_t cluster_size =
145 CardTable::card_size_in_words() * ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
146 size_t clusters = assignment._chunk_size / cluster_size;
147 assert(clusters * cluster_size == assignment._chunk_size, "Chunk assignments must align on cluster boundaries");
148 HeapWord* end_of_range = region->bottom() + assignment._chunk_offset + assignment._chunk_size;
149
150 // During concurrent mark, region->top() equals TAMS with respect to the current young-gen pass.
151 if (end_of_range > region->top()) {
152 end_of_range = region->top();
153 }
154 scanner->process_region_slice(region, assignment._chunk_offset, clusters, end_of_range, &cl, false, worker_id);
155 }
156 #ifdef ENABLE_REMEMBERED_SET_CANCELLATION
157 // This check is currently disabled to avoid crashes that occur
158 // when we try to cancel remembered set scanning; it should be re-enabled
159 // after the issues are fixed, as it would allow more prompt cancellation and
160 // transition to degenerated / full GCs. Note that work that has been assigned/
161 // claimed above must be completed before we return here upon cancellation.
162 if (heap->check_cancelled_gc_and_yield(_is_concurrent)) {
163 return;
164 }
165 #endif
166 }
167 }
168
169 size_t ShenandoahRegionChunkIterator::calc_regular_group_size() {
170 // The group size is calculated from the number of regions. Suppose the heap has N regions. The first group processes
171 // N/2 regions. The second group processes N/4 regions, the third group N/8 regions and so on.
172 // Note that infinite series N/2 + N/4 + N/8 + N/16 + ... sums to N.
173 //
174 // The normal group size is the number of regions / 2.
175 //
176 // In the case that the region_size_words is greater than _maximum_chunk_size_words, the first group_size is
177 // larger than the normal group size because each chunk in the group will be smaller than the region size.
178 //
179 // The last group also has more than the normal entries because it finishes the total scanning effort. The chunk sizes are
180 // different for each group. The intention is that the first group processes roughly half of the heap, the second processes
181 // half of the remaining heap, the third processes half of what remains and so on. The smallest chunk size
182 // is represented by _smallest_chunk_size_words. We do not divide work any smaller than this.
183 //
184
185 size_t group_size = _heap->num_regions() / 2;
186 return group_size;
187 }
188
189 size_t ShenandoahRegionChunkIterator::calc_first_group_chunk_size_b4_rebalance() {
190 size_t words_in_first_chunk = ShenandoahHeapRegion::region_size_words();
191 return words_in_first_chunk;
192 }
193
194 size_t ShenandoahRegionChunkIterator::calc_num_groups() {
195 size_t total_heap_size = _heap->num_regions() * ShenandoahHeapRegion::region_size_words();
196 size_t num_groups = 0;
197 size_t cumulative_group_span = 0;
198 size_t current_group_span = _first_group_chunk_size_b4_rebalance * _regular_group_size;
199 size_t smallest_group_span = smallest_chunk_size_words() * _regular_group_size;
200 while ((num_groups < _maximum_groups) && (cumulative_group_span + current_group_span <= total_heap_size)) {
201 num_groups++;
202 cumulative_group_span += current_group_span;
203 if (current_group_span <= smallest_group_span) {
204 break;
205 } else {
206 current_group_span /= 2; // Each group spans half of what the preceding group spanned.
207 }
208 }
209 // Loop post condition:
210 // num_groups <= _maximum_groups
211 // cumulative_group_span is the memory spanned by num_groups
212 // current_group_span is the span of the last fully populated group (assuming loop iterates at least once)
213 // each of num_groups is fully populated with _regular_group_size chunks in each
214 // Non post conditions:
215 // cumulative_group_span may be less than total_heap size for one or more of the folowing reasons
216 // a) The number of regions remaining to be spanned is smaller than a complete group, or
217 // b) We have filled up all groups through _maximum_groups and still have not spanned all regions
218
219 if (cumulative_group_span < total_heap_size) {
220 // We've got more regions to span
221 if ((num_groups < _maximum_groups) && (current_group_span > smallest_group_span)) {
222 num_groups++; // Place all remaining regions into a new not-full group (chunk_size half that of previous group)
223 }
224 // Else we are unable to create a new group because we've exceed the number of allowed groups or have reached the
225 // minimum chunk size.
226
227 // Any remaining regions will be treated as if they are part of the most recently created group. This group will
228 // have more than _regular_group_size chunks within it.
229 }
230 return num_groups;
231 }
232
233 size_t ShenandoahRegionChunkIterator::calc_total_chunks() {
234 size_t region_size_words = ShenandoahHeapRegion::region_size_words();
235 size_t unspanned_heap_size = _heap->num_regions() * region_size_words;
236 size_t num_chunks = 0;
237 size_t cumulative_group_span = 0;
238 size_t current_group_span = _first_group_chunk_size_b4_rebalance * _regular_group_size;
239 size_t smallest_group_span = smallest_chunk_size_words() * _regular_group_size;
240
241 // The first group gets special handling because the first chunk size can be no larger than _largest_chunk_size_words
242 if (region_size_words > _maximum_chunk_size_words) {
243 // In the case that we shrink the first group's chunk size, certain other groups will also be subsumed within the first group
244 size_t effective_chunk_size = _first_group_chunk_size_b4_rebalance;
245 while (effective_chunk_size >= _maximum_chunk_size_words) {
246 num_chunks += current_group_span / _maximum_chunk_size_words;
247 unspanned_heap_size -= current_group_span;
248 effective_chunk_size /= 2;
249 current_group_span /= 2;
250 }
251 } else {
252 num_chunks = _regular_group_size;
253 unspanned_heap_size -= current_group_span;
254 current_group_span /= 2;
255 }
256 size_t spanned_groups = 1;
257 while (unspanned_heap_size > 0) {
258 if (current_group_span <= unspanned_heap_size) {
259 unspanned_heap_size -= current_group_span;
260 num_chunks += _regular_group_size;
261 spanned_groups++;
262
263 // _num_groups is the number of groups required to span the configured heap size. We are not allowed
264 // to change the number of groups. The last group is responsible for spanning all chunks not spanned
265 // by previously processed groups.
266 if (spanned_groups >= _num_groups) {
267 // The last group has more than _regular_group_size entries.
268 size_t chunk_span = current_group_span / _regular_group_size;
269 size_t extra_chunks = unspanned_heap_size / chunk_span;
270 assert (extra_chunks * chunk_span == unspanned_heap_size, "Chunks must precisely span regions");
271 num_chunks += extra_chunks;
272 return num_chunks;
273 } else if (current_group_span <= smallest_group_span) {
274 // We cannot introduce new groups because we've reached the lower bound on group size. So this last
275 // group may hold extra chunks.
276 size_t chunk_span = smallest_chunk_size_words();
277 size_t extra_chunks = unspanned_heap_size / chunk_span;
278 assert (extra_chunks * chunk_span == unspanned_heap_size, "Chunks must precisely span regions");
279 num_chunks += extra_chunks;
280 return num_chunks;
281 } else {
282 current_group_span /= 2;
283 }
284 } else {
285 // This last group has fewer than _regular_group_size entries.
286 size_t chunk_span = current_group_span / _regular_group_size;
287 size_t last_group_size = unspanned_heap_size / chunk_span;
288 assert (last_group_size * chunk_span == unspanned_heap_size, "Chunks must precisely span regions");
289 num_chunks += last_group_size;
290 return num_chunks;
291 }
292 }
293 return num_chunks;
294 }
295
296 ShenandoahRegionChunkIterator::ShenandoahRegionChunkIterator(size_t worker_count) :
297 ShenandoahRegionChunkIterator(ShenandoahHeap::heap(), worker_count)
298 {
299 }
300
301 ShenandoahRegionChunkIterator::ShenandoahRegionChunkIterator(ShenandoahHeap* heap, size_t worker_count) :
302 _heap(heap),
303 _regular_group_size(calc_regular_group_size()),
304 _first_group_chunk_size_b4_rebalance(calc_first_group_chunk_size_b4_rebalance()),
305 _num_groups(calc_num_groups()),
306 _total_chunks(calc_total_chunks()),
307 _index(0)
308 {
309 #ifdef ASSERT
310 size_t expected_chunk_size_words = _clusters_in_smallest_chunk * CardTable::card_size_in_words() * ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
311 assert(smallest_chunk_size_words() == expected_chunk_size_words, "_smallest_chunk_size (" SIZE_FORMAT") is not valid because it does not equal (" SIZE_FORMAT ")",
312 smallest_chunk_size_words(), expected_chunk_size_words);
313 #endif
314 assert(_num_groups <= _maximum_groups,
315 "The number of remembered set scanning groups must be less than or equal to maximum groups");
316 assert(smallest_chunk_size_words() << (_maximum_groups - 1) == _maximum_chunk_size_words,
317 "Maximum number of groups needs to span maximum chunk size to smallest chunk size");
318
319 size_t words_in_region = ShenandoahHeapRegion::region_size_words();
320 _region_index[0] = 0;
321 _group_offset[0] = 0;
322 if (words_in_region > _maximum_chunk_size_words) {
323 // In the case that we shrink the first group's chunk size, certain other groups will also be subsumed within the first group
324 size_t num_chunks = 0;
325 size_t effective_chunk_size = _first_group_chunk_size_b4_rebalance;
326 size_t current_group_span = effective_chunk_size * _regular_group_size;
327 while (effective_chunk_size >= _maximum_chunk_size_words) {
328 num_chunks += current_group_span / _maximum_chunk_size_words;
329 effective_chunk_size /= 2;
330 current_group_span /= 2;
331 }
332 _group_entries[0] = num_chunks;
333 _group_chunk_size[0] = _maximum_chunk_size_words;
334 } else {
335 _group_entries[0] = _regular_group_size;
336 _group_chunk_size[0] = _first_group_chunk_size_b4_rebalance;
337 }
338
339 size_t previous_group_span = _group_entries[0] * _group_chunk_size[0];
340 for (size_t i = 1; i < _num_groups; i++) {
341 size_t previous_group_entries = (i == 1)? _group_entries[0]: (_group_entries[i-1] - _group_entries[i-2]);
342 _group_chunk_size[i] = _group_chunk_size[i-1] / 2;
343 size_t chunks_in_group = _regular_group_size;
344 size_t this_group_span = _group_chunk_size[i] * chunks_in_group;
345 size_t total_span_of_groups = previous_group_span + this_group_span;
346 _region_index[i] = previous_group_span / words_in_region;
347 _group_offset[i] = previous_group_span % words_in_region;
348 _group_entries[i] = _group_entries[i-1] + _regular_group_size;
349 previous_group_span = total_span_of_groups;
350 }
351 if (_group_entries[_num_groups-1] < _total_chunks) {
352 assert((_total_chunks - _group_entries[_num_groups-1]) * _group_chunk_size[_num_groups-1] + previous_group_span ==
353 heap->num_regions() * words_in_region, "Total region chunks (" SIZE_FORMAT
354 ") do not span total heap regions (" SIZE_FORMAT ")", _total_chunks, _heap->num_regions());
355 previous_group_span += (_total_chunks - _group_entries[_num_groups-1]) * _group_chunk_size[_num_groups-1];
356 _group_entries[_num_groups-1] = _total_chunks;
357 }
358 assert(previous_group_span == heap->num_regions() * words_in_region, "Total region chunks (" SIZE_FORMAT
359 ") do not span total heap regions (" SIZE_FORMAT "): " SIZE_FORMAT " does not equal " SIZE_FORMAT,
360 _total_chunks, _heap->num_regions(), previous_group_span, heap->num_regions() * words_in_region);
361
362 // Not necessary, but keeps things tidy
363 for (size_t i = _num_groups; i < _maximum_groups; i++) {
364 _region_index[i] = 0;
365 _group_offset[i] = 0;
366 _group_entries[i] = _group_entries[i-1];
367 _group_chunk_size[i] = 0;
368 }
369 }
370
371 void ShenandoahRegionChunkIterator::reset() {
372 _index = 0;
373 }