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/shenandoahFreeSet.hpp"
  29 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
  30 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
  31 #include "gc/shenandoah/shenandoahMarkingContext.inline.hpp"
  32 #include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
  33 #include "gc/shenandoah/shenandoahSimpleBitMap.inline.hpp"
  34 #include "logging/logStream.hpp"
  35 #include "memory/resourceArea.hpp"
  36 #include "runtime/orderAccess.hpp"
  37 
  38 static const char* partition_name(ShenandoahFreeSetPartitionId t) {
  39   switch (t) {
  40     case ShenandoahFreeSetPartitionId::NotFree: return "NotFree";
  41     case ShenandoahFreeSetPartitionId::Mutator: return "Mutator";
  42     case ShenandoahFreeSetPartitionId::Collector: return "Collector";
  43     default:
  44       ShouldNotReachHere();
  45       return "Unrecognized";
  46   }
  47 }
  48 
  49 #ifndef PRODUCT
  50 void ShenandoahRegionPartitions::dump_bitmap() const {
  51   log_info(gc)("Mutator range [" SSIZE_FORMAT ", " SSIZE_FORMAT "], Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT "]",
  52                _leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)],
  53                _rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)],
  54                _leftmosts[int(ShenandoahFreeSetPartitionId::Collector)],
  55                _rightmosts[int(ShenandoahFreeSetPartitionId::Collector)]);
  56   log_info(gc)("Empty Mutator range [" SSIZE_FORMAT ", " SSIZE_FORMAT
  57                "], Empty Collector range [" SSIZE_FORMAT ", " SSIZE_FORMAT "]",
  58                _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
  59                _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)],
  60                _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
  61                _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)]);
  62 
  63   log_info(gc)("%6s: %18s %18s %18s", "index", "Mutator Bits", "Collector Bits", "NotFree Bits");
  64   dump_bitmap_range(0, _max-1);
  65 }
  66 
  67 void ShenandoahRegionPartitions::dump_bitmap_range(idx_t start_region_idx, idx_t end_region_idx) const {
  68   assert((start_region_idx >= 0) && (start_region_idx < (idx_t) _max), "precondition");
  69   assert((end_region_idx >= 0) && (end_region_idx < (idx_t) _max), "precondition");
  70   idx_t aligned_start = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(start_region_idx);
  71   idx_t aligned_end = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(end_region_idx);
  72   idx_t alignment = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].alignment();
  73   while (aligned_start <= aligned_end) {
  74     dump_bitmap_row(aligned_start);
  75     aligned_start += alignment;
  76   }
  77 }
  78 
  79 void ShenandoahRegionPartitions::dump_bitmap_row(idx_t region_idx) const {
  80   assert((region_idx >= 0) && (region_idx < (idx_t) _max), "precondition");
  81   idx_t aligned_idx = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].aligned_index(region_idx);
  82   uintx mutator_bits = _membership[int(ShenandoahFreeSetPartitionId::Mutator)].bits_at(aligned_idx);
  83   uintx collector_bits = _membership[int(ShenandoahFreeSetPartitionId::Collector)].bits_at(aligned_idx);
  84   uintx free_bits = mutator_bits | collector_bits;
  85   uintx notfree_bits =  ~free_bits;
  86   log_info(gc)(SSIZE_FORMAT_W(6) ": " SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0 " 0x" SIZE_FORMAT_X_0,
  87                aligned_idx, mutator_bits, collector_bits, notfree_bits);
  88 }
  89 #endif
  90 
  91 ShenandoahRegionPartitions::ShenandoahRegionPartitions(size_t max_regions, ShenandoahFreeSet* free_set) :
  92     _max(max_regions),
  93     _region_size_bytes(ShenandoahHeapRegion::region_size_bytes()),
  94     _free_set(free_set),
  95     _membership{ ShenandoahSimpleBitMap(max_regions), ShenandoahSimpleBitMap(max_regions) }
  96 {
  97   make_all_regions_unavailable();
  98 }
  99 
 100 inline bool ShenandoahFreeSet::can_allocate_from(ShenandoahHeapRegion *r) const {
 101   return r->is_empty() || (r->is_trash() && !_heap->is_concurrent_weak_root_in_progress());
 102 }
 103 
 104 inline bool ShenandoahFreeSet::can_allocate_from(size_t idx) const {
 105   ShenandoahHeapRegion* r = _heap->get_region(idx);
 106   return can_allocate_from(r);
 107 }
 108 
 109 inline size_t ShenandoahFreeSet::alloc_capacity(ShenandoahHeapRegion *r) const {
 110   if (r->is_trash()) {
 111     // This would be recycled on allocation path
 112     return ShenandoahHeapRegion::region_size_bytes();
 113   } else {
 114     return r->free();
 115   }
 116 }
 117 
 118 inline size_t ShenandoahFreeSet::alloc_capacity(size_t idx) const {
 119   ShenandoahHeapRegion* r = _heap->get_region(idx);
 120   return alloc_capacity(r);
 121 }
 122 
 123 inline bool ShenandoahFreeSet::has_alloc_capacity(ShenandoahHeapRegion *r) const {
 124   return alloc_capacity(r) > 0;
 125 }
 126 
 127 inline idx_t ShenandoahRegionPartitions::leftmost(ShenandoahFreeSetPartitionId which_partition) const {
 128   assert (which_partition < NumPartitions, "selected free partition must be valid");
 129   idx_t idx = _leftmosts[int(which_partition)];
 130   if (idx >= _max) {
 131     return _max;
 132   } else {
 133     // Cannot assert that membership[which_partition.is_set(idx) because this helper method may be used
 134     // to query the original value of leftmost when leftmost must be adjusted because the interval representing
 135     // which_partition is shrinking after the region that used to be leftmost is retired.
 136     return idx;
 137   }
 138 }
 139 
 140 inline idx_t ShenandoahRegionPartitions::rightmost(ShenandoahFreeSetPartitionId which_partition) const {
 141   assert (which_partition < NumPartitions, "selected free partition must be valid");
 142   idx_t idx = _rightmosts[int(which_partition)];
 143   // Cannot assert that membership[which_partition.is_set(idx) because this helper method may be used
 144   // to query the original value of leftmost when leftmost must be adjusted because the interval representing
 145   // which_partition is shrinking after the region that used to be leftmost is retired.
 146   return idx;
 147 }
 148 
 149 void ShenandoahRegionPartitions::make_all_regions_unavailable() {
 150   for (size_t partition_id = 0; partition_id < IntNumPartitions; partition_id++) {
 151     _membership[partition_id].clear_all();
 152     _leftmosts[partition_id] = _max;
 153     _rightmosts[partition_id] = -1;
 154     _leftmosts_empty[partition_id] = _max;
 155     _rightmosts_empty[partition_id] = -1;;
 156     _capacity[partition_id] = 0;
 157     _used[partition_id] = 0;
 158   }
 159   _region_counts[int(ShenandoahFreeSetPartitionId::Mutator)] = _region_counts[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
 160 }
 161 
 162 void ShenandoahRegionPartitions::establish_mutator_intervals(idx_t mutator_leftmost, idx_t mutator_rightmost,
 163                                                              idx_t mutator_leftmost_empty, idx_t mutator_rightmost_empty,
 164                                                              size_t mutator_region_count, size_t mutator_used) {
 165   _region_counts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_region_count;
 166   _leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_leftmost;
 167   _rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_rightmost;
 168   _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_leftmost_empty;
 169   _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_rightmost_empty;
 170 
 171   _region_counts[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_region_count;
 172   _used[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_used;
 173   _capacity[int(ShenandoahFreeSetPartitionId::Mutator)] = mutator_region_count * _region_size_bytes;
 174 
 175   _leftmosts[int(ShenandoahFreeSetPartitionId::Collector)] = _max;
 176   _rightmosts[int(ShenandoahFreeSetPartitionId::Collector)] = -1;
 177   _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)] = _max;
 178   _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)] = -1;
 179 
 180   _region_counts[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
 181   _used[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
 182   _capacity[int(ShenandoahFreeSetPartitionId::Collector)] = 0;
 183 }
 184 
 185 void ShenandoahRegionPartitions::increase_used(ShenandoahFreeSetPartitionId which_partition, size_t bytes) {
 186   assert (which_partition < NumPartitions, "Partition must be valid");
 187   _used[int(which_partition)] += bytes;
 188   assert (_used[int(which_partition)] <= _capacity[int(which_partition)],
 189           "Must not use (" SIZE_FORMAT ") more than capacity (" SIZE_FORMAT ") after increase by " SIZE_FORMAT,
 190           _used[int(which_partition)], _capacity[int(which_partition)], bytes);
 191 }
 192 
 193 inline void ShenandoahRegionPartitions::shrink_interval_if_range_modifies_either_boundary(
 194   ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx) {
 195   assert((low_idx <= high_idx) && (low_idx >= 0) && (high_idx < _max), "Range must span legal index values");
 196   if (low_idx == leftmost(partition)) {
 197     assert (!_membership[int(partition)].is_set(low_idx), "Do not shrink interval if region not removed");
 198     if (high_idx + 1 == _max) {
 199       _leftmosts[int(partition)] = _max;
 200     } else {
 201       _leftmosts[int(partition)] = find_index_of_next_available_region(partition, high_idx + 1);
 202     }
 203     if (_leftmosts_empty[int(partition)] < _leftmosts[int(partition)]) {
 204       // This gets us closer to where we need to be; we'll scan further when leftmosts_empty is requested.
 205       _leftmosts_empty[int(partition)] = leftmost(partition);
 206     }
 207   }
 208   if (high_idx == _rightmosts[int(partition)]) {
 209     assert (!_membership[int(partition)].is_set(high_idx), "Do not shrink interval if region not removed");
 210     if (low_idx == 0) {
 211       _rightmosts[int(partition)] = -1;
 212     } else {
 213       _rightmosts[int(partition)] = find_index_of_previous_available_region(partition, low_idx - 1);
 214     }
 215     if (_rightmosts_empty[int(partition)] > _rightmosts[int(partition)]) {
 216       // This gets us closer to where we need to be; we'll scan further when rightmosts_empty is requested.
 217       _rightmosts_empty[int(partition)] = _rightmosts[int(partition)];
 218     }
 219   }
 220   if (_leftmosts[int(partition)] > _rightmosts[int(partition)]) {
 221     _leftmosts[int(partition)] = _max;
 222     _rightmosts[int(partition)] = -1;
 223     _leftmosts_empty[int(partition)] = _max;
 224     _rightmosts_empty[int(partition)] = -1;
 225   }
 226 }
 227 
 228 inline void ShenandoahRegionPartitions::shrink_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition, idx_t idx) {
 229   shrink_interval_if_range_modifies_either_boundary(partition, idx, idx);
 230 }
 231 
 232 inline void ShenandoahRegionPartitions::expand_interval_if_boundary_modified(ShenandoahFreeSetPartitionId partition,
 233                                                                              idx_t idx, size_t region_available) {
 234   if (_leftmosts[int(partition)] > idx) {
 235     _leftmosts[int(partition)] = idx;
 236   }
 237   if (_rightmosts[int(partition)] < idx) {
 238     _rightmosts[int(partition)] = idx;
 239   }
 240   if (region_available == _region_size_bytes) {
 241     if (_leftmosts_empty[int(partition)] > idx) {
 242       _leftmosts_empty[int(partition)] = idx;
 243     }
 244     if (_rightmosts_empty[int(partition)] < idx) {
 245       _rightmosts_empty[int(partition)] = idx;
 246     }
 247   }
 248 }
 249 
 250 void ShenandoahRegionPartitions::retire_range_from_partition(
 251   ShenandoahFreeSetPartitionId partition, idx_t low_idx, idx_t high_idx) {
 252 
 253   // Note: we may remove from free partition even if region is not entirely full, such as when available < PLAB::min_size()
 254   assert ((low_idx < _max) && (high_idx < _max), "Both indices are sane: " SIZE_FORMAT " and " SIZE_FORMAT " < " SIZE_FORMAT,
 255           low_idx, high_idx, _max);
 256   assert (partition < NumPartitions, "Cannot remove from free partitions if not already free");
 257 
 258   for (idx_t idx = low_idx; idx <= high_idx; idx++) {
 259     assert (in_free_set(partition, idx), "Must be in partition to remove from partition");
 260     _membership[int(partition)].clear_bit(idx);
 261   }
 262   _region_counts[int(partition)] -= high_idx + 1 - low_idx;
 263   shrink_interval_if_range_modifies_either_boundary(partition, low_idx, high_idx);
 264 }
 265 
 266 void ShenandoahRegionPartitions::retire_from_partition(ShenandoahFreeSetPartitionId partition, idx_t idx, size_t used_bytes) {
 267 
 268   // Note: we may remove from free partition even if region is not entirely full, such as when available < PLAB::min_size()
 269   assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
 270   assert (partition < NumPartitions, "Cannot remove from free partitions if not already free");
 271   assert (in_free_set(partition, idx), "Must be in partition to remove from partition");
 272 
 273   if (used_bytes < _region_size_bytes) {
 274     // Count the alignment pad remnant of memory as used when we retire this region
 275     increase_used(partition, _region_size_bytes - used_bytes);
 276   }
 277   _membership[int(partition)].clear_bit(idx);
 278   shrink_interval_if_boundary_modified(partition, idx);
 279   _region_counts[int(partition)]--;
 280 }
 281 
 282 void ShenandoahRegionPartitions::make_free(idx_t idx, ShenandoahFreeSetPartitionId which_partition, size_t available) {
 283   assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
 284   assert (membership(idx) == ShenandoahFreeSetPartitionId::NotFree, "Cannot make free if already free");
 285   assert (which_partition < NumPartitions, "selected free partition must be valid");
 286   assert (available <= _region_size_bytes, "Available cannot exceed region size");
 287 
 288   _membership[int(which_partition)].set_bit(idx);
 289   _capacity[int(which_partition)] += _region_size_bytes;
 290   _used[int(which_partition)] += _region_size_bytes - available;
 291   expand_interval_if_boundary_modified(which_partition, idx, available);
 292 
 293   _region_counts[int(which_partition)]++;
 294 }
 295 
 296 void ShenandoahRegionPartitions::move_from_partition_to_partition(idx_t idx, ShenandoahFreeSetPartitionId orig_partition,
 297                                                                   ShenandoahFreeSetPartitionId new_partition, size_t available) {
 298   assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
 299   assert (orig_partition < NumPartitions, "Original partition must be valid");
 300   assert (new_partition < NumPartitions, "New partition must be valid");
 301   assert (available <= _region_size_bytes, "Available cannot exceed region size");
 302 
 303   // Expected transitions:
 304   //  During rebuild:         Mutator => Collector
 305   //  During flip_to_gc:      Mutator empty => Collector
 306   // At start of update refs: Collector => Mutator
 307   assert (((available <= _region_size_bytes) &&
 308            (((orig_partition == ShenandoahFreeSetPartitionId::Mutator)
 309              && (new_partition == ShenandoahFreeSetPartitionId::Collector)) ||
 310             ((orig_partition == ShenandoahFreeSetPartitionId::Collector)
 311              && (new_partition == ShenandoahFreeSetPartitionId::Mutator)))) ||
 312           ((available == _region_size_bytes) &&
 313            ((orig_partition == ShenandoahFreeSetPartitionId::Mutator)
 314             && (new_partition == ShenandoahFreeSetPartitionId::Collector))), "Unexpected movement between partitions");
 315 
 316   size_t used = _region_size_bytes - available;
 317 
 318   _membership[int(orig_partition)].clear_bit(idx);
 319   _membership[int(new_partition)].set_bit(idx);
 320 
 321   _capacity[int(orig_partition)] -= _region_size_bytes;
 322   _used[int(orig_partition)] -= used;
 323   shrink_interval_if_boundary_modified(orig_partition, idx);
 324 
 325   _capacity[int(new_partition)] += _region_size_bytes;;
 326   _used[int(new_partition)] += used;
 327   expand_interval_if_boundary_modified(new_partition, idx, available);
 328 
 329   _region_counts[int(orig_partition)]--;
 330   _region_counts[int(new_partition)]++;
 331 }
 332 
 333 const char* ShenandoahRegionPartitions::partition_membership_name(idx_t idx) const {
 334   return partition_name(membership(idx));
 335 }
 336 
 337 inline ShenandoahFreeSetPartitionId ShenandoahRegionPartitions::membership(idx_t idx) const {
 338   assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
 339   ShenandoahFreeSetPartitionId result = ShenandoahFreeSetPartitionId::NotFree;
 340   for (uint partition_id = 0; partition_id < UIntNumPartitions; partition_id++) {
 341     if (_membership[partition_id].is_set(idx)) {
 342       assert(result == ShenandoahFreeSetPartitionId::NotFree, "Region should reside in only one partition");
 343       result = (ShenandoahFreeSetPartitionId) partition_id;
 344     }
 345   }
 346   return result;
 347 }
 348 
 349 #ifdef ASSERT
 350 inline bool ShenandoahRegionPartitions::partition_id_matches(idx_t idx, ShenandoahFreeSetPartitionId test_partition) const {
 351   assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max);
 352   assert (test_partition < ShenandoahFreeSetPartitionId::NotFree, "must be a valid partition");
 353 
 354   return membership(idx) == test_partition;
 355 }
 356 #endif
 357 
 358 inline bool ShenandoahRegionPartitions::is_empty(ShenandoahFreeSetPartitionId which_partition) const {
 359   assert (which_partition < NumPartitions, "selected free partition must be valid");
 360   return (leftmost(which_partition) > rightmost(which_partition));
 361 }
 362 
 363 inline idx_t ShenandoahRegionPartitions::find_index_of_next_available_region(
 364   ShenandoahFreeSetPartitionId which_partition, idx_t start_index) const {
 365   idx_t rightmost_idx = rightmost(which_partition);
 366   idx_t leftmost_idx = leftmost(which_partition);
 367   if ((rightmost_idx < leftmost_idx) || (start_index > rightmost_idx)) return _max;
 368   if (start_index < leftmost_idx) {
 369     start_index = leftmost_idx;
 370   }
 371   idx_t result = _membership[int(which_partition)].find_first_set_bit(start_index, rightmost_idx + 1);
 372   if (result > rightmost_idx) {
 373     result = _max;
 374   }
 375   assert (result >= start_index, "Requires progress");
 376   return result;
 377 }
 378 
 379 inline idx_t ShenandoahRegionPartitions::find_index_of_previous_available_region(
 380   ShenandoahFreeSetPartitionId which_partition, idx_t last_index) const {
 381   idx_t rightmost_idx = rightmost(which_partition);
 382   idx_t leftmost_idx = leftmost(which_partition);
 383   // if (leftmost_idx == max) then (last_index < leftmost_idx)
 384   if (last_index < leftmost_idx) return -1;
 385   if (last_index > rightmost_idx) {
 386     last_index = rightmost_idx;
 387   }
 388   idx_t result = _membership[int(which_partition)].find_last_set_bit(-1, last_index);
 389   if (result < leftmost_idx) {
 390     result = -1;
 391   }
 392   assert (result <= last_index, "Requires progress");
 393   return result;
 394 }
 395 
 396 inline idx_t ShenandoahRegionPartitions::find_index_of_next_available_cluster_of_regions(
 397   ShenandoahFreeSetPartitionId which_partition, idx_t start_index, size_t cluster_size) const {
 398   idx_t rightmost_idx = rightmost(which_partition);
 399   idx_t leftmost_idx = leftmost(which_partition);
 400   if ((rightmost_idx < leftmost_idx) || (start_index > rightmost_idx)) return _max;
 401   idx_t result = _membership[int(which_partition)].find_first_consecutive_set_bits(start_index, rightmost_idx + 1, cluster_size);
 402   if (result > rightmost_idx) {
 403     result = _max;
 404   }
 405   assert (result >= start_index, "Requires progress");
 406   return result;
 407 }
 408 
 409 inline idx_t ShenandoahRegionPartitions::find_index_of_previous_available_cluster_of_regions(
 410   ShenandoahFreeSetPartitionId which_partition, idx_t last_index, size_t cluster_size) const {
 411   idx_t leftmost_idx = leftmost(which_partition);
 412   // if (leftmost_idx == max) then (last_index < leftmost_idx)
 413   if (last_index < leftmost_idx) return -1;
 414   idx_t result = _membership[int(which_partition)].find_last_consecutive_set_bits(leftmost_idx - 1, last_index, cluster_size);
 415   if (result <= leftmost_idx) {
 416     result = -1;
 417   }
 418   assert (result <= last_index, "Requires progress");
 419   return result;
 420 }
 421 
 422 idx_t ShenandoahRegionPartitions::leftmost_empty(ShenandoahFreeSetPartitionId which_partition) {
 423   assert (which_partition < NumPartitions, "selected free partition must be valid");
 424   idx_t max_regions = _max;
 425   if (_leftmosts_empty[int(which_partition)] == _max) {
 426     return _max;
 427   }
 428   for (idx_t idx = find_index_of_next_available_region(which_partition, _leftmosts_empty[int(which_partition)]);
 429        idx < max_regions; ) {
 430     assert(in_free_set(which_partition, idx), "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
 431     if (_free_set->alloc_capacity(idx) == _region_size_bytes) {
 432       _leftmosts_empty[int(which_partition)] = idx;
 433       return idx;
 434     }
 435     idx = find_index_of_next_available_region(which_partition, idx + 1);
 436   }
 437   _leftmosts_empty[int(which_partition)] = _max;
 438   _rightmosts_empty[int(which_partition)] = -1;
 439   return _max;
 440 }
 441 
 442 idx_t ShenandoahRegionPartitions::rightmost_empty(ShenandoahFreeSetPartitionId which_partition) {
 443   assert (which_partition < NumPartitions, "selected free partition must be valid");
 444   if (_rightmosts_empty[int(which_partition)] < 0) {
 445     return -1;
 446   }
 447   for (idx_t idx = find_index_of_previous_available_region(which_partition, _rightmosts_empty[int(which_partition)]);
 448        idx >= 0; ) {
 449     assert(in_free_set(which_partition, idx), "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
 450     if (_free_set->alloc_capacity(idx) == _region_size_bytes) {
 451       _rightmosts_empty[int(which_partition)] = idx;
 452       return idx;
 453     }
 454     idx = find_index_of_previous_available_region(which_partition, idx - 1);
 455   }
 456   _leftmosts_empty[int(which_partition)] = _max;
 457   _rightmosts_empty[int(which_partition)] = -1;
 458   return -1;
 459 }
 460 
 461 
 462 #ifdef ASSERT
 463 void ShenandoahRegionPartitions::assert_bounds() {
 464 
 465   idx_t leftmosts[UIntNumPartitions];
 466   idx_t rightmosts[UIntNumPartitions];
 467   idx_t empty_leftmosts[UIntNumPartitions];
 468   idx_t empty_rightmosts[UIntNumPartitions];
 469 
 470   for (uint i = 0; i < UIntNumPartitions; i++) {
 471     leftmosts[i] = _max;
 472     empty_leftmosts[i] = _max;
 473     rightmosts[i] = -1;
 474     empty_rightmosts[i] = -1;
 475   }
 476 
 477   for (idx_t i = 0; i < _max; i++) {
 478     ShenandoahFreeSetPartitionId partition = membership(i);
 479     switch (partition) {
 480       case ShenandoahFreeSetPartitionId::NotFree:
 481         break;
 482 
 483       case ShenandoahFreeSetPartitionId::Mutator:
 484       case ShenandoahFreeSetPartitionId::Collector:
 485       {
 486         size_t capacity = _free_set->alloc_capacity(i);
 487         bool is_empty = (capacity == _region_size_bytes);
 488         assert(capacity > 0, "free regions must have allocation capacity");
 489         if (i < leftmosts[int(partition)]) {
 490           leftmosts[int(partition)] = i;
 491         }
 492         if (is_empty && (i < empty_leftmosts[int(partition)])) {
 493           empty_leftmosts[int(partition)] = i;
 494         }
 495         if (i > rightmosts[int(partition)]) {
 496           rightmosts[int(partition)] = i;
 497         }
 498         if (is_empty && (i > empty_rightmosts[int(partition)])) {
 499           empty_rightmosts[int(partition)] = i;
 500         }
 501         break;
 502       }
 503 
 504       default:
 505         ShouldNotReachHere();
 506     }
 507   }
 508 
 509   // Performance invariants. Failing these would not break the free partition, but performance would suffer.
 510   assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) <= _max,
 511           "leftmost in bounds: "  SSIZE_FORMAT " < " SSIZE_FORMAT, leftmost(ShenandoahFreeSetPartitionId::Mutator),  _max);
 512   assert (rightmost(ShenandoahFreeSetPartitionId::Mutator) < _max,
 513           "rightmost in bounds: "  SSIZE_FORMAT " < " SSIZE_FORMAT, rightmost(ShenandoahFreeSetPartitionId::Mutator),  _max);
 514 
 515   assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) == _max
 516           || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::Mutator), ShenandoahFreeSetPartitionId::Mutator),
 517           "leftmost region should be free: " SSIZE_FORMAT,  leftmost(ShenandoahFreeSetPartitionId::Mutator));
 518   assert (leftmost(ShenandoahFreeSetPartitionId::Mutator) == _max
 519           || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::Mutator), ShenandoahFreeSetPartitionId::Mutator),
 520           "rightmost region should be free: " SSIZE_FORMAT, rightmost(ShenandoahFreeSetPartitionId::Mutator));
 521 
 522   // If Mutator partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
 523   // Likewise for empty region partitions.
 524   idx_t beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
 525   idx_t end_off = rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
 526   assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::Mutator),
 527           "free regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 528           beg_off, leftmost(ShenandoahFreeSetPartitionId::Mutator));
 529   assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::Mutator),
 530           "free regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 531           end_off, rightmost(ShenandoahFreeSetPartitionId::Mutator));
 532 
 533   beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
 534   end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::Mutator)];
 535   assert (beg_off >= leftmost_empty(ShenandoahFreeSetPartitionId::Mutator),
 536           "free empty regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 537           beg_off, leftmost_empty(ShenandoahFreeSetPartitionId::Mutator));
 538   assert (end_off <= rightmost_empty(ShenandoahFreeSetPartitionId::Mutator),
 539           "free empty regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 540           end_off, rightmost_empty(ShenandoahFreeSetPartitionId::Mutator));
 541 
 542   // Performance invariants. Failing these would not break the free partition, but performance would suffer.
 543   assert (leftmost(ShenandoahFreeSetPartitionId::Collector) <= _max, "leftmost in bounds: "  SSIZE_FORMAT " < " SSIZE_FORMAT,
 544           leftmost(ShenandoahFreeSetPartitionId::Collector),  _max);
 545   assert (rightmost(ShenandoahFreeSetPartitionId::Collector) < _max, "rightmost in bounds: "  SSIZE_FORMAT " < " SSIZE_FORMAT,
 546           rightmost(ShenandoahFreeSetPartitionId::Collector),  _max);
 547 
 548   assert (leftmost(ShenandoahFreeSetPartitionId::Collector) == _max
 549           || partition_id_matches(leftmost(ShenandoahFreeSetPartitionId::Collector), ShenandoahFreeSetPartitionId::Collector),
 550           "leftmost region should be free: " SSIZE_FORMAT,  leftmost(ShenandoahFreeSetPartitionId::Collector));
 551   assert (leftmost(ShenandoahFreeSetPartitionId::Collector) == _max
 552           || partition_id_matches(rightmost(ShenandoahFreeSetPartitionId::Collector), ShenandoahFreeSetPartitionId::Collector),
 553           "rightmost region should be free: " SSIZE_FORMAT, rightmost(ShenandoahFreeSetPartitionId::Collector));
 554 
 555   // If Collector partition is empty, leftmosts will both equal max, rightmosts will both equal zero.
 556   // Likewise for empty region partitions.
 557   beg_off = leftmosts[int(ShenandoahFreeSetPartitionId::Collector)];
 558   end_off = rightmosts[int(ShenandoahFreeSetPartitionId::Collector)];
 559   assert (beg_off >= leftmost(ShenandoahFreeSetPartitionId::Collector),
 560           "free regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 561           beg_off, leftmost(ShenandoahFreeSetPartitionId::Collector));
 562   assert (end_off <= rightmost(ShenandoahFreeSetPartitionId::Collector),
 563           "free regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 564           end_off, rightmost(ShenandoahFreeSetPartitionId::Collector));
 565 
 566   beg_off = empty_leftmosts[int(ShenandoahFreeSetPartitionId::Collector)];
 567   end_off = empty_rightmosts[int(ShenandoahFreeSetPartitionId::Collector)];
 568   assert (beg_off >= _leftmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
 569           "free empty regions before the leftmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 570           beg_off, leftmost_empty(ShenandoahFreeSetPartitionId::Collector));
 571   assert (end_off <= _rightmosts_empty[int(ShenandoahFreeSetPartitionId::Collector)],
 572           "free empty regions past the rightmost: " SSIZE_FORMAT ", bound " SSIZE_FORMAT,
 573           end_off, rightmost_empty(ShenandoahFreeSetPartitionId::Collector));
 574 }
 575 #endif
 576 
 577 ShenandoahFreeSet::ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions) :
 578   _heap(heap),
 579   _partitions(max_regions, this),
 580   _right_to_left_bias(false),
 581   _alloc_bias_weight(0)
 582 {
 583   clear_internal();
 584 }
 585 
 586 HeapWord* ShenandoahFreeSet::allocate_single(ShenandoahAllocRequest& req, bool& in_new_region) {
 587   shenandoah_assert_heaplocked();
 588 
 589   // Scan the bitmap looking for a first fit.
 590   //
 591   // Leftmost and rightmost bounds provide enough caching to quickly find a region from which to allocate.
 592   //
 593   // Allocations are biased: GC allocations are taken from the high end of the heap.  Regular (and TLAB)
 594   // mutator allocations are taken from the middle of heap, below the memory reserved for Collector.
 595   // Humongous mutator allocations are taken from the bottom of the heap.
 596   //
 597   // Free set maintains mutator and collector partitions.  Mutator can only allocate from the
 598   // Mutator partition.  Collector prefers to allocate from the Collector partition, but may steal
 599   // regions from the Mutator partition if the Collector partition has been depleted.
 600 
 601   switch (req.type()) {
 602     case ShenandoahAllocRequest::_alloc_tlab:
 603     case ShenandoahAllocRequest::_alloc_shared: {
 604       // Try to allocate in the mutator view
 605       if (_alloc_bias_weight-- <= 0) {
 606         // We have observed that regions not collected in previous GC cycle tend to congregate at one end or the other
 607         // of the heap.  Typically, these are the more recently engaged regions and the objects in these regions have not
 608         // yet had a chance to die (and/or are treated as floating garbage).  If we use the same allocation bias on each
 609         // GC pass, these "most recently" engaged regions for GC pass N will also be the "most recently" engaged regions
 610         // for GC pass N+1, and the relatively large amount of live data and/or floating garbage introduced
 611         // during the most recent GC pass may once again prevent the region from being collected.  We have found that
 612         // alternating the allocation behavior between GC passes improves evacuation performance by 3-7% on certain
 613         // benchmarks.  In the best case, this has the effect of consuming these partially consumed regions before
 614         // the start of the next mark cycle so all of their garbage can be efficiently reclaimed.
 615         //
 616         // First, finish consuming regions that are already partially consumed so as to more tightly limit ranges of
 617         // available regions.  Other potential benefits:
 618         //  1. Eventual collection set has fewer regions because we have packed newly allocated objects into fewer regions
 619         //  2. We preserve the "empty" regions longer into the GC cycle, reducing likelihood of allocation failures
 620         //     late in the GC cycle.
 621         idx_t non_empty_on_left = (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator)
 622                                      - _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator));
 623         idx_t non_empty_on_right = (_partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator)
 624                                       - _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator));
 625         _right_to_left_bias = (non_empty_on_right > non_empty_on_left);
 626         _alloc_bias_weight = _InitialAllocBiasWeight;
 627       }
 628       if (_right_to_left_bias) {
 629         // Allocate within mutator free from high memory to low so as to preserve low memory for humongous allocations
 630         if (!_partitions.is_empty(ShenandoahFreeSetPartitionId::Mutator)) {
 631           // Use signed idx.  Otherwise, loop will never terminate.
 632           idx_t leftmost = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator);
 633           for (idx_t idx = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator); idx >= leftmost; ) {
 634             assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx),
 635                    "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
 636             ShenandoahHeapRegion* r = _heap->get_region(idx);
 637             // try_allocate_in() increases used if the allocation is successful.
 638             HeapWord* result;
 639             size_t min_size = (req.type() == ShenandoahAllocRequest::_alloc_tlab)? req.min_size(): req.size();
 640             if ((alloc_capacity(r) >= min_size) && ((result = try_allocate_in(r, req, in_new_region)) != nullptr)) {
 641               return result;
 642             }
 643             idx = _partitions.find_index_of_previous_available_region(ShenandoahFreeSetPartitionId::Mutator, idx - 1);
 644           }
 645         }
 646       } else {
 647         // Allocate from low to high memory.  This keeps the range of fully empty regions more tightly packed.
 648         // Note that the most recently allocated regions tend not to be evacuated in a given GC cycle.  So this
 649         // tends to accumulate "fragmented" uncollected regions in high memory.
 650         if (!_partitions.is_empty(ShenandoahFreeSetPartitionId::Mutator)) {
 651           // Use signed idx.  Otherwise, loop will never terminate.
 652           idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
 653           for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); idx <= rightmost; ) {
 654             assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx),
 655                    "Boundaries or find_last_set_bit failed: " SSIZE_FORMAT, idx);
 656             ShenandoahHeapRegion* r = _heap->get_region(idx);
 657             // try_allocate_in() increases used if the allocation is successful.
 658             HeapWord* result;
 659             size_t min_size = (req.type() == ShenandoahAllocRequest::_alloc_tlab)? req.min_size(): req.size();
 660             if ((alloc_capacity(r) >= min_size) && ((result = try_allocate_in(r, req, in_new_region)) != nullptr)) {
 661               return result;
 662             }
 663             idx = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, idx + 1);
 664           }
 665         }
 666       }
 667       // There is no recovery. Mutator does not touch collector view at all.
 668       break;
 669     }
 670     case ShenandoahAllocRequest::_alloc_gclab:
 671       // GCLABs are for evacuation so we must be in evacuation phase.
 672 
 673     case ShenandoahAllocRequest::_alloc_shared_gc: {
 674       // Fast-path: try to allocate in the collector view first
 675       idx_t leftmost_collector = _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector);
 676       for (idx_t idx = _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector); idx >= leftmost_collector; ) {
 677         assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, idx),
 678                "Boundaries or find_prev_last_bit failed: " SSIZE_FORMAT, idx);
 679         HeapWord* result = try_allocate_in(_heap->get_region(idx), req, in_new_region);
 680         if (result != nullptr) {
 681           return result;
 682         }
 683         idx = _partitions.find_index_of_previous_available_region(ShenandoahFreeSetPartitionId::Collector, idx - 1);
 684       }
 685 
 686       // No dice. Can we borrow space from mutator view?
 687       if (!ShenandoahEvacReserveOverflow) {
 688         return nullptr;
 689       }
 690 
 691       // Try to steal an empty region from the mutator view.
 692       idx_t leftmost_mutator_empty = _partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator);
 693       for (idx_t idx = _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator); idx >= leftmost_mutator_empty; ) {
 694         assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx),
 695                "Boundaries or find_prev_last_bit failed: " SSIZE_FORMAT, idx);
 696         ShenandoahHeapRegion* r = _heap->get_region(idx);
 697         if (can_allocate_from(r)) {
 698           flip_to_gc(r);
 699           HeapWord *result = try_allocate_in(r, req, in_new_region);
 700           if (result != nullptr) {
 701             log_debug(gc)("Flipped region " SIZE_FORMAT " to gc for request: " PTR_FORMAT, idx, p2i(&req));
 702             return result;
 703           }
 704         }
 705         idx = _partitions.find_index_of_previous_available_region(ShenandoahFreeSetPartitionId::Mutator, idx - 1);
 706       }
 707 
 708       // No dice. Do not try to mix mutator and GC allocations, because adjusting region UWM
 709       // due to GC allocations would expose unparsable mutator allocations.
 710       break;
 711     }
 712     default:
 713       ShouldNotReachHere();
 714   }
 715   return nullptr;
 716 }
 717 
 718 HeapWord* ShenandoahFreeSet::try_allocate_in(ShenandoahHeapRegion* r, ShenandoahAllocRequest& req, bool& in_new_region) {
 719   assert (has_alloc_capacity(r), "Performance: should avoid full regions on this path: " SIZE_FORMAT, r->index());
 720   if (_heap->is_concurrent_weak_root_in_progress() && r->is_trash()) {
 721     return nullptr;
 722   }
 723 
 724   HeapWord* result = nullptr;
 725   try_recycle_trashed(r);
 726   in_new_region = r->is_empty();
 727 
 728   if (in_new_region) {
 729     log_debug(gc)("Using new region (" SIZE_FORMAT ") for %s (" PTR_FORMAT ").",
 730                        r->index(), ShenandoahAllocRequest::alloc_type_to_string(req.type()), p2i(&req));
 731   }
 732 
 733   // req.size() is in words, r->free() is in bytes.
 734   if (req.is_lab_alloc()) {
 735     // This is a GCLAB or a TLAB allocation
 736     size_t adjusted_size = req.size();
 737     size_t free = align_down(r->free() >> LogHeapWordSize, MinObjAlignment);
 738     if (adjusted_size > free) {
 739       adjusted_size = free;
 740     }
 741     if (adjusted_size >= req.min_size()) {
 742       result = r->allocate(adjusted_size, req.type());
 743       log_debug(gc)("Allocated " SIZE_FORMAT " words (adjusted from " SIZE_FORMAT ") for %s @" PTR_FORMAT
 744                           " from %s region " SIZE_FORMAT ", free bytes remaining: " SIZE_FORMAT,
 745                           adjusted_size, req.size(), ShenandoahAllocRequest::alloc_type_to_string(req.type()), p2i(result),
 746                           _partitions.partition_membership_name(r->index()), r->index(), r->free());
 747       assert (result != nullptr, "Allocation must succeed: free " SIZE_FORMAT ", actual " SIZE_FORMAT, free, adjusted_size);
 748       req.set_actual_size(adjusted_size);
 749     } else {
 750       log_trace(gc, free)("Failed to shrink TLAB or GCLAB request (" SIZE_FORMAT ") in region " SIZE_FORMAT " to " SIZE_FORMAT
 751                           " because min_size() is " SIZE_FORMAT, req.size(), r->index(), adjusted_size, req.min_size());
 752     }
 753   } else {
 754     size_t size = req.size();
 755     result = r->allocate(size, req.type());
 756     if (result != nullptr) {
 757       // Record actual allocation size
 758       log_debug(gc)("Allocated " SIZE_FORMAT " words for %s @" PTR_FORMAT
 759                           " from %s region " SIZE_FORMAT ", free bytes remaining: " SIZE_FORMAT,
 760                           size, ShenandoahAllocRequest::alloc_type_to_string(req.type()), p2i(result),
 761                           _partitions.partition_membership_name(r->index()),  r->index(), r->free());
 762       req.set_actual_size(size);
 763     }
 764   }
 765 
 766   if (result != nullptr) {
 767     // Allocation successful, bump stats:
 768     if (req.is_mutator_alloc()) {
 769       _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, req.actual_size() * HeapWordSize);
 770     } else {
 771       assert(req.is_gc_alloc(), "Should be gc_alloc since req wasn't mutator alloc");
 772 
 773       // For GC allocations, we advance update_watermark because the objects relocated into this memory during
 774       // evacuation are not updated during evacuation.
 775       r->set_update_watermark(r->top());
 776     }
 777   }
 778 
 779   static const size_t min_capacity = (size_t) (ShenandoahHeapRegion::region_size_bytes() * (1.0 - 1.0 / ShenandoahEvacWaste));
 780   size_t ac = alloc_capacity(r);
 781 
 782   if (((result == nullptr) && (ac < min_capacity)) || (alloc_capacity(r) < PLAB::min_size() * HeapWordSize)) {
 783     // Regardless of whether this allocation succeeded, if the remaining memory is less than PLAB:min_size(), retire this region.
 784     // Note that retire_from_partition() increases used to account for waste.
 785 
 786     // Also, if this allocation request failed and the consumed within this region * ShenandoahEvacWaste > region size,
 787     // then retire the region so that subsequent searches can find available memory more quickly.
 788 
 789     size_t idx = r->index();
 790     _partitions.retire_from_partition(req.is_mutator_alloc()?
 791                                       ShenandoahFreeSetPartitionId::Mutator: ShenandoahFreeSetPartitionId::Collector,
 792                                       idx, r->used());
 793     _partitions.assert_bounds();
 794   }
 795   return result;
 796 }
 797 
 798 HeapWord* ShenandoahFreeSet::allocate_contiguous(ShenandoahAllocRequest& req) {
 799   assert(req.is_mutator_alloc(), "All humongous allocations are performed by mutator");
 800   shenandoah_assert_heaplocked();
 801 
 802   size_t words_size = req.size();
 803   idx_t num = ShenandoahHeapRegion::required_regions(words_size * HeapWordSize);
 804 
 805   // Check if there are enough regions left to satisfy allocation.
 806   if (num > (idx_t) _partitions.count(ShenandoahFreeSetPartitionId::Mutator)) {
 807     return nullptr;
 808   }
 809 
 810   idx_t start_range = _partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Mutator);
 811   idx_t end_range = _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Mutator) + 1;
 812   idx_t last_possible_start = end_range - num;
 813 
 814   // Find the continuous interval of $num regions, starting from $beg and ending in $end,
 815   // inclusive. Contiguous allocations are biased to the beginning.
 816   idx_t beg = _partitions.find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId::Mutator,
 817                                                                             start_range, num);
 818   if (beg > last_possible_start) {
 819     // Hit the end, goodbye
 820     return nullptr;
 821   }
 822   idx_t end = beg;
 823 
 824   while (true) {
 825     // We've confirmed num contiguous regions belonging to Mutator partition, so no need to confirm membership.
 826     // If region is not completely free, the current [beg; end] is useless, and we may fast-forward.  If we can extend
 827     // the existing range, we can exploit that certain regions are already known to be in the Mutator free set.
 828     while (!can_allocate_from(_heap->get_region(end))) {
 829       // region[end] is not empty, so we restart our search after region[end]
 830       idx_t slide_delta = end + 1 - beg;
 831       if (beg + slide_delta > last_possible_start) {
 832         // no room to slide
 833         return nullptr;
 834       }
 835       for (idx_t span_end = beg + num; slide_delta > 0; slide_delta--) {
 836         if (!_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, span_end)) {
 837           beg = _partitions.find_index_of_next_available_cluster_of_regions(ShenandoahFreeSetPartitionId::Mutator,
 838                                                                             span_end + 1, num);
 839           break;
 840         } else {
 841           beg++;
 842           span_end++;
 843         }
 844       }
 845       // Here, either beg identifies a range of num regions all of which are in the Mutator free set, or beg > last_possible_start
 846       if (beg > last_possible_start) {
 847         // Hit the end, goodbye
 848         return nullptr;
 849       }
 850       end = beg;
 851     }
 852 
 853     if ((end - beg + 1) == num) {
 854       // found the match
 855       break;
 856     }
 857 
 858     end++;
 859   }
 860 
 861   size_t remainder = words_size & ShenandoahHeapRegion::region_size_words_mask();
 862   // Initialize regions:
 863   for (idx_t i = beg; i <= end; i++) {
 864     ShenandoahHeapRegion* r = _heap->get_region(i);
 865     try_recycle_trashed(r);
 866 
 867     assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous");
 868     assert(r->is_empty(), "Should be empty");
 869 
 870     if (i == beg) {
 871       r->make_humongous_start();
 872     } else {
 873       r->make_humongous_cont();
 874     }
 875 
 876     // Trailing region may be non-full, record the remainder there
 877     size_t used_words;
 878     if ((i == end) && (remainder != 0)) {
 879       used_words = remainder;
 880     } else {
 881       used_words = ShenandoahHeapRegion::region_size_words();
 882     }
 883 
 884     r->set_top(r->bottom() + used_words);
 885   }
 886 
 887   if (remainder != 0) {
 888     // Record this remainder as allocation waste
 889     _heap->notify_mutator_alloc_words(ShenandoahHeapRegion::region_size_words() - remainder, true);
 890   }
 891 
 892   // retire_range_from_partition() will adjust bounds on Mutator free set if appropriate
 893   _partitions.retire_range_from_partition(ShenandoahFreeSetPartitionId::Mutator, beg, end);
 894 
 895   size_t total_humongous_size = ShenandoahHeapRegion::region_size_bytes() * num;
 896   _partitions.increase_used(ShenandoahFreeSetPartitionId::Mutator, total_humongous_size);
 897   _partitions.assert_bounds();
 898   req.set_actual_size(words_size);
 899   return _heap->get_region(beg)->bottom();
 900 }
 901 
 902 void ShenandoahFreeSet::try_recycle_trashed(ShenandoahHeapRegion *r) {
 903   if (r->is_trash()) {
 904     _heap->decrease_used(r->used());
 905     r->recycle();
 906   }
 907 }
 908 
 909 void ShenandoahFreeSet::recycle_trash() {
 910   // lock is not reentrable, check we don't have it
 911   shenandoah_assert_not_heaplocked();
 912 
 913   for (size_t i = 0; i < _heap->num_regions(); i++) {
 914     ShenandoahHeapRegion* r = _heap->get_region(i);
 915     if (r->is_trash()) {
 916       ShenandoahHeapLocker locker(_heap->lock());
 917       try_recycle_trashed(r);
 918     }
 919     SpinPause(); // allow allocators to take the lock
 920   }
 921 }
 922 
 923 void ShenandoahFreeSet::flip_to_gc(ShenandoahHeapRegion* r) {
 924   size_t idx = r->index();
 925 
 926   assert(_partitions.partition_id_matches(idx, ShenandoahFreeSetPartitionId::Mutator), "Should be in mutator view");
 927   assert(can_allocate_from(r), "Should not be allocated");
 928 
 929   size_t ac = alloc_capacity(r);
 930   _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
 931                                                ShenandoahFreeSetPartitionId::Collector, ac);
 932   _partitions.assert_bounds();
 933 
 934   // We do not ensure that the region is no longer trash, relying on try_allocate_in(), which always comes next,
 935   // to recycle trash before attempting to allocate anything in the region.
 936 }
 937 
 938 void ShenandoahFreeSet::clear() {
 939   shenandoah_assert_heaplocked();
 940   clear_internal();
 941 }
 942 
 943 void ShenandoahFreeSet::clear_internal() {
 944   _partitions.make_all_regions_unavailable();
 945 }
 946 
 947 void ShenandoahFreeSet::find_regions_with_alloc_capacity(size_t &cset_regions) {
 948 
 949   cset_regions = 0;
 950   clear_internal();
 951   size_t region_size_bytes = _partitions.region_size_bytes();
 952   size_t max_regions = _partitions.max_regions();
 953 
 954   size_t mutator_leftmost = max_regions;
 955   size_t mutator_rightmost = 0;
 956   size_t mutator_leftmost_empty = max_regions;
 957   size_t mutator_rightmost_empty = 0;
 958 
 959   size_t mutator_regions = 0;
 960   size_t mutator_used = 0;
 961 
 962   for (size_t idx = 0; idx < _heap->num_regions(); idx++) {
 963     ShenandoahHeapRegion* region = _heap->get_region(idx);
 964     if (region->is_trash()) {
 965       // Trashed regions represent regions that had been in the collection partition but have not yet been "cleaned up".
 966       // The cset regions are not "trashed" until we have finished update refs.
 967       cset_regions++;
 968     }
 969     if (region->is_alloc_allowed() || region->is_trash()) {
 970 
 971       // Do not add regions that would almost surely fail allocation
 972       size_t ac = alloc_capacity(region);
 973       if (ac > PLAB::min_size() * HeapWordSize) {
 974         _partitions.raw_assign_membership(idx, ShenandoahFreeSetPartitionId::Mutator);
 975 
 976         if (idx < mutator_leftmost) {
 977           mutator_leftmost = idx;
 978         }
 979         if (idx > mutator_rightmost) {
 980           mutator_rightmost = idx;
 981         }
 982         if (ac == region_size_bytes) {
 983           if (idx < mutator_leftmost_empty) {
 984             mutator_leftmost_empty = idx;
 985           }
 986           if (idx > mutator_rightmost_empty) {
 987             mutator_rightmost_empty = idx;
 988           }
 989         }
 990         mutator_regions++;
 991         mutator_used += (region_size_bytes - ac);
 992 
 993         log_debug(gc)(
 994           "  Adding Region " SIZE_FORMAT " (Free: " SIZE_FORMAT "%s, Used: " SIZE_FORMAT "%s) to mutator partition",
 995           idx, byte_size_in_proper_unit(region->free()), proper_unit_for_byte_size(region->free()),
 996           byte_size_in_proper_unit(region->used()), proper_unit_for_byte_size(region->used()));
 997       }
 998     }
 999   }
1000   _partitions.establish_mutator_intervals(mutator_leftmost, mutator_rightmost, mutator_leftmost_empty, mutator_rightmost_empty,
1001                                           mutator_regions, mutator_used);
1002 }
1003 
1004 void ShenandoahFreeSet::move_regions_from_collector_to_mutator(size_t max_xfer_regions) {
1005   size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1006   size_t collector_empty_xfer = 0;
1007   size_t collector_not_empty_xfer = 0;
1008 
1009   // Process empty regions within the Collector free partition
1010   if ((max_xfer_regions > 0) &&
1011       (_partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Collector)
1012        <= _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Collector))) {
1013     ShenandoahHeapLocker locker(_heap->lock());
1014     idx_t rightmost = _partitions.rightmost_empty(ShenandoahFreeSetPartitionId::Collector);
1015     for (idx_t idx = _partitions.leftmost_empty(ShenandoahFreeSetPartitionId::Collector);
1016          (max_xfer_regions > 0) && (idx <= rightmost); ) {
1017       assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, idx),
1018              "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, idx);
1019       // Note: can_allocate_from() denotes that region is entirely empty
1020       if (can_allocate_from(idx)) {
1021         _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Collector,
1022                                                      ShenandoahFreeSetPartitionId::Mutator, region_size_bytes);
1023         max_xfer_regions--;
1024         collector_empty_xfer += region_size_bytes;
1025       }
1026       idx = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Collector, idx + 1);
1027     }
1028   }
1029 
1030   // If there are any non-empty regions within Collector partition, we can also move them to the Mutator free partition
1031   if ((max_xfer_regions > 0) && (_partitions.leftmost(ShenandoahFreeSetPartitionId::Collector)
1032                                  <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector))) {
1033     ShenandoahHeapLocker locker(_heap->lock());
1034     idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector);
1035     for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector);
1036          (max_xfer_regions > 0) && (idx <= rightmost); ) {
1037       assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, idx),
1038              "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, idx);
1039       size_t ac = alloc_capacity(idx);
1040       if (ac > 0) {
1041         _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Collector,
1042                                                      ShenandoahFreeSetPartitionId::Mutator, ac);
1043         max_xfer_regions--;
1044         collector_not_empty_xfer += ac;
1045       }
1046       idx = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Collector, idx + 1);
1047     }
1048   }
1049 
1050   size_t collector_xfer = collector_empty_xfer + collector_not_empty_xfer;
1051   log_info(gc)("At start of update refs, moving " SIZE_FORMAT "%s to Mutator free partition from Collector Reserve",
1052                byte_size_in_proper_unit(collector_xfer), proper_unit_for_byte_size(collector_xfer));
1053 }
1054 
1055 void ShenandoahFreeSet::prepare_to_rebuild(size_t &cset_regions) {
1056   shenandoah_assert_heaplocked();
1057 
1058   log_debug(gc)("Rebuilding FreeSet");
1059 
1060   // This places regions that have alloc_capacity into the mutator partition.
1061   find_regions_with_alloc_capacity(cset_regions);
1062 }
1063 
1064 void ShenandoahFreeSet::finish_rebuild(size_t cset_regions) {
1065   shenandoah_assert_heaplocked();
1066 
1067   // Our desire is to reserve this much memory for future evacuation.  We may end up reserving less, if
1068   // memory is in short supply.
1069 
1070   size_t reserve = _heap->max_capacity() * ShenandoahEvacReserve / 100;
1071   size_t available_in_collector_partition = (_partitions.capacity_of(ShenandoahFreeSetPartitionId::Collector)
1072                                              - _partitions.used_by(ShenandoahFreeSetPartitionId::Collector));
1073   size_t additional_reserve;
1074   if (available_in_collector_partition < reserve) {
1075     additional_reserve = reserve - available_in_collector_partition;
1076   } else {
1077     additional_reserve = 0;
1078   }
1079 
1080   reserve_regions(reserve);
1081   _partitions.assert_bounds();
1082   log_status();
1083 }
1084 
1085 void ShenandoahFreeSet::rebuild() {
1086   size_t cset_regions;
1087   prepare_to_rebuild(cset_regions);
1088   finish_rebuild(cset_regions);
1089 }
1090 
1091 void ShenandoahFreeSet::reserve_regions(size_t to_reserve) {
1092   for (size_t i = _heap->num_regions(); i > 0; i--) {
1093     size_t idx = i - 1;
1094     ShenandoahHeapRegion* r = _heap->get_region(idx);
1095 
1096     if (!_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx)) {
1097       continue;
1098     }
1099 
1100     size_t ac = alloc_capacity(r);
1101     assert (ac > 0, "Membership in free partition implies has capacity");
1102 
1103     bool move_to_collector = _partitions.available_in(ShenandoahFreeSetPartitionId::Collector) < to_reserve;
1104     if (!move_to_collector) {
1105       // We've satisfied to_reserve
1106       break;
1107     }
1108 
1109     if (move_to_collector) {
1110       // Note: In a previous implementation, regions were only placed into the survivor space (collector_is_free) if
1111       // they were entirely empty.  This has the effect of causing new Mutator allocation to reside next to objects
1112       // that have already survived at least one GC, mixing ephemeral with longer-lived objects in the same region.
1113       // Any objects that have survived a GC are less likely to immediately become garbage, so a region that contains
1114       // survivor objects is less likely to be selected for the collection set.  This alternative implementation allows
1115       // survivor regions to continue accumulating other survivor objects, and makes it more likely that ephemeral objects
1116       // occupy regions comprised entirely of ephemeral objects.  These regions are highly likely to be included in the next
1117       // collection set, and they are easily evacuated because they have low density of live objects.
1118       _partitions.move_from_partition_to_partition(idx, ShenandoahFreeSetPartitionId::Mutator,
1119                                                    ShenandoahFreeSetPartitionId::Collector, ac);
1120       log_debug(gc)("  Shifting region " SIZE_FORMAT " from mutator_free to collector_free", idx);
1121     }
1122   }
1123 
1124   if (LogTarget(Info, gc, free)::is_enabled()) {
1125     size_t reserve = _partitions.capacity_of(ShenandoahFreeSetPartitionId::Collector);
1126     if (reserve < to_reserve) {
1127       log_debug(gc)("Wanted " PROPERFMT " for young reserve, but only reserved: " PROPERFMT,
1128                     PROPERFMTARGS(to_reserve), PROPERFMTARGS(reserve));
1129     }
1130   }
1131 }
1132 
1133 void ShenandoahFreeSet::log_status() {
1134   shenandoah_assert_heaplocked();
1135 
1136 #ifdef ASSERT
1137   // Dump of the FreeSet details is only enabled if assertions are enabled
1138   if (LogTarget(Debug, gc, free)::is_enabled()) {
1139 #define BUFFER_SIZE 80
1140     size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes();
1141     size_t consumed_collector = 0;
1142     size_t available_collector = 0;
1143     size_t consumed_mutator = 0;
1144     size_t available_mutator = 0;
1145 
1146     char buffer[BUFFER_SIZE];
1147     for (uint i = 0; i < BUFFER_SIZE; i++) {
1148       buffer[i] = '\0';
1149     }
1150     log_debug(gc)("FreeSet map legend: M:mutator_free C:collector_free H:humongous _:retired");
1151     log_debug(gc)(" mutator free range [" SIZE_FORMAT ".." SIZE_FORMAT "],"
1152                   " collector free range [" SIZE_FORMAT ".." SIZE_FORMAT "]",
1153                   _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator),
1154                   _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator),
1155                   _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector),
1156                   _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector));
1157 
1158     for (uint i = 0; i < _heap->num_regions(); i++) {
1159       ShenandoahHeapRegion *r = _heap->get_region(i);
1160       uint idx = i % 64;
1161       if ((i != 0) && (idx == 0)) {
1162         log_debug(gc)(" %6u: %s", i-64, buffer);
1163       }
1164       if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, i)) {
1165         size_t capacity = alloc_capacity(r);
1166         available_mutator += capacity;
1167         consumed_mutator += region_size_bytes - capacity;
1168         buffer[idx] = (capacity == region_size_bytes)? 'M': 'm';
1169       } else if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, i)) {
1170         size_t capacity = alloc_capacity(r);
1171         available_collector += capacity;
1172         consumed_collector += region_size_bytes - capacity;
1173         buffer[idx] = (capacity == region_size_bytes)? 'C': 'c';
1174       } else if (r->is_humongous()) {
1175         buffer[idx] = 'h';
1176       } else {
1177         buffer[idx] = '_';
1178       }
1179     }
1180     uint remnant = _heap->num_regions() % 64;
1181     if (remnant > 0) {
1182       buffer[remnant] = '\0';
1183     } else {
1184       remnant = 64;
1185     }
1186     log_debug(gc)(" %6u: %s", (uint) (_heap->num_regions() - remnant), buffer);
1187   }
1188 #endif
1189 
1190   LogTarget(Info, gc, free) lt;
1191   if (lt.is_enabled()) {
1192     ResourceMark rm;
1193     LogStream ls(lt);
1194 
1195     {
1196       idx_t last_idx = 0;
1197       size_t max = 0;
1198       size_t max_contig = 0;
1199       size_t empty_contig = 0;
1200 
1201       size_t total_used = 0;
1202       size_t total_free = 0;
1203       size_t total_free_ext = 0;
1204 
1205       for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator);
1206            idx <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator); idx++) {
1207         if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, idx)) {
1208           ShenandoahHeapRegion *r = _heap->get_region(idx);
1209           size_t free = alloc_capacity(r);
1210           max = MAX2(max, free);
1211           if (r->is_empty()) {
1212             total_free_ext += free;
1213             if (last_idx + 1 == idx) {
1214               empty_contig++;
1215             } else {
1216               empty_contig = 1;
1217             }
1218           } else {
1219             empty_contig = 0;
1220           }
1221           total_used += r->used();
1222           total_free += free;
1223           max_contig = MAX2(max_contig, empty_contig);
1224           last_idx = idx;
1225         }
1226       }
1227 
1228       size_t max_humongous = max_contig * ShenandoahHeapRegion::region_size_bytes();
1229       size_t free = capacity() - used();
1230 
1231       // Since certain regions that belonged to the Mutator free partition at the time of most recent rebuild may have been
1232       // retired, the sum of used and capacities within regions that are still in the Mutator free partition may not match
1233       // my internally tracked values of used() and free().
1234       assert(free == total_free, "Free memory should match");
1235 
1236       ls.print("Free: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s regular, " SIZE_FORMAT "%s humongous, ",
1237                byte_size_in_proper_unit(free),          proper_unit_for_byte_size(free),
1238                byte_size_in_proper_unit(max),           proper_unit_for_byte_size(max),
1239                byte_size_in_proper_unit(max_humongous), proper_unit_for_byte_size(max_humongous)
1240       );
1241 
1242       ls.print("Frag: ");
1243       size_t frag_ext;
1244       if (total_free_ext > 0) {
1245         frag_ext = 100 - (100 * max_humongous / total_free_ext);
1246       } else {
1247         frag_ext = 0;
1248       }
1249       ls.print(SIZE_FORMAT "%% external, ", frag_ext);
1250 
1251       size_t frag_int;
1252       if (_partitions.count(ShenandoahFreeSetPartitionId::Mutator) > 0) {
1253         frag_int = (100 * (total_used / _partitions.count(ShenandoahFreeSetPartitionId::Mutator))
1254                     / ShenandoahHeapRegion::region_size_bytes());
1255       } else {
1256         frag_int = 0;
1257       }
1258       ls.print(SIZE_FORMAT "%% internal; ", frag_int);
1259       ls.print("Used: " SIZE_FORMAT "%s, Mutator Free: " SIZE_FORMAT,
1260                byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used),
1261                _partitions.count(ShenandoahFreeSetPartitionId::Mutator));
1262     }
1263 
1264     {
1265       size_t max = 0;
1266       size_t total_free = 0;
1267       size_t total_used = 0;
1268 
1269       for (idx_t idx = _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector);
1270            idx <= _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector); idx++) {
1271         if (_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, idx)) {
1272           ShenandoahHeapRegion *r = _heap->get_region(idx);
1273           size_t free = alloc_capacity(r);
1274           max = MAX2(max, free);
1275           total_free += free;
1276           total_used += r->used();
1277         }
1278       }
1279       ls.print(" Collector Reserve: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s; Used: " SIZE_FORMAT "%s",
1280                byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
1281                byte_size_in_proper_unit(max),        proper_unit_for_byte_size(max),
1282                byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used));
1283     }
1284   }
1285 }
1286 
1287 HeapWord* ShenandoahFreeSet::allocate(ShenandoahAllocRequest& req, bool& in_new_region) {
1288   shenandoah_assert_heaplocked();
1289   if (req.size() > ShenandoahHeapRegion::humongous_threshold_words()) {
1290     switch (req.type()) {
1291       case ShenandoahAllocRequest::_alloc_shared:
1292       case ShenandoahAllocRequest::_alloc_shared_gc:
1293         in_new_region = true;
1294         return allocate_contiguous(req);
1295       case ShenandoahAllocRequest::_alloc_gclab:
1296       case ShenandoahAllocRequest::_alloc_tlab:
1297         in_new_region = false;
1298         assert(false, "Trying to allocate TLAB larger than the humongous threshold: " SIZE_FORMAT " > " SIZE_FORMAT,
1299                req.size(), ShenandoahHeapRegion::humongous_threshold_words());
1300         return nullptr;
1301       default:
1302         ShouldNotReachHere();
1303         return nullptr;
1304     }
1305   } else {
1306     return allocate_single(req, in_new_region);
1307   }
1308 }
1309 
1310 void ShenandoahFreeSet::print_on(outputStream* out) const {
1311   out->print_cr("Mutator Free Set: " SIZE_FORMAT "", _partitions.count(ShenandoahFreeSetPartitionId::Mutator));
1312   idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
1313   for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); index <= rightmost; ) {
1314     assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, index),
1315            "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
1316     _heap->get_region(index)->print_on(out);
1317     index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, index + 1);
1318   }
1319   out->print_cr("Collector Free Set: " SIZE_FORMAT "", _partitions.count(ShenandoahFreeSetPartitionId::Collector));
1320   rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Collector);
1321   for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Collector); index <= rightmost; ) {
1322     assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Collector, index),
1323            "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
1324     _heap->get_region(index)->print_on(out);
1325     index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Collector, index + 1);
1326   }
1327 }
1328 
1329 double ShenandoahFreeSet::internal_fragmentation() {
1330   double squared = 0;
1331   double linear = 0;
1332   int count = 0;
1333 
1334   idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
1335   for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); index <= rightmost; ) {
1336     assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, index),
1337            "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
1338     ShenandoahHeapRegion* r = _heap->get_region(index);
1339     size_t used = r->used();
1340     squared += used * used;
1341     linear += used;
1342     count++;
1343     index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, index + 1);
1344   }
1345 
1346   if (count > 0) {
1347     double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear);
1348     return 1 - s;
1349   } else {
1350     return 0;
1351   }
1352 }
1353 
1354 double ShenandoahFreeSet::external_fragmentation() {
1355   idx_t last_idx = 0;
1356   size_t max_contig = 0;
1357   size_t empty_contig = 0;
1358 
1359   size_t free = 0;
1360 
1361   idx_t rightmost = _partitions.rightmost(ShenandoahFreeSetPartitionId::Mutator);
1362   for (idx_t index = _partitions.leftmost(ShenandoahFreeSetPartitionId::Mutator); index <= rightmost; ) {
1363     assert(_partitions.in_free_set(ShenandoahFreeSetPartitionId::Mutator, index),
1364            "Boundaries or find_first_set_bit failed: " SSIZE_FORMAT, index);
1365     ShenandoahHeapRegion* r = _heap->get_region(index);
1366     if (r->is_empty()) {
1367       free += ShenandoahHeapRegion::region_size_bytes();
1368       if (last_idx + 1 == index) {
1369         empty_contig++;
1370       } else {
1371         empty_contig = 1;
1372       }
1373     } else {
1374       empty_contig = 0;
1375     }
1376     max_contig = MAX2(max_contig, empty_contig);
1377     last_idx = index;
1378     index = _partitions.find_index_of_next_available_region(ShenandoahFreeSetPartitionId::Mutator, index + 1);
1379   }
1380 
1381   if (free > 0) {
1382     return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free);
1383   } else {
1384     return 0;
1385   }
1386 }
1387