< prev index next >

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp

Print this page


  1 /*
  2  * Copyright (c) 2016, 2019, Red Hat, Inc. All rights reserved.
  3  * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
  4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  5  *
  6  * This code is free software; you can redistribute it and/or modify it
  7  * under the terms of the GNU General Public License version 2 only, as
  8  * published by the Free Software Foundation.
  9  *
 10  * This code is distributed in the hope that it will be useful, but WITHOUT
 11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 13  * version 2 for more details (a copy is included in the LICENSE file that
 14  * accompanied this code).
 15  *
 16  * You should have received a copy of the GNU General Public License version
 17  * 2 along with this work; if not, write to the Free Software Foundation,
 18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 19  *
 20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 21  * or visit www.oracle.com if you need additional information or have any
 22  * questions.
 23  *
 24  */
 25 
 26 #ifndef SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
 27 #define SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
 28 
 29 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
 30 #include "gc/shenandoah/shenandoahHeap.hpp"
 31 #include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
 32 
 33 // Each ShenandoahHeapRegion is associated with a ShenandoahFreeSetPartitionId.
 34 enum class ShenandoahFreeSetPartitionId : uint8_t {
 35   Mutator,                      // Region is in the Mutator free set: available memory is available to mutators.
 36   Collector,                    // Region is in the Collector free set: available memory is reserved for evacuations.


 37   NotFree                       // Region is in no free set: it has no available memory
 38 };
 39 
 40 // We do not maintain counts, capacity, or used for regions that are not free.  Informally, if a region is NotFree, it is
 41 // in no partition.  NumPartitions represents the size of an array that may be indexed by Mutator or Collector.
 42 #define NumPartitions           (ShenandoahFreeSetPartitionId::NotFree)
 43 #define IntNumPartitions     int(ShenandoahFreeSetPartitionId::NotFree)
 44 #define UIntNumPartitions   uint(ShenandoahFreeSetPartitionId::NotFree)
 45 
 46 // ShenandoahRegionPartitions provides an abstraction to help organize the implementation of ShenandoahFreeSet.  This
 47 // class implements partitioning of regions into distinct sets.  Each ShenandoahHeapRegion is either in the Mutator free set,
 48 // the Collector free set, or in neither free set (NotFree).  When we speak of a "free partition", we mean partitions that
 49 // for which the ShenandoahFreeSetPartitionId is not equal to NotFree.
 50 class ShenandoahRegionPartitions {
 51 
 52 private:
 53   const ssize_t _max;           // The maximum number of heap regions
 54   const size_t _region_size_bytes;
 55   const ShenandoahFreeSet* _free_set;
 56   // For each partition, we maintain a bitmap of which regions are affiliated with his partition.

 63   ssize_t _leftmosts[UIntNumPartitions];
 64   ssize_t _rightmosts[UIntNumPartitions];
 65 
 66   // Allocation for humongous objects needs to find regions that are entirely empty.  For each partion p, _leftmosts_empty[p]
 67   // represents the first region belonging to this partition that is completely empty and _rightmosts_empty[p] represents the
 68   // last region that is completely empty.  If there is no completely empty region in this partition, this is represented
 69   // by the canonical [_max, -1].
 70   ssize_t _leftmosts_empty[UIntNumPartitions];
 71   ssize_t _rightmosts_empty[UIntNumPartitions];
 72 
 73   // For each partition p, _capacity[p] represents the total amount of memory within the partition at the time
 74   // of the most recent rebuild, _used[p] represents the total amount of memory that has been allocated within this
 75   // partition (either already allocated as of the rebuild, or allocated since the rebuild).  _capacity[p] and _used[p]
 76   // are denoted in bytes.  Note that some regions that had been assigned to a particular partition at rebuild time
 77   // may have been retired following the rebuild.  The tallies for these regions are still reflected in _capacity[p]
 78   // and _used[p], even though the region may have been removed from the free set.
 79   size_t _capacity[UIntNumPartitions];
 80   size_t _used[UIntNumPartitions];
 81   size_t _region_counts[UIntNumPartitions];
 82 




 83   // Shrink the intervals associated with partition when region idx is removed from this free set
 84   inline void shrink_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, ssize_t idx);
 85 
 86   // Shrink the intervals associated with partition when regions low_idx through high_idx inclusive are removed from this free set
 87   inline void shrink_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId partition,
 88                                                                 ssize_t low_idx, ssize_t high_idx);
 89   inline void expand_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, ssize_t idx, size_t capacity);
 90 





 91 #ifndef PRODUCT
 92   void dump_bitmap_row(ssize_t region_idx) const;
 93   void dump_bitmap_range(ssize_t start_region_idx, ssize_t end_region_idx) const;
 94   void dump_bitmap() const;
 95 #endif
 96 public:
 97   ShenandoahRegionPartitions(size_t max_regions, ShenandoahFreeSet* free_set);
 98   ~ShenandoahRegionPartitions() {}
 99 
