1 /*
   2  * Copyright (c) 2001, 2019, 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 "precompiled.hpp"
  26 #include "gc/g1/collectionSetChooser.hpp"
  27 #include "gc/g1/g1CollectedHeap.inline.hpp"
  28 #include "gc/g1/heapRegionRemSet.hpp"
  29 #include "gc/shared/space.inline.hpp"
  30 #include "runtime/atomic.hpp"
  31 #include "utilities/quickSort.hpp"
  32 
  33 // Order regions according to GC efficiency. This will cause regions with a lot
  34 // of live objects and large remembered sets to end up at the end of the array.
  35 // Given that we might skip collecting the last few old regions, if after a few
  36 // mixed GCs the remaining have reclaimable bytes under a certain threshold, the
  37 // hope is that the ones we'll skip are ones with both large remembered sets and
  38 // a lot of live objects, not the ones with just a lot of live objects if we
  39 // ordered according to the amount of reclaimable bytes per region.
  40 static int order_regions(HeapRegion* hr1, HeapRegion* hr2) {
  41   // Make sure that NULL entries are moved to the end.
  42   if (hr1 == NULL) {
  43     if (hr2 == NULL) {
  44       return 0;
  45     } else {
  46       return 1;
  47     }
  48   } else if (hr2 == NULL) {
  49     return -1;
  50   }
  51 
  52   double gc_eff1 = hr1->gc_efficiency();
  53   double gc_eff2 = hr2->gc_efficiency();
  54 
  55   if (gc_eff1 > gc_eff2) {
  56     return -1;
  57   } if (gc_eff1 < gc_eff2) {
  58     return 1;
  59   } else {
  60     return 0;
  61   }
  62 }
  63 
  64 // Determine collection set candidates: For all regions determine whether they
  65 // should be a collection set candidates, calculate their efficiency, sort and
  66 // return them as G1CollectionSetCandidates instance.
  67 // Threads calculate the GC efficiency of the regions they get to process, and
  68 // put them into some work area unsorted. At the end the array is sorted and
  69 // copied into the G1CollectionSetCandidates instance; the caller will be the new
  70 // owner of this object.
  71 class G1BuildCandidateRegionsTask : public AbstractGangTask {
  72 
  73   // Work area for building the set of collection set candidates. Contains references
  74   // to heap regions with their GC efficiencies calculated. To reduce contention
  75   // on claiming array elements, worker threads claim parts of this array in chunks;
  76   // Array elements may be NULL as threads might not get enough regions to fill
  77   // up their chunks completely.
  78   // Final sorting will remove them.
  79   class G1BuildCandidateArray : public StackObj {
  80 
  81     uint const _max_size;
  82     uint const _chunk_size;
  83 
  84     HeapRegion** _data;
  85 
  86     uint volatile _cur_claim_idx;
  87 
  88     // Calculates the maximum array size that will be used.
  89     static uint required_array_size(uint num_regions, uint num_workers, uint chunk_size) {
  90       uint const max_waste = num_workers * chunk_size;
  91       // The array should be aligned with respect to chunk_size.
  92       uint const aligned_num_regions = ((num_regions + chunk_size - 1) / chunk_size) * chunk_size;
  93 
  94       return aligned_num_regions + max_waste;
  95     }
  96 
  97   public:
  98     G1BuildCandidateArray(uint max_num_regions, uint num_workers, uint chunk_size) :
  99       _max_size(required_array_size(max_num_regions, num_workers, chunk_size)),
 100       _chunk_size(chunk_size),
 101       _data(NEW_C_HEAP_ARRAY(HeapRegion*, _max_size, mtGC)),
 102       _cur_claim_idx(0) {
 103       for (uint i = 0; i < _max_size; i++) {
 104         _data[i] = NULL;
 105       }
 106     }
 107 
 108     ~G1BuildCandidateArray() {
 109       FREE_C_HEAP_ARRAY(HeapRegion*, _data);
 110     }
 111 
 112     // Claim a new chunk, returning its bounds [from, to[.
 113     void claim_chunk(uint& from, uint& to) {
 114       uint result = Atomic::add(_chunk_size, &_cur_claim_idx);
 115       assert(_max_size > result - 1,
 116              "Array too small, is %u should be %u with chunk size %u.",
 117              _max_size, result, _chunk_size);
 118       from = result - _chunk_size;
 119       to = result;
 120     }
 121 
 122     // Set element in array.
 123     void set(uint idx, HeapRegion* hr) {
 124       assert(idx < _max_size, "Index %u out of bounds %u", idx, _max_size);
 125       assert(_data[idx] == NULL, "Value must not have been set.");
 126       _data[idx] = hr;
 127     }
 128 
 129     void sort_and_copy_into(HeapRegion** dest, uint num_regions) {
 130       if (_cur_claim_idx == 0) {
 131         return;
 132       }
 133       for (uint i = _cur_claim_idx; i < _max_size; i++) {
 134         assert(_data[i] == NULL, "must be");
 135       }
 136       QuickSort::sort(_data, _cur_claim_idx, order_regions, true);
 137       for (uint i = num_regions; i < _max_size; i++) {
 138         assert(_data[i] == NULL, "must be");
 139       }
 140       for (uint i = 0; i < num_regions; i++) {
 141         dest[i] = _data[i];
 142       }
 143     }
 144   };
 145 
 146   // Per-region closure. In addition to determining whether a region should be
 147   // added to the candidates, and calculating those regions' gc efficiencies, also
 148   // gather additional statistics.
 149   class G1BuildCandidateRegionsClosure : public HeapRegionClosure {
 150     G1BuildCandidateArray* _array;
 151 
 152     uint _cur_chunk_idx;
 153     uint _cur_chunk_end;
 154 
 155     uint _regions_added;
 156     size_t _reclaimable_bytes_added;
 157 
 158     void add_region(HeapRegion* hr) {
 159       if (_cur_chunk_idx == _cur_chunk_end) {
 160         _array->claim_chunk(_cur_chunk_idx, _cur_chunk_end);
 161       }
 162       assert(_cur_chunk_idx < _cur_chunk_end, "Must be");
 163 
 164       hr->calc_gc_efficiency();
 165       _array->set(_cur_chunk_idx, hr);
 166 
 167       _cur_chunk_idx++;
 168 
 169       _regions_added++;
 170       _reclaimable_bytes_added += hr->reclaimable_bytes();
 171     }
 172 
 173     bool should_add(HeapRegion* hr) { return CollectionSetChooser::should_add(hr); }
 174 
 175   public:
 176     G1BuildCandidateRegionsClosure(G1BuildCandidateArray* array) :
 177       _array(array),
 178       _cur_chunk_idx(0),
 179       _cur_chunk_end(0),
 180       _regions_added(0),
 181       _reclaimable_bytes_added(0) { }
 182 
 183     bool do_heap_region(HeapRegion* r) {
 184       // We will skip any region that's currently used as an old GC
 185       // alloc region (we should not consider those for collection
 186       // before we fill them up).
 187       if (should_add(r) && !G1CollectedHeap::heap()->is_old_gc_alloc_region(r)) {
 188         add_region(r);
 189       } else if (r->is_old()) {
 190         // Keep remembered sets for humongous regions, otherwise clean out remembered
 191         // sets for old regions.
 192         r->rem_set()->clear(true /* only_cardset */);
 193       } else {
 194         assert(r->is_archive() || !r->is_old() || !r->rem_set()->is_tracked(),
 195                "Missed to clear unused remembered set of region %u (%s) that is %s",
 196                r->hrm_index(), r->get_type_str(), r->rem_set()->get_state_str());
 197       }
 198       return false;
 199     }
 200 
 201     uint regions_added() const { return _regions_added; }
 202     size_t reclaimable_bytes_added() const { return _reclaimable_bytes_added; }
 203   };
 204 
 205   G1CollectedHeap* _g1h;
 206   HeapRegionClaimer _hrclaimer;
 207 
 208   uint volatile _num_regions_added;
 209   size_t volatile _reclaimable_bytes_added;
 210 
 211   G1BuildCandidateArray _result;
 212 
 213   void update_totals(uint num_regions, size_t reclaimable_bytes) {
 214     if (num_regions > 0) {
 215       assert(reclaimable_bytes > 0, "invariant");
 216       Atomic::add(num_regions, &_num_regions_added);
 217       Atomic::add(reclaimable_bytes, &_reclaimable_bytes_added);
 218     } else {
 219       assert(reclaimable_bytes == 0, "invariant");
 220     }
 221   }
 222 
 223 public:
 224   G1BuildCandidateRegionsTask(uint max_num_regions, uint chunk_size, uint num_workers) :
 225     AbstractGangTask("G1 Build Candidate Regions"),
 226     _g1h(G1CollectedHeap::heap()),
 227     _hrclaimer(num_workers),
 228     _num_regions_added(0),
 229     _reclaimable_bytes_added(0),
 230     _result(max_num_regions, chunk_size, num_workers) { }
 231 
 232   void work(uint worker_id) {
 233     G1BuildCandidateRegionsClosure cl(&_result);
 234     _g1h->heap_region_par_iterate_from_worker_offset(&cl, &_hrclaimer, worker_id);
 235     update_totals(cl.regions_added(), cl.reclaimable_bytes_added());
 236   }
 237 
 238   G1CollectionSetCandidates* get_sorted_candidates() {
 239     HeapRegion** regions = NEW_C_HEAP_ARRAY(HeapRegion*, _num_regions_added, mtGC);
 240     _result.sort_and_copy_into(regions, _num_regions_added);
 241     return new G1CollectionSetCandidates(regions,
 242                                          _num_regions_added,
 243                                          _reclaimable_bytes_added);
 244   }
 245 };
 246 
 247 uint CollectionSetChooser::calculate_work_chunk_size(uint num_workers, uint num_regions) {
 248   assert(num_workers > 0, "Active gc workers should be greater than 0");
 249   return MAX2(num_regions / num_workers, 1U);
 250 }
 251 
 252 bool CollectionSetChooser::should_add(HeapRegion* hr) {
 253   return !hr->is_young() &&
 254          !hr->is_pinned() &&
 255          region_occupancy_low_enough_for_evac(hr->live_bytes()) &&
 256          hr->rem_set()->is_complete();
 257 }
 258 
 259 G1CollectionSetCandidates* CollectionSetChooser::build(WorkGang* workers, uint max_num_regions) {
 260   uint num_workers = workers->active_workers();
 261   uint chunk_size = calculate_work_chunk_size(num_workers, max_num_regions);
 262 
 263   G1BuildCandidateRegionsTask cl(max_num_regions, chunk_size, num_workers);
 264   workers->run_task(&cl, num_workers);
 265 
 266   G1CollectionSetCandidates* result = cl.get_sorted_candidates();
 267   result->verify();
 268   return result;
 269 }