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
27 #include "precompiled.hpp"
28
29 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
30 #include "gc/shenandoah/shenandoahOopClosures.inline.hpp"
31 #include "gc/shenandoah/shenandoahReferenceProcessor.hpp"
32 #include "gc/shenandoah/shenandoahScanRemembered.inline.hpp"
33
34 ShenandoahDirectCardMarkRememberedSet::ShenandoahDirectCardMarkRememberedSet(ShenandoahCardTable* card_table, size_t total_card_count) {
35 _heap = ShenandoahHeap::heap();
36 _card_table = card_table;
37 _total_card_count = total_card_count;
38 _cluster_count = total_card_count / ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
39 _card_shift = CardTable::card_shift();
40
41 _byte_map = _card_table->byte_for_index(0);
42
43 _whole_heap_base = _card_table->addr_for(_byte_map);
44 _byte_map_base = _byte_map - (uintptr_t(_whole_heap_base) >> _card_shift);
45
46 assert(total_card_count % ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster == 0, "Invalid card count.");
47 assert(total_card_count > 0, "Card count cannot be zero.");
48 }
49
50 ShenandoahScanRememberedTask::ShenandoahScanRememberedTask(ShenandoahObjToScanQueueSet* queue_set,
51 ShenandoahObjToScanQueueSet* old_queue_set,
52 ShenandoahReferenceProcessor* rp,
53 ShenandoahRegionChunkIterator* work_list, bool is_concurrent) :
54 WorkerTask("Scan Remembered Set"),
55 _queue_set(queue_set), _old_queue_set(old_queue_set), _rp(rp), _work_list(work_list), _is_concurrent(is_concurrent) {}
56
57 void ShenandoahScanRememberedTask::work(uint worker_id) {
58 if (_is_concurrent) {
59 // This sets up a thread local reference to the worker_id which is needed by the weak reference processor.
60 ShenandoahConcurrentWorkerSession worker_session(worker_id);
61 ShenandoahSuspendibleThreadSetJoiner stsj(ShenandoahSuspendibleWorkers);
62 do_work(worker_id);
63 } else {
64 // This sets up a thread local reference to the worker_id which is needed by the weak reference processor.
65 ShenandoahParallelWorkerSession worker_session(worker_id);
66 do_work(worker_id);
67 }
68 }
69
70 void ShenandoahScanRememberedTask::do_work(uint worker_id) {
71 ShenandoahWorkerTimingsTracker x(ShenandoahPhaseTimings::init_scan_rset, ShenandoahPhaseTimings::ScanClusters, worker_id);
72
73 ShenandoahObjToScanQueue* q = _queue_set->queue(worker_id);
74 ShenandoahObjToScanQueue* old = _old_queue_set == NULL ? NULL : _old_queue_set->queue(worker_id);
75 ShenandoahMarkRefsClosure<YOUNG> cl(q, _rp, old);
76 ShenandoahHeap* heap = ShenandoahHeap::heap();
77 RememberedScanner* scanner = heap->card_scan();
78
79 // set up thread local closure for shen ref processor
80 _rp->set_mark_closure(worker_id, &cl);
81 struct ShenandoahRegionChunk assignment;
82 bool has_work = _work_list->next(&assignment);
83 while (has_work) {
84 #ifdef ENABLE_REMEMBERED_SET_CANCELLATION
85 // This check is currently disabled to avoid crashes that occur
86 // when we try to cancel remembered set scanning
87 if (heap->check_cancelled_gc_and_yield(_is_concurrent)) {
88 return;
89 }
90 #endif
91 ShenandoahHeapRegion* region = assignment._r;
92 log_debug(gc)("ShenandoahScanRememberedTask::do_work(%u), processing slice of region "
93 SIZE_FORMAT " at offset " SIZE_FORMAT ", size: " SIZE_FORMAT,
94 worker_id, region->index(), assignment._chunk_offset, assignment._chunk_size);
95 if (region->affiliation() == OLD_GENERATION) {
96 size_t cluster_size =
97 CardTable::card_size_in_words() * ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster;
98 size_t clusters = assignment._chunk_size / cluster_size;
99 assert(clusters * cluster_size == assignment._chunk_size, "Chunk assignments must align on cluster boundaries");
100 HeapWord* end_of_range = region->bottom() + assignment._chunk_offset + assignment._chunk_size;
101
102 // During concurrent mark, region->top() equals TAMS with respect to the current young-gen pass. */
103 if (end_of_range > region->top()) {
104 end_of_range = region->top();
105 }
106 scanner->process_region_slice(region, assignment._chunk_offset, clusters, end_of_range, &cl, false, _is_concurrent);
107 }
108 has_work = _work_list->next(&assignment);
109 }
110 }
111
112 size_t ShenandoahRegionChunkIterator::calc_group_size() {
113 // The group size s calculated from the number of regions. Every group except the last processes the same number of chunks.
114 // The last group processes however many chunks are required to finish the total scanning effort. The chunk sizes are
115 // different for each group. The intention is that the first group processes roughly half of the heap, the second processes
116 // a quarter of the remaining heap, the third processes an eight of what remains and so on. The smallest chunk size
117 // is represented by _smallest_chunk_size. We do not divide work any smaller than this.
118 //
119 // Note that N/2 + N/4 + N/8 + N/16 + ... sums to N if expanded to infinite terms.
120 return _heap->num_regions() / 2;
121 }
122
123 size_t ShenandoahRegionChunkIterator::calc_first_group_chunk_size() {
124 size_t words_in_region = ShenandoahHeapRegion::region_size_words();
125 return words_in_region;
126 }
127
128 size_t ShenandoahRegionChunkIterator::calc_num_groups() {
129 size_t total_heap_size = _heap->num_regions() * ShenandoahHeapRegion::region_size_words();
130 size_t num_groups = 0;
131 size_t cumulative_group_span = 0;
132 size_t current_group_span = _first_group_chunk_size * _group_size;
133 size_t smallest_group_span = _smallest_chunk_size * _group_size;
134 while ((num_groups < _maximum_groups) && (cumulative_group_span + current_group_span <= total_heap_size)) {
135 num_groups++;
136 cumulative_group_span += current_group_span;
137 if (current_group_span <= smallest_group_span) {
138 break;
139 } else {
140 current_group_span /= 2; // Each group spans half of what the preceding group spanned.
141 }
142 }
143 // Loop post condition:
144 // num_groups <= _maximum_groups
145 // cumulative_group_span is the memory spanned by num_groups
146 // current_group_span is the span of the last fully populated group (assuming loop iterates at least once)
147 // each of num_groups is fully populated with _group_size chunks in each
148 // Non post conditions:
149 // cumulative_group_span may be less than total_heap size for one or more of the folowing reasons
150 // a) The number of regions remaining to be spanned is smaller than a complete group, or
151 // b) We have filled up all groups through _maximum_groups and still have not spanned all regions
152
153 if (cumulative_group_span < total_heap_size) {
154 // We've got more regions to span
155 if ((num_groups < _maximum_groups) && (current_group_span > smallest_group_span)) {
156 num_groups++; // Place all remaining regions into a new not-full group (chunk_size half that of previous group)
157 }
158 // Else we are unable to create a new group because we've exceed the number of allowed groups or have reached the
159 // minimum chunk size.
160
161 // Any remaining regions will be treated as if they are part of the most recently created group. This group will
162 // have more than _group_size chunks within it.
163 }
164 return num_groups;
165 }
166
167 size_t ShenandoahRegionChunkIterator::calc_total_chunks() {
168 size_t region_size_words = ShenandoahHeapRegion::region_size_words();
169 size_t unspanned_heap_size = _heap->num_regions() * region_size_words;
170 size_t num_chunks = 0;
171 size_t spanned_groups = 0;
172 size_t cumulative_group_span = 0;
173 size_t current_group_span = _first_group_chunk_size * _group_size;
174 size_t smallest_group_span = _smallest_chunk_size * _group_size;
175 while (unspanned_heap_size > 0) {
176 if (current_group_span <= unspanned_heap_size) {
177 unspanned_heap_size -= current_group_span;
178 num_chunks += _group_size;
179 spanned_groups++;
180
181 // _num_groups is the number of groups required to span the configured heap size. We are not allowed
182 // to change the number of groups. The last group is responsible for spanning all chunks not spanned
183 // by previously processed groups.
184 if (spanned_groups >= _num_groups) {
185 // The last group has more than _group_size entries.
186 size_t chunk_span = current_group_span / _group_size;
187 size_t extra_chunks = unspanned_heap_size / chunk_span;
188 assert (extra_chunks * chunk_span == unspanned_heap_size, "Chunks must precisely span regions");
189 num_chunks += extra_chunks;
190 return num_chunks;
191 } else if (current_group_span <= smallest_group_span) {
192 // We cannot introduce new groups because we've reached the lower bound on group size
193 size_t chunk_span = _smallest_chunk_size;
194 size_t extra_chunks = unspanned_heap_size / chunk_span;
195 assert (extra_chunks * chunk_span == unspanned_heap_size, "Chunks must precisely span regions");
196 num_chunks += extra_chunks;
197 return num_chunks;
198 } else {
199 current_group_span /= 2;
200 }
201 } else {
202 // The last group has fewer than _group_size entries.
203 size_t chunk_span = current_group_span / _group_size;
204 size_t last_group_size = unspanned_heap_size / chunk_span;
205 assert (last_group_size * chunk_span == unspanned_heap_size, "Chunks must precisely span regions");
206 num_chunks += last_group_size;
207 return num_chunks;
208 }
209 }
210 return num_chunks;
211 }
212
213 ShenandoahRegionChunkIterator::ShenandoahRegionChunkIterator(size_t worker_count) :
214 ShenandoahRegionChunkIterator(ShenandoahHeap::heap(), worker_count)
215 {
216 }
217
218 ShenandoahRegionChunkIterator::ShenandoahRegionChunkIterator(ShenandoahHeap* heap, size_t worker_count) :
219 _heap(heap),
220 _group_size(calc_group_size()),
221 _first_group_chunk_size(calc_first_group_chunk_size()),
222 _num_groups(calc_num_groups()),
223 _total_chunks(calc_total_chunks()),
224 _index(0)
225 {
226 assert(_smallest_chunk_size ==
227 CardTable::card_size_in_words() * ShenandoahCardCluster<ShenandoahDirectCardMarkRememberedSet>::CardsPerCluster,
228 "_smallest_chunk_size is not valid");
229
230 size_t words_in_region = ShenandoahHeapRegion::region_size_words();
231 size_t group_span = _first_group_chunk_size * _group_size;
232
233 _region_index[0] = 0;
234 _group_offset[0] = 0;
235 for (size_t i = 1; i < _num_groups; i++) {
236 _region_index[i] = _region_index[i-1] + (_group_offset[i-1] + group_span) / words_in_region;
237 _group_offset[i] = (_group_offset[i-1] + group_span) % words_in_region;
238 group_span /= 2;
239 }
240 // Not necessary, but keeps things tidy
241 for (size_t i = _num_groups; i < _maximum_groups; i++) {
242 _region_index[i] = 0;
243 _group_offset[i] = 0;
244 }
245 }
246
247 void ShenandoahRegionChunkIterator::reset() {
248 _index = 0;
249 }