100   // Remove all regions from all partitions and reset all bounds
101   void make_all_regions_unavailable();
102 
103   // Set the partition id for a particular region without adjusting interval bounds or usage/capacity tallies
104   inline void raw_assign_membership(size_t idx, ShenandoahFreeSetPartitionId p) {
105     _membership[int(p)].set_bit(idx);
106   }
107 
108   // Set the Mutator intervals, usage, and capacity according to arguments.  Reset the Collector intervals, used, capacity
109   // to represent empty Collector free set.  We use this at the end of rebuild_free_set() to avoid the overhead of making
110   // many redundant incremental adjustments to the mutator intervals as the free set is being rebuilt.
111   void establish_mutator_intervals(ssize_t mutator_leftmost, ssize_t mutator_rightmost,
112                                    ssize_t mutator_leftmost_empty, ssize_t mutator_rightmost_empty,
113                                    size_t mutator_region_count, size_t mutator_used);
114 







115   // Retire region idx from within partition, , leaving its capacity and used as part of the original free partition's totals.
116   // Requires that region idx is in in the Mutator or Collector partitions.  Hereafter, identifies this region as NotFree.
117   // Any remnant of available memory at the time of retirement is added to the original partition's total of used bytes.
118   void retire_from_partition(ShenandoahFreeSetPartitionId p, ssize_t idx, size_t used_bytes);
119 
120   // Retire all regions between low_idx and high_idx inclusive from within partition.  Requires that each region idx is
121   // in the same Mutator or Collector partition.  Hereafter, identifies each region as NotFree.   Assumes that each region
122   // is now considered fully used, since the region is presumably used to represent a humongous object.
123   void retire_range_from_partition(ShenandoahFreeSetPartitionId partition, ssize_t low_idx, ssize_t high_idx);
124 
125   // Place region idx into free set which_partition.  Requires that idx is currently NotFree.
126   void make_free(ssize_t idx, ShenandoahFreeSetPartitionId which_partition, size_t region_capacity);
127 
128   // Place region idx into free partition new_partition, adjusting used and capacity totals for the original and new partition
129   // given that available bytes can still be allocated within this region.  Requires that idx is currently not NotFree.
130   void move_from_partition_to_partition(ssize_t idx, ShenandoahFreeSetPartitionId orig_partition,
131                                         ShenandoahFreeSetPartitionId new_partition, size_t available);
132 
133   const char* partition_membership_name(ssize_t idx) const;
134 

163   inline size_t max_regions() const { return _max; }
164 
165   inline size_t region_size_bytes() const { return _region_size_bytes; };
166 
167   // The following four methods return the left-most and right-most bounds on ranges of regions representing
168   // the requested set.  The _empty variants represent bounds on the range that holds completely empty
169   // regions, which are required for humongous allocations and desired for "very large" allocations.
170   //   if the requested which_partition is empty:
171   //     leftmost() and leftmost_empty() return _max, rightmost() and rightmost_empty() return 0
172   //   otherwise, expect the following:
173   //     0 <= leftmost <= leftmost_empty <= rightmost_empty <= rightmost < _max
174   inline ssize_t leftmost(ShenandoahFreeSetPartitionId which_partition) const;
175   inline ssize_t rightmost(ShenandoahFreeSetPartitionId which_partition) const;
176   ssize_t leftmost_empty(ShenandoahFreeSetPartitionId which_partition);
177   ssize_t rightmost_empty(ShenandoahFreeSetPartitionId which_partition);
178 
179   inline bool is_empty(ShenandoahFreeSetPartitionId which_partition) const;
180 
181   inline void increase_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
182 










183   inline size_t capacity_of(ShenandoahFreeSetPartitionId which_partition) const {
184     assert (which_partition < NumPartitions, "selected free set must be valid");
185     return _capacity[int(which_partition)];
186   }
187 
188   inline size_t used_by(ShenandoahFreeSetPartitionId which_partition) const {
189     assert (which_partition < NumPartitions, "selected free set must be valid");
190     return _used[int(which_partition)];
191   }
192 
193   inline size_t available_in(ShenandoahFreeSetPartitionId which_partition) const {
194     assert (which_partition < NumPartitions, "selected free set must be valid");
195     return _capacity[int(which_partition)] - _used[int(which_partition)];
196   }
197 
198   inline void set_capacity_of(ShenandoahFreeSetPartitionId which_partition, size_t value) {
199     assert (which_partition < NumPartitions, "selected free set must be valid");
200     _capacity[int(which_partition)] = value;
201   }
202 

