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