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 
 33 enum ShenandoahFreeMemoryType : uint8_t {
 34   NotFree,
 35   Mutator,
 36   Collector,
 37   OldCollector,
 38   NumFreeSets
 39 };
 40 
 41 class ShenandoahSetsOfFree {
 42 
 43 private:
 44   size_t _max;                  // The maximum number of heap regions
 45   ShenandoahFreeSet* _free_set;
 46   size_t _region_size_bytes;
 47   ShenandoahFreeMemoryType* _membership;
 48   size_t _leftmosts[NumFreeSets];
 49   size_t _rightmosts[NumFreeSets];
 50   size_t _leftmosts_empty[NumFreeSets];
 51   size_t _rightmosts_empty[NumFreeSets];
 52   size_t _capacity_of[NumFreeSets];
 53   size_t _used_by[NumFreeSets];
 54   bool _left_to_right_bias[NumFreeSets];
 55   size_t _region_counts[NumFreeSets];
 56 
 57   inline void shrink_bounds_if_touched(ShenandoahFreeMemoryType set, size_t idx);
 58   inline void expand_bounds_maybe(ShenandoahFreeMemoryType set, size_t idx, size_t capacity);
 59 
 60   // Restore all state variables to initial default state.
 61   void clear_internal();
 62 
 63 public:
 64   ShenandoahSetsOfFree(size_t max_regions, ShenandoahFreeSet* free_set);
 65   ~ShenandoahSetsOfFree();
 66 
 67   // Make all regions NotFree and reset all bounds
 68   void clear_all();
 69 
 70   // Remove or retire region idx from all free sets.  Requires that idx is in a free set.  This does not affect capacity.
 71   void remove_from_free_sets(size_t idx);
 72 
 73   // Place region idx into free set which_set.  Requires that idx is currently NotFree.
 74   void make_free(size_t idx, ShenandoahFreeMemoryType which_set, size_t region_capacity);
 75 
 76   // Place region idx into free set new_set.  Requires that idx is currently not NotFree.
 77   void move_to_set(size_t idx, ShenandoahFreeMemoryType new_set, size_t region_capacity);
 78 
 79   // Returns the ShenandoahFreeMemoryType affiliation of region idx, or NotFree if this region is not currently free.  This does
 80   // not enforce that free_set membership implies allocation capacity.
 81   inline ShenandoahFreeMemoryType membership(size_t idx) const;
 82 
 83   // Returns true iff region idx is in the test_set free_set.  Before returning true, asserts that the free
 84   // set is not empty.  Requires that test_set != NotFree or NumFreeSets.
 85   inline bool in_free_set(size_t idx, ShenandoahFreeMemoryType which_set) const;
 86 
 87   // The following four methods return the left-most and right-most bounds on ranges of regions representing
 88   // the requested set.  The _empty variants represent bounds on the range that holds completely empty
 89   // regions, which are required for humongous allocations and desired for "very large" allocations.  A
 90   // return value of -1 from leftmost() or leftmost_empty() denotes that the corresponding set is empty.
 91   // In other words:
 92   //   if the requested which_set is empty:
 93   //     leftmost() and leftmost_empty() return _max, rightmost() and rightmost_empty() return 0
 94   //   otherwise, expect the following:
 95   //     0 <= leftmost <= leftmost_empty <= rightmost_empty <= rightmost < _max
 96   inline size_t leftmost(ShenandoahFreeMemoryType which_set) const;
 97   inline size_t rightmost(ShenandoahFreeMemoryType which_set) const;
 98   size_t leftmost_empty(ShenandoahFreeMemoryType which_set);
 99   size_t rightmost_empty(ShenandoahFreeMemoryType which_set);
100 
101   inline bool is_empty(ShenandoahFreeMemoryType which_set) const;
102 
103   inline void increase_used(ShenandoahFreeMemoryType which_set, size_t bytes);
104 
105   inline size_t capacity_of(ShenandoahFreeMemoryType which_set) const {
106     assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid");
107     return _capacity_of[which_set];
108   }
109 
110   inline size_t used_by(ShenandoahFreeMemoryType which_set) const {
111     assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid");
112     return _used_by[which_set];
113   }
114 
115   inline size_t max() const { return _max; }
116 
117   inline size_t count(ShenandoahFreeMemoryType which_set) const { return _region_counts[which_set]; }
118 
119   // Return true iff regions for allocation from this set should be peformed left to right.  Otherwise, allocate
120   // from right to left.
121   inline bool alloc_from_left_bias(ShenandoahFreeMemoryType which_set);
122 
123   // Determine whether we prefer to allocate from left to right or from right to left for this free-set.
124   void establish_alloc_bias(ShenandoahFreeMemoryType which_set);
125 
126   // Assure leftmost, rightmost, leftmost_empty, and rightmost_empty bounds are valid for all free sets.
127   // Valid bounds honor all of the following (where max is the number of heap regions):
128   //   if the set is empty, leftmost equals max and rightmost equals 0
129   //   Otherwise (the set is not empty):
130   //     0 <= leftmost < max and 0 <= rightmost < max
131   //     the region at leftmost is in the set
132   //     the region at rightmost is in the set
133   //     rightmost >= leftmost
134   //     for every idx that is in the set {
135   //       idx >= leftmost &&
136   //       idx <= rightmost
137   //     }
138   //   if the set has no empty regions, leftmost_empty equals max and rightmost_empty equals 0
139   //   Otherwise (the region has empty regions):
140   //     0 <= lefmost_empty < max and 0 <= rightmost_empty < max
141   //     rightmost_empty >= leftmost_empty
142   //     for every idx that is in the set and is empty {
143   //       idx >= leftmost &&
144   //       idx <= rightmost
145   //     }
146   void assert_bounds() NOT_DEBUG_RETURN;
147 };
148 
149 class ShenandoahFreeSet : public CHeapObj<mtGC> {
150 private:
151   ShenandoahHeap* const _heap;
152   ShenandoahSetsOfFree _free_sets;
153 
154   HeapWord* try_allocate_in(ShenandoahHeapRegion* region, ShenandoahAllocRequest& req, bool& in_new_region);
155 
156   HeapWord* allocate_aligned_plab(size_t size, ShenandoahAllocRequest& req, ShenandoahHeapRegion* r);
157 
158   // Satisfy young-generation or single-generation collector allocation request req by finding memory that matches
159   // affiliation, which either equals req.affiliation or FREE.  We know req.is_young().
160   HeapWord* allocate_with_affiliation(ShenandoahAffiliation affiliation, ShenandoahAllocRequest& req, bool& in_new_region);
161 
162   // Satisfy allocation request req by finding memory that matches affiliation, which either equals req.affiliation
163   // or FREE. We know req.is_old().
164   HeapWord* allocate_old_with_affiliation(ShenandoahAffiliation affiliation, ShenandoahAllocRequest& req, bool& in_new_region);
165 
166   // While holding the heap lock, allocate memory for a single object which is to be entirely contained
167   // within a single HeapRegion as characterized by req.  The req.size() value is known to be less than or
168   // equal to ShenandoahHeapRegion::humongous_threshold_words().  The caller of allocate_single is responsible
169   // for registering the resulting object and setting the remembered set card values as appropriate.  The
170   // most common case is that we are allocating a PLAB in which case object registering and card dirtying
171   // is managed after the PLAB is divided into individual objects.
172   HeapWord* allocate_single(ShenandoahAllocRequest& req, bool& in_new_region);
173   HeapWord* allocate_contiguous(ShenandoahAllocRequest& req);
174 
175   void flip_to_gc(ShenandoahHeapRegion* r);
176   void flip_to_old_gc(ShenandoahHeapRegion* r);
177 
178   void clear_internal();
179 
180   void try_recycle_trashed(ShenandoahHeapRegion *r);
181 
182   bool can_allocate_from(ShenandoahHeapRegion *r) const;
183   bool can_allocate_from(size_t idx) const;
184   bool has_alloc_capacity(ShenandoahHeapRegion *r) const;
185 
186 public:
187   ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions);
188 
189   size_t alloc_capacity(ShenandoahHeapRegion *r) const;
190   size_t alloc_capacity(size_t idx) const;
191 
192   void clear();
193   void prepare_to_rebuild(size_t &young_cset_regions, size_t &old_cset_regions,
194                           size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
195   void rebuild(size_t young_cset_regions, size_t old_cset_regions);
196   void move_collector_sets_to_mutator(size_t cset_regions);
197 
198   void add_old_collector_free_region(ShenandoahHeapRegion* region);
199 
200   void recycle_trash();
201 
202   void log_status();
203 
204   inline size_t capacity()  const { return _free_sets.capacity_of(Mutator); }
205   inline size_t used()      const { return _free_sets.used_by(Mutator);     }
206   inline size_t available() const {
207     assert(used() <= capacity(), "must use less than capacity");
208     return capacity() - used();
209   }
210 
211   HeapWord* allocate(ShenandoahAllocRequest& req, bool& in_new_region);
212   size_t unsafe_peek_free() const;
213 
214   double internal_fragmentation();
215   double external_fragmentation();
216 
217   void print_on(outputStream* out) const;
218 
219   void find_regions_with_alloc_capacity(size_t &young_cset_regions, size_t &old_cset_regions,
220                                         size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
221   void reserve_regions(size_t young_reserve, size_t old_reserve);
222 };
223 
224 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP