src/hotspot/share/gc/g1/g1CollectionSetChooser.cpp - toolchain/jdk/jdk21 - Git at Google

 /*
  * Copyright (c) 2001, 2023, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  *
  */

 #include "precompiled.hpp"
 #include "gc/g1/g1CollectedHeap.inline.hpp"
 #include "gc/g1/g1CollectionSetCandidates.hpp"
 #include "gc/g1/g1CollectionSetChooser.hpp"
 #include "gc/g1/heapRegionRemSet.inline.hpp"
 #include "gc/shared/space.inline.hpp"
 #include "runtime/atomic.hpp"
 #include "utilities/quickSort.hpp"

 // Determine collection set candidates: For all regions determine whether they
 // should be a collection set candidates, calculate their efficiency, sort and
 // return them as G1CollectionSetCandidates instance.
 // Threads calculate the GC efficiency of the regions they get to process, and
 // put them into some work area unsorted. At the end the array is sorted and
 // copied into the G1CollectionSetCandidates instance; the caller will be the new
 // owner of this object.
 class G1BuildCandidateRegionsTask : public WorkerTask {

   using CandidateInfo = G1CollectionCandidateList::CandidateInfo;

   // Work area for building the set of collection set candidates. Contains references
   // to heap regions with their GC efficiencies calculated. To reduce contention
   // on claiming array elements, worker threads claim parts of this array in chunks;
   // Array elements may be null as threads might not get enough regions to fill
   // up their chunks completely.
   // Final sorting will remove them.
   class G1BuildCandidateArray : public StackObj {

     uint const _max_size;
     uint const _chunk_size;

     CandidateInfo* _data;

     uint volatile _cur_claim_idx;

     // Calculates the maximum array size that will be used.
     static uint required_array_size(uint num_regions, uint chunk_size, uint num_workers) {
       uint const max_waste = num_workers * chunk_size;
       // The array should be aligned with respect to chunk_size.
       uint const aligned_num_regions = ((num_regions + chunk_size - 1) / chunk_size) * chunk_size;

       return aligned_num_regions + max_waste;
     }

   public:
     G1BuildCandidateArray(uint max_num_regions, uint chunk_size, uint num_workers) :
       _max_size(required_array_size(max_num_regions, chunk_size, num_workers)),
       _chunk_size(chunk_size),
       _data(NEW_C_HEAP_ARRAY(CandidateInfo, _max_size, mtGC)),
       _cur_claim_idx(0) {
       for (uint i = 0; i < _max_size; i++) {
         _data[i] = CandidateInfo();
       }
     }

     ~G1BuildCandidateArray() {
       FREE_C_HEAP_ARRAY(CandidateInfo, _data);
     }

     // Claim a new chunk, returning its bounds [from, to[.
     void claim_chunk(uint& from, uint& to) {
       uint result = Atomic::add(&_cur_claim_idx, _chunk_size);
       assert(_max_size > result - 1,
              "Array too small, is %u should be %u with chunk size %u.",
              _max_size, result, _chunk_size);
       from = result - _chunk_size;
       to = result;
     }

     // Set element in array.
     void set(uint idx, HeapRegion* hr) {
       assert(idx < _max_size, "Index %u out of bounds %u", idx, _max_size);
       assert(_data[idx]._r == nullptr, "Value must not have been set.");
       _data[idx] = CandidateInfo(hr, hr->calc_gc_efficiency());
     }

     void sort_by_efficiency() {
       if (_cur_claim_idx == 0) {
         return;
       }
       for (uint i = _cur_claim_idx; i < _max_size; i++) {
         assert(_data[i]._r == nullptr, "must be");
       }
       qsort(_data, _cur_claim_idx, sizeof(_data[0]), (_sort_Fn)G1CollectionCandidateList::compare);
       for (uint i = _cur_claim_idx; i < _max_size; i++) {
         assert(_data[i]._r == nullptr, "must be");
       }
     }

     CandidateInfo* array() const { return _data; }
   };

   // Per-region closure. In addition to determining whether a region should be
   // added to the candidates, and calculating those regions' gc efficiencies, also
   // gather additional statistics.
   class G1BuildCandidateRegionsClosure : public HeapRegionClosure {
     G1BuildCandidateArray* _array;

     uint _cur_chunk_idx;
     uint _cur_chunk_end;

     uint _regions_added;

     void add_region(HeapRegion* hr) {
       if (_cur_chunk_idx == _cur_chunk_end) {
         _array->claim_chunk(_cur_chunk_idx, _cur_chunk_end);
       }
       assert(_cur_chunk_idx < _cur_chunk_end, "Must be");

       _array->set(_cur_chunk_idx, hr);

       _cur_chunk_idx++;

       _regions_added++;
     }

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

   public:
     G1BuildCandidateRegionsClosure(G1BuildCandidateArray* array) :
       _array(array),
       _cur_chunk_idx(0),
       _cur_chunk_end(0),
       _regions_added(0) { }

     bool do_heap_region(HeapRegion* r) {
       // We will skip any region that's currently used as an old GC
       // alloc region (we should not consider those for collection
       // before we fill them up).
       if (should_add(r) && !G1CollectedHeap::heap()->is_old_gc_alloc_region(r)) {
         add_region(r);
       } else if (r->is_old()) {
         // Keep remembered sets for humongous regions, otherwise clean them out.
         r->rem_set()->clear(true /* only_cardset */);
       } else {
         assert(!r->is_old() || !r->rem_set()->is_tracked(),
                "Missed to clear unused remembered set of region %u (%s) that is %s",
                r->hrm_index(), r->get_type_str(), r->rem_set()->get_state_str());
       }
       return false;
     }

     uint regions_added() const { return _regions_added; }
   };

   G1CollectedHeap* _g1h;
   HeapRegionClaimer _hrclaimer;

   uint volatile _num_regions_added;

   G1BuildCandidateArray _result;

   void update_totals(uint num_regions) {
     if (num_regions > 0) {
       Atomic::add(&_num_regions_added, num_regions);
     }
   }

   // Early prune (remove) regions meeting the G1HeapWastePercent criteria. That
   // is, either until only the minimum amount of old collection set regions are
   // available (for forward progress in evacuation) or the waste accumulated by the
   // removed regions is above the maximum allowed waste.
   // Updates number of candidates and reclaimable bytes given.
   void prune(CandidateInfo* data) {
     G1Policy* p = G1CollectedHeap::heap()->policy();

     uint num_candidates = Atomic::load(&_num_regions_added);

     uint min_old_cset_length = p->calc_min_old_cset_length(num_candidates);
     uint num_pruned = 0;
     size_t wasted_bytes = 0;

     if (min_old_cset_length >= num_candidates) {
       // We take all of the candidate regions to provide some forward progress.
       return;
     }

     size_t allowed_waste = p->allowed_waste_in_collection_set();
     uint max_to_prune = num_candidates - min_old_cset_length;

     while (true) {
       HeapRegion* r = data[num_candidates - num_pruned - 1]._r;
       size_t const reclaimable = r->reclaimable_bytes();
       if (num_pruned >= max_to_prune ||
           wasted_bytes + reclaimable > allowed_waste) {
         break;
       }
       r->rem_set()->clear(true /* cardset_only */);

       wasted_bytes += reclaimable;
       num_pruned++;
     }

     log_debug(gc, ergo, cset)("Pruned %u regions out of %u, leaving " SIZE_FORMAT " bytes waste (allowed " SIZE_FORMAT ")",
                               num_pruned,
                               num_candidates,
                               wasted_bytes,
                               allowed_waste);

     Atomic::sub(&_num_regions_added, num_pruned, memory_order_relaxed);
   }

 public:
   G1BuildCandidateRegionsTask(uint max_num_regions, uint chunk_size, uint num_workers) :
     WorkerTask("G1 Build Candidate Regions"),
     _g1h(G1CollectedHeap::heap()),
     _hrclaimer(num_workers),
     _num_regions_added(0),
     _result(max_num_regions, chunk_size, num_workers) { }

   void work(uint worker_id) {
     G1BuildCandidateRegionsClosure cl(&_result);
     _g1h->heap_region_par_iterate_from_worker_offset(&cl, &_hrclaimer, worker_id);
     update_totals(cl.regions_added());
   }

   void sort_and_prune_into(G1CollectionSetCandidates* candidates) {
     _result.sort_by_efficiency();
     prune(_result.array());
     candidates->set_candidates_from_marking(_result.array(),
                                             _num_regions_added);
   }
 };

 uint G1CollectionSetChooser::calculate_work_chunk_size(uint num_workers, uint num_regions) {
   assert(num_workers > 0, "Active gc workers should be greater than 0");
   return MAX2(num_regions / num_workers, 1U);
 }

 bool G1CollectionSetChooser::should_add(HeapRegion* hr) {
   return !hr->is_young() &&
          !hr->is_humongous() &&
          region_occupancy_low_enough_for_evac(hr->live_bytes()) &&
          hr->rem_set()->is_complete();
 }

 void G1CollectionSetChooser::build(WorkerThreads* workers, uint max_num_regions, G1CollectionSetCandidates* candidates) {
   uint num_workers = workers->active_workers();
   uint chunk_size = calculate_work_chunk_size(num_workers, max_num_regions);

   G1BuildCandidateRegionsTask cl(max_num_regions, chunk_size, num_workers);
   workers->run_task(&cl, num_workers);

   cl.sort_and_prune_into(candidates);
   candidates->verify();
 }
	/*
	* Copyright (c) 2001, 2023, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*
	*/

	#include "precompiled.hpp"
	#include "gc/g1/g1CollectedHeap.inline.hpp"
	#include "gc/g1/g1CollectionSetCandidates.hpp"
	#include "gc/g1/g1CollectionSetChooser.hpp"
	#include "gc/g1/heapRegionRemSet.inline.hpp"
	#include "gc/shared/space.inline.hpp"
	#include "runtime/atomic.hpp"
	#include "utilities/quickSort.hpp"

	// Determine collection set candidates: For all regions determine whether they
	// should be a collection set candidates, calculate their efficiency, sort and
	// return them as G1CollectionSetCandidates instance.
	// Threads calculate the GC efficiency of the regions they get to process, and
	// put them into some work area unsorted. At the end the array is sorted and
	// copied into the G1CollectionSetCandidates instance; the caller will be the new
	// owner of this object.
	class G1BuildCandidateRegionsTask : public WorkerTask {

	using CandidateInfo = G1CollectionCandidateList::CandidateInfo;

	// Work area for building the set of collection set candidates. Contains references
	// to heap regions with their GC efficiencies calculated. To reduce contention
	// on claiming array elements, worker threads claim parts of this array in chunks;
	// Array elements may be null as threads might not get enough regions to fill
	// up their chunks completely.
	// Final sorting will remove them.
	class G1BuildCandidateArray : public StackObj {

	uint const _max_size;
	uint const _chunk_size;

	CandidateInfo* _data;

	uint volatile _cur_claim_idx;

	// Calculates the maximum array size that will be used.
	static uint required_array_size(uint num_regions, uint chunk_size, uint num_workers) {
	uint const max_waste = num_workers * chunk_size;
	// The array should be aligned with respect to chunk_size.
	uint const aligned_num_regions = ((num_regions + chunk_size - 1) / chunk_size) * chunk_size;

	return aligned_num_regions + max_waste;
	}

	public:
	G1BuildCandidateArray(uint max_num_regions, uint chunk_size, uint num_workers) :
	_max_size(required_array_size(max_num_regions, chunk_size, num_workers)),
	_chunk_size(chunk_size),
	_data(NEW_C_HEAP_ARRAY(CandidateInfo, _max_size, mtGC)),
	_cur_claim_idx(0) {
	for (uint i = 0; i < _max_size; i++) {
	_data[i] = CandidateInfo();
	}
	}

	~G1BuildCandidateArray() {
	FREE_C_HEAP_ARRAY(CandidateInfo, _data);
	}

	// Claim a new chunk, returning its bounds [from, to[.
	void claim_chunk(uint& from, uint& to) {
	uint result = Atomic::add(&_cur_claim_idx, _chunk_size);
	assert(_max_size > result - 1,
	"Array too small, is %u should be %u with chunk size %u.",
	_max_size, result, _chunk_size);
	from = result - _chunk_size;
	to = result;
	}

	// Set element in array.
	void set(uint idx, HeapRegion* hr) {
	assert(idx < _max_size, "Index %u out of bounds %u", idx, _max_size);
	assert(_data[idx]._r == nullptr, "Value must not have been set.");
	_data[idx] = CandidateInfo(hr, hr->calc_gc_efficiency());
	}

	void sort_by_efficiency() {
	if (_cur_claim_idx == 0) {
	return;
	}
	for (uint i = _cur_claim_idx; i < _max_size; i++) {
	assert(_data[i]._r == nullptr, "must be");
	}
	qsort(_data, _cur_claim_idx, sizeof(_data[0]), (_sort_Fn)G1CollectionCandidateList::compare);
	for (uint i = _cur_claim_idx; i < _max_size; i++) {
	assert(_data[i]._r == nullptr, "must be");
	}
	}

	CandidateInfo* array() const { return _data; }
	};

	// Per-region closure. In addition to determining whether a region should be
	// added to the candidates, and calculating those regions' gc efficiencies, also
	// gather additional statistics.
	class G1BuildCandidateRegionsClosure : public HeapRegionClosure {
	G1BuildCandidateArray* _array;

	uint _cur_chunk_idx;
	uint _cur_chunk_end;

	uint _regions_added;

	void add_region(HeapRegion* hr) {
	if (_cur_chunk_idx == _cur_chunk_end) {
	_array->claim_chunk(_cur_chunk_idx, _cur_chunk_end);
	}
	assert(_cur_chunk_idx < _cur_chunk_end, "Must be");

	_array->set(_cur_chunk_idx, hr);

	_cur_chunk_idx++;

	_regions_added++;
	}

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

	public:
	G1BuildCandidateRegionsClosure(G1BuildCandidateArray* array) :
	_array(array),
	_cur_chunk_idx(0),
	_cur_chunk_end(0),
	_regions_added(0) { }

	bool do_heap_region(HeapRegion* r) {
	// We will skip any region that's currently used as an old GC
	// alloc region (we should not consider those for collection
	// before we fill them up).
	if (should_add(r) && !G1CollectedHeap::heap()->is_old_gc_alloc_region(r)) {
	add_region(r);
	} else if (r->is_old()) {
	// Keep remembered sets for humongous regions, otherwise clean them out.
	r->rem_set()->clear(true /* only_cardset */);
	} else {
	assert(!r->is_old() \|\| !r->rem_set()->is_tracked(),
	"Missed to clear unused remembered set of region %u (%s) that is %s",
	r->hrm_index(), r->get_type_str(), r->rem_set()->get_state_str());
	}
	return false;
	}

	uint regions_added() const { return _regions_added; }
	};

	G1CollectedHeap* _g1h;
	HeapRegionClaimer _hrclaimer;

	uint volatile _num_regions_added;

	G1BuildCandidateArray _result;

	void update_totals(uint num_regions) {
	if (num_regions > 0) {
	Atomic::add(&_num_regions_added, num_regions);
	}
	}

	// Early prune (remove) regions meeting the G1HeapWastePercent criteria. That
	// is, either until only the minimum amount of old collection set regions are
	// available (for forward progress in evacuation) or the waste accumulated by the
	// removed regions is above the maximum allowed waste.
	// Updates number of candidates and reclaimable bytes given.
	void prune(CandidateInfo* data) {
	G1Policy* p = G1CollectedHeap::heap()->policy();

	uint num_candidates = Atomic::load(&_num_regions_added);

	uint min_old_cset_length = p->calc_min_old_cset_length(num_candidates);
	uint num_pruned = 0;
	size_t wasted_bytes = 0;

	if (min_old_cset_length >= num_candidates) {
	// We take all of the candidate regions to provide some forward progress.
	return;
	}

	size_t allowed_waste = p->allowed_waste_in_collection_set();
	uint max_to_prune = num_candidates - min_old_cset_length;

	while (true) {
	HeapRegion* r = data[num_candidates - num_pruned - 1]._r;
	size_t const reclaimable = r->reclaimable_bytes();
	if (num_pruned >= max_to_prune \|\|
	wasted_bytes + reclaimable > allowed_waste) {
	break;
	}
	r->rem_set()->clear(true /* cardset_only */);

	wasted_bytes += reclaimable;
	num_pruned++;
	}

	log_debug(gc, ergo, cset)("Pruned %u regions out of %u, leaving " SIZE_FORMAT " bytes waste (allowed " SIZE_FORMAT ")",
	num_pruned,
	num_candidates,
	wasted_bytes,
	allowed_waste);

	Atomic::sub(&_num_regions_added, num_pruned, memory_order_relaxed);
	}

	public:
	G1BuildCandidateRegionsTask(uint max_num_regions, uint chunk_size, uint num_workers) :
	WorkerTask("G1 Build Candidate Regions"),
	_g1h(G1CollectedHeap::heap()),
	_hrclaimer(num_workers),
	_num_regions_added(0),
	_result(max_num_regions, chunk_size, num_workers) { }

	void work(uint worker_id) {
	G1BuildCandidateRegionsClosure cl(&_result);
	_g1h->heap_region_par_iterate_from_worker_offset(&cl, &_hrclaimer, worker_id);
	update_totals(cl.regions_added());
	}

	void sort_and_prune_into(G1CollectionSetCandidates* candidates) {
	_result.sort_by_efficiency();
	prune(_result.array());
	candidates->set_candidates_from_marking(_result.array(),
	_num_regions_added);
	}
	};

	uint G1CollectionSetChooser::calculate_work_chunk_size(uint num_workers, uint num_regions) {
	assert(num_workers > 0, "Active gc workers should be greater than 0");
	return MAX2(num_regions / num_workers, 1U);
	}

	bool G1CollectionSetChooser::should_add(HeapRegion* hr) {
	return !hr->is_young() &&
	!hr->is_humongous() &&
	region_occupancy_low_enough_for_evac(hr->live_bytes()) &&
	hr->rem_set()->is_complete();
	}

	void G1CollectionSetChooser::build(WorkerThreads* workers, uint max_num_regions, G1CollectionSetCandidates* candidates) {
	uint num_workers = workers->active_workers();
	uint chunk_size = calculate_work_chunk_size(num_workers, max_num_regions);

	G1BuildCandidateRegionsTask cl(max_num_regions, chunk_size, num_workers);
	workers->run_task(&cl, num_workers);

	cl.sort_and_prune_into(candidates);
	candidates->verify();
	}