2  * Copyright (c) 2001, 2018, Oracle and/or its affiliates. All rights reserved.

     2  * Copyright (c) 2001, 2019, Oracle and/or its affiliates. All rights reserved.

    31 

    32 #include "utilities/quickSort.hpp"

    32 // Even though we don't use the GC efficiency in our heuristics as

    33 

    33 // much as we used to, we still order according to GC efficiency. This

    34 // Order regions according to GC efficiency. This will cause regions with a lot

    34 // will cause regions with a lot of live objects and large RSets to

    35 // of live objects and large remembered sets to end up at the end of the array.

    35 // end up at the end of the array. Given that we might skip collecting

    36 // Given that we might skip collecting the last few old regions, if after a few

    36 // the last few old regions, if after a few mixed GCs the remaining

    37 // mixed GCs the remaining have reclaimable bytes under a certain threshold, the

    37 // have reclaimable bytes under a certain threshold, the hope is that

    38 // hope is that the ones we'll skip are ones with both large remembered sets and

    38 // the ones we'll skip are ones with both large RSets and a lot of

    39 // a lot of live objects, not the ones with just a lot of live objects if we

    39 // live objects, not the ones with just a lot of live objects if we

    63 static int order_regions(HeapRegion** hr1p, HeapRegion** hr2p) {

    65 // Determine collection set candidates: For all regions determine whether they

    64   return order_regions(*hr1p, *hr2p);

    66 // should be a collection set candidates, calculate their efficiency, sort and

    65 }

    67 // return them as G1CollectionSetCandidates instance.

    66 

    68 // Threads calculate the GC efficiency of the regions they get to process, and

    67 CollectionSetChooser::CollectionSetChooser() :

    69 // put them into some work area unsorted. At the end the array is sorted and

    68   // The line below is the worst bit of C++ hackery I've ever written

    70 // copied into the G1CollectionSetCandidates instance; the caller will be the new

    69   // (Detlefs, 11/23).  You should think of it as equivalent to

    71 // owner of this object.

    70   // "_regions(100, true)": initialize the growable array and inform it

    72 class G1BuildCandidateRegionsTask : public AbstractGangTask {

    71   // that it should allocate its elem array(s) on the C heap.

    73 

    72   //

    74   // Work area for building the set of collection set candidates. Contains references

    73   // The first argument, however, is actually a comma expression

    75   // to heap regions with their GC efficiencies calculated. To reduce contention

    74   // (set_allocation_type(this, C_HEAP), 100). The purpose of the

    76   // on claiming array elements, worker threads claim parts of this array in chunks;

    75   // set_allocation_type() call is to replace the default allocation

    77   // Array elements may be NULL as threads might not get enough regions to fill

    76   // type for embedded objects STACK_OR_EMBEDDED with C_HEAP. It will

    78   // up their chunks completely.

    77   // allow to pass the assert in GenericGrowableArray() which checks

    79   // Final sorting will remove them.

    78   // that a growable array object must be on C heap if elements are.

    80   class G1BuildCandidateArray : public StackObj {

    79   //

    81 

    80   // Note: containing object is allocated on C heap since it is CHeapObj.

    82     uint const _max_size;

    81   //

    83     uint const _chunk_size;

    82   _regions((ResourceObj::set_allocation_type((address) &_regions,

    84 

    83                                              ResourceObj::C_HEAP),

    85     HeapRegion** _data;

    84                   100), true /* C_Heap */),

    86 

    85     _front(0), _end(0), _first_par_unreserved_idx(0),

    87     uint volatile _cur_claim_idx;

    86     _region_live_threshold_bytes(0), _remaining_reclaimable_bytes(0) {

    88 

    87   _region_live_threshold_bytes = mixed_gc_live_threshold_bytes();

    89     // Calculates the maximum array size that will be used.

    88 }

    90     static uint required_array_size(uint num_regions, uint num_workers, uint chunk_size) {

    89 

    91       uint const max_waste = num_workers * chunk_size;

    90 #ifndef PRODUCT

    92       // The array should be aligned with respect to chunk_size.

    91 void CollectionSetChooser::verify() {

    93       uint const aligned_num_regions = ((num_regions + chunk_size - 1) / chunk_size) * chunk_size;

    92   guarantee(_end <= regions_length(), "_end: %u regions length: %u", _end, regions_length());

    94 

    93   guarantee(_front <= _end, "_front: %u _end: %u", _front, _end);

    95       return aligned_num_regions + max_waste;

    94   uint index = 0;

    96     }

    95   size_t sum_of_reclaimable_bytes = 0;

    97 

    96   while (index < _front) {

    98   public:

    97     guarantee(regions_at(index) == NULL,

    99     G1BuildCandidateArray(uint max_num_regions, uint num_workers, uint chunk_size) :

    98               "all entries before _front should be NULL");

   100       _max_size(required_array_size(max_num_regions, num_workers, chunk_size)),

    99     index += 1;

   101       _chunk_size(chunk_size),

   100   }

   102       _data(NEW_C_HEAP_ARRAY(HeapRegion*, _max_size, mtGC)),

   101   HeapRegion *prev = NULL;

   103       _cur_claim_idx(0) {

   102   while (index < _end) {

   104       for (uint i = 0; i < _max_size; i++) {

   103     HeapRegion *curr = regions_at(index++);

   105         _data[i] = NULL;

   104     guarantee(curr != NULL, "Regions in _regions array cannot be NULL");

   106       }

   105     guarantee(!curr->is_young(), "should not be young!");

   107     }

   106     guarantee(!curr->is_pinned(),

   108 

   107               "Pinned region should not be in collection set (index %u)", curr->hrm_index());

   109     ~G1BuildCandidateArray() {

   108     if (prev != NULL) {

   110       FREE_C_HEAP_ARRAY(HeapRegion*, _data);

   109       guarantee(order_regions(prev, curr) != 1,

   111     }

   110                 "GC eff prev: %1.4f GC eff curr: %1.4f",

   112 

   111                 prev->gc_efficiency(), curr->gc_efficiency());

   113     // Claim a new chunk, returning its bounds [from, to[.

   112     }

   114     void claim_chunk(uint& from, uint& to) {

   113     sum_of_reclaimable_bytes += curr->reclaimable_bytes();

   115       uint result = Atomic::add(_chunk_size, &_cur_claim_idx);

   114     prev = curr;

   116       assert(_max_size > result - 1,

   115   }

   117              "Array too small, is %u should be %u with chunk size %u.",

   116   guarantee(sum_of_reclaimable_bytes == _remaining_reclaimable_bytes,

   118              _max_size, result, _chunk_size);

   117             "reclaimable bytes inconsistent, "

   119       from = result - _chunk_size;

   118             "remaining: " SIZE_FORMAT " sum: " SIZE_FORMAT,

   120       to = result;

   119             _remaining_reclaimable_bytes, sum_of_reclaimable_bytes);

   121     }

   120 }

   122 

   121 #endif // !PRODUCT

   123     // Set element in array.

   122 

   124     void set(uint idx, HeapRegion* hr) {

   123 void CollectionSetChooser::sort_regions() {

   125       assert(idx < _max_size, "Index %u out of bounds %u", idx, _max_size);

   124   // First trim any unused portion of the top in the parallel case.

   126       assert(_data[idx] == NULL, "Value must not have been set.");

   125   if (_first_par_unreserved_idx > 0) {

   127       _data[idx] = hr;

   126     assert(_first_par_unreserved_idx <= regions_length(),

   128     }

   127            "Or we didn't reserved enough length");

   129 

   128     regions_trunc_to(_first_par_unreserved_idx);

   130     void sort_and_copy_into(HeapRegion** dest, uint num_regions) {

   129   }

   131       if (_cur_claim_idx == 0) {

   130   _regions.sort(order_regions);

   132         return;

   131   assert(_end <= regions_length(), "Requirement");

   133       }

   132 #ifdef ASSERT

   134       for (uint i = _cur_claim_idx; i < _max_size; i++) {

   133   for (uint i = 0; i < _end; i++) {

   135         assert(_data[i] == NULL, "must be");

   134     assert(regions_at(i) != NULL, "Should be true by sorting!");

   136       }

   135   }

   137       QuickSort::sort(_data, _cur_claim_idx, order_regions, true);

   136 #endif // ASSERT

   138       for (uint i = num_regions; i < _max_size; i++) {

   137   if (log_is_enabled(Trace, gc, liveness)) {

   139         assert(_data[i] == NULL, "must be");

   138     G1PrintRegionLivenessInfoClosure cl("Post-Sorting");

   140       }

   139     for (uint i = 0; i < _end; ++i) {

   141       for (uint i = 0; i < num_regions; i++) {

   140       HeapRegion* r = regions_at(i);

   142         dest[i] = _data[i];

   141       cl.do_heap_region(r);

   143       }

   142     }

   144     }

   143   }

   145   };

   144   verify();

   146 

   145 }

   147   // Per-region closure. In addition to determining whether a region should be

   146 

   148   // added to the candidates, and calculating those regions' gc efficiencies, also

   147 void CollectionSetChooser::add_region(HeapRegion* hr) {

   149   // gather additional statistics.

   148   assert(!hr->is_pinned(),

   150   class G1BuildCandidateRegionsClosure : public HeapRegionClosure {

   149          "Pinned region shouldn't be added to the collection set (index %u)", hr->hrm_index());

   151     G1BuildCandidateArray* _array;

   150   assert(hr->is_old(), "should be old but is %s", hr->get_type_str());

   152 

   151   assert(hr->rem_set()->is_complete(),

   153     uint _cur_chunk_idx;

   152          "Trying to add region %u to the collection set with incomplete remembered set", hr->hrm_index());

   154     uint _cur_chunk_end;

   153   _regions.append(hr);

   155 

   154   _end++;

   156     uint _regions_added;

   155   _remaining_reclaimable_bytes += hr->reclaimable_bytes();

   157     size_t _reclaimable_bytes_added;

   156   hr->calc_gc_efficiency();

   158 

   157 }

   159     void add_region(HeapRegion* hr) {

   158 

   160       if (_cur_chunk_idx == _cur_chunk_end) {

   159 void CollectionSetChooser::push(HeapRegion* hr) {

   161         _array->claim_chunk(_cur_chunk_idx, _cur_chunk_end);

   160   assert(hr != NULL, "Can't put back a NULL region");

   162       }

   161   assert(_front >= 1, "Too many regions have been put back");

   163       assert(_cur_chunk_idx < _cur_chunk_end, "Must be");

   162   _front--;

   164 

   163   regions_at_put(_front, hr);

   165       hr->calc_gc_efficiency();

   164   _remaining_reclaimable_bytes += hr->reclaimable_bytes();

   166       _array->set(_cur_chunk_idx, hr);

   165 }

   167 

   166 

   168       _cur_chunk_idx++;

   167 void CollectionSetChooser::prepare_for_par_region_addition(uint n_threads,

   169 

   168                                                            uint n_regions,

   170       _regions_added++;

   169                                                            uint chunk_size) {

   171       _reclaimable_bytes_added += hr->reclaimable_bytes();

   170   _first_par_unreserved_idx = 0;

   172     }

   171   uint max_waste = n_threads * chunk_size;

   173 

   172   // it should be aligned with respect to chunk_size

   174     bool should_add(HeapRegion* hr) { return CollectionSetChooser::should_add(hr); }

   173   uint aligned_n_regions = (n_regions + chunk_size - 1) / chunk_size * chunk_size;

   175 

   174   assert(aligned_n_regions % chunk_size == 0, "should be aligned");

   176   public:

   175   regions_at_put_grow(aligned_n_regions + max_waste - 1, NULL);

   177     G1BuildCandidateRegionsClosure(G1BuildCandidateArray* array) :

   176 }

   178       _array(array),

   177 

   179       _cur_chunk_idx(0),

   178 uint CollectionSetChooser::claim_array_chunk(uint chunk_size) {

   180       _cur_chunk_end(0),

   179   uint res = (uint) Atomic::add((jint) chunk_size,

   181       _regions_added(0),

   180                                 (volatile jint*) &_first_par_unreserved_idx);

   182       _reclaimable_bytes_added(0) { }

   181   assert(regions_length() > res + chunk_size - 1,

   183 

   182          "Should already have been expanded");

   184     bool do_heap_region(HeapRegion* r) {

   183   return res - chunk_size;

   185       // We will skip any region that's currently used as an old GC

   184 }

   186       // alloc region (we should not consider those for collection

   185 

   187       // before we fill them up).

   186 void CollectionSetChooser::set_region(uint index, HeapRegion* hr) {

   188       if (should_add(r) && !G1CollectedHeap::heap()->is_old_gc_alloc_region(r)) {

   187   assert(regions_at(index) == NULL, "precondition");

   189         add_region(r);

   188   assert(hr->is_old(), "should be old but is %s", hr->get_type_str());

   190       } else if (r->is_old()) {

   189   regions_at_put(index, hr);

   191         // Keep remembered sets for humongous regions, otherwise clean out remembered

   190   hr->calc_gc_efficiency();

   192         // sets for old regions.

   191 }

   193         r->rem_set()->clear(true /* only_cardset */);

   192 

   194       } else {

   193 void CollectionSetChooser::update_totals(uint region_num,

   195         assert(r->is_archive() || !r->is_old() || !r->rem_set()->is_tracked(),

   194                                          size_t reclaimable_bytes) {

   196                "Missed to clear unused remembered set of region %u (%s) that is %s",

   195   // Only take the lock if we actually need to update the totals.

   197                r->hrm_index(), r->get_type_str(), r->rem_set()->get_state_str());

   196   if (region_num > 0) {

   198       }

   197     assert(reclaimable_bytes > 0, "invariant");

   199       return false;

   198     // We could have just used atomics instead of taking the

   200     }

   199     // lock. However, we currently don't have an atomic add for size_t.

   201 

   200     MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

   202     uint regions_added() const { return _regions_added; }

   201     _end += region_num;

   203     size_t reclaimable_bytes_added() const { return _reclaimable_bytes_added; }

   202     _remaining_reclaimable_bytes += reclaimable_bytes;

   204   };

   203   } else {

   205 

   204     assert(reclaimable_bytes == 0, "invariant");

   205   }

   206 }

   207 

   208 void CollectionSetChooser::iterate(HeapRegionClosure* cl) {

   209   for (uint i = _front; i < _end; i++) {

   210     HeapRegion* r = regions_at(i);

   211     if (cl->do_heap_region(r)) {

   212       cl->set_incomplete();

   213       break;

   214     }

   215   }

   216 }

   217 

   218 void CollectionSetChooser::clear() {

   219   _regions.clear();

   220   _front = 0;

   221   _end = 0;

   222   _remaining_reclaimable_bytes = 0;

   223 }

   224 

   225 class ParKnownGarbageHRClosure: public HeapRegionClosure {

   226   G1CollectedHeap* _g1h;

   227   CSetChooserParUpdater _cset_updater;

   228 

   229 public:

   230   ParKnownGarbageHRClosure(CollectionSetChooser* hrSorted,

   231                            uint chunk_size) :

   232     _g1h(G1CollectedHeap::heap()),

   233     _cset_updater(hrSorted, true /* parallel */, chunk_size) { }

   234 

   235   bool do_heap_region(HeapRegion* r) {

   236     // We will skip any region that's currently used as an old GC

   237     // alloc region (we should not consider those for collection

   238     // before we fill them up).

   239     if (_cset_updater.should_add(r) && !_g1h->is_old_gc_alloc_region(r)) {

   240       _cset_updater.add_region(r);

   241     } else if (r->is_old()) {

   242       // Keep remembered sets for humongous regions, otherwise clean out remembered

   243       // sets for old regions.

   244       r->rem_set()->clear(true /* only_cardset */);

   245     } else {

   246       assert(r->is_archive() || !r->is_old() || !r->rem_set()->is_tracked(),

   247              "Missed to clear unused remembered set of region %u (%s) that is %s",

   248              r->hrm_index(), r->get_type_str(), r->rem_set()->get_state_str());

   249     }

   250     return false;

   251   }

   252 };

   253 

   254 class ParKnownGarbageTask: public AbstractGangTask {

   255   CollectionSetChooser* _hrSorted;

   256   uint _chunk_size;

   261   ParKnownGarbageTask(CollectionSetChooser* hrSorted, uint chunk_size, uint n_workers) :

   225   G1BuildCandidateRegionsTask(uint max_num_regions, uint chunk_size, uint num_workers) :

   262       AbstractGangTask("ParKnownGarbageTask"),

   226     AbstractGangTask("G1 Build Candidate Regions"),

   263       _hrSorted(hrSorted), _chunk_size(chunk_size),

   227     _g1h(G1CollectedHeap::heap()),

   264       _g1h(G1CollectedHeap::heap()), _hrclaimer(n_workers) {}

   228     _hrclaimer(num_workers),

   229     _num_regions_added(0),

   230     _reclaimable_bytes_added(0),

   231     _result(max_num_regions, chunk_size, num_workers) { }

   267     ParKnownGarbageHRClosure par_known_garbage_cl(_hrSorted, _chunk_size);

   234     G1BuildCandidateRegionsClosure cl(&_result);

   268     _g1h->heap_region_par_iterate_from_worker_offset(&par_known_garbage_cl, &_hrclaimer, worker_id);

   235     _g1h->heap_region_par_iterate_from_worker_offset(&cl, &_hrclaimer, worker_id);

   236     update_totals(cl.regions_added(), cl.reclaimable_bytes_added());

   237   }

   238 

   239   G1CollectionSetCandidates* get_sorted_candidates() {

   240     HeapRegion** regions = NEW_C_HEAP_ARRAY(HeapRegion*, _num_regions_added, mtGC);

   241     _result.sort_and_copy_into(regions, _num_regions_added);

   242     return new G1CollectionSetCandidates(regions,

   243                                          _num_regions_added,

   244                                          _reclaimable_bytes_added);

   272 uint CollectionSetChooser::calculate_parallel_work_chunk_size(uint n_workers, uint n_regions) const {

   248 uint CollectionSetChooser::calculate_work_chunk_size(uint num_workers, uint num_regions) {

   273   assert(n_workers > 0, "Active gc workers should be greater than 0");

   249   assert(num_workers > 0, "Active gc workers should be greater than 0");

   274   const uint overpartition_factor = 4;

   250   return MAX2(num_regions / num_workers, 1U);

   275   const uint min_chunk_size = MAX2(n_regions / n_workers, 1U);

   251 }

   276   return MAX2(n_regions / (n_workers * overpartition_factor), min_chunk_size);

   252 

   277 }

   253 bool CollectionSetChooser::should_add(HeapRegion* hr) {

   278 

   279 bool CollectionSetChooser::region_occupancy_low_enough_for_evac(size_t live_bytes) {

   280   return live_bytes < mixed_gc_live_threshold_bytes();

   281 }

   282 

   283 bool CollectionSetChooser::should_add(HeapRegion* hr) const {

   290 void CollectionSetChooser::rebuild(WorkGang* workers, uint n_regions) {

   260 G1CollectionSetCandidates* CollectionSetChooser::build(WorkGang* workers, uint max_num_regions) {

   291   clear();

   261   uint num_workers = workers->active_workers();

   292 

   262   uint chunk_size = calculate_work_chunk_size(num_workers, max_num_regions);

   293   uint n_workers = workers->active_workers();

   263 

   294 

   264   G1BuildCandidateRegionsTask cl(max_num_regions, chunk_size, num_workers);

   295   uint chunk_size = calculate_parallel_work_chunk_size(n_workers, n_regions);

   265   workers->run_task(&cl, num_workers);

   296   prepare_for_par_region_addition(n_workers, n_regions, chunk_size);

   266 

   297 

   267   G1CollectionSetCandidates* result = cl.get_sorted_candidates();

   298   ParKnownGarbageTask par_known_garbage_task(this, chunk_size, n_workers);

   268   result->verify();

   299   workers->run_task(&par_known_garbage_task);

   269   return result;

   300 

   270 }

   301   sort_regions();

   302 }