220   //       idx <= rightmost
221   //     }
222   //   if the set has no empty regions, leftmost_empty equals max and rightmost_empty equals 0
223   //   Otherwise (the region has empty regions):
224   //     0 <= leftmost_empty < max and 0 <= rightmost_empty < max
225   //     rightmost_empty >= leftmost_empty
226   //     for every idx that is in the set and is empty {
227   //       idx >= leftmost &&
228   //       idx <= rightmost
229   //     }
230   void assert_bounds() NOT_DEBUG_RETURN;
231 };
232 
233 // Publicly, ShenandoahFreeSet represents memory that is available to mutator threads.  The public capacity(), used(),
234 // and available() methods represent this public notion of memory that is under control of the mutator.  Separately,
235 // ShenandoahFreeSet also represents memory available to garbage collection activities for compaction purposes.
236 //
237 // The Shenandoah garbage collector evacuates live objects out of specific regions that are identified as members of the
238 // collection set (cset).
239 //
240 // The ShenandoahFreeSet endeavors to congregrate survivor objects (objects that have been evacuated at least once) at the
241 // high end of memory.  New mutator allocations are taken from the low end of memory.  Within the mutator's range of regions,
242 // humongous allocations are taken from the lowest addresses, and LAB (local allocation buffers) and regular shared allocations
243 // are taken from the higher address of the mutator's range of regions.  This approach allows longer lasting survivor regions
244 // to congregate at the top of the heap and longer lasting humongous regions to congregate at the bottom of the heap, with
245 // short-lived frequently evacuated regions occupying the middle of the heap.
246 //
247 // Mutator and garbage collection activities tend to scramble the content of regions.  Twice, during each GC pass, we rebuild
248 // the free set in an effort to restore the efficient segregation of Collector and Mutator regions:
249 //
250 //  1. At the start of evacuation, we know exactly how much memory is going to be evacuated, and this guides our
251 //     sizing of the Collector free set.
252 //
253 //  2. At the end of GC, we have reclaimed all of the memory that was spanned by the cset.  We rebuild here to make
254 //     sure there is enough memory reserved at the high end of memory to hold the objects that might need to be evacuated
255 //     during the next GC pass.
256 
257 class ShenandoahFreeSet : public CHeapObj<mtGC> {
258 private:
259   ShenandoahHeap* const _heap;
260   ShenandoahRegionPartitions _partitions;



261 
262   // Mutator allocations are biased from left-to-right or from right-to-left based on which end of mutator range
263   // is most likely to hold partially used regions.  In general, we want to finish consuming partially used
264   // regions and retire them in order to reduce the regions that must be searched for each allocation request.
265   bool _right_to_left_bias;

266 
267   // We re-evaluate the left-to-right allocation bias whenever _alloc_bias_weight is less than zero.  Each time
268   // we allocate an object, we decrement the count of this value.  Each time we re-evaluate whether to allocate
269   // from right-to-left or left-to-right, we reset the value of this counter to _InitialAllocBiasWeight.
270   ssize_t _alloc_bias_weight;
271 
272   const ssize_t _InitialAllocBiasWeight = 256;
273 
274   HeapWord* try_allocate_in(ShenandoahHeapRegion* region, ShenandoahAllocRequest& req, bool& in_new_region);
275 
276   // While holding the heap lock, allocate memory for a single object or LAB  which is to be entirely contained
277   // within a single HeapRegion as characterized by req.
278   //
279   // Precondition: req.size() <= ShenandoahHeapRegion::humongous_threshold_words().
280   HeapWord* allocate_single(ShenandoahAllocRequest& req, bool& in_new_region);
281 
282   // While holding the heap lock, allocate memory for a humongous object which spans one or more regions that
283   // were previously empty.  Regions that represent humongous objects are entirely dedicated to the humongous
284   // object.  No other objects are packed into these regions.
285   //
286   // Precondition: req.size() > ShenandoahHeapRegion::humongous_threshold_words().
287   HeapWord* allocate_contiguous(ShenandoahAllocRequest& req);
288 
289   // Change region r from the Mutator partition to the GC's Collector partition.  This requires that the region is entirely empty.


290   // Typical usage: During evacuation, the GC may find it needs more memory than had been reserved at the start of evacuation to
291   // hold evacuated objects.  If this occurs and memory is still available in the Mutator's free set, we will flip a region from
292   // the Mutator free set into the Collector free set.
293   void flip_to_gc(ShenandoahHeapRegion* r);


294   void clear_internal();
295   void try_recycle_trashed(ShenandoahHeapRegion *r);
296 
297   // Returns true iff this region is entirely available, either because it is empty() or because it has been found to represent
298   // immediate trash and we'll be able to immediately recycle it.  Note that we cannot recycle immediate trash if
299   // concurrent weak root processing is in progress.
300   inline bool can_allocate_from(ShenandoahHeapRegion *r) const;
301   inline bool can_allocate_from(size_t idx) const;
302 
303   inline bool has_alloc_capacity(ShenandoahHeapRegion *r) const;
304 
305   // This function places all regions that have allocation capacity into the mutator_partition, identifying regions
306   // that have no allocation capacity as NotFree.  Subsequently, we will move some of the mutator regions into the
307   // collector partition with the intent of packing collector memory into the highest (rightmost) addresses of the
308   // heap, with mutator memory consuming the lowest addresses of the heap.
309   void find_regions_with_alloc_capacity(size_t &cset_regions);

310 
311   // Having placed all regions that have allocation capacity into the mutator partition, move some of these regions from
312   // the mutator partition into the collector partition in order to assure that the memory available for allocations within
313   // the collector partition is at least to_reserve.
314   void reserve_regions(size_t to_reserve);
315 
316   // Overwrite arguments to represent the number of regions to be reclaimed from the cset
317   void prepare_to_rebuild(size_t &cset_regions);
318 
319   void finish_rebuild(size_t cset_regions);


320 
321 public:
322   ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions);
323 
324   // Public because ShenandoahRegionPartitions assertions require access.
325   inline size_t alloc_capacity(ShenandoahHeapRegion *r) const;
326   inline size_t alloc_capacity(size_t idx) const;
327 
328   void clear();
329   void rebuild();




































