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/shenandoahHeap.hpp"
30 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
31 #include "gc/shenandoah/shenandoahLock.hpp"
32 #include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
33 #include "logging/logStream.hpp"
34
35 typedef ShenandoahLock ShenandoahRebuildLock;
36 typedef ShenandoahLocker<ShenandoahRebuildLock> ShenandoahRebuildLocker;
37
38 // Each ShenandoahHeapRegion is associated with a ShenandoahFreeSetPartitionId.
39 enum class ShenandoahFreeSetPartitionId : uint8_t {
40 Mutator, // Region is in the Mutator free set: available memory is available to mutators.
41 Collector, // Region is in the Collector free set: available memory is reserved for evacuations.
42 OldCollector, // Region is in the Old Collector free set:
43 // available memory is reserved for old evacuations and for promotions.
44 NotFree // Region is in no free set: it has no available memory. Consult region affiliation
45 // to determine whether this retired region is young or old. If young, the region
46 // is considered to be part of the Mutator partition. (When we retire from the
47 // Collector partition, we decrease total_region_count for Collector and increaese
48 // for Mutator, making similar adjustments to used (net impact on available is neutral).
49 };
50
51 // ShenandoahRegionPartitions provides an abstraction to help organize the implementation of ShenandoahFreeSet. This
52 // class implements partitioning of regions into distinct sets. Each ShenandoahHeapRegion is either in the Mutator free set,
53 // the Collector free set, or in neither free set (NotFree). When we speak of a "free partition", we mean partitions that
54 // for which the ShenandoahFreeSetPartitionId is not equal to NotFree.
55 class ShenandoahRegionPartitions {
56
57 using idx_t = ShenandoahSimpleBitMap::idx_t;
58
59 public:
60 // We do not maintain counts, capacity, or used for regions that are not free. Informally, if a region is NotFree, it is
61 // in no partition. NumPartitions represents the size of an array that may be indexed by Mutator or Collector.
62 static constexpr ShenandoahFreeSetPartitionId NumPartitions = ShenandoahFreeSetPartitionId::NotFree;
63 static constexpr int IntNumPartitions = int(ShenandoahFreeSetPartitionId::NotFree);
64 static constexpr uint UIntNumPartitions = uint(ShenandoahFreeSetPartitionId::NotFree);
65
66 private:
67 const idx_t _max; // The maximum number of heap regions
68 const size_t _region_size_bytes;
69 const ShenandoahFreeSet* _free_set;
70 // For each partition, we maintain a bitmap of which regions are affiliated with his partition.
71 ShenandoahSimpleBitMap _membership[UIntNumPartitions];
72 // For each partition, we track an interval outside of which a region affiliated with that partition is guaranteed
73 // not to be found. This makes searches for free space more efficient. For each partition p, _leftmosts[p]
74 // represents its least index, and its _rightmosts[p] its greatest index. Empty intervals are indicated by the
75 // canonical [_max, -1].
76 idx_t _leftmosts[UIntNumPartitions];
77 idx_t _rightmosts[UIntNumPartitions];
78
79 // Allocation for humongous objects needs to find regions that are entirely empty. For each partion p, _leftmosts_empty[p]
80 // represents the first region belonging to this partition that is completely empty and _rightmosts_empty[p] represents the
81 // last region that is completely empty. If there is no completely empty region in this partition, this is represented
82 // by the canonical [_max, -1].
83 idx_t _leftmosts_empty[UIntNumPartitions];
84 idx_t _rightmosts_empty[UIntNumPartitions];
85
86 // For each partition p:
87 // _capacity[p] represents the total amount of memory within the partition, including retired regions, as adjusted
88 // by transfers of memory between partitions
89 // _used[p] represents the total amount of memory that has been allocated within this partition (either already
90 // allocated as of the rebuild, or allocated since the rebuild).
91 // _available[p] represents the total amount of memory that can be allocated within partition p, calculated from
92 // _capacity[p] minus _used[p], where the difference is computed and assigned under heap lock
93 //
94 // _region_counts[p] represents the number of regions associated with the partition which currently have available memory.
95 // When a region is retired from partition p, _region_counts[p] is decremented.
96 // total_region_counts[p] is _capacity[p] / RegionSizeBytes.
97 // _empty_region_counts[p] is number of regions associated with p which are entirely empty
98 //
99 // capacity and used values are expressed in bytes.
100 //
101 // When a region is retired, the used[p] is increased to account for alignment waste. capacity is unaffected.
102 //
103 // When a region is "flipped", we adjust capacities and region counts for original and destination partitions. We also
104 // adjust used values when flipping from mutator to collector. Flip to old collector does not need to adjust used because
105 // only empty regions can be flipped to old collector.
106 //
107 // All memory quantities (capacity, available, used) are represented in bytes.
108
109 size_t _capacity[UIntNumPartitions];
110
111 size_t _used[UIntNumPartitions];
112 size_t _available[UIntNumPartitions];
113
114 // Some notes:
115 // total_region_counts[p] is _capacity[p] / region_size_bytes
116 // retired_regions[p] is total_region_counts[p] - _region_counts[p]
117 // _empty_region_counts[p] <= _region_counts[p] <= total_region_counts[p]
118 // affiliated regions is total_region_counts[p] - empty_region_counts[p]
119 // used_regions is affilaited_regions * region_size_bytes
120 // _available[p] is _capacity[p] - _used[p]
121 size_t _region_counts[UIntNumPartitions];
122 size_t _empty_region_counts[UIntNumPartitions];
123
124 // Humongous waste, in bytes, can exist in Mutator partition for recently allocated humongous objects
125 // and in OldCollector partition for humongous objects that have been promoted in place.
126 size_t _humongous_waste[UIntNumPartitions];
127
128 // For each partition p, _left_to_right_bias is true iff allocations are normally made from lower indexed regions
129 // before higher indexed regions.
130 bool _left_to_right_bias[UIntNumPartitions];
131
132 inline bool is_mutator_partition(ShenandoahFreeSetPartitionId p);
133 inline bool is_young_collector_partition(ShenandoahFreeSetPartitionId p);
134 inline bool is_old_collector_partition(ShenandoahFreeSetPartitionId p);
135 inline bool available_implies_empty(size_t available);
136
137 #ifndef PRODUCT
138 void dump_bitmap_row(idx_t region_idx) const;
139 void dump_bitmap_range(idx_t start_region_idx, idx_t end_region_idx) const;
140 void dump_bitmap() const;
141 #endif
142 public:
143 ShenandoahRegionPartitions(size_t max_regions, ShenandoahFreeSet* free_set);
144 ~ShenandoahRegionPartitions() {}
145
146 inline idx_t max() const { return _max; }
147
148 // At initialization, reset OldCollector tallies
149 void initialize_old_collector();
150
151 // Remove all regions from all partitions and reset all bounds
152 void make_all_regions_unavailable();
153
154 // Set the partition id for a particular region without adjusting interval bounds or usage/capacity tallies
155 inline void raw_assign_membership(size_t idx, ShenandoahFreeSetPartitionId p) {
156 _membership[int(p)].set_bit(idx);
157 }
158
159 // Clear the partition id for a particular region without adjusting interval bounds or usage/capacity tallies
160 inline void raw_clear_membership(size_t idx, ShenandoahFreeSetPartitionId p) {
161 _membership[int(p)].clear_bit(idx);
162 }
163
164 inline void one_region_is_no_longer_empty(ShenandoahFreeSetPartitionId partition);
165
166 // Set the Mutator intervals, usage, and capacity according to arguments. Reset the Collector intervals, used, capacity
167 // to represent empty Collector free set. We use this at the end of rebuild_free_set() to avoid the overhead of making
168 // many redundant incremental adjustments to the mutator intervals as the free set is being rebuilt.
169 void establish_mutator_intervals(idx_t mutator_leftmost, idx_t mutator_rightmost,
170 idx_t mutator_leftmost_empty, idx_t mutator_rightmost_empty,
171 size_t total_mutator_regions, size_t empty_mutator_regions,
172 size_t mutator_region_count, size_t mutator_used, size_t mutator_humongous_words_waste);
173
174 // Set the OldCollector intervals, usage, and capacity according to arguments. We use this at the end of rebuild_free_set()
175 // to avoid the overhead of making many redundant incremental adjustments to the mutator intervals as the free set is being
176 // rebuilt.
177 void establish_old_collector_intervals(idx_t old_collector_leftmost, idx_t old_collector_rightmost,
178 idx_t old_collector_leftmost_empty, idx_t old_collector_rightmost_empty,
179 size_t total_old_collector_region_count, size_t old_collector_empty,
180 size_t old_collector_regions, size_t old_collector_used,
181 size_t old_collector_humongous_words_waste);
182
183 void establish_interval(ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx,
184 idx_t low_empty_idx, idx_t high_empty_idx);
185
186 // Shrink the intervals associated with partition when region idx is removed from this free set
187 inline void shrink_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, idx_t idx);
188
189 // Shrink the intervals associated with partition when regions low_idx through high_idx inclusive are removed from this free set
190 void shrink_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId partition,
191 idx_t low_idx, idx_t high_idx, size_t num_regions);
192
193 void expand_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, idx_t idx, size_t capacity);
194 void expand_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId partition,
195 idx_t low_idx, idx_t high_idx,
196 idx_t low_empty_idx, idx_t high_empty_idx);
197
198 // Retire region idx from within partition, , leaving its capacity and used as part of the original free partition's totals.
199 // Requires that region idx is in in the Mutator or Collector partitions. Hereafter, identifies this region as NotFree.
200 // Any remnant of available memory at the time of retirement is added to the original partition's total of used bytes.
201 // Return the number of waste bytes (if any).
202 size_t retire_from_partition(ShenandoahFreeSetPartitionId p, idx_t idx, size_t used_bytes);
203
204 // Retire all regions between low_idx and high_idx inclusive from within partition. Requires that each region idx is
205 // in the same Mutator or Collector partition. Hereafter, identifies each region as NotFree. Assumes that each region
206 // is now considered fully used, since the region is presumably used to represent a humongous object.
207 void retire_range_from_partition(ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx);
208
209 void unretire_to_partition(ShenandoahHeapRegion* region, ShenandoahFreeSetPartitionId which_partition);
210
211 // Place region idx into free set which_partition. Requires that idx is currently NotFree.
212 void make_free(idx_t idx, ShenandoahFreeSetPartitionId which_partition, size_t region_capacity);
213
214 // Place region idx into free partition new_partition, not adjusting used and capacity totals for the original and new partition.
215 // available represents bytes that can still be allocated within this region. Requires that idx is currently not NotFree.
216 size_t move_from_partition_to_partition_with_deferred_accounting(idx_t idx, ShenandoahFreeSetPartitionId orig_partition,
217 ShenandoahFreeSetPartitionId new_partition, size_t available);
218
219 // Place region idx into free partition new_partition, adjusting used and capacity totals for the original and new partition.
220 // available represents bytes that can still be allocated within this region. Requires that idx is currently not NotFree.
221 void move_from_partition_to_partition(idx_t idx, ShenandoahFreeSetPartitionId orig_partition,
222 ShenandoahFreeSetPartitionId new_partition, size_t available);
223
224 void transfer_used_capacity_from_to(ShenandoahFreeSetPartitionId from_partition, ShenandoahFreeSetPartitionId to_partition,
225 size_t regions);
226
227 // For recycled region r in the OldCollector partition but possibly not within the interval for empty OldCollector regions,
228 // expand the empty interval to include this region.
229 inline void adjust_interval_for_recycled_old_region_under_lock(ShenandoahHeapRegion* r);
230
231 const char* partition_membership_name(idx_t idx) const;
232
233 // Return the index of the next available region >= start_index, or maximum_regions if not found.
234 inline idx_t find_index_of_next_available_region(ShenandoahFreeSetPartitionId which_partition,
235 idx_t start_index) const;
236
237 // Return the index of the previous available region <= last_index, or -1 if not found.
238 inline idx_t find_index_of_previous_available_region(ShenandoahFreeSetPartitionId which_partition,
239 idx_t last_index) const;
240
241 // Return the index of the next available cluster of cluster_size regions >= start_index, or maximum_regions if not found.
242 inline idx_t find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId which_partition,
243 idx_t start_index, size_t cluster_size) const;
244
245 // Return the index of the previous available cluster of cluster_size regions <= last_index, or -1 if not found.
246 inline idx_t find_index_of_previous_available_cluster_of_regions(ShenandoahFreeSetPartitionId which_partition,
247 idx_t last_index, size_t cluster_size) const;
248
249 inline bool in_free_set(ShenandoahFreeSetPartitionId which_partition, idx_t idx) const {
250 return _membership[int(which_partition)].is_set(idx);
251 }
252
253 // Returns the ShenandoahFreeSetPartitionId affiliation of region idx, NotFree if this region is not currently in any partition.
254 // This does not enforce that free_set membership implies allocation capacity.
255 inline ShenandoahFreeSetPartitionId membership(idx_t idx) const {
256 assert (idx < _max, "index is sane: %zu < %zu", idx, _max);
257 ShenandoahFreeSetPartitionId result = ShenandoahFreeSetPartitionId::NotFree;
258 for (uint partition_id = 0; partition_id < UIntNumPartitions; partition_id++) {
259 if (_membership[partition_id].is_set(idx)) {
260 assert(result == ShenandoahFreeSetPartitionId::NotFree, "Region should reside in only one partition");
261 result = (ShenandoahFreeSetPartitionId) partition_id;
262 }
263 }
264 return result;
265 }
266
267 #ifdef ASSERT
268 // Returns true iff region idx's membership is which_partition. If which_partition represents a free set, asserts
269 // that the region has allocation capacity.
270 inline bool partition_id_matches(idx_t idx, ShenandoahFreeSetPartitionId which_partition) const;
271 #endif
272
273 inline size_t region_size_bytes() const { return _region_size_bytes; };
274
275 // The following four methods return the left-most and right-most bounds on ranges of regions representing
276 // the requested set. The _empty variants represent bounds on the range that holds completely empty
277 // regions, which are required for humongous allocations and desired for "very large" allocations.
278 // if the requested which_partition is empty:
279 // leftmost() and leftmost_empty() return _max, rightmost() and rightmost_empty() return 0
280 // otherwise, expect the following:
281 // 0 <= leftmost <= leftmost_empty <= rightmost_empty <= rightmost < _max
282 inline idx_t leftmost(ShenandoahFreeSetPartitionId which_partition) const;
283 inline idx_t rightmost(ShenandoahFreeSetPartitionId which_partition) const;
284 idx_t leftmost_empty(ShenandoahFreeSetPartitionId which_partition);
285 idx_t rightmost_empty(ShenandoahFreeSetPartitionId which_partition);
286
287 inline bool is_empty(ShenandoahFreeSetPartitionId which_partition) const;
288
289 inline void increase_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions);
290 inline void decrease_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions);
291 inline size_t get_region_counts(ShenandoahFreeSetPartitionId which_partition) {
292 assert (which_partition < NumPartitions, "selected free set must be valid");
293 return _region_counts[int(which_partition)];
294 }
295
296 inline void increase_empty_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions);
297 inline void decrease_empty_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions);
298 inline size_t get_empty_region_counts(ShenandoahFreeSetPartitionId which_partition) {
299 assert (which_partition < NumPartitions, "selected free set must be valid");
300 return _empty_region_counts[int(which_partition)];
301 }
302
303 inline void increase_capacity(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
304 inline void decrease_capacity(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
305 inline size_t get_capacity(ShenandoahFreeSetPartitionId which_partition) const {
306 assert (which_partition < NumPartitions, "Partition must be valid");
307 return _capacity[int(which_partition)];
308 }
309
310 inline size_t get_capacity_region_count(ShenandoahFreeSetPartitionId which_partition) const {
311 return get_capacity(which_partition) / ShenandoahHeapRegion::region_size_bytes();
312 }
313
314 inline void increase_available(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
315 inline void decrease_available(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
316 inline size_t get_available(ShenandoahFreeSetPartitionId which_partition);
317
318 inline void increase_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
319 inline void decrease_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
320 inline size_t get_used(ShenandoahFreeSetPartitionId which_partition) {
321 assert (which_partition < NumPartitions, "Partition must be valid");
322 return _used[int(which_partition)];
323 }
324
325 inline void increase_humongous_waste(ShenandoahFreeSetPartitionId which_partition, size_t bytes);
326 inline void decrease_humongous_waste(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
327 shenandoah_assert_heaplocked();
328 assert (which_partition < NumPartitions, "Partition must be valid");
329 assert(_humongous_waste[int(which_partition)] >= bytes, "Cannot decrease waste beyond what is there");
330 _humongous_waste[int(which_partition)] -= bytes;
331 }
332
333 inline size_t get_humongous_waste(ShenandoahFreeSetPartitionId which_partition);
334
335 inline void set_bias_from_left_to_right(ShenandoahFreeSetPartitionId which_partition, bool value) {
336 assert (which_partition < NumPartitions, "selected free set must be valid");
337 _left_to_right_bias[int(which_partition)] = value;
338 }
339
340 inline bool alloc_from_left_bias(ShenandoahFreeSetPartitionId which_partition) const {
341 assert (which_partition < NumPartitions, "selected free set must be valid");
342 return _left_to_right_bias[int(which_partition)];
343 }
344
345 inline size_t capacity_of(ShenandoahFreeSetPartitionId which_partition) const {
346 assert (which_partition < NumPartitions, "selected free set must be valid");
347 return _capacity[int(which_partition)];
348 }
349
350 inline size_t used_by(ShenandoahFreeSetPartitionId which_partition) const {
351 assert (which_partition < NumPartitions, "selected free set must be valid");
352 return _used[int(which_partition)];
353 }
354
355 inline size_t available_in(ShenandoahFreeSetPartitionId which_partition) const {
356 assert (which_partition < NumPartitions, "selected free set must be valid");
357 shenandoah_assert_heaplocked();
358 assert(_available[int(which_partition)] == _capacity[int(which_partition)] - _used[int(which_partition)],
359 "Expect available (%zu) equals capacity (%zu) - used (%zu) for partition %s",
360 _available[int(which_partition)], _capacity[int(which_partition)], _used[int(which_partition)],
361 partition_membership_name(idx_t(which_partition)));
362 return _available[int(which_partition)];
363 }
364
365 // Return available_in assuming caller does not hold the heap lock but does hold the rebuild_lock.
366 // The returned value may be "slightly stale" because we do not assure that every fetch of this value
367 // sees the most recent update of this value. Requiring the caller to hold the rebuild_lock assures
368 // that we don't see "bogus" values that are "worse than stale". During rebuild of the freeset, the
369 // value of _available is not reliable.
370 inline size_t available_in_locked_for_rebuild(ShenandoahFreeSetPartitionId which_partition) const {
371 assert (which_partition < NumPartitions, "selected free set must be valid");
372 return _available[int(which_partition)];
373 }
374
375 // Returns bytes of humongous waste
376 inline size_t humongous_waste(ShenandoahFreeSetPartitionId which_partition) const {
377 assert (which_partition < NumPartitions, "selected free set must be valid");
378 // This may be called with or without the global heap lock. Changes to _humongous_waste[] are always made with heap lock.
379 return _humongous_waste[int(which_partition)];
380 }
381
382 inline void set_capacity_of(ShenandoahFreeSetPartitionId which_partition, size_t value);
383
384 inline void set_used_by(ShenandoahFreeSetPartitionId which_partition, size_t value);
385
386 inline size_t count(ShenandoahFreeSetPartitionId which_partition) const { return _region_counts[int(which_partition)]; }
387
388 // Assure leftmost, rightmost, leftmost_empty, and rightmost_empty bounds are valid for all free sets.
389 // Valid bounds honor all of the following (where max is the number of heap regions):
390 // if the set is empty, leftmost equals max and rightmost equals 0
391 // Otherwise (the set is not empty):
392 // 0 <= leftmost < max and 0 <= rightmost < max
393 // the region at leftmost is in the set
394 // the region at rightmost is in the set
395 // rightmost >= leftmost
396 // for every idx that is in the set {
397 // idx >= leftmost &&
398 // idx <= rightmost
399 // }
400 // if the set has no empty regions, leftmost_empty equals max and rightmost_empty equals 0
401 // Otherwise (the region has empty regions):
402 // 0 <= leftmost_empty < max and 0 <= rightmost_empty < max
403 // rightmost_empty >= leftmost_empty
404 // for every idx that is in the set and is empty {
405 // idx >= leftmost &&
406 // idx <= rightmost
407 // }
408 void assert_bounds() NOT_DEBUG_RETURN;
409 // this checks certain sanity conditions related to the bounds with much less effort than is required to
410 // more rigorously enforce correctness as is done by assert_bounds()
411 inline void assert_bounds_sanity() NOT_DEBUG_RETURN;
412 };
413
414 // Publicly, ShenandoahFreeSet represents memory that is available to mutator threads. The public capacity(), used(),
415 // and available() methods represent this public notion of memory that is under control of the mutator. Separately,
416 // ShenandoahFreeSet also represents memory available to garbage collection activities for compaction purposes.
417 //
418 // The Shenandoah garbage collector evacuates live objects out of specific regions that are identified as members of the
419 // collection set (cset).
420 //
421 // The ShenandoahFreeSet tries to colocate survivor objects (objects that have been evacuated at least once) at the
422 // high end of memory. New mutator allocations are taken from the low end of memory. Within the mutator's range of regions,
423 // humongous allocations are taken from the lowest addresses, and LAB (local allocation buffers) and regular shared allocations
424 // are taken from the higher address of the mutator's range of regions. This approach allows longer lasting survivor regions
425 // to congregate at the top of the heap and longer lasting humongous regions to congregate at the bottom of the heap, with
426 // short-lived frequently evacuated regions occupying the middle of the heap.
427 //
428 // Mutator and garbage collection activities tend to scramble the content of regions. Twice, during each GC pass, we rebuild
429 // the free set in an effort to restore the efficient segregation of Collector and Mutator regions:
430 //
431 // 1. At the start of evacuation, we know exactly how much memory is going to be evacuated, and this guides our
432 // sizing of the Collector free set.
433 //
434 // 2. At the end of GC, we have reclaimed all of the memory that was spanned by the cset. We rebuild here to make
435 // sure there is enough memory reserved at the high end of memory to hold the objects that might need to be evacuated
436 // during the next GC pass.
437
438 class ShenandoahFreeSet : public CHeapObj<mtGC> {
439 using idx_t = ShenandoahSimpleBitMap::idx_t;
440 private:
441 ShenandoahHeap* const _heap;
442 ShenandoahRegionPartitions _partitions;
443
444 // Temporarily holds mutator_Free allocatable bytes between prepare_to_rebuild() and finish_rebuild()
445 size_t _prepare_to_rebuild_mutator_free;
446
447 // This locks the rebuild process (in combination with the global heap lock). Whenever we rebuild the free set,
448 // we first acquire the global heap lock and then we acquire this _rebuild_lock in a nested context. Threads that
449 // need to check available, acquire only the _rebuild_lock to make sure that they are not obtaining the value of
450 // available for a partially reconstructed free-set.
451 //
452 // Note that there is rank ordering of nested locks to prevent deadlock. All threads that need to acquire both
453 // locks will acquire them in the same order: first the global heap lock and then the rebuild lock.
454 ShenandoahRebuildLock _rebuild_lock;
455
456
457 size_t _total_humongous_waste;
458
459 // We re-evaluate the left-to-right allocation bias whenever _alloc_bias_weight is less than zero. Each time
460 // we allocate an object, we decrement the count of this value. Each time we re-evaluate whether to allocate
461 // from right-to-left or left-to-right, we reset the value of this counter to _InitialAllocBiasWeight.
462 ssize_t _alloc_bias_weight;
463
464 const ssize_t INITIAL_ALLOC_BIAS_WEIGHT = 256;
465
466 // bytes used by young
467 size_t _total_young_used;
468 template<bool UsedByMutatorChanged, bool UsedByCollectorChanged>
469 inline void recompute_total_young_used() {
470 if (UsedByMutatorChanged || UsedByCollectorChanged) {
471 shenandoah_assert_heaplocked();
472 _total_young_used = (_partitions.used_by(ShenandoahFreeSetPartitionId::Mutator) +
473 _partitions.used_by(ShenandoahFreeSetPartitionId::Collector));
474 }
475 }
476
477 // bytes used by old
478 size_t _total_old_used;
479 template<bool UsedByOldCollectorChanged>
480 inline void recompute_total_old_used() {
481 if (UsedByOldCollectorChanged) {
482 shenandoah_assert_heaplocked();
483 _total_old_used =_partitions.used_by(ShenandoahFreeSetPartitionId::OldCollector);
484 }
485 }
486
487 public:
488 // We make this public so that native code can see its value
489 // bytes used by global
490 size_t _total_global_used;
491 private:
492 // Prerequisite: _total_young_used and _total_old_used are valid
493 template<bool UsedByMutatorChanged, bool UsedByCollectorChanged, bool UsedByOldCollectorChanged>
494 inline void recompute_total_global_used() {
495 if (UsedByMutatorChanged || UsedByCollectorChanged || UsedByOldCollectorChanged) {
496 shenandoah_assert_heaplocked();
497 _total_global_used = _total_young_used + _total_old_used;
498 }
499 }
500
501 template<bool UsedByMutatorChanged, bool UsedByCollectorChanged, bool UsedByOldCollectorChanged>
502 inline void recompute_total_used() {
503 recompute_total_young_used<UsedByMutatorChanged, UsedByCollectorChanged>();
504 recompute_total_old_used<UsedByOldCollectorChanged>();
505 recompute_total_global_used<UsedByMutatorChanged, UsedByCollectorChanged, UsedByOldCollectorChanged>();
506 }
507
508 size_t _young_affiliated_regions;
509 size_t _old_affiliated_regions;
510 size_t _global_affiliated_regions;
511
512 size_t _young_unaffiliated_regions;
513 size_t _global_unaffiliated_regions;
514
515 size_t _total_young_regions;
516 size_t _total_global_regions;
517
518 // If only affiliation changes are promote-in-place and generation sizes have not changed,
519 // we have AffiliatedChangesAreGlobalNeutral
520 // If only affiliation changes are non-empty regions moved from Mutator to Collector and young size has not changed,
521 // we have AffiliatedChangesAreYoungNeutral
522 // If only unaffiliated changes are empty regions from Mutator to/from Collector, we have UnaffiliatedChangesAreYoungNeutral
523 template<bool MutatorEmptiesChanged, bool CollectorEmptiesChanged, bool OldCollectorEmptiesChanged,
524 bool MutatorSizeChanged, bool CollectorSizeChanged, bool OldCollectorSizeChanged,
525 bool AffiliatedChangesAreYoungNeutral, bool AffiliatedChangesAreGlobalNeutral,
526 bool UnaffiliatedChangesAreYoungNeutral>
527 inline void recompute_total_affiliated() {
528 shenandoah_assert_heaplocked();
529 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
530 if (!UnaffiliatedChangesAreYoungNeutral && (MutatorEmptiesChanged || CollectorEmptiesChanged)) {
531 _young_unaffiliated_regions = (_partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Mutator) +
532 _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Collector));
533 }
534 if (!AffiliatedChangesAreYoungNeutral &&
535 (MutatorSizeChanged || CollectorSizeChanged || MutatorEmptiesChanged || CollectorEmptiesChanged)) {
536 _young_affiliated_regions = ((_partitions.get_capacity(ShenandoahFreeSetPartitionId::Mutator) +
537 _partitions.get_capacity(ShenandoahFreeSetPartitionId::Collector)) / region_size_bytes -
538 _young_unaffiliated_regions);
539 }
540 if (OldCollectorSizeChanged || OldCollectorEmptiesChanged) {
541 _old_affiliated_regions = (_partitions.get_capacity(ShenandoahFreeSetPartitionId::OldCollector) / region_size_bytes -
542 _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector));
543 }
544 if (!AffiliatedChangesAreGlobalNeutral &&
545 (MutatorEmptiesChanged || CollectorEmptiesChanged || OldCollectorEmptiesChanged)) {
546 _global_unaffiliated_regions =
547 _young_unaffiliated_regions + _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector);
548 }
549 if (!AffiliatedChangesAreGlobalNeutral &&
550 (MutatorSizeChanged || CollectorSizeChanged || MutatorEmptiesChanged || CollectorEmptiesChanged ||
551 OldCollectorSizeChanged || OldCollectorEmptiesChanged)) {
552 _global_affiliated_regions = _young_affiliated_regions + _old_affiliated_regions;
553 }
554 #ifdef ASSERT
555 if (ShenandoahHeap::heap()->mode()->is_generational()) {
556 assert(_young_affiliated_regions * ShenandoahHeapRegion::region_size_bytes() >= _total_young_used, "sanity");
557 assert(_old_affiliated_regions * ShenandoahHeapRegion::region_size_bytes() >= _total_old_used, "sanity");
558 }
559 assert(_global_affiliated_regions * ShenandoahHeapRegion::region_size_bytes() >= _total_global_used, "sanity");
560 #endif
561 }
562
563 // Increases used memory for the partition if the allocation is successful. `in_new_region` will be set
564 // if this is the first allocation in the region.
565 HeapWord* try_allocate_in(ShenandoahHeapRegion* region, ShenandoahAllocRequest& req, bool& in_new_region);
566
567 // While holding the heap lock, allocate memory for a single object or LAB which is to be entirely contained
568 // within a single HeapRegion as characterized by req.
569 //
570 // Precondition: !ShenandoahHeapRegion::requires_humongous(req.size())
571 HeapWord* allocate_single(ShenandoahAllocRequest& req, bool& in_new_region);
572
573 // While holding the heap lock, allocate memory for a humongous object which spans one or more regions that
574 // were previously empty. Regions that represent humongous objects are entirely dedicated to the humongous
575 // object. No other objects are packed into these regions.
576 //
577 // Precondition: ShenandoahHeapRegion::requires_humongous(req.size())
578 HeapWord* allocate_contiguous(ShenandoahAllocRequest& req, bool is_humongous);
579
580 bool transfer_one_region_from_mutator_to_old_collector(size_t idx, size_t alloc_capacity);
581
582 // Change region r from the Mutator partition to the GC's Collector or OldCollector partition. This requires that the
583 // region is entirely empty.
584 //
585 // Typical usage: During evacuation, the GC may find it needs more memory than had been reserved at the start of evacuation to
586 // hold evacuated objects. If this occurs and memory is still available in the Mutator's free set, we will flip a region from
587 // the Mutator free set into the Collector or OldCollector free set. The conditions to move this region are checked by
588 // the caller, so the given region is always moved.
589 void flip_to_gc(ShenandoahHeapRegion* r);
590
591 // Return true if and only if the given region is successfully flipped to the old partition
592 bool flip_to_old_gc(ShenandoahHeapRegion* r);
593
594 // Handle allocation for mutator.
595 HeapWord* allocate_for_mutator(ShenandoahAllocRequest &req, bool &in_new_region);
596
597 // Update allocation bias and decided whether to allocate from the left or right side of the heap.
598 void update_allocation_bias();
599
600 // Search for regions to satisfy allocation request using iterator.
601 template<typename Iter>
602 HeapWord* allocate_from_regions(Iter& iterator, ShenandoahAllocRequest &req, bool &in_new_region);
603
604 // Handle allocation for collector (for evacuation).
605 HeapWord* allocate_for_collector(ShenandoahAllocRequest& req, bool& in_new_region);
606
607 // Search for allocation in region with same affiliation as request, using given iterator,
608 // or affiliate the first usable FREE region with given affiliation and allocate in.
609 template<typename Iter>
610 HeapWord* allocate_with_affiliation(Iter& iterator,
611 ShenandoahAffiliation affiliation,
612 ShenandoahAllocRequest& req,
613 bool& in_new_region);
614
615 // Attempt to allocate memory for an evacuation from the mutator's partition.
616 HeapWord* try_allocate_from_mutator(ShenandoahAllocRequest& req, bool& in_new_region);
617
618 void clear_internal();
619
620 // Returns true iff this region is entirely available, either because it is empty() or because it has been found to represent
621 // immediate trash and we'll be able to immediately recycle it. Note that we cannot recycle immediate trash if
622 // concurrent weak root processing is in progress.
623 inline bool can_allocate_from(ShenandoahHeapRegion *r) const;
624 inline bool can_allocate_from(size_t idx) const;
625
626 inline bool has_alloc_capacity(ShenandoahHeapRegion *r) const;
627
628 void transfer_empty_regions_from_to(ShenandoahFreeSetPartitionId source_partition,
629 ShenandoahFreeSetPartitionId dest_partition,
630 size_t num_regions);
631
632 size_t transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
633 size_t max_xfer_regions,
634 size_t& bytes_transferred);
635 size_t transfer_non_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
636 size_t max_xfer_regions,
637 size_t& bytes_transferred);
638
639 // Determine whether we prefer to allocate from left to right or from right to left within the OldCollector free-set.
640 void establish_old_collector_alloc_bias();
641
642 void reduce_young_reserve(size_t adjusted_young_reserve, size_t requested_young_reserve);
643 void reduce_old_reserve(size_t adjusted_old_reserve, size_t requested_old_reserve);
644
645 void log_freeset_stats(ShenandoahFreeSetPartitionId partition_id, LogStream& ls);
646
647 // log status, assuming lock has already been acquired by the caller.
648 void log_status();
649
650 public:
651 ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions);
652
653 ShenandoahRebuildLock* rebuild_lock() {
654 return &_rebuild_lock;
655 }
656
657 inline size_t max_regions() const { return _partitions.max(); }
658 ShenandoahFreeSetPartitionId membership(size_t index) const { return _partitions.membership(index); }
659 inline void shrink_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId partition,
660 idx_t low_idx, idx_t high_idx, size_t num_regions) {
661 return _partitions.shrink_interval_if_range_modifies_either_boundary(partition, low_idx, high_idx, num_regions);
662 }
663
664 // Public because ShenandoahRegionPartitions assertions require access.
665 inline size_t alloc_capacity(ShenandoahHeapRegion *r) const;
666 inline size_t alloc_capacity(size_t idx) const;
667
668 // Return bytes used by old
669 inline size_t old_used() {
670 return _total_old_used;
671 }
672
673 ShenandoahFreeSetPartitionId prepare_to_promote_in_place(size_t idx, size_t bytes);
674 void account_for_pip_regions(size_t mutator_regions, size_t mutator_bytes, size_t collector_regions, size_t collector_bytes);
675
676 // This is used for unit testing. Not for preoduction. Invokes exit() if old cannot be resized.
677 void resize_old_collector_capacity(size_t desired_regions);
678
679 // Return bytes used by young
680 inline size_t young_used() {
681 return _total_young_used;
682 }
683
684 // Return bytes used by global
685 inline size_t global_used() {
686 return _total_global_used;
687 }
688
689 // A negative argument results in moving from old_collector to collector
690 void move_unaffiliated_regions_from_collector_to_old_collector(ssize_t regions);
691
692 inline size_t global_unaffiliated_regions() {
693 return _global_unaffiliated_regions;
694 }
695
696 inline size_t young_unaffiliated_regions() {
697 return _young_unaffiliated_regions;
698 }
699
700 inline size_t collector_unaffiliated_regions() {
701 return _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Collector);
702 }
703
704 inline size_t old_collector_unaffiliated_regions() {
705 return _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector);
706 }
707
708 inline size_t old_unaffiliated_regions() {
709 return _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector);
710 }
711
712 inline size_t young_affiliated_regions() {
713 return _young_affiliated_regions;
714 }
715
716 inline size_t old_affiliated_regions() {
717 return _old_affiliated_regions;
718 }
719
720 inline size_t global_affiliated_regions() {
721 return _global_affiliated_regions;
722 }
723
724 inline size_t total_young_regions() {
725 return _total_young_regions;
726 }
727
728 inline size_t total_old_regions() {
729 return _partitions.get_capacity_region_count(ShenandoahFreeSetPartitionId::OldCollector);
730 }
731
732 size_t total_global_regions() {
733 return _total_global_regions;
734 }
735
736 void clear();
737
738 // Examine the existing free set representation, capturing the current state into var arguments:
739 //
740 // young_trashed_regions is the number of trashed regions (immediate garbage at final mark, cset regions after update refs)
741 // old_trashed_regions is the number of trashed regions
742 // (immediate garbage at final old mark, cset regions after update refs for mixed evac)
743 // first_old_region is the index of the first region that is part of the OldCollector set
744 // last_old_region is the index of the last region that is part of the OldCollector set
745 // old_region_count is the number of regions in the OldCollector set that have memory available to be allocated
746 void prepare_to_rebuild(size_t &young_trashed_regions, size_t &old_trashed_regions,
747 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
748
749 // At the end of final mark, but before we begin evacuating, heuristics calculate how much memory is required to
750 // hold the results of evacuating to young-gen and to old-gen. These quantities, stored in reserves for their
751 // respective generations, are consulted prior to rebuilding the free set (ShenandoahFreeSet) in preparation for
752 // evacuation. When the free set is rebuilt, we make sure to reserve sufficient memory in the collector and
753 // old_collector sets to hold evacuations. Likewise, at the end of update refs, we rebuild the free set in order
754 // to set aside reserves to be consumed during the next GC cycle.
755 //
756 // young_trashed_regions is the number of trashed regions (immediate garbage at final mark, cset regions after update refs)
757 // old_trashed_regions is the number of trashed regions
758 // (immediate garbage at final old mark, cset regions after update refs for mixed evac)
759 // num_old_regions is the number of old-gen regions that have available memory for further allocations (excluding old cset)
760 void finish_rebuild(size_t young_trashed_regions, size_t old_trashed_regions, size_t num_old_regions);
761
762 // When a region is promoted in place, we add the region's available memory if it is greater than plab_min_size()
763 // into the old collector partition by invoking this method.
764 void add_promoted_in_place_region_to_old_collector(ShenandoahHeapRegion* region);
765
766 // Move up to cset_regions number of regions from being available to the collector to being available to the mutator.
767 //
768 // Typical usage: At the end of evacuation, when the collector no longer needs the regions that had been reserved
769 // for evacuation, invoke this to make regions available for mutator allocations.
770 void move_regions_from_collector_to_mutator(size_t cset_regions);
771
772 void transfer_humongous_regions_from_mutator_to_old_collector(size_t xfer_regions, size_t humongous_waste_words);
773
774 void recycle_trash();
775
776 // Acquire heap lock and log status, assuming heap lock is not acquired by the caller.
777 void log_status_under_lock();
778
779 // All four of the following functions may produce stale data if called without owning the global heap lock.
780 // Changes to the values of these variables are performed with a lock. A change to capacity or used "atomically"
781 // adjusts available with respect to lock holders. However, sequential calls to these three functions may produce
782 // inconsistent data: available may not equal capacity - used because the intermediate states of any "atomic"
783 // locked action can be seen by these unlocked functions.
784
785 // Note that capacity is the number of regions that had available memory at most recent rebuild. It is not the
786 // entire size of the young or global generation. (Regions within the generation that were fully utilized at time of
787 // rebuild are not counted as part of capacity.)
788 inline size_t capacity_holding_lock() const {
789 shenandoah_assert_heaplocked();
790 return _partitions.capacity_of(ShenandoahFreeSetPartitionId::Mutator);
791 }
792 inline size_t capacity_not_holding_lock() {
793 shenandoah_assert_not_heaplocked();
794 ShenandoahRebuildLocker locker(rebuild_lock());
795 return _partitions.capacity_of(ShenandoahFreeSetPartitionId::Mutator);
796 }
797 inline size_t used_holding_lock() const {
798 shenandoah_assert_heaplocked();
799 return _partitions.used_by(ShenandoahFreeSetPartitionId::Mutator);
800 }
801 inline size_t used_not_holding_lock() {
802 shenandoah_assert_not_heaplocked();
803 ShenandoahRebuildLocker locker(rebuild_lock());
804 return _partitions.used_by(ShenandoahFreeSetPartitionId::Mutator);
805 }
806 inline size_t reserved() const { return _partitions.capacity_of(ShenandoahFreeSetPartitionId::Collector); }
807 inline size_t available() {
808 shenandoah_assert_not_heaplocked();
809 ShenandoahRebuildLocker locker(rebuild_lock());
810 return _partitions.available_in_locked_for_rebuild(ShenandoahFreeSetPartitionId::Mutator);
811 }
812
813 // Use this version of available() if the heap lock is held.
814 inline size_t available_locked() const {
815 return _partitions.available_in(ShenandoahFreeSetPartitionId::Mutator);
816 }
817
818 inline size_t collector_available_locked() const {
819 return _partitions.available_in(ShenandoahFreeSetPartitionId::Collector);
820 }
821
822 inline size_t old_collector_available_locked() const {
823 return _partitions.available_in(ShenandoahFreeSetPartitionId::OldCollector);
824 }
825
826 inline size_t total_humongous_waste() const { return _total_humongous_waste; }
827 inline size_t humongous_waste_in_mutator() const {
828 return _partitions.humongous_waste(ShenandoahFreeSetPartitionId::Mutator);
829 }
830 inline size_t humongous_waste_in_old() const {
831 return _partitions.humongous_waste(ShenandoahFreeSetPartitionId::OldCollector);
832 }
833
834 void decrease_humongous_waste_for_regular_bypass(ShenandoahHeapRegion* r, size_t waste);
835
836 HeapWord* allocate(ShenandoahAllocRequest& req, bool& in_new_region);
837
838 /*
839 * Internal fragmentation metric: describes how fragmented the heap regions are.
840 *
841 * It is derived as:
842 *
843 * sum(used[i]^2, i=0..k)
844 * IF = 1 - ------------------------------
845 * C * sum(used[i], i=0..k)
846 *
847 * ...where k is the number of regions in computation, C is the region capacity, and
848 * used[i] is the used space in the region.
849 *
850 * The non-linearity causes IF to be lower for the cases where the same total heap
851 * used is densely packed. For example:
852 * a) Heap is completely full => IF = 0
853 * b) Heap is half full, first 50% regions are completely full => IF = 0
854 * c) Heap is half full, each region is 50% full => IF = 1/2
855 * d) Heap is quarter full, first 50% regions are completely full => IF = 0
856 * e) Heap is quarter full, each region is 25% full => IF = 3/4
857 * f) Heap has one small object per each region => IF =~ 1
858 */
859 double internal_fragmentation();
860
861 /*
862 * External fragmentation metric: describes how fragmented the heap is.
863 *
864 * It is derived as:
865 *
866 * EF = 1 - largest_contiguous_free / total_free
867 *
868 * For example:
869 * a) Heap is completely empty => EF = 0
870 * b) Heap is completely full => EF = 0
871 * c) Heap is first-half full => EF = 1/2
872 * d) Heap is half full, full and empty regions interleave => EF =~ 1
873 */
874 double external_fragmentation();
875
876 void print_on(outputStream* out) const;
877
878 // This function places all regions that have allocation capacity into the mutator partition, or if the region
879 // is already affiliated with old, into the old collector partition, identifying regions that have no allocation
880 // capacity as NotFree. Capture the modified state of the freeset into var arguments:
881 //
882 // young_cset_regions is the number of regions currently in the young cset if we are starting to evacuate, or zero
883 // old_cset_regions is the number of regions currently in the old cset if we are starting a mixed evacuation, or zero
884 // first_old_region is the index of the first region that is part of the OldCollector set
885 // last_old_region is the index of the last region that is part of the OldCollector set
886 // old_region_count is the number of regions in the OldCollector set that have memory available to be allocated
887 //
888 // Returns allocatable memory within Mutator partition, in words.
889 size_t find_regions_with_alloc_capacity(size_t &young_cset_regions, size_t &old_cset_regions,
890 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count);
891
892 // Ensure that Collector has at least to_reserve bytes of available memory, and OldCollector has at least old_reserve
893 // bytes of available memory. On input, old_region_count holds the number of regions already present in the
894 // OldCollector partition. Upon return, old_region_count holds the updated number of regions in the OldCollector partition.
895 //
896 // Returns allocatable memory within Mutator partition, in words.
897 size_t reserve_regions(size_t to_reserve, size_t old_reserve, size_t &old_region_count,
898 size_t &young_used_regions, size_t &old_used_regions, size_t &young_used_bytes, size_t &old_used_bytes);
899
900 // Reserve space for evacuations, with regions reserved for old evacuations placed to the right
901 // of regions reserved of young evacuations.
902 void compute_young_and_old_reserves(size_t young_cset_regions, size_t old_cset_regions,
903 size_t &young_reserve_result, size_t &old_reserve_result) const;
904 };
905
906 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHFREESET_HPP