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 * 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 OldCollector, // Region is in the Old Collector free set:
38 // available memory is reserved for old evacuations and for promotions..
39 NotFree // Region is in no free set: it has no available memory
40 };
41
42 // We do not maintain counts, capacity, or used for regions that are not free. Informally, if a region is NotFree, it is
43 // in no partition. NumPartitions represents the size of an array that may be indexed by Mutator or Collector.
44 #define NumPartitions (ShenandoahFreeSetPartitionId::NotFree)
45 #define IntNumPartitions int(ShenandoahFreeSetPartitionId::NotFree)
46 #define UIntNumPartitions uint(ShenandoahFreeSetPartitionId::NotFree)
47
48 // ShenandoahRegionPartitions provides an abstraction to help organize the implementation of ShenandoahFreeSet. This
49 // class implements partitioning of regions into distinct sets. Each ShenandoahHeapRegion is either in the Mutator free set,
50 // the Collector free set, or in neither free set (NotFree). When we speak of a "free partition", we mean partitions that
51 // for which the ShenandoahFreeSetPartitionId is not equal to NotFree.
52 class ShenandoahRegionPartitions {
53
54 private:
55 const ssize_t _max; // The maximum number of heap regions
56 const size_t _region_size_bytes;
57 const ShenandoahFreeSet* _free_set;
58 // For each partition, we maintain a bitmap of which regions are affiliated with his partition.
59 ShenandoahSimpleBitMap _membership[UIntNumPartitions];
60
61 // For each partition, we track an interval outside of which a region affiliated with that partition is guaranteed
62 // not to be found. This makes searches for free space more efficient. For each partition p, _leftmosts[p]
63 // represents its least index, and its _rightmosts[p] its greatest index. Empty intervals are indicated by the
64 // canonical [_max, -1].
65 ssize_t _leftmosts[UIntNumPartitions];
66 ssize_t _rightmosts[UIntNumPartitions];
67
68 // Allocation for humongous objects needs to find regions that are entirely empty. For each partion p, _leftmosts_empty[p]
69 // represents the first region belonging to this partition that is completely empty and _rightmosts_empty[p] represents the
70 // last region that is completely empty. If there is no completely empty region in this partition, this is represented
71 // by the canonical [_max, -1].
72 ssize_t _leftmosts_empty[UIntNumPartitions];
73 ssize_t _rightmosts_empty[UIntNumPartitions];
74
75 // For each partition p, _capacity[p] represents the total amount of memory within the partition at the time
76 // of the most recent rebuild, _used[p] represents the total amount of memory that has been allocated within this
77 // partition (either already allocated as of the rebuild, or allocated since the rebuild). _capacity[p] and _used[p]
78 // are denoted in bytes. Note that some regions that had been assigned to a particular partition at rebuild time
79 // may have been retired following the rebuild. The tallies for these regions are still reflected in _capacity[p]
80 // and _used[p], even though the region may have been removed from the free set.
81 size_t _capacity[UIntNumPartitions];
82 size_t _used[UIntNumPartitions];
83 size_t _region_counts[UIntNumPartitions];
84
85 // For each partition p, _left_to_right_bias is true iff allocations are normally made from lower indexed regions
86 // before higher indexed regions.
87 bool _left_to_right_bias[UIntNumPartitions];
88
89 // Shrink the intervals associated with partition when region idx is removed from this free set
90 inline void shrink_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, ssize_t idx);
91
92 // Shrink the intervals associated with partition when regions low_idx through high_idx inclusive are removed from this free set
93 inline void shrink_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId partition,
94 ssize_t low_idx, ssize_t high_idx);
95 inline void expand_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, ssize_t idx, size_t capacity);
96
97 inline bool is_mutator_partition(ShenandoahFreeSetPartitionId p);
98 inline bool is_young_collector_partition(ShenandoahFreeSetPartitionId p);
99 inline bool is_old_collector_partition(ShenandoahFreeSetPartitionId p);
100 inline bool available_implies_empty(size_t available);
101
102 #ifndef PRODUCT
103 void dump_bitmap_row(ssize_t region_idx) const;
104 void dump_bitmap_range(ssize_t start_region_idx, ssize_t end_region_idx) const;
105 void dump_bitmap() const;
106 #endif
107 public:
108 ShenandoahRegionPartitions(size_t max_regions, ShenandoahFreeSet* free_set);
109 ~ShenandoahRegionPartitions() {}
110
111 // Remove all regions from all partitions and reset all bounds
112 void make_all_regions_unavailable();
113
114 // Set the partition id for a particular region without adjusting interval bounds or usage/capacity tallies
115 inline void raw_assign_membership(size_t idx, ShenandoahFreeSetPartitionId p) {
116 _membership[int(p)].set_bit(idx);
117 }
118
119 // Set the Mutator intervals, usage, and capacity according to arguments. Reset the Collector intervals, used, capacity
120 // to represent empty Collector free set. We use this at the end of rebuild_free_set() to avoid the overhead of making
121 // many redundant incremental adjustments to the mutator intervals as the free set is being rebuilt.
122 void establish_mutator_intervals(ssize_t mutator_leftmost, ssize_t mutator_rightmost,
123 ssize_t mutator_leftmost_empty, ssize_t mutator_rightmost_empty,
124 size_t mutator_region_count, size_t mutator_used);
125
126 // Set the OldCollector intervals, usage, and capacity according to arguments. We use this at the end of rebuild_free_set()
127 // to avoid the overhead of making many redundant incremental adjustments to the mutator intervals as the free set is being
128 // rebuilt.
129 void establish_old_collector_intervals(ssize_t old_collector_leftmost, ssize_t old_collector_rightmost,
130 ssize_t old_collector_leftmost_empty, ssize_t old_collector_rightmost_empty,
131 size_t old_collector_region_count, size_t old_collector_used);
132
133 // Retire region idx from within partition, , leaving its capacity and used as part of the original free partition's totals.
134 // Requires that region idx is in in the Mutator or Collector partitions. Hereafter, identifies this region as NotFree.
135 // Any remnant of available memory at the time of retirement is added to the original partition's total of used bytes.
136 void retire_from_partition(ShenandoahFreeSetPartitionId p, ssize_t idx, size_t used_bytes);
137
138 // Retire all regions between low_idx and high_idx inclusive from within partition. Requires that each region idx is
139 // in the same Mutator or Collector partition. Hereafter, identifies each region as NotFree. Assumes that each region
140 // is now considered fully used, since the region is presumably used to represent a humongous object.
141 void retire_range_from_partition(ShenandoahFreeSetPartitionId partition, ssize_t low_idx, ssize_t high_idx);
142
143 // Place region idx into free set which_partition. Requires that idx is currently NotFree.
144 void make_free(ssize_t idx, ShenandoahFreeSetPartitionId which_partition, size_t region_capacity);
145
146 // Place region idx into free partition new_partition, adjusting used and capacity totals for the original and new partition
147 // given that available bytes can still be allocated within this region. Requires that idx is currently not NotFree.
148 void move_from_partition_to_partition(ssize_t idx, ShenandoahFreeSetPartitionId orig_partition,
149 ShenandoahFreeSetPartitionId new_partition, size_t available);
150
151 const char* partition_membership_name(ssize_t idx) const;
152
153 // Return the index of the next available region >= start_index, or maximum_regions if not found.
154 inline ssize_t find_index_of_next_available_region(ShenandoahFreeSetPartitionId which_partition, ssize_t start_index) const;
155
156 // Return the index of the previous available region <= last_index, or -1 if not found.
157 inline ssize_t find_index_of_previous_available_region(ShenandoahFreeSetPartitionId which_partition, ssize_t last_index) const;
158
159 // Return the index of the next available cluster of cluster_size regions >= start_index, or maximum_regions if not found.
160 inline ssize_t find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId which_partition,
161 ssize_t start_index, size_t cluster_size) const;
162
163 // Return the index of the previous available cluster of cluster_size regions <= last_index, or -1 if not found.
164 inline ssize_t find_index_of_previous_available_cluster_of_regions(ShenandoahFreeSetPartitionId which_partition,
165 ssize_t last_index, size_t cluster_size) const;
166
167 inline bool in_free_set(ShenandoahFreeSetPartitionId which_partition, ssize_t idx) const {
168 return _membership[int(which_partition)].is_set(idx);
169 }
170
171 // Returns the ShenandoahFreeSetPartitionId affiliation of region idx, NotFree if this region is not currently in any partition.
172 // This does not enforce that free_set membership implies allocation capacity.
173 inline ShenandoahFreeSetPartitionId membership(ssize_t idx) const;
174
175 #ifdef ASSERT
176 // Returns true iff region idx's membership is which_partition. If which_partition represents a free set, asserts
177 // that the region has allocation capacity.
178 inline bool partition_id_matches(ssize_t idx, ShenandoahFreeSetPartitionId which_partition) const;
179 #endif
180
181 inline size_t max_regions() const { return _max; }
182
183 inline size_t region_size_bytes() const { return _region_size_bytes; };
184
185 // The following four methods return the left-most and right-most bounds on ranges of regions representing
186 // the requested set. The _empty variants represent bounds on the range that holds completely empty
187 // regions, which are required for humongous allocations and desired for "very large" allocations.
188 // if the requested which_partition is empty:
189 // leftmost() and leftmost_empty() return _max, rightmost() and rightmost_empty() return 0
190 // otherwise, expect the following:
191 // 0 <= leftmost <= leftmost_empty <= rightmost_empty <= rightmost < _max
192 inline ssize_t leftmost(ShenandoahFreeSetPartitionId which_partition) const;
193 inline ssize_t rightmost(ShenandoahFreeSetPartitionId which_partition) const;
194 ssize_t leftmost_empty(ShenandoahFreeSetPartitionId which_partition);
195 ssize_t rightmost_empty(ShenandoahFreeSetPartitionId which_partition);
196
197 inline bool is_empty(ShenandoahFreeSetPartitionId which_partition) const;
198
199 inline void increase_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
200
201 inline void set_bias_from_left_to_right(ShenandoahFreeSetPartitionId which_partition, bool value) {
202 assert (which_partition < NumPartitions, "selected free set must be valid");
203 _left_to_right_bias[int(which_partition)] = value;
204 }
205
206 inline bool alloc_from_left_bias(ShenandoahFreeSetPartitionId which_partition) const {
207 assert (which_partition < NumPartitions, "selected free set must be valid");
208 return _left_to_right_bias[int(which_partition)];
209 }
210
211 inline size_t capacity_of(ShenandoahFreeSetPartitionId which_partition) const {
212 assert (which_partition < NumPartitions, "selected free set must be valid");
213 return _capacity[int(which_partition)];
214 }
215
216 inline size_t used_by(ShenandoahFreeSetPartitionId which_partition) const {
217 assert (which_partition < NumPartitions, "selected free set must be valid");
218 return _used[int(which_partition)];
219 }
220
221 inline size_t available_in(ShenandoahFreeSetPartitionId which_partition) const {
222 assert (which_partition < NumPartitions, "selected free set must be valid");
223 return _capacity[int(which_partition)] - _used[int(which_partition)];
224 }
225
226 inline void set_capacity_of(ShenandoahFreeSetPartitionId which_partition, size_t value) {
227 assert (which_partition < NumPartitions, "selected free set must be valid");
228 _capacity[int(which_partition)] = value;
229 }
230
231 inline void set_used_by(ShenandoahFreeSetPartitionId which_partition, size_t value) {
232 assert (which_partition < NumPartitions, "selected free set must be valid");
233 _used[int(which_partition)] = value;
234 }
235
236 inline size_t count(ShenandoahFreeSetPartitionId which_partition) const { return _region_counts[int(which_partition)]; }
237
238 // Assure leftmost, rightmost, leftmost_empty, and rightmost_empty bounds are valid for all free sets.
239 // Valid bounds honor all of the following (where max is the number of heap regions):
240 // if the set is empty, leftmost equals max and rightmost equals 0
241 // Otherwise (the set is not empty):
242 // 0 <= leftmost < max and 0 <= rightmost < max
243 // the region at leftmost is in the set
244 // the region at rightmost is in the set
245 // rightmost >= leftmost
246 // for every idx that is in the set {
247 // idx >= leftmost &&
248 // idx <= rightmost
249 // }
250 // if the set has no empty regions, leftmost_empty equals max and rightmost_empty equals 0
251 // Otherwise (the region has empty regions):
252 // 0 <= leftmost_empty < max and 0 <= rightmost_empty < max
253 // rightmost_empty >= leftmost_empty
254 // for every idx that is in the set and is empty {
255 // idx >= leftmost &&
256 // idx <= rightmost
257 // }
258 void assert_bounds() NOT_DEBUG_RETURN;
259 };
260
261 // Publicly, ShenandoahFreeSet represents memory that is available to mutator threads. The public capacity(), used(),
262 // and available() methods represent this public notion of memory that is under control of the mutator. Separately,
263 // ShenandoahFreeSet also represents memory available to garbage collection activities for compaction purposes.
264 //
265 // The Shenandoah garbage collector evacuates live objects out of specific regions that are identified as members of the
266 // collection set (cset).
267 //
268 // The ShenandoahFreeSet tries to colocate survivor objects (objects that have been evacuated at least once) at the
269 // high end of memory. New mutator allocations are taken from the low end of memory. Within the mutator's range of regions,
270 // humongous allocations are taken from the lowest addresses, and LAB (local allocation buffers) and regular shared allocations
271 // are taken from the higher address of the mutator's range of regions. This approach allows longer lasting survivor regions
272 // to congregate at the top of the heap and longer lasting humongous regions to congregate at the bottom of the heap, with
273 // short-lived frequently evacuated regions occupying the middle of the heap.
274 //
275 // Mutator and garbage collection activities tend to scramble the content of regions. Twice, during each GC pass, we rebuild
276 // the free set in an effort to restore the efficient segregation of Collector and Mutator regions:
277 //
278 // 1. At the start of evacuation, we know exactly how much memory is going to be evacuated, and this guides our
279 // sizing of the Collector free set.
280 //
281 // 2. At the end of GC, we have reclaimed all of the memory that was spanned by the cset. We rebuild here to make
282 // sure there is enough memory reserved at the high end of memory to hold the objects that might need to be evacuated
283 // during the next GC pass.
284
285 class ShenandoahFreeSet : public CHeapObj<mtGC> {
286 private:
287 ShenandoahHeap* const _heap;
288 ShenandoahRegionPartitions _partitions;
289
290 HeapWord* allocate_aligned_plab(size_t size, ShenandoahAllocRequest& req, ShenandoahHeapRegion* r);
291
292 // Return the address of memory allocated, setting in_new_region to true iff the allocation is taken
293 // from a region that was previously empty. Return nullptr if memory could not be allocated.
294 inline HeapWord* allocate_from_partition_with_affiliation(ShenandoahAffiliation affiliation,
295 ShenandoahAllocRequest& req, bool& in_new_region);
296
297 // We re-evaluate the left-to-right allocation bias whenever _alloc_bias_weight is less than zero. Each time
298 // we allocate an object, we decrement the count of this value. Each time we re-evaluate whether to allocate
299 // from right-to-left or left-to-right, we reset the value of this counter to _InitialAllocBiasWeight.
300 ssize_t _alloc_bias_weight;
301
302 const ssize_t INITIAL_ALLOC_BIAS_WEIGHT = 256;
303
304 // Increases used memory for the partition if the allocation is successful. `in_new_region` will be set
305 // if this is the first allocation in the region.
306 HeapWord* try_allocate_in(ShenandoahHeapRegion* region, ShenandoahAllocRequest& req, bool& in_new_region);
307
308 // While holding the heap lock, allocate memory for a single object or LAB which is to be entirely contained
309 // within a single HeapRegion as characterized by req.
310 //
311 // Precondition: !ShenandoahHeapRegion::requires_humongous(req.size())
312 HeapWord* allocate_single(ShenandoahAllocRequest& req, bool& in_new_region);
313
314 // While holding the heap lock, allocate memory for a humongous object which spans one or more regions that
315 // were previously empty. Regions that represent humongous objects are entirely dedicated to the humongous
316 // object. No other objects are packed into these regions.
317 //
318 // Precondition: ShenandoahHeapRegion::requires_humongous(req.size())
319 HeapWord* allocate_contiguous(ShenandoahAllocRequest& req);
320
321 // Change region r from the Mutator partition to the GC's Collector or OldCollector partition. This requires that the
322 // region is entirely empty.
323 //
324 // Typical usage: During evacuation, the GC may find it needs more memory than had been reserved at the start of evacuation to
325 // hold evacuated objects. If this occurs and memory is still available in the Mutator's free set, we will flip a region from
326 // the Mutator free set into the Collector or OldCollector free set.
327 void flip_to_gc(ShenandoahHeapRegion* r);
328 void flip_to_old_gc(ShenandoahHeapRegion* r);
329
330 // Handle allocation for mutator.
331 HeapWord* allocate_for_mutator(ShenandoahAllocRequest &req, bool &in_new_region);
332
333 // Update allocation bias and decided whether to allocate from the left or right side of the heap.
334 void update_allocation_bias();
335
336 // Search for regions to satisfy allocation request using iterator.
337 template<typename Iter>
338 HeapWord* allocate_from_regions(Iter& iterator, ShenandoahAllocRequest &req, bool &in_new_region);
339
340 // Handle allocation for collector (for evacuation).
341 HeapWord* allocate_for_collector(ShenandoahAllocRequest& req, bool& in_new_region);
342
343 // Search for allocation in region with same affiliation as request, using given iterator.
344 template<typename Iter>
345 HeapWord* allocate_with_affiliation(Iter& iterator, ShenandoahAffiliation affiliation, ShenandoahAllocRequest& req, bool& in_new_region);
346
347 // Return true if the respective generation for this request has free regions.
348 bool can_allocate_in_new_region(const ShenandoahAllocRequest& req);
349
350 // Attempt to allocate memory for an evacuation from the mutator's partition.
351 HeapWord* try_allocate_from_mutator(ShenandoahAllocRequest& req, bool& in_new_region);
352
353 void clear_internal();
354
355 // Returns true iff this region is entirely available, either because it is empty() or because it has been found to represent
356 // immediate trash and we'll be able to immediately recycle it. Note that we cannot recycle immediate trash if
357 // concurrent weak root processing is in progress.
358 inline bool can_allocate_from(ShenandoahHeapRegion *r) const;
359 inline bool can_allocate_from(size_t idx) const;
360
361 inline bool has_alloc_capacity(ShenandoahHeapRegion *r) const;
362
363 size_t transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
364 size_t max_xfer_regions,
365 size_t& bytes_transferred);
366 size_t transfer_non_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
367 size_t max_xfer_regions,
368 size_t& bytes_transferred);
369
370
371 // Determine whether we prefer to allocate from left to right or from right to left within the OldCollector free-set.
372 void establish_old_collector_alloc_bias();
373
374 // Set max_capacity for young and old generations
375 void establish_generation_sizes(size_t young_region_count, size_t old_region_count);
376 size_t get_usable_free_words(size_t free_bytes) const;
377
378 // log status, assuming lock has already been acquired by the caller.
379 void log_status();
380
381 public:
382 ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions);
383
384 // Public because ShenandoahRegionPartitions assertions require access.
385 inline size_t alloc_capacity(ShenandoahHeapRegion *r) const;
386 inline size_t alloc_capacity(size_t idx) const;
387
388 void clear();
389
390 // Examine the existing free set representation, capturing the current state into var arguments:
391 //
392 // young_cset_regions is the number of regions currently in the young cset if we are starting to evacuate, or zero
393 // old_cset_regions is the number of regions currently in the old cset if we are starting a mixed evacuation, or zero
394 // first_old_region is the index of the first region that is part of the OldCollector set
395 // last_old_region is the index of the last region that is part of the OldCollector set
396 // old_region_count is the number of regions in the OldCollector set that have memory available to be allocated
397 void prepare_to_rebuild(size_t &young_cset_regions, size_t &old_cset_regions,
398 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
399
400 // At the end of final mark, but before we begin evacuating, heuristics calculate how much memory is required to
401 // hold the results of evacuating to young-gen and to old-gen, and have_evacuation_reserves should be true.
402 // These quantities, stored as reserves for their respective generations, are consulted prior to rebuilding
403 // the free set (ShenandoahFreeSet) in preparation for evacuation. When the free set is rebuilt, we make sure
404 // to reserve sufficient memory in the collector and old_collector sets to hold evacuations.
405 //
406 // We also rebuild the free set at the end of GC, as we prepare to idle GC until the next trigger. In this case,
407 // have_evacuation_reserves is false because we don't yet know how much memory will need to be evacuated in the
408 // next GC cycle. When have_evacuation_reserves is false, the free set rebuild operation reserves for the collector
409 // and old_collector sets based on alternative mechanisms, such as ShenandoahEvacReserve, ShenandoahOldEvacReserve, and
410 // ShenandoahOldCompactionReserve. In a future planned enhancement, the reserve for old_collector set when the
411 // evacuation reserves are unknown, is based in part on anticipated promotion as determined by analysis of live data
412 // found during the previous GC pass which is one less than the current tenure age.
413 //
414 // young_cset_regions is the number of regions currently in the young cset if we are starting to evacuate, or zero
415 // old_cset_regions is the number of regions currently in the old cset if we are starting a mixed evacuation, or zero
416 // num_old_regions is the number of old-gen regions that have available memory for further allocations (excluding old cset)
417 // have_evacuation_reserves is true iff the desired values of young-gen and old-gen evacuation reserves and old-gen
418 // promotion reserve have been precomputed (and can be obtained by invoking
419 // <generation>->get_evacuation_reserve() or old_gen->get_promoted_reserve()
420 void finish_rebuild(size_t young_cset_regions, size_t old_cset_regions, size_t num_old_regions,
421 bool have_evacuation_reserves = false);
422
423 // When a region is promoted in place, we add the region's available memory if it is greater than plab_min_size()
424 // into the old collector partition by invoking this method.
425 void add_promoted_in_place_region_to_old_collector(ShenandoahHeapRegion* region);
426
427 // Move up to cset_regions number of regions from being available to the collector to being available to the mutator.
428 //
429 // Typical usage: At the end of evacuation, when the collector no longer needs the regions that had been reserved
430 // for evacuation, invoke this to make regions available for mutator allocations.
431 void move_regions_from_collector_to_mutator(size_t cset_regions);
432
433 void recycle_trash();
434
435 // Acquire heap lock and log status, assuming heap lock is not acquired by the caller.
436 void log_status_under_lock();
437
438 // Note that capacity is the number of regions that had available memory at most recent rebuild. It is not the
439 // entire size of the young or global generation. (Regions within the generation that were fully utilized at time of
440 // rebuild are not counted as part of capacity.)
441 inline size_t capacity() const { return _partitions.capacity_of(ShenandoahFreeSetPartitionId::Mutator); }
442 inline size_t used() const { return _partitions.used_by(ShenandoahFreeSetPartitionId::Mutator); }
443
444 inline size_t available() const {
445 assert(used() <= capacity(), "must use less than capacity");
446 return capacity() - used();
447 }
448
449 HeapWord* allocate(ShenandoahAllocRequest& req, bool& in_new_region);
450
451 /*
452 * Internal fragmentation metric: describes how fragmented the heap regions are.
453 *
454 * It is derived as:
455 *
456 * sum(used[i]^2, i=0..k)
457 * IF = 1 - ------------------------------
458 * C * sum(used[i], i=0..k)
459 *
460 * ...where k is the number of regions in computation, C is the region capacity, and
461 * used[i] is the used space in the region.
462 *
463 * The non-linearity causes IF to be lower for the cases where the same total heap
464 * used is densely packed. For example:
465 * a) Heap is completely full => IF = 0
466 * b) Heap is half full, first 50% regions are completely full => IF = 0
467 * c) Heap is half full, each region is 50% full => IF = 1/2
468 * d) Heap is quarter full, first 50% regions are completely full => IF = 0
469 * e) Heap is quarter full, each region is 25% full => IF = 3/4
470 * f) Heap has one small object per each region => IF =~ 1
471 */
472 double internal_fragmentation();
473
474 /*
475 * External fragmentation metric: describes how fragmented the heap is.
476 *
477 * It is derived as:
478 *
479 * EF = 1 - largest_contiguous_free / total_free
480 *
481 * For example:
482 * a) Heap is completely empty => EF = 0
483 * b) Heap is completely full => EF = 0
484 * c) Heap is first-half full => EF = 1/2
485 * d) Heap is half full, full and empty regions interleave => EF =~ 1
486 */
487 double external_fragmentation();
488
489 void print_on(outputStream* out) const;
490
491 // This function places all regions that have allocation capacity into the mutator partition, or if the region
492 // is already affiliated with old, into the old collector partition, identifying regions that have no allocation
493 // capacity as NotFree. Capture the modified state of the freeset into var arguments:
494 //
495 // young_cset_regions is the number of regions currently in the young cset if we are starting to evacuate, or zero
496 // old_cset_regions is the number of regions currently in the old cset if we are starting a mixed evacuation, or zero
497 // first_old_region is the index of the first region that is part of the OldCollector set
498 // last_old_region is the index of the last region that is part of the OldCollector set
499 // old_region_count is the number of regions in the OldCollector set that have memory available to be allocated
500 void find_regions_with_alloc_capacity(size_t &young_cset_regions, size_t &old_cset_regions,
501 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
502
503 // Ensure that Collector has at least to_reserve bytes of available memory, and OldCollector has at least old_reserve
504 // bytes of available memory. On input, old_region_count holds the number of regions already present in the
505 // OldCollector partition. Upon return, old_region_count holds the updated number of regions in the OldCollector partition.
506 void reserve_regions(size_t to_reserve, size_t old_reserve, size_t &old_region_count);
507
508 // Reserve space for evacuations, with regions reserved for old evacuations placed to the right
509 // of regions reserved of young evacuations.
510 void compute_young_and_old_reserves(size_t young_cset_regions, size_t old_cset_regions, bool have_evacuation_reserves,
511 size_t &young_reserve_result, size_t &old_reserve_result) const;
512 };
513
514 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP
|