1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/gc_implementation/g1/collectionSetChooser.cpp Thu Jun 05 15:57:56 2008 -0700
1.3 @@ -0,0 +1,409 @@
1.4 +/*
1.5 + * Copyright 2001-2007 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +# include "incls/_precompiled.incl"
1.29 +# include "incls/_collectionSetChooser.cpp.incl"
1.30 +
1.31 +CSetChooserCache::CSetChooserCache() {
1.32 + for (int i = 0; i < CacheLength; ++i)
1.33 + _cache[i] = NULL;
1.34 + clear();
1.35 +}
1.36 +
1.37 +void CSetChooserCache::clear() {
1.38 + _occupancy = 0;
1.39 + _first = 0;
1.40 + for (int i = 0; i < CacheLength; ++i) {
1.41 + HeapRegion *hr = _cache[i];
1.42 + if (hr != NULL)
1.43 + hr->set_sort_index(-1);
1.44 + _cache[i] = NULL;
1.45 + }
1.46 +}
1.47 +
1.48 +#ifndef PRODUCT
1.49 +bool CSetChooserCache::verify() {
1.50 + int index = _first;
1.51 + HeapRegion *prev = NULL;
1.52 + for (int i = 0; i < _occupancy; ++i) {
1.53 + guarantee(_cache[index] != NULL, "cache entry should not be empty");
1.54 + HeapRegion *hr = _cache[index];
1.55 + guarantee(!hr->is_young(), "should not be young!");
1.56 + if (prev != NULL) {
1.57 + guarantee(prev->gc_efficiency() >= hr->gc_efficiency(),
1.58 + "cache should be correctly ordered");
1.59 + }
1.60 + guarantee(hr->sort_index() == get_sort_index(index),
1.61 + "sort index should be correct");
1.62 + index = trim_index(index + 1);
1.63 + prev = hr;
1.64 + }
1.65 +
1.66 + for (int i = 0; i < (CacheLength - _occupancy); ++i) {
1.67 + guarantee(_cache[index] == NULL, "cache entry should be empty");
1.68 + index = trim_index(index + 1);
1.69 + }
1.70 +
1.71 + guarantee(index == _first, "we should have reached where we started from");
1.72 + return true;
1.73 +}
1.74 +#endif // PRODUCT
1.75 +
1.76 +void CSetChooserCache::insert(HeapRegion *hr) {
1.77 + assert(!is_full(), "cache should not be empty");
1.78 + hr->calc_gc_efficiency();
1.79 +
1.80 + int empty_index;
1.81 + if (_occupancy == 0) {
1.82 + empty_index = _first;
1.83 + } else {
1.84 + empty_index = trim_index(_first + _occupancy);
1.85 + assert(_cache[empty_index] == NULL, "last slot should be empty");
1.86 + int last_index = trim_index(empty_index - 1);
1.87 + HeapRegion *last = _cache[last_index];
1.88 + assert(last != NULL,"as the cache is not empty, last should not be empty");
1.89 + while (empty_index != _first &&
1.90 + last->gc_efficiency() < hr->gc_efficiency()) {
1.91 + _cache[empty_index] = last;
1.92 + last->set_sort_index(get_sort_index(empty_index));
1.93 + empty_index = last_index;
1.94 + last_index = trim_index(last_index - 1);
1.95 + last = _cache[last_index];
1.96 + }
1.97 + }
1.98 + _cache[empty_index] = hr;
1.99 + hr->set_sort_index(get_sort_index(empty_index));
1.100 +
1.101 + ++_occupancy;
1.102 + assert(verify(), "cache should be consistent");
1.103 +}
1.104 +
1.105 +HeapRegion *CSetChooserCache::remove_first() {
1.106 + if (_occupancy > 0) {
1.107 + assert(_cache[_first] != NULL, "cache should have at least one region");
1.108 + HeapRegion *ret = _cache[_first];
1.109 + _cache[_first] = NULL;
1.110 + ret->set_sort_index(-1);
1.111 + --_occupancy;
1.112 + _first = trim_index(_first + 1);
1.113 + assert(verify(), "cache should be consistent");
1.114 + return ret;
1.115 + } else {
1.116 + return NULL;
1.117 + }
1.118 +}
1.119 +
1.120 +// this is a bit expensive... but we expect that it should not be called
1.121 +// to often.
1.122 +void CSetChooserCache::remove(HeapRegion *hr) {
1.123 + assert(_occupancy > 0, "cache should not be empty");
1.124 + assert(hr->sort_index() < -1, "should already be in the cache");
1.125 + int index = get_index(hr->sort_index());
1.126 + assert(_cache[index] == hr, "index should be correct");
1.127 + int next_index = trim_index(index + 1);
1.128 + int last_index = trim_index(_first + _occupancy - 1);
1.129 + while (index != last_index) {
1.130 + assert(_cache[next_index] != NULL, "should not be null");
1.131 + _cache[index] = _cache[next_index];
1.132 + _cache[index]->set_sort_index(get_sort_index(index));
1.133 +
1.134 + index = next_index;
1.135 + next_index = trim_index(next_index+1);
1.136 + }
1.137 + assert(index == last_index, "should have reached the last one");
1.138 + _cache[index] = NULL;
1.139 + hr->set_sort_index(-1);
1.140 + --_occupancy;
1.141 + assert(verify(), "cache should be consistent");
1.142 +}
1.143 +
1.144 +static inline int orderRegions(HeapRegion* hr1, HeapRegion* hr2) {
1.145 + if (hr1 == NULL) {
1.146 + if (hr2 == NULL) return 0;
1.147 + else return 1;
1.148 + } else if (hr2 == NULL) {
1.149 + return -1;
1.150 + }
1.151 + if (hr2->gc_efficiency() < hr1->gc_efficiency()) return -1;
1.152 + else if (hr1->gc_efficiency() < hr2->gc_efficiency()) return 1;
1.153 + else return 0;
1.154 +}
1.155 +
1.156 +static int orderRegions(HeapRegion** hr1p, HeapRegion** hr2p) {
1.157 + return orderRegions(*hr1p, *hr2p);
1.158 +}
1.159 +
1.160 +CollectionSetChooser::CollectionSetChooser() :
1.161 + // The line below is the worst bit of C++ hackery I've ever written
1.162 + // (Detlefs, 11/23). You should think of it as equivalent to
1.163 + // "_regions(100, true)": initialize the growable array and inform it
1.164 + // that it should allocate its elem array(s) on the C heap. The first
1.165 + // argument, however, is actually a comma expression (new-expr, 100).
1.166 + // The purpose of the new_expr is to inform the growable array that it
1.167 + // is *already* allocated on the C heap: it uses the placement syntax to
1.168 + // keep it from actually doing any allocation.
1.169 + _markedRegions((ResourceObj::operator new (sizeof(GrowableArray<HeapRegion*>),
1.170 + (void*)&_markedRegions,
1.171 + ResourceObj::C_HEAP),
1.172 + 100),
1.173 + true),
1.174 + _curMarkedIndex(0),
1.175 + _numMarkedRegions(0),
1.176 + _unmarked_age_1_returned_as_new(false),
1.177 + _first_par_unreserved_idx(0)
1.178 +{}
1.179 +
1.180 +
1.181 +
1.182 +#ifndef PRODUCT
1.183 +bool CollectionSetChooser::verify() {
1.184 + int index = 0;
1.185 + guarantee(_curMarkedIndex <= _numMarkedRegions,
1.186 + "_curMarkedIndex should be within bounds");
1.187 + while (index < _curMarkedIndex) {
1.188 + guarantee(_markedRegions.at(index++) == NULL,
1.189 + "all entries before _curMarkedIndex should be NULL");
1.190 + }
1.191 + HeapRegion *prev = NULL;
1.192 + while (index < _numMarkedRegions) {
1.193 + HeapRegion *curr = _markedRegions.at(index++);
1.194 + if (curr != NULL) {
1.195 + int si = curr->sort_index();
1.196 + guarantee(!curr->is_young(), "should not be young!");
1.197 + guarantee(si > -1 && si == (index-1), "sort index invariant");
1.198 + if (prev != NULL) {
1.199 + guarantee(orderRegions(prev, curr) != 1, "regions should be sorted");
1.200 + }
1.201 + prev = curr;
1.202 + }
1.203 + }
1.204 + return _cache.verify();
1.205 +}
1.206 +#endif
1.207 +
1.208 +bool
1.209 +CollectionSetChooser::addRegionToCache() {
1.210 + assert(!_cache.is_full(), "cache should not be full");
1.211 +
1.212 + HeapRegion *hr = NULL;
1.213 + while (hr == NULL && _curMarkedIndex < _numMarkedRegions) {
1.214 + hr = _markedRegions.at(_curMarkedIndex++);
1.215 + }
1.216 + if (hr == NULL)
1.217 + return false;
1.218 + assert(!hr->is_young(), "should not be young!");
1.219 + assert(hr->sort_index() == _curMarkedIndex-1, "sort_index invariant");
1.220 + _markedRegions.at_put(hr->sort_index(), NULL);
1.221 + _cache.insert(hr);
1.222 + assert(!_cache.is_empty(), "cache should not be empty");
1.223 + assert(verify(), "cache should be consistent");
1.224 + return false;
1.225 +}
1.226 +
1.227 +void
1.228 +CollectionSetChooser::fillCache() {
1.229 + while (!_cache.is_full() && addRegionToCache()) {
1.230 + }
1.231 +}
1.232 +
1.233 +void
1.234 +CollectionSetChooser::sortMarkedHeapRegions() {
1.235 + guarantee(_cache.is_empty(), "cache should be empty");
1.236 + // First trim any unused portion of the top in the parallel case.
1.237 + if (_first_par_unreserved_idx > 0) {
1.238 + if (G1PrintParCleanupStats) {
1.239 + gclog_or_tty->print(" Truncating _markedRegions from %d to %d.\n",
1.240 + _markedRegions.length(), _first_par_unreserved_idx);
1.241 + }
1.242 + assert(_first_par_unreserved_idx <= _markedRegions.length(),
1.243 + "Or we didn't reserved enough length");
1.244 + _markedRegions.trunc_to(_first_par_unreserved_idx);
1.245 + }
1.246 + _markedRegions.sort(orderRegions);
1.247 + assert(_numMarkedRegions <= _markedRegions.length(), "Requirement");
1.248 + assert(_numMarkedRegions == 0
1.249 + || _markedRegions.at(_numMarkedRegions-1) != NULL,
1.250 + "Testing _numMarkedRegions");
1.251 + assert(_numMarkedRegions == _markedRegions.length()
1.252 + || _markedRegions.at(_numMarkedRegions) == NULL,
1.253 + "Testing _numMarkedRegions");
1.254 + if (G1PrintParCleanupStats) {
1.255 + gclog_or_tty->print_cr(" Sorted %d marked regions.", _numMarkedRegions);
1.256 + }
1.257 + for (int i = 0; i < _numMarkedRegions; i++) {
1.258 + assert(_markedRegions.at(i) != NULL, "Should be true by sorting!");
1.259 + _markedRegions.at(i)->set_sort_index(i);
1.260 + if (G1PrintRegionLivenessInfo > 0) {
1.261 + if (i == 0) gclog_or_tty->print_cr("Sorted marked regions:");
1.262 + if (i < G1PrintRegionLivenessInfo ||
1.263 + (_numMarkedRegions-i) < G1PrintRegionLivenessInfo) {
1.264 + HeapRegion* hr = _markedRegions.at(i);
1.265 + size_t u = hr->used();
1.266 + gclog_or_tty->print_cr(" Region %d: %d used, %d max live, %5.2f%%.",
1.267 + i, u, hr->max_live_bytes(),
1.268 + 100.0*(float)hr->max_live_bytes()/(float)u);
1.269 + }
1.270 + }
1.271 + }
1.272 + if (G1PolicyVerbose > 1)
1.273 + printSortedHeapRegions();
1.274 + assert(verify(), "should now be sorted");
1.275 +}
1.276 +
1.277 +void
1.278 +printHeapRegion(HeapRegion *hr) {
1.279 + if (hr->isHumongous())
1.280 + gclog_or_tty->print("H: ");
1.281 + if (hr->in_collection_set())
1.282 + gclog_or_tty->print("CS: ");
1.283 + if (hr->popular())
1.284 + gclog_or_tty->print("pop: ");
1.285 + gclog_or_tty->print_cr("Region " PTR_FORMAT " (%s%s) "
1.286 + "[" PTR_FORMAT ", " PTR_FORMAT"] "
1.287 + "Used: " SIZE_FORMAT "K, garbage: " SIZE_FORMAT "K.",
1.288 + hr, hr->is_young() ? "Y " : " ",
1.289 + hr->is_marked()? "M1" : "M0",
1.290 + hr->bottom(), hr->end(),
1.291 + hr->used()/K, hr->garbage_bytes()/K);
1.292 +}
1.293 +
1.294 +void
1.295 +CollectionSetChooser::addMarkedHeapRegion(HeapRegion* hr) {
1.296 + assert(!hr->isHumongous(),
1.297 + "Humongous regions shouldn't be added to the collection set");
1.298 + assert(!hr->is_young(), "should not be young!");
1.299 + _markedRegions.append(hr);
1.300 + _numMarkedRegions++;
1.301 + hr->calc_gc_efficiency();
1.302 +}
1.303 +
1.304 +void
1.305 +CollectionSetChooser::
1.306 +prepareForAddMarkedHeapRegionsPar(size_t n_regions, size_t chunkSize) {
1.307 + _first_par_unreserved_idx = 0;
1.308 + size_t max_waste = ParallelGCThreads * chunkSize;
1.309 + // it should be aligned with respect to chunkSize
1.310 + size_t aligned_n_regions =
1.311 + (n_regions + (chunkSize - 1)) / chunkSize * chunkSize;
1.312 + assert( aligned_n_regions % chunkSize == 0, "should be aligned" );
1.313 + _markedRegions.at_put_grow((int)(aligned_n_regions + max_waste - 1), NULL);
1.314 +}
1.315 +
1.316 +jint
1.317 +CollectionSetChooser::getParMarkedHeapRegionChunk(jint n_regions) {
1.318 + jint res = Atomic::add(n_regions, &_first_par_unreserved_idx);
1.319 + assert(_markedRegions.length() > res + n_regions - 1,
1.320 + "Should already have been expanded");
1.321 + return res - n_regions;
1.322 +}
1.323 +
1.324 +void
1.325 +CollectionSetChooser::setMarkedHeapRegion(jint index, HeapRegion* hr) {
1.326 + assert(_markedRegions.at(index) == NULL, "precondition");
1.327 + assert(!hr->is_young(), "should not be young!");
1.328 + _markedRegions.at_put(index, hr);
1.329 + hr->calc_gc_efficiency();
1.330 +}
1.331 +
1.332 +void
1.333 +CollectionSetChooser::incNumMarkedHeapRegions(jint inc_by) {
1.334 + (void)Atomic::add(inc_by, &_numMarkedRegions);
1.335 +}
1.336 +
1.337 +void
1.338 +CollectionSetChooser::clearMarkedHeapRegions(){
1.339 + for (int i = 0; i < _markedRegions.length(); i++) {
1.340 + HeapRegion* r = _markedRegions.at(i);
1.341 + if (r != NULL) r->set_sort_index(-1);
1.342 + }
1.343 + _markedRegions.clear();
1.344 + _curMarkedIndex = 0;
1.345 + _numMarkedRegions = 0;
1.346 + _cache.clear();
1.347 +};
1.348 +
1.349 +void
1.350 +CollectionSetChooser::updateAfterFullCollection() {
1.351 + G1CollectedHeap* g1h = G1CollectedHeap::heap();
1.352 + clearMarkedHeapRegions();
1.353 +}
1.354 +
1.355 +void
1.356 +CollectionSetChooser::printSortedHeapRegions() {
1.357 + gclog_or_tty->print_cr("Printing %d Heap Regions sorted by amount of known garbage",
1.358 + _numMarkedRegions);
1.359 + for (int i = 0; i < _markedRegions.length(); i++) {
1.360 + printHeapRegion(_markedRegions.at(i));
1.361 + }
1.362 + gclog_or_tty->print_cr("Done sorted heap region print");
1.363 +}
1.364 +
1.365 +void CollectionSetChooser::removeRegion(HeapRegion *hr) {
1.366 + int si = hr->sort_index();
1.367 + assert(si == -1 || hr->is_marked(), "Sort index not valid.");
1.368 + if (si > -1) {
1.369 + assert(_markedRegions.at(si) == hr, "Sort index not valid." );
1.370 + _markedRegions.at_put(si, NULL);
1.371 + } else if (si < -1) {
1.372 + assert(_cache.region_in_cache(hr), "should be in the cache");
1.373 + _cache.remove(hr);
1.374 + assert(hr->sort_index() == -1, "sort index invariant");
1.375 + }
1.376 + hr->set_sort_index(-1);
1.377 +}
1.378 +
1.379 +// if time_remaining < 0.0, then this method should try to return
1.380 +// a region, whether it fits within the remaining time or not
1.381 +HeapRegion*
1.382 +CollectionSetChooser::getNextMarkedRegion(double time_remaining,
1.383 + double avg_prediction) {
1.384 + G1CollectedHeap* g1h = G1CollectedHeap::heap();
1.385 + G1CollectorPolicy* g1p = g1h->g1_policy();
1.386 + fillCache();
1.387 + if (_cache.is_empty()) {
1.388 + assert(_curMarkedIndex == _numMarkedRegions,
1.389 + "if cache is empty, list should also be empty");
1.390 + return NULL;
1.391 + }
1.392 +
1.393 + HeapRegion *hr = _cache.get_first();
1.394 + assert(hr != NULL, "if cache not empty, first entry should be non-null");
1.395 + double predicted_time = g1h->predict_region_elapsed_time_ms(hr, false);
1.396 +
1.397 + if (g1p->adaptive_young_list_length()) {
1.398 + if (time_remaining - predicted_time < 0.0) {
1.399 + g1h->check_if_region_is_too_expensive(predicted_time);
1.400 + return NULL;
1.401 + }
1.402 + } else {
1.403 + if (predicted_time > 2.0 * avg_prediction) {
1.404 + return NULL;
1.405 + }
1.406 + }
1.407 +
1.408 + HeapRegion *hr2 = _cache.remove_first();
1.409 + assert(hr == hr2, "cache contents should not have changed");
1.410 +
1.411 + return hr;
1.412 +}
