1 /*
2 * Copyright (c) 2016, 2021, Red Hat, Inc. All rights reserved.
3 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26 #include "precompiled.hpp"
27 #include "gc/shared/tlab_globals.hpp"
28 #include "gc/shenandoah/shenandoahAffiliation.hpp"
29 #include "gc/shenandoah/shenandoahBarrierSet.hpp"
30 #include "gc/shenandoah/shenandoahFreeSet.hpp"
31 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
32 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
33 #include "gc/shenandoah/shenandoahMarkingContext.inline.hpp"
34 #include "gc/shenandoah/shenandoahOldGeneration.hpp"
35 #include "gc/shenandoah/shenandoahScanRemembered.inline.hpp"
36 #include "gc/shenandoah/shenandoahYoungGeneration.hpp"
37 #include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
38 #include "gc/shenandoah/shenandoahSimpleBitMap.inline.hpp"
39 #include "logging/logStream.hpp"
40 #include "memory/resourceArea.hpp"
41 #include "runtime/orderAccess.hpp"
42
43 static const char* partition_name(ShenandoahFreeSetPartitionId t) {
44 switch (t) {
45 case ShenandoahFreeSetPartitionId::NotFree: return "NotFree";
46 case ShenandoahFreeSetPartitionId::Mutator: return "Mutator";
47 case ShenandoahFreeSetPartitionId::Collector: return "Collector";
48 case ShenandoahFreeSetPartitionId::OldCollector: return "OldCollector";
49 default:
50 ShouldNotReachHere();
51 return "Unrecognized";
52 }
53 }
54
55 #ifndef PRODUCT
56 void ShenandoahRegionPartitions::dump_bitmap() const {
57 log_debug(gc)("Mutator range [" SSIZE_FORMAT ", " SSIZE_FORMAT "], Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT
58 "], Old Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT "]",
59 _leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)],
60 _rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)],
61 _leftmosts[int(ShenandoahFreeSetPartitionId::Collector)],
62 _rightmosts[int(ShenandoahFreeSetPartitionId::Collector)],
63 _leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)],
64 _rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)]);
65 log_debug(gc)("Empty Mutator range [" SSIZE_FORMAT ", " SSIZE_FORMAT
66 "], Empty Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT
67 "], Empty Old Collecto range [" SSIZE_FORMAT ", " SSIZE_FORMAT "]",
68 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
69 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
70 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
71 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
72 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
73 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)]);
74
75 log_debug(gc)("%6s: %18s %18s %18s %18s", "index", "Mutator Bits", "Collector Bits", "Old Collector Bits", "NotFree Bits");
76 dump_bitmap_range(0, _max-1);
77 }
78
79 void ShenandoahRegionPartitions::dump_bitmap_range(idx_t start_region_idx, idx_t end_region_idx) const {
80 assert((start_region_idx >= 0) && (start_region_idx < (idx_t) _max), "precondition");
81 assert((end_region_idx >= 0) && (end_region_idx < (idx_t) _max), "precondition");
82 idx_t aligned_start = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(start_region_idx);
83 idx_t aligned_end = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(end_region_idx);
84 idx_t alignment = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].alignment();
85 while (aligned_start <= aligned_end) {
86 dump_bitmap_row(aligned_start);
87 aligned_start += alignment;
88 }
89 }
90
91 void ShenandoahRegionPartitions::dump_bitmap_row(idx_t region_idx) const {
92 assert((region_idx >= 0) && (region_idx < (idx_t) _max), "precondition");
93 idx_t aligned_idx = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(region_idx);
94 uintx mutator_bits = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].bits_at(aligned_idx);
95 uintx collector_bits = _membership[int(ShenandoahFreeSetPartitionId::Collector)].bits_at(aligned_idx);
96 uintx old_collector_bits = _membership[int(ShenandoahFreeSetPartitionId::OldCollector)].bits_at(aligned_idx);
97 uintx free_bits = mutator_bits | collector_bits | old_collector_bits;
98 uintx notfree_bits = ~free_bits;
99 log_debug(gc)(SSIZE_FORMAT_W(6) ": " SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0,
100 aligned_idx, mutator_bits, collector_bits, old_collector_bits, notfree_bits);
101 }
102 #endif
103
104 ShenandoahRegionPartitions::ShenandoahRegionPartitions(size_t max_regions, ShenandoahFreeSet* free_set) :
105 _max(max_regions),
106 _region_size_bytes(ShenandoahHeapRegion::region_size_bytes()),
107 _free_set(free_set),
108 _membership{ ShenandoahSimpleBitMap(max_regions), ShenandoahSimpleBitMap(max_regions) , ShenandoahSimpleBitMap(max_regions) }
109 {
110 make_all_regions_unavailable();
111 }
112
113 inline bool ShenandoahFreeSet::can_allocate_from(ShenandoahHeapRegion *r) const {
114 return r->is_empty() || (r->is_trash() && !_heap->is_concurrent_weak_root_in_progress());
115 }
116
117 inline bool ShenandoahFreeSet::can_allocate_from(size_t idx) const {
118 ShenandoahHeapRegion* r = _heap->get_region(idx);
119 return can_allocate_from(r);
120 }
121
122 inline size_t ShenandoahFreeSet::alloc_capacity(ShenandoahHeapRegion *r) const {
123 if (r->is_trash()) {
124 // This would be recycled on allocation path
125 return ShenandoahHeapRegion::region_size_bytes();
126 } else {
127 return r->free();
128 }
129 }
130
131 inline size_t ShenandoahFreeSet::alloc_capacity(size_t idx) const {
132 ShenandoahHeapRegion* r = _heap->get_region(idx);
133 return alloc_capacity(r);
134 }
135
136 inline bool ShenandoahFreeSet::has_alloc_capacity(ShenandoahHeapRegion *r) const {
137 return alloc_capacity(r) > 0;
138 }
139
140 inline idx_t ShenandoahRegionPartitions::leftmost(ShenandoahFreeSetPartitionId which_partition) const {
141 assert (which_partition < NumPartitions, "selected free partition must be valid");
142 idx_t idx = _leftmosts[int(which_partition)];
143 if (idx >= _max) {
144 return _max;
145 } else {
146 // Cannot assert that membership[which_partition.is_set(idx) because this helper method may be used
147 // to query the original value of leftmost when leftmost must be adjusted because the interval representing
148 // which_partition is shrinking after the region that used to be leftmost is retired.
149 return idx;
150 }
151 }
152
153 inline idx_t ShenandoahRegionPartitions::rightmost(ShenandoahFreeSetPartitionId which_partition) const {
154 assert (which_partition < NumPartitions, "selected free partition must be valid");
155 idx_t idx = _rightmosts[int(which_partition)];
156 // Cannot assert that membership[which_partition.is_set(idx) because this helper method may be used
157 // to query the original value of leftmost when leftmost must be adjusted because the interval representing
158 // which_partition is shrinking after the region that used to be leftmost is retired.
159 return idx;
160 }
161
162 void ShenandoahRegionPartitions::make_all_regions_unavailable() {
163 for (size_t partition_id = 0; partition_id < IntNumPartitions; partition_id++) {
164 _membership[partition_id].clear_all();
165 _leftmosts[partition_id] = _max;
166 _rightmosts[partition_id] = -1;
167 _leftmosts_empty[partition_id] = _max;
168 _rightmosts_empty[partition_id] = -1;;
169 _capacity[partition_id] = 0;
170 _used[partition_id] = 0;
171 }
172 _region_counts[int(ShenandoahFreeSetPartitionId::Mutator)] = _region_counts[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
173 }
174
175 void ShenandoahRegionPartitions::establish_mutator_intervals(idx_t mutator_leftmost, idx_t mutator_rightmost,
176 idx_t mutator_leftmost_empty, idx_t mutator_rightmost_empty,
177 size_t mutator_region_count, size_t mutator_used) {
178 _leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_leftmost;
179 _rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_rightmost;
180 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_leftmost_empty;
181 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_rightmost_empty;
182
183 _region_counts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_region_count;
184 _used[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_used;
185 _capacity[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_region_count * _region_size_bytes;
186
187 _leftmosts[int(ShenandoahFreeSetPartitionId::Collector)] = _max;
188 _rightmosts[int(ShenandoahFreeSetPartitionId::Collector)] = -1;
189 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)] = _max;
190 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)] = -1;
191
192 _region_counts[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
193 _used[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
194 _capacity[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
195 }
196
197 void ShenandoahRegionPartitions::establish_old_collector_intervals(idx_t old_collector_leftmost, idx_t old_collector_rightmost,
198 idx_t old_collector_leftmost_empty,
199 idx_t old_collector_rightmost_empty,
200 size_t old_collector_region_count, size_t old_collector_used) {
201 _leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_leftmost;
202 _rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_rightmost;
203 _leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_leftmost_empty;
204 _rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_rightmost_empty;
205
206 _region_counts[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_region_count;
207 _used[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_used;
208 _capacity[int(ShenandoahFreeSetPartitionId::OldCollector)] = old_collector_region_count * _region_size_bytes;
209 }
210
211 void ShenandoahRegionPartitions::increase_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
212 assert (which_partition < NumPartitions, "Partition must be valid");
213 _used[int(which_partition)] += bytes;
214 assert (_used[int(which_partition)] <= _capacity[int(which_partition)],
215 "Must not use (" SIZE_FORMAT ") more than capacity (" SIZE_FORMAT ") after increase by " SIZE_FORMAT,
216 _used[int(which_partition)], _capacity[int(which_partition)], bytes);
217 }
218
219 inline void ShenandoahRegionPartitions::shrink_interval_if_range_modifies_either_boundary(
220 ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx) {
221 assert((low_idx <= high_idx) && (low_idx >= 0) && (high_idx < _max), "Range must span legal index values");
222 if (low_idx == leftmost(partition)) {
223 assert (!_membership[int(partition)].is_set(low_idx), "Do not shrink interval if region not removed");
224 if (high_idx + 1 == _max) {
225 _leftmosts[int(partition)] = _max;
226 } else {
227 _leftmosts[int(partition)] = find_index_of_next_available_region(partition, high_idx + 1);
228 }
229 if (_leftmosts_empty[int(partition)] < _leftmosts[int(partition)]) {
230 // This gets us closer to where we need to be; we'll scan further when leftmosts_empty is requested.
231 _leftmosts_empty[int(partition)] = _leftmosts[int(partition)];
232 }
233 }
234 if (high_idx == _rightmosts[int(partition)]) {
235 assert (!_membership[int(partition)].is_set(high_idx), "Do not shrink interval if region not removed");
236 if (low_idx == 0) {
237 _rightmosts[int(partition)] = -1;
238 } else {
239 _rightmosts[int(partition)] = find_index_of_previous_available_region(partition, low_idx - 1);
240 }
241 if (_rightmosts_empty[int(partition)] > _rightmosts[int(partition)]) {
242 // This gets us closer to where we need to be; we'll scan further when rightmosts_empty is requested.
243 _rightmosts_empty[int(partition)] = _rightmosts[int(partition)];
244 }
245 }
246 if (_leftmosts[int(partition)] > _rightmosts[int(partition)]) {
247 _leftmosts[int(partition)] = _max;
248 _rightmosts[int(partition)] = -1;
249 _leftmosts_empty[int(partition)] = _max;
250 _rightmosts_empty[int(partition)] = -1;
251 }
252 }
253
254 inline void ShenandoahRegionPartitions::shrink_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, idx_t idx) {
255 shrink_interval_if_range_modifies_either_boundary(partition, idx, idx);
256 }
257
258 inline void ShenandoahRegionPartitions::expand_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition,
259 idx_t idx, size_t region_available) {
260 if (_leftmosts[int(partition)] > idx) {
261 _leftmosts[int(partition)] = idx;
262 }
263 if (_rightmosts[int(partition)] < idx) {
264 _rightmosts[int(partition)] = idx;
265 }
266 if (region_available == _region_size_bytes) {
267 if (_leftmosts_empty[int(partition)] > idx) {
268 _leftmosts_empty[int(partition)] = idx;
269 }
270 if (_rightmosts_empty[int(partition)] < idx) {
271 _rightmosts_empty[int(partition)] = idx;
272 }
273 }
274 }
275
276 void ShenandoahRegionPartitions::retire_range_from_partition(
277 ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx) {
278
279 // Note: we may remove from free partition even if region is not entirely full, such as when available < PLAB::min_size()
280 assert ((low_idx < _max) && (high_idx < _max), "Both indices are sane: " SIZE_FORMAT " and " SIZE_FORMAT " < " SIZE_FORMAT,
281 low_idx, high_idx, _max);
282 assert (partition < NumPartitions, "Cannot remove from free partitions if not already free");
283
284 for (idx_t idx = low_idx; idx <= high_idx; idx++) {
285 assert (in_free_set(partition, idx), "Must be in partition to remove from partition");
286 _membership[int(partition)].clear_bit(idx);
287 }
288 _region_counts[int(partition)] -= high_idx + 1 - low_idx;
289 shrink_interval_if_range_modifies_either_boundary(partition, low_idx, high_idx);
290 }
291
292 void ShenandoahRegionPartitions::retire_from_partition(ShenandoahFreeSetPartitionId partition, idx_t idx, size_t used_bytes) {
293
294 // Note: we may remove from free partition even if region is not entirely full, such as when available < PLAB::min_size()
295 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
296 assert (partition < NumPartitions, "Cannot remove from free partitions if not already free");
297 assert (in_free_set(partition, idx), "Must be in partition to remove from partition");
298
299 if (used_bytes < _region_size_bytes) {
300 // Count the alignment pad remnant of memory as used when we retire this region
301 increase_used(partition, _region_size_bytes - used_bytes);
302 }
303 _membership[int(partition)].clear_bit(idx);
304 shrink_interval_if_boundary_modified(partition, idx);
305 _region_counts[int(partition)]--;
306 }
307
308 void ShenandoahRegionPartitions::make_free(idx_t idx, ShenandoahFreeSetPartitionId which_partition, size_t available) {
309 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
310 assert (membership(idx) == ShenandoahFreeSetPartitionId::NotFree, "Cannot make free if already free");
311 assert (which_partition < NumPartitions, "selected free partition must be valid");
312 assert (available <= _region_size_bytes, "Available cannot exceed region size");
313
314 _membership[int(which_partition)].set_bit(idx);
315 _capacity[int(which_partition)] += _region_size_bytes;
316 _used[int(which_partition)] += _region_size_bytes - available;
317 expand_interval_if_boundary_modified(which_partition, idx, available);
318 _region_counts[int(which_partition)]++;
319 }
320
321 bool ShenandoahRegionPartitions::is_mutator_partition(ShenandoahFreeSetPartitionId p) {
322 return (p == ShenandoahFreeSetPartitionId::Mutator);
323 }
324
325 bool ShenandoahRegionPartitions::is_young_collector_partition(ShenandoahFreeSetPartitionId p) {
326 return (p == ShenandoahFreeSetPartitionId::Collector);
327 }
328
329 bool ShenandoahRegionPartitions::is_old_collector_partition(ShenandoahFreeSetPartitionId p) {
330 return (p == ShenandoahFreeSetPartitionId::OldCollector);
331 }
332
333 bool ShenandoahRegionPartitions::available_implies_empty(size_t available_in_region) {
334 return (available_in_region == _region_size_bytes);
335 }
336
337
338 void ShenandoahRegionPartitions::move_from_partition_to_partition(idx_t idx, ShenandoahFreeSetPartitionId orig_partition,
339 ShenandoahFreeSetPartitionId new_partition, size_t available) {
340 ShenandoahHeapRegion* r = ShenandoahHeap::heap()->get_region(idx);
341 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
342 assert (orig_partition < NumPartitions, "Original partition must be valid");
343 assert (new_partition < NumPartitions, "New partition must be valid");
344 assert (available <= _region_size_bytes, "Available cannot exceed region size");
345 assert (_membership[int(orig_partition)].is_set(idx), "Cannot move from partition unless in partition");
346 assert ((r != nullptr) && ((r->is_trash() && (available == _region_size_bytes)) ||
347 (r->used() + available == _region_size_bytes)),
348 "Used: " SIZE_FORMAT " + available: " SIZE_FORMAT " should equal region size: " SIZE_FORMAT,
349 ShenandoahHeap::heap()->get_region(idx)->used(), available, _region_size_bytes);
350
351 // Expected transitions:
352 // During rebuild: Mutator => Collector
353 // Mutator empty => Collector
354 // Mutator empty => OldCollector
355 // During flip_to_gc: Mutator empty => Collector
356 // Mutator empty => OldCollector
357 // At start of update refs: Collector => Mutator
358 // OldCollector Empty => Mutator
359 assert ((is_mutator_partition(orig_partition) && is_young_collector_partition(new_partition)) ||
360 (is_mutator_partition(orig_partition) &&
361 available_implies_empty(available) && is_old_collector_partition(new_partition)) ||
362 (is_young_collector_partition(orig_partition) && is_mutator_partition(new_partition)) ||
363 (is_old_collector_partition(orig_partition)
364 && available_implies_empty(available) && is_mutator_partition(new_partition)),
365 "Unexpected movement between partitions, available: " SIZE_FORMAT ", _region_size_bytes: " SIZE_FORMAT
366 ", orig_partition: %s, new_partition: %s",
367 available, _region_size_bytes, partition_name(orig_partition), partition_name(new_partition));
368
369 size_t used = _region_size_bytes - available;
370 assert (_used[int(orig_partition)] >= used,
371 "Orig partition used: " SIZE_FORMAT " must exceed moved used: " SIZE_FORMAT " within region " SSIZE_FORMAT,
372 _used[int(orig_partition)], used, idx);
373
374 _membership[int(orig_partition)].clear_bit(idx);
375 _membership[int(new_partition)].set_bit(idx);
376
377 _capacity[int(orig_partition)] -= _region_size_bytes;
378 _used[int(orig_partition)] -= used;
379 shrink_interval_if_boundary_modified(orig_partition, idx);
380
381 _capacity[int(new_partition)] += _region_size_bytes;;
382 _used[int(new_partition)] += used;
383 expand_interval_if_boundary_modified(new_partition, idx, available);
384
385 _region_counts[int(orig_partition)]--;
386 _region_counts[int(new_partition)]++;
387 }
388
389 const char* ShenandoahRegionPartitions::partition_membership_name(idx_t idx) const {
390 return partition_name(membership(idx));
391 }
392
393 inline ShenandoahFreeSetPartitionId ShenandoahRegionPartitions::membership(idx_t idx) const {
394 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
395 ShenandoahFreeSetPartitionId result = ShenandoahFreeSetPartitionId::NotFree;
396 for (uint partition_id = 0; partition_id < UIntNumPartitions; partition_id++) {
397 if (_membership[partition_id].is_set(idx)) {
398 assert(result == ShenandoahFreeSetPartitionId::NotFree, "Region should reside in only one partition");
399 result = (ShenandoahFreeSetPartitionId) partition_id;
400 }
401 }
402 return result;
403 }
404
405 #ifdef ASSERT
406 inline bool ShenandoahRegionPartitions::partition_id_matches(idx_t idx, ShenandoahFreeSetPartitionId test_partition) const {
407 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
408 assert (test_partition < ShenandoahFreeSetPartitionId::NotFree, "must be a valid partition");
409
410 return membership(idx) == test_partition;
411 }
412 #endif
413
414 inline bool ShenandoahRegionPartitions::is_empty(ShenandoahFreeSetPartitionId which_partition) const {
415 assert (which_partition < NumPartitions, "selected free partition must be valid");
416 return (leftmost(which_partition) > rightmost(which_partition));
417 }
418
419 inline idx_t ShenandoahRegionPartitions::find_index_of_next_available_region(
420 ShenandoahFreeSetPartitionId which_partition, idx_t start_index) const {
421 idx_t rightmost_idx = rightmost(which_partition);
422 idx_t leftmost_idx = leftmost(which_partition);
423 if ((rightmost_idx < leftmost_idx) || (start_index > rightmost_idx)) return _max;
424 if (start_index < leftmost_idx) {
425 start_index = leftmost_idx;
426 }
427 idx_t result = _membership[int(which_partition)].find_first_set_bit(start_index, rightmost_idx + 1);
428 if (result > rightmost_idx) {
429 result = _max;
430 }
431 assert (result >= start_index, "Requires progress");
432 return result;
433 }
434
435 inline idx_t ShenandoahRegionPartitions::find_index_of_previous_available_region(
436 ShenandoahFreeSetPartitionId which_partition, idx_t last_index) const {
437 idx_t rightmost_idx = rightmost(which_partition);
438 idx_t leftmost_idx = leftmost(which_partition);
439 // if (leftmost_idx == max) then (last_index < leftmost_idx)
440 if (last_index < leftmost_idx) return -1;
441 if (last_index > rightmost_idx) {
442 last_index = rightmost_idx;
443 }
444 idx_t result = _membership[int(which_partition)].find_last_set_bit(-1, last_index);
445 if (result < leftmost_idx) {
446 result = -1;
447 }
448 assert (result <= last_index, "Requires progress");
449 return result;
450 }
451
452 inline idx_t ShenandoahRegionPartitions::find_index_of_next_available_cluster_of_regions(
453 ShenandoahFreeSetPartitionId which_partition, idx_t start_index, size_t cluster_size) const {
454 idx_t rightmost_idx = rightmost(which_partition);
455 idx_t leftmost_idx = leftmost(which_partition);
456 if ((rightmost_idx < leftmost_idx) || (start_index > rightmost_idx)) return _max;
457 idx_t result = _membership[int(which_partition)].find_first_consecutive_set_bits(start_index, rightmost_idx + 1, cluster_size);
458 if (result > rightmost_idx) {
459 result = _max;
460 }
461 assert (result >= start_index, "Requires progress");
462 return result;
463 }
464
465 inline idx_t ShenandoahRegionPartitions::find_index_of_previous_available_cluster_of_regions(
466 ShenandoahFreeSetPartitionId which_partition, idx_t last_index, size_t cluster_size) const {
467 idx_t leftmost_idx = leftmost(which_partition);
468 // if (leftmost_idx == max) then (last_index < leftmost_idx)
469 if (last_index < leftmost_idx) return -1;
470 idx_t result = _membership[int(which_partition)].find_last_consecutive_set_bits(leftmost_idx - 1, last_index, cluster_size);
471 if (result <= leftmost_idx) {
472 result = -1;
473 }
474 assert (result <= last_index, "Requires progress");
475 return result;
476 }
477
478 idx_t ShenandoahRegionPartitions::leftmost_empty(ShenandoahFreeSetPartitionId which_partition) {
479 assert (which_partition < NumPartitions, "selected free partition must be valid");
480 idx_t max_regions = _max;
481 if (_leftmosts_empty[int(which_partition)] == _max) {
482 return _max;
483 }
484 for (idx_t idx = find_index_of_next_available_region(which_partition, _leftmosts_empty[int(which_partition)]);
485 idx < max_regions; ) {
486 assert(in_free_set(which_partition, idx), "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
487 if (_free_set->alloc_capacity(idx) == _region_size_bytes) {
488 _leftmosts_empty[int(which_partition)] = idx;
489 return idx;
490 }
491 idx = find_index_of_next_available_region(which_partition, idx + 1);
492 }
493 _leftmosts_empty[int(which_partition)] = _max;
494 _rightmosts_empty[int(which_partition)] = -1;
495 return _max;
496 }
497
498 idx_t ShenandoahRegionPartitions::rightmost_empty(ShenandoahFreeSetPartitionId which_partition) {
499 assert (which_partition < NumPartitions, "selected free partition must be valid");
500 if (_rightmosts_empty[int(which_partition)] < 0) {
501 return -1;
502 }
503 for (idx_t idx = find_index_of_previous_available_region(which_partition, _rightmosts_empty[int(which_partition)]);
504 idx >= 0; ) {
505 assert(in_free_set(which_partition, idx), "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
506 if (_free_set->alloc_capacity(idx) == _region_size_bytes) {
507 _rightmosts_empty[int(which_partition)] = idx;
508 return idx;
509 }
510 idx = find_index_of_previous_available_region(which_partition, idx - 1);
511 }
512 _leftmosts_empty[int(which_partition)] = _max;
513 _rightmosts_empty[int(which_partition)] = -1;
514 return -1;
515 }
516
517
518 #ifdef ASSERT
519 void ShenandoahRegionPartitions::assert_bounds() {
520
521 idx_t leftmosts[UIntNumPartitions];
522 idx_t rightmosts[UIntNumPartitions];
523 idx_t empty_leftmosts[UIntNumPartitions];
524 idx_t empty_rightmosts[UIntNumPartitions];
525
526 for (uint i = 0; i < UIntNumPartitions; i++) {
527 leftmosts[i] = _max;
528 empty_leftmosts[i] = _max;
529 rightmosts[i] = -1;
530 empty_rightmosts[i] = -1;
531 }
532
533 for (idx_t i = 0; i < _max; i++) {
534 ShenandoahFreeSetPartitionId partition = membership(i);
535 switch (partition) {
536 case ShenandoahFreeSetPartitionId::NotFree:
537 break;
538
539 case ShenandoahFreeSetPartitionId::Mutator:
540 case ShenandoahFreeSetPartitionId::Collector:
541 case ShenandoahFreeSetPartitionId::OldCollector:
542 {
543 size_t capacity = _free_set->alloc_capacity(i);
544 bool is_empty = (capacity == _region_size_bytes);
545 assert(capacity > 0, "free regions must have allocation capacity");
546 if (i < leftmosts[int(partition)]) {
547 leftmosts[int(partition)] = i;
548 }
549 if (is_empty && (i < empty_leftmosts[int(partition)])) {
550 empty_leftmosts[int(partition)] = i;
551 }
552 if (i > rightmosts[int(partition)]) {
553 rightmosts[int(partition)] = i;
554 }
555 if (is_empty && (i > empty_rightmosts[int(partition)])) {
556 empty_rightmosts[int(partition)] = i;
557 }
558 break;
559 }
560
561 default:
562 ShouldNotReachHere();
563 }
564 }
565
566 // Performance invariants. Failing these would not break the free partition, but performance would suffer.
567 assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) <= _max,
568 "leftmost in bounds: " SSIZE_FORMAT " < " SSIZE_FORMAT, leftmost(ShenandoahFreeSetPartitionId::Mutator), _max);
569 assert (rightmost(ShenandoahFreeSetPartitionId::Mutator) < _max,
570 "rightmost in bounds: " SSIZE_FORMAT " < " SSIZE_FORMAT, rightmost(ShenandoahFreeSetPartitionId::Mutator), _max);
571
572 assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) == _max
573 || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::Mutator), ShenandoahFreeSetPartitionId::Mutator),
574 "leftmost region should be free: " SSIZE_FORMAT, leftmost(ShenandoahFreeSetPartitionId::Mutator));
575 assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) == _max
576 || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::Mutator), ShenandoahFreeSetPartitionId::Mutator),
577 "rightmost region should be free: " SSIZE_FORMAT, rightmost(ShenandoahFreeSetPartitionId::Mutator));
578
579 // If Mutator partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
580 // Likewise for empty region partitions.
581 idx_t beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
582 idx_t end_off = rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
583 assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::Mutator),
584 "free regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
585 beg_off, leftmost(ShenandoahFreeSetPartitionId::Mutator));
586 assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::Mutator),
587 "free regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
588 end_off, rightmost(ShenandoahFreeSetPartitionId::Mutator));
589
590 beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
591 end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
592 assert (beg_off >= leftmost_empty(ShenandoahFreeSetPartitionId::Mutator),
593 "free empty regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
594 beg_off, leftmost_empty(ShenandoahFreeSetPartitionId::Mutator));
595 assert (end_off <= rightmost_empty(ShenandoahFreeSetPartitionId::Mutator),
596 "free empty regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
597 end_off, rightmost_empty(ShenandoahFreeSetPartitionId::Mutator));
598
599 // Performance invariants. Failing these would not break the free partition, but performance would suffer.
600 assert (leftmost(ShenandoahFreeSetPartitionId::Collector) <= _max, "leftmost in bounds: " SSIZE_FORMAT " < " SSIZE_FORMAT,
601 leftmost(ShenandoahFreeSetPartitionId::Collector), _max);
602 assert (rightmost(ShenandoahFreeSetPartitionId::Collector) < _max, "rightmost in bounds: " SSIZE_FORMAT " < " SSIZE_FORMAT,
603 rightmost(ShenandoahFreeSetPartitionId::Collector), _max);
604
605 assert (leftmost(ShenandoahFreeSetPartitionId::Collector) == _max
606 || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::Collector), ShenandoahFreeSetPartitionId::Collector),
607 "leftmost region should be free: " SSIZE_FORMAT, leftmost(ShenandoahFreeSetPartitionId::Collector));
608 assert (leftmost(ShenandoahFreeSetPartitionId::Collector) == _max
609 || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::Collector), ShenandoahFreeSetPartitionId::Collector),
610 "rightmost region should be free: " SSIZE_FORMAT, rightmost(ShenandoahFreeSetPartitionId::Collector));
611
612 // If Collector partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
613 // Likewise for empty region partitions.
614 beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::Collector)];
615 end_off = rightmosts[int(ShenandoahFreeSetPartitionId::Collector)];
616 assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::Collector),
617 "free regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
618 beg_off, leftmost(ShenandoahFreeSetPartitionId::Collector));
619 assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::Collector),
620 "free regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
621 end_off, rightmost(ShenandoahFreeSetPartitionId::Collector));
622
623 beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::Collector)];
624 end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::Collector)];
625 assert (beg_off >= _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
626 "free empty regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
627 beg_off, leftmost_empty(ShenandoahFreeSetPartitionId::Collector));
628 assert (end_off <= _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
629 "free empty regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
630 end_off, rightmost_empty(ShenandoahFreeSetPartitionId::Collector));
631
632 // Performance invariants. Failing these would not break the free partition, but performance would suffer.
633 assert (leftmost(ShenandoahFreeSetPartitionId::OldCollector) <= _max, "leftmost in bounds: " SSIZE_FORMAT " < " SSIZE_FORMAT,
634 leftmost(ShenandoahFreeSetPartitionId::OldCollector), _max);
635 assert (rightmost(ShenandoahFreeSetPartitionId::OldCollector) < _max, "rightmost in bounds: " SSIZE_FORMAT " < " SSIZE_FORMAT,
636 rightmost(ShenandoahFreeSetPartitionId::OldCollector), _max);
637
638 assert (leftmost(ShenandoahFreeSetPartitionId::OldCollector) == _max
639 || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::OldCollector),
640 ShenandoahFreeSetPartitionId::OldCollector),
641 "leftmost region should be free: " SSIZE_FORMAT, leftmost(ShenandoahFreeSetPartitionId::OldCollector));
642 assert (leftmost(ShenandoahFreeSetPartitionId::OldCollector) == _max
643 || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::OldCollector),
644 ShenandoahFreeSetPartitionId::OldCollector),
645 "rightmost region should be free: " SSIZE_FORMAT, rightmost(ShenandoahFreeSetPartitionId::OldCollector));
646
647 // If OldCollector partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
648 // Likewise for empty region partitions.
649 beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
650 end_off = rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
651 assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::OldCollector),
652 "free regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
653 beg_off, leftmost(ShenandoahFreeSetPartitionId::OldCollector));
654 assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::OldCollector),
655 "free regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
656 end_off, rightmost(ShenandoahFreeSetPartitionId::OldCollector));
657
658 beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
659 end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::OldCollector)];
660 assert (beg_off >= _leftmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
661 "free empty regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
662 beg_off, leftmost_empty(ShenandoahFreeSetPartitionId::OldCollector));
663 assert (end_off <= _rightmosts_empty[int(ShenandoahFreeSetPartitionId::OldCollector)],
664 "free empty regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
665 end_off, rightmost_empty(ShenandoahFreeSetPartitionId::OldCollector));
666 }
667 #endif
668
669 ShenandoahFreeSet::ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions) :
670 _heap(heap),
671 _partitions(max_regions, this),
672 _trash_regions(NEW_C_HEAP_ARRAY(ShenandoahHeapRegion*, max_regions, mtGC)),
673 _alloc_bias_weight(0)
674 {
675 clear_internal();
676 }
677
678 void ShenandoahFreeSet::add_promoted_in_place_region_to_old_collector(ShenandoahHeapRegion* region) {
679 shenandoah_assert_heaplocked();
680 size_t plab_min_size_in_bytes = ShenandoahGenerationalHeap::heap()->plab_min_size() * HeapWordSize;
681 size_t idx = region->index();
682 size_t capacity = alloc_capacity(region);
683 assert(_partitions.membership(idx) == ShenandoahFreeSetPartitionId::NotFree,
684 "Regions promoted in place should have been excluded from Mutator partition");
685 if (capacity >= plab_min_size_in_bytes) {
686 _partitions.make_free(idx, ShenandoahFreeSetPartitionId::OldCollector, capacity);
687 _heap->old_generation()->augment_promoted_reserve(capacity);
688 }
689 }
690
691 HeapWord* ShenandoahFreeSet::allocate_from_partition_with_affiliation(ShenandoahFreeSetPartitionId which_partition,
692 ShenandoahAffiliation affiliation,
693 ShenandoahAllocRequest& req, bool& in_new_region) {
694 shenandoah_assert_heaplocked();
695 idx_t rightmost_collector = ((affiliation == ShenandoahAffiliation::FREE)?
696 _partitions.rightmost_empty(which_partition): _partitions.rightmost(which_partition));
697 idx_t leftmost_collector = ((affiliation == ShenandoahAffiliation::FREE)?
698 _partitions.leftmost_empty(which_partition): _partitions.leftmost(which_partition));
699 if (_partitions.alloc_from_left_bias(which_partition)) {
700 for (idx_t idx = leftmost_collector; idx <= rightmost_collector; ) {
701 assert(_partitions.in_free_set(which_partition, idx), "Boundaries or find_prev_last_bit failed: " SSIZE_FORMAT, idx);
702 ShenandoahHeapRegion* r = _heap->get_region(idx);
703 if (r->affiliation() == affiliation) {
704 HeapWord* result = try_allocate_in(r, req, in_new_region);
705 if (result != nullptr) {
706 return result;
707 }
708 }
709 idx = _partitions.find_index_of_next_available_region(which_partition, idx + 1);
710 }
711 } else {
712 for (idx_t idx = rightmost_collector; idx >= leftmost_collector; ) {
713 assert(_partitions.in_free_set(which_partition, idx),
714 "Boundaries or find_prev_last_bit failed: " SSIZE_FORMAT, idx);
715 ShenandoahHeapRegion* r = _heap->get_region(idx);
716 if (r->affiliation() == affiliation) {
717 HeapWord* result = try_allocate_in(r, req, in_new_region);
718 if (result != nullptr) {
719 return result;
720 }
721 }
722 idx = _partitions.find_index_of_previous_available_region(which_partition, idx - 1);
723 }
724 }
725 log_debug(gc, free)("Could not allocate collector region with affiliation: %s for request " PTR_FORMAT,
726 shenandoah_affiliation_name(affiliation), p2i(&req));
727 return nullptr;
728 }
729
730 HeapWord* ShenandoahFreeSet::allocate_single(ShenandoahAllocRequest& req, bool& in_new_region) {
731 shenandoah_assert_heaplocked();
732
733 // Scan the bitmap looking for a first fit.
734 //
735 // Leftmost and rightmost bounds provide enough caching to walk bitmap efficiently. Normally,
736 // we would find the region to allocate at right away.
737 //
738 // Allocations are biased: GC allocations are taken from the high end of the heap. Regular (and TLAB)
739 // mutator allocations are taken from the middle of heap, below the memory reserved for Collector.
740 // Humongous mutator allocations are taken from the bottom of the heap.
741 //
742 // Free set maintains mutator and collector partitions. Normally, each allocates only from its partition,
743 // except in special cases when the collector steals regions from the mutator partition.
744
745 // Overwrite with non-zero (non-NULL) values only if necessary for allocation bookkeeping.
746 bool allow_new_region = true;
747 if (_heap->mode()->is_generational()) {
748 switch (req.affiliation()) {
749 case ShenandoahAffiliation::OLD_GENERATION:
750 // Note: unsigned result from free_unaffiliated_regions() will never be less than zero, but it may equal zero.
751 if (_heap->old_generation()->free_unaffiliated_regions() <= 0) {
752 allow_new_region = false;
753 }
754 break;
755
756 case ShenandoahAffiliation::YOUNG_GENERATION:
757 // Note: unsigned result from free_unaffiliated_regions() will never be less than zero, but it may equal zero.
758 if (_heap->young_generation()->free_unaffiliated_regions() <= 0) {
759 allow_new_region = false;
760 }
761 break;
762
763 case ShenandoahAffiliation::FREE:
764 fatal("Should request affiliation");
765
766 default:
767 ShouldNotReachHere();
768 break;
769 }
770 }
771 switch (req.type()) {
772 case ShenandoahAllocRequest::_alloc_tlab:
773 case ShenandoahAllocRequest::_alloc_shared: {
774 // Try to allocate in the mutator view
775 if (_alloc_bias_weight-- <= 0) {
776 // We have observed that regions not collected in previous GC cycle tend to congregate at one end or the other
777 // of the heap. Typically, these are the more recently engaged regions and the objects in these regions have not
778 // yet had a chance to die (and/or are treated as floating garbage). If we use the same allocation bias on each
779 // GC pass, these "most recently" engaged regions for GC pass N will also be the "most recently" engaged regions
780 // for GC pass N+1, and the relatively large amount of live data and/or floating garbage introduced
781 // during the most recent GC pass may once again prevent the region from being collected. We have found that
782 // alternating the allocation behavior between GC passes improves evacuation performance by 3-7% on certain
783 // benchmarks. In the best case, this has the effect of consuming these partially consumed regions before
784 // the start of the next mark cycle so all of their garbage can be efficiently reclaimed.
785 //
786 // First, finish consuming regions that are already partially consumed so as to more tightly limit ranges of
787 // available regions. Other potential benefits:
788 // 1. Eventual collection set has fewer regions because we have packed newly allocated objects into fewer regions
789 // 2. We preserve the "empty" regions longer into the GC cycle, reducing likelihood of allocation failures
790 // late in the GC cycle.
791 idx_t non_empty_on_left = (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator)
792 - _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator));
793 idx_t non_empty_on_right = (_partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator)
794 - _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator));
795 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::Mutator, (non_empty_on_right < non_empty_on_left));
796 _alloc_bias_weight = _InitialAllocBiasWeight;
797 }
798 if (!_partitions.alloc_from_left_bias(ShenandoahFreeSetPartitionId::Mutator)) {
799 // Allocate within mutator free from high memory to low so as to preserve low memory for humongous allocations
800 if (!_partitions.is_empty(ShenandoahFreeSetPartitionId::Mutator)) {
801 // Use signed idx. Otherwise, loop will never terminate.
802 idx_t leftmost = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator);
803 for (idx_t idx = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator); idx >= leftmost; ) {
804 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx),
805 "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
806 ShenandoahHeapRegion* r = _heap->get_region(idx);
807 // try_allocate_in() increases used if the allocation is successful.
808 HeapWord* result;
809 size_t min_size = (req.type() == ShenandoahAllocRequest::_alloc_tlab)? req.min_size(): req.size();
810 if ((alloc_capacity(r) >= min_size) && ((result = try_allocate_in(r, req, in_new_region)) != nullptr)) {
811 return result;
812 }
813 idx = _partitions.find_index_of_previous_available_region(ShenandoahFreeSetPartitionId::Mutator, idx - 1);
814 }
815 }
816 } else {
817 // Allocate from low to high memory. This keeps the range of fully empty regions more tightly packed.
818 // Note that the most recently allocated regions tend not to be evacuated in a given GC cycle. So this
819 // tends to accumulate "fragmented" uncollected regions in high memory.
820 if (!_partitions.is_empty(ShenandoahFreeSetPartitionId::Mutator)) {
821 // Use signed idx. Otherwise, loop will never terminate.
822 idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
823 for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); idx <= rightmost; ) {
824 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx),
825 "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
826 ShenandoahHeapRegion* r = _heap->get_region(idx);
827 // try_allocate_in() increases used if the allocation is successful.
828 HeapWord* result;
829 size_t min_size = (req.type() == ShenandoahAllocRequest::_alloc_tlab)? req.min_size(): req.size();
830 if ((alloc_capacity(r) >= min_size) && ((result = try_allocate_in(r, req, in_new_region)) != nullptr)) {
831 return result;
832 }
833 idx = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, idx + 1);
834 }
835 }
836 }
837 // There is no recovery. Mutator does not touch collector view at all.
838 break;
839 }
840 case ShenandoahAllocRequest::_alloc_gclab:
841 // GCLABs are for evacuation so we must be in evacuation phase.
842
843 case ShenandoahAllocRequest::_alloc_plab: {
844 // PLABs always reside in old-gen and are only allocated during
845 // evacuation phase.
846
847 case ShenandoahAllocRequest::_alloc_shared_gc: {
848 // Fast-path: try to allocate in the collector view first
849 HeapWord* result;
850 result = allocate_from_partition_with_affiliation(req.is_old()? ShenandoahFreeSetPartitionId::OldCollector:
851 ShenandoahFreeSetPartitionId::Collector,
852 req.affiliation(), req, in_new_region);
853 if (result != nullptr) {
854 return result;
855 } else if (allow_new_region) {
856 // Try a free region that is dedicated to GC allocations.
857 result = allocate_from_partition_with_affiliation(req.is_old()? ShenandoahFreeSetPartitionId::OldCollector:
858 ShenandoahFreeSetPartitionId::Collector,
859 ShenandoahAffiliation::FREE, req, in_new_region);
860 if (result != nullptr) {
861 return result;
862 }
863 }
864
865 // No dice. Can we borrow space from mutator view?
866 if (!ShenandoahEvacReserveOverflow) {
867 return nullptr;
868 }
869 if (!allow_new_region && req.is_old() && (_heap->young_generation()->free_unaffiliated_regions() > 0)) {
870 // This allows us to flip a mutator region to old_collector
871 allow_new_region = true;
872 }
873
874 // We should expand old-gen if this can prevent an old-gen evacuation failure. We don't care so much about
875 // promotion failures since they can be mitigated in a subsequent GC pass. Would be nice to know if this
876 // allocation request is for evacuation or promotion. Individual threads limit their use of PLAB memory for
877 // promotions, so we already have an assurance that any additional memory set aside for old-gen will be used
878 // only for old-gen evacuations.
879
880 // TODO:
881 // if (GC is idle (out of cycle) and mutator allocation fails and there is memory reserved in Collector
882 // or OldCollector sets, transfer a region of memory so that we can satisfy the allocation request, and
883 // immediately trigger the start of GC. Is better to satisfy the allocation than to trigger out-of-cycle
884 // allocation failure (even if this means we have a little less memory to handle evacuations during the
885 // subsequent GC pass).
886
887 if (allow_new_region) {
888 // Try to steal an empty region from the mutator view.
889 idx_t rightmost_mutator = _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator);
890 idx_t leftmost_mutator = _partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator);
891 for (idx_t idx = rightmost_mutator; idx >= leftmost_mutator; ) {
892 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx),
893 "Boundaries or find_prev_last_bit failed: " SSIZE_FORMAT, idx);
894 ShenandoahHeapRegion* r = _heap->get_region(idx);
895 if (can_allocate_from(r)) {
896 if (req.is_old()) {
897 flip_to_old_gc(r);
898 } else {
899 flip_to_gc(r);
900 }
901 // Region r is entirely empty. If try_allocat_in fails on region r, something else is really wrong.
902 // Don't bother to retry with other regions.
903 log_debug(gc, free)("Flipped region " SIZE_FORMAT " to gc for request: " PTR_FORMAT, idx, p2i(&req));
904 return try_allocate_in(r, req, in_new_region);
905 }
906 idx = _partitions.find_index_of_previous_available_region(ShenandoahFreeSetPartitionId::Mutator, idx - 1);
907 }
908 }
909 // No dice. Do not try to mix mutator and GC allocations, because adjusting region UWM
910 // due to GC allocations would expose unparsable mutator allocations.
911 break;
912 }
913 }
914 default:
915 ShouldNotReachHere();
916 }
917 return nullptr;
918 }
919
920 // This work method takes an argument corresponding to the number of bytes
921 // free in a region, and returns the largest amount in heapwords that can be allocated
922 // such that both of the following conditions are satisfied:
923 //
924 // 1. it is a multiple of card size
925 // 2. any remaining shard may be filled with a filler object
926 //
927 // The idea is that the allocation starts and ends at card boundaries. Because
928 // a region ('s end) is card-aligned, the remainder shard that must be filled is
929 // at the start of the free space.
930 //
931 // This is merely a helper method to use for the purpose of such a calculation.
932 size_t ShenandoahFreeSet::get_usable_free_words(size_t free_bytes) const {
933 // e.g. card_size is 512, card_shift is 9, min_fill_size() is 8
934 // free is 514
935 // usable_free is 512, which is decreased to 0
936 size_t usable_free = (free_bytes / CardTable::card_size()) << CardTable::card_shift();
937 assert(usable_free <= free_bytes, "Sanity check");
938 if ((free_bytes != usable_free) && (free_bytes - usable_free < ShenandoahHeap::min_fill_size() * HeapWordSize)) {
939 // After aligning to card multiples, the remainder would be smaller than
940 // the minimum filler object, so we'll need to take away another card's
941 // worth to construct a filler object.
942 if (usable_free >= CardTable::card_size()) {
943 usable_free -= CardTable::card_size();
944 } else {
945 assert(usable_free == 0, "usable_free is a multiple of card_size and card_size > min_fill_size");
946 }
947 }
948
949 return usable_free / HeapWordSize;
950 }
951
952 // Given a size argument, which is a multiple of card size, a request struct
953 // for a PLAB, and an old region, return a pointer to the allocated space for
954 // a PLAB which is card-aligned and where any remaining shard in the region
955 // has been suitably filled by a filler object.
956 // It is assumed (and assertion-checked) that such an allocation is always possible.
957 HeapWord* ShenandoahFreeSet::allocate_aligned_plab(size_t size, ShenandoahAllocRequest& req, ShenandoahHeapRegion* r) {
958 assert(_heap->mode()->is_generational(), "PLABs are only for generational mode");
959 assert(r->is_old(), "All PLABs reside in old-gen");
960 assert(!req.is_mutator_alloc(), "PLABs should not be allocated by mutators.");
961 assert(is_aligned(size, CardTable::card_size_in_words()), "Align by design");
962
963 HeapWord* result = r->allocate_aligned(size, req, CardTable::card_size());
964 assert(result != nullptr, "Allocation cannot fail");
965 assert(r->top() <= r->end(), "Allocation cannot span end of region");
966 assert(is_aligned(result, CardTable::card_size_in_words()), "Align by design");
967 return result;
968 }
969
970 HeapWord* ShenandoahFreeSet::try_allocate_in(ShenandoahHeapRegion* r, ShenandoahAllocRequest& req, bool& in_new_region) {
971 assert (has_alloc_capacity(r), "Performance: should avoid full regions on this path: " SIZE_FORMAT, r->index());
972 if (_heap->is_concurrent_weak_root_in_progress() && r->is_trash()) {
973 return nullptr;
974 }
975 HeapWord* result = nullptr;
976 try_recycle_trashed(r);
977 in_new_region = r->is_empty();
978
979 if (in_new_region) {
980 log_debug(gc)("Using new region (" SIZE_FORMAT ") for %s (" PTR_FORMAT ").",
981 r->index(), ShenandoahAllocRequest::alloc_type_to_string(req.type()), p2i(&req));
982 assert(!r->is_affiliated(), "New region " SIZE_FORMAT " should be unaffiliated", r->index());
983 r->set_affiliation(req.affiliation());
984 if (r->is_old()) {
985 // Any OLD region allocated during concurrent coalesce-and-fill does not need to be coalesced and filled because
986 // all objects allocated within this region are above TAMS (and thus are implicitly marked). In case this is an
987 // OLD region and concurrent preparation for mixed evacuations visits this region before the start of the next
988 // old-gen concurrent mark (i.e. this region is allocated following the start of old-gen concurrent mark but before
989 // concurrent preparations for mixed evacuations are completed), we mark this region as not requiring any
990 // coalesce-and-fill processing.
991 r->end_preemptible_coalesce_and_fill();
992 _heap->old_generation()->clear_cards_for(r);
993 }
994 _heap->generation_for(r->affiliation())->increment_affiliated_region_count();
995
996 #ifdef ASSERT
997 ShenandoahMarkingContext* const ctx = _heap->complete_marking_context();
998 assert(ctx->top_at_mark_start(r) == r->bottom(), "Newly established allocation region starts with TAMS equal to bottom");
999 assert(ctx->is_bitmap_clear_range(ctx->top_bitmap(r), r->end()), "Bitmap above top_bitmap() must be clear");
1000 #endif
1001 log_debug(gc)("Using new region (" SIZE_FORMAT ") for %s (" PTR_FORMAT ").",
1002 r->index(), ShenandoahAllocRequest::alloc_type_to_string(req.type()), p2i(&req));
1003 } else {
1004 assert(r->is_affiliated(), "Region " SIZE_FORMAT " that is not new should be affiliated", r->index());
1005 if (r->affiliation() != req.affiliation()) {
1006 assert(_heap->mode()->is_generational(), "Request for %s from %s region should only happen in generational mode.",
1007 req.affiliation_name(), r->affiliation_name());
1008 return nullptr;
1009 }
1010 }
1011
1012 // req.size() is in words, r->free() is in bytes.
1013 if (req.is_lab_alloc()) {
1014 size_t adjusted_size = req.size();
1015 size_t free = r->free(); // free represents bytes available within region r
1016 if (req.type() == ShenandoahAllocRequest::_alloc_plab) {
1017 // This is a PLAB allocation
1018 assert(_heap->mode()->is_generational(), "PLABs are only for generational mode");
1019 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, r->index()),
1020 "PLABS must be allocated in old_collector_free regions");
1021
1022 // Need to assure that plabs are aligned on multiple of card region
1023 // Convert free from unaligned bytes to aligned number of words
1024 size_t usable_free = get_usable_free_words(free);
1025 if (adjusted_size > usable_free) {
1026 adjusted_size = usable_free;
1027 }
1028 adjusted_size = align_down(adjusted_size, CardTable::card_size_in_words());
1029 if (adjusted_size >= req.min_size()) {
1030 result = allocate_aligned_plab(adjusted_size, req, r);
1031 assert(result != nullptr, "allocate must succeed");
1032 req.set_actual_size(adjusted_size);
1033 } else {
1034 // Otherwise, leave result == nullptr because the adjusted size is smaller than min size.
1035 log_trace(gc, free)("Failed to shrink PLAB request (" SIZE_FORMAT ") in region " SIZE_FORMAT " to " SIZE_FORMAT
1036 " because min_size() is " SIZE_FORMAT, req.size(), r->index(), adjusted_size, req.min_size());
1037 }
1038 } else {
1039 // This is a GCLAB or a TLAB allocation
1040 // Convert free from unaligned bytes to aligned number of words
1041 free = align_down(free >> LogHeapWordSize, MinObjAlignment);
1042 if (adjusted_size > free) {
1043 adjusted_size = free;
1044 }
1045 if (adjusted_size >= req.min_size()) {
1046 result = r->allocate(adjusted_size, req);
1047 assert (result != nullptr, "Allocation must succeed: free " SIZE_FORMAT ", actual " SIZE_FORMAT, free, adjusted_size);
1048 req.set_actual_size(adjusted_size);
1049 } else {
1050 log_trace(gc, free)("Failed to shrink TLAB or GCLAB request (" SIZE_FORMAT ") in region " SIZE_FORMAT " to " SIZE_FORMAT
1051 " because min_size() is " SIZE_FORMAT, req.size(), r->index(), adjusted_size, req.min_size());
1052 }
1053 }
1054 } else {
1055 size_t size = req.size();
1056 result = r->allocate(size, req);
1057 if (result != nullptr) {
1058 // Record actual allocation size
1059 req.set_actual_size(size);
1060 }
1061 }
1062
1063 if (result != nullptr) {
1064 // Allocation successful, bump stats:
1065 if (req.is_mutator_alloc()) {
1066 assert(req.is_young(), "Mutator allocations always come from young generation.");
1067 _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, req.actual_size() * HeapWordSize);
1068 } else {
1069 assert(req.is_gc_alloc(), "Should be gc_alloc since req wasn't mutator alloc");
1070
1071 // For GC allocations, we advance update_watermark because the objects relocated into this memory during
1072 // evacuation are not updated during evacuation. For both young and old regions r, it is essential that all
1073 // PLABs be made parsable at the end of evacuation. This is enabled by retiring all plabs at end of evacuation.
1074 // TODO: Making a PLAB parsable involves placing a filler object in its remnant memory but does not require
1075 // that the PLAB be disabled for all future purposes. We may want to introduce a new service to make the
1076 // PLABs parsable while still allowing the PLAB to serve future allocation requests that arise during the
1077 // next evacuation pass.
1078 r->set_update_watermark(r->top());
1079 if (r->is_old()) {
1080 _partitions.increase_used(ShenandoahFreeSetPartitionId::OldCollector, req.actual_size() * HeapWordSize);
1081 assert(req.type() != ShenandoahAllocRequest::_alloc_gclab, "old-gen allocations use PLAB or shared allocation");
1082 // for plabs, we'll sort the difference between evac and promotion usage when we retire the plab
1083 } else {
1084 _partitions.increase_used(ShenandoahFreeSetPartitionId::Collector, req.actual_size() * HeapWordSize);
1085 }
1086 }
1087 }
1088
1089 static const size_t min_capacity = (size_t) (ShenandoahHeapRegion::region_size_bytes() * (1.0 - 1.0 / ShenandoahEvacWaste));
1090 size_t ac = alloc_capacity(r);
1091
1092 if (((result == nullptr) && (ac < min_capacity)) || (alloc_capacity(r) < PLAB::min_size() * HeapWordSize)) {
1093 // Regardless of whether this allocation succeeded, if the remaining memory is less than PLAB:min_size(), retire this region.
1094 // Note that retire_from_partition() increases used to account for waste.
1095
1096 // Also, if this allocation request failed and the consumed within this region * ShenandoahEvacWaste > region size,
1097 // then retire the region so that subsequent searches can find available memory more quickly.
1098
1099 size_t idx = r->index();
1100 ShenandoahFreeSetPartitionId orig_partition;
1101 if (req.is_mutator_alloc()) {
1102 orig_partition = ShenandoahFreeSetPartitionId::Mutator;
1103 } else if (req.type() == ShenandoahAllocRequest::_alloc_gclab) {
1104 orig_partition = ShenandoahFreeSetPartitionId::Collector;
1105 } else if (req.type() == ShenandoahAllocRequest::_alloc_plab) {
1106 orig_partition = ShenandoahFreeSetPartitionId::OldCollector;
1107 } else {
1108 assert(req.type() == ShenandoahAllocRequest::_alloc_shared_gc, "Unexpected allocation type");
1109 if (req.is_old()) {
1110 orig_partition = ShenandoahFreeSetPartitionId::OldCollector;
1111 } else {
1112 orig_partition = ShenandoahFreeSetPartitionId::Collector;
1113 }
1114 }
1115 _partitions.retire_from_partition(orig_partition, idx, r->used());
1116 _partitions.assert_bounds();
1117 }
1118 return result;
1119 }
1120
1121 HeapWord* ShenandoahFreeSet::allocate_contiguous(ShenandoahAllocRequest& req) {
1122 assert(req.is_mutator_alloc(), "All humongous allocations are performed by mutator");
1123 shenandoah_assert_heaplocked();
1124
1125 size_t words_size = req.size();
1126 idx_t num = ShenandoahHeapRegion::required_regions(words_size * HeapWordSize);
1127
1128 assert(req.is_young(), "Humongous regions always allocated in YOUNG");
1129 ShenandoahGeneration* generation = _heap->generation_for(req.affiliation());
1130
1131 // Check if there are enough regions left to satisfy allocation.
1132 if (num > (idx_t) _partitions.count(ShenandoahFreeSetPartitionId::Mutator)) {
1133 return nullptr;
1134 }
1135
1136 idx_t start_range = _partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator);
1137 idx_t end_range = _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator) + 1;
1138 idx_t last_possible_start = end_range - num;
1139
1140 // Find the continuous interval of $num regions, starting from $beg and ending in $end,
1141 // inclusive. Contiguous allocations are biased to the beginning.
1142 idx_t beg = _partitions.find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId::Mutator,
1143 start_range, num);
1144 if (beg > last_possible_start) {
1145 // Hit the end, goodbye
1146 return nullptr;
1147 }
1148 idx_t end = beg;
1149
1150 while (true) {
1151 // We've confirmed num contiguous regions belonging to Mutator partition, so no need to confirm membership.
1152 // If region is not completely free, the current [beg; end] is useless, and we may fast-forward. If we can extend
1153 // the existing range, we can exploit that certain regions are already known to be in the Mutator free set.
1154 while (!can_allocate_from(_heap->get_region(end))) {
1155 // region[end] is not empty, so we restart our search after region[end]
1156 idx_t slide_delta = end + 1 - beg;
1157 if (beg + slide_delta > last_possible_start) {
1158 // no room to slide
1159 return nullptr;
1160 }
1161 for (idx_t span_end = beg + num; slide_delta > 0; slide_delta--) {
1162 if (!_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, span_end)) {
1163 beg = _partitions.find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId::Mutator,
1164 span_end + 1, num);
1165 break;
1166 } else {
1167 beg++;
1168 span_end++;
1169 }
1170 }
1171 // Here, either beg identifies a range of num regions all of which are in the Mutator free set, or beg > last_possible_start
1172 if (beg > last_possible_start) {
1173 // Hit the end, goodbye
1174 return nullptr;
1175 }
1176 end = beg;
1177 }
1178
1179 if ((end - beg + 1) == num) {
1180 // found the match
1181 break;
1182 }
1183
1184 end++;
1185 }
1186
1187 size_t remainder = words_size & ShenandoahHeapRegion::region_size_words_mask();
1188 // Initialize regions:
1189 for (idx_t i = beg; i <= end; i++) {
1190 ShenandoahHeapRegion* r = _heap->get_region(i);
1191 try_recycle_trashed(r);
1192
1193 assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous");
1194 assert(r->is_empty(), "Should be empty");
1195
1196 if (i == beg) {
1197 r->make_humongous_start();
1198 } else {
1199 r->make_humongous_cont();
1200 }
1201
1202 // Trailing region may be non-full, record the remainder there
1203 size_t used_words;
1204 if ((i == end) && (remainder != 0)) {
1205 used_words = remainder;
1206 } else {
1207 used_words = ShenandoahHeapRegion::region_size_words();
1208 }
1209
1210 r->set_affiliation(req.affiliation());
1211 r->set_update_watermark(r->bottom());
1212 r->set_top(r->bottom() + used_words);
1213 }
1214 generation->increase_affiliated_region_count(num);
1215 if (remainder != 0) {
1216 // Record this remainder as allocation waste
1217 _heap->notify_mutator_alloc_words(ShenandoahHeapRegion::region_size_words() - remainder, true);
1218 }
1219
1220 // retire_range_from_partition() will adjust bounds on Mutator free set if appropriate
1221 _partitions.retire_range_from_partition(ShenandoahFreeSetPartitionId::Mutator, beg, end);
1222
1223 size_t total_humongous_size = ShenandoahHeapRegion::region_size_bytes() * num;
1224 _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, total_humongous_size);
1225 _partitions.assert_bounds();
1226 req.set_actual_size(words_size);
1227 if (remainder != 0) {
1228 req.set_waste(ShenandoahHeapRegion::region_size_words() - remainder);
1229 }
1230 return _heap->get_region(beg)->bottom();
1231 }
1232
1233 void ShenandoahFreeSet::try_recycle_trashed(ShenandoahHeapRegion* r) {
1234 if (r->is_trash()) {
1235 r->recycle();
1236 }
1237 }
1238
1239 void ShenandoahFreeSet::recycle_trash() {
1240 // lock is not reentrable, check we don't have it
1241 shenandoah_assert_not_heaplocked();
1242
1243 size_t count = 0;
1244 for (size_t i = 0; i < _heap->num_regions(); i++) {
1245 ShenandoahHeapRegion* r = _heap->get_region(i);
1246 if (r->is_trash()) {
1247 _trash_regions[count++] = r;
1248 }
1249 }
1250
1251 // Relinquish the lock after this much time passed.
1252 static constexpr jlong deadline_ns = 30000; // 30 us
1253 size_t idx = 0;
1254 while (idx < count) {
1255 os::naked_yield(); // Yield to allow allocators to take the lock
1256 ShenandoahHeapLocker locker(_heap->lock());
1257 const jlong deadline = os::javaTimeNanos() + deadline_ns;
1258 while (idx < count && os::javaTimeNanos() < deadline) {
1259 try_recycle_trashed(_trash_regions[idx++]);
1260 }
1261 }
1262 }
1263
1264 void ShenandoahFreeSet::flip_to_old_gc(ShenandoahHeapRegion* r) {
1265 size_t idx = r->index();
1266
1267 assert(_partitions.partition_id_matches(idx, ShenandoahFreeSetPartitionId::Mutator), "Should be in mutator view");
1268 assert(can_allocate_from(r), "Should not be allocated");
1269
1270 ShenandoahGenerationalHeap* gen_heap = ShenandoahGenerationalHeap::heap();
1271 size_t region_capacity = alloc_capacity(r);
1272 _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
1273 ShenandoahFreeSetPartitionId::OldCollector, region_capacity);
1274 _partitions.assert_bounds();
1275 _heap->old_generation()->augment_evacuation_reserve(region_capacity);
1276 bool transferred = gen_heap->generation_sizer()->transfer_to_old(1);
1277 if (!transferred) {
1278 log_warning(gc, free)("Forcing transfer of " SIZE_FORMAT " to old reserve.", idx);
1279 gen_heap->generation_sizer()->force_transfer_to_old(1);
1280 }
1281 // We do not ensure that the region is no longer trash, relying on try_allocate_in(), which always comes next,
1282 // to recycle trash before attempting to allocate anything in the region.
1283 }
1284
1285 void ShenandoahFreeSet::flip_to_gc(ShenandoahHeapRegion* r) {
1286 size_t idx = r->index();
1287
1288 assert(_partitions.partition_id_matches(idx, ShenandoahFreeSetPartitionId::Mutator), "Should be in mutator view");
1289 assert(can_allocate_from(r), "Should not be allocated");
1290
1291 size_t ac = alloc_capacity(r);
1292 _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
1293 ShenandoahFreeSetPartitionId::Collector, ac);
1294 _partitions.assert_bounds();
1295
1296 // We do not ensure that the region is no longer trash, relying on try_allocate_in(), which always comes next,
1297 // to recycle trash before attempting to allocate anything in the region.
1298 }
1299
1300 void ShenandoahFreeSet::clear() {
1301 shenandoah_assert_heaplocked();
1302 clear_internal();
1303 }
1304
1305 void ShenandoahFreeSet::clear_internal() {
1306 _partitions.make_all_regions_unavailable();
1307
1308 _alloc_bias_weight = 0;
1309 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::Mutator, true);
1310 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::Collector, false);
1311 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::OldCollector, false);
1312 }
1313
1314 void ShenandoahFreeSet::find_regions_with_alloc_capacity(size_t &young_cset_regions, size_t &old_cset_regions,
1315 size_t &first_old_region, size_t &last_old_region,
1316 size_t &old_region_count) {
1317 clear_internal();
1318
1319 first_old_region = _heap->num_regions();
1320 last_old_region = 0;
1321 old_region_count = 0;
1322 old_cset_regions = 0;
1323 young_cset_regions = 0;
1324
1325 size_t region_size_bytes = _partitions.region_size_bytes();
1326 size_t max_regions = _partitions.max_regions();
1327
1328 size_t mutator_leftmost = max_regions;
1329 size_t mutator_rightmost = 0;
1330 size_t mutator_leftmost_empty = max_regions;
1331 size_t mutator_rightmost_empty = 0;
1332 size_t mutator_regions = 0;
1333 size_t mutator_used = 0;
1334
1335 size_t old_collector_leftmost = max_regions;
1336 size_t old_collector_rightmost = 0;
1337 size_t old_collector_leftmost_empty = max_regions;
1338 size_t old_collector_rightmost_empty = 0;
1339 size_t old_collector_regions = 0;
1340 size_t old_collector_used = 0;
1341
1342 for (size_t idx = 0; idx < _heap->num_regions(); idx++) {
1343 ShenandoahHeapRegion* region = _heap->get_region(idx);
1344 if (region->is_trash()) {
1345 // Trashed regions represent regions that had been in the collection partition but have not yet been "cleaned up".
1346 // The cset regions are not "trashed" until we have finished update refs.
1347 if (region->is_old()) {
1348 old_cset_regions++;
1349 } else {
1350 assert(region->is_young(), "Trashed region should be old or young");
1351 young_cset_regions++;
1352 }
1353 } else if (region->is_old()) {
1354 // count both humongous and regular regions, but don't count trash (cset) regions.
1355 old_region_count++;
1356 if (first_old_region > idx) {
1357 first_old_region = idx;
1358 }
1359 last_old_region = idx;
1360 }
1361 if (region->is_alloc_allowed() || region->is_trash()) {
1362 assert(!region->is_cset(), "Shouldn't be adding cset regions to the free set");
1363
1364 // Do not add regions that would almost surely fail allocation
1365 size_t ac = alloc_capacity(region);
1366 if (ac > PLAB::min_size() * HeapWordSize) {
1367 if (region->is_trash() || !region->is_old()) {
1368 // Both young and old collected regions (trashed) are placed into the Mutator set
1369 _partitions.raw_assign_membership(idx, ShenandoahFreeSetPartitionId::Mutator);
1370 if (idx < mutator_leftmost) {
1371 mutator_leftmost = idx;
1372 }
1373 if (idx > mutator_rightmost) {
1374 mutator_rightmost = idx;
1375 }
1376 if (ac == region_size_bytes) {
1377 if (idx < mutator_leftmost_empty) {
1378 mutator_leftmost_empty = idx;
1379 }
1380 if (idx > mutator_rightmost_empty) {
1381 mutator_rightmost_empty = idx;
1382 }
1383 }
1384 mutator_regions++;
1385 mutator_used += (region_size_bytes - ac);
1386 } else {
1387 // !region->is_trash() && region is_old()
1388 _partitions.raw_assign_membership(idx, ShenandoahFreeSetPartitionId::OldCollector);
1389 if (idx < old_collector_leftmost) {
1390 old_collector_leftmost = idx;
1391 }
1392 if (idx > old_collector_rightmost) {
1393 old_collector_rightmost = idx;
1394 }
1395 if (ac == region_size_bytes) {
1396 if (idx < old_collector_leftmost_empty) {
1397 old_collector_leftmost_empty = idx;
1398 }
1399 if (idx > old_collector_rightmost_empty) {
1400 old_collector_rightmost_empty = idx;
1401 }
1402 }
1403 old_collector_regions++;
1404 old_collector_used += (region_size_bytes - ac);
1405 }
1406 }
1407 }
1408 }
1409 log_debug(gc)(" At end of prep_to_rebuild, mutator_leftmost: " SIZE_FORMAT
1410 ", mutator_rightmost: " SIZE_FORMAT
1411 ", mutator_leftmost_empty: " SIZE_FORMAT
1412 ", mutator_rightmost_empty: " SIZE_FORMAT
1413 ", mutator_regions: " SIZE_FORMAT
1414 ", mutator_used: " SIZE_FORMAT,
1415 mutator_leftmost, mutator_rightmost, mutator_leftmost_empty, mutator_rightmost_empty,
1416 mutator_regions, mutator_used);
1417
1418 log_debug(gc)(" old_collector_leftmost: " SIZE_FORMAT
1419 ", old_collector_rightmost: " SIZE_FORMAT
1420 ", old_collector_leftmost_empty: " SIZE_FORMAT
1421 ", old_collector_rightmost_empty: " SIZE_FORMAT
1422 ", old_collector_regions: " SIZE_FORMAT
1423 ", old_collector_used: " SIZE_FORMAT,
1424 old_collector_leftmost, old_collector_rightmost, old_collector_leftmost_empty, old_collector_rightmost_empty,
1425 old_collector_regions, old_collector_used);
1426
1427 _partitions.establish_mutator_intervals(mutator_leftmost, mutator_rightmost, mutator_leftmost_empty, mutator_rightmost_empty,
1428 mutator_regions, mutator_used);
1429 _partitions.establish_old_collector_intervals(old_collector_leftmost, old_collector_rightmost, old_collector_leftmost_empty,
1430 old_collector_rightmost_empty, old_collector_regions, old_collector_used);
1431 log_debug(gc)(" After find_regions_with_alloc_capacity(), Mutator range [" SSIZE_FORMAT ", " SSIZE_FORMAT "],"
1432 " Old Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT "]",
1433 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
1434 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
1435 _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector),
1436 _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector));
1437 }
1438
1439 // Returns number of regions transferred, adds transferred bytes to var argument bytes_transferred
1440 size_t ShenandoahFreeSet::transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId which_collector,
1441 size_t max_xfer_regions,
1442 size_t& bytes_transferred) {
1443 shenandoah_assert_heaplocked();
1444 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1445 size_t transferred_regions = 0;
1446 idx_t rightmost = _partitions.rightmost_empty(which_collector);
1447 for (idx_t idx = _partitions.leftmost_empty(which_collector); (transferred_regions < max_xfer_regions) && (idx <= rightmost); ) {
1448 assert(_partitions.in_free_set(which_collector, idx), "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, idx);
1449 // Note: can_allocate_from() denotes that region is entirely empty
1450 if (can_allocate_from(idx)) {
1451 _partitions.move_from_partition_to_partition(idx, which_collector, ShenandoahFreeSetPartitionId::Mutator, region_size_bytes);
1452 transferred_regions++;
1453 bytes_transferred += region_size_bytes;
1454 }
1455 idx = _partitions.find_index_of_next_available_region(which_collector, idx + 1);
1456 }
1457 return transferred_regions;
1458 }
1459
1460 // Returns number of regions transferred, adds transferred bytes to var argument bytes_transferred
1461 size_t ShenandoahFreeSet::transfer_non_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId collector_id,
1462 size_t max_xfer_regions,
1463 size_t& bytes_transferred) {
1464 shenandoah_assert_heaplocked();
1465 size_t transferred_regions = 0;
1466 idx_t rightmost = _partitions.rightmost(collector_id);
1467 for (idx_t idx = _partitions.leftmost(collector_id); (transferred_regions < max_xfer_regions) && (idx <= rightmost); ) {
1468 assert(_partitions.in_free_set(collector_id, idx), "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, idx);
1469 size_t ac = alloc_capacity(idx);
1470 if (ac > 0) {
1471 _partitions.move_from_partition_to_partition(idx, collector_id, ShenandoahFreeSetPartitionId::Mutator, ac);
1472 transferred_regions++;
1473 bytes_transferred += ac;
1474 }
1475 idx = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Collector, idx + 1);
1476 }
1477 return transferred_regions;
1478 }
1479
1480 void ShenandoahFreeSet::move_regions_from_collector_to_mutator(size_t max_xfer_regions) {
1481 size_t collector_xfer = 0;
1482 size_t old_collector_xfer = 0;
1483
1484 // Process empty regions within the Collector free partition
1485 if ((max_xfer_regions > 0) &&
1486 (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Collector)
1487 <= _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Collector))) {
1488 ShenandoahHeapLocker locker(_heap->lock());
1489 max_xfer_regions -=
1490 transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId::Collector, max_xfer_regions,
1491 collector_xfer);
1492 }
1493
1494 // Process empty regions within the OldCollector free partition
1495 if ((max_xfer_regions > 0) &&
1496 (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::OldCollector)
1497 <= _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::OldCollector))) {
1498 ShenandoahHeapLocker locker(_heap->lock());
1499 size_t old_collector_regions =
1500 transfer_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId::OldCollector, max_xfer_regions,
1501 old_collector_xfer);
1502 max_xfer_regions -= old_collector_regions;
1503 if (old_collector_regions > 0) {
1504 ShenandoahGenerationalHeap::cast(_heap)->generation_sizer()->transfer_to_young(old_collector_regions);
1505 }
1506 }
1507
1508 // If there are any non-empty regions within Collector partition, we can also move them to the Mutator free partition
1509 if ((max_xfer_regions > 0) && (_partitions.leftmost(ShenandoahFreeSetPartitionId::Collector)
1510 <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector))) {
1511 ShenandoahHeapLocker locker(_heap->lock());
1512 max_xfer_regions -=
1513 transfer_non_empty_regions_from_collector_set_to_mutator_set(ShenandoahFreeSetPartitionId::Collector, max_xfer_regions,
1514 collector_xfer);
1515 }
1516
1517 size_t total_xfer = collector_xfer + old_collector_xfer;
1518 log_info(gc, ergo)("At start of update refs, moving " SIZE_FORMAT "%s to Mutator free set from Collector Reserve ("
1519 SIZE_FORMAT "%s) and from Old Collector Reserve (" SIZE_FORMAT "%s)",
1520 byte_size_in_proper_unit(total_xfer), proper_unit_for_byte_size(total_xfer),
1521 byte_size_in_proper_unit(collector_xfer), proper_unit_for_byte_size(collector_xfer),
1522 byte_size_in_proper_unit(old_collector_xfer), proper_unit_for_byte_size(old_collector_xfer));
1523 }
1524
1525
1526 // Overwrite arguments to represent the amount of memory in each generation that is about to be recycled
1527 void ShenandoahFreeSet::prepare_to_rebuild(size_t &young_cset_regions, size_t &old_cset_regions,
1528 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count) {
1529 shenandoah_assert_heaplocked();
1530 // This resets all state information, removing all regions from all sets.
1531 clear();
1532 log_debug(gc, free)("Rebuilding FreeSet");
1533
1534 // This places regions that have alloc_capacity into the old_collector set if they identify as is_old() or the
1535 // mutator set otherwise. All trashed (cset) regions are affiliated young and placed in mutator set.
1536 find_regions_with_alloc_capacity(young_cset_regions, old_cset_regions, first_old_region, last_old_region, old_region_count);
1537 }
1538
1539 void ShenandoahFreeSet::establish_generation_sizes(size_t young_region_count, size_t old_region_count) {
1540 assert(young_region_count + old_region_count == ShenandoahHeap::heap()->num_regions(), "Sanity");
1541 if (ShenandoahHeap::heap()->mode()->is_generational()) {
1542 ShenandoahGenerationalHeap* heap = ShenandoahGenerationalHeap::heap();
1543 ShenandoahOldGeneration* old_gen = heap->old_generation();
1544 ShenandoahYoungGeneration* young_gen = heap->young_generation();
1545 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1546
1547 old_gen->set_capacity(old_region_count * region_size_bytes);
1548 young_gen->set_capacity(young_region_count * region_size_bytes);
1549 }
1550 }
1551
1552 void ShenandoahFreeSet::finish_rebuild(size_t young_cset_regions, size_t old_cset_regions, size_t old_region_count,
1553 bool have_evacuation_reserves) {
1554 shenandoah_assert_heaplocked();
1555 size_t young_reserve(0), old_reserve(0);
1556
1557 if (_heap->mode()->is_generational()) {
1558 compute_young_and_old_reserves(young_cset_regions, old_cset_regions, have_evacuation_reserves,
1559 young_reserve, old_reserve);
1560 } else {
1561 young_reserve = (_heap->max_capacity() / 100) * ShenandoahEvacReserve;
1562 old_reserve = 0;
1563 }
1564
1565 // Move some of the mutator regions in the Collector and OldCollector partitions in order to satisfy
1566 // young_reserve and old_reserve.
1567 reserve_regions(young_reserve, old_reserve, old_region_count);
1568 size_t young_region_count = _heap->num_regions() - old_region_count;
1569 establish_generation_sizes(young_region_count, old_region_count);
1570 establish_old_collector_alloc_bias();
1571 _partitions.assert_bounds();
1572 log_status();
1573 }
1574
1575 void ShenandoahFreeSet::compute_young_and_old_reserves(size_t young_cset_regions, size_t old_cset_regions,
1576 bool have_evacuation_reserves,
1577 size_t& young_reserve_result, size_t& old_reserve_result) const {
1578 shenandoah_assert_generational();
1579 const size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1580
1581 ShenandoahOldGeneration* const old_generation = _heap->old_generation();
1582 size_t old_available = old_generation->available();
1583 size_t old_unaffiliated_regions = old_generation->free_unaffiliated_regions();
1584 ShenandoahYoungGeneration* const young_generation = _heap->young_generation();
1585 size_t young_capacity = young_generation->max_capacity();
1586 size_t young_unaffiliated_regions = young_generation->free_unaffiliated_regions();
1587
1588 // Add in the regions we anticipate to be freed by evacuation of the collection set
1589 old_unaffiliated_regions += old_cset_regions;
1590 young_unaffiliated_regions += young_cset_regions;
1591
1592 // Consult old-region balance to make adjustments to current generation capacities and availability.
1593 // The generation region transfers take place after we rebuild.
1594 const ssize_t old_region_balance = old_generation->get_region_balance();
1595 if (old_region_balance != 0) {
1596 #ifdef ASSERT
1597 if (old_region_balance > 0) {
1598 assert(old_region_balance <= checked_cast<ssize_t>(old_unaffiliated_regions), "Cannot transfer regions that are affiliated");
1599 } else {
1600 assert(0 - old_region_balance <= checked_cast<ssize_t>(young_unaffiliated_regions), "Cannot transfer regions that are affiliated");
1601 }
1602 #endif
1603
1604 ssize_t xfer_bytes = old_region_balance * checked_cast<ssize_t>(region_size_bytes);
1605 old_available -= xfer_bytes;
1606 old_unaffiliated_regions -= old_region_balance;
1607 young_capacity += xfer_bytes;
1608 young_unaffiliated_regions += old_region_balance;
1609 }
1610
1611 // All allocations taken from the old collector set are performed by GC, generally using PLABs for both
1612 // promotions and evacuations. The partition between which old memory is reserved for evacuation and
1613 // which is reserved for promotion is enforced using thread-local variables that prescribe intentions for
1614 // each PLAB's available memory.
1615 if (have_evacuation_reserves) {
1616 // We are rebuilding at the end of final mark, having already established evacuation budgets for this GC pass.
1617 const size_t promoted_reserve = old_generation->get_promoted_reserve();
1618 const size_t old_evac_reserve = old_generation->get_evacuation_reserve();
1619 young_reserve_result = young_generation->get_evacuation_reserve();
1620 old_reserve_result = promoted_reserve + old_evac_reserve;
1621 assert(old_reserve_result <= old_available,
1622 "Cannot reserve (" SIZE_FORMAT " + " SIZE_FORMAT") more OLD than is available: " SIZE_FORMAT,
1623 promoted_reserve, old_evac_reserve, old_available);
1624 } else {
1625 // We are rebuilding at end of GC, so we set aside budgets specified on command line (or defaults)
1626 young_reserve_result = (young_capacity * ShenandoahEvacReserve) / 100;
1627 // The auto-sizer has already made old-gen large enough to hold all anticipated evacuations and promotions.
1628 // Affiliated old-gen regions are already in the OldCollector free set. Add in the relevant number of
1629 // unaffiliated regions.
1630 old_reserve_result = old_available;
1631 }
1632
1633 // Old available regions that have less than PLAB::min_size() of available memory are not placed into the OldCollector
1634 // free set. Because of this, old_available may not have enough memory to represent the intended reserve. Adjust
1635 // the reserve downward to account for this possibility. This loss is part of the reason why the original budget
1636 // was adjusted with ShenandoahOldEvacWaste and ShenandoahOldPromoWaste multipliers.
1637 if (old_reserve_result >
1638 _partitions.capacity_of(ShenandoahFreeSetPartitionId::OldCollector) + old_unaffiliated_regions * region_size_bytes) {
1639 old_reserve_result =
1640 _partitions.capacity_of(ShenandoahFreeSetPartitionId::OldCollector) + old_unaffiliated_regions * region_size_bytes;
1641 }
1642
1643 if (young_reserve_result > young_unaffiliated_regions * region_size_bytes) {
1644 young_reserve_result = young_unaffiliated_regions * region_size_bytes;
1645 }
1646 }
1647
1648 // Having placed all regions that have allocation capacity into the mutator set if they identify as is_young()
1649 // or into the old collector set if they identify as is_old(), move some of these regions from the mutator set
1650 // into the collector set or old collector set in order to assure that the memory available for allocations within
1651 // the collector set is at least to_reserve and the memory available for allocations within the old collector set
1652 // is at least to_reserve_old.
1653 void ShenandoahFreeSet::reserve_regions(size_t to_reserve, size_t to_reserve_old, size_t &old_region_count) {
1654 for (size_t i = _heap->num_regions(); i > 0; i--) {
1655 size_t idx = i - 1;
1656 ShenandoahHeapRegion* r = _heap->get_region(idx);
1657 if (!_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx)) {
1658 continue;
1659 }
1660
1661 size_t ac = alloc_capacity(r);
1662 assert (ac > 0, "Membership in free set implies has capacity");
1663 assert (!r->is_old() || r->is_trash(), "Except for trash, mutator_is_free regions should not be affiliated OLD");
1664
1665 bool move_to_old_collector = _partitions.available_in(ShenandoahFreeSetPartitionId::OldCollector) < to_reserve_old;
1666 bool move_to_collector = _partitions.available_in(ShenandoahFreeSetPartitionId::Collector) < to_reserve;
1667
1668 if (!move_to_collector && !move_to_old_collector) {
1669 // We've satisfied both to_reserve and to_reserved_old
1670 break;
1671 }
1672
1673 if (move_to_old_collector) {
1674 // We give priority to OldCollector partition because we desire to pack OldCollector regions into higher
1675 // addresses than Collector regions. Presumably, OldCollector regions are more "stable" and less likely to
1676 // be collected in the near future.
1677 if (r->is_trash() || !r->is_affiliated()) {
1678 // OLD regions that have available memory are already in the old_collector free set.
1679 _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
1680 ShenandoahFreeSetPartitionId::OldCollector, ac);
1681 log_debug(gc)(" Shifting region " SIZE_FORMAT " from mutator_free to old_collector_free", idx);
1682 log_debug(gc)(" Shifted Mutator range [" SSIZE_FORMAT ", " SSIZE_FORMAT "],"
1683 " Old Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT "]",
1684 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
1685 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
1686 _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector),
1687 _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector));
1688 old_region_count++;
1689 continue;
1690 }
1691 }
1692
1693 if (move_to_collector) {
1694 // Note: In a previous implementation, regions were only placed into the survivor space (collector_is_free) if
1695 // they were entirely empty. This has the effect of causing new Mutator allocation to reside next to objects
1696 // that have already survived at least one GC, mixing ephemeral with longer-lived objects in the same region.
1697 // Any objects that have survived a GC are less likely to immediately become garbage, so a region that contains
1698 // survivor objects is less likely to be selected for the collection set. This alternative implementation allows
1699 // survivor regions to continue accumulating other survivor objects, and makes it more likely that ephemeral objects
1700 // occupy regions comprised entirely of ephemeral objects. These regions are highly likely to be included in the next
1701 // collection set, and they are easily evacuated because they have low density of live objects.
1702 _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
1703 ShenandoahFreeSetPartitionId::Collector, ac);
1704 log_debug(gc)(" Shifting region " SIZE_FORMAT " from mutator_free to collector_free", idx);
1705 log_debug(gc)(" Shifted Mutator range [" SSIZE_FORMAT ", " SSIZE_FORMAT "],"
1706 " Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT "]",
1707 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
1708 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
1709 _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector),
1710 _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector));
1711 }
1712 }
1713
1714 if (LogTarget(Info, gc, free)::is_enabled()) {
1715 size_t old_reserve = _partitions.capacity_of(ShenandoahFreeSetPartitionId::OldCollector);
1716 if (old_reserve < to_reserve_old) {
1717 log_info(gc, free)("Wanted " PROPERFMT " for old reserve, but only reserved: " PROPERFMT,
1718 PROPERFMTARGS(to_reserve_old), PROPERFMTARGS(old_reserve));
1719 }
1720 size_t reserve = _partitions.capacity_of(ShenandoahFreeSetPartitionId::Collector);
1721 if (reserve < to_reserve) {
1722 log_debug(gc)("Wanted " PROPERFMT " for young reserve, but only reserved: " PROPERFMT,
1723 PROPERFMTARGS(to_reserve), PROPERFMTARGS(reserve));
1724 }
1725 }
1726 }
1727
1728 void ShenandoahFreeSet::establish_old_collector_alloc_bias() {
1729 ShenandoahHeap* heap = ShenandoahHeap::heap();
1730 shenandoah_assert_heaplocked();
1731
1732 idx_t left_idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector);
1733 idx_t right_idx = _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector);
1734 idx_t middle = (left_idx + right_idx) / 2;
1735 size_t available_in_first_half = 0;
1736 size_t available_in_second_half = 0;
1737
1738 for (idx_t index = left_idx; index < middle; index++) {
1739 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, index)) {
1740 ShenandoahHeapRegion* r = heap->get_region((size_t) index);
1741 available_in_first_half += r->free();
1742 }
1743 }
1744 for (idx_t index = middle; index <= right_idx; index++) {
1745 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, index)) {
1746 ShenandoahHeapRegion* r = heap->get_region(index);
1747 available_in_second_half += r->free();
1748 }
1749 }
1750
1751 // We desire to first consume the sparsely distributed regions in order that the remaining regions are densely packed.
1752 // Densely packing regions reduces the effort to search for a region that has sufficient memory to satisfy a new allocation
1753 // request. Regions become sparsely distributed following a Full GC, which tends to slide all regions to the front of the
1754 // heap rather than allowing survivor regions to remain at the high end of the heap where we intend for them to congregate.
1755
1756 // TODO: In the future, we may modify Full GC so that it slides old objects to the end of the heap and young objects to the
1757 // front of the heap. If this is done, we can always search survivor Collector and OldCollector regions right to left.
1758 _partitions.set_bias_from_left_to_right(ShenandoahFreeSetPartitionId::OldCollector,
1759 (available_in_second_half > available_in_first_half));
1760 }
1761
1762 void ShenandoahFreeSet::log_status_under_lock() {
1763 // Must not be heap locked, it acquires heap lock only when log is enabled
1764 shenandoah_assert_not_heaplocked();
1765 if (LogTarget(Info, gc, free)::is_enabled()
1766 DEBUG_ONLY(|| LogTarget(Debug, gc, free)::is_enabled())) {
1767 ShenandoahHeapLocker locker(_heap->lock());
1768 log_status();
1769 }
1770 }
1771
1772 void ShenandoahFreeSet::log_status() {
1773 shenandoah_assert_heaplocked();
1774
1775 #ifdef ASSERT
1776 // Dump of the FreeSet details is only enabled if assertions are enabled
1777 if (LogTarget(Debug, gc, free)::is_enabled()) {
1778 #define BUFFER_SIZE 80
1779 size_t retired_old = 0;
1780 size_t retired_old_humongous = 0;
1781 size_t retired_young = 0;
1782 size_t retired_young_humongous = 0;
1783 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1784 size_t retired_young_waste = 0;
1785 size_t retired_old_waste = 0;
1786 size_t consumed_collector = 0;
1787 size_t consumed_old_collector = 0;
1788 size_t consumed_mutator = 0;
1789 size_t available_old = 0;
1790 size_t available_young = 0;
1791 size_t available_mutator = 0;
1792 size_t available_collector = 0;
1793 size_t available_old_collector = 0;
1794
1795 char buffer[BUFFER_SIZE];
1796 for (uint i = 0; i < BUFFER_SIZE; i++) {
1797 buffer[i] = '\0';
1798 }
1799
1800 log_debug(gc)("FreeSet map legend:"
1801 " M:mutator_free C:collector_free O:old_collector_free"
1802 " H:humongous ~:retired old _:retired young");
1803 log_debug(gc)(" mutator free range [" SIZE_FORMAT ".." SIZE_FORMAT "] allocating from %s, "
1804 " collector free range [" SIZE_FORMAT ".." SIZE_FORMAT "], "
1805 "old collector free range [" SIZE_FORMAT ".." SIZE_FORMAT "] allocates from %s",
1806 _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
1807 _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
1808 _partitions.alloc_from_left_bias(ShenandoahFreeSetPartitionId::Mutator)? "left to right": "right to left",
1809 _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector),
1810 _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector),
1811 _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector),
1812 _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector),
1813 _partitions.alloc_from_left_bias(ShenandoahFreeSetPartitionId::OldCollector)? "left to right": "right to left");
1814
1815 for (uint i = 0; i < _heap->num_regions(); i++) {
1816 ShenandoahHeapRegion *r = _heap->get_region(i);
1817 uint idx = i % 64;
1818 if ((i != 0) && (idx == 0)) {
1819 log_debug(gc)(" %6u: %s", i-64, buffer);
1820 }
1821 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, i)) {
1822 size_t capacity = alloc_capacity(r);
1823 assert(!r->is_old() || r->is_trash(), "Old regions except trash regions should not be in mutator_free set");
1824 available_mutator += capacity;
1825 consumed_mutator += region_size_bytes - capacity;
1826 buffer[idx] = (capacity == region_size_bytes)? 'M': 'm';
1827 } else if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, i)) {
1828 size_t capacity = alloc_capacity(r);
1829 assert(!r->is_old() || r->is_trash(), "Old regions except trash regions should not be in collector_free set");
1830 available_collector += capacity;
1831 consumed_collector += region_size_bytes - capacity;
1832 buffer[idx] = (capacity == region_size_bytes)? 'C': 'c';
1833 } else if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, i)) {
1834 size_t capacity = alloc_capacity(r);
1835 available_old_collector += capacity;
1836 consumed_old_collector += region_size_bytes - capacity;
1837 buffer[idx] = (capacity == region_size_bytes)? 'O': 'o';
1838 } else if (r->is_humongous()) {
1839 if (r->is_old()) {
1840 buffer[idx] = 'H';
1841 retired_old_humongous += region_size_bytes;
1842 } else {
1843 buffer[idx] = 'h';
1844 retired_young_humongous += region_size_bytes;
1845 }
1846 } else {
1847 if (r->is_old()) {
1848 buffer[idx] = '~';
1849 retired_old_waste += alloc_capacity(r);
1850 retired_old += region_size_bytes;
1851 } else {
1852 buffer[idx] = '_';
1853 retired_young_waste += alloc_capacity(r);
1854 retired_young += region_size_bytes;
1855 }
1856 }
1857 }
1858 uint remnant = _heap->num_regions() % 64;
1859 if (remnant > 0) {
1860 buffer[remnant] = '\0';
1861 } else {
1862 remnant = 64;
1863 }
1864 log_debug(gc)(" %6u: %s", (uint) (_heap->num_regions() - remnant), buffer);
1865 }
1866 #endif
1867
1868 LogTarget(Info, gc, free) lt;
1869 if (lt.is_enabled()) {
1870 ResourceMark rm;
1871 LogStream ls(lt);
1872
1873 {
1874 idx_t last_idx = 0;
1875 size_t max = 0;
1876 size_t max_contig = 0;
1877 size_t empty_contig = 0;
1878
1879 size_t total_used = 0;
1880 size_t total_free = 0;
1881 size_t total_free_ext = 0;
1882
1883 for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator);
1884 idx <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator); idx++) {
1885 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx)) {
1886 ShenandoahHeapRegion *r = _heap->get_region(idx);
1887 size_t free = alloc_capacity(r);
1888 max = MAX2(max, free);
1889 if (r->is_empty()) {
1890 total_free_ext += free;
1891 if (last_idx + 1 == idx) {
1892 empty_contig++;
1893 } else {
1894 empty_contig = 1;
1895 }
1896 } else {
1897 empty_contig = 0;
1898 }
1899 total_used += r->used();
1900 total_free += free;
1901 max_contig = MAX2(max_contig, empty_contig);
1902 last_idx = idx;
1903 }
1904 }
1905
1906 size_t max_humongous = max_contig * ShenandoahHeapRegion::region_size_bytes();
1907 size_t free = capacity() - used();
1908
1909 // Since certain regions that belonged to the Mutator free partition at the time of most recent rebuild may have been
1910 // retired, the sum of used and capacities within regions that are still in the Mutator free partition may not match
1911 // my internally tracked values of used() and free().
1912 assert(free == total_free, "Free memory should match");
1913 ls.print("Free: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s regular, " SIZE_FORMAT "%s humongous, ",
1914 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
1915 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max),
1916 byte_size_in_proper_unit(max_humongous), proper_unit_for_byte_size(max_humongous)
1917 );
1918
1919 ls.print("Frag: ");
1920 size_t frag_ext;
1921 if (total_free_ext > 0) {
1922 frag_ext = 100 - (100 * max_humongous / total_free_ext);
1923 } else {
1924 frag_ext = 0;
1925 }
1926 ls.print(SIZE_FORMAT "%% external, ", frag_ext);
1927
1928 size_t frag_int;
1929 if (_partitions.count(ShenandoahFreeSetPartitionId::Mutator) > 0) {
1930 frag_int = (100 * (total_used / _partitions.count(ShenandoahFreeSetPartitionId::Mutator))
1931 / ShenandoahHeapRegion::region_size_bytes());
1932 } else {
1933 frag_int = 0;
1934 }
1935 ls.print(SIZE_FORMAT "%% internal; ", frag_int);
1936 ls.print("Used: " SIZE_FORMAT "%s, Mutator Free: " SIZE_FORMAT,
1937 byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used),
1938 _partitions.count(ShenandoahFreeSetPartitionId::Mutator));
1939 }
1940
1941 {
1942 size_t max = 0;
1943 size_t total_free = 0;
1944 size_t total_used = 0;
1945
1946 for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector);
1947 idx <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector); idx++) {
1948 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, idx)) {
1949 ShenandoahHeapRegion *r = _heap->get_region(idx);
1950 size_t free = alloc_capacity(r);
1951 max = MAX2(max, free);
1952 total_free += free;
1953 total_used += r->used();
1954 }
1955 }
1956 ls.print(" Collector Reserve: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s; Used: " SIZE_FORMAT "%s",
1957 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
1958 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max),
1959 byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used));
1960 }
1961
1962 if (_heap->mode()->is_generational()) {
1963 size_t max = 0;
1964 size_t total_free = 0;
1965 size_t total_used = 0;
1966
1967 for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector);
1968 idx <= _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector); idx++) {
1969 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, idx)) {
1970 ShenandoahHeapRegion *r = _heap->get_region(idx);
1971 size_t free = alloc_capacity(r);
1972 max = MAX2(max, free);
1973 total_free += free;
1974 total_used += r->used();
1975 }
1976 }
1977 ls.print_cr(" Old Collector Reserve: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s; Used: " SIZE_FORMAT "%s",
1978 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
1979 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max),
1980 byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used));
1981 }
1982 }
1983 }
1984
1985 HeapWord* ShenandoahFreeSet::allocate(ShenandoahAllocRequest& req, bool& in_new_region) {
1986 shenandoah_assert_heaplocked();
1987 if (req.size() > ShenandoahHeapRegion::humongous_threshold_words()) {
1988 switch (req.type()) {
1989 case ShenandoahAllocRequest::_alloc_shared:
1990 case ShenandoahAllocRequest::_alloc_shared_gc:
1991 in_new_region = true;
1992 return allocate_contiguous(req);
1993 case ShenandoahAllocRequest::_alloc_plab:
1994 case ShenandoahAllocRequest::_alloc_gclab:
1995 case ShenandoahAllocRequest::_alloc_tlab:
1996 in_new_region = false;
1997 assert(false, "Trying to allocate TLAB larger than the humongous threshold: " SIZE_FORMAT " > " SIZE_FORMAT,
1998 req.size(), ShenandoahHeapRegion::humongous_threshold_words());
1999 return nullptr;
2000 default:
2001 ShouldNotReachHere();
2002 return nullptr;
2003 }
2004 } else {
2005 return allocate_single(req, in_new_region);
2006 }
2007 }
2008
2009 void ShenandoahFreeSet::print_on(outputStream* out) const {
2010 out->print_cr("Mutator Free Set: " SIZE_FORMAT "", _partitions.count(ShenandoahFreeSetPartitionId::Mutator));
2011 idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
2012 for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); index <= rightmost; ) {
2013 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, index),
2014 "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
2015 _heap->get_region(index)->print_on(out);
2016 index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, index + 1);
2017 }
2018 out->print_cr("Collector Free Set: " SIZE_FORMAT "", _partitions.count(ShenandoahFreeSetPartitionId::Collector));
2019 rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector);
2020 for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector); index <= rightmost; ) {
2021 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, index),
2022 "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
2023 _heap->get_region(index)->print_on(out);
2024 index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Collector, index + 1);
2025 }
2026 if (_heap->mode()->is_generational()) {
2027 out->print_cr("Old Collector Free Set: " SIZE_FORMAT "", _partitions.count(ShenandoahFreeSetPartitionId::OldCollector));
2028 for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::OldCollector);
2029 index <= _partitions.rightmost(ShenandoahFreeSetPartitionId::OldCollector); index++) {
2030 if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::OldCollector, index)) {
2031 _heap->get_region(index)->print_on(out);
2032 }
2033 }
2034 }
2035 }
2036
2037 double ShenandoahFreeSet::internal_fragmentation() {
2038 double squared = 0;
2039 double linear = 0;
2040
2041 idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
2042 for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); index <= rightmost; ) {
2043 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, index),
2044 "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
2045 ShenandoahHeapRegion* r = _heap->get_region(index);
2046 size_t used = r->used();
2047 squared += used * used;
2048 linear += used;
2049 index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, index + 1);
2050 }
2051
2052 if (linear > 0) {
2053 double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear);
2054 return 1 - s;
2055 } else {
2056 return 0;
2057 }
2058 }
2059
2060 double ShenandoahFreeSet::external_fragmentation() {
2061 idx_t last_idx = 0;
2062 size_t max_contig = 0;
2063 size_t empty_contig = 0;
2064
2065 size_t free = 0;
2066
2067 idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
2068 for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); index <= rightmost; ) {
2069 assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, index),
2070 "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
2071 ShenandoahHeapRegion* r = _heap->get_region(index);
2072 if (r->is_empty()) {
2073 free += ShenandoahHeapRegion::region_size_bytes();
2074 if (last_idx + 1 == index) {
2075 empty_contig++;
2076 } else {
2077 empty_contig = 1;
2078 }
2079 } else {
2080 empty_contig = 0;
2081 }
2082 max_contig = MAX2(max_contig, empty_contig);
2083 last_idx = index;
2084 index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, index + 1);
2085 }
2086
2087 if (free > 0) {
2088 return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free);
2089 } else {
2090 return 0;
2091 }
2092 }
2093