330 
331   // Move up to cset_regions number of regions from being available to the collector to being available to the mutator.
332   //
333   // Typical usage: At the end of evacuation, when the collector no longer needs the regions that had been reserved
334   // for evacuation, invoke this to make regions available for mutator allocations.
335   //
336   // Note that we plan to replenish the Collector reserve at the end of update refs, at which time all
337   // of the regions recycled from the collection set will be available.  If the very unlikely event that there
338   // are fewer regions in the collection set than remain in the collector set, we limit the transfer in order
339   // to assure that the replenished Collector reserve can be sufficiently large.
340   void move_regions_from_collector_to_mutator(size_t cset_regions);
341 
342   void recycle_trash();

343   void log_status();
344 
345   inline size_t capacity()  const { return _partitions.capacity_of(ShenandoahFreeSetPartitionId::Mutator); }
346   inline size_t used()      const { return _partitions.used_by(ShenandoahFreeSetPartitionId::Mutator);     }
347   inline size_t available() const {
348     assert(used() <= capacity(), "must use less than capacity");
349     return capacity() - used();
350   }
351 
352   HeapWord* allocate(ShenandoahAllocRequest& req, bool& in_new_region);
353   size_t unsafe_peek_free() const;
354 
355   /*
356    * Internal fragmentation metric: describes how fragmented the heap regions are.
357    *
358    * It is derived as:
359    *
360    *               sum(used[i]^2, i=0..k)
361    *   IF = 1 - ------------------------------
362    *              C * sum(used[i], i=0..k)

374    *   f) Heap has one small object per each region => IF =~ 1
375    */
376   double internal_fragmentation();
377 
378   /*
379    * External fragmentation metric: describes how fragmented the heap is.
380    *
381    * It is derived as:
382    *
383    *   EF = 1 - largest_contiguous_free / total_free
384    *
385    * For example:
386    *   a) Heap is completely empty => EF = 0
387    *   b) Heap is completely full => EF = 0
388    *   c) Heap is first-half full => EF = 1/2
389    *   d) Heap is half full, full and empty regions interleave => EF =~ 1
390    */
391   double external_fragmentation();
392 
393   void print_on(outputStream* out) const;






















394 };
395 
396 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP

  1 
  2 /*
  3  * Copyright (c) 2016, 2019, Red Hat, Inc. All rights reserved.
  4  * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
  5  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  6  *
  7  * This code is free software; you can redistribute it and/or modify it
  8  * under the terms of the GNU General Public License version 2 only, as
  9  * published by the Free Software Foundation.
 10  *
 11  * This code is distributed in the hope that it will be useful, but WITHOUT
 12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 14  * version 2 for more details (a copy is included in the LICENSE file that
 15  * accompanied this code).
 16  *
 17  * You should have received a copy of the GNU General Public License version
 18  * 2 along with this work; if not, write to the Free Software Foundation,
 19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 20  *
 21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 22  * or visit www.oracle.com if you need additional information or have any
 23  * questions.
 24  *
 25  */
 26 
 27 #ifndef SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
 28 #define SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
 29 
 30 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
 31 #include "gc/shenandoah/shenandoahHeap.hpp"
 32 #include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
 33 
 34 // Each ShenandoahHeapRegion is associated with a ShenandoahFreeSetPartitionId.
 35 enum class ShenandoahFreeSetPartitionId : uint8_t {
 36   Mutator,                      // Region is in the Mutator free set: available memory is available to mutators.
 37   Collector,                    // Region is in the Collector free set: available memory is reserved for evacuations.
 38   OldCollector,                 // Region is in the Old Collector free set:
 39                                 //    available memory is reserved for old evacuations and for promotions..
 40   NotFree                       // Region is in no free set: it has no available memory
 41 };
 42 
 43 // We do not maintain counts, capacity, or used for regions that are not free.  Informally, if a region is NotFree, it is
 44 // in no partition.  NumPartitions represents the size of an array that may be indexed by Mutator or Collector.
 45 #define NumPartitions           (ShenandoahFreeSetPartitionId::NotFree)
 46 #define IntNumPartitions     int(ShenandoahFreeSetPartitionId::NotFree)
 47 #define UIntNumPartitions   uint(ShenandoahFreeSetPartitionId::NotFree)
 48 
 49 // ShenandoahRegionPartitions provides an abstraction to help organize the implementation of ShenandoahFreeSet.  This
 50 // class implements partitioning of regions into distinct sets.  Each ShenandoahHeapRegion is either in the Mutator free set,
 51 // the Collector free set, or in neither free set (NotFree).  When we speak of a "free partition", we mean partitions that
 52 // for which the ShenandoahFreeSetPartitionId is not equal to NotFree.
 53 class ShenandoahRegionPartitions {
 54 
 55 private:
 56   const ssize_t _max;           // The maximum number of heap regions
 57   const size_t _region_size_bytes;
 58   const ShenandoahFreeSet* _free_set;
 59   // For each partition, we maintain a bitmap of which regions are affiliated with his partition.

 66   ssize_t _leftmosts[UIntNumPartitions];
 67   ssize_t _rightmosts[UIntNumPartitions];
 68 
 69   // Allocation for humongous objects needs to find regions that are entirely empty.  For each partion p, _leftmosts_empty[p]
 70   // represents the first region belonging to this partition that is completely empty and _rightmosts_empty[p] represents the
 71   // last region that is completely empty.  If there is no completely empty region in this partition, this is represented
 72   // by the canonical [_max, -1].
 73   ssize_t _leftmosts_empty[UIntNumPartitions];
 74   ssize_t _rightmosts_empty[UIntNumPartitions];
 75 
 76   // For each partition p, _capacity[p] represents the total amount of memory within the partition at the time
 77   // of the most recent rebuild, _used[p] represents the total amount of memory that has been allocated within this
 78   // partition (either already allocated as of the rebuild, or allocated since the rebuild).  _capacity[p] and _used[p]
 79   // are denoted in bytes.  Note that some regions that had been assigned to a particular partition at rebuild time
 80   // may have been retired following the rebuild.  The tallies for these regions are still reflected in _capacity[p]
 81   // and _used[p], even though the region may have been removed from the free set.
 82   size_t _capacity[UIntNumPartitions];
 83   size_t _used[UIntNumPartitions];
 84   size_t _region_counts[UIntNumPartitions];
 85 
 86   // For each partition p, _left_to_right_bias is true iff allocations are normally made from lower indexed regions
 87   // before higher indexed regions.
 88   bool _left_to_right_bias[UIntNumPartitions];
 89 
 90   // Shrink the intervals associated with partition when region idx is removed from this free set
 91   inline void shrink_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, ssize_t idx);
 92 
 93   // Shrink the intervals associated with partition when regions low_idx through high_idx inclusive are removed from this free set
 94   inline void shrink_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId partition,
 95                                                                 ssize_t low_idx, ssize_t high_idx);
 96   inline void expand_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, ssize_t idx, size_t capacity);
 97 
 98   inline bool is_mutator_partition(ShenandoahFreeSetPartitionId p);
 99   inline bool is_young_collector_partition(ShenandoahFreeSetPartitionId p);
