1 /*
2 * Copyright (c) 2016, 2021, Red Hat, Inc. All rights reserved.
3 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
4 * Copyright (c) 2025, Oracle and/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 #include "gc/shared/tlab_globals.hpp"
28 #include "gc/shenandoah/shenandoahAffiliation.hpp"
29 #include "gc/shenandoah/shenandoahFreeSet.hpp"
30 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
31 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
32 #include "gc/shenandoah/shenandoahMarkingContext.inline.hpp"
33 #include "gc/shenandoah/shenandoahOldGeneration.hpp"
34 #include "gc/shenandoah/shenandoahSimpleBitMap.inline.hpp"
35 #include "gc/shenandoah/shenandoahYoungGeneration.hpp"
36 #include "logging/logStream.hpp"
37 #include "memory/resourceArea.hpp"
38 #include "runtime/orderAccess.hpp"
39
40 static const char* partition_name(ShenandoahFreeSetPartitionId t) {
41 switch (t) {
42 case ShenandoahFreeSetPartitionId::NotFree: return "NotFree";
43 case ShenandoahFreeSetPartitionId::Mutator: return "Mutator";
44 case ShenandoahFreeSetPartitionId::Collector: return "Collector";
45 case ShenandoahFreeSetPartitionId::OldCollector: return "OldCollector";
46 default:
47 ShouldNotReachHere();
48 return "Unrecognized";
49 }
50 }
51
52 class ShenandoahLeftRightIterator {
53 private:
54 idx_t _idx;
55 idx_t _end;
56 ShenandoahRegionPartitions* _partitions;
57 ShenandoahFreeSetPartitionId _partition;
58 public:
59 explicit ShenandoahLeftRightIterator(ShenandoahRegionPartitions* partitions,
60 ShenandoahFreeSetPartitionId partition, bool use_empty = false)
61 : _idx(0), _end(0), _partitions(partitions), _partition(partition) {
62 _idx = use_empty ? _partitions->leftmost_empty(_partition) : _partitions->leftmost(_partition);
63 _end = use_empty ? _partitions->rightmost_empty(_partition) : _partitions->rightmost(_partition);
64 }
65
66 bool has_next() const {
67 if (_idx <= _end) {
68 assert(_partitions->in_free_set(_partition, _idx), "Boundaries or find_last_set_bit failed: %zd", _idx);
69 return true;
70 }
71 return false;
72 }
73
74 idx_t current() const {
75 return _idx;
76 }
77
78 idx_t next() {
79 _idx = _partitions->find_index_of_next_available_region(_partition, _idx + 1);
80 return current();
81 }
82 };
83
84 class ShenandoahRightLeftIterator {
85 private:
86 idx_t _idx;
87 idx_t _end;
88 ShenandoahRegionPartitions* _partitions;
89 ShenandoahFreeSetPartitionId _partition;
90 public:
91 explicit ShenandoahRightLeftIterator(ShenandoahRegionPartitions* partitions,
92 ShenandoahFreeSetPartitionId partition, bool use_empty = false)
93 : _idx(0), _end(0), _partitions(partitions), _partition(partition) {
94 _idx = use_empty ? _partitions->rightmost_empty(_partition) : _partitions->rightmost(_partition);
95 _end = use_empty ? _partitions->leftmost_empty(_partition) : _partitions->leftmost(_partition);
96 }
97
98 bool has_next() const {
99 if (_idx >= _end) {
100 assert(_partitions->in_free_set(_partition, _idx), "Boundaries or find_last_set_bit failed: %zd", _idx);
101 return true;
102 }
103 return false;
104 }
105
106 idx_t current() const {
107 return _idx;
108 }
109
110 idx_t next() {
111 _idx = _partitions->find_index_of_previous_available_region(_partition, _idx - 1);
112 return current();
113 }
114 };
115
116 #ifndef PRODUCT
117 void ShenandoahRegionPartitions::dump_bitmap() const {
118 log_debug(gc)("Mutator range [%zd, %zd], Collector range [%zd, %zd"
119 "], Old Collector range [%zd, %zd]",
120 _leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)],
121 _rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)],
122 _leftmosts[int(ShenandoahFreeSetPartitionId::Collector)],
123 _rightmosts[int(ShenandoahFreeSetPartitionId::Collector)],
124 _leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)],
125 _rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)]);
126 log_debug(gc)("Empty Mutator range [%zd, %zd"
127 "], Empty Collector range [%zd, %zd"
128 "], Empty Old Collecto range [%zd, %zd]",
129 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
130 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
131 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
132 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
133 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
134 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)]);
135
136 log_debug(gc)("%6s: %18s %18s %18s %18s", "index", "Mutator Bits", "Collector Bits", "Old Collector Bits", "NotFree Bits");
137 dump_bitmap_range(0, _max-1);
138 }
139
140 void ShenandoahRegionPartitions::dump_bitmap_range(idx_t start_region_idx, idx_t end_region_idx) const {
141 assert((start_region_idx >= 0) && (start_region_idx < (idx_t) _max), "precondition");
142 assert((end_region_idx >= 0) && (end_region_idx < (idx_t) _max), "precondition");
143 idx_t aligned_start = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(start_region_idx);
144 idx_t aligned_end = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(end_region_idx);
145 idx_t alignment = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].alignment();
146 while (aligned_start <= aligned_end) {
147 dump_bitmap_row(aligned_start);
148 aligned_start += alignment;
149 }
150 }
151
152 void ShenandoahRegionPartitions::dump_bitmap_row(idx_t region_idx) const {
153 assert((region_idx >= 0) && (region_idx < (idx_t) _max), "precondition");
154 idx_t aligned_idx = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(region_idx);
155 uintx mutator_bits = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].bits_at(aligned_idx);
156 uintx collector_bits = _membership[int(ShenandoahFreeSetPartitionId::Collector)].bits_at(aligned_idx);
157 uintx old_collector_bits = _membership[int(ShenandoahFreeSetPartitionId::OldCollector)].bits_at(aligned_idx);
158 uintx free_bits = mutator_bits | collector_bits | old_collector_bits;
159 uintx notfree_bits = ~free_bits;
160 log_debug(gc)("%6zd : " SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0,
161 aligned_idx, mutator_bits, collector_bits, old_collector_bits, notfree_bits);
162 }
163 #endif
164
165 ShenandoahRegionPartitions::ShenandoahRegionPartitions(size_t max_regions, ShenandoahFreeSet* free_set) :
166 _max(max_regions),
167 _region_size_bytes(ShenandoahHeapRegion::region_size_bytes()),
168 _free_set(free_set),
169 _membership{ ShenandoahSimpleBitMap(max_regions), ShenandoahSimpleBitMap(max_regions) , ShenandoahSimpleBitMap(max_regions) }
170 {
171 initialize_old_collector();
172 make_all_regions_unavailable();
173 }
174
175 void ShenandoahFreeSet::account_for_pip_regions(size_t mutator_regions, size_t mutator_bytes,
176 size_t collector_regions, size_t collector_bytes) {
177 shenandoah_assert_heaplocked();
178
179 // We have removed all of these regions from their respective partition. Each pip region is "in" the NotFree partition.
180 // We want to account for all pip pad memory as if it had been consumed from within the Mutator partition.
181 //
182 // After we finish promote in place, the pad memory will be deallocated and made available within the OldCollector
183 // region. At that time, we will transfer the used memory from the Mutator partition to the OldCollector parttion,
184 // and then we will unallocate the pad memory.
185
186
187 _partitions.decrease_region_counts(ShenandoahFreeSetPartitionId::Mutator, mutator_regions);
188 _partitions.decrease_region_counts(ShenandoahFreeSetPartitionId::Collector, collector_regions);
189
190 // Increase used by remnant fill objects placed in both Mutator and Collector partitions
191 _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, mutator_bytes);
192 _partitions.increase_used(ShenandoahFreeSetPartitionId::Collector, collector_bytes);
193
194 // Now transfer all of the memory contained within Collector pip regions from the Collector to the Mutator.
195 // Each of these regions is treated as fully used, even though some of the region's memory may be artifically used,
196 // to be recycled and put into allocatable OldCollector partition after the region has been promoted in place.
197 _partitions.transfer_used_capacity_from_to(ShenandoahFreeSetPartitionId::Collector, ShenandoahFreeSetPartitionId::Mutator,
198 collector_regions);
199
200 // Conservatively, act as if we've promoted from both Mutator and Collector partitions
201 recompute_total_affiliated</* MutatorEmptiesChanged */ false, /* CollectorEmptiesChanged */ false,
202 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ true,
203 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ false,
204 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
205 /* UnaffiliatedChangesAreYoungNeutral */ false>();
206 recompute_total_young_used</* UsedByMutatorChanged */ true, /*UsedByCollectorChanged */ true>();
207 recompute_total_global_used</* UsedByMutatorChanged */ true, /* UsedByCollectorChanged */ true,
208 /* UsedByOldCollectorChanged */ false>();
209 }
210
211 ShenandoahFreeSetPartitionId ShenandoahFreeSet::prepare_to_promote_in_place(size_t idx, size_t bytes) {
212 shenandoah_assert_heaplocked();
213 size_t min_remnant_size = PLAB::min_size() * HeapWordSize;
214 ShenandoahFreeSetPartitionId p = _partitions.membership(idx);
215 if (bytes >= min_remnant_size) {
216 assert((p == ShenandoahFreeSetPartitionId::Mutator) || (p == ShenandoahFreeSetPartitionId::Collector),
217 "PIP region must be associated with young");
218 _partitions.raw_clear_membership(idx, p);
219 } else {
220 assert(p == ShenandoahFreeSetPartitionId::NotFree, "We did not fill this region and do not need to adjust used");
221 }
222 return p;
223 }
224
225 inline bool ShenandoahFreeSet::can_allocate_from(ShenandoahHeapRegion *r) const {
226 const auto state = r->state();
227 return ShenandoahHeapRegion::is_empty_state(state)
228 || (ShenandoahHeapRegion::is_trash(state) && !_heap->is_concurrent_weak_root_in_progress());
229 }
230
231 inline bool ShenandoahFreeSet::can_allocate_from(size_t idx) const {
232 ShenandoahHeapRegion* r = _heap->get_region(idx);
233 return can_allocate_from(r);
234 }
235
236 inline size_t ShenandoahFreeSet::alloc_capacity(ShenandoahHeapRegion *r) const {
237 if (r->is_trash()) {
238 // This would be recycled on allocation path
239 return ShenandoahHeapRegion::region_size_bytes();
240 } else {
241 return r->free();
242 }
243 }
244
245 inline size_t ShenandoahFreeSet::alloc_capacity(size_t idx) const {
246 ShenandoahHeapRegion* r = _heap->get_region(idx);
247 return alloc_capacity(r);
248 }
249
250 inline bool ShenandoahFreeSet::has_alloc_capacity(ShenandoahHeapRegion *r) const {
251 return alloc_capacity(r) > 0;
252 }
253
254 // This is used for unit testing. Do not use in production code.
255 void ShenandoahFreeSet::resize_old_collector_capacity(size_t regions) {
256 shenandoah_assert_heaplocked();
257 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
258 size_t original_old_regions = _partitions.get_capacity(ShenandoahFreeSetPartitionId::OldCollector) / region_size_bytes;
259 size_t unaffiliated_mutator_regions = _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Mutator);
260 size_t unaffiliated_collector_regions = _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Collector);
261 size_t unaffiliated_old_collector_regions = _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector);
262 if (regions > original_old_regions) {
263 size_t regions_to_transfer = regions - original_old_regions;
264 if (regions_to_transfer <= unaffiliated_mutator_regions + unaffiliated_collector_regions) {
265 size_t regions_from_mutator =
266 (regions_to_transfer > unaffiliated_mutator_regions)? unaffiliated_mutator_regions: regions_to_transfer;
267 regions_to_transfer -= regions_from_mutator;
268 size_t regions_from_collector = regions_to_transfer;
269 if (regions_from_mutator > 0) {
270 transfer_empty_regions_from_to(ShenandoahFreeSetPartitionId::Mutator, ShenandoahFreeSetPartitionId::OldCollector,
271 regions_from_mutator);
272 }
273 if (regions_from_collector > 0) {
274 transfer_empty_regions_from_to(ShenandoahFreeSetPartitionId::Collector, ShenandoahFreeSetPartitionId::OldCollector,
275 regions_from_mutator);
276 }
277 } else {
278 fatal("Could not resize old for unit test");
279 }
280 } else if (regions < original_old_regions) {
281 size_t regions_to_transfer = original_old_regions - regions;
282 if (regions_to_transfer <= unaffiliated_old_collector_regions) {
283 transfer_empty_regions_from_to(ShenandoahFreeSetPartitionId::OldCollector, ShenandoahFreeSetPartitionId::Mutator,
284 regions_to_transfer);
285 } else {
286 fatal("Could not resize old for unit test");
287 }
288 }
289 // else, old generation is already appropriately sized
290 }
291
292 inline idx_t ShenandoahRegionPartitions::leftmost(ShenandoahFreeSetPartitionId which_partition) const {
293 assert (which_partition < NumPartitions, "selected free partition must be valid");
294 idx_t idx = _leftmosts[int(which_partition)];
295 if (idx >= _max) {
296 return _max;
297 } else {
298 // Cannot assert that membership[which_partition.is_set(idx) because this helper method may be used
299 // to query the original value of leftmost when leftmost must be adjusted because the interval representing
300 // which_partition is shrinking after the region that used to be leftmost is retired.
301 return idx;
302 }
303 }
304
305 inline idx_t ShenandoahRegionPartitions::rightmost(ShenandoahFreeSetPartitionId which_partition) const {
306 assert (which_partition < NumPartitions, "selected free partition must be valid");
307 idx_t idx = _rightmosts[int(which_partition)];
308 // Cannot assert that membership[which_partition.is_set(idx) because this helper method may be used
309 // to query the original value of leftmost when leftmost must be adjusted because the interval representing
310 // which_partition is shrinking after the region that used to be leftmost is retired.
311 return idx;
312 }
313
314 void ShenandoahRegionPartitions::initialize_old_collector() {
315 _capacity[int(ShenandoahFreeSetPartitionId::OldCollector)] = 0;
316 _region_counts[int(ShenandoahFreeSetPartitionId::OldCollector)] = 0;
317 _empty_region_counts[int(ShenandoahFreeSetPartitionId::OldCollector)] = 0;
318 }
319
320 void ShenandoahRegionPartitions::make_all_regions_unavailable() {
321 shenandoah_assert_heaplocked_or_safepoint();
322 for (size_t partition_id = 0; partition_id < IntNumPartitions; partition_id++) {
323 _membership[partition_id].clear_all();
324 _leftmosts[partition_id] = _max;
325 _rightmosts[partition_id] = -1;
326 _leftmosts_empty[partition_id] = _max;
327 _rightmosts_empty[partition_id] = -1;
328 _capacity[partition_id] = 0;
329 _region_counts[partition_id] = 0;
330 _empty_region_counts[partition_id] = 0;
331 _used[partition_id] = 0;
332 _humongous_waste[partition_id] = 0;
333 _available[partition_id] = 0;
334 }
335 }
336
337 void ShenandoahRegionPartitions::establish_mutator_intervals(idx_t mutator_leftmost, idx_t mutator_rightmost,
338 idx_t mutator_leftmost_empty, idx_t mutator_rightmost_empty,
339 size_t total_mutator_regions, size_t empty_mutator_regions,
340 size_t mutator_region_count, size_t mutator_used,
341 size_t mutator_humongous_waste_bytes) {
342 shenandoah_assert_heaplocked();
343
344 _leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_leftmost;
345 _rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_rightmost;
346 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_leftmost_empty;
347 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_rightmost_empty;
348
349 _region_counts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_region_count;
350 _used[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_used;
351 _capacity[int(ShenandoahFreeSetPartitionId::Mutator)] = total_mutator_regions * _region_size_bytes;
352 _humongous_waste[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_humongous_waste_bytes;
353 _available[int(ShenandoahFreeSetPartitionId::Mutator)] =
354 _capacity[int(ShenandoahFreeSetPartitionId::Mutator)] - _used[int(ShenandoahFreeSetPartitionId::Mutator)];
355
356 _empty_region_counts[int(ShenandoahFreeSetPartitionId::Mutator)] = empty_mutator_regions;
357
358 _leftmosts[int(ShenandoahFreeSetPartitionId::Collector)] = _max;
359 _rightmosts[int(ShenandoahFreeSetPartitionId::Collector)] = -1;
360 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)] = _max;
361 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)] = -1;
362
363 _region_counts[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
364 _used[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
365 _capacity[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
366 _humongous_waste[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
367 _available[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
368
369 _empty_region_counts[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
370 }
371
372 void ShenandoahRegionPartitions::establish_old_collector_intervals(idx_t old_collector_leftmost,
373 idx_t old_collector_rightmost,
374 idx_t old_collector_leftmost_empty,
375 idx_t old_collector_rightmost_empty,
376 size_t total_old_collector_region_count,
377 size_t old_collector_empty, size_t old_collector_regions,
378 size_t old_collector_used,
379 size_t old_collector_humongous_waste_bytes) {
380 shenandoah_assert_heaplocked();
381
382 _leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_leftmost;
383 _rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_rightmost;
384 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_leftmost_empty;
385 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_rightmost_empty;
386
387 _region_counts[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_regions;
388 _used[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_used;
389 _capacity[int(ShenandoahFreeSetPartitionId::OldCollector)] = total_old_collector_region_count * _region_size_bytes;
390 _humongous_waste[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_humongous_waste_bytes;
391 _available[int(ShenandoahFreeSetPartitionId::OldCollector)] =
392 _capacity[int(ShenandoahFreeSetPartitionId::OldCollector)] - _used[int(ShenandoahFreeSetPartitionId::OldCollector)];
393
394 _empty_region_counts[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_empty;
395 }
396
397 void ShenandoahRegionPartitions::increase_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
398 shenandoah_assert_heaplocked();
399 assert (which_partition < NumPartitions, "Partition must be valid");
400
401 _used[int(which_partition)] += bytes;
402 _available[int(which_partition)] -= bytes;
403 assert (_used[int(which_partition)] <= _capacity[int(which_partition)],
404 "Must not use (%zu) more than capacity (%zu) after increase by %zu",
405 _used[int(which_partition)], _capacity[int(which_partition)], bytes);
406 }
407
408 void ShenandoahRegionPartitions::decrease_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
409 shenandoah_assert_heaplocked();
410 assert (which_partition < NumPartitions, "Partition must be valid");
411 assert (_used[int(which_partition)] >= bytes, "Must not use less than zero after decrease");
412 _used[int(which_partition)] -= bytes;
413 _available[int(which_partition)] += bytes;
414 }
415
416 void ShenandoahRegionPartitions::increase_humongous_waste(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
417 shenandoah_assert_heaplocked();
418 assert (which_partition < NumPartitions, "Partition must be valid");
419 _humongous_waste[int(which_partition)] += bytes;
420 }
421
422 size_t ShenandoahRegionPartitions::get_humongous_waste(ShenandoahFreeSetPartitionId which_partition) {
423 assert (which_partition < NumPartitions, "Partition must be valid");
424 return _humongous_waste[int(which_partition)];
425 }
426
427 void ShenandoahRegionPartitions::set_capacity_of(ShenandoahFreeSetPartitionId which_partition, size_t value) {
428 shenandoah_assert_heaplocked();
429 assert (which_partition < NumPartitions, "selected free set must be valid");
430 _capacity[int(which_partition)] = value;
431 _available[int(which_partition)] = value - _used[int(which_partition)];
432 }
433
434 void ShenandoahRegionPartitions::set_used_by(ShenandoahFreeSetPartitionId which_partition, size_t value) {
435 shenandoah_assert_heaplocked();
436 assert (which_partition < NumPartitions, "selected free set must be valid");
437 _used[int(which_partition)] = value;
438 _available[int(which_partition)] = _capacity[int(which_partition)] - value;
439 }
440
441
442 void ShenandoahRegionPartitions::increase_capacity(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
443 shenandoah_assert_heaplocked();
444 assert (which_partition < NumPartitions, "Partition must be valid");
445 _capacity[int(which_partition)] += bytes;
446 _available[int(which_partition)] += bytes;
447 }
448
449 void ShenandoahRegionPartitions::transfer_used_capacity_from_to(ShenandoahFreeSetPartitionId from_partition,
450 ShenandoahFreeSetPartitionId to_partition, size_t regions) {
451 shenandoah_assert_heaplocked();
452 size_t bytes = regions * ShenandoahHeapRegion::region_size_bytes();
453 assert (from_partition < NumPartitions, "Partition must be valid");
454 assert (to_partition < NumPartitions, "Partition must be valid");
455 assert(_capacity[int(from_partition)] >= bytes, "Cannot remove more capacity bytes than are present");
456 assert(_used[int(from_partition)] >= bytes, "Cannot transfer used bytes that are not used");
457
458 // available is unaffected by transfer
459 _capacity[int(from_partition)] -= bytes;
460 _used[int(from_partition)] -= bytes;
461 _capacity[int(to_partition)] += bytes;
462 _used[int(to_partition)] += bytes;
463 }
464
465 void ShenandoahRegionPartitions::decrease_capacity(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
466 shenandoah_assert_heaplocked();
467 assert (which_partition < NumPartitions, "Partition must be valid");
468 assert(_capacity[int(which_partition)] >= bytes, "Cannot remove more capacity bytes than are present");
469 assert(_available[int(which_partition)] >= bytes, "Cannot shrink capacity unless capacity is unused");
470 _capacity[int(which_partition)] -= bytes;
471 _available[int(which_partition)] -= bytes;
472 }
473
474 void ShenandoahRegionPartitions::increase_available(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
475 shenandoah_assert_heaplocked();
476 assert (which_partition < NumPartitions, "Partition must be valid");
477 _available[int(which_partition)] += bytes;
478 }
479
480 void ShenandoahRegionPartitions::decrease_available(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
481 shenandoah_assert_heaplocked();
482 assert (which_partition < NumPartitions, "Partition must be valid");
483 assert(_available[int(which_partition)] >= bytes, "Cannot remove more available bytes than are present");
484 _available[int(which_partition)] -= bytes;
485 }
486
487 size_t ShenandoahRegionPartitions::get_available(ShenandoahFreeSetPartitionId which_partition) {
488 assert (which_partition < NumPartitions, "Partition must be valid");
489 return _available[int(which_partition)];
490 }
491
492 void ShenandoahRegionPartitions::increase_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions) {
493 _region_counts[int(which_partition)] += regions;
494 }
495
496 void ShenandoahRegionPartitions::decrease_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions) {
497 assert(_region_counts[int(which_partition)] >= regions, "Cannot remove more regions than are present");
498 _region_counts[int(which_partition)] -= regions;
499 }
500
501 void ShenandoahRegionPartitions::increase_empty_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions) {
502 _empty_region_counts[int(which_partition)] += regions;
503 }
504
505 void ShenandoahRegionPartitions::decrease_empty_region_counts(ShenandoahFreeSetPartitionId which_partition, size_t regions) {
506 assert(_empty_region_counts[int(which_partition)] >= regions, "Cannot remove more regions than are present");
507 _empty_region_counts[int(which_partition)] -= regions;
508 }
509
510 void ShenandoahRegionPartitions::one_region_is_no_longer_empty(ShenandoahFreeSetPartitionId partition) {
511 decrease_empty_region_counts(partition, (size_t) 1);
512 }
513
514 // All members of partition between low_idx and high_idx inclusive have been removed.
515 void ShenandoahRegionPartitions::shrink_interval_if_range_modifies_either_boundary(
516 ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx, size_t num_regions) {
517 assert((low_idx <= high_idx) && (low_idx >= 0) && (high_idx < _max), "Range must span legal index values");
518 size_t span = high_idx + 1 - low_idx;
519 bool regions_are_contiguous = (span == num_regions);
520 if (low_idx == leftmost(partition)) {
521 assert (!_membership[int(partition)].is_set(low_idx), "Do not shrink interval if region not removed");
522 if (high_idx + 1 == _max) {
523 if (regions_are_contiguous) {
524 _leftmosts[int(partition)] = _max;
525 } else {
526 _leftmosts[int(partition)] = find_index_of_next_available_region(partition, low_idx + 1);
527 }
528 } else {
529 if (regions_are_contiguous) {
530 _leftmosts[int(partition)] = find_index_of_next_available_region(partition, high_idx + 1);
531 } else {
532 _leftmosts[int(partition)] = find_index_of_next_available_region(partition, low_idx + 1);
533 }
534 }
535 if (_leftmosts_empty[int(partition)] < _leftmosts[int(partition)]) {
536 // This gets us closer to where we need to be; we'll scan further when leftmosts_empty is requested.
537 _leftmosts_empty[int(partition)] = _leftmosts[int(partition)];
538 }
539 }
540 if (high_idx == _rightmosts[int(partition)]) {
541 assert (!_membership[int(partition)].is_set(high_idx), "Do not shrink interval if region not removed");
542 if (low_idx == 0) {
543 if (regions_are_contiguous) {
544 _rightmosts[int(partition)] = -1;
545 } else {
546 _rightmosts[int(partition)] = find_index_of_previous_available_region(partition, high_idx - 1);
547 }
548 } else {
549 if (regions_are_contiguous) {
550 _rightmosts[int(partition)] = find_index_of_previous_available_region(partition, low_idx - 1);
551 } else {
552 _rightmosts[int(partition)] = find_index_of_previous_available_region(partition, high_idx - 1);
553 }
554 }
555 if (_rightmosts_empty[int(partition)] > _rightmosts[int(partition)]) {
556 // This gets us closer to where we need to be; we'll scan further when rightmosts_empty is requested.
557 _rightmosts_empty[int(partition)] = _rightmosts[int(partition)];
558 }
559 }
560 if (_leftmosts[int(partition)] > _rightmosts[int(partition)]) {
561 _leftmosts[int(partition)] = _max;
562 _rightmosts[int(partition)] = -1;
563 _leftmosts_empty[int(partition)] = _max;
564 _rightmosts_empty[int(partition)] = -1;
565 }
566 }
567
568 void ShenandoahRegionPartitions::establish_interval(ShenandoahFreeSetPartitionId partition, idx_t low_idx,
569 idx_t high_idx, idx_t low_empty_idx, idx_t high_empty_idx) {
570 #ifdef ASSERT
571 assert (partition < NumPartitions, "invalid partition");
572 if (low_idx != max()) {
573 assert((low_idx <= high_idx) && (low_idx >= 0) && (high_idx < _max), "Range must span legal index values");
574 assert (in_free_set(partition, low_idx), "Must be in partition of established interval");
575 assert (in_free_set(partition, high_idx), "Must be in partition of established interval");
576 }
577 if (low_empty_idx != max()) {
578 ShenandoahHeapRegion* r = ShenandoahHeap::heap()->get_region(low_empty_idx);
579 assert (in_free_set(partition, low_empty_idx) && (r->is_trash() || r->free() == _region_size_bytes),
580 "Must be empty and in partition of established interval");
581 r = ShenandoahHeap::heap()->get_region(high_empty_idx);
582 assert (in_free_set(partition, high_empty_idx), "Must be in partition of established interval");
583 }
584 #endif
585
586 _leftmosts[int(partition)] = low_idx;
587 _rightmosts[int(partition)] = high_idx;
588 _leftmosts_empty[int(partition)] = low_empty_idx;
589 _rightmosts_empty[int(partition)] = high_empty_idx;
590 }
591
592 inline void ShenandoahRegionPartitions::shrink_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition,
593 idx_t idx) {
594 shrink_interval_if_range_modifies_either_boundary(partition, idx, idx, 1);
595 }
596
597 // Some members of partition between low_idx and high_idx inclusive have been added.
598 void ShenandoahRegionPartitions::
599 expand_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx,
600 idx_t low_empty_idx, idx_t high_empty_idx) {
601 if (_leftmosts[int(partition)] > low_idx) {
602 _leftmosts[int(partition)] = low_idx;
603 }
604 if (_rightmosts[int(partition)] < high_idx) {
605 _rightmosts[int(partition)] = high_idx;
606 }
607 if (_leftmosts_empty[int(partition)] > low_empty_idx) {
608 _leftmosts_empty[int(partition)] = low_empty_idx;
609 }
610 if (_rightmosts_empty[int(partition)] < high_empty_idx) {
611 _rightmosts_empty[int(partition)] = high_empty_idx;
612 }
613 }
614
615 void ShenandoahRegionPartitions::expand_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition,
616 idx_t idx, size_t region_available) {
617 if (_leftmosts[int(partition)] > idx) {
618 _leftmosts[int(partition)] = idx;
619 }
620 if (_rightmosts[int(partition)] < idx) {
621 _rightmosts[int(partition)] = idx;
622 }
623 if (region_available == _region_size_bytes) {
624 if (_leftmosts_empty[int(partition)] > idx) {
625 _leftmosts_empty[int(partition)] = idx;
626 }
627 if (_rightmosts_empty[int(partition)] < idx) {
628 _rightmosts_empty[int(partition)] = idx;
629 }
630 }
631 }
632
633 void ShenandoahRegionPartitions::retire_range_from_partition(
634 ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx) {
635
636 // Note: we may remove from free partition even if region is not entirely full, such as when available < PLAB::min_size()
637 assert ((low_idx < _max) && (high_idx < _max), "Both indices are sane: %zu and %zu < %zu",
638 low_idx, high_idx, _max);
639 assert (partition < NumPartitions, "Cannot remove from free partitions if not already free");
640
641 for (idx_t idx = low_idx; idx <= high_idx; idx++) {
642 #ifdef ASSERT
643 ShenandoahHeapRegion* r = ShenandoahHeap::heap()->get_region(idx);
644 assert (in_free_set(partition, idx), "Must be in partition to remove from partition");
645 assert(r->is_empty_or_trash(), "Region must be empty or trash");
646 #endif
647 _membership[int(partition)].clear_bit(idx);
648 }
649 size_t num_regions = high_idx + 1 - low_idx;
650 decrease_region_counts(partition, num_regions);
651 decrease_empty_region_counts(partition, num_regions);
652 shrink_interval_if_range_modifies_either_boundary(partition, low_idx, high_idx, num_regions);
653 }
654
655 size_t ShenandoahRegionPartitions::retire_from_partition(ShenandoahFreeSetPartitionId partition,
656 idx_t idx, size_t used_bytes) {
657
658 size_t waste_bytes = 0;
659 // Note: we may remove from free partition even if region is not entirely full, such as when available < PLAB::min_size()
660 assert (idx < _max, "index is sane: %zu < %zu", idx, _max);
661 assert (partition < NumPartitions, "Cannot remove from free partitions if not already free");
662 assert (in_free_set(partition, idx), "Must be in partition to remove from partition");
663
664 if (used_bytes < _region_size_bytes) {
665 // Count the alignment pad remnant of memory as used when we retire this region
666 size_t fill_padding = _region_size_bytes - used_bytes;
667 waste_bytes = fill_padding;
668 increase_used(partition, fill_padding);
669 }
670 _membership[int(partition)].clear_bit(idx);
671 decrease_region_counts(partition, 1);
672 shrink_interval_if_boundary_modified(partition, idx);
673
674 // This region is fully used, whether or not top() equals end(). It
675 // is retired and no more memory will be allocated from within it.
676
677 return waste_bytes;
678 }
679
680 void ShenandoahRegionPartitions::unretire_to_partition(ShenandoahHeapRegion* r, ShenandoahFreeSetPartitionId which_partition) {
681 shenandoah_assert_heaplocked();
682 make_free(r->index(), which_partition, r->free());
683 }
684
685
686 // The caller is responsible for increasing capacity and available and used in which_partition, and decreasing the
687 // same quantities for the original partition
688 void ShenandoahRegionPartitions::make_free(idx_t idx, ShenandoahFreeSetPartitionId which_partition, size_t available) {
689 shenandoah_assert_heaplocked();
690 assert (idx < _max, "index is sane: %zu < %zu", idx, _max);
691 assert (membership(idx) == ShenandoahFreeSetPartitionId::NotFree, "Cannot make free if already free");
692 assert (which_partition < NumPartitions, "selected free partition must be valid");
693 assert (available <= _region_size_bytes, "Available cannot exceed region size");
694
695 _membership[int(which_partition)].set_bit(idx);
696 expand_interval_if_boundary_modified(which_partition, idx, available);
697 }
698
699 bool ShenandoahRegionPartitions::is_mutator_partition(ShenandoahFreeSetPartitionId p) {
700 return (p == ShenandoahFreeSetPartitionId::Mutator);
701 }
702
703 bool ShenandoahRegionPartitions::is_young_collector_partition(ShenandoahFreeSetPartitionId p) {
704 return (p == ShenandoahFreeSetPartitionId::Collector);
705 }
706
707 bool ShenandoahRegionPartitions::is_old_collector_partition(ShenandoahFreeSetPartitionId p) {
708 return (p == ShenandoahFreeSetPartitionId::OldCollector);
709 }
710
711 bool ShenandoahRegionPartitions::available_implies_empty(size_t available_in_region) {
712 return (available_in_region == _region_size_bytes);
713 }
714
715 // Do not adjust capacities, available, or used. Return used delta.
716 size_t ShenandoahRegionPartitions::
717 move_from_partition_to_partition_with_deferred_accounting(idx_t idx, ShenandoahFreeSetPartitionId orig_partition,
718 ShenandoahFreeSetPartitionId new_partition, size_t available) {
719 ShenandoahHeapRegion* r = ShenandoahHeap::heap()->get_region(idx);
720 shenandoah_assert_heaplocked();
721 assert (idx < _max, "index is sane: %zu < %zu", idx, _max);
722 assert (orig_partition < NumPartitions, "Original partition must be valid");
723 assert (new_partition < NumPartitions, "New partition must be valid");
724 assert (available <= _region_size_bytes, "Available cannot exceed region size");
725 assert (_membership[int(orig_partition)].is_set(idx), "Cannot move from partition unless in partition");
726 assert ((r != nullptr) && ((r->is_trash() && (available == _region_size_bytes)) ||
727 (r->used() + available == _region_size_bytes)),
728 "Used: %zu + available: %zu should equal region size: %zu",
729 ShenandoahHeap::heap()->get_region(idx)->used(), available, _region_size_bytes);
730
731 // Expected transitions:
732 // During rebuild: Mutator => Collector
733 // Mutator empty => Collector
734 // Mutator empty => OldCollector
735 // During flip_to_gc: Mutator empty => Collector
736 // Mutator empty => OldCollector
737 // At start of update refs: Collector => Mutator
738 // OldCollector Empty => Mutator
739 assert ((is_mutator_partition(orig_partition) && is_young_collector_partition(new_partition)) ||
740 (is_mutator_partition(orig_partition) &&
741 available_implies_empty(available) && is_old_collector_partition(new_partition)) ||
742 (is_young_collector_partition(orig_partition) && is_mutator_partition(new_partition)) ||
743 (is_old_collector_partition(orig_partition)
744 && available_implies_empty(available) && is_mutator_partition(new_partition)),
745 "Unexpected movement between partitions, available: %zu, _region_size_bytes: %zu"
746 ", orig_partition: %s, new_partition: %s",
747 available, _region_size_bytes, partition_name(orig_partition), partition_name(new_partition));
748
749 size_t used = _region_size_bytes - available;
750 assert (_used[int(orig_partition)] >= used,
751 "Orig partition used: %zu must exceed moved used: %zu within region %zd",
752 _used[int(orig_partition)], used, idx);
753
754 _membership[int(orig_partition)].clear_bit(idx);
755 _membership[int(new_partition)].set_bit(idx);
756 return used;
757 }
758
759 void ShenandoahRegionPartitions::move_from_partition_to_partition(idx_t idx, ShenandoahFreeSetPartitionId orig_partition,
760 ShenandoahFreeSetPartitionId new_partition, size_t available) {
761 size_t used = move_from_partition_to_partition_with_deferred_accounting(idx, orig_partition, new_partition, available);
762
763 // We decreased used, which increases available, but then we decrease available by full region size below
764 decrease_used(orig_partition, used);
765 _region_counts[int(orig_partition)]--;
766 _capacity[int(orig_partition)] -= _region_size_bytes;
767 _available[int(orig_partition)] -= _region_size_bytes;
768 shrink_interval_if_boundary_modified(orig_partition, idx);
769
770 _capacity[int(new_partition)] += _region_size_bytes;
771 _available[int(new_partition)] += _region_size_bytes;
772 _region_counts[int(new_partition)]++;
773 // We increased availableby full region size above, but decrease it by used within this region now.
774 increase_used(new_partition, used);
775 expand_interval_if_boundary_modified(new_partition, idx, available);
776
777 if (available == _region_size_bytes) {
778 _empty_region_counts[int(orig_partition)]--;
779 _empty_region_counts[int(new_partition)]++;
780 }
781 }
782
783 const char* ShenandoahRegionPartitions::partition_membership_name(idx_t idx) const {
784 return partition_name(membership(idx));
785 }
786
787 #ifdef ASSERT
788 inline bool ShenandoahRegionPartitions::partition_id_matches(idx_t idx, ShenandoahFreeSetPartitionId test_partition) const {
789 assert (idx < _max, "index is sane: %zu < %zu", idx, _max);
790 assert (test_partition < ShenandoahFreeSetPartitionId::NotFree, "must be a valid partition");
791
792 return membership(idx) == test_partition;
793 }
794 #endif
795
796 inline bool ShenandoahRegionPartitions::is_empty(ShenandoahFreeSetPartitionId which_partition) const {
797 assert (which_partition < NumPartitions, "selected free partition must be valid");
798 return (leftmost(which_partition) > rightmost(which_partition));
799 }
800
801 inline idx_t ShenandoahRegionPartitions::find_index_of_next_available_region(
802 ShenandoahFreeSetPartitionId which_partition, idx_t start_index) const {
803 idx_t rightmost_idx = rightmost(which_partition);
804 idx_t leftmost_idx = leftmost(which_partition);
805 if ((rightmost_idx < leftmost_idx) || (start_index > rightmost_idx)) return _max;
806 if (start_index < leftmost_idx) {
807 start_index = leftmost_idx;
808 }
809 idx_t result = _membership[int(which_partition)].find_first_set_bit(start_index, rightmost_idx + 1);
810 if (result > rightmost_idx) {
811 result = _max;
812 }
813 assert (result >= start_index, "Requires progress");
814 return result;
815 }
816
817 inline idx_t ShenandoahRegionPartitions::find_index_of_previous_available_region(
818 ShenandoahFreeSetPartitionId which_partition, idx_t last_index) const {
819 idx_t rightmost_idx = rightmost(which_partition);
820 idx_t leftmost_idx = leftmost(which_partition);
821 // if (leftmost_idx == max) then (last_index < leftmost_idx)
822 if (last_index < leftmost_idx) return -1;
823 if (last_index > rightmost_idx) {
824 last_index = rightmost_idx;
825 }
826 idx_t result = _membership[int(which_partition)].find_last_set_bit(-1, last_index);
827 if (result < leftmost_idx) {
828 result = -1;
829 }
830 assert (result <= last_index, "Requires progress");
831 return result;
832 }
833
834 inline idx_t ShenandoahRegionPartitions::find_index_of_next_available_cluster_of_regions(
835 ShenandoahFreeSetPartitionId which_partition, idx_t start_index, size_t cluster_size) const {
836 idx_t rightmost_idx = rightmost(which_partition);
837 idx_t leftmost_idx = leftmost(which_partition);
838 if ((rightmost_idx < leftmost_idx) || (start_index > rightmost_idx)) return _max;
839 idx_t result =
840 _membership[int(which_partition)].find_first_consecutive_set_bits(start_index, rightmost_idx + 1, cluster_size);
841 if (result > rightmost_idx) {
842 result = _max;
843 }
844 assert (result >= start_index, "Requires progress");
845 return result;
846 }
847
848 inline idx_t ShenandoahRegionPartitions::find_index_of_previous_available_cluster_of_regions(
849 ShenandoahFreeSetPartitionId which_partition, idx_t last_index, size_t cluster_size) const {
850 idx_t leftmost_idx = leftmost(which_partition);
851 // if (leftmost_idx == max) then (last_index < leftmost_idx)
852 if (last_index < leftmost_idx) return -1;
853 idx_t result = _membership[int(which_partition)].find_last_consecutive_set_bits(leftmost_idx - 1, last_index, cluster_size);
854 if (result <= leftmost_idx) {
855 result = -1;
856 }
857 assert (result <= last_index, "Requires progress");
858 return result;
859 }
860
861 idx_t ShenandoahRegionPartitions::leftmost_empty(ShenandoahFreeSetPartitionId which_partition) {
862 assert (which_partition < NumPartitions, "selected free partition must be valid");
863 idx_t max_regions = _max;
864 if (_leftmosts_empty[int(which_partition)] == _max) {
865 return _max;
866 }
867 for (idx_t idx = find_index_of_next_available_region(which_partition, _leftmosts_empty[int(which_partition)]);
868 idx < max_regions; ) {
869 assert(in_free_set(which_partition, idx), "Boundaries or find_last_set_bit failed: %zd", idx);
870 if (_free_set->alloc_capacity(idx) == _region_size_bytes) {
871 _leftmosts_empty[int(which_partition)] = idx;
872 return idx;
873 }
874 idx = find_index_of_next_available_region(which_partition, idx + 1);
875 }
876 _leftmosts_empty[int(which_partition)] = _max;
877 _rightmosts_empty[int(which_partition)] = -1;
878 return _max;
879 }
880
881 idx_t ShenandoahRegionPartitions::rightmost_empty(ShenandoahFreeSetPartitionId which_partition) {
882 assert (which_partition < NumPartitions, "selected free partition must be valid");
883 if (_rightmosts_empty[int(which_partition)] < 0) {
884 return -1;
885 }
886 for (idx_t idx = find_index_of_previous_available_region(which_partition, _rightmosts_empty[int(which_partition)]);
887 idx >= 0; ) {
888 assert(in_free_set(which_partition, idx), "Boundaries or find_last_set_bit failed: %zd", idx);
889 if (_free_set->alloc_capacity(idx) == _region_size_bytes) {
890 _rightmosts_empty[int(which_partition)] = idx;
891 return idx;
892 }
893 idx = find_index_of_previous_available_region(which_partition, idx - 1);
894 }
895 _leftmosts_empty[int(which_partition)] = _max;
896 _rightmosts_empty[int(which_partition)] = -1;
897 return -1;
898 }
899
900
901 #ifdef ASSERT
902 void ShenandoahRegionPartitions::assert_bounds() {
903
904 size_t capacities[UIntNumPartitions];
905 size_t used[UIntNumPartitions];
906 size_t regions[UIntNumPartitions];
907 size_t humongous_waste[UIntNumPartitions];
908
909 // We don't know whether young retired regions belonged to Mutator or Collector before they were retired.
910 // We just tally the total, and divide it to make matches work if possible.
911 size_t young_retired_regions = 0;
912 size_t young_retired_used = 0;
913 size_t young_retired_capacity = 0;
914 size_t young_humongous_waste = 0;
915
916 idx_t leftmosts[UIntNumPartitions];
917 idx_t rightmosts[UIntNumPartitions];
918 idx_t empty_leftmosts[UIntNumPartitions];
919 idx_t empty_rightmosts[UIntNumPartitions];
920
921 for (uint i = 0; i < UIntNumPartitions; i++) {
922 leftmosts[i] = _max;
923 empty_leftmosts[i] = _max;
924 rightmosts[i] = -1;
925 empty_rightmosts[i] = -1;
926 capacities[i] = 0;
927 used[i] = 0;
928 regions[i] = 0;
929 humongous_waste[i] = 0;
930 }
931
932 for (idx_t i = 0; i < _max; i++) {
933 ShenandoahFreeSetPartitionId partition = membership(i);
934 size_t capacity = _free_set->alloc_capacity(i);
935 switch (partition) {
936 case ShenandoahFreeSetPartitionId::NotFree:
937 {
938 assert(capacity != _region_size_bytes, "Should not be retired if empty");
939 ShenandoahHeapRegion* r = ShenandoahHeap::heap()->get_region(i);
940 if (r->is_humongous()) {
941 if (r->is_old()) {
942 regions[int(ShenandoahFreeSetPartitionId::OldCollector)]++;
943 used[int(ShenandoahFreeSetPartitionId::OldCollector)] += _region_size_bytes;
944 capacities[int(ShenandoahFreeSetPartitionId::OldCollector)] += _region_size_bytes;
945 humongous_waste[int(ShenandoahFreeSetPartitionId::OldCollector)] += capacity;
946 } else {
947 assert(r->is_young(), "Must be young if not old");
948 young_retired_regions++;
949 // Count entire region as used even if there is some waste.
950 young_retired_used += _region_size_bytes;
951 young_retired_capacity += _region_size_bytes;
952 young_humongous_waste += capacity;
953 }
954 } else {
955 assert(r->is_cset() || (capacity < PLAB::min_size() * HeapWordSize),
956 "Expect retired remnant size to be smaller than min plab size");
957 // This region has been retired already or it is in the cset. In either case, we set capacity to zero
958 // so that the entire region will be counted as used. We count young cset regions as "retired".
959 capacity = 0;
960 if (r->is_old()) {
961 regions[int(ShenandoahFreeSetPartitionId::OldCollector)]++;
962 used[int(ShenandoahFreeSetPartitionId::OldCollector)] += _region_size_bytes - capacity;
963 capacities[int(ShenandoahFreeSetPartitionId::OldCollector)] += _region_size_bytes;
964 } else {
965 assert(r->is_young(), "Must be young if not old");
966 young_retired_regions++;
967 young_retired_used += _region_size_bytes - capacity;
968 young_retired_capacity += _region_size_bytes;
969 }
970 }
971 }
972 break;
973
974 case ShenandoahFreeSetPartitionId::Mutator:
975 case ShenandoahFreeSetPartitionId::Collector:
976 case ShenandoahFreeSetPartitionId::OldCollector:
977 {
978 ShenandoahHeapRegion* r = ShenandoahHeap::heap()->get_region(i);
979 assert(capacity > 0, "free regions must have allocation capacity");
980 bool is_empty = (capacity == _region_size_bytes);
981 regions[int(partition)]++;
982 used[int(partition)] += _region_size_bytes - capacity;
983 capacities[int(partition)] += _region_size_bytes;
984 if (i < leftmosts[int(partition)]) {
985 leftmosts[int(partition)] = i;
986 }
987 if (is_empty && (i < empty_leftmosts[int(partition)])) {
988 empty_leftmosts[int(partition)] = i;
989 }
990 if (i > rightmosts[int(partition)]) {
991 rightmosts[int(partition)] = i;
992 }
993 if (is_empty && (i > empty_rightmosts[int(partition)])) {
994 empty_rightmosts[int(partition)] = i;
995 }
996 break;
997 }
998
999 default:
1000 ShouldNotReachHere();
1001 }
1002 }
1003
1004 // Performance invariants. Failing these would not break the free partition, but performance would suffer.
1005 assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) <= _max,
1006 "leftmost in bounds: %zd < %zd", leftmost(ShenandoahFreeSetPartitionId::Mutator), _max);
1007 assert (rightmost(ShenandoahFreeSetPartitionId::Mutator) < _max,
1008 "rightmost in bounds: %zd < %zd", rightmost(ShenandoahFreeSetPartitionId::Mutator), _max);
1009
1010 assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) == _max
1011 || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::Mutator), ShenandoahFreeSetPartitionId::Mutator),
1012 "leftmost region should be free: %zd", leftmost(ShenandoahFreeSetPartitionId::Mutator));
1013 assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) == _max
1014 || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::Mutator), ShenandoahFreeSetPartitionId::Mutator),
1015 "rightmost region should be free: %zd", rightmost(ShenandoahFreeSetPartitionId::Mutator));
1016
1017 // If Mutator partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
1018 // Likewise for empty region partitions.
1019 idx_t beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
1020 idx_t end_off = rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
1021 assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::Mutator),
1022 "Mutator free region before the leftmost: %zd, bound %zd",
1023 beg_off, leftmost(ShenandoahFreeSetPartitionId::Mutator));
1024 assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::Mutator),
1025 "Mutator free region past the rightmost: %zd, bound %zd",
1026 end_off, rightmost(ShenandoahFreeSetPartitionId::Mutator));
1027
1028 beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
1029 end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
1030 assert (beg_off >= _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
1031 "free empty region (%zd) before the leftmost bound %zd",
1032 beg_off, _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)]);
1033 assert (end_off <= _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
1034 "free empty region (%zd) past the rightmost bound %zd",
1035 end_off, _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)]);
1036
1037 // Performance invariants. Failing these would not break the free partition, but performance would suffer.
1038 assert (leftmost(ShenandoahFreeSetPartitionId::Collector) <= _max, "leftmost in bounds: %zd < %zd",
1039 leftmost(ShenandoahFreeSetPartitionId::Collector), _max);
1040 assert (rightmost(ShenandoahFreeSetPartitionId::Collector) < _max, "rightmost in bounds: %zd < %zd",
1041 rightmost(ShenandoahFreeSetPartitionId::Collector), _max);
1042
1043 assert (leftmost(ShenandoahFreeSetPartitionId::Collector) == _max
1044 || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::Collector), ShenandoahFreeSetPartitionId::Collector),
1045 "Collector leftmost region should be free: %zd", leftmost(ShenandoahFreeSetPartitionId::Collector));
1046 assert (leftmost(ShenandoahFreeSetPartitionId::Collector) == _max
1047 || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::Collector), ShenandoahFreeSetPartitionId::Collector),
1048 "Collector rightmost region should be free: %zd", rightmost(ShenandoahFreeSetPartitionId::Collector));
1049
1050 // If Collector partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
1051 // Likewise for empty region partitions.
1052 beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::Collector)];
1053 end_off = rightmosts[int(ShenandoahFreeSetPartitionId::Collector)];
1054 assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::Collector),
1055 "Collector free region before the leftmost: %zd, bound %zd",
1056 beg_off, leftmost(ShenandoahFreeSetPartitionId::Collector));
1057 assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::Collector),
1058 "Collector free region past the rightmost: %zd, bound %zd",
1059 end_off, rightmost(ShenandoahFreeSetPartitionId::Collector));
1060
1061 beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::Collector)];
1062 end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::Collector)];
1063 assert (beg_off >= _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
1064 "Collector free empty region before the leftmost: %zd, bound %zd",
1065 beg_off, _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)]);
1066 assert (end_off <= _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
1067 "Collector free empty region past the rightmost: %zd, bound %zd",
1068 end_off, _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)]);
1069
1070 // Performance invariants. Failing these would not break the free partition, but performance would suffer.
1071 assert (leftmost(ShenandoahFreeSetPartitionId::OldCollector) <= _max, "OldCollector leftmost in bounds: %zd < %zd",
1072 leftmost(ShenandoahFreeSetPartitionId::OldCollector), _max);
1073 assert (rightmost(ShenandoahFreeSetPartitionId::OldCollector) < _max, "OldCollector rightmost in bounds: %zd < %zd",
1074 rightmost(ShenandoahFreeSetPartitionId::OldCollector), _max);
1075
1076 assert (leftmost(ShenandoahFreeSetPartitionId::OldCollector) == _max
1077 || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::OldCollector),
1078 ShenandoahFreeSetPartitionId::OldCollector),
1079 "OldCollector leftmost region should be free: %zd", leftmost(ShenandoahFreeSetPartitionId::OldCollector));
1080 assert (leftmost(ShenandoahFreeSetPartitionId::OldCollector) == _max
1081 || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::OldCollector),
1082 ShenandoahFreeSetPartitionId::OldCollector),
1083 "OldCollector rightmost region should be free: %zd", rightmost(ShenandoahFreeSetPartitionId::OldCollector));
1084
1085 // Concurrent recycling of trash recycles a region (changing its state from is_trash to is_empty without the heap lock),
1086
1087 // If OldCollector partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
1088 // Likewise for empty region partitions.
1089 beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
1090 end_off = rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
1091 assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::OldCollector), "free regions before the leftmost: %zd, bound %zd",
1092 beg_off, leftmost(ShenandoahFreeSetPartitionId::OldCollector));
1093 assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::OldCollector), "free regions past the rightmost: %zd, bound %zd",
1094 end_off, rightmost(ShenandoahFreeSetPartitionId::OldCollector));
1095
1096 beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
1097 end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
1098 assert (beg_off >= _leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
1099 "free empty region (%zd) before the leftmost bound %zd, region %s trash",
1100 beg_off, _leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
1101 ((beg_off >= _max)? "out of bounds is not":
1102 (ShenandoahHeap::heap()->get_region(_leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)])->is_trash()?
1103 "is": "is not")));
1104 assert (end_off <= _rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
1105 "free empty region (%zd) past the rightmost bound %zd, region %s trash",
1106 end_off, _rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
1107 ((end_off < 0)? "out of bounds is not" :
1108 (ShenandoahHeap::heap()->get_region(_rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)])->is_trash()?
1109 "is": "is not")));
1110
1111 // young_retired_regions need to be added to either Mutator or Collector partitions, 100% used.
1112 // Give enough of young_retired_regions, young_retired_capacity, young_retired_user
1113 // to the Mutator partition to top it off so that it matches the running totals.
1114 //
1115 // Give any remnants to the Collector partition. After topping off the Collector partition, its values
1116 // should also match running totals.
1117 assert(young_retired_regions * _region_size_bytes == young_retired_capacity, "sanity");
1118 assert(young_retired_capacity == young_retired_used, "sanity");
1119
1120 assert(capacities[int(ShenandoahFreeSetPartitionId::OldCollector)]
1121 == _capacity[int(ShenandoahFreeSetPartitionId::OldCollector)], "Old collector capacities must match (%zu != %zu)",
1122 capacities[int(ShenandoahFreeSetPartitionId::OldCollector)],
1123 _capacity[int(ShenandoahFreeSetPartitionId::OldCollector)]);
1124 assert(used[int(ShenandoahFreeSetPartitionId::OldCollector)]
1125 == _used[int(ShenandoahFreeSetPartitionId::OldCollector)], "Old collector used must match");
1126 assert(regions[int(ShenandoahFreeSetPartitionId::OldCollector)]
1127 == _capacity[int(ShenandoahFreeSetPartitionId::OldCollector)] / _region_size_bytes, "Old collector regions must match");
1128 assert(_capacity[int(ShenandoahFreeSetPartitionId::OldCollector)]
1129 >= _used[int(ShenandoahFreeSetPartitionId::OldCollector)], "Old Collector capacity must be >= used");
1130 assert(_available[int(ShenandoahFreeSetPartitionId::OldCollector)] ==
1131 (_capacity[int(ShenandoahFreeSetPartitionId::OldCollector)] - _used[int(ShenandoahFreeSetPartitionId::OldCollector)]),
1132 "Old Collector available must equal capacity minus used");
1133 assert(_humongous_waste[int(ShenandoahFreeSetPartitionId::OldCollector)] ==
1134 humongous_waste[int(ShenandoahFreeSetPartitionId::OldCollector)], "Old Collector humongous waste must match");
1135
1136 assert(_capacity[int(ShenandoahFreeSetPartitionId::Mutator)] >= capacities[int(ShenandoahFreeSetPartitionId::Mutator)],
1137 "Capacity total must be >= counted tally");
1138 size_t mutator_capacity_shortfall =
1139 _capacity[int(ShenandoahFreeSetPartitionId::Mutator)] - capacities[int(ShenandoahFreeSetPartitionId::Mutator)];
1140 assert(mutator_capacity_shortfall <= young_retired_capacity, "sanity");
1141 capacities[int(ShenandoahFreeSetPartitionId::Mutator)] += mutator_capacity_shortfall;
1142 young_retired_capacity -= mutator_capacity_shortfall;
1143 capacities[int(ShenandoahFreeSetPartitionId::Collector)] += young_retired_capacity;
1144
1145 assert(_used[int(ShenandoahFreeSetPartitionId::Mutator)] >= used[int(ShenandoahFreeSetPartitionId::Mutator)],
1146 "Used total must be >= counted tally");
1147 size_t mutator_used_shortfall =
1148 _used[int(ShenandoahFreeSetPartitionId::Mutator)] - used[int(ShenandoahFreeSetPartitionId::Mutator)];
1149 assert(mutator_used_shortfall <= young_retired_used, "sanity");
1150 used[int(ShenandoahFreeSetPartitionId::Mutator)] += mutator_used_shortfall;
1151 young_retired_used -= mutator_used_shortfall;
1152 used[int(ShenandoahFreeSetPartitionId::Collector)] += young_retired_used;
1153
1154 assert(_capacity[int(ShenandoahFreeSetPartitionId::Mutator)] / _region_size_bytes
1155 >= regions[int(ShenandoahFreeSetPartitionId::Mutator)], "Region total must be >= counted tally");
1156 size_t mutator_regions_shortfall = (_capacity[int(ShenandoahFreeSetPartitionId::Mutator)] / _region_size_bytes
1157 - regions[int(ShenandoahFreeSetPartitionId::Mutator)]);
1158 assert(mutator_regions_shortfall <= young_retired_regions, "sanity");
1159 regions[int(ShenandoahFreeSetPartitionId::Mutator)] += mutator_regions_shortfall;
1160 young_retired_regions -= mutator_regions_shortfall;
1161 regions[int(ShenandoahFreeSetPartitionId::Collector)] += young_retired_regions;
1162
1163 assert(capacities[int(ShenandoahFreeSetPartitionId::Collector)] == _capacity[int(ShenandoahFreeSetPartitionId::Collector)],
1164 "Collector capacities must match");
1165 assert(used[int(ShenandoahFreeSetPartitionId::Collector)] == _used[int(ShenandoahFreeSetPartitionId::Collector)],
1166 "Collector used must match");
1167 assert(regions[int(ShenandoahFreeSetPartitionId::Collector)]
1168 == _capacity[int(ShenandoahFreeSetPartitionId::Collector)] / _region_size_bytes, "Collector regions must match");
1169 assert(_capacity[int(ShenandoahFreeSetPartitionId::Collector)] >= _used[int(ShenandoahFreeSetPartitionId::Collector)],
1170 "Collector Capacity must be >= used");
1171 assert(_available[int(ShenandoahFreeSetPartitionId::Collector)] ==
1172 (_capacity[int(ShenandoahFreeSetPartitionId::Collector)] - _used[int(ShenandoahFreeSetPartitionId::Collector)]),
1173 "Collector Available must equal capacity minus used");
1174
1175 assert(capacities[int(ShenandoahFreeSetPartitionId::Mutator)] == _capacity[int(ShenandoahFreeSetPartitionId::Mutator)],
1176 "Mutator capacities must match");
1177 assert(used[int(ShenandoahFreeSetPartitionId::Mutator)] == _used[int(ShenandoahFreeSetPartitionId::Mutator)],
1178 "Mutator used must match");
1179 assert(regions[int(ShenandoahFreeSetPartitionId::Mutator)]
1180 == _capacity[int(ShenandoahFreeSetPartitionId::Mutator)] / _region_size_bytes, "Mutator regions must match");
1181 assert(_capacity[int(ShenandoahFreeSetPartitionId::Mutator)] >= _used[int(ShenandoahFreeSetPartitionId::Mutator)],
1182 "Mutator capacity must be >= used");
1183 assert(_available[int(ShenandoahFreeSetPartitionId::Mutator)] ==
1184 (_capacity[int(ShenandoahFreeSetPartitionId::Mutator)] - _used[int(ShenandoahFreeSetPartitionId::Mutator)]),
1185 "Mutator available must equal capacity minus used");
1186 assert(_humongous_waste[int(ShenandoahFreeSetPartitionId::Mutator)] == young_humongous_waste,
1187 "Mutator humongous waste must match");
1188 }
1189
1190 inline void ShenandoahRegionPartitions::assert_bounds_sanity() {
1191 for (uint8_t i = 0; i < UIntNumPartitions; i++) {
1192 ShenandoahFreeSetPartitionId partition = static_cast<ShenandoahFreeSetPartitionId>(i);
1193 assert(leftmost(partition) == _max || membership(leftmost(partition)) == partition, "Left most boundry must be sane");
1194 assert(rightmost(partition) == -1 || membership(rightmost(partition)) == partition, "Right most boundry must be sane");
1195
1196 assert(leftmost_empty(partition) == _max || leftmost_empty(partition) >= leftmost(partition), "Left most empty must be sane");
1197 assert(rightmost_empty(partition) == -1 || rightmost_empty(partition) <= rightmost(partition), "Right most empty must be sane");
1198 }
1199 }
1200
1201 #endif
1202
1203 ShenandoahFreeSet::ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions) :
1204 _heap(heap),
1205 _partitions(max_regions, this),
1206 _total_humongous_waste(0),
1207 _alloc_bias_weight(0),
1208 _total_young_used(0),
1209 _total_old_used(0),
1210 _total_global_used(0),
1211 _young_affiliated_regions(0),
1212 _old_affiliated_regions(0),
1213 _global_affiliated_regions(0),
1214 _young_unaffiliated_regions(0),
1215 _global_unaffiliated_regions(0),
1216 _total_young_regions(0),
1217 _total_global_regions(0)
1218 {
1219 clear_internal();
1220 }
1221
1222 void ShenandoahFreeSet::move_unaffiliated_regions_from_collector_to_old_collector(ssize_t count) {
1223 shenandoah_assert_heaplocked();
1224 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1225
1226 size_t old_capacity = _partitions.get_capacity(ShenandoahFreeSetPartitionId::OldCollector);
1227 size_t collector_capacity = _partitions.get_capacity(ShenandoahFreeSetPartitionId::Collector);
1228 if (count > 0) {
1229 size_t ucount = count;
1230 size_t bytes_moved = ucount * region_size_bytes;
1231 assert(collector_capacity >= bytes_moved, "Cannot transfer");
1232 assert(_partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Collector) >= ucount,
1233 "Cannot transfer %zu of %zu", ucount, _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Collector));
1234 _partitions.decrease_empty_region_counts(ShenandoahFreeSetPartitionId::Collector, ucount);
1235 _partitions.set_capacity_of(ShenandoahFreeSetPartitionId::Collector, collector_capacity - bytes_moved);
1236 _partitions.set_capacity_of(ShenandoahFreeSetPartitionId::OldCollector, old_capacity + bytes_moved);
1237 _partitions.increase_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector, ucount);
1238 } else if (count < 0) {
1239 size_t ucount = -count;
1240 size_t bytes_moved = ucount * region_size_bytes;
1241 assert(old_capacity >= bytes_moved, "Cannot transfer");
1242 assert(_partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector) >= ucount,
1243 "Cannot transfer %zu of %zu", ucount, _partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector));
1244 _partitions.decrease_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector, ucount);
1245 _partitions.set_capacity_of(ShenandoahFreeSetPartitionId::OldCollector, old_capacity - bytes_moved);
1246 _partitions.set_capacity_of(ShenandoahFreeSetPartitionId::Collector, collector_capacity + bytes_moved);
1247 _partitions.increase_empty_region_counts(ShenandoahFreeSetPartitionId::Collector, ucount);
1248 }
1249 // else, do nothing
1250 }
1251
1252 // was pip_pad_bytes
1253 void ShenandoahFreeSet::add_promoted_in_place_region_to_old_collector(ShenandoahHeapRegion* region) {
1254 shenandoah_assert_heaplocked();
1255 size_t plab_min_size_in_bytes = ShenandoahGenerationalHeap::heap()->plab_min_size() * HeapWordSize;
1256 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1257 size_t available_in_region = alloc_capacity(region);
1258 size_t region_index = region->index();
1259 ShenandoahFreeSetPartitionId p = _partitions.membership(region_index);
1260 assert(_partitions.membership(region_index) == ShenandoahFreeSetPartitionId::NotFree,
1261 "Regions promoted in place should have been excluded from Mutator partition");
1262
1263 // If region had been retired, its end-of-region alignment pad had been counted as used within the Mutator partition
1264 size_t used_while_awaiting_pip = region_size_bytes;
1265 size_t used_after_pip = region_size_bytes;
1266 if (available_in_region >= plab_min_size_in_bytes) {
1267 used_after_pip -= available_in_region;
1268 } else {
1269 if (available_in_region >= ShenandoahHeap::min_fill_size() * HeapWordSize) {
1270 size_t fill_words = available_in_region / HeapWordSize;
1271 ShenandoahHeap::heap()->old_generation()->card_scan()->register_object(region->top());
1272 region->allocate_fill(fill_words);
1273 }
1274 available_in_region = 0;
1275 }
1276
1277 assert(p == ShenandoahFreeSetPartitionId::NotFree, "pip region must be NotFree");
1278 assert(region->is_young(), "pip region must be young");
1279
1280 // Though this region may have been promoted in place from the Collector region, its usage is now accounted within
1281 // the Mutator partition.
1282 _partitions.decrease_used(ShenandoahFreeSetPartitionId::Mutator, used_while_awaiting_pip);
1283
1284 // decrease capacity adjusts available
1285 _partitions.decrease_capacity(ShenandoahFreeSetPartitionId::Mutator, region_size_bytes);
1286 _partitions.increase_capacity(ShenandoahFreeSetPartitionId::OldCollector, region_size_bytes);
1287 _partitions.increase_used(ShenandoahFreeSetPartitionId::OldCollector, used_after_pip);
1288 region->set_affiliation(ShenandoahAffiliation::OLD_GENERATION);
1289 if (available_in_region > 0) {
1290 assert(available_in_region >= plab_min_size_in_bytes, "enforced above");
1291 _partitions.increase_region_counts(ShenandoahFreeSetPartitionId::OldCollector, 1);
1292 // make_free() adjusts bounds for OldCollector partition
1293 _partitions.make_free(region_index, ShenandoahFreeSetPartitionId::OldCollector, available_in_region);
1294 _heap->old_generation()->augment_promoted_reserve(available_in_region);
1295 assert(available_in_region != region_size_bytes, "Nothing to promote in place");
1296 }
1297 // else, leave this region as NotFree
1298
1299 recompute_total_used</* UsedByMutatorChanged */ true,
1300 /* UsedByCollectorChanged */ false, /* UsedByOldCollectorChanged */ true>();
1301 // Conservatively, assume that pip regions came from both Mutator and Collector
1302 recompute_total_affiliated</* MutatorEmptiesChanged */ false, /* CollectorEmptiesChanged */ false,
1303 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ true,
1304 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ true,
1305 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ true,
1306 /* UnaffiliatedChangesAreYoungNeutral */ true>();
1307 _partitions.assert_bounds();
1308 }
1309
1310 template<typename Iter>
1311 HeapWord* ShenandoahFreeSet::allocate_with_affiliation(Iter& iterator,
1312 ShenandoahAffiliation affiliation,
1313 ShenandoahAllocRequest& req,
1314 bool& in_new_region) {
1315 assert(affiliation != ShenandoahAffiliation::FREE, "Must not");
1316 ShenandoahHeapRegion* free_region = nullptr;
1317 for (idx_t idx = iterator.current(); iterator.has_next(); idx = iterator.next()) {
1318 ShenandoahHeapRegion* r = _heap->get_region(idx);
1319 if (r->affiliation() == affiliation) {
1320 HeapWord* result = try_allocate_in(r, req, in_new_region);
1321 if (result != nullptr) {
1322 return result;
1323 }
1324 } else if (free_region == nullptr && r->affiliation() == FREE) {
1325 free_region = r;
1326 }
1327 }
1328 // Failed to allocate within any affiliated region, try the first free region in the partition.
1329 if (free_region != nullptr) {
1330 HeapWord* result = try_allocate_in(free_region, req, in_new_region);
1331 assert(result != nullptr, "Allocate in free region in the partition always succeed.");
1332 return result;
1333 }
1334 log_debug(gc, free)("Could not allocate collector region with affiliation: %s for request " PTR_FORMAT,
1335 shenandoah_affiliation_name(affiliation), p2i(&req));
1336 return nullptr;
1337 }
1338
1339 HeapWord* ShenandoahFreeSet::allocate_single(ShenandoahAllocRequest& req, bool& in_new_region) {
1340 shenandoah_assert_heaplocked();
1341
1342 // Scan the bitmap looking for a first fit.
1343 //
1344 // Leftmost and rightmost bounds provide enough caching to walk bitmap efficiently. Normally,
1345 // we would find the region to allocate at right away.
1346 //
1347 // Allocations are biased: GC allocations are taken from the high end of the heap. Regular (and TLAB)
1348 // mutator allocations are taken from the middle of heap, below the memory reserved for Collector.
1349 // Humongous mutator allocations are taken from the bottom of the heap.
1350 //
1351 // Free set maintains mutator and collector partitions. Normally, each allocates only from its partition,
1352 // except in special cases when the collector steals regions from the mutator partition.
1353
1354 // Overwrite with non-zero (non-null) values only if necessary for allocation bookkeeping.
1355
1356 if (req.is_mutator_alloc()) {
1357 return allocate_for_mutator(req, in_new_region);
1358 } else {
1359 return allocate_for_collector(req, in_new_region);
1360 }
1361 }
1362
1363 HeapWord* ShenandoahFreeSet::allocate_for_mutator(ShenandoahAllocRequest &req, bool &in_new_region) {
1364 update_allocation_bias();
1365
1366 if (_partitions.is_empty(ShenandoahFreeSetPartitionId::Mutator)) {
1367 // There is no recovery. Mutator does not touch collector view at all.
1368 return nullptr;
1369 }
1370
1371 // Try to allocate in the mutator view
1372 if (_partitions.alloc_from_left_bias(ShenandoahFreeSetPartitionId::Mutator)) {
1373 // Allocate from low to high memory. This keeps the range of fully empty regions more tightly packed.
1374 // Note that the most recently allocated regions tend not to be evacuated in a given GC cycle. So this
1375 // tends to accumulate "fragmented" uncollected regions in high memory.
1376 ShenandoahLeftRightIterator iterator(&_partitions, ShenandoahFreeSetPartitionId::Mutator);
1377 return allocate_from_regions(iterator, req, in_new_region);
1378 }
1379
1380 // Allocate from high to low memory. This preserves low memory for humongous allocations.
1381 ShenandoahRightLeftIterator iterator(&_partitions, ShenandoahFreeSetPartitionId::Mutator);
1382 return allocate_from_regions(iterator, req, in_new_region);
1383 }
1384
1385 void ShenandoahFreeSet::update_allocation_bias() {
1386 if (_alloc_bias_weight-- <= 0) {
1387 // We have observed that regions not collected in previous GC cycle tend to congregate at one end or the other
1388 // of the heap. Typically, these are the more recently engaged regions and the objects in these regions have not
1389 // yet had a chance to die (and/or are treated as floating garbage). If we use the same allocation bias on each
1390 // GC pass, these "most recently" engaged regions for GC pass N will also be the "most recently" engaged regions
1391 // for GC pass N+1, and the relatively large amount of live data and/or floating garbage introduced
1392 // during the most recent GC pass may once again prevent the region from being collected. We have found that
1393 // alternating the allocation behavior between GC passes improves evacuation performance by 3-7% on certain
1394 // benchmarks. In the best case, this has the effect of consuming these partially consumed regions before
1395 // the start of the next mark cycle so all of their garbage can be efficiently reclaimed.
1396 //
1397 // First, finish consuming regions that are already partially consumed so as to more tightly limit ranges of
1398 // available regions. Other potential benefits:
1399 // 1. Eventual collection set has fewer regions because we have packed newly allocated objects into fewer regions
1400 // 2. We preserve the "empty" regions longer into the GC cycle, reducing likelihood of allocation failures
1401 // late in the GC cycle.
1402 idx_t non_empty_on_left = (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator)
1403 - _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator));
1404 idx_t non_empty_on_right = (_partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator)
1405 - _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator));
1406 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::Mutator, (non_empty_on_right < non_empty_on_left));
1407 _alloc_bias_weight = INITIAL_ALLOC_BIAS_WEIGHT;
1408 }
1409 }
1410
1411 template<typename Iter>
1412 HeapWord* ShenandoahFreeSet::allocate_from_regions(Iter& iterator, ShenandoahAllocRequest &req, bool &in_new_region) {
1413 for (idx_t idx = iterator.current(); iterator.has_next(); idx = iterator.next()) {
1414 ShenandoahHeapRegion* r = _heap->get_region(idx);
1415 size_t min_size = req.is_lab_alloc() ? req.min_size() : req.size();
1416 if (alloc_capacity(r) >= min_size * HeapWordSize) {
1417 HeapWord* result = try_allocate_in(r, req, in_new_region);
1418 if (result != nullptr) {
1419 return result;
1420 }
1421 }
1422 }
1423 return nullptr;
1424 }
1425
1426 HeapWord* ShenandoahFreeSet::allocate_for_collector(ShenandoahAllocRequest &req, bool &in_new_region) {
1427 shenandoah_assert_heaplocked();
1428 ShenandoahFreeSetPartitionId which_partition = req.is_old()? ShenandoahFreeSetPartitionId::OldCollector: ShenandoahFreeSetPartitionId::Collector;
1429 HeapWord* result = nullptr;
1430 if (_partitions.alloc_from_left_bias(which_partition)) {
1431 ShenandoahLeftRightIterator iterator(&_partitions, which_partition);
1432 result = allocate_with_affiliation(iterator, req.affiliation(), req, in_new_region);
1433 } else {
1434 ShenandoahRightLeftIterator iterator(&_partitions, which_partition);
1435 result = allocate_with_affiliation(iterator, req.affiliation(), req, in_new_region);
1436 }
1437
1438 if (result != nullptr) {
1439 return result;
1440 }
1441
1442 // No dice. Can we borrow space from mutator view?
1443 if (!ShenandoahEvacReserveOverflow) {
1444 return nullptr;
1445 }
1446
1447 if (_partitions.get_empty_region_counts(ShenandoahFreeSetPartitionId::Mutator) > 0) {
1448 // Try to steal an empty region from the mutator view.
1449 result = try_allocate_from_mutator(req, in_new_region);
1450 }
1451
1452 // This is it. Do not try to mix mutator and GC allocations, because adjusting region UWM
1453 // due to GC allocations would expose unparsable mutator allocations.
1454 return result;
1455 }
1456
1457 HeapWord* ShenandoahFreeSet::try_allocate_from_mutator(ShenandoahAllocRequest& req, bool& in_new_region) {
1458 // The collector prefers to keep longer lived regions toward the right side of the heap, so it always
1459 // searches for regions from right to left here.
1460 ShenandoahRightLeftIterator iterator(&_partitions, ShenandoahFreeSetPartitionId::Mutator, true);
1461 for (idx_t idx = iterator.current(); iterator.has_next(); idx = iterator.next()) {
1462 ShenandoahHeapRegion* r = _heap->get_region(idx);
1463 if (can_allocate_from(r)) {
1464 if (req.is_old()) {
1465 if (!flip_to_old_gc(r)) {
1466 continue;
1467 }
1468 } else {
1469 flip_to_gc(r);
1470 }
1471 // Region r is entirely empty. If try_allocate_in fails on region r, something else is really wrong.
1472 // Don't bother to retry with other regions.
1473 log_debug(gc, free)("Flipped region %zu to gc for request: " PTR_FORMAT, idx, p2i(&req));
1474 return try_allocate_in(r, req, in_new_region);
1475 }
1476 }
1477
1478 return nullptr;
1479 }
1480
1481
1482 HeapWord* ShenandoahFreeSet::try_allocate_in(ShenandoahHeapRegion* r, ShenandoahAllocRequest& req, bool& in_new_region) {
1483 assert (has_alloc_capacity(r), "Performance: should avoid full regions on this path: %zu", r->index());
1484 if (_heap->is_concurrent_weak_root_in_progress() && r->is_trash()) {
1485 // We cannot use this region for allocation when weak roots are in progress because the collector may need
1486 // to reference unmarked oops during concurrent classunloading. The collector also needs accurate marking
1487 // information to determine which weak handles need to be null'd out. If the region is recycled before weak
1488 // roots processing has finished, weak root processing may fail to null out a handle into a trashed region.
1489 // This turns the handle into a dangling pointer and will crash or corrupt the heap.
1490 return nullptr;
1491 }
1492 HeapWord* result = nullptr;
1493 // We must call try_recycle_under_lock() even if !r->is_trash(). The reason is that if r is being recycled at this
1494 // moment by a GC worker thread, it may appear to be not trash even though it has not yet been fully recycled. If
1495 // we proceed without waiting for the worker to finish recycling the region, the worker thread may overwrite the
1496 // region's affiliation with FREE after we set the region's affiliation to req.affiliation() below
1497 r->try_recycle_under_lock();
1498 in_new_region = r->is_empty();
1499 if (in_new_region) {
1500 log_debug(gc, free)("Using new region (%zu) for %s (" PTR_FORMAT ").",
1501 r->index(), req.type_string(), p2i(&req));
1502 assert(!r->is_affiliated(), "New region %zu should be unaffiliated", r->index());
1503 r->set_affiliation(req.affiliation());
1504 if (r->is_old()) {
1505 // Any OLD region allocated during concurrent coalesce-and-fill does not need to be coalesced and filled because
1506 // all objects allocated within this region are above TAMS (and thus are implicitly marked). In case this is an
1507 // OLD region and concurrent preparation for mixed evacuations visits this region before the start of the next
1508 // old-gen concurrent mark (i.e. this region is allocated following the start of old-gen concurrent mark but before
1509 // concurrent preparations for mixed evacuations are completed), we mark this region as not requiring any
1510 // coalesce-and-fill processing.
1511 r->end_preemptible_coalesce_and_fill();
1512 }
1513 #ifdef ASSERT
1514 ShenandoahMarkingContext* const ctx = _heap->marking_context();
1515 assert(ctx->top_at_mark_start(r) == r->bottom(), "Newly established allocation region starts with TAMS equal to bottom");
1516 assert(ctx->is_bitmap_range_within_region_clear(ctx->top_bitmap(r), r->end()), "Bitmap above top_bitmap() must be clear");
1517 #endif
1518 log_debug(gc, free)("Using new region (%zu) for %s (" PTR_FORMAT ").",
1519 r->index(), req.type_string(), p2i(&req));
1520 } else {
1521 assert(r->is_affiliated(), "Region %zu that is not new should be affiliated", r->index());
1522 if (r->affiliation() != req.affiliation()) {
1523 assert(_heap->mode()->is_generational(), "Request for %s from %s region should only happen in generational mode.",
1524 req.affiliation_name(), r->affiliation_name());
1525 return nullptr;
1526 }
1527 }
1528
1529 // req.size() is in words, r->free() is in bytes.
1530 if (req.is_lab_alloc()) {
1531 size_t adjusted_size = req.size();
1532 size_t free = align_down(r->free() >> LogHeapWordSize, MinObjAlignment);
1533 if (adjusted_size > free) {
1534 adjusted_size = free;
1535 }
1536 if (adjusted_size >= req.min_size()) {
1537 result = r->allocate(adjusted_size, req);
1538 assert (result != nullptr, "Allocation must succeed: free %zu, actual %zu", free, adjusted_size);
1539 req.set_actual_size(adjusted_size);
1540 } else {
1541 log_trace(gc, free)("Failed to shrink LAB request (%zu) in region %zu to %zu"
1542 " because min_size() is %zu", req.size(), r->index(), adjusted_size, req.min_size());
1543 }
1544 } else {
1545 size_t size = req.size();
1546 result = r->allocate(size, req);
1547 if (result != nullptr) {
1548 // Record actual allocation size
1549 req.set_actual_size(size);
1550 }
1551 }
1552
1553 if (result != nullptr) {
1554 // Allocation successful, bump stats:
1555 if (req.is_mutator_alloc()) {
1556 assert(req.is_young(), "Mutator allocations always come from young generation.");
1557 _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, req.actual_size() * HeapWordSize);
1558 } else {
1559 assert(req.is_gc_alloc(), "Should be gc_alloc since req wasn't mutator alloc");
1560
1561 // For GC allocations, we advance update_watermark because the objects relocated into this memory during
1562 // evacuation are not updated during evacuation. For both young and old regions r, it is essential that all
1563 // PLABs be made parsable at the end of evacuation. This is enabled by retiring all plabs at end of evacuation.
1564 r->set_update_watermark(r->top());
1565 if (r->is_old()) {
1566 _partitions.increase_used(ShenandoahFreeSetPartitionId::OldCollector, (req.actual_size() + req.waste()) * HeapWordSize);
1567 } else {
1568 _partitions.increase_used(ShenandoahFreeSetPartitionId::Collector, (req.actual_size() + req.waste()) * HeapWordSize);
1569 }
1570 }
1571 }
1572
1573 ShenandoahFreeSetPartitionId orig_partition;
1574 if (req.is_mutator_alloc()) {
1575 orig_partition = ShenandoahFreeSetPartitionId::Mutator;
1576 } else if (req.is_old()) {
1577 orig_partition = ShenandoahFreeSetPartitionId::OldCollector;
1578 } else {
1579 // Not old collector alloc, so this is a young collector gclab or shared allocation
1580 orig_partition = ShenandoahFreeSetPartitionId::Collector;
1581 }
1582 DEBUG_ONLY(bool boundary_changed = false;)
1583 if ((result != nullptr) && in_new_region) {
1584 _partitions.one_region_is_no_longer_empty(orig_partition);
1585 DEBUG_ONLY(boundary_changed = true;)
1586 }
1587
1588 if (alloc_capacity(r) < PLAB::min_size() * HeapWordSize) {
1589 // Regardless of whether this allocation succeeded, if the remaining memory is less than PLAB:min_size(), retire this region.
1590 // Note that retire_from_partition() increases used to account for waste.
1591
1592 size_t idx = r->index();
1593 size_t waste_bytes = _partitions.retire_from_partition(orig_partition, idx, r->used());
1594 DEBUG_ONLY(boundary_changed = true;)
1595 if (req.is_mutator_alloc() && (waste_bytes > 0)) {
1596 req.set_waste(waste_bytes / HeapWordSize);
1597 }
1598 }
1599
1600 switch (orig_partition) {
1601 case ShenandoahFreeSetPartitionId::Mutator:
1602 recompute_total_used</* UsedByMutatorChanged */ true,
1603 /* UsedByCollectorChanged */ false, /* UsedByOldCollectorChanged */ false>();
1604 if (in_new_region) {
1605 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ false,
1606 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ false,
1607 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ false,
1608 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ false,
1609 /* UnaffiliatedChangesAreYoungNeutral */ false>();
1610 }
1611 break;
1612 case ShenandoahFreeSetPartitionId::Collector:
1613 recompute_total_used</* UsedByMutatorChanged */ false,
1614 /* UsedByCollectorChanged */ true, /* UsedByOldCollectorChanged */ false>();
1615 if (in_new_region) {
1616 recompute_total_affiliated</* MutatorEmptiesChanged */ false, /* CollectorEmptiesChanged */ true,
1617 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ false,
1618 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ false,
1619 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ false,
1620 /* UnaffiliatedChangesAreYoungNeutral */ false>();
1621 }
1622 break;
1623 case ShenandoahFreeSetPartitionId::OldCollector:
1624 recompute_total_used</* UsedByMutatorChanged */ false,
1625 /* UsedByCollectorChanged */ false, /* UsedByOldCollectorChanged */ true>();
1626 if (in_new_region) {
1627 recompute_total_affiliated</* MutatorEmptiesChanged */ false, /* CollectorEmptiesChanged */ false,
1628 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ false,
1629 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ false,
1630 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ false,
1631 /* UnaffiliatedChangesAreYoungNeutral */ true>();
1632 }
1633 break;
1634 case ShenandoahFreeSetPartitionId::NotFree:
1635 default:
1636 assert(false, "won't happen");
1637 }
1638 #ifdef ASSERT
1639 if (boundary_changed) {
1640 _partitions.assert_bounds();
1641 } else {
1642 _partitions.assert_bounds_sanity();
1643 }
1644 #endif
1645 return result;
1646 }
1647
1648 HeapWord* ShenandoahFreeSet::allocate_contiguous(ShenandoahAllocRequest& req, bool is_humongous) {
1649 assert(req.is_mutator_alloc(), "All contiguous allocations are performed by mutator");
1650 shenandoah_assert_heaplocked();
1651
1652 size_t words_size = req.size();
1653 idx_t num = ShenandoahHeapRegion::required_regions(words_size * HeapWordSize);
1654
1655 assert(req.is_young(), "Humongous regions always allocated in YOUNG");
1656
1657 // Check if there are enough regions left to satisfy allocation.
1658 if (num > (idx_t) _partitions.count(ShenandoahFreeSetPartitionId::Mutator)) {
1659 return nullptr;
1660 }
1661
1662 idx_t start_range = _partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator);
1663 idx_t end_range = _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator) + 1;
1664 idx_t last_possible_start = end_range - num;
1665
1666 // Find the continuous interval of $num regions, starting from $beg and ending in $end,
1667 // inclusive. Contiguous allocations are biased to the beginning.
1668 idx_t beg = _partitions.find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId::Mutator,
1669 start_range, num);
1670 if (beg > last_possible_start) {
1671 // Hit the end, goodbye
1672 return nullptr;
1673 }
1674 idx_t end = beg;
1675
1676 while (true) {
1677 // We've confirmed num contiguous regions belonging to Mutator partition, so no need to confirm membership.
1678 // If region is not completely free, the current [beg; end] is useless, and we may fast-forward. If we can extend
1679 // the existing range, we can exploit that certain regions are already known to be in the Mutator free set.
1680 while (!can_allocate_from(_heap->get_region(end))) {
1681 // region[end] is not empty, so we restart our search after region[end]
1682 idx_t slide_delta = end + 1 - beg;
1683 if (beg + slide_delta > last_possible_start) {
1684 // no room to slide
1685 return nullptr;
1686 }
1687 for (idx_t span_end = beg + num; slide_delta > 0; slide_delta--) {
1688 if (!_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, span_end)) {
1689 beg = _partitions.find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId::Mutator,
1690 span_end + 1, num);
1691 break;
1692 } else {
1693 beg++;
1694 span_end++;
1695 }
1696 }
1697 // Here, either beg identifies a range of num regions all of which are in the Mutator free set, or beg > last_possible_start
1698 if (beg > last_possible_start) {
1699 // Hit the end, goodbye
1700 return nullptr;
1701 }
1702 end = beg;
1703 }
1704
1705 if ((end - beg + 1) == num) {
1706 // found the match
1707 break;
1708 }
1709 end++;
1710 }
1711
1712 size_t total_used = 0;
1713 const size_t used_words_in_last_region = words_size & ShenandoahHeapRegion::region_size_words_mask();
1714 size_t waste_bytes;
1715 // Retire regions from free partition and initialize them.
1716 if (is_humongous) {
1717 // Humongous allocation retires all regions at once: no allocation is possible anymore.
1718 // retire_range_from_partition() will adjust bounds on Mutator free set if appropriate and will recompute affiliated.
1719 _partitions.retire_range_from_partition(ShenandoahFreeSetPartitionId::Mutator, beg, end);
1720 for (idx_t i = beg; i <= end; i++) {
1721 ShenandoahHeapRegion* r = _heap->get_region(i);
1722 assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous");
1723 r->try_recycle_under_lock();
1724 assert(r->is_empty(), "Should be empty");
1725 r->set_affiliation(req.affiliation());
1726 if (i == beg) {
1727 r->make_humongous_start();
1728 } else {
1729 r->make_humongous_cont();
1730 }
1731 if ((i == end) && (used_words_in_last_region > 0)) {
1732 r->set_top(r->bottom() + used_words_in_last_region);
1733 } else {
1734 // if used_words_in_last_region is zero, then the end region is fully consumed.
1735 r->set_top(r->end());
1736 }
1737 r->set_update_watermark(r->bottom());
1738 }
1739 total_used = ShenandoahHeapRegion::region_size_bytes() * num;
1740 waste_bytes =
1741 (used_words_in_last_region == 0)? 0: ShenandoahHeapRegion::region_size_bytes() - used_words_in_last_region * HeapWordSize;
1742 } else {
1743 // Non-humongous allocation retires only the regions that cannot be used for allocation anymore.
1744 waste_bytes = 0;
1745 for (idx_t i = beg; i <= end; i++) {
1746 ShenandoahHeapRegion* r = _heap->get_region(i);
1747 assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous");
1748 r->try_recycle_under_lock();
1749 assert(r->is_empty(), "Should be empty");
1750 r->set_affiliation(req.affiliation());
1751 r->make_regular_allocation(req.affiliation());
1752 if ((i == end) && (used_words_in_last_region > 0)) {
1753 r->set_top(r->bottom() + used_words_in_last_region);
1754 } else {
1755 // if used_words_in_last_region is zero, then the end region is fully consumed.
1756 r->set_top(r->end());
1757 }
1758 r->set_update_watermark(r->bottom());
1759 total_used += r->used();
1760 if (r->free() < PLAB::min_size() * HeapWordSize) {
1761 // retire_from_partition() will adjust bounds on Mutator free set if appropriate and will recompute affiliated.
1762 // It also increases used for the waste bytes, which includes bytes filled at retirement and bytes too small
1763 // to be filled. Only the last iteration may have non-zero waste_bytes.
1764 waste_bytes += _partitions.retire_from_partition(ShenandoahFreeSetPartitionId::Mutator, i, r->used());
1765 }
1766 }
1767 _partitions.decrease_empty_region_counts(ShenandoahFreeSetPartitionId::Mutator, num);
1768 }
1769
1770 _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, total_used);
1771 req.set_actual_size(words_size);
1772 // If !is_humongous, the "waste" is made availabe for new allocation
1773 if (waste_bytes > 0) {
1774 req.set_waste(waste_bytes / HeapWordSize);
1775 if (is_humongous) {
1776 _partitions.increase_humongous_waste(ShenandoahFreeSetPartitionId::Mutator, waste_bytes);
1777 _total_humongous_waste += waste_bytes;
1778 }
1779 }
1780
1781 recompute_total_young_used</* UsedByMutatorChanged */ true, /*UsedByCollectorChanged */ false>();
1782 recompute_total_global_used</* UsedByMutatorChanged */ true, /*UsedByCollectorChanged */ false,
1783 /* UsedByOldCollectorChanged */ true>();
1784 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ false,
1785 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ false,
1786 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ false,
1787 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ false,
1788 /* UnaffiliatedChangesAreYoungNeutral */ false>();
1789 _partitions.assert_bounds();
1790 return _heap->get_region(beg)->bottom();
1791 }
1792
1793 class ShenandoahRecycleTrashedRegionClosure final : public ShenandoahHeapRegionClosure {
1794 public:
1795 void heap_region_do(ShenandoahHeapRegion* r) {
1796 if (r->is_trash()) {
1797 r->try_recycle();
1798 }
1799 }
1800
1801 bool is_thread_safe() {
1802 return true;
1803 }
1804 };
1805
1806 void ShenandoahFreeSet::recycle_trash() {
1807 // lock is not non-reentrant, check we don't have it
1808 shenandoah_assert_not_heaplocked();
1809
1810 ShenandoahHeap* heap = ShenandoahHeap::heap();
1811 heap->assert_gc_workers(heap->workers()->active_workers());
1812
1813 ShenandoahRecycleTrashedRegionClosure closure;
1814 heap->parallel_heap_region_iterate(&closure);
1815 }
1816
1817 bool ShenandoahFreeSet::transfer_one_region_from_mutator_to_old_collector(size_t idx, size_t alloc_capacity) {
1818 ShenandoahGenerationalHeap* gen_heap = ShenandoahGenerationalHeap::heap();
1819 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1820 assert(alloc_capacity == region_size_bytes, "Region must be empty");
1821 if (young_unaffiliated_regions() > 0) {
1822 _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
1823 ShenandoahFreeSetPartitionId::OldCollector, alloc_capacity);
1824 gen_heap->old_generation()->augment_evacuation_reserve(alloc_capacity);
1825 recompute_total_used</* UsedByMutatorChanged */ true,
1826 /* UsedByCollectorChanged */ false, /* UsedByOldCollectorChanged */ true>();
1827 // Transferred region is unaffilliated, empty
1828 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ false,
1829 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
1830 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ true,
1831 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
1832 /* UnaffiliatedChangesAreYoungNeutral */ false>();
1833 _partitions.assert_bounds();
1834 return true;
1835 } else {
1836 return false;
1837 }
1838 }
1839
1840 bool ShenandoahFreeSet::flip_to_old_gc(ShenandoahHeapRegion* r) {
1841 const size_t idx = r->index();
1842
1843 assert(_partitions.partition_id_matches(idx, ShenandoahFreeSetPartitionId::Mutator), "Should be in mutator view");
1844 assert(can_allocate_from(r), "Should not be allocated");
1845
1846 const size_t region_alloc_capacity = alloc_capacity(r);
1847
1848 if (transfer_one_region_from_mutator_to_old_collector(idx, region_alloc_capacity)) {
1849 return true;
1850 }
1851
1852 if (_heap->young_generation()->free_unaffiliated_regions() == 0 && _heap->old_generation()->free_unaffiliated_regions() > 0) {
1853 // Old has free unaffiliated regions, but it couldn't use them for allocation (likely because they
1854 // are trash and weak roots are in process). In this scenario, we aren't really stealing from the
1855 // mutator (they have nothing to steal), but they do have a usable region in their partition. What
1856 // we want to do here is swap that region from the mutator partition with one from the old collector
1857 // partition.
1858 // 1. Find a temporarily unusable trash region in the old collector partition
1859 ShenandoahRightLeftIterator iterator(&_partitions, ShenandoahFreeSetPartitionId::OldCollector, true);
1860 idx_t unusable_trash = -1;
1861 for (unusable_trash = iterator.current(); iterator.has_next(); unusable_trash = iterator.next()) {
1862 const ShenandoahHeapRegion* region = _heap->get_region(unusable_trash);
1863 if (region->is_trash() && _heap->is_concurrent_weak_root_in_progress()) {
1864 break;
1865 }
1866 }
1867
1868 if (unusable_trash != -1) {
1869 const size_t unusable_capacity = alloc_capacity(unusable_trash);
1870 // 2. Move the (temporarily) unusable trash region we found to the mutator partition
1871 _partitions.move_from_partition_to_partition(unusable_trash,
1872 ShenandoahFreeSetPartitionId::OldCollector,
1873 ShenandoahFreeSetPartitionId::Mutator, unusable_capacity);
1874
1875 // 3. Move this usable region from the mutator partition to the old collector partition
1876 _partitions.move_from_partition_to_partition(idx,
1877 ShenandoahFreeSetPartitionId::Mutator,
1878 ShenandoahFreeSetPartitionId::OldCollector, region_alloc_capacity);
1879 // Should have no effect on used, since flipped regions are trashed: zero used */
1880 // Transferred regions are not affiliated, because they are empty (trash)
1881 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ false,
1882 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
1883 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ true,
1884 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
1885 /* UnaffiliatedChangesAreYoungNeutral */ false>();
1886 _partitions.assert_bounds();
1887 // 4. Do not adjust capacities for generations, we just swapped the regions that have already
1888 // been accounted for. However, we should adjust the evacuation reserves as those may have changed.
1889 shenandoah_assert_heaplocked();
1890 const size_t reserve = _heap->old_generation()->get_evacuation_reserve();
1891 _heap->old_generation()->set_evacuation_reserve(reserve - unusable_capacity + region_alloc_capacity);
1892 return true;
1893 }
1894 }
1895
1896 // We can't take this region young because it has no free unaffiliated regions (transfer failed).
1897 return false;
1898 }
1899
1900 void ShenandoahFreeSet::flip_to_gc(ShenandoahHeapRegion* r) {
1901 size_t idx = r->index();
1902
1903 assert(_partitions.partition_id_matches(idx, ShenandoahFreeSetPartitionId::Mutator), "Should be in mutator view");
1904 assert(can_allocate_from(r), "Should not be allocated");
1905
1906 size_t ac = alloc_capacity(r);
1907 _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
1908 ShenandoahFreeSetPartitionId::Collector, ac);
1909 recompute_total_used</* UsedByMutatorChanged */ true,
1910 /* UsedByCollectorChanged */ false, /* UsedByOldCollectorChanged */ true>();
1911 // Transfer only affects unaffiliated regions, which stay in young
1912 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ true,
1913 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ true,
1914 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ false,
1915 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
1916 /* UnaffiliatedChangesAreYoungNeutral */ true>();
1917 _partitions.assert_bounds();
1918 // We do not ensure that the region is no longer trash, relying on try_allocate_in(), which always comes next,
1919 // to recycle trash before attempting to allocate anything in the region.
1920 }
1921
1922 void ShenandoahFreeSet::clear() {
1923 clear_internal();
1924 }
1925
1926 void ShenandoahFreeSet::clear_internal() {
1927 shenandoah_assert_heaplocked();
1928 _partitions.make_all_regions_unavailable();
1929 recompute_total_used</* UsedByMutatorChanged */ true,
1930 /* UsedByCollectorChanged */ true, /* UsedByOldCollectorChanged */ true>();
1931 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ true,
1932 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
1933 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ true,
1934 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
1935 /* UnaffiliatedChangesAreYoungNeutral */ true>();
1936 _alloc_bias_weight = 0;
1937 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::Mutator, true);
1938 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::Collector, false);
1939 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::OldCollector, false);
1940 }
1941
1942 // Returns total allocatable words in Mutator partition
1943 size_t ShenandoahFreeSet::find_regions_with_alloc_capacity(size_t &young_trashed_regions, size_t &old_trashed_regions,
1944 size_t &first_old_region, size_t &last_old_region,
1945 size_t &old_region_count) {
1946 // This resets all state information, removing all regions from all sets.
1947 clear_internal();
1948
1949 first_old_region = _heap->num_regions();
1950 last_old_region = 0;
1951 old_region_count = 0;
1952 old_trashed_regions = 0;
1953 young_trashed_regions = 0;
1954
1955 size_t old_cset_regions = 0;
1956 size_t young_cset_regions = 0;
1957
1958 size_t region_size_bytes = _partitions.region_size_bytes();
1959 size_t max_regions = _partitions.max();
1960
1961 size_t mutator_alloc_capacity_in_words = 0;
1962
1963 size_t mutator_leftmost = max_regions;
1964 size_t mutator_rightmost = 0;
1965 size_t mutator_leftmost_empty = max_regions;
1966 size_t mutator_rightmost_empty = 0;
1967
1968 size_t old_collector_leftmost = max_regions;
1969 size_t old_collector_rightmost = 0;
1970 size_t old_collector_leftmost_empty = max_regions;
1971 size_t old_collector_rightmost_empty = 0;
1972
1973 size_t mutator_empty = 0;
1974 size_t old_collector_empty = 0;
1975
1976 // These two variables represent the total used within each partition, including humongous waste and retired regions
1977 size_t mutator_used = 0;
1978 size_t old_collector_used = 0;
1979
1980 // These two variables represent memory that is wasted within humongous regions due to alignment padding
1981 size_t mutator_humongous_waste = 0;
1982 size_t old_collector_humongous_waste = 0;
1983
1984 // These two variables track regions that have allocatable memory
1985 size_t mutator_regions = 0;
1986 size_t old_collector_regions = 0;
1987
1988 // These two variables track regions that are not empty within each partition
1989 size_t affiliated_mutator_regions = 0;
1990 size_t affiliated_old_collector_regions = 0;
1991
1992 // These two variables represent the total capacity of each partition, including retired regions
1993 size_t total_mutator_regions = 0;
1994 size_t total_old_collector_regions = 0;
1995
1996 size_t num_regions = _heap->num_regions();
1997 for (size_t idx = 0; idx < num_regions; idx++) {
1998 ShenandoahHeapRegion* region = _heap->get_region(idx);
1999 if (region->is_trash()) {
2000 // Trashed regions represent regions that had been in the collection set (or may have been identified as immediate garbage)
2001 // but have not yet been "cleaned up". The cset regions are not "trashed" until we have finished update refs.
2002 if (region->is_old()) {
2003 // We're going to place this region into the Mutator set. We increment old_trashed_regions because this count represents
2004 // regions that the old generation is entitled to without any transfer from young. We do not place this region into
2005 // the OldCollector partition at this time. Instead, we let reserve_regions() decide whether to place this region
2006 // into the OldCollector partition. Deferring the decision allows reserve_regions() to more effectively pack the
2007 // OldCollector regions into high-address memory. We do not adjust capacities of old and young generations at this
2008 // time. At the end of finish_rebuild(), the capacities are adjusted based on the results of reserve_regions().
2009 old_trashed_regions++;
2010 } else {
2011 assert(region->is_young(), "Trashed region should be old or young");
2012 young_trashed_regions++;
2013 }
2014 } else if (region->is_old()) {
2015 // We count humongous and regular regions as "old regions". We do not count trashed regions that are old. Those
2016 // are counted (above) as old_trashed_regions.
2017 old_region_count++;
2018 if (first_old_region > idx) {
2019 first_old_region = idx;
2020 }
2021 last_old_region = idx;
2022 }
2023 if (region->is_alloc_allowed() || region->is_trash()) {
2024 assert(!region->is_cset(), "Shouldn't be adding cset regions to the free set");
2025
2026 // Do not add regions that would almost surely fail allocation
2027 size_t ac = alloc_capacity(region);
2028 if (ac >= PLAB::min_size() * HeapWordSize) {
2029 if (region->is_trash() || !region->is_old()) {
2030 // Both young and old (possibly immediately) collected regions (trashed) are placed into the Mutator set
2031 _partitions.raw_assign_membership(idx, ShenandoahFreeSetPartitionId::Mutator);
2032 mutator_alloc_capacity_in_words += ac / HeapWordSize;
2033 if (idx < mutator_leftmost) {
2034 mutator_leftmost = idx;
2035 }
2036 if (idx > mutator_rightmost) {
2037 mutator_rightmost = idx;
2038 }
2039 if (ac == region_size_bytes) {
2040 mutator_empty++;
2041 if (idx < mutator_leftmost_empty) {
2042 mutator_leftmost_empty = idx;
2043 }
2044 if (idx > mutator_rightmost_empty) {
2045 mutator_rightmost_empty = idx;
2046 }
2047 } else {
2048 affiliated_mutator_regions++;
2049 }
2050 mutator_regions++;
2051 total_mutator_regions++;
2052 mutator_used += (region_size_bytes - ac);
2053 } else {
2054 // !region->is_trash() && region is_old()
2055 _partitions.raw_assign_membership(idx, ShenandoahFreeSetPartitionId::OldCollector);
2056 if (idx < old_collector_leftmost) {
2057 old_collector_leftmost = idx;
2058 }
2059 if (idx > old_collector_rightmost) {
2060 old_collector_rightmost = idx;
2061 }
2062 assert(ac != region_size_bytes, "Empty regions should be in mutator partition");
2063 affiliated_old_collector_regions++;
2064 old_collector_regions++;
2065 total_old_collector_regions++;
2066 old_collector_used += region_size_bytes - ac;
2067 }
2068 } else {
2069 // This region does not have enough free to be part of the free set. Count all of its memory as used.
2070 assert(_partitions.membership(idx) == ShenandoahFreeSetPartitionId::NotFree, "Region should have been retired");
2071 if (region->is_old()) {
2072 old_collector_used += region_size_bytes;
2073 total_old_collector_regions++;
2074 affiliated_old_collector_regions++;
2075 } else {
2076 mutator_used += region_size_bytes;
2077 total_mutator_regions++;
2078 affiliated_mutator_regions++;
2079 }
2080 }
2081 } else {
2082 // This region does not allow allocation (it is retired or is humongous or is in cset).
2083 // Retired and humongous regions generally have no alloc capacity, but cset regions may have large alloc capacity.
2084 if (region->is_cset()) {
2085 if (region->is_old()) {
2086 old_cset_regions++;
2087 } else {
2088 young_cset_regions++;
2089 }
2090 } else {
2091 assert(_partitions.membership(idx) == ShenandoahFreeSetPartitionId::NotFree, "Region should have been retired");
2092 size_t humongous_waste_bytes = 0;
2093 if (region->is_humongous_start()) {
2094 // Since rebuild does not necessarily happen at a safepoint, a newly allocated humongous object may not have been
2095 // fully initialized. Therefore, we cannot safely consult its header.
2096 ShenandoahHeapRegion* last_of_humongous_continuation = region;
2097 size_t next_idx;
2098 for (next_idx = idx + 1; next_idx < num_regions; next_idx++) {
2099 ShenandoahHeapRegion* humongous_cont_candidate = _heap->get_region(next_idx);
2100 if (!humongous_cont_candidate->is_humongous_continuation()) {
2101 break;
2102 }
2103 last_of_humongous_continuation = humongous_cont_candidate;
2104 }
2105 // For humongous regions, used() is established while holding the global heap lock so it is reliable here
2106 humongous_waste_bytes = ShenandoahHeapRegion::region_size_bytes() - last_of_humongous_continuation->used();
2107 }
2108 if (region->is_old()) {
2109 old_collector_used += region_size_bytes;
2110 total_old_collector_regions++;
2111 old_collector_humongous_waste += humongous_waste_bytes;
2112 affiliated_old_collector_regions++;
2113 } else {
2114 mutator_used += region_size_bytes;
2115 total_mutator_regions++;
2116 mutator_humongous_waste += humongous_waste_bytes;
2117 affiliated_mutator_regions++;
2118 }
2119 }
2120 }
2121 }
2122 // At the start of evacuation, the cset regions are not counted as part of Mutator or OldCollector partitions.
2123
2124 // At the end of GC, when we rebuild rebuild freeset (which happens before we have recycled the collection set), we treat
2125 // all cset regions as part of capacity, as fully available, as unaffiliated. We place trashed regions into the Mutator
2126 // partition.
2127
2128 // No need to update generation sizes here. These are the sizes already recognized by the generations. These
2129 // adjustments allow the freeset tallies to match the generation tallies.
2130
2131 log_debug(gc, free)(" At end of prep_to_rebuild, mutator_leftmost: %zu"
2132 ", mutator_rightmost: %zu"
2133 ", mutator_leftmost_empty: %zu"
2134 ", mutator_rightmost_empty: %zu"
2135 ", mutator_regions: %zu"
2136 ", mutator_used: %zu",
2137 mutator_leftmost, mutator_rightmost, mutator_leftmost_empty, mutator_rightmost_empty,
2138 mutator_regions, mutator_used);
2139 log_debug(gc, free)(" old_collector_leftmost: %zu"
2140 ", old_collector_rightmost: %zu"
2141 ", old_collector_leftmost_empty: %zu"
2142 ", old_collector_rightmost_empty: %zu"
2143 ", old_collector_regions: %zu"
2144 ", old_collector_used: %zu",
2145 old_collector_leftmost, old_collector_rightmost, old_collector_leftmost_empty, old_collector_rightmost_empty,
2146 old_collector_regions, old_collector_used);
2147 log_debug(gc, free)(" total_mutator_regions: %zu, total_old_collector_regions: %zu"
2148 ", mutator_empty: %zu, old_collector_empty: %zu",
2149 total_mutator_regions, total_old_collector_regions, mutator_empty, old_collector_empty);
2150
2151 idx_t rightmost_idx = (mutator_leftmost == max_regions)? -1: (idx_t) mutator_rightmost;
2152 idx_t rightmost_empty_idx = (mutator_leftmost_empty == max_regions)? -1: (idx_t) mutator_rightmost_empty;
2153
2154 _partitions.establish_mutator_intervals(mutator_leftmost, rightmost_idx, mutator_leftmost_empty, rightmost_empty_idx,
2155 total_mutator_regions + young_cset_regions, mutator_empty, mutator_regions,
2156 mutator_used + young_cset_regions * region_size_bytes, mutator_humongous_waste);
2157 rightmost_idx = (old_collector_leftmost == max_regions)? -1: (idx_t) old_collector_rightmost;
2158 rightmost_empty_idx = (old_collector_leftmost_empty == max_regions)? -1: (idx_t) old_collector_rightmost_empty;
2159 _partitions.establish_old_collector_intervals(old_collector_leftmost, rightmost_idx,
2160 old_collector_leftmost_empty, rightmost_empty_idx,
2161 total_old_collector_regions + old_cset_regions,
2162 old_collector_empty, old_collector_regions,
2163 old_collector_used + old_cset_regions * region_size_bytes,
2164 old_collector_humongous_waste);
2165 _total_humongous_waste = mutator_humongous_waste + old_collector_humongous_waste;
2166 _total_young_regions = total_mutator_regions + young_cset_regions;
2167 _total_global_regions = _total_young_regions + total_old_collector_regions + old_cset_regions;
2168 recompute_total_used</* UsedByMutatorChanged */ true,
2169 /* UsedByCollectorChanged */ true, /* UsedByOldCollectorChanged */ true>();
2170 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ true,
2171 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
2172 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ true,
2173 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ false,
2174 /* UnaffiliatedChangesAreYoungNeutral */ false>();
2175 _partitions.assert_bounds();
2176 #ifdef ASSERT
2177 if (_heap->mode()->is_generational()) {
2178 assert(young_affiliated_regions() == _heap->young_generation()->get_affiliated_region_count(), "sanity");
2179 } else {
2180 assert(young_affiliated_regions() == _heap->global_generation()->get_affiliated_region_count(), "sanity");
2181 }
2182 #endif
2183 log_debug(gc, free)(" After find_regions_with_alloc_capacity(), Mutator range [%zd, %zd],"
2184 " Old Collector range [%zd, %zd]",
2185 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
2186 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
2187 _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector),
2188 _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector));
2189 return mutator_alloc_capacity_in_words;
2190 }
2191
2192 void ShenandoahFreeSet::transfer_humongous_regions_from_mutator_to_old_collector(size_t xfer_regions,
2193 size_t humongous_waste_bytes) {
2194 shenandoah_assert_heaplocked();
2195 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
2196
2197 _partitions.decrease_humongous_waste(ShenandoahFreeSetPartitionId::Mutator, humongous_waste_bytes);
2198 _partitions.decrease_used(ShenandoahFreeSetPartitionId::Mutator, xfer_regions * region_size_bytes);
2199 _partitions.decrease_capacity(ShenandoahFreeSetPartitionId::Mutator, xfer_regions * region_size_bytes);
2200
2201 _partitions.increase_capacity(ShenandoahFreeSetPartitionId::OldCollector, xfer_regions * region_size_bytes);
2202 _partitions.increase_humongous_waste(ShenandoahFreeSetPartitionId::OldCollector, humongous_waste_bytes);
2203 _partitions.increase_used(ShenandoahFreeSetPartitionId::OldCollector, xfer_regions * region_size_bytes);
2204
2205 // _total_humongous_waste, _total_global_regions are unaffected by transfer
2206 _total_young_regions -= xfer_regions;
2207 recompute_total_young_used</* UsedByMutatorChanged */ true, /* UsedByCollectorChanged */ false>();
2208 recompute_total_old_used</* UsedByOldCollectorChanged */ true>();
2209 recompute_total_affiliated</* MutatorEmptiesChanged */ false, /* CollectorEmptiesChanged */ false,
2210 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ true,
2211 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ true,
2212 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ true,
2213 /* UnaffiliatedChangesAreYoungNeutral */ true>();
2214 _partitions.assert_bounds();
2215 // global_used is unaffected by this transfer
2216
2217 // No need to adjust ranges because humongous regions are not allocatable
2218 }
2219
2220 void ShenandoahFreeSet::transfer_empty_regions_from_to(ShenandoahFreeSetPartitionId source,
2221 ShenandoahFreeSetPartitionId dest,
2222 size_t num_regions) {
2223 assert(dest != source, "precondition");
2224 shenandoah_assert_heaplocked();
2225 const size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
2226 size_t transferred_regions = 0;
2227 size_t used_transfer = 0;
2228 idx_t source_low_idx = _partitions.max();
2229 idx_t source_high_idx = -1;
2230 idx_t dest_low_idx = _partitions.max();
2231 idx_t dest_high_idx = -1;
2232 ShenandoahLeftRightIterator iterator(&_partitions, source, true);
2233 for (idx_t idx = iterator.current(); transferred_regions < num_regions && iterator.has_next(); idx = iterator.next()) {
2234 // Note: can_allocate_from() denotes that region is entirely empty
2235 if (can_allocate_from(idx)) {
2236 if (idx < source_low_idx) {
2237 source_low_idx = idx;
2238 }
2239 if (idx > source_high_idx) {
2240 source_high_idx = idx;
2241 }
2242 if (idx < dest_low_idx) {
2243 dest_low_idx = idx;
2244 }
2245 if (idx > dest_high_idx) {
2246 dest_high_idx = idx;
2247 }
2248 used_transfer += _partitions.move_from_partition_to_partition_with_deferred_accounting(idx, source, dest, region_size_bytes);
2249 transferred_regions++;
2250 }
2251 }
2252
2253 // All transferred regions are empty.
2254 assert(used_transfer == 0, "empty regions should have no used");
2255 _partitions.expand_interval_if_range_modifies_either_boundary(dest, dest_low_idx,
2256 dest_high_idx, dest_low_idx, dest_high_idx);
2257 _partitions.shrink_interval_if_range_modifies_either_boundary(source, source_low_idx, source_high_idx,
2258 transferred_regions);
2259
2260 _partitions.decrease_region_counts(source, transferred_regions);
2261 _partitions.decrease_empty_region_counts(source, transferred_regions);
2262 _partitions.decrease_capacity(source, transferred_regions * region_size_bytes);
2263
2264 _partitions.increase_capacity(dest, transferred_regions * region_size_bytes);
2265 _partitions.increase_region_counts(dest, transferred_regions);
2266 _partitions.increase_empty_region_counts(dest, transferred_regions);
2267
2268 // Since only empty regions are transferred, no need to recompute_total_used()
2269 if (source == ShenandoahFreeSetPartitionId::OldCollector) {
2270 assert((dest == ShenandoahFreeSetPartitionId::Collector) || (dest == ShenandoahFreeSetPartitionId::Mutator), "sanity");
2271 _total_young_regions += transferred_regions;
2272 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ true,
2273 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
2274 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ true,
2275 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
2276 /* UnaffiliatedChangesAreYoungNeutral */ false>();
2277 } else {
2278 assert((source == ShenandoahFreeSetPartitionId::Collector) || (source == ShenandoahFreeSetPartitionId::Mutator), "sanity");
2279 if (dest == ShenandoahFreeSetPartitionId::OldCollector) {
2280 _total_young_regions -= transferred_regions;
2281 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ true,
2282 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
2283 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ true,
2284 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
2285 /* UnaffiliatedChangesAreYoungNeutral */ false>();
2286 } else {
2287 assert((dest == ShenandoahFreeSetPartitionId::Collector) || (dest == ShenandoahFreeSetPartitionId::Mutator), "sanity");
2288 // No adjustments to total_young_regions if transferring within young
2289 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ true,
2290 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ true,
2291 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ false,
2292 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
2293 /* UnaffiliatedChangesAreYoungNeutral */ true>();
2294 }
2295 }
2296 _partitions.assert_bounds();
2297 }
2298
2299 // Returns number of regions transferred, adds transferred bytes to var argument bytes_transferred
2300 size_t ShenandoahFreeSet::transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
2301 size_t max_xfer_regions,
2302 size_t& bytes_transferred) {
2303 shenandoah_assert_heaplocked();
2304 const size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
2305 size_t transferred_regions = 0;
2306 size_t used_transfer = 0;
2307 idx_t collector_low_idx = _partitions.max();
2308 idx_t collector_high_idx = -1;
2309 idx_t mutator_low_idx = _partitions.max();
2310 idx_t mutator_high_idx = -1;
2311 ShenandoahLeftRightIterator iterator(&_partitions, which_collector, true);
2312 for (idx_t idx = iterator.current(); transferred_regions < max_xfer_regions && iterator.has_next(); idx = iterator.next()) {
2313 // Note: can_allocate_from() denotes that region is entirely empty
2314 if (can_allocate_from(idx)) {
2315 if (idx < collector_low_idx) {
2316 collector_low_idx = idx;
2317 }
2318 if (idx > collector_high_idx) {
2319 collector_high_idx = idx;
2320 }
2321 if (idx < mutator_low_idx) {
2322 mutator_low_idx = idx;
2323 }
2324 if (idx > mutator_high_idx) {
2325 mutator_high_idx = idx;
2326 }
2327 used_transfer += _partitions.move_from_partition_to_partition_with_deferred_accounting(idx, which_collector,
2328 ShenandoahFreeSetPartitionId::Mutator,
2329 region_size_bytes);
2330 transferred_regions++;
2331 bytes_transferred += region_size_bytes;
2332 }
2333 }
2334 // All transferred regions are empty.
2335 assert(used_transfer == 0, "empty regions should have no used");
2336 _partitions.expand_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId::Mutator, mutator_low_idx,
2337 mutator_high_idx, mutator_low_idx, mutator_high_idx);
2338 _partitions.shrink_interval_if_range_modifies_either_boundary(which_collector, collector_low_idx, collector_high_idx,
2339 transferred_regions);
2340
2341 _partitions.decrease_region_counts(which_collector, transferred_regions);
2342 _partitions.decrease_empty_region_counts(which_collector, transferred_regions);
2343 _partitions.decrease_capacity(which_collector, transferred_regions * region_size_bytes);
2344
2345 _partitions.increase_capacity(ShenandoahFreeSetPartitionId::Mutator, transferred_regions * region_size_bytes);
2346 _partitions.increase_region_counts(ShenandoahFreeSetPartitionId::Mutator, transferred_regions);
2347 _partitions.increase_empty_region_counts(ShenandoahFreeSetPartitionId::Mutator, transferred_regions);
2348
2349 if (which_collector == ShenandoahFreeSetPartitionId::OldCollector) {
2350 _total_young_regions += transferred_regions;
2351 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ false,
2352 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
2353 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ true,
2354 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
2355 /* UnaffiliatedChangesAreYoungNeutral */ false>();
2356 } else {
2357 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ true,
2358 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ true,
2359 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ false,
2360 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
2361 /* UnaffiliatedChangesAreYoungNeutral */ true>();
2362 }
2363 _partitions.assert_bounds();
2364 return transferred_regions;
2365 }
2366
2367 // Returns number of regions transferred, adds transferred bytes to var argument bytes_transferred
2368 size_t ShenandoahFreeSet::
2369 transfer_non_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
2370 size_t max_xfer_regions, size_t& bytes_transferred) {
2371 shenandoah_assert_heaplocked();
2372 size_t region_size_bytes = _partitions.region_size_bytes();
2373 size_t transferred_regions = 0;
2374 size_t used_transfer = 0;
2375 idx_t collector_low_idx = _partitions.max();
2376 idx_t collector_high_idx = -1;
2377 idx_t mutator_low_idx = _partitions.max();
2378 idx_t mutator_high_idx = -1;
2379
2380 ShenandoahLeftRightIterator iterator(&_partitions, which_collector, false);
2381 for (idx_t idx = iterator.current(); transferred_regions < max_xfer_regions && iterator.has_next(); idx = iterator.next()) {
2382 size_t ac = alloc_capacity(idx);
2383 if (ac > 0) {
2384 if (idx < collector_low_idx) {
2385 collector_low_idx = idx;
2386 }
2387 if (idx > collector_high_idx) {
2388 collector_high_idx = idx;
2389 }
2390 if (idx < mutator_low_idx) {
2391 mutator_low_idx = idx;
2392 }
2393 if (idx > mutator_high_idx) {
2394 mutator_high_idx = idx;
2395 }
2396 assert (ac < region_size_bytes, "Move empty regions with different function");
2397 used_transfer += _partitions.move_from_partition_to_partition_with_deferred_accounting(idx, which_collector,
2398 ShenandoahFreeSetPartitionId::Mutator,
2399 ac);
2400 transferred_regions++;
2401 bytes_transferred += ac;
2402 }
2403 }
2404 // _empty_region_counts is unaffected, because we transfer only non-empty regions here.
2405
2406 _partitions.decrease_used(which_collector, used_transfer);
2407 _partitions.expand_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId::Mutator,
2408 mutator_low_idx, mutator_high_idx, _partitions.max(), -1);
2409 _partitions.shrink_interval_if_range_modifies_either_boundary(which_collector, collector_low_idx, collector_high_idx,
2410 transferred_regions);
2411
2412 _partitions.decrease_region_counts(which_collector, transferred_regions);
2413 _partitions.decrease_capacity(which_collector, transferred_regions * region_size_bytes);
2414 _partitions.increase_capacity(ShenandoahFreeSetPartitionId::Mutator, transferred_regions * region_size_bytes);
2415 _partitions.increase_region_counts(ShenandoahFreeSetPartitionId::Mutator, transferred_regions);
2416 _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, used_transfer);
2417
2418 if (which_collector == ShenandoahFreeSetPartitionId::OldCollector) {
2419 _total_young_regions += transferred_regions;
2420 }
2421 // _total_global_regions unaffected by transfer
2422 recompute_total_used</* UsedByMutatorChanged */ true,
2423 /* UsedByCollectorChanged */ true, /* UsedByOldCollectorChanged */ true>();
2424 // All transfers are affiliated
2425 if (which_collector == ShenandoahFreeSetPartitionId::OldCollector) {
2426 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollectorEmptiesChanged */ false,
2427 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
2428 /* CollectorSizeChanged */ false, /* OldCollectorSizeChanged */ true,
2429 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ true,
2430 /* UnaffiliatedChangesAreYoungNeutral */ true>();
2431 } else {
2432 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollecteorEmptiesChanged */true,
2433 /* OldCollectorEmptiesChanged */ false, /* MutatorSizeChanged */ true,
2434 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ false,
2435 /* AffiliatedChangesAreYoungNeutral */ true, /* AffiliatedChangesAreGlobalNeutral */ true,
2436 /* UnaffiliatedChangesAreYoungNeutral */ true>();
2437 }
2438 _partitions.assert_bounds();
2439 return transferred_regions;
2440 }
2441
2442 void ShenandoahFreeSet::move_regions_from_collector_to_mutator(size_t max_xfer_regions) {
2443 size_t collector_xfer = 0;
2444 size_t old_collector_xfer = 0;
2445
2446 // Process empty regions within the Collector free partition
2447 if ((max_xfer_regions > 0) &&
2448 (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Collector)
2449 <= _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Collector))) {
2450 ShenandoahHeapLocker locker(_heap->lock());
2451 max_xfer_regions -=
2452 transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId::Collector, max_xfer_regions,
2453 collector_xfer);
2454 }
2455
2456 // Process empty regions within the OldCollector free partition
2457 if ((max_xfer_regions > 0) &&
2458 (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::OldCollector)
2459 <= _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::OldCollector))) {
2460 ShenandoahHeapLocker locker(_heap->lock());
2461 size_t old_collector_regions =
2462 transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId::OldCollector, max_xfer_regions,
2463 old_collector_xfer);
2464 max_xfer_regions -= old_collector_regions;
2465 }
2466
2467 // If there are any non-empty regions within Collector partition, we can also move them to the Mutator free partition
2468 if ((max_xfer_regions > 0) && (_partitions.leftmost(ShenandoahFreeSetPartitionId::Collector)
2469 <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector))) {
2470 ShenandoahHeapLocker locker(_heap->lock());
2471 max_xfer_regions -=
2472 transfer_non_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId::Collector, max_xfer_regions,
2473 collector_xfer);
2474 }
2475
2476 size_t total_xfer = collector_xfer + old_collector_xfer;
2477 log_info(gc, ergo)("At start of update refs, moving %zu%s to Mutator free set from Collector Reserve ("
2478 "%zu%s) and from Old Collector Reserve (%zu%s)",
2479 byte_size_in_proper_unit(total_xfer), proper_unit_for_byte_size(total_xfer),
2480 byte_size_in_proper_unit(collector_xfer), proper_unit_for_byte_size(collector_xfer),
2481 byte_size_in_proper_unit(old_collector_xfer), proper_unit_for_byte_size(old_collector_xfer));
2482 }
2483
2484 // Overwrite arguments to represent the amount of memory in each generation that is about to be recycled
2485 void ShenandoahFreeSet::prepare_to_rebuild(size_t &young_trashed_regions, size_t &old_trashed_regions,
2486 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count) {
2487 shenandoah_assert_heaplocked();
2488 assert(rebuild_lock() != nullptr, "sanity");
2489 rebuild_lock()->lock(false);
2490 // This resets all state information, removing all regions from all sets.
2491 clear();
2492 log_debug(gc, free)("Rebuilding FreeSet");
2493
2494 // Place regions that have alloc_capacity into the old_collector set if they identify as is_old() or the
2495 // mutator set otherwise. All trashed (cset) regions are affiliated young and placed in mutator set. Save the
2496 // allocatable words in mutator partition in state variable.
2497 _prepare_to_rebuild_mutator_free = find_regions_with_alloc_capacity(young_trashed_regions, old_trashed_regions,
2498 first_old_region, last_old_region, old_region_count);
2499 }
2500
2501 // Return mutator free
2502 void ShenandoahFreeSet::finish_rebuild(size_t young_trashed_regions, size_t old_trashed_regions, size_t old_region_count) {
2503 shenandoah_assert_heaplocked();
2504 size_t young_reserve(0), old_reserve(0);
2505
2506 if (_heap->mode()->is_generational()) {
2507 compute_young_and_old_reserves(young_trashed_regions, old_trashed_regions, young_reserve, old_reserve);
2508 } else {
2509 young_reserve = (_heap->max_capacity() / 100) * ShenandoahEvacReserve;
2510 old_reserve = 0;
2511 }
2512
2513 // Move some of the mutator regions into the Collector and OldCollector partitions in order to satisfy
2514 // young_reserve and old_reserve.
2515 size_t young_used_regions, old_used_regions, young_used_bytes, old_used_bytes;
2516 reserve_regions(young_reserve, old_reserve, old_region_count, young_used_regions, old_used_regions,
2517 young_used_bytes, old_used_bytes);
2518 _total_young_regions = _heap->num_regions() - old_region_count;
2519 _total_global_regions = _heap->num_regions();
2520 establish_old_collector_alloc_bias();
2521
2522 // Release the rebuild lock now. What remains in this function is read-only
2523 rebuild_lock()->unlock();
2524 _partitions.assert_bounds();
2525 log_status();
2526 if (_heap->mode()->is_generational()) {
2527 // Clear the region balance until it is adjusted in preparation for a subsequent GC cycle.
2528 _heap->old_generation()->set_region_balance(0);
2529 }
2530 }
2531
2532
2533 // Reduce old reserve (when there are insufficient resources to satisfy the original request).
2534 void ShenandoahFreeSet::reduce_old_reserve(size_t adjusted_old_reserve, size_t requested_old_reserve) {
2535 ShenandoahOldGeneration* const old_generation = _heap->old_generation();
2536 size_t requested_promoted_reserve = old_generation->get_promoted_reserve();
2537 size_t requested_old_evac_reserve = old_generation->get_evacuation_reserve();
2538 assert(adjusted_old_reserve < requested_old_reserve, "Only allow reduction");
2539 assert(requested_promoted_reserve + requested_old_evac_reserve >= adjusted_old_reserve, "Sanity");
2540 size_t delta = requested_old_reserve - adjusted_old_reserve;
2541
2542 if (requested_promoted_reserve >= delta) {
2543 requested_promoted_reserve -= delta;
2544 old_generation->set_promoted_reserve(requested_promoted_reserve);
2545 } else {
2546 delta -= requested_promoted_reserve;
2547 requested_promoted_reserve = 0;
2548 requested_old_evac_reserve -= delta;
2549 old_generation->set_promoted_reserve(requested_promoted_reserve);
2550 old_generation->set_evacuation_reserve(requested_old_evac_reserve);
2551 }
2552 }
2553
2554 // Reduce young reserve (when there are insufficient resources to satisfy the original request).
2555 void ShenandoahFreeSet::reduce_young_reserve(size_t adjusted_young_reserve, size_t requested_young_reserve) {
2556 ShenandoahYoungGeneration* const young_generation = _heap->young_generation();
2557 assert(adjusted_young_reserve < requested_young_reserve, "Only allow reduction");
2558 young_generation->set_evacuation_reserve(adjusted_young_reserve);
2559 }
2560
2561 /**
2562 * Set young_reserve_result and old_reserve_result to the number of bytes that we desire to set aside to hold the
2563 * results of evacuation to young and old collector spaces respectively during the next evacuation phase. Overwrite
2564 * old_generation region balance in case the original value is incompatible with the current reality.
2565 *
2566 * These values are determined by how much memory is currently available within each generation, which is
2567 * represented by:
2568 * 1. Memory currently available within old and young
2569 * 2. Trashed regions currently residing in young and old, which will become available momentarily
2570 * 3. The value of old_generation->get_region_balance() which represents the number of regions that we plan
2571 * to transfer from old generation to young generation. At the end of each GC cycle, we reset region_balance
2572 * to zero. As we prepare to rebuild free set at the end of update-refs, we call
2573 * ShenandoahGenerationalHeap::compute_old_generation_balance() to compute a new value of region_balance.
2574 * This allows us to expand or shrink the size of the Old Collector reserves based on anticipated needs of
2575 * the next GC cycle.
2576 */
2577 void ShenandoahFreeSet::compute_young_and_old_reserves(size_t young_trashed_regions, size_t old_trashed_regions,
2578 size_t& young_reserve_result, size_t& old_reserve_result) const {
2579 shenandoah_assert_generational();
2580 shenandoah_assert_heaplocked();
2581 const size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
2582 ShenandoahOldGeneration* const old_generation = _heap->old_generation();
2583 size_t old_available = old_generation->available();
2584 size_t old_unaffiliated_regions = old_generation->free_unaffiliated_regions();
2585 ShenandoahYoungGeneration* const young_generation = _heap->young_generation();
2586 size_t young_capacity = young_generation->max_capacity();
2587 size_t young_unaffiliated_regions = young_generation->free_unaffiliated_regions();
2588
2589 // Add in the regions we anticipate to be freed by evacuation of the collection set
2590 old_unaffiliated_regions += old_trashed_regions;
2591 old_available += old_trashed_regions * region_size_bytes;
2592 young_unaffiliated_regions += young_trashed_regions;
2593
2594 assert(young_capacity >= young_generation->used(),
2595 "Young capacity (%zu) must exceed used (%zu)", young_capacity, young_generation->used());
2596
2597 size_t young_available = young_capacity - young_generation->used();
2598 young_available += young_trashed_regions * region_size_bytes;
2599
2600 assert(young_available >= young_unaffiliated_regions * region_size_bytes, "sanity");
2601 assert(old_available >= old_unaffiliated_regions * region_size_bytes, "sanity");
2602
2603 // Consult old-region balance to make adjustments to current generation capacities and availability.
2604 // The generation region transfers take place after we rebuild. old_region_balance represents number of regions
2605 // to transfer from old to young.
2606 ssize_t old_region_balance = old_generation->get_region_balance();
2607 if (old_region_balance != 0) {
2608 #ifdef ASSERT
2609 if (old_region_balance > 0) {
2610 assert(old_region_balance <= checked_cast<ssize_t>(old_unaffiliated_regions),
2611 "Cannot transfer %zd regions that are affiliated (old_trashed: %zu, old_unaffiliated: %zu)",
2612 old_region_balance, old_trashed_regions, old_unaffiliated_regions);
2613 } else {
2614 assert(0 - old_region_balance <= checked_cast<ssize_t>(young_unaffiliated_regions),
2615 "Cannot transfer regions that are affiliated");
2616 }
2617 #endif
2618
2619 ssize_t xfer_bytes = old_region_balance * checked_cast<ssize_t>(region_size_bytes);
2620 old_available -= xfer_bytes;
2621 old_unaffiliated_regions -= old_region_balance;
2622 young_available += xfer_bytes;
2623 young_capacity += xfer_bytes;
2624 young_unaffiliated_regions += old_region_balance;
2625 }
2626
2627 // All allocations taken from the old collector set are performed by GC, generally using PLABs for both
2628 // promotions and evacuations. The partition between which old memory is reserved for evacuation and
2629 // which is reserved for promotion is enforced using thread-local variables that prescribe intentions for
2630 // each PLAB's available memory.
2631 const size_t promoted_reserve = old_generation->get_promoted_reserve();
2632 const size_t old_evac_reserve = old_generation->get_evacuation_reserve();
2633 young_reserve_result = young_generation->get_evacuation_reserve();
2634 old_reserve_result = promoted_reserve + old_evac_reserve;
2635 assert(old_reserve_result + young_reserve_result <= old_available + young_available,
2636 "Cannot reserve (%zu + %zu + %zu) more than is available: %zu + %zu",
2637 promoted_reserve, old_evac_reserve, young_reserve_result, old_available, young_available);
2638
2639 // Old available regions that have less than PLAB::min_size() of available memory are not placed into the OldCollector
2640 // free set. Because of this, old_available may not have enough memory to represent the intended reserve. Adjust
2641 // the reserve downward to account for this possibility. This loss is part of the reason why the original budget
2642 // was adjusted with ShenandoahOldEvacWaste and ShenandoahOldPromoWaste multipliers.
2643 if (old_reserve_result >
2644 _partitions.available_in(ShenandoahFreeSetPartitionId::OldCollector) + old_unaffiliated_regions * region_size_bytes) {
2645 old_reserve_result =
2646 _partitions.available_in(ShenandoahFreeSetPartitionId::OldCollector) + old_unaffiliated_regions * region_size_bytes;
2647 }
2648
2649 if (young_reserve_result > young_unaffiliated_regions * region_size_bytes) {
2650 young_reserve_result = young_unaffiliated_regions * region_size_bytes;
2651 }
2652 }
2653
2654 // Having placed all regions that have allocation capacity into the mutator set if they identify as is_young()
2655 // or into the old collector set if they identify as is_old(), move some of these regions from the mutator set
2656 // into the collector set or old collector set in order to assure that the memory available for allocations within
2657 // the collector set is at least to_reserve and the memory available for allocations within the old collector set
2658 // is at least to_reserve_old.
2659 //
2660 // Returns total mutator alloc capacity, in words.
2661 size_t ShenandoahFreeSet::reserve_regions(size_t to_reserve, size_t to_reserve_old, size_t &old_region_count,
2662 size_t &young_used_regions, size_t &old_used_regions,
2663 size_t &young_used_bytes, size_t &old_used_bytes) {
2664 const size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
2665 size_t mutator_allocatable_words = _prepare_to_rebuild_mutator_free;
2666
2667 young_used_regions = 0;
2668 old_used_regions = 0;
2669 young_used_bytes = 0;
2670 old_used_bytes = 0;
2671
2672 idx_t mutator_low_idx = _partitions.max();
2673 idx_t mutator_high_idx = -1;
2674 idx_t mutator_empty_low_idx = _partitions.max();
2675 idx_t mutator_empty_high_idx = -1;
2676
2677 idx_t collector_low_idx = _partitions.max();
2678 idx_t collector_high_idx = -1;
2679 idx_t collector_empty_low_idx = _partitions.max();
2680 idx_t collector_empty_high_idx = -1;
2681
2682 idx_t old_collector_low_idx = _partitions.max();
2683 idx_t old_collector_high_idx = -1;
2684 idx_t old_collector_empty_low_idx = _partitions.max();
2685 idx_t old_collector_empty_high_idx = -1;
2686
2687 size_t used_to_collector = 0;
2688 size_t used_to_old_collector = 0;
2689 size_t regions_to_collector = 0;
2690 size_t regions_to_old_collector = 0;
2691 size_t empty_regions_to_collector = 0;
2692 size_t empty_regions_to_old_collector = 0;
2693
2694 size_t old_collector_available = _partitions.available_in(ShenandoahFreeSetPartitionId::OldCollector);
2695 size_t collector_available = _partitions.available_in(ShenandoahFreeSetPartitionId::Collector);
2696
2697 for (size_t i = _heap->num_regions(); i > 0; i--) {
2698 idx_t idx = i - 1;
2699 ShenandoahHeapRegion* r = _heap->get_region(idx);
2700 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx)) {
2701 // Note: trashed regions have region_size_bytes alloc capacity.
2702 size_t ac = alloc_capacity(r);
2703 assert (ac > 0, "Membership in free set implies has capacity");
2704 assert (!r->is_old() || r->is_trash(), "Except for trash, mutator_is_free regions should not be affiliated OLD");
2705
2706 bool move_to_old_collector = old_collector_available < to_reserve_old;
2707 bool move_to_collector = collector_available < to_reserve;
2708
2709 if (move_to_old_collector) {
2710 // We give priority to OldCollector partition because we desire to pack OldCollector regions into higher
2711 // addresses than Collector regions. Presumably, OldCollector regions are more "stable" and less likely to
2712 // be collected in the near future.
2713 if (r->is_trash() || !r->is_affiliated()) {
2714 // OLD regions that have available memory are already in the old_collector free set.
2715 assert(r->is_empty_or_trash(), "Not affiliated implies region %zu is empty", r->index());
2716 if (idx < old_collector_low_idx) {
2717 old_collector_low_idx = idx;
2718 }
2719 if (idx > old_collector_high_idx) {
2720 old_collector_high_idx = idx;
2721 }
2722 if (idx < old_collector_empty_low_idx) {
2723 old_collector_empty_low_idx = idx;
2724 }
2725 if (idx > old_collector_empty_high_idx) {
2726 old_collector_empty_high_idx = idx;
2727 }
2728 used_to_old_collector +=
2729 _partitions.move_from_partition_to_partition_with_deferred_accounting(idx, ShenandoahFreeSetPartitionId::Mutator,
2730 ShenandoahFreeSetPartitionId::OldCollector, ac);
2731 old_collector_available += ac;
2732 regions_to_old_collector++;
2733 empty_regions_to_old_collector++;
2734
2735 log_trace(gc, free)(" Shifting region %zu from mutator_free to old_collector_free", idx);
2736 log_trace(gc, free)(" Shifted Mutator range [%zd, %zd],"
2737 " Old Collector range [%zd, %zd]",
2738 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
2739 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
2740 _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector),
2741 _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector));
2742 old_region_count++;
2743 assert(ac == ShenandoahHeapRegion::region_size_bytes(), "Cannot move to old unless entire region is in alloc capacity");
2744 mutator_allocatable_words -= ShenandoahHeapRegion::region_size_words();
2745 continue;
2746 }
2747 }
2748
2749 if (move_to_collector) {
2750 // Note: In a previous implementation, regions were only placed into the survivor space (collector_is_free) if
2751 // they were entirely empty. This has the effect of causing new Mutator allocation to reside next to objects
2752 // that have already survived at least one GC, mixing ephemeral with longer-lived objects in the same region.
2753 // Any objects that have survived a GC are less likely to immediately become garbage, so a region that contains
2754 // survivor objects is less likely to be selected for the collection set. This alternative implementation allows
2755 // survivor regions to continue accumulating other survivor objects, and makes it more likely that ephemeral objects
2756 // occupy regions comprised entirely of ephemeral objects. These regions are highly likely to be included in the next
2757 // collection set, and they are easily evacuated because they have low density of live objects.
2758 if (idx < collector_low_idx) {
2759 collector_low_idx = idx;
2760 }
2761 if (idx > collector_high_idx) {
2762 collector_high_idx = idx;
2763 }
2764 if (ac == region_size_bytes) {
2765 if (idx < collector_empty_low_idx) {
2766 collector_empty_low_idx = idx;
2767 }
2768 if (idx > collector_empty_high_idx) {
2769 collector_empty_high_idx = idx;
2770 }
2771 empty_regions_to_collector++;
2772 }
2773 used_to_collector +=
2774 _partitions.move_from_partition_to_partition_with_deferred_accounting(idx, ShenandoahFreeSetPartitionId::Mutator,
2775 ShenandoahFreeSetPartitionId::Collector, ac);
2776 collector_available += ac;
2777 regions_to_collector++;
2778 if (ac != region_size_bytes) {
2779 young_used_regions++;
2780 young_used_bytes = region_size_bytes - ac;
2781 }
2782
2783 log_trace(gc, free)(" Shifting region %zu from mutator_free to collector_free", idx);
2784 log_trace(gc, free)(" Shifted Mutator range [%zd, %zd],"
2785 " Collector range [%zd, %zd]",
2786 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
2787 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
2788 _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector),
2789 _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector));
2790
2791 mutator_allocatable_words -= ac / HeapWordSize;
2792 continue;
2793 }
2794
2795 // Mutator region is not moved to Collector or OldCollector. Still, do the accounting.
2796 if (idx < mutator_low_idx) {
2797 mutator_low_idx = idx;
2798 }
2799 if (idx > mutator_high_idx) {
2800 mutator_high_idx = idx;
2801 }
2802 if ((ac == region_size_bytes) && (idx < mutator_empty_low_idx)) {
2803 mutator_empty_low_idx = idx;
2804 }
2805 if ((ac == region_size_bytes) && (idx > mutator_empty_high_idx)) {
2806 mutator_empty_high_idx = idx;
2807 }
2808 if (ac != region_size_bytes) {
2809 young_used_regions++;
2810 young_used_bytes += region_size_bytes - ac;
2811 }
2812 } else {
2813 // Region is not in Mutator partition. Do the accounting.
2814 ShenandoahFreeSetPartitionId p = _partitions.membership(idx);
2815 size_t ac = alloc_capacity(r);
2816 assert(ac != region_size_bytes, "Empty regions should be in Mutator partion at entry to reserve_regions");
2817 assert(p != ShenandoahFreeSetPartitionId::Collector, "Collector regions must be converted from Mutator regions");
2818 if (p == ShenandoahFreeSetPartitionId::OldCollector) {
2819 assert(!r->is_empty(), "Empty regions should be in Mutator partition at entry to reserve_regions");
2820 old_used_regions++;
2821 old_used_bytes = region_size_bytes - ac;
2822 // This region is within the range for OldCollector partition, as established by find_regions_with_alloc_capacity()
2823 assert((_partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector) <= idx) &&
2824 (_partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector) >= idx),
2825 "find_regions_with_alloc_capacity() should have established this is in range");
2826 } else {
2827 assert(p == ShenandoahFreeSetPartitionId::NotFree, "sanity");
2828 // This region has been retired
2829 if (r->is_old()) {
2830 old_used_regions++;
2831 old_used_bytes += region_size_bytes - ac;
2832 } else {
2833 assert(r->is_young(), "Retired region should be old or young");
2834 young_used_regions++;
2835 young_used_bytes += region_size_bytes - ac;
2836 }
2837 }
2838 }
2839 }
2840
2841 _partitions.decrease_used(ShenandoahFreeSetPartitionId::Mutator, used_to_old_collector + used_to_collector);
2842 _partitions.decrease_region_counts(ShenandoahFreeSetPartitionId::Mutator, regions_to_old_collector + regions_to_collector);
2843 _partitions.decrease_empty_region_counts(ShenandoahFreeSetPartitionId::Mutator,
2844 empty_regions_to_old_collector + empty_regions_to_collector);
2845 // decrease_capacity() also decreases available
2846 _partitions.decrease_capacity(ShenandoahFreeSetPartitionId::Mutator,
2847 (regions_to_old_collector + regions_to_collector) * region_size_bytes);
2848 // increase_capacity() also increases available
2849 _partitions.increase_capacity(ShenandoahFreeSetPartitionId::Collector, regions_to_collector * region_size_bytes);
2850 _partitions.increase_region_counts(ShenandoahFreeSetPartitionId::Collector, regions_to_collector);
2851 _partitions.increase_empty_region_counts(ShenandoahFreeSetPartitionId::Collector, empty_regions_to_collector);
2852 // increase_capacity() also increases available
2853 _partitions.increase_capacity(ShenandoahFreeSetPartitionId::OldCollector, regions_to_old_collector * region_size_bytes);
2854 _partitions.increase_region_counts(ShenandoahFreeSetPartitionId::OldCollector, regions_to_old_collector);
2855 _partitions.increase_empty_region_counts(ShenandoahFreeSetPartitionId::OldCollector, empty_regions_to_old_collector);
2856
2857 if (used_to_collector > 0) {
2858 _partitions.increase_used(ShenandoahFreeSetPartitionId::Collector, used_to_collector);
2859 }
2860
2861 if (used_to_old_collector > 0) {
2862 _partitions.increase_used(ShenandoahFreeSetPartitionId::OldCollector, used_to_old_collector);
2863 }
2864
2865 _partitions.establish_interval(ShenandoahFreeSetPartitionId::Mutator,
2866 mutator_low_idx, mutator_high_idx, mutator_empty_low_idx, mutator_empty_high_idx);
2867 _partitions.establish_interval(ShenandoahFreeSetPartitionId::Collector,
2868 collector_low_idx, collector_high_idx, collector_empty_low_idx, collector_empty_high_idx);
2869
2870 _partitions.expand_interval_if_range_modifies_either_boundary(ShenandoahFreeSetPartitionId::OldCollector,
2871 old_collector_low_idx, old_collector_high_idx,
2872 old_collector_empty_low_idx, old_collector_empty_high_idx);
2873
2874 recompute_total_used</* UsedByMutatorChanged */ true,
2875 /* UsedByCollectorChanged */ true, /* UsedByOldCollectorChanged */ true>();
2876 recompute_total_affiliated</* MutatorEmptiesChanged */ true, /* CollecteorEmptiesChanged */true,
2877 /* OldCollectorEmptiesChanged */ true, /* MutatorSizeChanged */ true,
2878 /* CollectorSizeChanged */ true, /* OldCollectorSizeChanged */ true,
2879 /* AffiliatedChangesAreYoungNeutral */ false, /* AffiliatedChangesAreGlobalNeutral */ false,
2880 /* UnaffiliatedChangesAreYoungNeutral */ false>();
2881 _partitions.assert_bounds();
2882 if (LogTarget(Info, gc, free)::is_enabled()) {
2883 size_t old_reserve = _partitions.available_in(ShenandoahFreeSetPartitionId::OldCollector);
2884 if (old_reserve < to_reserve_old) {
2885 log_info(gc, free)("Wanted " PROPERFMT " for old reserve, but only reserved: " PROPERFMT,
2886 PROPERFMTARGS(to_reserve_old), PROPERFMTARGS(old_reserve));
2887 assert(_heap->mode()->is_generational(), "to_old_reserve > 0 implies generational mode");
2888 reduce_old_reserve(old_reserve, to_reserve_old);
2889 }
2890 size_t reserve = _partitions.available_in(ShenandoahFreeSetPartitionId::Collector);
2891 if (reserve < to_reserve) {
2892 if (_heap->mode()->is_generational()) {
2893 reduce_young_reserve(reserve, to_reserve);
2894 }
2895 log_info(gc, free)("Wanted " PROPERFMT " for young reserve, but only reserved: " PROPERFMT,
2896 PROPERFMTARGS(to_reserve), PROPERFMTARGS(reserve));
2897 }
2898 }
2899 return mutator_allocatable_words;
2900 }
2901
2902 void ShenandoahFreeSet::establish_old_collector_alloc_bias() {
2903 ShenandoahHeap* heap = ShenandoahHeap::heap();
2904 shenandoah_assert_heaplocked();
2905
2906 idx_t left_idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector);
2907 idx_t right_idx = _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector);
2908 idx_t middle = (left_idx + right_idx) / 2;
2909 size_t available_in_first_half = 0;
2910 size_t available_in_second_half = 0;
2911
2912 for (idx_t index = left_idx; index < middle; index++) {
2913 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, index)) {
2914 ShenandoahHeapRegion* r = heap->get_region((size_t) index);
2915 available_in_first_half += r->free();
2916 }
2917 }
2918 for (idx_t index = middle; index <= right_idx; index++) {
2919 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, index)) {
2920 ShenandoahHeapRegion* r = heap->get_region(index);
2921 available_in_second_half += r->free();
2922 }
2923 }
2924
2925 // We desire to first consume the sparsely distributed regions in order that the remaining regions are densely packed.
2926 // Densely packing regions reduces the effort to search for a region that has sufficient memory to satisfy a new allocation
2927 // request. Regions become sparsely distributed following a Full GC, which tends to slide all regions to the front of the
2928 // heap rather than allowing survivor regions to remain at the high end of the heap where we intend for them to congregate.
2929 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::OldCollector,
2930 (available_in_second_half > available_in_first_half));
2931 }
2932
2933 void ShenandoahFreeSet::log_status_under_lock() {
2934 // Must not be heap locked, it acquires heap lock only when log is enabled
2935 shenandoah_assert_not_heaplocked();
2936 if (LogTarget(Info, gc, free)::is_enabled()
2937 DEBUG_ONLY(|| LogTarget(Debug, gc, free)::is_enabled())) {
2938 ShenandoahHeapLocker locker(_heap->lock());
2939 log_status();
2940 }
2941 }
2942
2943 void ShenandoahFreeSet::log_freeset_stats(ShenandoahFreeSetPartitionId partition_id, LogStream& ls) {
2944 size_t max_free_in_single_region = 0;
2945 size_t freeset_free = 0;
2946 size_t freeset_total_used = 0;
2947
2948 for (idx_t idx = _partitions.leftmost(partition_id);
2949 idx <= _partitions.rightmost(partition_id); idx++) {
2950 if (_partitions.in_free_set(partition_id, idx)) {
2951 ShenandoahHeapRegion *r = _heap->get_region(idx);
2952 size_t free = alloc_capacity(r);
2953 max_free_in_single_region = MAX2(max_free_in_single_region, free);
2954 freeset_free += free;
2955 freeset_total_used += ShenandoahHeapRegion::region_size_bytes() - free;
2956 }
2957 }
2958
2959 ls.print_cr(" %s partition stats: regions in capacity: %zu, regions in freeset: %zu. "
2960 "Used size including retired regions: " PROPERFMT ", used size in freeset: " PROPERFMT
2961 ". Free available size: " PROPERFMT ". Max free available in a single region: " PROPERFMT ".",
2962 partition_name(partition_id), _partitions.get_capacity_region_count(partition_id), _partitions.count(partition_id),
2963 PROPERFMTARGS(_partitions.get_used(partition_id)), PROPERFMTARGS(freeset_total_used),
2964 PROPERFMTARGS(freeset_free), PROPERFMTARGS(max_free_in_single_region)
2965 );
2966 }
2967
2968 void ShenandoahFreeSet::log_status() {
2969 shenandoah_assert_heaplocked();
2970
2971 #ifdef ASSERT
2972 // Dump of the FreeSet details is only enabled if assertions are enabled
2973 LogTarget(Debug, gc, free) debug_free;
2974 if (debug_free.is_enabled()) {
2975 #define BUFFER_SIZE 80
2976 LogStream ls(debug_free);
2977
2978 char buffer[BUFFER_SIZE];
2979 for (uint i = 0; i < BUFFER_SIZE; i++) {
2980 buffer[i] = '\0';
2981 }
2982
2983
2984 ls.cr();
2985 ls.print_cr("Mutator free range [%zd..%zd] allocating from %s",
2986 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
2987 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
2988 _partitions.alloc_from_left_bias(ShenandoahFreeSetPartitionId::Mutator)? "left to right": "right to left");
2989
2990 ls.print_cr("Collector free range [%zd..%zd] allocating from %s",
2991 _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector),
2992 _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector),
2993 _partitions.alloc_from_left_bias(ShenandoahFreeSetPartitionId::Collector)? "left to right": "right to left");
2994
2995 ls.print_cr("Old collector free range [%zd..%zd] allocates from %s",
2996 _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector),
2997 _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector),
2998 _partitions.alloc_from_left_bias(ShenandoahFreeSetPartitionId::OldCollector)? "left to right": "right to left");
2999 ls.cr();
3000 ls.print_cr("FreeSet map legend:");
3001 ls.print_cr(" M/m:mutator, C/c:collector O/o:old_collector (Empty/Occupied)");
3002 ls.print_cr(" H/h:humongous, X/x:no alloc capacity, ~/_:retired (Old/Young)");
3003
3004 for (uint i = 0; i < _heap->num_regions(); i++) {
3005 ShenandoahHeapRegion *r = _heap->get_region(i);
3006 uint idx = i % 64;
3007 if ((i != 0) && (idx == 0)) {
3008 ls.print_cr(" %6u: %s", i-64, buffer);
3009 }
3010 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, i)) {
3011 size_t capacity = alloc_capacity(r);
3012 assert(!r->is_old() || r->is_trash(), "Old regions except trash regions should not be in mutator_free set");
3013 buffer[idx] = (capacity == ShenandoahHeapRegion::region_size_bytes()) ? 'M' : 'm';
3014 } else if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, i)) {
3015 size_t capacity = alloc_capacity(r);
3016 assert(!r->is_old() || r->is_trash(), "Old regions except trash regions should not be in collector_free set");
3017 buffer[idx] = (capacity == ShenandoahHeapRegion::region_size_bytes()) ? 'C' : 'c';
3018 } else if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, i)) {
3019 size_t capacity = alloc_capacity(r);
3020 buffer[idx] = (capacity == ShenandoahHeapRegion::region_size_bytes()) ? 'O' : 'o';
3021 } else if (r->is_humongous()) {
3022 buffer[idx] = (r->is_old() ? 'H' : 'h');
3023 } else if (alloc_capacity(r) == 0) {
3024 buffer[idx] = (r->is_old() ? 'X' : 'x');
3025 } else {
3026 buffer[idx] = (r->is_old() ? '~' : '_');
3027 }
3028 }
3029 uint remnant = _heap->num_regions() % 64;
3030 if (remnant > 0) {
3031 buffer[remnant] = '\0';
3032 } else {
3033 remnant = 64;
3034 }
3035 ls.print_cr(" %6u: %s", (uint) (_heap->num_regions() - remnant), buffer);
3036 }
3037 #endif
3038
3039 LogTarget(Info, gc, free) lt;
3040 if (lt.is_enabled()) {
3041 ResourceMark rm;
3042 LogStream ls(lt);
3043
3044 {
3045 idx_t last_idx = 0;
3046 size_t max_contig = 0;
3047 size_t empty_contig = 0;
3048
3049 size_t total_used_in_freeset = 0;
3050 size_t total_free_ext = 0;
3051
3052 for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator);
3053 idx <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator); idx++) {
3054 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx)) {
3055 ShenandoahHeapRegion *r = _heap->get_region(idx);
3056 size_t free = alloc_capacity(r);
3057 size_t used_in_region = r->used();
3058 if (r->is_empty_or_trash()) {
3059 used_in_region = 0;
3060 total_free_ext += free;
3061 if (last_idx + 1 == idx) {
3062 empty_contig++;
3063 } else {
3064 empty_contig = 1;
3065 }
3066 } else {
3067 empty_contig = 0;
3068 }
3069 total_used_in_freeset += used_in_region;
3070 max_contig = MAX2(max_contig, empty_contig);
3071 last_idx = idx;
3072 }
3073 }
3074
3075 size_t max_humongous = max_contig * ShenandoahHeapRegion::region_size_bytes();
3076
3077 size_t total_free = available_locked() + collector_available_locked();
3078 total_free += old_collector_available_locked();
3079 ls.print("Whole heap stats: Total free: " PROPERFMT ", Total used: " PROPERFMT
3080 ", Max humongous allocatable: " PROPERFMT "; ",
3081 PROPERFMTARGS(total_free), PROPERFMTARGS(global_used()), PROPERFMTARGS(max_humongous));
3082
3083 double frag_ext;
3084 if (total_free_ext > 0) {
3085 frag_ext = 100 - (100.0 * max_humongous / total_free_ext);
3086 } else {
3087 frag_ext = 0;
3088 }
3089 ls.print("External fragmentation: %.2f%%; ", frag_ext);
3090
3091 double mutator_filling_percentage = 0;
3092 size_t mutator_partition = _partitions.count(ShenandoahFreeSetPartitionId::Mutator);
3093 if (mutator_partition > 0) {
3094 mutator_filling_percentage = 100 * (1.0 * total_used_in_freeset / mutator_partition)
3095 / ShenandoahHeapRegion::region_size_bytes();
3096 }
3097 ls.print_cr("Mutator freeset filling percentage: %.2f%%", mutator_filling_percentage);
3098 }
3099
3100 log_freeset_stats(ShenandoahFreeSetPartitionId::Mutator, ls);
3101 log_freeset_stats(ShenandoahFreeSetPartitionId::Collector, ls);
3102 if (_heap->mode()->is_generational()) {
3103 log_freeset_stats(ShenandoahFreeSetPartitionId::OldCollector, ls);
3104 }
3105 }
3106 }
3107
3108 void ShenandoahFreeSet::decrease_humongous_waste_for_regular_bypass(ShenandoahHeapRegion*r, size_t waste) {
3109 shenandoah_assert_heaplocked();
3110 assert(_partitions.membership(r->index()) == ShenandoahFreeSetPartitionId::NotFree, "Humongous regions should be NotFree");
3111 ShenandoahFreeSetPartitionId p =
3112 r->is_old()? ShenandoahFreeSetPartitionId::OldCollector: ShenandoahFreeSetPartitionId::Mutator;
3113 _partitions.decrease_humongous_waste(p, waste);
3114 if (waste >= PLAB::min_size() * HeapWordSize) {
3115 _partitions.decrease_used(p, waste);
3116 _partitions.unretire_to_partition(r, p);
3117 if (r->is_old()) {
3118 recompute_total_used</* UsedByMutatorChanged */ false,
3119 /* UsedByCollectorChanged */ false, /* UsedByOldCollectorChanged */ true>();
3120 } else {
3121 recompute_total_used</* UsedByMutatorChanged */ true,
3122 /* UsedByCollectorChanged */ false, /* UsedByOldCollectorChanged */ false>();
3123 }
3124 }
3125 _total_humongous_waste -= waste;
3126 }
3127
3128
3129 HeapWord* ShenandoahFreeSet::allocate(ShenandoahAllocRequest& req, bool& in_new_region) {
3130 shenandoah_assert_heaplocked();
3131 // A freshly allocated mutator object is not yet hashed and may grow by one word
3132 // when an identity hash-code is injected during a future GC copy. Classify it by
3133 // its potential expanded size so an object that could outgrow a region is placed
3134 // as humongous from the start, rather than allocated as a regular object and then
3135 // needing to become humongous after it grows. Every other request carries an
3136 // already-final size:
3137 // - a GC copy (_alloc_shared_gc*) uses an already-expanded copy_size(),
3138 // - a CDS allocation (_alloc_cds) requests a raw archive range; its objects are
3139 // written at their final, already hash-expanded size (copy_size_cds) and are
3140 // not grown at load time,
3141 // - a LAB buffer (TLAB/GCLAB/PLAB, bounded by max_tlab_size_words()) never grows.
3142 const bool may_expand_for_hash = (req.type() == ShenandoahAllocRequest::_alloc_shared);
3143 if (ShenandoahHeapRegion::requires_humongous(req.size(), may_expand_for_hash)) {
3144 switch (req.type()) {
3145 case ShenandoahAllocRequest::_alloc_shared:
3146 case ShenandoahAllocRequest::_alloc_shared_gc:
3147 in_new_region = true;
3148 return allocate_contiguous(req, /* is_humongous = */ true);
3149 case ShenandoahAllocRequest::_alloc_cds:
3150 in_new_region = true;
3151 return allocate_contiguous(req, /* is_humongous = */ false);
3152 case ShenandoahAllocRequest::_alloc_plab:
3153 case ShenandoahAllocRequest::_alloc_gclab:
3154 case ShenandoahAllocRequest::_alloc_tlab:
3155 in_new_region = false;
3156 assert(false, "Trying to allocate TLAB in humongous region: %zu", req.size());
3157 return nullptr;
3158 default:
3159 ShouldNotReachHere();
3160 return nullptr;
3161 }
3162 } else {
3163 return allocate_single(req, in_new_region);
3164 }
3165 }
3166
3167 void ShenandoahFreeSet::print_on(outputStream* out) const {
3168 out->print_cr("Mutator Free Set: %zu", _partitions.count(ShenandoahFreeSetPartitionId::Mutator));
3169 ShenandoahLeftRightIterator mutator(const_cast<ShenandoahRegionPartitions*>(&_partitions), ShenandoahFreeSetPartitionId::Mutator);
3170 for (idx_t index = mutator.current(); mutator.has_next(); index = mutator.next()) {
3171 _heap->get_region(index)->print_on(out);
3172 }
3173
3174 out->print_cr("Collector Free Set: %zu", _partitions.count(ShenandoahFreeSetPartitionId::Collector));
3175 ShenandoahLeftRightIterator collector(const_cast<ShenandoahRegionPartitions*>(&_partitions), ShenandoahFreeSetPartitionId::Collector);
3176 for (idx_t index = collector.current(); collector.has_next(); index = collector.next()) {
3177 _heap->get_region(index)->print_on(out);
3178 }
3179
3180 if (_heap->mode()->is_generational()) {
3181 out->print_cr("Old Collector Free Set: %zu", _partitions.count(ShenandoahFreeSetPartitionId::OldCollector));
3182 for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector);
3183 index <= _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector); index++) {
3184 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, index)) {
3185 _heap->get_region(index)->print_on(out);
3186 }
3187 }
3188 }
3189 }
3190
3191 double ShenandoahFreeSet::internal_fragmentation() {
3192 double squared = 0;
3193 double linear = 0;
3194
3195 ShenandoahLeftRightIterator iterator(&_partitions, ShenandoahFreeSetPartitionId::Mutator);
3196 for (idx_t index = iterator.current(); iterator.has_next(); index = iterator.next()) {
3197 ShenandoahHeapRegion* r = _heap->get_region(index);
3198 size_t used = r->used();
3199 squared += used * used;
3200 linear += used;
3201 }
3202
3203 if (linear > 0) {
3204 double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear);
3205 return 1 - s;
3206 } else {
3207 return 0;
3208 }
3209 }
3210
3211 double ShenandoahFreeSet::external_fragmentation() {
3212 idx_t last_idx = 0;
3213 size_t max_contig = 0;
3214 size_t empty_contig = 0;
3215 size_t free = 0;
3216
3217 ShenandoahLeftRightIterator iterator(&_partitions, ShenandoahFreeSetPartitionId::Mutator);
3218 for (idx_t index = iterator.current(); iterator.has_next(); index = iterator.next()) {
3219 ShenandoahHeapRegion* r = _heap->get_region(index);
3220 if (r->is_empty()) {
3221 free += ShenandoahHeapRegion::region_size_bytes();
3222 if (last_idx + 1 == index) {
3223 empty_contig++;
3224 } else {
3225 empty_contig = 1;
3226 }
3227 } else {
3228 empty_contig = 0;
3229 }
3230 max_contig = MAX2(max_contig, empty_contig);
3231 last_idx = index;
3232 }
3233
3234 if (free > 0) {
3235 return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free);
3236 } else {
3237 return 0;
3238 }
3239 }
3240