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 196 // At the end of final mark, but before we begin evacuating, heuristics calculate how much memory is required to 197 // hold the results of evacuating to young-gen and to old-gen. These quantities, stored in reserves for their, 198 // respective generations, are consulted prior to rebuilding the free set (ShenandoahFreeSet) in preparation for 199 // evacuation. When the free set is rebuilt, we make sure to reserve sufficient memory in the collector and 200 // old_collector sets to hold evacuations, if have_evacuation_reserves is true. The other time we rebuild the free 201 // set is at the end of GC, as we prepare to idle GC until the next trigger. In this case, have_evacuation_reserves 202 // is false because we don't yet know how much memory will need to be evacuated in the next GC cycle. When 203 // have_evacuation_reserves is false, the free set rebuild operation reserves for the collector and old_collector sets 204 // based on alternative mechanisms, such as ShenandoahEvacReserve, ShenandoahOldEvacReserve, and 205 // ShenandoahOldCompactionReserve. In a future planned enhancement, the reserve for old_collector set when the 206 // evacuation reserves are unknown, is based in part on anticipated promotion as determined by analysis of live data 207 // found during the previous GC pass which is one less than the current tenure age. 208 void rebuild(size_t young_cset_regions, size_t old_cset_regions, bool have_evacuation_reserves = false); 209 210 void move_collector_sets_to_mutator(size_t cset_regions); 211 212 void add_old_collector_free_region(ShenandoahHeapRegion* region); 213 214 void recycle_trash(); 215 216 void log_status(); 217 218 inline size_t capacity() const { return _free_sets.capacity_of(Mutator); } 219 inline size_t used() const { return _free_sets.used_by(Mutator); } 220 inline size_t available() const { 221 assert(used() <= capacity(), "must use less than capacity"); 222 return capacity() - used(); 223 } 224 225 HeapWord* allocate(ShenandoahAllocRequest& req, bool& in_new_region); 226 size_t unsafe_peek_free() const; 227 228 double internal_fragmentation(); 229 double external_fragmentation(); 230 231 void print_on(outputStream* out) const; 232 233 void find_regions_with_alloc_capacity(size_t &young_cset_regions, size_t &old_cset_regions, 234 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count); 235 void reserve_regions(size_t young_reserve, size_t old_reserve); 236 237 // Reserve space for evacuations, with regions reserved for old evacuations placed to the right 238 // of regions reserved of young evacuations. 239 void compute_young_and_old_reserves(size_t young_cset_regions, size_t old_cset_regions, bool have_evacuation_reserves, 240 size_t &young_reserve_result, size_t &old_reserve_result) const; 241 }; 242 243 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP