Wed, 15 Feb 2012 13:06:53 -0500
7132029: G1: mixed GC phase lasts for longer than it should
Summary: Revamp of the mechanism that chooses old regions for inclusion in the CSet. It simplifies the code and introduces min and max bounds on the number of old regions added to the CSet at each mixed GC to avoid pathological cases. It also ensures that when we do a mixed GC we'll always find old regions to add to the CSet (i.e., it eliminates the case where a mixed GC will collect no old regions which can happen today).
Reviewed-by: johnc, brutisso
1 /*
2 * Copyright (c) 2001, 2012, 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 */
25 #include "precompiled.hpp"
26 #include "gc_implementation/g1/collectionSetChooser.hpp"
27 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
28 #include "gc_implementation/g1/g1CollectorPolicy.hpp"
29 #include "gc_implementation/g1/g1ErgoVerbose.hpp"
30 #include "memory/space.inline.hpp"
32 CSetChooserCache::CSetChooserCache() {
33 for (int i = 0; i < CacheLength; ++i)
34 _cache[i] = NULL;
35 clear();
36 }
38 void CSetChooserCache::clear() {
39 _occupancy = 0;
40 _first = 0;
41 for (int i = 0; i < CacheLength; ++i) {
42 HeapRegion *hr = _cache[i];
43 if (hr != NULL)
44 hr->set_sort_index(-1);
45 _cache[i] = NULL;
46 }
47 }
49 #ifndef PRODUCT
50 bool CSetChooserCache::verify() {
51 guarantee(false, "CSetChooserCache::verify(): don't call this any more");
53 int index = _first;
54 HeapRegion *prev = NULL;
55 for (int i = 0; i < _occupancy; ++i) {
56 guarantee(_cache[index] != NULL, "cache entry should not be empty");
57 HeapRegion *hr = _cache[index];
58 guarantee(!hr->is_young(), "should not be young!");
59 if (prev != NULL) {
60 guarantee(prev->gc_efficiency() >= hr->gc_efficiency(),
61 "cache should be correctly ordered");
62 }
63 guarantee(hr->sort_index() == get_sort_index(index),
64 "sort index should be correct");
65 index = trim_index(index + 1);
66 prev = hr;
67 }
69 for (int i = 0; i < (CacheLength - _occupancy); ++i) {
70 guarantee(_cache[index] == NULL, "cache entry should be empty");
71 index = trim_index(index + 1);
72 }
74 guarantee(index == _first, "we should have reached where we started from");
75 return true;
76 }
77 #endif // PRODUCT
79 void CSetChooserCache::insert(HeapRegion *hr) {
80 guarantee(false, "CSetChooserCache::insert(): don't call this any more");
82 assert(!is_full(), "cache should not be empty");
83 hr->calc_gc_efficiency();
85 int empty_index;
86 if (_occupancy == 0) {
87 empty_index = _first;
88 } else {
89 empty_index = trim_index(_first + _occupancy);
90 assert(_cache[empty_index] == NULL, "last slot should be empty");
91 int last_index = trim_index(empty_index - 1);
92 HeapRegion *last = _cache[last_index];
93 assert(last != NULL,"as the cache is not empty, last should not be empty");
94 while (empty_index != _first &&
95 last->gc_efficiency() < hr->gc_efficiency()) {
96 _cache[empty_index] = last;
97 last->set_sort_index(get_sort_index(empty_index));
98 empty_index = last_index;
99 last_index = trim_index(last_index - 1);
100 last = _cache[last_index];
101 }
102 }
103 _cache[empty_index] = hr;
104 hr->set_sort_index(get_sort_index(empty_index));
106 ++_occupancy;
107 assert(verify(), "cache should be consistent");
108 }
110 HeapRegion *CSetChooserCache::remove_first() {
111 guarantee(false, "CSetChooserCache::remove_first(): "
112 "don't call this any more");
114 if (_occupancy > 0) {
115 assert(_cache[_first] != NULL, "cache should have at least one region");
116 HeapRegion *ret = _cache[_first];
117 _cache[_first] = NULL;
118 ret->set_sort_index(-1);
119 --_occupancy;
120 _first = trim_index(_first + 1);
121 assert(verify(), "cache should be consistent");
122 return ret;
123 } else {
124 return NULL;
125 }
126 }
128 // Even though we don't use the GC efficiency in our heuristics as
129 // much as we used to, we still order according to GC efficiency. This
130 // will cause regions with a lot of live objects and large RSets to
131 // end up at the end of the array. Given that we might skip collecting
132 // the last few old regions, if after a few mixed GCs the remaining
133 // have reclaimable bytes under a certain threshold, the hope is that
134 // the ones we'll skip are ones with both large RSets and a lot of
135 // live objects, not the ones with just a lot of live objects if we
136 // ordered according to the amount of reclaimable bytes per region.
137 static int orderRegions(HeapRegion* hr1, HeapRegion* hr2) {
138 if (hr1 == NULL) {
139 if (hr2 == NULL) {
140 return 0;
141 } else {
142 return 1;
143 }
144 } else if (hr2 == NULL) {
145 return -1;
146 }
148 double gc_eff1 = hr1->gc_efficiency();
149 double gc_eff2 = hr2->gc_efficiency();
150 if (gc_eff1 > gc_eff2) {
151 return -1;
152 } if (gc_eff1 < gc_eff2) {
153 return 1;
154 } else {
155 return 0;
156 }
157 }
159 static int orderRegions(HeapRegion** hr1p, HeapRegion** hr2p) {
160 return orderRegions(*hr1p, *hr2p);
161 }
163 CollectionSetChooser::CollectionSetChooser() :
164 // The line below is the worst bit of C++ hackery I've ever written
165 // (Detlefs, 11/23). You should think of it as equivalent to
166 // "_regions(100, true)": initialize the growable array and inform it
167 // that it should allocate its elem array(s) on the C heap.
168 //
169 // The first argument, however, is actually a comma expression
170 // (set_allocation_type(this, C_HEAP), 100). The purpose of the
171 // set_allocation_type() call is to replace the default allocation
172 // type for embedded objects STACK_OR_EMBEDDED with C_HEAP. It will
173 // allow to pass the assert in GenericGrowableArray() which checks
174 // that a growable array object must be on C heap if elements are.
175 //
176 // Note: containing object is allocated on C heap since it is CHeapObj.
177 //
178 _markedRegions((ResourceObj::set_allocation_type((address)&_markedRegions,
179 ResourceObj::C_HEAP),
180 100), true /* C_Heap */),
181 _curr_index(0), _length(0),
182 _regionLiveThresholdBytes(0), _remainingReclaimableBytes(0),
183 _first_par_unreserved_idx(0) {
184 _regionLiveThresholdBytes =
185 HeapRegion::GrainBytes * (size_t) G1OldCSetRegionLiveThresholdPercent / 100;
186 }
188 #ifndef PRODUCT
189 bool CollectionSetChooser::verify() {
190 guarantee(_length >= 0, err_msg("_length: %d", _length));
191 guarantee(0 <= _curr_index && _curr_index <= _length,
192 err_msg("_curr_index: %d _length: %d", _curr_index, _length));
193 int index = 0;
194 size_t sum_of_reclaimable_bytes = 0;
195 while (index < _curr_index) {
196 guarantee(_markedRegions.at(index) == NULL,
197 "all entries before _curr_index should be NULL");
198 index += 1;
199 }
200 HeapRegion *prev = NULL;
201 while (index < _length) {
202 HeapRegion *curr = _markedRegions.at(index++);
203 guarantee(curr != NULL, "Regions in _markedRegions array cannot be NULL");
204 int si = curr->sort_index();
205 guarantee(!curr->is_young(), "should not be young!");
206 guarantee(!curr->isHumongous(), "should not be humongous!");
207 guarantee(si > -1 && si == (index-1), "sort index invariant");
208 if (prev != NULL) {
209 guarantee(orderRegions(prev, curr) != 1,
210 err_msg("GC eff prev: %1.4f GC eff curr: %1.4f",
211 prev->gc_efficiency(), curr->gc_efficiency()));
212 }
213 sum_of_reclaimable_bytes += curr->reclaimable_bytes();
214 prev = curr;
215 }
216 guarantee(sum_of_reclaimable_bytes == _remainingReclaimableBytes,
217 err_msg("reclaimable bytes inconsistent, "
218 "remaining: "SIZE_FORMAT" sum: "SIZE_FORMAT,
219 _remainingReclaimableBytes, sum_of_reclaimable_bytes));
220 return true;
221 }
222 #endif
224 void CollectionSetChooser::fillCache() {
225 guarantee(false, "fillCache: don't call this any more");
227 while (!_cache.is_full() && (_curr_index < _length)) {
228 HeapRegion* hr = _markedRegions.at(_curr_index);
229 assert(hr != NULL,
230 err_msg("Unexpected NULL hr in _markedRegions at index %d",
231 _curr_index));
232 _curr_index += 1;
233 assert(!hr->is_young(), "should not be young!");
234 assert(hr->sort_index() == _curr_index-1, "sort_index invariant");
235 _markedRegions.at_put(hr->sort_index(), NULL);
236 _cache.insert(hr);
237 assert(!_cache.is_empty(), "cache should not be empty");
238 }
239 assert(verify(), "cache should be consistent");
240 }
242 void CollectionSetChooser::sortMarkedHeapRegions() {
243 // First trim any unused portion of the top in the parallel case.
244 if (_first_par_unreserved_idx > 0) {
245 if (G1PrintParCleanupStats) {
246 gclog_or_tty->print(" Truncating _markedRegions from %d to %d.\n",
247 _markedRegions.length(), _first_par_unreserved_idx);
248 }
249 assert(_first_par_unreserved_idx <= _markedRegions.length(),
250 "Or we didn't reserved enough length");
251 _markedRegions.trunc_to(_first_par_unreserved_idx);
252 }
253 _markedRegions.sort(orderRegions);
254 assert(_length <= _markedRegions.length(), "Requirement");
255 assert(_length == 0 || _markedRegions.at(_length - 1) != NULL,
256 "Testing _length");
257 assert(_length == _markedRegions.length() ||
258 _markedRegions.at(_length) == NULL, "Testing _length");
259 if (G1PrintParCleanupStats) {
260 gclog_or_tty->print_cr(" Sorted %d marked regions.", _length);
261 }
262 for (int i = 0; i < _length; i++) {
263 assert(_markedRegions.at(i) != NULL, "Should be true by sorting!");
264 _markedRegions.at(i)->set_sort_index(i);
265 }
266 if (G1PrintRegionLivenessInfo) {
267 G1PrintRegionLivenessInfoClosure cl(gclog_or_tty, "Post-Sorting");
268 for (int i = 0; i < _length; ++i) {
269 HeapRegion* r = _markedRegions.at(i);
270 cl.doHeapRegion(r);
271 }
272 }
273 assert(verify(), "CSet chooser verification");
274 }
276 size_t CollectionSetChooser::calcMinOldCSetLength() {
277 // The min old CSet region bound is based on the maximum desired
278 // number of mixed GCs after a cycle. I.e., even if some old regions
279 // look expensive, we should add them to the CSet anyway to make
280 // sure we go through the available old regions in no more than the
281 // maximum desired number of mixed GCs.
282 //
283 // The calculation is based on the number of marked regions we added
284 // to the CSet chooser in the first place, not how many remain, so
285 // that the result is the same during all mixed GCs that follow a cycle.
287 const size_t region_num = (size_t) _length;
288 const size_t gc_num = (size_t) G1MaxMixedGCNum;
289 size_t result = region_num / gc_num;
290 // emulate ceiling
291 if (result * gc_num < region_num) {
292 result += 1;
293 }
294 return result;
295 }
297 size_t CollectionSetChooser::calcMaxOldCSetLength() {
298 // The max old CSet region bound is based on the threshold expressed
299 // as a percentage of the heap size. I.e., it should bound the
300 // number of old regions added to the CSet irrespective of how many
301 // of them are available.
303 G1CollectedHeap* g1h = G1CollectedHeap::heap();
304 const size_t region_num = g1h->n_regions();
305 const size_t perc = (size_t) G1OldCSetRegionThresholdPercent;
306 size_t result = region_num * perc / 100;
307 // emulate ceiling
308 if (100 * result < region_num * perc) {
309 result += 1;
310 }
311 return result;
312 }
314 void CollectionSetChooser::addMarkedHeapRegion(HeapRegion* hr) {
315 assert(!hr->isHumongous(),
316 "Humongous regions shouldn't be added to the collection set");
317 assert(!hr->is_young(), "should not be young!");
318 _markedRegions.append(hr);
319 _length++;
320 _remainingReclaimableBytes += hr->reclaimable_bytes();
321 hr->calc_gc_efficiency();
322 }
324 void CollectionSetChooser::prepareForAddMarkedHeapRegionsPar(size_t n_regions,
325 size_t chunkSize) {
326 _first_par_unreserved_idx = 0;
327 int n_threads = ParallelGCThreads;
328 if (UseDynamicNumberOfGCThreads) {
329 assert(G1CollectedHeap::heap()->workers()->active_workers() > 0,
330 "Should have been set earlier");
331 // This is defensive code. As the assertion above says, the number
332 // of active threads should be > 0, but in case there is some path
333 // or some improperly initialized variable with leads to no
334 // active threads, protect against that in a product build.
335 n_threads = MAX2(G1CollectedHeap::heap()->workers()->active_workers(),
336 1U);
337 }
338 size_t max_waste = n_threads * chunkSize;
339 // it should be aligned with respect to chunkSize
340 size_t aligned_n_regions =
341 (n_regions + (chunkSize - 1)) / chunkSize * chunkSize;
342 assert( aligned_n_regions % chunkSize == 0, "should be aligned" );
343 _markedRegions.at_put_grow((int)(aligned_n_regions + max_waste - 1), NULL);
344 }
346 jint CollectionSetChooser::getParMarkedHeapRegionChunk(jint n_regions) {
347 // Don't do this assert because this can be called at a point
348 // where the loop up stream will not execute again but might
349 // try to claim more chunks (loop test has not been done yet).
350 // assert(_markedRegions.length() > _first_par_unreserved_idx,
351 // "Striding beyond the marked regions");
352 jint res = Atomic::add(n_regions, &_first_par_unreserved_idx);
353 assert(_markedRegions.length() > res + n_regions - 1,
354 "Should already have been expanded");
355 return res - n_regions;
356 }
358 void CollectionSetChooser::setMarkedHeapRegion(jint index, HeapRegion* hr) {
359 assert(_markedRegions.at(index) == NULL, "precondition");
360 assert(!hr->is_young(), "should not be young!");
361 _markedRegions.at_put(index, hr);
362 hr->calc_gc_efficiency();
363 }
365 void CollectionSetChooser::updateTotals(jint region_num,
366 size_t reclaimable_bytes) {
367 // Only take the lock if we actually need to update the totals.
368 if (region_num > 0) {
369 assert(reclaimable_bytes > 0, "invariant");
370 // We could have just used atomics instead of taking the
371 // lock. However, we currently don't have an atomic add for size_t.
372 MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);
373 _length += (int) region_num;
374 _remainingReclaimableBytes += reclaimable_bytes;
375 } else {
376 assert(reclaimable_bytes == 0, "invariant");
377 }
378 }
380 void CollectionSetChooser::clearMarkedHeapRegions() {
381 for (int i = 0; i < _markedRegions.length(); i++) {
382 HeapRegion* r = _markedRegions.at(i);
383 if (r != NULL) {
384 r->set_sort_index(-1);
385 }
386 }
387 _markedRegions.clear();
388 _curr_index = 0;
389 _length = 0;
390 _remainingReclaimableBytes = 0;
391 };