Mercurial > hg > truffle
comparison src/share/vm/gc_implementation/g1/collectionSetChooser.cpp @ 342:37f87013dfd8
6711316: Open source the Garbage-First garbage collector
Summary: First mercurial integration of the code for the Garbage-First garbage collector.
Reviewed-by: apetrusenko, iveresov, jmasa, sgoldman, tonyp, ysr
author | ysr |
---|---|
date | Thu, 05 Jun 2008 15:57:56 -0700 |
parents | |
children | 96b229c54d1e |
comparison
equal
deleted
inserted
replaced
189:0b27f3512f9e | 342:37f87013dfd8 |
---|---|
1 /* | |
2 * Copyright 2001-2007 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any 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. The first | |
162 // argument, however, is actually a comma expression (new-expr, 100). | |
163 // The purpose of the new_expr is to inform the growable array that it | |
164 // is *already* allocated on the C heap: it uses the placement syntax to | |
165 // keep it from actually doing any allocation. | |
166 _markedRegions((ResourceObj::operator new (sizeof(GrowableArray<HeapRegion*>), | |
167 (void*)&_markedRegions, | |
168 ResourceObj::C_HEAP), | |
169 100), | |
170 true), | |
171 _curMarkedIndex(0), | |
172 _numMarkedRegions(0), | |
173 _unmarked_age_1_returned_as_new(false), | |
174 _first_par_unreserved_idx(0) | |
175 {} | |
176 | |
177 | |
178 | |
179 #ifndef PRODUCT | |
180 bool CollectionSetChooser::verify() { | |
181 int index = 0; | |
182 guarantee(_curMarkedIndex <= _numMarkedRegions, | |
183 "_curMarkedIndex should be within bounds"); | |
184 while (index < _curMarkedIndex) { | |
185 guarantee(_markedRegions.at(index++) == NULL, | |
186 "all entries before _curMarkedIndex should be NULL"); | |
187 } | |
188 HeapRegion *prev = NULL; | |
189 while (index < _numMarkedRegions) { | |
190 HeapRegion *curr = _markedRegions.at(index++); | |
191 if (curr != NULL) { | |
192 int si = curr->sort_index(); | |
193 guarantee(!curr->is_young(), "should not be young!"); | |
194 guarantee(si > -1 && si == (index-1), "sort index invariant"); | |
195 if (prev != NULL) { | |
196 guarantee(orderRegions(prev, curr) != 1, "regions should be sorted"); | |
197 } | |
198 prev = curr; | |
199 } | |
200 } | |
201 return _cache.verify(); | |
202 } | |
203 #endif | |
204 | |
205 bool | |
206 CollectionSetChooser::addRegionToCache() { | |
207 assert(!_cache.is_full(), "cache should not be full"); | |
208 | |
209 HeapRegion *hr = NULL; | |
210 while (hr == NULL && _curMarkedIndex < _numMarkedRegions) { | |
211 hr = _markedRegions.at(_curMarkedIndex++); | |
212 } | |
213 if (hr == NULL) | |
214 return false; | |
215 assert(!hr->is_young(), "should not be young!"); | |
216 assert(hr->sort_index() == _curMarkedIndex-1, "sort_index invariant"); | |
217 _markedRegions.at_put(hr->sort_index(), NULL); | |
218 _cache.insert(hr); | |
219 assert(!_cache.is_empty(), "cache should not be empty"); | |
220 assert(verify(), "cache should be consistent"); | |
221 return false; | |
222 } | |
223 | |
224 void | |
225 CollectionSetChooser::fillCache() { | |
226 while (!_cache.is_full() && addRegionToCache()) { | |
227 } | |
228 } | |
229 | |
230 void | |
231 CollectionSetChooser::sortMarkedHeapRegions() { | |
232 guarantee(_cache.is_empty(), "cache should be empty"); | |
233 // First trim any unused portion of the top in the parallel case. | |
234 if (_first_par_unreserved_idx > 0) { | |
235 if (G1PrintParCleanupStats) { | |
236 gclog_or_tty->print(" Truncating _markedRegions from %d to %d.\n", | |
237 _markedRegions.length(), _first_par_unreserved_idx); | |
238 } | |
239 assert(_first_par_unreserved_idx <= _markedRegions.length(), | |
240 "Or we didn't reserved enough length"); | |
241 _markedRegions.trunc_to(_first_par_unreserved_idx); | |
242 } | |
243 _markedRegions.sort(orderRegions); | |
244 assert(_numMarkedRegions <= _markedRegions.length(), "Requirement"); | |
245 assert(_numMarkedRegions == 0 | |
246 || _markedRegions.at(_numMarkedRegions-1) != NULL, | |
247 "Testing _numMarkedRegions"); | |
248 assert(_numMarkedRegions == _markedRegions.length() | |
249 || _markedRegions.at(_numMarkedRegions) == NULL, | |
250 "Testing _numMarkedRegions"); | |
251 if (G1PrintParCleanupStats) { | |
252 gclog_or_tty->print_cr(" Sorted %d marked regions.", _numMarkedRegions); | |
253 } | |
254 for (int i = 0; i < _numMarkedRegions; i++) { | |
255 assert(_markedRegions.at(i) != NULL, "Should be true by sorting!"); | |
256 _markedRegions.at(i)->set_sort_index(i); | |
257 if (G1PrintRegionLivenessInfo > 0) { | |
258 if (i == 0) gclog_or_tty->print_cr("Sorted marked regions:"); | |
259 if (i < G1PrintRegionLivenessInfo || | |
260 (_numMarkedRegions-i) < G1PrintRegionLivenessInfo) { | |
261 HeapRegion* hr = _markedRegions.at(i); | |
262 size_t u = hr->used(); | |
263 gclog_or_tty->print_cr(" Region %d: %d used, %d max live, %5.2f%%.", | |
264 i, u, hr->max_live_bytes(), | |
265 100.0*(float)hr->max_live_bytes()/(float)u); | |
266 } | |
267 } | |
268 } | |
269 if (G1PolicyVerbose > 1) | |
270 printSortedHeapRegions(); | |
271 assert(verify(), "should now be sorted"); | |
272 } | |
273 | |
274 void | |
275 printHeapRegion(HeapRegion *hr) { | |
276 if (hr->isHumongous()) | |
277 gclog_or_tty->print("H: "); | |
278 if (hr->in_collection_set()) | |
279 gclog_or_tty->print("CS: "); | |
280 if (hr->popular()) | |
281 gclog_or_tty->print("pop: "); | |
282 gclog_or_tty->print_cr("Region " PTR_FORMAT " (%s%s) " | |
283 "[" PTR_FORMAT ", " PTR_FORMAT"] " | |
284 "Used: " SIZE_FORMAT "K, garbage: " SIZE_FORMAT "K.", | |
285 hr, hr->is_young() ? "Y " : " ", | |
286 hr->is_marked()? "M1" : "M0", | |
287 hr->bottom(), hr->end(), | |
288 hr->used()/K, hr->garbage_bytes()/K); | |
289 } | |
290 | |
291 void | |
292 CollectionSetChooser::addMarkedHeapRegion(HeapRegion* hr) { | |
293 assert(!hr->isHumongous(), | |
294 "Humongous regions shouldn't be added to the collection set"); | |
295 assert(!hr->is_young(), "should not be young!"); | |
296 _markedRegions.append(hr); | |
297 _numMarkedRegions++; | |
298 hr->calc_gc_efficiency(); | |
299 } | |
300 | |
301 void | |
302 CollectionSetChooser:: | |
303 prepareForAddMarkedHeapRegionsPar(size_t n_regions, size_t chunkSize) { | |
304 _first_par_unreserved_idx = 0; | |
305 size_t max_waste = ParallelGCThreads * chunkSize; | |
306 // it should be aligned with respect to chunkSize | |
307 size_t aligned_n_regions = | |
308 (n_regions + (chunkSize - 1)) / chunkSize * chunkSize; | |
309 assert( aligned_n_regions % chunkSize == 0, "should be aligned" ); | |
310 _markedRegions.at_put_grow((int)(aligned_n_regions + max_waste - 1), NULL); | |
311 } | |
312 | |
313 jint | |
314 CollectionSetChooser::getParMarkedHeapRegionChunk(jint n_regions) { | |
315 jint res = Atomic::add(n_regions, &_first_par_unreserved_idx); | |
316 assert(_markedRegions.length() > res + n_regions - 1, | |
317 "Should already have been expanded"); | |
318 return res - n_regions; | |
319 } | |
320 | |
321 void | |
322 CollectionSetChooser::setMarkedHeapRegion(jint index, HeapRegion* hr) { | |
323 assert(_markedRegions.at(index) == NULL, "precondition"); | |
324 assert(!hr->is_young(), "should not be young!"); | |
325 _markedRegions.at_put(index, hr); | |
326 hr->calc_gc_efficiency(); | |
327 } | |
328 | |
329 void | |
330 CollectionSetChooser::incNumMarkedHeapRegions(jint inc_by) { | |
331 (void)Atomic::add(inc_by, &_numMarkedRegions); | |
332 } | |
333 | |
334 void | |
335 CollectionSetChooser::clearMarkedHeapRegions(){ | |
336 for (int i = 0; i < _markedRegions.length(); i++) { | |
337 HeapRegion* r = _markedRegions.at(i); | |
338 if (r != NULL) r->set_sort_index(-1); | |
339 } | |
340 _markedRegions.clear(); | |
341 _curMarkedIndex = 0; | |
342 _numMarkedRegions = 0; | |
343 _cache.clear(); | |
344 }; | |
345 | |
346 void | |
347 CollectionSetChooser::updateAfterFullCollection() { | |
348 G1CollectedHeap* g1h = G1CollectedHeap::heap(); | |
349 clearMarkedHeapRegions(); | |
350 } | |
351 | |
352 void | |
353 CollectionSetChooser::printSortedHeapRegions() { | |
354 gclog_or_tty->print_cr("Printing %d Heap Regions sorted by amount of known garbage", | |
355 _numMarkedRegions); | |
356 for (int i = 0; i < _markedRegions.length(); i++) { | |
357 printHeapRegion(_markedRegions.at(i)); | |
358 } | |
359 gclog_or_tty->print_cr("Done sorted heap region print"); | |
360 } | |
361 | |
362 void CollectionSetChooser::removeRegion(HeapRegion *hr) { | |
363 int si = hr->sort_index(); | |
364 assert(si == -1 || hr->is_marked(), "Sort index not valid."); | |
365 if (si > -1) { | |
366 assert(_markedRegions.at(si) == hr, "Sort index not valid." ); | |
367 _markedRegions.at_put(si, NULL); | |
368 } else if (si < -1) { | |
369 assert(_cache.region_in_cache(hr), "should be in the cache"); | |
370 _cache.remove(hr); | |
371 assert(hr->sort_index() == -1, "sort index invariant"); | |
372 } | |
373 hr->set_sort_index(-1); | |
374 } | |
375 | |
376 // if time_remaining < 0.0, then this method should try to return | |
377 // a region, whether it fits within the remaining time or not | |
378 HeapRegion* | |
379 CollectionSetChooser::getNextMarkedRegion(double time_remaining, | |
380 double avg_prediction) { | |
381 G1CollectedHeap* g1h = G1CollectedHeap::heap(); | |
382 G1CollectorPolicy* g1p = g1h->g1_policy(); | |
383 fillCache(); | |
384 if (_cache.is_empty()) { | |
385 assert(_curMarkedIndex == _numMarkedRegions, | |
386 "if cache is empty, list should also be empty"); | |
387 return NULL; | |
388 } | |
389 | |
390 HeapRegion *hr = _cache.get_first(); | |
391 assert(hr != NULL, "if cache not empty, first entry should be non-null"); | |
392 double predicted_time = g1h->predict_region_elapsed_time_ms(hr, false); | |
393 | |
394 if (g1p->adaptive_young_list_length()) { | |
395 if (time_remaining - predicted_time < 0.0) { | |
396 g1h->check_if_region_is_too_expensive(predicted_time); | |
397 return NULL; | |
398 } | |
399 } else { | |
400 if (predicted_time > 2.0 * avg_prediction) { | |
401 return NULL; | |
402 } | |
403 } | |
404 | |
405 HeapRegion *hr2 = _cache.remove_first(); | |
406 assert(hr == hr2, "cache contents should not have changed"); | |
407 | |
408 return hr; | |
409 } |