100   inline bool is_old_collector_partition(ShenandoahFreeSetPartitionId p);
101   inline bool available_implies_empty(size_t available);
102 
103 #ifndef PRODUCT
104   void dump_bitmap_row(ssize_t region_idx) const;
105   void dump_bitmap_range(ssize_t start_region_idx, ssize_t end_region_idx) const;
106   void dump_bitmap() const;
107 #endif
108 public:
109   ShenandoahRegionPartitions(size_t max_regions, ShenandoahFreeSet* free_set);
110   ~ShenandoahRegionPartitions() {}
111 
112   // Remove all regions from all partitions and reset all bounds
113   void make_all_regions_unavailable();
114 
115   // Set the partition id for a particular region without adjusting interval bounds or usage/capacity tallies
116   inline void raw_assign_membership(size_t idx, ShenandoahFreeSetPartitionId p) {
117     _membership[int(p)].set_bit(idx);
118   }
119 
120   // Set the Mutator intervals, usage, and capacity according to arguments.  Reset the Collector intervals, used, capacity
121   // to represent empty Collector free set.  We use this at the end of rebuild_free_set() to avoid the overhead of making
122   // many redundant incremental adjustments to the mutator intervals as the free set is being rebuilt.
123   void establish_mutator_intervals(ssize_t mutator_leftmost, ssize_t mutator_rightmost,
124                                    ssize_t mutator_leftmost_empty, ssize_t mutator_rightmost_empty,
125                                    size_t mutator_region_count, size_t mutator_used);
126 
127   // Set the OldCollector intervals, usage, and capacity according to arguments.  We use this at the end of rebuild_free_set()
128   // to avoid the overhead of making many redundant incremental adjustments to the mutator intervals as the free set is being
129   // rebuilt.
130   void establish_old_collector_intervals(ssize_t old_collector_leftmost, ssize_t old_collector_rightmost,
131                                          ssize_t old_collector_leftmost_empty, ssize_t old_collector_rightmost_empty,
132                                          size_t old_collector_region_count, size_t old_collector_used);
133 
134   // Retire region idx from within partition, , leaving its capacity and used as part of the original free partition's totals.
135   // Requires that region idx is in in the Mutator or Collector partitions.  Hereafter, identifies this region as NotFree.
136   // Any remnant of available memory at the time of retirement is added to the original partition's total of used bytes.
137   void retire_from_partition(ShenandoahFreeSetPartitionId p, ssize_t idx, size_t used_bytes);
138 
139   // Retire all regions between low_idx and high_idx inclusive from within partition.  Requires that each region idx is
140   // in the same Mutator or Collector partition.  Hereafter, identifies each region as NotFree.   Assumes that each region
141   // is now considered fully used, since the region is presumably used to represent a humongous object.
142   void retire_range_from_partition(ShenandoahFreeSetPartitionId partition, ssize_t low_idx, ssize_t high_idx);
143 
144   // Place region idx into free set which_partition.  Requires that idx is currently NotFree.
145   void make_free(ssize_t idx, ShenandoahFreeSetPartitionId which_partition, size_t region_capacity);
146 
147   // Place region idx into free partition new_partition, adjusting used and capacity totals for the original and new partition
148   // given that available bytes can still be allocated within this region.  Requires that idx is currently not NotFree.
149   void move_from_partition_to_partition(ssize_t idx, ShenandoahFreeSetPartitionId orig_partition,
150                                         ShenandoahFreeSetPartitionId new_partition, size_t available);
151 
152   const char* partition_membership_name(ssize_t idx) const;
153 

