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 }