1 /*
2 * Copyright (c) 2001, 2009, 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 "incls/_precompiled.incl"
26 # include "incls/_collectionSetChooser.cpp.incl"
27
28 CSetChooserCache::CSetChooserCache() {
29 for (int i = 0; i < CacheLength; ++i)
30 _cache[i] = NULL;
31 clear();
32 }
33
34 void CSetChooserCache::clear() {
35 _occupancy = 0;
36 _first = 0;
37 for (int i = 0; i < CacheLength; ++i) {
38 HeapRegion *hr = _cache[i];
39 if (hr != NULL)
40 hr->set_sort_index(-1);
41 _cache[i] = NULL;
42 }
43 }
44
45 #ifndef PRODUCT
46 bool CSetChooserCache::verify() {
47 int index = _first;
48 HeapRegion *prev = NULL;
49 for (int i = 0; i < _occupancy; ++i) {
50 guarantee(_cache[index] != NULL, "cache entry should not be empty");
51 HeapRegion *hr = _cache[index];
52 guarantee(!hr->is_young(), "should not be young!");
53 if (prev != NULL) {
54 guarantee(prev->gc_efficiency() >= hr->gc_efficiency(),
55 "cache should be correctly ordered");
56 }
57 guarantee(hr->sort_index() == get_sort_index(index),
58 "sort index should be correct");
59 index = trim_index(index + 1);
60 prev = hr;
61 }
62
63 for (int i = 0; i < (CacheLength - _occupancy); ++i) {
64 guarantee(_cache[index] == NULL, "cache entry should be empty");
65 index = trim_index(index + 1);
66 }
67
68 guarantee(index == _first, "we should have reached where we started from");
69 return true;
70 }
71 #endif // PRODUCT
72
73 void CSetChooserCache::insert(HeapRegion *hr) {
74 assert(!is_full(), "cache should not be empty");
75 hr->calc_gc_efficiency();
76
77 int empty_index;
78 if (_occupancy == 0) {
79 empty_index = _first;
80 } else {
81 empty_index = trim_index(_first + _occupancy);
82 assert(_cache[empty_index] == NULL, "last slot should be empty");
83 int last_index = trim_index(empty_index - 1);
84 HeapRegion *last = _cache[last_index];
85 assert(last != NULL,"as the cache is not empty, last should not be empty");
86 while (empty_index != _first &&
87 last->gc_efficiency() < hr->gc_efficiency()) {
88 _cache[empty_index] = last;
89 last->set_sort_index(get_sort_index(empty_index));
90 empty_index = last_index;
91 last_index = trim_index(last_index - 1);
92 last = _cache[last_index];
93 }
94 }
95 _cache[empty_index] = hr;
96 hr->set_sort_index(get_sort_index(empty_index));
97
98 ++_occupancy;
99 assert(verify(), "cache should be consistent");
100 }
101
102 HeapRegion *CSetChooserCache::remove_first() {
103 if (_occupancy > 0) {
104 assert(_cache[_first] != NULL, "cache should have at least one region");
105 HeapRegion *ret = _cache[_first];
106 _cache[_first] = NULL;
107 ret->set_sort_index(-1);
108 --_occupancy;
109 _first = trim_index(_first + 1);
110 assert(verify(), "cache should be consistent");
111 return ret;
112 } else {
113 return NULL;
114 }
115 }
116
117 // this is a bit expensive... but we expect that it should not be called
118 // to often.
119 void CSetChooserCache::remove(HeapRegion *hr) {
120 assert(_occupancy > 0, "cache should not be empty");
121 assert(hr->sort_index() < -1, "should already be in the cache");
122 int index = get_index(hr->sort_index());
123 assert(_cache[index] == hr, "index should be correct");
124 int next_index = trim_index(index + 1);
125 int last_index = trim_index(_first + _occupancy - 1);
126 while (index != last_index) {
127 assert(_cache[next_index] != NULL, "should not be null");
128 _cache[index] = _cache[next_index];
129 _cache[index]->set_sort_index(get_sort_index(index));
130
131 index = next_index;
132 next_index = trim_index(next_index+1);
133 }
134 assert(index == last_index, "should have reached the last one");
135 _cache[index] = NULL;
136 hr->set_sort_index(-1);
137 --_occupancy;
138 assert(verify(), "cache should be consistent");
139 }
140
141 static inline int orderRegions(HeapRegion* hr1, HeapRegion* hr2) {
142 if (hr1 == NULL) {
143 if (hr2 == NULL) return 0;
144 else return 1;
145 } else if (hr2 == NULL) {
146 return -1;
147 }
148 if (hr2->gc_efficiency() < hr1->gc_efficiency()) return -1;
149 else if (hr1->gc_efficiency() < hr2->gc_efficiency()) return 1;
150 else return 0;
151 }
152
153 static int orderRegions(HeapRegion** hr1p, HeapRegion** hr2p) {
154 return orderRegions(*hr1p, *hr2p);
155 }
156
157 CollectionSetChooser::CollectionSetChooser() :
158 // The line below is the worst bit of C++ hackery I've ever written
159 // (Detlefs, 11/23). You should think of it as equivalent to
160 // "_regions(100, true)": initialize the growable array and inform it
161 // that it should allocate its elem array(s) on the C heap.
162 //
163 // The first argument, however, is actually a comma expression
164 // (set_allocation_type(this, C_HEAP), 100). The purpose of the
165 // set_allocation_type() call is to replace the default allocation
166 // type for embedded objects STACK_OR_EMBEDDED with C_HEAP. It will
167 // allow to pass the assert in GenericGrowableArray() which checks
168 // that a growable array object must be on C heap if elements are.
169 //
170 // Note: containing object is allocated on C heap since it is CHeapObj.
171 //
172 _markedRegions((ResourceObj::set_allocation_type((address)&_markedRegions,
173 ResourceObj::C_HEAP),
174 100),
175 true),
176 _curMarkedIndex(0),
177 _numMarkedRegions(0),
178 _unmarked_age_1_returned_as_new(false),
179 _first_par_unreserved_idx(0)
180 {}
181
182
183
184 #ifndef PRODUCT
185 bool CollectionSetChooser::verify() {
186 int index = 0;
187 guarantee(_curMarkedIndex <= _numMarkedRegions,
188 "_curMarkedIndex should be within bounds");
189 while (index < _curMarkedIndex) {
190 guarantee(_markedRegions.at(index++) == NULL,
191 "all entries before _curMarkedIndex should be NULL");
192 }
193 HeapRegion *prev = NULL;
194 while (index < _numMarkedRegions) {
195 HeapRegion *curr = _markedRegions.at(index++);
196 if (curr != NULL) {
197 int si = curr->sort_index();
198 guarantee(!curr->is_young(), "should not be young!");
199 guarantee(si > -1 && si == (index-1), "sort index invariant");
200 if (prev != NULL) {
201 guarantee(orderRegions(prev, curr) != 1, "regions should be sorted");
202 }
203 prev = curr;
204 }
205 }
206 return _cache.verify();
207 }
208 #endif
209
210 bool
211 CollectionSetChooser::addRegionToCache() {
212 assert(!_cache.is_full(), "cache should not be full");
213
214 HeapRegion *hr = NULL;
215 while (hr == NULL && _curMarkedIndex < _numMarkedRegions) {
216 hr = _markedRegions.at(_curMarkedIndex++);
217 }
218 if (hr == NULL)
219 return false;
220 assert(!hr->is_young(), "should not be young!");
221 assert(hr->sort_index() == _curMarkedIndex-1, "sort_index invariant");
222 _markedRegions.at_put(hr->sort_index(), NULL);
223 _cache.insert(hr);
224 assert(!_cache.is_empty(), "cache should not be empty");
225 assert(verify(), "cache should be consistent");
226 return false;
227 }
228
229 void
230 CollectionSetChooser::fillCache() {
231 while (!_cache.is_full() && addRegionToCache()) {
232 }
233 }
234
235 void
236 CollectionSetChooser::sortMarkedHeapRegions() {
237 guarantee(_cache.is_empty(), "cache should be empty");
238 // First trim any unused portion of the top in the parallel case.
239 if (_first_par_unreserved_idx > 0) {
240 if (G1PrintParCleanupStats) {
241 gclog_or_tty->print(" Truncating _markedRegions from %d to %d.\n",
242 _markedRegions.length(), _first_par_unreserved_idx);
243 }
244 assert(_first_par_unreserved_idx <= _markedRegions.length(),
245 "Or we didn't reserved enough length");
246 _markedRegions.trunc_to(_first_par_unreserved_idx);
247 }
248 _markedRegions.sort(orderRegions);
249 assert(_numMarkedRegions <= _markedRegions.length(), "Requirement");
250 assert(_numMarkedRegions == 0
251 || _markedRegions.at(_numMarkedRegions-1) != NULL,
252 "Testing _numMarkedRegions");
253 assert(_numMarkedRegions == _markedRegions.length()
254 || _markedRegions.at(_numMarkedRegions) == NULL,
255 "Testing _numMarkedRegions");
256 if (G1PrintParCleanupStats) {
257 gclog_or_tty->print_cr(" Sorted %d marked regions.", _numMarkedRegions);
258 }
259 for (int i = 0; i < _numMarkedRegions; i++) {
260 assert(_markedRegions.at(i) != NULL, "Should be true by sorting!");
261 _markedRegions.at(i)->set_sort_index(i);
262 if (G1PrintRegionLivenessInfo > 0) {
263 if (i == 0) gclog_or_tty->print_cr("Sorted marked regions:");
264 if (i < G1PrintRegionLivenessInfo ||
265 (_numMarkedRegions-i) < G1PrintRegionLivenessInfo) {
266 HeapRegion* hr = _markedRegions.at(i);
267 size_t u = hr->used();
268 gclog_or_tty->print_cr(" Region %d: %d used, %d max live, %5.2f%%.",
269 i, u, hr->max_live_bytes(),
270 100.0*(float)hr->max_live_bytes()/(float)u);
271 }
272 }
273 }
274 if (G1PolicyVerbose > 1)
275 printSortedHeapRegions();
276 assert(verify(), "should now be sorted");
277 }
278
279 void
280 printHeapRegion(HeapRegion *hr) {
281 if (hr->isHumongous())
282 gclog_or_tty->print("H: ");
283 if (hr->in_collection_set())
284 gclog_or_tty->print("CS: ");
285 gclog_or_tty->print_cr("Region " PTR_FORMAT " (%s%s) "
286 "[" PTR_FORMAT ", " PTR_FORMAT"] "
287 "Used: " SIZE_FORMAT "K, garbage: " SIZE_FORMAT "K.",
288 hr, hr->is_young() ? "Y " : " ",
289 hr->is_marked()? "M1" : "M0",
290 hr->bottom(), hr->end(),
291 hr->used()/K, hr->garbage_bytes()/K);
292 }
293
294 void
295 CollectionSetChooser::addMarkedHeapRegion(HeapRegion* hr) {
296 assert(!hr->isHumongous(),
297 "Humongous regions shouldn't be added to the collection set");
298 assert(!hr->is_young(), "should not be young!");
299 _markedRegions.append(hr);
300 _numMarkedRegions++;
301 hr->calc_gc_efficiency();
302 }
303
304 void
305 CollectionSetChooser::
306 prepareForAddMarkedHeapRegionsPar(size_t n_regions, size_t chunkSize) {
307 _first_par_unreserved_idx = 0;
308 size_t max_waste = ParallelGCThreads * chunkSize;
309 // it should be aligned with respect to chunkSize
310 size_t aligned_n_regions =
311 (n_regions + (chunkSize - 1)) / chunkSize * chunkSize;
312 assert( aligned_n_regions % chunkSize == 0, "should be aligned" );
313 _markedRegions.at_put_grow((int)(aligned_n_regions + max_waste - 1), NULL);
314 }
315
316 jint
317 CollectionSetChooser::getParMarkedHeapRegionChunk(jint n_regions) {
318 jint res = Atomic::add(n_regions, &_first_par_unreserved_idx);
319 assert(_markedRegions.length() > res + n_regions - 1,
320 "Should already have been expanded");
321 return res - n_regions;
322 }
323
324 void
325 CollectionSetChooser::setMarkedHeapRegion(jint index, HeapRegion* hr) {
326 assert(_markedRegions.at(index) == NULL, "precondition");
327 assert(!hr->is_young(), "should not be young!");
328 _markedRegions.at_put(index, hr);
329 hr->calc_gc_efficiency();
330 }
331
332 void
333 CollectionSetChooser::incNumMarkedHeapRegions(jint inc_by) {
334 (void)Atomic::add(inc_by, &_numMarkedRegions);
335 }
336
337 void
338 CollectionSetChooser::clearMarkedHeapRegions(){
339 for (int i = 0; i < _markedRegions.length(); i++) {
340 HeapRegion* r = _markedRegions.at(i);
341 if (r != NULL) r->set_sort_index(-1);
342 }
343 _markedRegions.clear();
344 _curMarkedIndex = 0;
345 _numMarkedRegions = 0;
346 _cache.clear();
347 };
348
349 void
350 CollectionSetChooser::updateAfterFullCollection() {
351 G1CollectedHeap* g1h = G1CollectedHeap::heap();
352 clearMarkedHeapRegions();
353 }
354
355 void
356 CollectionSetChooser::printSortedHeapRegions() {
357 gclog_or_tty->print_cr("Printing %d Heap Regions sorted by amount of known garbage",
358 _numMarkedRegions);
359
360 DEBUG_ONLY(int marked_count = 0;)
361 for (int i = 0; i < _markedRegions.length(); i++) {
362 HeapRegion* r = _markedRegions.at(i);
363 if (r != NULL) {
364 printHeapRegion(r);
365 DEBUG_ONLY(marked_count++;)
366 }
367 }
368 assert(marked_count == _numMarkedRegions, "must be");
369 gclog_or_tty->print_cr("Done sorted heap region print");
370 }
371
372 void CollectionSetChooser::removeRegion(HeapRegion *hr) {
373 int si = hr->sort_index();
374 assert(si == -1 || hr->is_marked(), "Sort index not valid.");
375 if (si > -1) {
376 assert(_markedRegions.at(si) == hr, "Sort index not valid." );
377 _markedRegions.at_put(si, NULL);
378 } else if (si < -1) {
379 assert(_cache.region_in_cache(hr), "should be in the cache");
380 _cache.remove(hr);
381 assert(hr->sort_index() == -1, "sort index invariant");
382 }
383 hr->set_sort_index(-1);
384 }
385
386 // if time_remaining < 0.0, then this method should try to return
387 // a region, whether it fits within the remaining time or not
388 HeapRegion*
389 CollectionSetChooser::getNextMarkedRegion(double time_remaining,
390 double avg_prediction) {
391 G1CollectedHeap* g1h = G1CollectedHeap::heap();
392 G1CollectorPolicy* g1p = g1h->g1_policy();
393 fillCache();
394 if (_cache.is_empty()) {
395 assert(_curMarkedIndex == _numMarkedRegions,
396 "if cache is empty, list should also be empty");
397 return NULL;
398 }
399
400 HeapRegion *hr = _cache.get_first();
401 assert(hr != NULL, "if cache not empty, first entry should be non-null");
402 double predicted_time = g1h->predict_region_elapsed_time_ms(hr, false);
403
404 if (g1p->adaptive_young_list_length()) {
405 if (time_remaining - predicted_time < 0.0) {
406 g1h->check_if_region_is_too_expensive(predicted_time);
407 return NULL;
408 }
409 } else {
410 if (predicted_time > 2.0 * avg_prediction) {
411 return NULL;
412 }
413 }
414
415 HeapRegion *hr2 = _cache.remove_first();
416 assert(hr == hr2, "cache contents should not have changed");
417
418 return hr;
419 }