182   inline size_t max_regions() const { return _max; }
183 
184   inline size_t region_size_bytes() const { return _region_size_bytes; };
185 
186   // The following four methods return the left-most and right-most bounds on ranges of regions representing
187   // the requested set.  The _empty variants represent bounds on the range that holds completely empty
188   // regions, which are required for humongous allocations and desired for "very large" allocations.
189   //   if the requested which_partition is empty:
190   //     leftmost() and leftmost_empty() return _max, rightmost() and rightmost_empty() return 0
191   //   otherwise, expect the following:
192   //     0 <= leftmost <= leftmost_empty <= rightmost_empty <= rightmost < _max
193   inline ssize_t leftmost(ShenandoahFreeSetPartitionId which_partition) const;
194   inline ssize_t rightmost(ShenandoahFreeSetPartitionId which_partition) const;
195   ssize_t leftmost_empty(ShenandoahFreeSetPartitionId which_partition);
196   ssize_t rightmost_empty(ShenandoahFreeSetPartitionId which_partition);
197 
198   inline bool is_empty(ShenandoahFreeSetPartitionId which_partition) const;
199 
200   inline void increase_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
201 
202   inline void set_bias_from_left_to_right(ShenandoahFreeSetPartitionId which_partition, bool value) {
203     assert (which_partition < NumPartitions, "selected free set must be valid");
204     _left_to_right_bias[int(which_partition)] = value;
205   }
206 
207   inline bool alloc_from_left_bias(ShenandoahFreeSetPartitionId which_partition) const {
208     assert (which_partition < NumPartitions, "selected free set must be valid");
209     return _left_to_right_bias[int(which_partition)];
210   }
211 
212   inline size_t capacity_of(ShenandoahFreeSetPartitionId which_partition) const {
213     assert (which_partition < NumPartitions, "selected free set must be valid");
214     return _capacity[int(which_partition)];
215   }
216 
217   inline size_t used_by(ShenandoahFreeSetPartitionId which_partition) const {
218     assert (which_partition < NumPartitions, "selected free set must be valid");
219     return _used[int(which_partition)];
220   }
221 
222   inline size_t available_in(ShenandoahFreeSetPartitionId which_partition) const {
223     assert (which_partition < NumPartitions, "selected free set must be valid");
224     return _capacity[int(which_partition)] - _used[int(which_partition)];
225   }
226 
227   inline void set_capacity_of(ShenandoahFreeSetPartitionId which_partition, size_t value) {
228     assert (which_partition < NumPartitions, "selected free set must be valid");
229     _capacity[int(which_partition)] = value;
230   }
231 

