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 "logging/logStream.hpp" 38 #include "memory/resourceArea.hpp" 39 #include "runtime/orderAccess.hpp" 40 41 ShenandoahSetsOfFree::ShenandoahSetsOfFree(size_t max_regions, ShenandoahFreeSet* free_set) : 42 _max(max_regions), 43 _free_set(free_set), 44 _region_size_bytes(ShenandoahHeapRegion::region_size_bytes()) 45 { 46 _membership = NEW_C_HEAP_ARRAY(ShenandoahFreeMemoryType, max_regions, mtGC); 47 clear_internal(); 48 } 49 50 ShenandoahSetsOfFree::~ShenandoahSetsOfFree() { 51 FREE_C_HEAP_ARRAY(ShenandoahFreeMemoryType, _membership); 52 } 53 54 55 void ShenandoahSetsOfFree::clear_internal() { 56 for (size_t idx = 0; idx < _max; idx++) { 57 _membership[idx] = NotFree; 58 } 59 60 for (size_t idx = 0; idx < NumFreeSets; idx++) { 61 _leftmosts[idx] = _max; 62 _rightmosts[idx] = 0; 63 _leftmosts_empty[idx] = _max; 64 _rightmosts_empty[idx] = 0; 65 _capacity_of[idx] = 0; 66 _used_by[idx] = 0; 67 } 68 69 _left_to_right_bias[Mutator] = true; 70 _left_to_right_bias[Collector] = false; 71 _left_to_right_bias[OldCollector] = false; 72 73 _region_counts[Mutator] = 0; 74 _region_counts[Collector] = 0; 75 _region_counts[OldCollector] = 0; 76 _region_counts[NotFree] = _max; 77 } 78 79 void ShenandoahSetsOfFree::clear_all() { 80 clear_internal(); 81 } 82 83 void ShenandoahSetsOfFree::increase_used(ShenandoahFreeMemoryType which_set, size_t bytes) { 84 assert (which_set > NotFree && which_set < NumFreeSets, "Set must correspond to a valid freeset"); 85 _used_by[which_set] += bytes; 86 assert (_used_by[which_set] <= _capacity_of[which_set], 87 "Must not use (" SIZE_FORMAT ") more than capacity (" SIZE_FORMAT ") after increase by " SIZE_FORMAT, 88 _used_by[which_set], _capacity_of[which_set], bytes); 89 } 90 91 inline void ShenandoahSetsOfFree::shrink_bounds_if_touched(ShenandoahFreeMemoryType set, size_t idx) { 92 if (idx == _leftmosts[set]) { 93 while ((_leftmosts[set] < _max) && !in_free_set(_leftmosts[set], set)) { 94 _leftmosts[set]++; 95 } 96 if (_leftmosts_empty[set] < _leftmosts[set]) { 97 // This gets us closer to where we need to be; we'll scan further when leftmosts_empty is requested. 98 _leftmosts_empty[set] = _leftmosts[set]; 99 } 100 } 101 if (idx == _rightmosts[set]) { 102 while (_rightmosts[set] > 0 && !in_free_set(_rightmosts[set], set)) { 103 _rightmosts[set]--; 104 } 105 if (_rightmosts_empty[set] > _rightmosts[set]) { 106 // This gets us closer to where we need to be; we'll scan further when rightmosts_empty is requested. 107 _rightmosts_empty[set] = _rightmosts[set]; 108 } 109 } 110 } 111 112 inline void ShenandoahSetsOfFree::expand_bounds_maybe(ShenandoahFreeMemoryType set, size_t idx, size_t region_capacity) { 113 if (region_capacity == _region_size_bytes) { 114 if (_leftmosts_empty[set] > idx) { 115 _leftmosts_empty[set] = idx; 116 } 117 if (_rightmosts_empty[set] < idx) { 118 _rightmosts_empty[set] = idx; 119 } 120 } 121 if (_leftmosts[set] > idx) { 122 _leftmosts[set] = idx; 123 } 124 if (_rightmosts[set] < idx) { 125 _rightmosts[set] = idx; 126 } 127 } 128 129 void ShenandoahSetsOfFree::remove_from_free_sets(size_t idx) { 130 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max); 131 ShenandoahFreeMemoryType orig_set = membership(idx); 132 assert (orig_set > NotFree && orig_set < NumFreeSets, "Cannot remove from free sets if not already free"); 133 _membership[idx] = NotFree; 134 shrink_bounds_if_touched(orig_set, idx); 135 136 _region_counts[orig_set]--; 137 _region_counts[NotFree]++; 138 } 139 140 141 void ShenandoahSetsOfFree::make_free(size_t idx, ShenandoahFreeMemoryType which_set, size_t region_capacity) { 142 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max); 143 assert (_membership[idx] == NotFree, "Cannot make free if already free"); 144 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 145 _membership[idx] = which_set; 146 _capacity_of[which_set] += region_capacity; 147 expand_bounds_maybe(which_set, idx, region_capacity); 148 149 _region_counts[NotFree]--; 150 _region_counts[which_set]++; 151 } 152 153 void ShenandoahSetsOfFree::move_to_set(size_t idx, ShenandoahFreeMemoryType new_set, size_t region_capacity) { 154 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max); 155 assert ((new_set > NotFree) && (new_set < NumFreeSets), "New set must be valid"); 156 ShenandoahFreeMemoryType orig_set = _membership[idx]; 157 assert ((orig_set > NotFree) && (orig_set < NumFreeSets), "Cannot move free unless already free"); 158 // Expected transitions: 159 // During rebuild: Mutator => Collector 160 // Mutator empty => Collector 161 // During flip_to_gc: 162 // Mutator empty => Collector 163 // Mutator empty => Old Collector 164 // At start of update refs: 165 // Collector => Mutator 166 // OldCollector Empty => Mutator 167 assert (((region_capacity <= _region_size_bytes) && 168 ((orig_set == Mutator) && (new_set == Collector)) || 169 ((orig_set == Collector) && (new_set == Mutator))) || 170 ((region_capacity == _region_size_bytes) && 171 ((orig_set == Mutator) && (new_set == Collector)) || 172 ((orig_set == OldCollector) && (new_set == Mutator)) || 173 (new_set == OldCollector)), "Unexpected movement between sets"); 174 175 _membership[idx] = new_set; 176 _capacity_of[orig_set] -= region_capacity; 177 shrink_bounds_if_touched(orig_set, idx); 178 179 _capacity_of[new_set] += region_capacity; 180 expand_bounds_maybe(new_set, idx, region_capacity); 181 182 _region_counts[orig_set]--; 183 _region_counts[new_set]++; 184 } 185 186 inline ShenandoahFreeMemoryType ShenandoahSetsOfFree::membership(size_t idx) const { 187 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max); 188 return _membership[idx]; 189 } 190 191 // Returns true iff region idx is in the test_set free_set. Before returning true, asserts that the free 192 // set is not empty. Requires that test_set != NotFree or NumFreeSets. 193 inline bool ShenandoahSetsOfFree::in_free_set(size_t idx, ShenandoahFreeMemoryType test_set) const { 194 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT, idx, _max); 195 if (_membership[idx] == test_set) { 196 assert (test_set == NotFree || _free_set->alloc_capacity(idx) > 0, "Free regions must have alloc capacity"); 197 return true; 198 } else { 199 return false; 200 } 201 } 202 203 inline size_t ShenandoahSetsOfFree::leftmost(ShenandoahFreeMemoryType which_set) const { 204 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 205 size_t idx = _leftmosts[which_set]; 206 if (idx >= _max) { 207 return _max; 208 } else { 209 assert (in_free_set(idx, which_set), "left-most region must be free"); 210 return idx; 211 } 212 } 213 214 inline size_t ShenandoahSetsOfFree::rightmost(ShenandoahFreeMemoryType which_set) const { 215 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 216 size_t idx = _rightmosts[which_set]; 217 assert ((_leftmosts[which_set] == _max) || in_free_set(idx, which_set), "right-most region must be free"); 218 return idx; 219 } 220 221 inline bool ShenandoahSetsOfFree::is_empty(ShenandoahFreeMemoryType which_set) const { 222 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 223 return (leftmost(which_set) > rightmost(which_set)); 224 } 225 226 size_t ShenandoahSetsOfFree::leftmost_empty(ShenandoahFreeMemoryType which_set) { 227 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 228 for (size_t idx = _leftmosts_empty[which_set]; idx < _max; idx++) { 229 if ((membership(idx) == which_set) && (_free_set->alloc_capacity(idx) == _region_size_bytes)) { 230 _leftmosts_empty[which_set] = idx; 231 return idx; 232 } 233 } 234 _leftmosts_empty[which_set] = _max; 235 _rightmosts_empty[which_set] = 0; 236 return _max; 237 } 238 239 inline size_t ShenandoahSetsOfFree::rightmost_empty(ShenandoahFreeMemoryType which_set) { 240 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 241 for (intptr_t idx = _rightmosts_empty[which_set]; idx >= 0; idx--) { 242 if ((membership(idx) == which_set) && (_free_set->alloc_capacity(idx) == _region_size_bytes)) { 243 _rightmosts_empty[which_set] = idx; 244 return idx; 245 } 246 } 247 _leftmosts_empty[which_set] = _max; 248 _rightmosts_empty[which_set] = 0; 249 return 0; 250 } 251 252 inline bool ShenandoahSetsOfFree::alloc_from_left_bias(ShenandoahFreeMemoryType which_set) { 253 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 254 return _left_to_right_bias[which_set]; 255 } 256 257 void ShenandoahSetsOfFree::establish_alloc_bias(ShenandoahFreeMemoryType which_set) { 258 ShenandoahHeap* heap = ShenandoahHeap::heap(); 259 shenandoah_assert_heaplocked(); 260 assert (which_set > NotFree && which_set < NumFreeSets, "selected free set must be valid"); 261 262 size_t middle = (_leftmosts[which_set] + _rightmosts[which_set]) / 2; 263 size_t available_in_first_half = 0; 264 size_t available_in_second_half = 0; 265 266 for (size_t index = _leftmosts[which_set]; index < middle; index++) { 267 if (in_free_set(index, which_set)) { 268 ShenandoahHeapRegion* r = heap->get_region(index); 269 available_in_first_half += r->free(); 270 } 271 } 272 for (size_t index = middle; index <= _rightmosts[which_set]; index++) { 273 if (in_free_set(index, which_set)) { 274 ShenandoahHeapRegion* r = heap->get_region(index); 275 available_in_second_half += r->free(); 276 } 277 } 278 279 // We desire to first consume the sparsely distributed regions in order that the remaining regions are densely packed. 280 // Densely packing regions reduces the effort to search for a region that has sufficient memory to satisfy a new allocation 281 // request. Regions become sparsely distributed following a Full GC, which tends to slide all regions to the front of the 282 // heap rather than allowing survivor regions to remain at the high end of the heap where we intend for them to congregate. 283 284 // 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 285 // front of the heap. If this is done, we can always search survivor Collector and OldCollector regions right to left. 286 _left_to_right_bias[which_set] = (available_in_second_half > available_in_first_half); 287 } 288 289 #ifdef ASSERT 290 void ShenandoahSetsOfFree::assert_bounds() { 291 292 size_t leftmosts[NumFreeSets]; 293 size_t rightmosts[NumFreeSets]; 294 size_t empty_leftmosts[NumFreeSets]; 295 size_t empty_rightmosts[NumFreeSets]; 296 297 for (int i = 0; i < NumFreeSets; i++) { 298 leftmosts[i] = _max; 299 empty_leftmosts[i] = _max; 300 rightmosts[i] = 0; 301 empty_rightmosts[i] = 0; 302 } 303 304 for (size_t i = 0; i < _max; i++) { 305 ShenandoahFreeMemoryType set = membership(i); 306 switch (set) { 307 case NotFree: 308 break; 309 310 case Mutator: 311 case Collector: 312 case OldCollector: 313 { 314 size_t capacity = _free_set->alloc_capacity(i); 315 bool is_empty = (capacity == _region_size_bytes); 316 assert(capacity > 0, "free regions must have allocation capacity"); 317 if (i < leftmosts[set]) { 318 leftmosts[set] = i; 319 } 320 if (is_empty && (i < empty_leftmosts[set])) { 321 empty_leftmosts[set] = i; 322 } 323 if (i > rightmosts[set]) { 324 rightmosts[set] = i; 325 } 326 if (is_empty && (i > empty_rightmosts[set])) { 327 empty_rightmosts[set] = i; 328 } 329 break; 330 } 331 332 case NumFreeSets: 333 default: 334 ShouldNotReachHere(); 335 } 336 } 337 338 // Performance invariants. Failing these would not break the free set, but performance would suffer. 339 assert (leftmost(Mutator) <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, leftmost(Mutator), _max); 340 assert (rightmost(Mutator) < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, rightmost(Mutator), _max); 341 342 assert (leftmost(Mutator) == _max || in_free_set(leftmost(Mutator), Mutator), 343 "leftmost region should be free: " SIZE_FORMAT, leftmost(Mutator)); 344 assert (leftmost(Mutator) == _max || in_free_set(rightmost(Mutator), Mutator), 345 "rightmost region should be free: " SIZE_FORMAT, rightmost(Mutator)); 346 347 // If Mutator set is empty, leftmosts will both equal max, rightmosts will both equal zero. Likewise for empty region sets. 348 size_t beg_off = leftmosts[Mutator]; 349 size_t end_off = rightmosts[Mutator]; 350 assert (beg_off >= leftmost(Mutator), 351 "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, leftmost(Mutator)); 352 assert (end_off <= rightmost(Mutator), 353 "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, rightmost(Mutator)); 354 355 beg_off = empty_leftmosts[Mutator]; 356 end_off = empty_rightmosts[Mutator]; 357 assert (beg_off >= leftmost_empty(Mutator), 358 "free empty regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, leftmost_empty(Mutator)); 359 assert (end_off <= rightmost_empty(Mutator), 360 "free empty regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, rightmost_empty(Mutator)); 361 362 // Performance invariants. Failing these would not break the free set, but performance would suffer. 363 assert (leftmost(Collector) <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, leftmost(Collector), _max); 364 assert (rightmost(Collector) < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, rightmost(Collector), _max); 365 366 assert (leftmost(Collector) == _max || in_free_set(leftmost(Collector), Collector), 367 "leftmost region should be free: " SIZE_FORMAT, leftmost(Collector)); 368 assert (leftmost(Collector) == _max || in_free_set(rightmost(Collector), Collector), 369 "rightmost region should be free: " SIZE_FORMAT, rightmost(Collector)); 370 371 // If Collector set is empty, leftmosts will both equal max, rightmosts will both equal zero. Likewise for empty region sets. 372 beg_off = leftmosts[Collector]; 373 end_off = rightmosts[Collector]; 374 assert (beg_off >= leftmost(Collector), 375 "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, leftmost(Collector)); 376 assert (end_off <= rightmost(Collector), 377 "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, rightmost(Collector)); 378 379 beg_off = empty_leftmosts[Collector]; 380 end_off = empty_rightmosts[Collector]; 381 assert (beg_off >= leftmost_empty(Collector), 382 "free empty regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, leftmost_empty(Collector)); 383 assert (end_off <= rightmost_empty(Collector), 384 "free empty regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, rightmost_empty(Collector)); 385 386 // Performance invariants. Failing these would not break the free set, but performance would suffer. 387 assert (leftmost(OldCollector) <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, leftmost(OldCollector), _max); 388 assert (rightmost(OldCollector) < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, rightmost(OldCollector), _max); 389 390 assert (leftmost(OldCollector) == _max || in_free_set(leftmost(OldCollector), OldCollector), 391 "leftmost region should be free: " SIZE_FORMAT, leftmost(OldCollector)); 392 assert (leftmost(OldCollector) == _max || in_free_set(rightmost(OldCollector), OldCollector), 393 "rightmost region should be free: " SIZE_FORMAT, rightmost(OldCollector)); 394 395 // If OldCollector set is empty, leftmosts will both equal max, rightmosts will both equal zero. Likewise for empty region sets. 396 beg_off = leftmosts[OldCollector]; 397 end_off = rightmosts[OldCollector]; 398 assert (beg_off >= leftmost(OldCollector), 399 "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, leftmost(OldCollector)); 400 assert (end_off <= rightmost(OldCollector), 401 "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, rightmost(OldCollector)); 402 403 beg_off = empty_leftmosts[OldCollector]; 404 end_off = empty_rightmosts[OldCollector]; 405 assert (beg_off >= leftmost_empty(OldCollector), 406 "free empty regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, leftmost_empty(OldCollector)); 407 assert (end_off <= rightmost_empty(OldCollector), 408 "free empty regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, rightmost_empty(OldCollector)); 409 } 410 #endif 411 412 ShenandoahFreeSet::ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions) : 413 _heap(heap), 414 _free_sets(max_regions, this) 415 { 416 clear_internal(); 417 } 418 419 // This allocates from a region within the old_collector_set. If affiliation equals OLD, the allocation must be taken 420 // from a region that is_old(). Otherwise, affiliation should be FREE, in which case this will put a previously unaffiliated 421 // region into service. 422 HeapWord* ShenandoahFreeSet::allocate_old_with_affiliation(ShenandoahAffiliation affiliation, 423 ShenandoahAllocRequest& req, bool& in_new_region) { 424 shenandoah_assert_heaplocked(); 425 426 size_t rightmost = 427 (affiliation == ShenandoahAffiliation::FREE)? _free_sets.rightmost_empty(OldCollector): _free_sets.rightmost(OldCollector); 428 size_t leftmost = 429 (affiliation == ShenandoahAffiliation::FREE)? _free_sets.leftmost_empty(OldCollector): _free_sets.leftmost(OldCollector); 430 if (_free_sets.alloc_from_left_bias(OldCollector)) { 431 // This mode picks up stragglers left by a full GC 432 for (size_t idx = leftmost; idx <= rightmost; idx++) { 433 if (_free_sets.in_free_set(idx, OldCollector)) { 434 ShenandoahHeapRegion* r = _heap->get_region(idx); 435 assert(r->is_trash() || !r->is_affiliated() || r->is_old(), "old_collector_set region has bad affiliation"); 436 if (r->affiliation() == affiliation) { 437 HeapWord* result = try_allocate_in(r, req, in_new_region); 438 if (result != nullptr) { 439 return result; 440 } 441 } 442 } 443 } 444 } else { 445 // This mode picks up stragglers left by a previous concurrent GC 446 for (size_t count = rightmost + 1; count > leftmost; count--) { 447 // size_t is unsigned, need to dodge underflow when _leftmost = 0 448 size_t idx = count - 1; 449 if (_free_sets.in_free_set(idx, OldCollector)) { 450 ShenandoahHeapRegion* r = _heap->get_region(idx); 451 assert(r->is_trash() || !r->is_affiliated() || r->is_old(), "old_collector_set region has bad affiliation"); 452 if (r->affiliation() == affiliation) { 453 HeapWord* result = try_allocate_in(r, req, in_new_region); 454 if (result != nullptr) { 455 return result; 456 } 457 } 458 } 459 } 460 } 461 return nullptr; 462 } 463 464 void ShenandoahFreeSet::add_old_collector_free_region(ShenandoahHeapRegion* region) { 465 shenandoah_assert_heaplocked(); 466 size_t idx = region->index(); 467 size_t capacity = alloc_capacity(region); 468 assert(_free_sets.membership(idx) == NotFree, "Regions promoted in place should not be in any free set"); 469 if (capacity >= PLAB::min_size() * HeapWordSize) { 470 _free_sets.make_free(idx, OldCollector, capacity); 471 _heap->augment_promo_reserve(capacity); 472 } 473 } 474 475 HeapWord* ShenandoahFreeSet::allocate_with_affiliation(ShenandoahAffiliation affiliation, 476 ShenandoahAllocRequest& req, bool& in_new_region) { 477 shenandoah_assert_heaplocked(); 478 size_t rightmost = 479 (affiliation == ShenandoahAffiliation::FREE)? _free_sets.rightmost_empty(Collector): _free_sets.rightmost(Collector); 480 size_t leftmost = 481 (affiliation == ShenandoahAffiliation::FREE)? _free_sets.leftmost_empty(Collector): _free_sets.leftmost(Collector); 482 for (size_t c = rightmost + 1; c > leftmost; c--) { 483 // size_t is unsigned, need to dodge underflow when _leftmost = 0 484 size_t idx = c - 1; 485 if (_free_sets.in_free_set(idx, Collector)) { 486 ShenandoahHeapRegion* r = _heap->get_region(idx); 487 if (r->affiliation() == affiliation) { 488 HeapWord* result = try_allocate_in(r, req, in_new_region); 489 if (result != nullptr) { 490 return result; 491 } 492 } 493 } 494 } 495 log_debug(gc, free)("Could not allocate collector region with affiliation: %s for request " PTR_FORMAT, 496 shenandoah_affiliation_name(affiliation), p2i(&req)); 497 return nullptr; 498 } 499 500 HeapWord* ShenandoahFreeSet::allocate_single(ShenandoahAllocRequest& req, bool& in_new_region) { 501 shenandoah_assert_heaplocked(); 502 503 // Scan the bitmap looking for a first fit. 504 // 505 // Leftmost and rightmost bounds provide enough caching to walk bitmap efficiently. Normally, 506 // we would find the region to allocate at right away. 507 // 508 // Allocations are biased: new application allocs go to beginning of the heap, and GC allocs 509 // go to the end. This makes application allocation faster, because we would clear lots 510 // of regions from the beginning most of the time. 511 // 512 // Free set maintains mutator and collector views, and normally they allocate in their views only, 513 // unless we special cases for stealing and mixed allocations. 514 515 // Overwrite with non-zero (non-NULL) values only if necessary for allocation bookkeeping. 516 517 bool allow_new_region = true; 518 if (_heap->mode()->is_generational()) { 519 switch (req.affiliation()) { 520 case ShenandoahAffiliation::OLD_GENERATION: 521 // Note: unsigned result from free_unaffiliated_regions() will never be less than zero, but it may equal zero. 522 if (_heap->old_generation()->free_unaffiliated_regions() <= 0) { 523 allow_new_region = false; 524 } 525 break; 526 527 case ShenandoahAffiliation::YOUNG_GENERATION: 528 // Note: unsigned result from free_unaffiliated_regions() will never be less than zero, but it may equal zero. 529 if (_heap->young_generation()->free_unaffiliated_regions() <= 0) { 530 allow_new_region = false; 531 } 532 break; 533 534 case ShenandoahAffiliation::FREE: 535 fatal("Should request affiliation"); 536 537 default: 538 ShouldNotReachHere(); 539 break; 540 } 541 } 542 switch (req.type()) { 543 case ShenandoahAllocRequest::_alloc_tlab: 544 case ShenandoahAllocRequest::_alloc_shared: { 545 // Try to allocate in the mutator view 546 // Allocate within mutator free from high memory to low so as to preserve low memory for humongous allocations 547 if (!_free_sets.is_empty(Mutator)) { 548 // Use signed idx. Otherwise, loop will never terminate. 549 int leftmost = (int) _free_sets.leftmost(Mutator); 550 for (int idx = (int) _free_sets.rightmost(Mutator); idx >= leftmost; idx--) { 551 ShenandoahHeapRegion* r = _heap->get_region(idx); 552 if (_free_sets.in_free_set(idx, Mutator) && (allow_new_region || r->is_affiliated())) { 553 // try_allocate_in() increases used if the allocation is successful. 554 HeapWord* result; 555 size_t min_size = (req.type() == ShenandoahAllocRequest::_alloc_tlab)? req.min_size(): req.size(); 556 if ((alloc_capacity(r) >= min_size) && ((result = try_allocate_in(r, req, in_new_region)) != nullptr)) { 557 return result; 558 } 559 } 560 } 561 } 562 // There is no recovery. Mutator does not touch collector view at all. 563 break; 564 } 565 case ShenandoahAllocRequest::_alloc_gclab: 566 // GCLABs are for evacuation so we must be in evacuation phase. If this allocation is successful, increment 567 // the relevant evac_expended rather than used value. 568 569 case ShenandoahAllocRequest::_alloc_plab: 570 // PLABs always reside in old-gen and are only allocated during evacuation phase. 571 572 case ShenandoahAllocRequest::_alloc_shared_gc: { 573 if (!_heap->mode()->is_generational()) { 574 // size_t is unsigned, need to dodge underflow when _leftmost = 0 575 // Fast-path: try to allocate in the collector view first 576 for (size_t c = _free_sets.rightmost(Collector) + 1; c > _free_sets.leftmost(Collector); c--) { 577 size_t idx = c - 1; 578 if (_free_sets.in_free_set(idx, Collector)) { 579 HeapWord* result = try_allocate_in(_heap->get_region(idx), req, in_new_region); 580 if (result != nullptr) { 581 return result; 582 } 583 } 584 } 585 } else { 586 // First try to fit into a region that is already in use in the same generation. 587 HeapWord* result; 588 if (req.is_old()) { 589 result = allocate_old_with_affiliation(req.affiliation(), req, in_new_region); 590 } else { 591 result = allocate_with_affiliation(req.affiliation(), req, in_new_region); 592 } 593 if (result != nullptr) { 594 return result; 595 } 596 if (allow_new_region) { 597 // Then try a free region that is dedicated to GC allocations. 598 if (req.is_old()) { 599 result = allocate_old_with_affiliation(FREE, req, in_new_region); 600 } else { 601 result = allocate_with_affiliation(FREE, req, in_new_region); 602 } 603 if (result != nullptr) { 604 return result; 605 } 606 } 607 } 608 // No dice. Can we borrow space from mutator view? 609 if (!ShenandoahEvacReserveOverflow) { 610 return nullptr; 611 } 612 613 if (!allow_new_region && req.is_old() && (_heap->young_generation()->free_unaffiliated_regions() > 0)) { 614 // This allows us to flip a mutator region to old_collector 615 allow_new_region = true; 616 } 617 618 // We should expand old-gen if this can prevent an old-gen evacuation failure. We don't care so much about 619 // promotion failures since they can be mitigated in a subsequent GC pass. Would be nice to know if this 620 // allocation request is for evacuation or promotion. Individual threads limit their use of PLAB memory for 621 // promotions, so we already have an assurance that any additional memory set aside for old-gen will be used 622 // only for old-gen evacuations. 623 624 // Also TODO: 625 // if (GC is idle (out of cycle) and mutator allocation fails and there is memory reserved in Collector 626 // or OldCollector sets, transfer a region of memory so that we can satisfy the allocation request, and 627 // immediately trigger the start of GC. Is better to satisfy the allocation than to trigger out-of-cycle 628 // allocation failure (even if this means we have a little less memory to handle evacuations during the 629 // subsequent GC pass). 630 631 if (allow_new_region) { 632 // Try to steal an empty region from the mutator view. 633 for (size_t c = _free_sets.rightmost_empty(Mutator) + 1; c > _free_sets.leftmost_empty(Mutator); c--) { 634 size_t idx = c - 1; 635 if (_free_sets.in_free_set(idx, Mutator)) { 636 ShenandoahHeapRegion* r = _heap->get_region(idx); 637 if (can_allocate_from(r)) { 638 if (req.is_old()) { 639 flip_to_old_gc(r); 640 } else { 641 flip_to_gc(r); 642 } 643 HeapWord *result = try_allocate_in(r, req, in_new_region); 644 if (result != nullptr) { 645 log_debug(gc, free)("Flipped region " SIZE_FORMAT " to gc for request: " PTR_FORMAT, idx, p2i(&req)); 646 return result; 647 } 648 } 649 } 650 } 651 } 652 653 // No dice. Do not try to mix mutator and GC allocations, because 654 // URWM moves due to GC allocations would expose unparsable mutator 655 // allocations. 656 break; 657 } 658 default: 659 ShouldNotReachHere(); 660 } 661 return nullptr; 662 } 663 664 // This work method takes an argument corresponding to the number of bytes 665 // free in a region, and returns the largest amount in heapwords that can be allocated 666 // such that both of the following conditions are satisfied: 667 // 668 // 1. it is a multiple of card size 669 // 2. any remaining shard may be filled with a filler object 670 // 671 // The idea is that the allocation starts and ends at card boundaries. Because 672 // a region ('s end) is card-aligned, the remainder shard that must be filled is 673 // at the start of the free space. 674 // 675 // This is merely a helper method to use for the purpose of such a calculation. 676 size_t get_usable_free_words(size_t free_bytes) { 677 // e.g. card_size is 512, card_shift is 9, min_fill_size() is 8 678 // free is 514 679 // usable_free is 512, which is decreased to 0 680 size_t usable_free = (free_bytes / CardTable::card_size()) << CardTable::card_shift(); 681 assert(usable_free <= free_bytes, "Sanity check"); 682 if ((free_bytes != usable_free) && (free_bytes - usable_free < ShenandoahHeap::min_fill_size() * HeapWordSize)) { 683 // After aligning to card multiples, the remainder would be smaller than 684 // the minimum filler object, so we'll need to take away another card's 685 // worth to construct a filler object. 686 if (usable_free >= CardTable::card_size()) { 687 usable_free -= CardTable::card_size(); 688 } else { 689 assert(usable_free == 0, "usable_free is a multiple of card_size and card_size > min_fill_size"); 690 } 691 } 692 693 return usable_free / HeapWordSize; 694 } 695 696 // Given a size argument, which is a multiple of card size, a request struct 697 // for a PLAB, and an old region, return a pointer to the allocated space for 698 // a PLAB which is card-aligned and where any remaining shard in the region 699 // has been suitably filled by a filler object. 700 // It is assumed (and assertion-checked) that such an allocation is always possible. 701 HeapWord* ShenandoahFreeSet::allocate_aligned_plab(size_t size, ShenandoahAllocRequest& req, ShenandoahHeapRegion* r) { 702 assert(_heap->mode()->is_generational(), "PLABs are only for generational mode"); 703 assert(r->is_old(), "All PLABs reside in old-gen"); 704 assert(!req.is_mutator_alloc(), "PLABs should not be allocated by mutators."); 705 assert(size % CardTable::card_size_in_words() == 0, "size must be multiple of card table size, was " SIZE_FORMAT, size); 706 707 HeapWord* result = r->allocate_aligned(size, req, CardTable::card_size()); 708 assert(result != nullptr, "Allocation cannot fail"); 709 assert(r->top() <= r->end(), "Allocation cannot span end of region"); 710 assert(req.actual_size() == size, "Should not have needed to adjust size for PLAB."); 711 assert(((uintptr_t) result) % CardTable::card_size_in_words() == 0, "PLAB start must align with card boundary"); 712 713 return result; 714 } 715 716 HeapWord* ShenandoahFreeSet::try_allocate_in(ShenandoahHeapRegion* r, ShenandoahAllocRequest& req, bool& in_new_region) { 717 assert (has_alloc_capacity(r), "Performance: should avoid full regions on this path: " SIZE_FORMAT, r->index()); 718 if (_heap->is_concurrent_weak_root_in_progress() && r->is_trash()) { 719 return nullptr; 720 } 721 722 try_recycle_trashed(r); 723 if (!r->is_affiliated()) { 724 ShenandoahMarkingContext* const ctx = _heap->complete_marking_context(); 725 r->set_affiliation(req.affiliation()); 726 if (r->is_old()) { 727 // Any OLD region allocated during concurrent coalesce-and-fill does not need to be coalesced and filled because 728 // all objects allocated within this region are above TAMS (and thus are implicitly marked). In case this is an 729 // OLD region and concurrent preparation for mixed evacuations visits this region before the start of the next 730 // old-gen concurrent mark (i.e. this region is allocated following the start of old-gen concurrent mark but before 731 // concurrent preparations for mixed evacuations are completed), we mark this region as not requiring any 732 // coalesce-and-fill processing. 733 r->end_preemptible_coalesce_and_fill(); 734 _heap->clear_cards_for(r); 735 _heap->old_generation()->increment_affiliated_region_count(); 736 } else { 737 _heap->young_generation()->increment_affiliated_region_count(); 738 } 739 740 assert(ctx->top_at_mark_start(r) == r->bottom(), "Newly established allocation region starts with TAMS equal to bottom"); 741 assert(ctx->is_bitmap_clear_range(ctx->top_bitmap(r), r->end()), "Bitmap above top_bitmap() must be clear"); 742 } else if (r->affiliation() != req.affiliation()) { 743 assert(_heap->mode()->is_generational(), "Request for %s from %s region should only happen in generational mode.", 744 req.affiliation_name(), r->affiliation_name()); 745 return nullptr; 746 } 747 748 in_new_region = r->is_empty(); 749 HeapWord* result = nullptr; 750 751 if (in_new_region) { 752 log_debug(gc, free)("Using new region (" SIZE_FORMAT ") for %s (" PTR_FORMAT ").", 753 r->index(), ShenandoahAllocRequest::alloc_type_to_string(req.type()), p2i(&req)); 754 } 755 756 // req.size() is in words, r->free() is in bytes. 757 if (ShenandoahElasticTLAB && req.is_lab_alloc()) { 758 if (req.type() == ShenandoahAllocRequest::_alloc_plab) { 759 assert(_heap->mode()->is_generational(), "PLABs are only for generational mode"); 760 assert(_free_sets.in_free_set(r->index(), OldCollector), "PLABS must be allocated in old_collector_free regions"); 761 // Need to assure that plabs are aligned on multiple of card region. 762 // Since we have Elastic TLABs, align sizes up. They may be decreased to fit in the usable 763 // memory remaining in the region (which will also be aligned to cards). 764 size_t adjusted_size = align_up(req.size(), CardTable::card_size_in_words()); 765 size_t adjusted_min_size = align_up(req.min_size(), CardTable::card_size_in_words()); 766 size_t usable_free = get_usable_free_words(r->free()); 767 768 if (adjusted_size > usable_free) { 769 adjusted_size = usable_free; 770 } 771 772 if (adjusted_size >= adjusted_min_size) { 773 result = allocate_aligned_plab(adjusted_size, req, r); 774 } 775 // Otherwise, leave result == nullptr because the adjusted size is smaller than min size. 776 } else { 777 // This is a GCLAB or a TLAB allocation 778 size_t adjusted_size = req.size(); 779 size_t free = align_down(r->free() >> LogHeapWordSize, MinObjAlignment); 780 if (adjusted_size > free) { 781 adjusted_size = free; 782 } 783 if (adjusted_size >= req.min_size()) { 784 result = r->allocate(adjusted_size, req); 785 assert (result != nullptr, "Allocation must succeed: free " SIZE_FORMAT ", actual " SIZE_FORMAT, free, adjusted_size); 786 req.set_actual_size(adjusted_size); 787 } else { 788 log_trace(gc, free)("Failed to shrink TLAB or GCLAB request (" SIZE_FORMAT ") in region " SIZE_FORMAT " to " SIZE_FORMAT 789 " because min_size() is " SIZE_FORMAT, req.size(), r->index(), adjusted_size, req.min_size()); 790 } 791 } 792 } else if (req.is_lab_alloc() && req.type() == ShenandoahAllocRequest::_alloc_plab) { 793 794 // inelastic PLAB 795 size_t size = req.size(); 796 size_t usable_free = get_usable_free_words(r->free()); 797 if (size <= usable_free) { 798 result = allocate_aligned_plab(size, req, r); 799 } 800 } else { 801 size_t size = req.size(); 802 result = r->allocate(size, req); 803 if (result != nullptr) { 804 // Record actual allocation size 805 req.set_actual_size(size); 806 } 807 } 808 809 ShenandoahGeneration* generation = _heap->generation_for(req.affiliation()); 810 if (result != nullptr) { 811 // Allocation successful, bump stats: 812 if (req.is_mutator_alloc()) { 813 assert(req.is_young(), "Mutator allocations always come from young generation."); 814 _free_sets.increase_used(Mutator, req.actual_size() * HeapWordSize); 815 } else { 816 assert(req.is_gc_alloc(), "Should be gc_alloc since req wasn't mutator alloc"); 817 818 // For GC allocations, we advance update_watermark because the objects relocated into this memory during 819 // evacuation are not updated during evacuation. For both young and old regions r, it is essential that all 820 // PLABs be made parsable at the end of evacuation. This is enabled by retiring all plabs at end of evacuation. 821 // TODO: Making a PLAB parsable involves placing a filler object in its remnant memory but does not require 822 // that the PLAB be disabled for all future purposes. We may want to introduce a new service to make the 823 // PLABs parsable while still allowing the PLAB to serve future allocation requests that arise during the 824 // next evacuation pass. 825 r->set_update_watermark(r->top()); 826 if (r->is_old()) { 827 assert(req.type() != ShenandoahAllocRequest::_alloc_gclab, "old-gen allocations use PLAB or shared allocation"); 828 // for plabs, we'll sort the difference between evac and promotion usage when we retire the plab 829 } 830 } 831 } 832 833 if (result == nullptr || alloc_capacity(r) < PLAB::min_size() * HeapWordSize) { 834 // Region cannot afford this and is likely to not afford future allocations. Retire it. 835 // 836 // While this seems a bit harsh, especially in the case when this large allocation does not 837 // fit but the next small one would, we are risking to inflate scan times when lots of 838 // almost-full regions precede the fully-empty region where we want to allocate the entire TLAB. 839 840 // Record the remainder as allocation waste 841 size_t idx = r->index(); 842 if (req.is_mutator_alloc()) { 843 size_t waste = r->free(); 844 if (waste > 0) { 845 _free_sets.increase_used(Mutator, waste); 846 // This one request could cause several regions to be "retired", so we must accumulate the waste 847 req.set_waste((waste >> LogHeapWordSize) + req.waste()); 848 } 849 assert(_free_sets.membership(idx) == Mutator, "Must be mutator free: " SIZE_FORMAT, idx); 850 } else { 851 assert(_free_sets.membership(idx) == Collector || _free_sets.membership(idx) == OldCollector, 852 "Must be collector or old-collector free: " SIZE_FORMAT, idx); 853 } 854 // This region is no longer considered free (in any set) 855 _free_sets.remove_from_free_sets(idx); 856 _free_sets.assert_bounds(); 857 } 858 return result; 859 } 860 861 HeapWord* ShenandoahFreeSet::allocate_contiguous(ShenandoahAllocRequest& req) { 862 shenandoah_assert_heaplocked(); 863 864 size_t words_size = req.size(); 865 size_t num = ShenandoahHeapRegion::required_regions(words_size * HeapWordSize); 866 867 assert(req.is_young(), "Humongous regions always allocated in YOUNG"); 868 ShenandoahGeneration* generation = _heap->generation_for(req.affiliation()); 869 870 // Check if there are enough regions left to satisfy allocation. 871 if (_heap->mode()->is_generational()) { 872 size_t avail_young_regions = generation->free_unaffiliated_regions(); 873 if (num > _free_sets.count(Mutator) || (num > avail_young_regions)) { 874 return nullptr; 875 } 876 } else { 877 if (num > _free_sets.count(Mutator)) { 878 return nullptr; 879 } 880 } 881 882 // Find the continuous interval of $num regions, starting from $beg and ending in $end, 883 // inclusive. Contiguous allocations are biased to the beginning. 884 885 size_t beg = _free_sets.leftmost(Mutator); 886 size_t end = beg; 887 888 while (true) { 889 if (end >= _free_sets.max()) { 890 // Hit the end, goodbye 891 return nullptr; 892 } 893 894 // If regions are not adjacent, then current [beg; end] is useless, and we may fast-forward. 895 // If region is not completely free, the current [beg; end] is useless, and we may fast-forward. 896 if (!_free_sets.in_free_set(end, Mutator) || !can_allocate_from(_heap->get_region(end))) { 897 end++; 898 beg = end; 899 continue; 900 } 901 902 if ((end - beg + 1) == num) { 903 // found the match 904 break; 905 } 906 907 end++; 908 } 909 910 size_t remainder = words_size & ShenandoahHeapRegion::region_size_words_mask(); 911 ShenandoahMarkingContext* const ctx = _heap->complete_marking_context(); 912 913 // Initialize regions: 914 for (size_t i = beg; i <= end; i++) { 915 ShenandoahHeapRegion* r = _heap->get_region(i); 916 try_recycle_trashed(r); 917 918 assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous"); 919 assert(r->is_empty(), "Should be empty"); 920 921 if (i == beg) { 922 r->make_humongous_start(); 923 } else { 924 r->make_humongous_cont(); 925 } 926 927 // Trailing region may be non-full, record the remainder there 928 size_t used_words; 929 if ((i == end) && (remainder != 0)) { 930 used_words = remainder; 931 } else { 932 used_words = ShenandoahHeapRegion::region_size_words(); 933 } 934 935 r->set_affiliation(req.affiliation()); 936 r->set_update_watermark(r->bottom()); 937 r->set_top(r->bottom() + used_words); 938 939 // While individual regions report their true use, all humongous regions are marked used in the free set. 940 _free_sets.remove_from_free_sets(r->index()); 941 } 942 _heap->young_generation()->increase_affiliated_region_count(num); 943 944 size_t total_humongous_size = ShenandoahHeapRegion::region_size_bytes() * num; 945 _free_sets.increase_used(Mutator, total_humongous_size); 946 _free_sets.assert_bounds(); 947 req.set_actual_size(words_size); 948 if (remainder != 0) { 949 req.set_waste(ShenandoahHeapRegion::region_size_words() - remainder); 950 } 951 return _heap->get_region(beg)->bottom(); 952 } 953 954 // Returns true iff this region is entirely available, either because it is empty() or because it has been found to represent 955 // immediate trash and we'll be able to immediately recycle it. Note that we cannot recycle immediate trash if 956 // concurrent weak root processing is in progress. 957 bool ShenandoahFreeSet::can_allocate_from(ShenandoahHeapRegion *r) const { 958 return r->is_empty() || (r->is_trash() && !_heap->is_concurrent_weak_root_in_progress()); 959 } 960 961 bool ShenandoahFreeSet::can_allocate_from(size_t idx) const { 962 ShenandoahHeapRegion* r = _heap->get_region(idx); 963 return can_allocate_from(r); 964 } 965 966 size_t ShenandoahFreeSet::alloc_capacity(size_t idx) const { 967 ShenandoahHeapRegion* r = _heap->get_region(idx); 968 return alloc_capacity(r); 969 } 970 971 size_t ShenandoahFreeSet::alloc_capacity(ShenandoahHeapRegion *r) const { 972 if (r->is_trash()) { 973 // This would be recycled on allocation path 974 return ShenandoahHeapRegion::region_size_bytes(); 975 } else { 976 return r->free(); 977 } 978 } 979 980 bool ShenandoahFreeSet::has_alloc_capacity(ShenandoahHeapRegion *r) const { 981 return alloc_capacity(r) > 0; 982 } 983 984 void ShenandoahFreeSet::try_recycle_trashed(ShenandoahHeapRegion *r) { 985 if (r->is_trash()) { 986 r->recycle(); 987 } 988 } 989 990 void ShenandoahFreeSet::recycle_trash() { 991 // lock is not reentrable, check we don't have it 992 shenandoah_assert_not_heaplocked(); 993 994 for (size_t i = 0; i < _heap->num_regions(); i++) { 995 ShenandoahHeapRegion* r = _heap->get_region(i); 996 if (r->is_trash()) { 997 ShenandoahHeapLocker locker(_heap->lock()); 998 try_recycle_trashed(r); 999 } 1000 SpinPause(); // allow allocators to take the lock 1001 } 1002 } 1003 1004 void ShenandoahFreeSet::flip_to_old_gc(ShenandoahHeapRegion* r) { 1005 size_t idx = r->index(); 1006 1007 assert(_free_sets.in_free_set(idx, Mutator), "Should be in mutator view"); 1008 // Note: can_allocate_from(r) means r is entirely empty 1009 assert(can_allocate_from(r), "Should not be allocated"); 1010 1011 size_t region_capacity = alloc_capacity(r); 1012 _free_sets.move_to_set(idx, OldCollector, region_capacity); 1013 _free_sets.assert_bounds(); 1014 _heap->augment_old_evac_reserve(region_capacity); 1015 bool transferred = _heap->generation_sizer()->transfer_to_old(1); 1016 if (!transferred) { 1017 log_warning(gc, free)("Forcing transfer of " SIZE_FORMAT " to old reserve.", idx); 1018 _heap->generation_sizer()->force_transfer_to_old(1); 1019 } 1020 // We do not ensure that the region is no longer trash, relying on try_allocate_in(), which always comes next, 1021 // to recycle trash before attempting to allocate anything in the region. 1022 } 1023 1024 void ShenandoahFreeSet::flip_to_gc(ShenandoahHeapRegion* r) { 1025 size_t idx = r->index(); 1026 1027 assert(_free_sets.in_free_set(idx, Mutator), "Should be in mutator view"); 1028 assert(can_allocate_from(r), "Should not be allocated"); 1029 1030 size_t region_capacity = alloc_capacity(r); 1031 _free_sets.move_to_set(idx, Collector, region_capacity); 1032 _free_sets.assert_bounds(); 1033 1034 // We do not ensure that the region is no longer trash, relying on try_allocate_in(), which always comes next, 1035 // to recycle trash before attempting to allocate anything in the region. 1036 } 1037 1038 void ShenandoahFreeSet::clear() { 1039 shenandoah_assert_heaplocked(); 1040 clear_internal(); 1041 } 1042 1043 void ShenandoahFreeSet::clear_internal() { 1044 _free_sets.clear_all(); 1045 } 1046 1047 // This function places all is_old() regions that have allocation capacity into the old_collector set. It places 1048 // all other regions (not is_old()) that have allocation capacity into the mutator_set. Subsequently, we will 1049 // move some of the mutator regions into the collector set or old_collector set with the intent of packing 1050 // old_collector memory into the highest (rightmost) addresses of the heap and the collector memory into the 1051 // next highest addresses of the heap, with mutator memory consuming the lowest addresses of the heap. 1052 void ShenandoahFreeSet::find_regions_with_alloc_capacity(size_t &young_cset_regions, size_t &old_cset_regions, 1053 size_t &first_old_region, size_t &last_old_region, 1054 size_t &old_region_count) { 1055 first_old_region = _heap->num_regions(); 1056 last_old_region = 0; 1057 old_region_count = 0; 1058 old_cset_regions = 0; 1059 young_cset_regions = 0; 1060 for (size_t idx = 0; idx < _heap->num_regions(); idx++) { 1061 ShenandoahHeapRegion* region = _heap->get_region(idx); 1062 if (region->is_trash()) { 1063 // Trashed regions represent regions that had been in the collection set but have not yet been "cleaned up". 1064 if (region->is_old()) { 1065 old_cset_regions++; 1066 } else { 1067 assert(region->is_young(), "Trashed region should be old or young"); 1068 young_cset_regions++; 1069 } 1070 } else if (region->is_old() && region->is_regular()) { 1071 old_region_count++; 1072 if (first_old_region > idx) { 1073 first_old_region = idx; 1074 } 1075 last_old_region = idx; 1076 } 1077 if (region->is_alloc_allowed() || region->is_trash()) { 1078 assert(!region->is_cset(), "Shouldn't be adding cset regions to the free set"); 1079 assert(_free_sets.in_free_set(idx, NotFree), "We are about to make region free; it should not be free already"); 1080 1081 // Do not add regions that would almost surely fail allocation 1082 if (alloc_capacity(region) < PLAB::min_size() * HeapWordSize) continue; 1083 1084 if (region->is_old()) { 1085 _free_sets.make_free(idx, OldCollector, alloc_capacity(region)); 1086 log_debug(gc, free)( 1087 " Adding Region " SIZE_FORMAT " (Free: " SIZE_FORMAT "%s, Used: " SIZE_FORMAT "%s) to old collector set", 1088 idx, byte_size_in_proper_unit(region->free()), proper_unit_for_byte_size(region->free()), 1089 byte_size_in_proper_unit(region->used()), proper_unit_for_byte_size(region->used())); 1090 } else { 1091 _free_sets.make_free(idx, Mutator, alloc_capacity(region)); 1092 log_debug(gc, free)( 1093 " Adding Region " SIZE_FORMAT " (Free: " SIZE_FORMAT "%s, Used: " SIZE_FORMAT "%s) to mutator set", 1094 idx, byte_size_in_proper_unit(region->free()), proper_unit_for_byte_size(region->free()), 1095 byte_size_in_proper_unit(region->used()), proper_unit_for_byte_size(region->used())); 1096 } 1097 } 1098 } 1099 } 1100 1101 // Move no more than cset_regions from the existing Collector and OldCollector free sets to the Mutator free set. 1102 // This is called from outside the heap lock. 1103 void ShenandoahFreeSet::move_collector_sets_to_mutator(size_t max_xfer_regions) { 1104 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes(); 1105 size_t collector_empty_xfer = 0; 1106 size_t collector_not_empty_xfer = 0; 1107 size_t old_collector_empty_xfer = 0; 1108 1109 // Process empty regions within the Collector free set 1110 if ((max_xfer_regions > 0) && (_free_sets.leftmost_empty(Collector) <= _free_sets.rightmost_empty(Collector))) { 1111 ShenandoahHeapLocker locker(_heap->lock()); 1112 for (size_t idx = _free_sets.leftmost_empty(Collector); 1113 (max_xfer_regions > 0) && (idx <= _free_sets.rightmost_empty(Collector)); idx++) { 1114 if (_free_sets.in_free_set(idx, Collector) && can_allocate_from(idx)) { 1115 _free_sets.move_to_set(idx, Mutator, region_size_bytes); 1116 max_xfer_regions--; 1117 collector_empty_xfer += region_size_bytes; 1118 } 1119 } 1120 } 1121 1122 // Process empty regions within the OldCollector free set 1123 size_t old_collector_regions = 0; 1124 if ((max_xfer_regions > 0) && (_free_sets.leftmost_empty(OldCollector) <= _free_sets.rightmost_empty(OldCollector))) { 1125 ShenandoahHeapLocker locker(_heap->lock()); 1126 for (size_t idx = _free_sets.leftmost_empty(OldCollector); 1127 (max_xfer_regions > 0) && (idx <= _free_sets.rightmost_empty(OldCollector)); idx++) { 1128 if (_free_sets.in_free_set(idx, OldCollector) && can_allocate_from(idx)) { 1129 _free_sets.move_to_set(idx, Mutator, region_size_bytes); 1130 max_xfer_regions--; 1131 old_collector_empty_xfer += region_size_bytes; 1132 old_collector_regions++; 1133 } 1134 } 1135 if (old_collector_regions > 0) { 1136 _heap->generation_sizer()->transfer_to_young(old_collector_regions); 1137 } 1138 } 1139 1140 // If there are any non-empty regions within Collector set, we can also move them to the Mutator free set 1141 if ((max_xfer_regions > 0) && (_free_sets.leftmost(Collector) <= _free_sets.rightmost(Collector))) { 1142 ShenandoahHeapLocker locker(_heap->lock()); 1143 for (size_t idx = _free_sets.leftmost(Collector); (max_xfer_regions > 0) && (idx <= _free_sets.rightmost(Collector)); idx++) { 1144 size_t alloc_capacity = this->alloc_capacity(idx); 1145 if (_free_sets.in_free_set(idx, Collector) && (alloc_capacity > 0)) { 1146 _free_sets.move_to_set(idx, Mutator, alloc_capacity); 1147 max_xfer_regions--; 1148 collector_not_empty_xfer += alloc_capacity; 1149 } 1150 } 1151 } 1152 1153 size_t collector_xfer = collector_empty_xfer + collector_not_empty_xfer; 1154 size_t total_xfer = collector_xfer + old_collector_empty_xfer; 1155 log_info(gc, free)("At start of update refs, moving " SIZE_FORMAT "%s to Mutator free set from Collector Reserve (" 1156 SIZE_FORMAT "%s) and from Old Collector Reserve (" SIZE_FORMAT "%s)", 1157 byte_size_in_proper_unit(total_xfer), proper_unit_for_byte_size(total_xfer), 1158 byte_size_in_proper_unit(collector_xfer), proper_unit_for_byte_size(collector_xfer), 1159 byte_size_in_proper_unit(old_collector_empty_xfer), proper_unit_for_byte_size(old_collector_empty_xfer)); 1160 } 1161 1162 1163 // Overwrite arguments to represent the amount of memory in each generation that is about to be recycled 1164 void ShenandoahFreeSet::prepare_to_rebuild(size_t &young_cset_regions, size_t &old_cset_regions, 1165 size_t &first_old_region, size_t &last_old_region, size_t &old_region_count) { 1166 shenandoah_assert_heaplocked(); 1167 // This resets all state information, removing all regions from all sets. 1168 clear(); 1169 log_debug(gc, free)("Rebuilding FreeSet"); 1170 1171 // This places regions that have alloc_capacity into the old_collector set if they identify as is_old() or the 1172 // mutator set otherwise. 1173 find_regions_with_alloc_capacity(young_cset_regions, old_cset_regions, first_old_region, last_old_region, old_region_count); 1174 } 1175 1176 void ShenandoahFreeSet::rebuild(size_t young_cset_regions, size_t old_cset_regions) { 1177 shenandoah_assert_heaplocked(); 1178 size_t young_reserve, old_reserve; 1179 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes(); 1180 1181 size_t old_capacity = _heap->old_generation()->max_capacity(); 1182 size_t old_available = _heap->old_generation()->available(); 1183 size_t old_unaffiliated_regions = _heap->old_generation()->free_unaffiliated_regions(); 1184 size_t young_capacity = _heap->young_generation()->max_capacity(); 1185 size_t young_available = _heap->young_generation()->available(); 1186 size_t young_unaffiliated_regions = _heap->young_generation()->free_unaffiliated_regions(); 1187 1188 old_unaffiliated_regions += old_cset_regions; 1189 old_available += old_cset_regions * region_size_bytes; 1190 young_unaffiliated_regions += young_cset_regions; 1191 young_available += young_cset_regions * region_size_bytes; 1192 1193 // Consult old-region surplus and deficit to make adjustments to current generation capacities and availability. 1194 // The generation region transfers take place after we rebuild. 1195 size_t old_region_surplus = _heap->get_old_region_surplus(); 1196 size_t old_region_deficit = _heap->get_old_region_deficit(); 1197 1198 if (old_region_surplus > 0) { 1199 size_t xfer_bytes = old_region_surplus * region_size_bytes; 1200 assert(old_region_surplus <= old_unaffiliated_regions, "Cannot transfer regions that are affiliated"); 1201 old_capacity -= xfer_bytes; 1202 old_available -= xfer_bytes; 1203 old_unaffiliated_regions -= old_region_surplus; 1204 young_capacity += xfer_bytes; 1205 young_available += xfer_bytes; 1206 young_unaffiliated_regions += old_region_surplus; 1207 } else if (old_region_deficit > 0) { 1208 size_t xfer_bytes = old_region_deficit * region_size_bytes; 1209 assert(old_region_deficit <= young_unaffiliated_regions, "Cannot transfer regions that are affiliated"); 1210 old_capacity += xfer_bytes; 1211 old_available += xfer_bytes; 1212 old_unaffiliated_regions += old_region_deficit; 1213 young_capacity -= xfer_bytes; 1214 young_available -= xfer_bytes; 1215 young_unaffiliated_regions -= old_region_deficit; 1216 } 1217 1218 // Evac reserve: reserve trailing space for evacuations, with regions reserved for old evacuations placed to the right 1219 // of regions reserved of young evacuations. 1220 if (!_heap->mode()->is_generational()) { 1221 young_reserve = (_heap->max_capacity() / 100) * ShenandoahEvacReserve; 1222 old_reserve = 0; 1223 } else { 1224 // All allocations taken from the old collector set are performed by GC, generally using PLABs for both 1225 // promotions and evacuations. The partition between which old memory is reserved for evacuation and 1226 // which is reserved for promotion is enforced using thread-local variables that prescribe intentons for 1227 // each PLAB's available memory. 1228 if (_heap->has_evacuation_reserve_quantities()) { 1229 // We are rebuilding at the end of final mark, having already established evacuation budgets for this GC pass. 1230 young_reserve = _heap->get_young_evac_reserve(); 1231 old_reserve = _heap->get_promoted_reserve() + _heap->get_old_evac_reserve(); 1232 assert(old_reserve <= old_available, 1233 "Cannot reserve (" SIZE_FORMAT " + " SIZE_FORMAT") more OLD than is available: " SIZE_FORMAT, 1234 _heap->get_promoted_reserve(), _heap->get_old_evac_reserve(), old_available); 1235 } else { 1236 // We are rebuilding at end of GC, so we set aside budgets specified on command line (or defaults) 1237 young_reserve = (young_capacity * ShenandoahEvacReserve) / 100; 1238 // The auto-sizer has already made old-gen large enough to hold all anticipated evacuations and promotions. 1239 // Affiliated old-gen regions are already in the OldCollector free set. Add in the relevant number of 1240 // unaffiliated regions. 1241 old_reserve = old_available; 1242 } 1243 } 1244 1245 // Old available regions that have less than PLAB::min_size() of available memory are not placed into the OldCollector 1246 // free set. Because of this, old_available may not have enough memory to represent the intended reserve. Adjust 1247 // the reserve downward to account for this possibility. This loss is part of the reason why the original budget 1248 // was adjusted with ShenandoahOldEvacWaste and ShenandoahOldPromoWaste multipliers. 1249 if (old_reserve > _free_sets.capacity_of(OldCollector) + old_unaffiliated_regions * region_size_bytes) { 1250 old_reserve = _free_sets.capacity_of(OldCollector) + old_unaffiliated_regions * region_size_bytes; 1251 } 1252 1253 if (young_reserve > young_unaffiliated_regions * region_size_bytes) { 1254 young_reserve = young_unaffiliated_regions * region_size_bytes; 1255 } 1256 1257 reserve_regions(young_reserve, old_reserve); 1258 _free_sets.establish_alloc_bias(OldCollector); 1259 _free_sets.assert_bounds(); 1260 log_status(); 1261 } 1262 1263 // Having placed all regions that have allocation capacity into the mutator set if they identify as is_young() 1264 // or into the old collector set if they identify as is_old(), move some of these regions from the mutator set 1265 // into the collector set or old collector set in order to assure that the memory available for allocations within 1266 // the collector set is at least to_reserve, and the memory available for allocations within the old collector set 1267 // is at least to_reserve_old. 1268 void ShenandoahFreeSet::reserve_regions(size_t to_reserve, size_t to_reserve_old) { 1269 for (size_t i = _heap->num_regions(); i > 0; i--) { 1270 size_t idx = i - 1; 1271 ShenandoahHeapRegion* r = _heap->get_region(idx); 1272 if (!_free_sets.in_free_set(idx, Mutator)) { 1273 continue; 1274 } 1275 1276 size_t ac = alloc_capacity(r); 1277 assert (ac > 0, "Membership in free set implies has capacity"); 1278 assert (!r->is_old(), "mutator_is_free regions should not be affiliated OLD"); 1279 1280 bool move_to_old = _free_sets.capacity_of(OldCollector) < to_reserve_old; 1281 bool move_to_young = _free_sets.capacity_of(Collector) < to_reserve; 1282 1283 if (!move_to_old && !move_to_young) { 1284 // We've satisfied both to_reserve and to_reserved_old 1285 break; 1286 } 1287 1288 if (move_to_old) { 1289 if (r->is_trash() || !r->is_affiliated()) { 1290 // OLD regions that have available memory are already in the old_collector free set 1291 _free_sets.move_to_set(idx, OldCollector, ac); 1292 log_debug(gc, free)(" Shifting region " SIZE_FORMAT " from mutator_free to old_collector_free", idx); 1293 continue; 1294 } 1295 } 1296 1297 if (move_to_young) { 1298 // Note: In a previous implementation, regions were only placed into the survivor space (collector_is_free) if 1299 // they were entirely empty. I'm not sure I understand the rationale for that. That alternative behavior would 1300 // tend to mix survivor objects with ephemeral objects, making it more difficult to reclaim the memory for the 1301 // ephemeral objects. It also delays aging of regions, causing promotion in place to be delayed. 1302 _free_sets.move_to_set(idx, Collector, ac); 1303 log_debug(gc)(" Shifting region " SIZE_FORMAT " from mutator_free to collector_free", idx); 1304 } 1305 } 1306 1307 if (LogTarget(Info, gc, free)::is_enabled()) { 1308 size_t old_reserve = _free_sets.capacity_of(OldCollector); 1309 if (old_reserve < to_reserve_old) { 1310 log_info(gc, free)("Wanted " PROPERFMT " for old reserve, but only reserved: " PROPERFMT, 1311 PROPERFMTARGS(to_reserve_old), PROPERFMTARGS(old_reserve)); 1312 } 1313 size_t young_reserve = _free_sets.capacity_of(Collector); 1314 if (young_reserve < to_reserve) { 1315 log_info(gc, free)("Wanted " PROPERFMT " for young reserve, but only reserved: " PROPERFMT, 1316 PROPERFMTARGS(to_reserve), PROPERFMTARGS(young_reserve)); 1317 } 1318 } 1319 } 1320 1321 void ShenandoahFreeSet::log_status() { 1322 shenandoah_assert_heaplocked(); 1323 1324 #ifdef ASSERT 1325 // Dump of the FreeSet details is only enabled if assertions are enabled 1326 if (LogTarget(Debug, gc, free)::is_enabled()) { 1327 #define BUFFER_SIZE 80 1328 size_t retired_old = 0; 1329 size_t retired_old_humongous = 0; 1330 size_t retired_young = 0; 1331 size_t retired_young_humongous = 0; 1332 size_t region_size_bytes = ShenandoahHeapRegion::region_size_bytes(); 1333 size_t retired_young_waste = 0; 1334 size_t retired_old_waste = 0; 1335 size_t consumed_collector = 0; 1336 size_t consumed_old_collector = 0; 1337 size_t consumed_mutator = 0; 1338 size_t available_old = 0; 1339 size_t available_young = 0; 1340 size_t available_mutator = 0; 1341 size_t available_collector = 0; 1342 size_t available_old_collector = 0; 1343 1344 char buffer[BUFFER_SIZE]; 1345 for (uint i = 0; i < BUFFER_SIZE; i++) { 1346 buffer[i] = '\0'; 1347 } 1348 log_debug(gc, free)("FreeSet map legend:" 1349 " M:mutator_free C:collector_free O:old_collector_free" 1350 " H:humongous ~:retired old _:retired young"); 1351 log_debug(gc, free)(" mutator free range [" SIZE_FORMAT ".." SIZE_FORMAT "], " 1352 " collector free range [" SIZE_FORMAT ".." SIZE_FORMAT "], " 1353 "old collector free range [" SIZE_FORMAT ".." SIZE_FORMAT "] allocates from %s", 1354 _free_sets.leftmost(Mutator), _free_sets.rightmost(Mutator), 1355 _free_sets.leftmost(Collector), _free_sets.rightmost(Collector), 1356 _free_sets.leftmost(OldCollector), _free_sets.rightmost(OldCollector), 1357 _free_sets.alloc_from_left_bias(OldCollector)? "left to right": "right to left"); 1358 1359 for (uint i = 0; i < _heap->num_regions(); i++) { 1360 ShenandoahHeapRegion *r = _heap->get_region(i); 1361 uint idx = i % 64; 1362 if ((i != 0) && (idx == 0)) { 1363 log_debug(gc, free)(" %6u: %s", i-64, buffer); 1364 } 1365 if (_free_sets.in_free_set(i, Mutator)) { 1366 assert(!r->is_old(), "Old regions should not be in mutator_free set"); 1367 size_t capacity = alloc_capacity(r); 1368 available_mutator += capacity; 1369 consumed_mutator += region_size_bytes - capacity; 1370 buffer[idx] = (capacity == region_size_bytes)? 'M': 'm'; 1371 } else if (_free_sets.in_free_set(i, Collector)) { 1372 assert(!r->is_old(), "Old regions should not be in collector_free set"); 1373 size_t capacity = alloc_capacity(r); 1374 available_collector += capacity; 1375 consumed_collector += region_size_bytes - capacity; 1376 buffer[idx] = (capacity == region_size_bytes)? 'C': 'c'; 1377 } else if (_free_sets.in_free_set(i, OldCollector)) { 1378 size_t capacity = alloc_capacity(r); 1379 available_old_collector += capacity; 1380 consumed_old_collector += region_size_bytes - capacity; 1381 buffer[idx] = (capacity == region_size_bytes)? 'O': 'o'; 1382 } else if (r->is_humongous()) { 1383 if (r->is_old()) { 1384 buffer[idx] = 'H'; 1385 retired_old_humongous += region_size_bytes; 1386 } else { 1387 buffer[idx] = 'h'; 1388 retired_young_humongous += region_size_bytes; 1389 } 1390 } else { 1391 if (r->is_old()) { 1392 buffer[idx] = '~'; 1393 retired_old_waste += alloc_capacity(r); 1394 retired_old += region_size_bytes; 1395 } else { 1396 buffer[idx] = '_'; 1397 retired_young_waste += alloc_capacity(r); 1398 retired_young += region_size_bytes; 1399 } 1400 } 1401 } 1402 uint remnant = _heap->num_regions() % 64; 1403 if (remnant > 0) { 1404 buffer[remnant] = '\0'; 1405 } else { 1406 remnant = 64; 1407 } 1408 log_debug(gc, free)(" %6u: %s", (uint) (_heap->num_regions() - remnant), buffer); 1409 size_t total_young = retired_young + retired_young_humongous; 1410 size_t total_old = retired_old + retired_old_humongous; 1411 } 1412 #endif 1413 1414 LogTarget(Info, gc, free) lt; 1415 if (lt.is_enabled()) { 1416 ResourceMark rm; 1417 LogStream ls(lt); 1418 1419 { 1420 size_t last_idx = 0; 1421 size_t max = 0; 1422 size_t max_contig = 0; 1423 size_t empty_contig = 0; 1424 1425 size_t total_used = 0; 1426 size_t total_free = 0; 1427 size_t total_free_ext = 0; 1428 1429 for (size_t idx = _free_sets.leftmost(Mutator); idx <= _free_sets.rightmost(Mutator); idx++) { 1430 if (_free_sets.in_free_set(idx, Mutator)) { 1431 ShenandoahHeapRegion *r = _heap->get_region(idx); 1432 size_t free = alloc_capacity(r); 1433 max = MAX2(max, free); 1434 if (r->is_empty()) { 1435 total_free_ext += free; 1436 if (last_idx + 1 == idx) { 1437 empty_contig++; 1438 } else { 1439 empty_contig = 1; 1440 } 1441 } else { 1442 empty_contig = 0; 1443 } 1444 total_used += r->used(); 1445 total_free += free; 1446 max_contig = MAX2(max_contig, empty_contig); 1447 last_idx = idx; 1448 } 1449 } 1450 1451 size_t max_humongous = max_contig * ShenandoahHeapRegion::region_size_bytes(); 1452 size_t free = capacity() - used(); 1453 1454 assert(free == total_free, "Sum of free within mutator regions (" SIZE_FORMAT 1455 ") should match mutator capacity (" SIZE_FORMAT ") minus mutator used (" SIZE_FORMAT ")", 1456 total_free, capacity(), used()); 1457 1458 ls.print("Free: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s regular, " SIZE_FORMAT "%s humongous, ", 1459 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free), 1460 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max), 1461 byte_size_in_proper_unit(max_humongous), proper_unit_for_byte_size(max_humongous) 1462 ); 1463 1464 ls.print("Frag: "); 1465 size_t frag_ext; 1466 if (total_free_ext > 0) { 1467 frag_ext = 100 - (100 * max_humongous / total_free_ext); 1468 } else { 1469 frag_ext = 0; 1470 } 1471 ls.print(SIZE_FORMAT "%% external, ", frag_ext); 1472 1473 size_t frag_int; 1474 if (_free_sets.count(Mutator) > 0) { 1475 frag_int = (100 * (total_used / _free_sets.count(Mutator)) / ShenandoahHeapRegion::region_size_bytes()); 1476 } else { 1477 frag_int = 0; 1478 } 1479 ls.print(SIZE_FORMAT "%% internal; ", frag_int); 1480 ls.print("Used: " SIZE_FORMAT "%s, Mutator Free: " SIZE_FORMAT, 1481 byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used), _free_sets.count(Mutator)); 1482 } 1483 1484 { 1485 size_t max = 0; 1486 size_t total_free = 0; 1487 size_t total_used = 0; 1488 1489 for (size_t idx = _free_sets.leftmost(Collector); idx <= _free_sets.rightmost(Collector); idx++) { 1490 if (_free_sets.in_free_set(idx, Collector)) { 1491 ShenandoahHeapRegion *r = _heap->get_region(idx); 1492 size_t free = alloc_capacity(r); 1493 max = MAX2(max, free); 1494 total_free += free; 1495 total_used += r->used(); 1496 } 1497 } 1498 ls.print(" Collector Reserve: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s; Used: " SIZE_FORMAT "%s", 1499 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free), 1500 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max), 1501 byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used)); 1502 } 1503 1504 if (_heap->mode()->is_generational()) { 1505 size_t max = 0; 1506 size_t total_free = 0; 1507 size_t total_used = 0; 1508 1509 for (size_t idx = _free_sets.leftmost(OldCollector); idx <= _free_sets.rightmost(OldCollector); idx++) { 1510 if (_free_sets.in_free_set(idx, OldCollector)) { 1511 ShenandoahHeapRegion *r = _heap->get_region(idx); 1512 size_t free = alloc_capacity(r); 1513 max = MAX2(max, free); 1514 total_free += free; 1515 total_used += r->used(); 1516 } 1517 } 1518 ls.print_cr(" Old Collector Reserve: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s; Used: " SIZE_FORMAT "%s", 1519 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free), 1520 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max), 1521 byte_size_in_proper_unit(total_used), proper_unit_for_byte_size(total_used)); 1522 } 1523 } 1524 } 1525 1526 HeapWord* ShenandoahFreeSet::allocate(ShenandoahAllocRequest& req, bool& in_new_region) { 1527 shenandoah_assert_heaplocked(); 1528 1529 // Allocation request is known to satisfy all memory budgeting constraints. 1530 if (req.size() > ShenandoahHeapRegion::humongous_threshold_words()) { 1531 switch (req.type()) { 1532 case ShenandoahAllocRequest::_alloc_shared: 1533 case ShenandoahAllocRequest::_alloc_shared_gc: 1534 in_new_region = true; 1535 return allocate_contiguous(req); 1536 case ShenandoahAllocRequest::_alloc_plab: 1537 case ShenandoahAllocRequest::_alloc_gclab: 1538 case ShenandoahAllocRequest::_alloc_tlab: 1539 in_new_region = false; 1540 assert(false, "Trying to allocate TLAB larger than the humongous threshold: " SIZE_FORMAT " > " SIZE_FORMAT, 1541 req.size(), ShenandoahHeapRegion::humongous_threshold_words()); 1542 return nullptr; 1543 default: 1544 ShouldNotReachHere(); 1545 return nullptr; 1546 } 1547 } else { 1548 return allocate_single(req, in_new_region); 1549 } 1550 } 1551 1552 size_t ShenandoahFreeSet::unsafe_peek_free() const { 1553 // Deliberately not locked, this method is unsafe when free set is modified. 1554 1555 for (size_t index = _free_sets.leftmost(Mutator); index <= _free_sets.rightmost(Mutator); index++) { 1556 if (index < _free_sets.max() && _free_sets.in_free_set(index, Mutator)) { 1557 ShenandoahHeapRegion* r = _heap->get_region(index); 1558 if (r->free() >= MinTLABSize) { 1559 return r->free(); 1560 } 1561 } 1562 } 1563 1564 // It appears that no regions left 1565 return 0; 1566 } 1567 1568 void ShenandoahFreeSet::print_on(outputStream* out) const { 1569 out->print_cr("Mutator Free Set: " SIZE_FORMAT "", _free_sets.count(Mutator)); 1570 for (size_t index = _free_sets.leftmost(Mutator); index <= _free_sets.rightmost(Mutator); index++) { 1571 if (_free_sets.in_free_set(index, Mutator)) { 1572 _heap->get_region(index)->print_on(out); 1573 } 1574 } 1575 out->print_cr("Collector Free Set: " SIZE_FORMAT "", _free_sets.count(Collector)); 1576 for (size_t index = _free_sets.leftmost(Collector); index <= _free_sets.rightmost(Collector); index++) { 1577 if (_free_sets.in_free_set(index, Collector)) { 1578 _heap->get_region(index)->print_on(out); 1579 } 1580 } 1581 if (_heap->mode()->is_generational()) { 1582 out->print_cr("Old Collector Free Set: " SIZE_FORMAT "", _free_sets.count(OldCollector)); 1583 for (size_t index = _free_sets.leftmost(OldCollector); index <= _free_sets.rightmost(OldCollector); index++) { 1584 if (_free_sets.in_free_set(index, OldCollector)) { 1585 _heap->get_region(index)->print_on(out); 1586 } 1587 } 1588 } 1589 } 1590 1591 /* 1592 * Internal fragmentation metric: describes how fragmented the heap regions are. 1593 * 1594 * It is derived as: 1595 * 1596 * sum(used[i]^2, i=0..k) 1597 * IF = 1 - ------------------------------ 1598 * C * sum(used[i], i=0..k) 1599 * 1600 * ...where k is the number of regions in computation, C is the region capacity, and 1601 * used[i] is the used space in the region. 1602 * 1603 * The non-linearity causes IF to be lower for the cases where the same total heap 1604 * used is densely packed. For example: 1605 * a) Heap is completely full => IF = 0 1606 * b) Heap is half full, first 50% regions are completely full => IF = 0 1607 * c) Heap is half full, each region is 50% full => IF = 1/2 1608 * d) Heap is quarter full, first 50% regions are completely full => IF = 0 1609 * e) Heap is quarter full, each region is 25% full => IF = 3/4 1610 * f) Heap has one small object per each region => IF =~ 1 1611 */ 1612 double ShenandoahFreeSet::internal_fragmentation() { 1613 double squared = 0; 1614 double linear = 0; 1615 int count = 0; 1616 1617 for (size_t index = _free_sets.leftmost(Mutator); index <= _free_sets.rightmost(Mutator); index++) { 1618 if (_free_sets.in_free_set(index, Mutator)) { 1619 ShenandoahHeapRegion* r = _heap->get_region(index); 1620 size_t used = r->used(); 1621 squared += used * used; 1622 linear += used; 1623 count++; 1624 } 1625 } 1626 1627 if (count > 0) { 1628 double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear); 1629 return 1 - s; 1630 } else { 1631 return 0; 1632 } 1633 } 1634 1635 /* 1636 * External fragmentation metric: describes how fragmented the heap is. 1637 * 1638 * It is derived as: 1639 * 1640 * EF = 1 - largest_contiguous_free / total_free 1641 * 1642 * For example: 1643 * a) Heap is completely empty => EF = 0 1644 * b) Heap is completely full => EF = 0 1645 * c) Heap is first-half full => EF = 1/2 1646 * d) Heap is half full, full and empty regions interleave => EF =~ 1 1647 */ 1648 double ShenandoahFreeSet::external_fragmentation() { 1649 size_t last_idx = 0; 1650 size_t max_contig = 0; 1651 size_t empty_contig = 0; 1652 1653 size_t free = 0; 1654 1655 for (size_t index = _free_sets.leftmost(Mutator); index <= _free_sets.rightmost(Mutator); index++) { 1656 if (_free_sets.in_free_set(index, Mutator)) { 1657 ShenandoahHeapRegion* r = _heap->get_region(index); 1658 if (r->is_empty()) { 1659 free += ShenandoahHeapRegion::region_size_bytes(); 1660 if (last_idx + 1 == index) { 1661 empty_contig++; 1662 } else { 1663 empty_contig = 1; 1664 } 1665 } else { 1666 empty_contig = 0; 1667 } 1668 1669 max_contig = MAX2(max_contig, empty_contig); 1670 last_idx = index; 1671 } 1672 } 1673 1674 if (free > 0) { 1675 return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free); 1676 } else { 1677 return 0; 1678 } 1679 } 1680