1 /*
2 * Copyright (c) 2016, 2019, Red Hat, Inc. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
26 #define SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
27
28 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
29 #include "gc/shenandoah/shenandoahHeap.hpp"
30
31 class ShenandoahFreeSet : public CHeapObj<mtGC> {
32 private:
33 ShenandoahHeap* const _heap;
34 CHeapBitMap _mutator_free_bitmap;
35 CHeapBitMap _collector_free_bitmap;
36 size_t _max;
37
38 // Left-most and right-most region indexes. There are no free regions outside
39 // of [left-most; right-most] index intervals
40 size_t _mutator_leftmost, _mutator_rightmost;
41 size_t _collector_leftmost, _collector_rightmost;
42
43 size_t _capacity;
44 size_t _used;
45
46 void assert_bounds() const NOT_DEBUG_RETURN;
47
48 bool is_mutator_free(size_t idx) const;
49 bool is_collector_free(size_t idx) const;
50
51 HeapWord* try_allocate_in(ShenandoahHeapRegion* region, ShenandoahAllocRequest& req, bool& in_new_region);
52 HeapWord* allocate_single(ShenandoahAllocRequest& req, bool& in_new_region);
53 HeapWord* allocate_contiguous(ShenandoahAllocRequest& req);
54
55 void flip_to_gc(ShenandoahHeapRegion* r);
56
57 void recompute_bounds();
58 void adjust_bounds();
59 bool touches_bounds(size_t num) const;
60
61 void increase_used(size_t amount);
62 void clear_internal();
63
64 size_t collector_count() const { return _collector_free_bitmap.count_one_bits(); }
65 size_t mutator_count() const { return _mutator_free_bitmap.count_one_bits(); }
66
67 void try_recycle_trashed(ShenandoahHeapRegion *r);
68
69 bool can_allocate_from(ShenandoahHeapRegion *r);
70 size_t alloc_capacity(ShenandoahHeapRegion *r);
71 bool has_no_alloc_capacity(ShenandoahHeapRegion *r);
72
73 public:
74 ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions);
75
76 void clear();
77 void rebuild();
78
79 void recycle_trash();
80
81 void log_status();
82
83 size_t capacity() const { return _capacity; }
84 size_t used() const { return _used; }
85 size_t available() const {
86 assert(_used <= _capacity, "must use less than capacity");
87 return _capacity - _used;
88 }
89
90 HeapWord* allocate(ShenandoahAllocRequest& req, bool& in_new_region);
91 size_t unsafe_peek_free() const;
92
93 double internal_fragmentation();
94 double external_fragmentation();
95
96 void print_on(outputStream* out) const;
97 };
98
99 #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
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
|