249   //       idx <= rightmost
250   //     }
251   //   if the set has no empty regions, leftmost_empty equals max and rightmost_empty equals 0
252   //   Otherwise (the region has empty regions):
253   //     0 <= leftmost_empty < max and 0 <= rightmost_empty < max
254   //     rightmost_empty >= leftmost_empty
255   //     for every idx that is in the set and is empty {
256   //       idx >= leftmost &&
257   //       idx <= rightmost
258   //     }
259   void assert_bounds() NOT_DEBUG_RETURN;
260 };
261 
262 // Publicly, ShenandoahFreeSet represents memory that is available to mutator threads.  The public capacity(), used(),
263 // and available() methods represent this public notion of memory that is under control of the mutator.  Separately,
264 // ShenandoahFreeSet also represents memory available to garbage collection activities for compaction purposes.
265 //
266 // The Shenandoah garbage collector evacuates live objects out of specific regions that are identified as members of the
267 // collection set (cset).
268 //
269 // The ShenandoahFreeSet tries to colocate survivor objects (objects that have been evacuated at least once) at the
270 // high end of memory.  New mutator allocations are taken from the low end of memory.  Within the mutator's range of regions,
271 // humongous allocations are taken from the lowest addresses, and LAB (local allocation buffers) and regular shared allocations
272 // are taken from the higher address of the mutator's range of regions.  This approach allows longer lasting survivor regions
273 // to congregate at the top of the heap and longer lasting humongous regions to congregate at the bottom of the heap, with
274 // short-lived frequently evacuated regions occupying the middle of the heap.
275 //
276 // Mutator and garbage collection activities tend to scramble the content of regions.  Twice, during each GC pass, we rebuild
277 // the free set in an effort to restore the efficient segregation of Collector and Mutator regions:
278 //
279 //  1. At the start of evacuation, we know exactly how much memory is going to be evacuated, and this guides our
280 //     sizing of the Collector free set.
281 //
282 //  2. At the end of GC, we have reclaimed all of the memory that was spanned by the cset.  We rebuild here to make
283 //     sure there is enough memory reserved at the high end of memory to hold the objects that might need to be evacuated
284 //     during the next GC pass.
285 
286 class ShenandoahFreeSet : public CHeapObj<mtGC> {
287 private:
288   ShenandoahHeap* const _heap;
289   ShenandoahRegionPartitions _partitions;
290   size_t _retired_old_regions;
291 
292   HeapWord* allocate_aligned_plab(size_t size, ShenandoahAllocRequest& req, ShenandoahHeapRegion* r);
293 
294   // Return the address of memory allocated, setting in_new_region to true iff the allocation is taken
295   // from a region that was previously empty.  Return nullptr if memory could not be allocated.
296   inline HeapWord* allocate_from_partition_with_affiliation(ShenandoahFreeSetPartitionId which_partition,
297                                                             ShenandoahAffiliation affiliation,
298                                                             ShenandoahAllocRequest& req, bool& in_new_region);
299 
300   // We re-evaluate the left-to-right allocation bias whenever _alloc_bias_weight is less than zero.  Each time
301   // we allocate an object, we decrement the count of this value.  Each time we re-evaluate whether to allocate
302   // from right-to-left or left-to-right, we reset the value of this counter to _InitialAllocBiasWeight.
303   ssize_t _alloc_bias_weight;
304 
305   const ssize_t _InitialAllocBiasWeight = 256;
306 
307   HeapWord* try_allocate_in(ShenandoahHeapRegion* region, ShenandoahAllocRequest& req, bool& in_new_region);
308 
309   // While holding the heap lock, allocate memory for a single object or LAB  which is to be entirely contained
310   // within a single HeapRegion as characterized by req.
311   //
312   // Precondition: req.size() <= ShenandoahHeapRegion::humongous_threshold_words().
313   HeapWord* allocate_single(ShenandoahAllocRequest& req, bool& in_new_region);
314 
315   // While holding the heap lock, allocate memory for a humongous object which spans one or more regions that
316   // were previously empty.  Regions that represent humongous objects are entirely dedicated to the humongous
317   // object.  No other objects are packed into these regions.
318   //
319   // Precondition: req.size() > ShenandoahHeapRegion::humongous_threshold_words().
320   HeapWord* allocate_contiguous(ShenandoahAllocRequest& req);
321 
322   // Change region r from the Mutator partition to the GC's Collector or OldCollector partition.  This requires that the
323   // region is entirely empty.
324   //
325   // Typical usage: During evacuation, the GC may find it needs more memory than had been reserved at the start of evacuation to
326   // hold evacuated objects.  If this occurs and memory is still available in the Mutator's free set, we will flip a region from
327   // the Mutator free set into the Collector or OldCollector free set.
328   void flip_to_gc(ShenandoahHeapRegion* r);
329   void flip_to_old_gc(ShenandoahHeapRegion* r);
330 
331   void clear_internal();
332   void try_recycle_trashed(ShenandoahHeapRegion *r);
333 
334   // Returns true iff this region is entirely available, either because it is empty() or because it has been found to represent
335   // immediate trash and we'll be able to immediately recycle it.  Note that we cannot recycle immediate trash if
336   // concurrent weak root processing is in progress.
337   inline bool can_allocate_from(ShenandoahHeapRegion *r) const;
338   inline bool can_allocate_from(size_t idx) const;
339 
340   inline bool has_alloc_capacity(ShenandoahHeapRegion *r) const;
341 
342   size_t transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
343                                                                   size_t max_xfer_regions,
344                                                                   size_t& bytes_transferred);
345   size_t transfer_non_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId collector_id,
346                                                                       size_t max_xfer_regions,
347                                                                       size_t& bytes_transferred);
348 




