1 /*
2 * Copyright (c) 2016, Oracle and/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 #include "precompiled.hpp"
26 #include "gc/g1/g1CollectedHeap.hpp"
27 #include "gc/g1/g1CollectionSet.hpp"
28 #include "gc/g1/g1CollectorPolicy.hpp"
29 #include "gc/g1/g1CollectorState.hpp"
30 #include "gc/g1/heapRegion.inline.hpp"
31 #include "gc/g1/heapRegionRemSet.hpp"
32 #include "gc/g1/heapRegionSet.hpp"
33 #include "utilities/debug.hpp"
34
35 G1CollectorState* G1CollectionSet::collector_state() {
36 return _g1->collector_state();
37 }
38
39 G1GCPhaseTimes* G1CollectionSet::phase_times() {
40 return _g1p->phase_times();
41 }
42
43 CollectionSetChooser* G1CollectionSet::cset_chooser() {
44 return _cset_chooser;
45 }
46
47 double G1CollectionSet::predict_region_elapsed_time_ms(HeapRegion* hr) {
48 return _g1p->predict_region_elapsed_time_ms(hr, collector_state()->gcs_are_young());
49 }
50
51
52 G1CollectionSet::G1CollectionSet(G1CollectedHeap* g1h, G1CollectorPolicy* g1p) :
53 _g1(g1h),
54 _g1p(g1p),
55 _cset_chooser(new CollectionSetChooser()),
56 _eden_region_length(0),
57 _survivor_region_length(0),
58 _old_region_length(0),
59
60 _head(NULL),
61 _bytes_used_before(0),
62 _recorded_rs_lengths(0),
63 // Incremental CSet attributes
64 _inc_build_state(Inactive),
65 _inc_head(NULL),
66 _inc_tail(NULL),
67 _inc_bytes_used_before(0),
68 _inc_recorded_rs_lengths(0),
69 _inc_recorded_rs_lengths_diffs(0),
70 _inc_predicted_elapsed_time_ms(0.0),
71 _inc_predicted_elapsed_time_ms_diffs(0.0) {}
72
73 G1CollectionSet::~G1CollectionSet() {
74 delete _cset_chooser;
75 }
76
77 void G1CollectionSet::init_region_lengths(uint eden_cset_region_length,
78 uint survivor_cset_region_length) {
79 _eden_region_length = eden_cset_region_length;
80 _survivor_region_length = survivor_cset_region_length;
81 _old_region_length = 0;
82 }
83
84 void G1CollectionSet::set_recorded_rs_lengths(size_t rs_lengths) {
85 _recorded_rs_lengths = rs_lengths;
86 }
87
88 // Add the heap region at the head of the non-incremental collection set
89 void G1CollectionSet::add_old_region(HeapRegion* hr) {
90 assert(_inc_build_state == Active, "Precondition");
91 assert(hr->is_old(), "the region should be old");
92
93 assert(!hr->in_collection_set(), "should not already be in the CSet");
94 _g1->register_old_region_with_cset(hr);
95 hr->set_next_in_collection_set(_head);
96 _head = hr;
97 _bytes_used_before += hr->used();
98 size_t rs_length = hr->rem_set()->occupied();
99 _recorded_rs_lengths += rs_length;
100 _old_region_length += 1;
101 }
102
103 // Initialize the per-collection-set information
104 void G1CollectionSet::start_incremental_building() {
105 assert(_inc_build_state == Inactive, "Precondition");
106
107 _inc_head = NULL;
108 _inc_tail = NULL;
109 _inc_bytes_used_before = 0;
110
111 _inc_recorded_rs_lengths = 0;
112 _inc_recorded_rs_lengths_diffs = 0;
113 _inc_predicted_elapsed_time_ms = 0.0;
114 _inc_predicted_elapsed_time_ms_diffs = 0.0;
115 _inc_build_state = Active;
116 }
117
118 void G1CollectionSet::finalize_incremental_building() {
119 assert(_inc_build_state == Active, "Precondition");
120 assert(SafepointSynchronize::is_at_safepoint(), "should be at a safepoint");
121
122 // The two "main" fields, _inc_cset_recorded_rs_lengths and
123 // _inc_cset_predicted_elapsed_time_ms, are updated by the thread
124 // that adds a new region to the CSet. Further updates by the
125 // concurrent refinement thread that samples the young RSet lengths
126 // are accumulated in the *_diffs fields. Here we add the diffs to
127 // the "main" fields.
128
129 if (_inc_recorded_rs_lengths_diffs >= 0) {
130 _inc_recorded_rs_lengths += _inc_recorded_rs_lengths_diffs;
131 } else {
132 // This is defensive. The diff should in theory be always positive
133 // as RSets can only grow between GCs. However, given that we
134 // sample their size concurrently with other threads updating them
135 // it's possible that we might get the wrong size back, which
136 // could make the calculations somewhat inaccurate.
137 size_t diffs = (size_t) (-_inc_recorded_rs_lengths_diffs);
138 if (_inc_recorded_rs_lengths >= diffs) {
139 _inc_recorded_rs_lengths -= diffs;
140 } else {
141 _inc_recorded_rs_lengths = 0;
142 }
143 }
144 _inc_predicted_elapsed_time_ms +=
145 _inc_predicted_elapsed_time_ms_diffs;
146
147 _inc_recorded_rs_lengths_diffs = 0;
148 _inc_predicted_elapsed_time_ms_diffs = 0.0;
149 }
150
151 void G1CollectionSet::update_young_region_prediction(HeapRegion* hr,
152 size_t new_rs_length) {
153 // Update the CSet information that is dependent on the new RS length
154 assert(hr->is_young(), "Precondition");
155 assert(!SafepointSynchronize::is_at_safepoint(),
156 "should not be at a safepoint");
157
158 // We could have updated _inc_cset_recorded_rs_lengths and
159 // _inc_cset_predicted_elapsed_time_ms directly but we'd need to do
160 // that atomically, as this code is executed by a concurrent
161 // refinement thread, potentially concurrently with a mutator thread
162 // allocating a new region and also updating the same fields. To
163 // avoid the atomic operations we accumulate these updates on two
164 // separate fields (*_diffs) and we'll just add them to the "main"
165 // fields at the start of a GC.
166
167 ssize_t old_rs_length = (ssize_t) hr->recorded_rs_length();
168 ssize_t rs_lengths_diff = (ssize_t) new_rs_length - old_rs_length;
169 _inc_recorded_rs_lengths_diffs += rs_lengths_diff;
170
171 double old_elapsed_time_ms = hr->predicted_elapsed_time_ms();
172 double new_region_elapsed_time_ms = predict_region_elapsed_time_ms(hr);
173 double elapsed_ms_diff = new_region_elapsed_time_ms - old_elapsed_time_ms;
174 _inc_predicted_elapsed_time_ms_diffs += elapsed_ms_diff;
175
176 hr->set_recorded_rs_length(new_rs_length);
177 hr->set_predicted_elapsed_time_ms(new_region_elapsed_time_ms);
178 }
179
180 void G1CollectionSet::add_young_region_common(HeapRegion* hr) {
181 assert(hr->is_young(), "invariant");
182 assert(hr->young_index_in_cset() > -1, "should have already been set");
183 assert(_inc_build_state == Active, "Precondition");
184
185 // This routine is used when:
186 // * adding survivor regions to the incremental cset at the end of an
187 // evacuation pause or
188 // * adding the current allocation region to the incremental cset
189 // when it is retired.
190 // Therefore this routine may be called at a safepoint by the
191 // VM thread, or in-between safepoints by mutator threads (when
192 // retiring the current allocation region)
193 // We need to clear and set the cached recorded/cached collection set
194 // information in the heap region here (before the region gets added
195 // to the collection set). An individual heap region's cached values
196 // are calculated, aggregated with the policy collection set info,
197 // and cached in the heap region here (initially) and (subsequently)
198 // by the Young List sampling code.
199
200 size_t rs_length = hr->rem_set()->occupied();
201 double region_elapsed_time_ms = predict_region_elapsed_time_ms(hr);
202
203 // Cache the values we have added to the aggregated information
204 // in the heap region in case we have to remove this region from
205 // the incremental collection set, or it is updated by the
206 // rset sampling code
207 hr->set_recorded_rs_length(rs_length);
208 hr->set_predicted_elapsed_time_ms(region_elapsed_time_ms);
209
210 size_t used_bytes = hr->used();
211 _inc_recorded_rs_lengths += rs_length;
212 _inc_predicted_elapsed_time_ms += region_elapsed_time_ms;
213 _inc_bytes_used_before += used_bytes;
214
215 assert(!hr->in_collection_set(), "invariant");
216 _g1->register_young_region_with_cset(hr);
217 assert(hr->next_in_collection_set() == NULL, "invariant");
218 }
219
220 // Add the region at the RHS of the incremental cset
221 void G1CollectionSet::add_survivor_regions(HeapRegion* hr) {
222 // We should only ever be appending survivors at the end of a pause
223 assert(hr->is_survivor(), "Logic");
224
225 // Do the 'common' stuff
226 add_young_region_common(hr);
227
228 // Now add the region at the right hand side
229 if (_inc_tail == NULL) {
230 assert(_inc_head == NULL, "invariant");
231 _inc_head = hr;
232 } else {
233 _inc_tail->set_next_in_collection_set(hr);
234 }
235 _inc_tail = hr;
236 }
237
238 // Add the region to the LHS of the incremental cset
239 void G1CollectionSet::add_eden_region(HeapRegion* hr) {
240 // Survivors should be added to the RHS at the end of a pause
241 assert(hr->is_eden(), "Logic");
242
243 // Do the 'common' stuff
244 add_young_region_common(hr);
245
246 // Add the region at the left hand side
247 hr->set_next_in_collection_set(_inc_head);
248 if (_inc_head == NULL) {
249 assert(_inc_tail == NULL, "Invariant");
250 _inc_tail = hr;
251 }
252 _inc_head = hr;
253 }
254
255 #ifndef PRODUCT
256 void G1CollectionSet::print(HeapRegion* list_head, outputStream* st) {
257 assert(list_head == inc_head() || list_head == head(), "must be");
258
259 st->print_cr("\nCollection_set:");
260 HeapRegion* csr = list_head;
261 while (csr != NULL) {
262 HeapRegion* next = csr->next_in_collection_set();
263 assert(csr->in_collection_set(), "bad CS");
264 st->print_cr(" " HR_FORMAT ", P: " PTR_FORMAT "N: " PTR_FORMAT ", age: %4d",
265 HR_FORMAT_PARAMS(csr),
266 p2i(csr->prev_top_at_mark_start()), p2i(csr->next_top_at_mark_start()),
267 csr->age_in_surv_rate_group_cond());
268 csr = next;
269 }
270 }
271 #endif // !PRODUCT
272
273 double G1CollectionSet::finalize_young_part(double target_pause_time_ms) {
274 double young_start_time_sec = os::elapsedTime();
275
276 YoungList* young_list = _g1->young_list();
277 finalize_incremental_building();
278
279 guarantee(target_pause_time_ms > 0.0,
280 "target_pause_time_ms = %1.6lf should be positive", target_pause_time_ms);
281 guarantee(_head == NULL, "Precondition");
282
283 size_t pending_cards = _g1p->pending_cards();
284 double base_time_ms = _g1p->predict_base_elapsed_time_ms(pending_cards);
285 double time_remaining_ms = MAX2(target_pause_time_ms - base_time_ms, 0.0);
286
287 log_trace(gc, ergo, cset)("Start choosing CSet. pending cards: " SIZE_FORMAT " predicted base time: %1.2fms remaining time: %1.2fms target pause time: %1.2fms",
288 pending_cards, base_time_ms, time_remaining_ms, target_pause_time_ms);
289
290 collector_state()->set_last_gc_was_young(collector_state()->gcs_are_young());
291
292 // The young list is laid with the survivor regions from the previous
293 // pause are appended to the RHS of the young list, i.e.
294 // [Newly Young Regions ++ Survivors from last pause].
295
296 uint survivor_region_length = young_list->survivor_length();
297 uint eden_region_length = young_list->eden_length();
298 init_region_lengths(eden_region_length, survivor_region_length);
299
300 HeapRegion* hr = young_list->first_survivor_region();
301 while (hr != NULL) {
302 assert(hr->is_survivor(), "badly formed young list");
303 // There is a convention that all the young regions in the CSet
304 // are tagged as "eden", so we do this for the survivors here. We
305 // use the special set_eden_pre_gc() as it doesn't check that the
306 // region is free (which is not the case here).
307 hr->set_eden_pre_gc();
308 hr = hr->get_next_young_region();
309 }
310
311 // Clear the fields that point to the survivor list - they are all young now.
312 young_list->clear_survivors();
313
314 _head = _inc_head;
315 _bytes_used_before = _inc_bytes_used_before;
316 time_remaining_ms = MAX2(time_remaining_ms - _inc_predicted_elapsed_time_ms, 0.0);
317
318 log_trace(gc, ergo, cset)("Add young regions to CSet. eden: %u regions, survivors: %u regions, predicted young region time: %1.2fms, target pause time: %1.2fms",
319 eden_region_length, survivor_region_length, _inc_predicted_elapsed_time_ms, target_pause_time_ms);
320
321 // The number of recorded young regions is the incremental
322 // collection set's current size
323 set_recorded_rs_lengths(_inc_recorded_rs_lengths);
324
325 double young_end_time_sec = os::elapsedTime();
326 phase_times()->record_young_cset_choice_time_ms((young_end_time_sec - young_start_time_sec) * 1000.0);
327
328 return time_remaining_ms;
329 }
330
331 void G1CollectionSet::finalize_old_part(double time_remaining_ms) {
332 double non_young_start_time_sec = os::elapsedTime();
333 double predicted_old_time_ms = 0.0;
334
335
336 if (!collector_state()->gcs_are_young()) {
337 cset_chooser()->verify();
338 const uint min_old_cset_length = _g1p->calc_min_old_cset_length();
339 const uint max_old_cset_length = _g1p->calc_max_old_cset_length();
340
341 uint expensive_region_num = 0;
342 bool check_time_remaining = _g1p->adaptive_young_list_length();
343
344 HeapRegion* hr = cset_chooser()->peek();
345 while (hr != NULL) {
346 if (old_region_length() >= max_old_cset_length) {
347 // Added maximum number of old regions to the CSet.
348 log_debug(gc, ergo, cset)("Finish adding old regions to CSet (old CSet region num reached max). old %u regions, max %u regions",
349 old_region_length(), max_old_cset_length);
350 break;
351 }
352
353
354 // Stop adding regions if the remaining reclaimable space is
355 // not above G1HeapWastePercent.
356 size_t reclaimable_bytes = cset_chooser()->remaining_reclaimable_bytes();
357 double reclaimable_perc = _g1p->reclaimable_bytes_perc(reclaimable_bytes);
358 double threshold = (double) G1HeapWastePercent;
359 if (reclaimable_perc <= threshold) {
360 // We've added enough old regions that the amount of uncollected
361 // reclaimable space is at or below the waste threshold. Stop
362 // adding old regions to the CSet.
363 log_debug(gc, ergo, cset)("Finish adding old regions to CSet (reclaimable percentage not over threshold). "
364 "old %u regions, max %u regions, reclaimable: " SIZE_FORMAT "B (%1.2f%%) threshold: " UINTX_FORMAT "%%",
365 old_region_length(), max_old_cset_length, reclaimable_bytes, reclaimable_perc, G1HeapWastePercent);
366 break;
367 }
368
369 double predicted_time_ms = predict_region_elapsed_time_ms(hr);
370 if (check_time_remaining) {
371 if (predicted_time_ms > time_remaining_ms) {
372 // Too expensive for the current CSet.
373
374 if (old_region_length() >= min_old_cset_length) {
375 // We have added the minimum number of old regions to the CSet,
376 // we are done with this CSet.
377 log_debug(gc, ergo, cset)("Finish adding old regions to CSet (predicted time is too high). "
378 "predicted time: %1.2fms, remaining time: %1.2fms old %u regions, min %u regions",
379 predicted_time_ms, time_remaining_ms, old_region_length(), min_old_cset_length);
380 break;
381 }
382
383 // We'll add it anyway given that we haven't reached the
384 // minimum number of old regions.
385 expensive_region_num += 1;
386 }
387 } else {
388 if (old_region_length() >= min_old_cset_length) {
389 // In the non-auto-tuning case, we'll finish adding regions
390 // to the CSet if we reach the minimum.
391
392 log_debug(gc, ergo, cset)("Finish adding old regions to CSet (old CSet region num reached min). old %u regions, min %u regions",
393 old_region_length(), min_old_cset_length);
394 break;
395 }
396 }
397
398 // We will add this region to the CSet.
399 time_remaining_ms = MAX2(time_remaining_ms - predicted_time_ms, 0.0);
400 predicted_old_time_ms += predicted_time_ms;
401 cset_chooser()->pop(); // already have region via peek()
402 _g1->old_set_remove(hr);
403 add_old_region(hr);
404
405 hr = cset_chooser()->peek();
406 }
407 if (hr == NULL) {
408 log_debug(gc, ergo, cset)("Finish adding old regions to CSet (candidate old regions not available)");
409 }
410
411 if (expensive_region_num > 0) {
412 // We print the information once here at the end, predicated on
413 // whether we added any apparently expensive regions or not, to
414 // avoid generating output per region.
415 log_debug(gc, ergo, cset)("Added expensive regions to CSet (old CSet region num not reached min)."
416 "old: %u regions, expensive: %u regions, min: %u regions, remaining time: %1.2fms",
417 old_region_length(), expensive_region_num, min_old_cset_length, time_remaining_ms);
418 }
419
420 cset_chooser()->verify();
421 }
422
423 stop_incremental_building();
424
425 log_debug(gc, ergo, cset)("Finish choosing CSet. old: %u regions, predicted old region time: %1.2fms, time remaining: %1.2f",
426 old_region_length(), predicted_old_time_ms, time_remaining_ms);
427
428 double non_young_end_time_sec = os::elapsedTime();
429 phase_times()->record_non_young_cset_choice_time_ms((non_young_end_time_sec - non_young_start_time_sec) * 1000.0);
430 }