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 }