349 
350   // Determine whether we prefer to allocate from left to right or from right to left within the OldCollector free-set.
351   void establish_old_collector_alloc_bias();
352 
353   // Set max_capacity for young and old generations
354   void establish_generation_sizes(size_t young_region_count, size_t old_region_count);
355   size_t get_usable_free_words(size_t free_bytes) const;
356 
357 public:
358   ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions);
359 
360   // Public because ShenandoahRegionPartitions assertions require access.
361   inline size_t alloc_capacity(ShenandoahHeapRegion *r) const;
362   inline size_t alloc_capacity(size_t idx) const;
363 
364   void clear();
365 
366   // Examine the existing free set representation, capturing the current state into var arguments:
367   //
368   // young_cset_regions is the number of regions currently in the young cset if we are starting to evacuate, or zero
369   //   old_cset_regions is the number of regions currently in the old cset if we are starting a mixed evacuation, or zero
370   //   first_old_region is the index of the first region that is part of the OldCollector set
371   //    last_old_region is the index of the last region that is part of the OldCollector set
372   //   old_region_count is the number of regions in the OldCollector set that have memory available to be allocated
373   void prepare_to_rebuild(size_t &young_cset_regions, size_t &old_cset_regions,
374                           size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
375 
376   // At the end of final mark, but before we begin evacuating, heuristics calculate how much memory is required to
377   // hold the results of evacuating to young-gen and to old-gen, and have_evacuation_reserves should be true.
378   // These quantities, stored as reserves for their respective generations, are consulted prior to rebuilding
379   // the free set (ShenandoahFreeSet) in preparation for evacuation.  When the free set is rebuilt, we make sure
380   // to reserve sufficient memory in the collector and old_collector sets to hold evacuations.
381   //
382   // We also rebuild the free set at the end of GC, as we prepare to idle GC until the next trigger.  In this case,
383   // have_evacuation_reserves is false because we don't yet know how much memory will need to be evacuated in the
384   // next GC cycle.  When have_evacuation_reserves is false, the free set rebuild operation reserves for the collector
385   // and old_collector sets based on alternative mechanisms, such as ShenandoahEvacReserve, ShenandoahOldEvacReserve, and
386   // ShenandoahOldCompactionReserve.  In a future planned enhancement, the reserve for old_collector set when the
387   // evacuation reserves are unknown, is based in part on anticipated promotion as determined by analysis of live data
388   // found during the previous GC pass which is one less than the current tenure age.
389   //
390   // young_cset_regions is the number of regions currently in the young cset if we are starting to evacuate, or zero
391   //   old_cset_regions is the number of regions currently in the old cset if we are starting a mixed evacuation, or zero
392   //    num_old_regions is the number of old-gen regions that have available memory for further allocations (excluding old cset)
393   // have_evacuation_reserves is true iff the desired values of young-gen and old-gen evacuation reserves and old-gen
394   //                    promotion reserve have been precomputed (and can be obtained by invoking
395   //                    <generation>->get_evacuation_reserve() or old_gen->get_promoted_reserve()
396   void finish_rebuild(size_t young_cset_regions, size_t old_cset_regions, size_t num_old_regions,
397                       bool have_evacuation_reserves = false);
398 
399   // When a region is promoted in place, we add the region's available memory if it is greater than plab_min_size()
400   // into the old collector partition by invoking this method.
401   void add_promoted_in_place_region_to_old_collector(ShenandoahHeapRegion* region);
402 
403   // Move up to cset_regions number of regions from being available to the collector to being available to the mutator.
404   //
405   // Typical usage: At the end of evacuation, when the collector no longer needs the regions that had been reserved
406   // for evacuation, invoke this to make regions available for mutator allocations.





407   void move_regions_from_collector_to_mutator(size_t cset_regions);
408 
409   void recycle_trash();
410 
411   void log_status();
412 
413   inline size_t capacity()  const { return _partitions.capacity_of(ShenandoahFreeSetPartitionId::Mutator); }
414   inline size_t used()      const { return _partitions.used_by(ShenandoahFreeSetPartitionId::Mutator);     }
415   inline size_t available() const {
416     assert(used() <= capacity(), "must use less than capacity");
417     return capacity() - used();
418   }
419 
420   HeapWord* allocate(ShenandoahAllocRequest& req, bool& in_new_region);
421   size_t unsafe_peek_free() const;
422 
423   /*
424    * Internal fragmentation metric: describes how fragmented the heap regions are.
425    *
426    * It is derived as:
427    *
428    *               sum(used[i]^2, i=0..k)
429    *   IF = 1 - ------------------------------
430    *              C * sum(used[i], i=0..k)

442    *   f) Heap has one small object per each region => IF =~ 1
443    */
444   double internal_fragmentation();
445 
446   /*
447    * External fragmentation metric: describes how fragmented the heap is.
448    *
449    * It is derived as:
450    *
451    *   EF = 1 - largest_contiguous_free / total_free
452    *
453    * For example:
454    *   a) Heap is completely empty => EF = 0
455    *   b) Heap is completely full => EF = 0
456    *   c) Heap is first-half full => EF = 1/2
457    *   d) Heap is half full, full and empty regions interleave => EF =~ 1
458    */
459   double external_fragmentation();
460 
461   void print_on(outputStream* out) const;
462 
463   // This function places all regions that have allocation capacity into the mutator partition, or if the region
464   // is already affiliated with old, into the old collector partition, identifying regions that have no allocation
465   // capacity as NotFree.  Capture the modified state of the freeset into var arguments:
466   //
467   // young_cset_regions is the number of regions currently in the young cset if we are starting to evacuate, or zero
468   //   old_cset_regions is the number of regions currently in the old cset if we are starting a mixed evacuation, or zero
469   //   first_old_region is the index of the first region that is part of the OldCollector set
470   //    last_old_region is the index of the last region that is part of the OldCollector set
471   //   old_region_count is the number of regions in the OldCollector set that have memory available to be allocated
472   void find_regions_with_alloc_capacity(size_t &young_cset_regions, size_t &old_cset_regions,
473                                         size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
474 
475   // Ensure that Collector has at least to_reserve bytes of available memory, and OldCollector has at least old_reserve
476   // bytes of available memory.  On input, old_region_count holds the number of regions already present in the
477   // OldCollector partition.  Upon return, old_region_count holds the updated number of regions in the OldCollector partition.
478   void reserve_regions(size_t to_reserve, size_t old_reserve, size_t &old_region_count);
479 
480   // Reserve space for evacuations, with regions reserved for old evacuations placed to the right
481   // of regions reserved of young evacuations.
482   void compute_young_and_old_reserves(size_t young_cset_regions, size_t old_cset_regions, bool have_evacuation_reserves,
483                                       size_t &young_reserve_result, size_t &old_reserve_result) const;
484 };
485 
486 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
< prev index next >