1 /* 2 * Copyright (c) 2016, 2021, Red Hat, Inc. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #include "precompiled.hpp" 26 #include "gc/shared/tlab_globals.hpp" 27 #include "gc/shenandoah/shenandoahBarrierSet.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/shenandoahOldGeneration.hpp" 33 #include "gc/shenandoah/shenandoahScanRemembered.inline.hpp" 34 #include "gc/shenandoah/shenandoahYoungGeneration.hpp" 35 #include "logging/logStream.hpp" 36 #include "memory/resourceArea.hpp" 37 #include "runtime/orderAccess.hpp" 38 39 ShenandoahFreeSet::ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions) : 40 _heap(heap), 41 _mutator_free_bitmap(max_regions, mtGC), 42 _collector_free_bitmap(max_regions, mtGC), 43 _max(max_regions) 44 { 45 clear_internal(); 46 } 47 48 void ShenandoahFreeSet::increase_used(size_t num_bytes) { 49 shenandoah_assert_heaplocked(); 50 _used += num_bytes; 51 52 assert(_used <= _capacity, "must not use more than we have: used: " SIZE_FORMAT 53 ", capacity: " SIZE_FORMAT ", num_bytes: " SIZE_FORMAT, _used, _capacity, num_bytes); 54 } 55 56 bool ShenandoahFreeSet::is_mutator_free(size_t idx) const { 57 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT " (left: " SIZE_FORMAT ", right: " SIZE_FORMAT ")", 58 idx, _max, _mutator_leftmost, _mutator_rightmost); 59 return _mutator_free_bitmap.at(idx); 60 } 61 62 bool ShenandoahFreeSet::is_collector_free(size_t idx) const { 63 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT " (left: " SIZE_FORMAT ", right: " SIZE_FORMAT ")", 64 idx, _max, _collector_leftmost, _collector_rightmost); 65 return _collector_free_bitmap.at(idx); 66 } 67 68 // This is a temporary solution to work around a shortcoming with the existing free set implementation. 69 // TODO: 70 // Remove this function after restructing FreeSet representation. A problem in the existing implementation is that old-gen 71 // regions are not considered to reside within the is_collector_free range. 72 // 73 HeapWord* ShenandoahFreeSet::allocate_with_old_affiliation(ShenandoahAllocRequest& req, bool& in_new_region) { 74 ShenandoahRegionAffiliation affiliation = ShenandoahRegionAffiliation::OLD_GENERATION; 75 76 size_t rightmost = MAX2(_collector_rightmost, _mutator_rightmost); 77 size_t leftmost = MIN2(_collector_leftmost, _mutator_leftmost); 78 79 for (size_t c = rightmost + 1; c > leftmost; c--) { 80 // size_t is unsigned, need to dodge underflow when _leftmost = 0 81 size_t idx = c - 1; 82 ShenandoahHeapRegion* r = _heap->get_region(idx); 83 if (r->affiliation() == affiliation && !r->is_humongous()) { 84 if (!r->is_cset() && !has_no_alloc_capacity(r)) { 85 HeapWord* result = try_allocate_in(r, req, in_new_region); 86 if (result != NULL) { 87 return result; 88 } 89 } 90 } 91 } 92 return nullptr; 93 } 94 95 HeapWord* ShenandoahFreeSet::allocate_with_affiliation(ShenandoahRegionAffiliation affiliation, ShenandoahAllocRequest& req, bool& in_new_region) { 96 for (size_t c = _collector_rightmost + 1; c > _collector_leftmost; c--) { 97 // size_t is unsigned, need to dodge underflow when _leftmost = 0 98 size_t idx = c - 1; 99 if (is_collector_free(idx)) { 100 ShenandoahHeapRegion* r = _heap->get_region(idx); 101 if (r->affiliation() == affiliation) { 102 HeapWord* result = try_allocate_in(r, req, in_new_region); 103 if (result != NULL) { 104 return result; 105 } 106 } 107 } 108 } 109 return NULL; 110 } 111 112 HeapWord* ShenandoahFreeSet::allocate_single(ShenandoahAllocRequest& req, bool& in_new_region) { 113 // Scan the bitmap looking for a first fit. 114 // 115 // Leftmost and rightmost bounds provide enough caching to walk bitmap efficiently. Normally, 116 // we would find the region to allocate at right away. 117 // 118 // Allocations are biased: new application allocs go to beginning of the heap, and GC allocs 119 // go to the end. This makes application allocation faster, because we would clear lots 120 // of regions from the beginning most of the time. 121 // 122 // Free set maintains mutator and collector views, and normally they allocate in their views only, 123 // unless we special cases for stealing and mixed allocations. 124 125 // Overwrite with non-zero (non-NULL) values only if necessary for allocation bookkeeping. 126 127 bool allow_new_region = true; 128 switch (req.affiliation()) { 129 case ShenandoahRegionAffiliation::OLD_GENERATION: 130 // Note: unsigned result from adjusted_unaffiliated_regions() will never be less than zero, but it may equal zero. 131 if (_heap->old_generation()->adjusted_unaffiliated_regions() <= 0) { 132 allow_new_region = false; 133 } 134 break; 135 136 case ShenandoahRegionAffiliation::YOUNG_GENERATION: 137 // Note: unsigned result from adjusted_unaffiliated_regions() will never be less than zero, but it may equal zero. 138 if (_heap->young_generation()->adjusted_unaffiliated_regions() <= 0) { 139 allow_new_region = false; 140 } 141 break; 142 143 case ShenandoahRegionAffiliation::FREE: 144 default: 145 ShouldNotReachHere(); 146 break; 147 } 148 149 switch (req.type()) { 150 case ShenandoahAllocRequest::_alloc_tlab: 151 case ShenandoahAllocRequest::_alloc_shared: { 152 // Try to allocate in the mutator view 153 for (size_t idx = _mutator_leftmost; idx <= _mutator_rightmost; idx++) { 154 ShenandoahHeapRegion* r = _heap->get_region(idx); 155 if (is_mutator_free(idx) && (allow_new_region || r->affiliation() != ShenandoahRegionAffiliation::FREE)) { 156 // try_allocate_in() increases used if the allocation is successful. 157 HeapWord* result = try_allocate_in(r, req, in_new_region); 158 if (result != NULL) { 159 return result; 160 } 161 } 162 } 163 // There is no recovery. Mutator does not touch collector view at all. 164 break; 165 } 166 case ShenandoahAllocRequest::_alloc_gclab: 167 // GCLABs are for evacuation so we must be in evacuation phase. If this allocation is successful, increment 168 // the relevant evac_expended rather than used value. 169 170 case ShenandoahAllocRequest::_alloc_plab: 171 // PLABs always reside in old-gen and are only allocated during evacuation phase. 172 173 case ShenandoahAllocRequest::_alloc_shared_gc: { 174 // First try to fit into a region that is already in use in the same generation. 175 HeapWord* result; 176 if (req.affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION) { 177 // TODO: this is a work around to address a deficiency in FreeSet representation. A better solution fixes 178 // the FreeSet implementation to deal more efficiently with old-gen regions as being in the "collector free set" 179 result = allocate_with_old_affiliation(req, in_new_region); 180 } else { 181 result = allocate_with_affiliation(req.affiliation(), req, in_new_region); 182 } 183 if (result != NULL) { 184 return result; 185 } 186 if (allow_new_region) { 187 // Then try a free region that is dedicated to GC allocations. 188 result = allocate_with_affiliation(FREE, req, in_new_region); 189 if (result != NULL) { 190 return result; 191 } 192 } 193 194 // No dice. Can we borrow space from mutator view? 195 if (!ShenandoahEvacReserveOverflow) { 196 return NULL; 197 } 198 199 if (allow_new_region) { 200 // Try to steal an empty region from the mutator view. 201 for (size_t c = _mutator_rightmost + 1; c > _mutator_leftmost; c--) { 202 size_t idx = c - 1; 203 if (is_mutator_free(idx)) { 204 ShenandoahHeapRegion* r = _heap->get_region(idx); 205 if (can_allocate_from(r)) { 206 flip_to_gc(r); 207 HeapWord *result = try_allocate_in(r, req, in_new_region); 208 if (result != NULL) { 209 return result; 210 } 211 } 212 } 213 } 214 } 215 216 // No dice. Do not try to mix mutator and GC allocations, because 217 // URWM moves due to GC allocations would expose unparsable mutator 218 // allocations. 219 break; 220 } 221 default: 222 ShouldNotReachHere(); 223 } 224 return NULL; 225 } 226 227 HeapWord* ShenandoahFreeSet::try_allocate_in(ShenandoahHeapRegion* r, ShenandoahAllocRequest& req, bool& in_new_region) { 228 assert (!has_no_alloc_capacity(r), "Performance: should avoid full regions on this path: " SIZE_FORMAT, r->index()); 229 230 if (_heap->is_concurrent_weak_root_in_progress() && 231 r->is_trash()) { 232 return NULL; 233 } 234 try_recycle_trashed(r); 235 if (r->affiliation() == ShenandoahRegionAffiliation::FREE) { 236 ShenandoahMarkingContext* const ctx = _heap->complete_marking_context(); 237 r->set_affiliation(req.affiliation()); 238 if (r->is_old()) { 239 // Any OLD region allocated during concurrent coalesce-and-fill does not need to be coalesced and filled because 240 // all objects allocated within this region are above TAMS (and thus are implicitly marked). In case this is an 241 // OLD region and concurrent preparation for mixed evacuations visits this region before the start of the next 242 // old-gen concurrent mark (i.e. this region is allocated following the start of old-gen concurrent mark but before 243 // concurrent preparations for mixed evacuations are completed), we mark this region as not requiring any 244 // coalesce-and-fill processing. 245 r->end_preemptible_coalesce_and_fill(); 246 _heap->clear_cards_for(r); 247 } 248 249 assert(ctx->top_at_mark_start(r) == r->bottom(), "Newly established allocation region starts with TAMS equal to bottom"); 250 assert(ctx->is_bitmap_clear_range(ctx->top_bitmap(r), r->end()), "Bitmap above top_bitmap() must be clear"); 251 252 // Leave top_bitmap alone. The first time a heap region is put into service, top_bitmap should equal end. 253 // Thereafter, it should represent the upper bound on parts of the bitmap that need to be cleared. 254 log_debug(gc)("NOT clearing bitmap for region " SIZE_FORMAT ", top_bitmap: " 255 PTR_FORMAT " at transition from FREE to %s", 256 r->index(), p2i(ctx->top_bitmap(r)), affiliation_name(req.affiliation())); 257 } else if (r->affiliation() != req.affiliation()) { 258 return NULL; 259 } 260 261 in_new_region = r->is_empty(); 262 HeapWord* result = NULL; 263 size_t size = req.size(); 264 265 // req.size() is in words, r->free() is in bytes. 266 if (ShenandoahElasticTLAB && req.is_lab_alloc()) { 267 if (req.type() == ShenandoahAllocRequest::_alloc_plab) { 268 // Need to assure that plabs are aligned on multiple of card region. 269 size_t free = r->free(); 270 size_t usable_free = (free / CardTable::card_size()) << CardTable::card_shift(); 271 if ((free != usable_free) && (free - usable_free < ShenandoahHeap::min_fill_size() * HeapWordSize)) { 272 // We'll have to add another card's memory to the padding 273 if (usable_free > CardTable::card_size()) { 274 usable_free -= CardTable::card_size(); 275 } else { 276 assert(usable_free == 0, "usable_free is a multiple of card_size and card_size > min_fill_size"); 277 } 278 } 279 free /= HeapWordSize; 280 usable_free /= HeapWordSize; 281 size_t remnant = size % CardTable::card_size_in_words(); 282 if (remnant > 0) { 283 // Since we have Elastic TLABs, align size up. This is consistent with aligning min_size up. 284 size = size - remnant + CardTable::card_size_in_words(); 285 } 286 if (size > usable_free) { 287 size = usable_free; 288 assert(size % CardTable::card_size_in_words() == 0, "usable_free is a multiple of card table size"); 289 } 290 291 size_t adjusted_min_size = req.min_size(); 292 remnant = adjusted_min_size % CardTable::card_size_in_words(); 293 if (remnant > 0) { 294 // Round up adjusted_min_size to a multiple of alignment size 295 adjusted_min_size = adjusted_min_size - remnant + CardTable::card_size_in_words(); 296 } 297 if (size >= adjusted_min_size) { 298 result = r->allocate_aligned(size, req, CardTable::card_size()); 299 assert(result != nullptr, "Allocation cannot fail"); 300 size = req.actual_size(); 301 assert(r->top() <= r->end(), "Allocation cannot span end of region"); 302 // actual_size() will be set to size below. 303 assert((result == nullptr) || (size % CardTable::card_size_in_words() == 0), 304 "PLAB size must be multiple of card size"); 305 assert((result == nullptr) || (((uintptr_t) result) % CardTable::card_size_in_words() == 0), 306 "PLAB start must align with card boundary"); 307 if (free > usable_free) { 308 // Account for the alignment padding 309 size_t padding = (free - usable_free) * HeapWordSize; 310 increase_used(padding); 311 assert(r->affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION, "All PLABs reside in old-gen"); 312 _heap->old_generation()->increase_used(padding); 313 // For verification consistency, we need to report this padding to _heap 314 _heap->increase_used(padding); 315 } 316 } 317 // Otherwise, leave result == NULL because the adjusted size is smaller than min size. 318 } else { 319 // This is a GCLAB or a TLAB allocation 320 size_t free = align_down(r->free() >> LogHeapWordSize, MinObjAlignment); 321 if (size > free) { 322 size = free; 323 } 324 if (size >= req.min_size()) { 325 result = r->allocate(size, req); 326 if (result != nullptr) { 327 // Record actual allocation size 328 req.set_actual_size(size); 329 } 330 assert (result != NULL, "Allocation must succeed: free " SIZE_FORMAT ", actual " SIZE_FORMAT, free, size); 331 } else { 332 log_trace(gc, ergo)("Failed to shrink TLAB or GCLAB request (" SIZE_FORMAT ") in region " SIZE_FORMAT " to " SIZE_FORMAT 333 " because min_size() is " SIZE_FORMAT, req.size(), r->index(), size, req.min_size()); 334 } 335 } 336 } else if (req.is_lab_alloc() && req.type() == ShenandoahAllocRequest::_alloc_plab) { 337 // inelastic PLAB 338 size_t free = r->free(); 339 size_t usable_free = (free / CardTable::card_size()) << CardTable::card_shift(); 340 free /= HeapWordSize; 341 usable_free /= HeapWordSize; 342 if ((free != usable_free) && (free - usable_free < ShenandoahHeap::min_fill_size() * HeapWordSize)) { 343 // We'll have to add another card's memory to the padding 344 if (usable_free > CardTable::card_size_in_words()) { 345 usable_free -= CardTable::card_size_in_words(); 346 } else { 347 assert(usable_free == 0, "usable_free is a multiple of card_size and card_size > min_fill_size"); 348 } 349 } 350 assert(size % CardTable::card_size_in_words() == 0, "PLAB size must be multiple of remembered set card size"); 351 if (size <= usable_free) { 352 result = r->allocate_aligned(size, req, CardTable::card_size()); 353 size = req.actual_size(); 354 assert(result != nullptr, "Allocation cannot fail"); 355 assert(r->top() <= r->end(), "Allocation cannot span end of region"); 356 assert(req.actual_size() % CardTable::card_size_in_words() == 0, "PLAB start must align with card boundary"); 357 assert(((uintptr_t) result) % CardTable::card_size_in_words() == 0, "PLAB start must align with card boundary"); 358 if (free > usable_free) { 359 // Account for the alignment padding 360 size_t padding = (free - usable_free) * HeapWordSize; 361 increase_used(padding); 362 assert(r->affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION, "All PLABs reside in old-gen"); 363 _heap->old_generation()->increase_used(padding); 364 // For verification consistency, we need to report this padding to _heap 365 _heap->increase_used(padding); 366 } 367 } 368 } else { 369 result = r->allocate(size, req); 370 if (result != nullptr) { 371 // Record actual allocation size 372 req.set_actual_size(size); 373 } 374 } 375 376 if (result != NULL) { 377 // Allocation successful, bump stats: 378 if (req.is_mutator_alloc()) { 379 // Mutator allocations always pull from young gen. 380 _heap->young_generation()->increase_used(size * HeapWordSize); 381 increase_used(size * HeapWordSize); 382 } else { 383 assert(req.is_gc_alloc(), "Should be gc_alloc since req wasn't mutator alloc"); 384 385 // For GC allocations, we advance update_watermark because the objects relocated into this memory during 386 // evacuation are not updated during evacuation. For both young and old regions r, it is essential that all 387 // PLABs be made parsable at the end of evacuation. This is enabled by retiring all plabs at end of evacuation. 388 // TODO: Making a PLAB parsable involves placing a filler object in its remnant memory but does not require 389 // that the PLAB be disabled for all future purposes. We may want to introduce a new service to make the 390 // PLABs parsable while still allowing the PLAB to serve future allocation requests that arise during the 391 // next evacuation pass. 392 r->set_update_watermark(r->top()); 393 394 if (r->affiliation() == ShenandoahRegionAffiliation::YOUNG_GENERATION) { 395 _heap->young_generation()->increase_used(size * HeapWordSize); 396 } else { 397 assert(r->affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION, "GC Alloc was not YOUNG so must be OLD"); 398 assert(req.type() != ShenandoahAllocRequest::_alloc_gclab, "old-gen allocations use PLAB or shared allocation"); 399 _heap->old_generation()->increase_used(size * HeapWordSize); 400 // for plabs, we'll sort the difference between evac and promotion usage when we retire the plab 401 } 402 } 403 } 404 if (result == NULL || has_no_alloc_capacity(r)) { 405 // Region cannot afford this or future allocations. Retire it. 406 // 407 // While this seems a bit harsh, especially in the case when this large allocation does not 408 // fit, but the next small one would, we are risking to inflate scan times when lots of 409 // almost-full regions precede the fully-empty region where we want to allocate the entire TLAB. 410 // TODO: Record first fully-empty region, and use that for large allocations and/or organize 411 // available free segments within regions for more efficient searches for "good fit". 412 413 // Record the remainder as allocation waste 414 if (req.is_mutator_alloc()) { 415 size_t waste = r->free(); 416 if (waste > 0) { 417 increase_used(waste); 418 _heap->generation_for(req.affiliation())->increase_allocated(waste); 419 _heap->notify_mutator_alloc_words(waste >> LogHeapWordSize, true); 420 } 421 } 422 423 size_t num = r->index(); 424 _collector_free_bitmap.clear_bit(num); 425 _mutator_free_bitmap.clear_bit(num); 426 // Touched the bounds? Need to update: 427 if (touches_bounds(num)) { 428 adjust_bounds(); 429 } 430 assert_bounds(); 431 } 432 return result; 433 } 434 435 bool ShenandoahFreeSet::touches_bounds(size_t num) const { 436 return num == _collector_leftmost || num == _collector_rightmost || num == _mutator_leftmost || num == _mutator_rightmost; 437 } 438 439 void ShenandoahFreeSet::recompute_bounds() { 440 // Reset to the most pessimistic case: 441 _mutator_rightmost = _max - 1; 442 _mutator_leftmost = 0; 443 _collector_rightmost = _max - 1; 444 _collector_leftmost = 0; 445 446 // ...and adjust from there 447 adjust_bounds(); 448 } 449 450 void ShenandoahFreeSet::adjust_bounds() { 451 // Rewind both mutator bounds until the next bit. 452 while (_mutator_leftmost < _max && !is_mutator_free(_mutator_leftmost)) { 453 _mutator_leftmost++; 454 } 455 while (_mutator_rightmost > 0 && !is_mutator_free(_mutator_rightmost)) { 456 _mutator_rightmost--; 457 } 458 // Rewind both collector bounds until the next bit. 459 while (_collector_leftmost < _max && !is_collector_free(_collector_leftmost)) { 460 _collector_leftmost++; 461 } 462 while (_collector_rightmost > 0 && !is_collector_free(_collector_rightmost)) { 463 _collector_rightmost--; 464 } 465 } 466 467 HeapWord* ShenandoahFreeSet::allocate_contiguous(ShenandoahAllocRequest& req) { 468 shenandoah_assert_heaplocked(); 469 470 size_t words_size = req.size(); 471 size_t num = ShenandoahHeapRegion::required_regions(words_size * HeapWordSize); 472 473 assert(req.affiliation() == ShenandoahRegionAffiliation::YOUNG_GENERATION, "Humongous regions always allocated in YOUNG"); 474 size_t avail_young_regions = _heap->young_generation()->adjusted_unaffiliated_regions(); 475 476 // No regions left to satisfy allocation, bye. 477 if (num > mutator_count() || (num > avail_young_regions)) { 478 return NULL; 479 } 480 481 // Find the continuous interval of $num regions, starting from $beg and ending in $end, 482 // inclusive. Contiguous allocations are biased to the beginning. 483 484 size_t beg = _mutator_leftmost; 485 size_t end = beg; 486 487 while (true) { 488 if (end >= _max) { 489 // Hit the end, goodbye 490 return NULL; 491 } 492 493 // If regions are not adjacent, then current [beg; end] is useless, and we may fast-forward. 494 // If region is not completely free, the current [beg; end] is useless, and we may fast-forward. 495 if (!is_mutator_free(end) || !can_allocate_from(_heap->get_region(end))) { 496 end++; 497 beg = end; 498 continue; 499 } 500 501 if ((end - beg + 1) == num) { 502 // found the match 503 break; 504 } 505 506 end++; 507 }; 508 509 size_t remainder = words_size & ShenandoahHeapRegion::region_size_words_mask(); 510 ShenandoahMarkingContext* const ctx = _heap->complete_marking_context(); 511 512 // Initialize regions: 513 for (size_t i = beg; i <= end; i++) { 514 ShenandoahHeapRegion* r = _heap->get_region(i); 515 try_recycle_trashed(r); 516 517 assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous"); 518 assert(r->is_empty(), "Should be empty"); 519 520 if (i == beg) { 521 r->make_humongous_start(); 522 } else { 523 r->make_humongous_cont(); 524 } 525 526 // Trailing region may be non-full, record the remainder there 527 size_t used_words; 528 if ((i == end) && (remainder != 0)) { 529 used_words = remainder; 530 } else { 531 used_words = ShenandoahHeapRegion::region_size_words(); 532 } 533 534 r->set_affiliation(req.affiliation()); 535 r->set_update_watermark(r->bottom()); 536 r->set_top(r->bottom()); // Set top to bottom so we can capture TAMS 537 ctx->capture_top_at_mark_start(r); 538 r->set_top(r->bottom() + used_words); // Then change top to reflect allocation of humongous object. 539 assert(ctx->top_at_mark_start(r) == r->bottom(), "Newly established allocation region starts with TAMS equal to bottom"); 540 assert(ctx->is_bitmap_clear_range(ctx->top_bitmap(r), r->end()), "Bitmap above top_bitmap() must be clear"); 541 542 // Leave top_bitmap alone. The first time a heap region is put into service, top_bitmap should equal end. 543 // Thereafter, it should represent the upper bound on parts of the bitmap that need to be cleared. 544 // ctx->clear_bitmap(r); 545 log_debug(gc)("NOT clearing bitmap for Humongous region [" PTR_FORMAT ", " PTR_FORMAT "], top_bitmap: " 546 PTR_FORMAT " at transition from FREE to %s", 547 p2i(r->bottom()), p2i(r->end()), p2i(ctx->top_bitmap(r)), affiliation_name(req.affiliation())); 548 549 _mutator_free_bitmap.clear_bit(r->index()); 550 } 551 552 // While individual regions report their true use, all humongous regions are 553 // marked used in the free set. 554 increase_used(ShenandoahHeapRegion::region_size_bytes() * num); 555 if (req.affiliation() == ShenandoahRegionAffiliation::YOUNG_GENERATION) { 556 _heap->young_generation()->increase_used(words_size * HeapWordSize); 557 } else if (req.affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION) { 558 _heap->old_generation()->increase_used(words_size * HeapWordSize); 559 } 560 561 if (remainder != 0) { 562 // Record this remainder as allocation waste 563 size_t waste = ShenandoahHeapRegion::region_size_words() - remainder; 564 _heap->notify_mutator_alloc_words(waste, true); 565 _heap->generation_for(req.affiliation())->increase_allocated(waste * HeapWordSize); 566 } 567 568 // Allocated at left/rightmost? Move the bounds appropriately. 569 if (beg == _mutator_leftmost || end == _mutator_rightmost) { 570 adjust_bounds(); 571 } 572 assert_bounds(); 573 req.set_actual_size(words_size); 574 return _heap->get_region(beg)->bottom(); 575 } 576 577 bool ShenandoahFreeSet::can_allocate_from(ShenandoahHeapRegion *r) { 578 return r->is_empty() || (r->is_trash() && !_heap->is_concurrent_weak_root_in_progress()); 579 } 580 581 size_t ShenandoahFreeSet::alloc_capacity(ShenandoahHeapRegion *r) { 582 if (r->is_trash()) { 583 // This would be recycled on allocation path 584 return ShenandoahHeapRegion::region_size_bytes(); 585 } else { 586 return r->free(); 587 } 588 } 589 590 bool ShenandoahFreeSet::has_no_alloc_capacity(ShenandoahHeapRegion *r) { 591 return alloc_capacity(r) == 0; 592 } 593 594 void ShenandoahFreeSet::try_recycle_trashed(ShenandoahHeapRegion *r) { 595 if (r->is_trash()) { 596 _heap->decrease_used(r->used()); 597 r->recycle(); 598 } 599 } 600 601 void ShenandoahFreeSet::recycle_trash() { 602 // lock is not reentrable, check we don't have it 603 shenandoah_assert_not_heaplocked(); 604 for (size_t i = 0; i < _heap->num_regions(); i++) { 605 ShenandoahHeapRegion* r = _heap->get_region(i); 606 if (r->is_trash()) { 607 ShenandoahHeapLocker locker(_heap->lock()); 608 try_recycle_trashed(r); 609 } 610 SpinPause(); // allow allocators to take the lock 611 } 612 } 613 614 void ShenandoahFreeSet::flip_to_gc(ShenandoahHeapRegion* r) { 615 size_t idx = r->index(); 616 617 assert(_mutator_free_bitmap.at(idx), "Should be in mutator view"); 618 assert(can_allocate_from(r), "Should not be allocated"); 619 620 _mutator_free_bitmap.clear_bit(idx); 621 _collector_free_bitmap.set_bit(idx); 622 _collector_leftmost = MIN2(idx, _collector_leftmost); 623 _collector_rightmost = MAX2(idx, _collector_rightmost); 624 625 _capacity -= alloc_capacity(r); 626 627 if (touches_bounds(idx)) { 628 adjust_bounds(); 629 } 630 assert_bounds(); 631 632 // We do not ensure that the region is no longer trash, 633 // relying on try_allocate_in(), which always comes next, 634 // to recycle trash before attempting to allocate anything in the region. 635 } 636 637 void ShenandoahFreeSet::clear() { 638 shenandoah_assert_heaplocked(); 639 clear_internal(); 640 } 641 642 void ShenandoahFreeSet::clear_internal() { 643 _mutator_free_bitmap.clear(); 644 _collector_free_bitmap.clear(); 645 _mutator_leftmost = _max; 646 _mutator_rightmost = 0; 647 _collector_leftmost = _max; 648 _collector_rightmost = 0; 649 _capacity = 0; 650 _used = 0; 651 } 652 653 void ShenandoahFreeSet::rebuild() { 654 shenandoah_assert_heaplocked(); 655 clear(); 656 657 log_debug(gc)("Rebuilding FreeSet"); 658 for (size_t idx = 0; idx < _heap->num_regions(); idx++) { 659 ShenandoahHeapRegion* region = _heap->get_region(idx); 660 if (region->is_alloc_allowed() || region->is_trash()) { 661 assert(!region->is_cset(), "Shouldn't be adding those to the free set"); 662 663 // Do not add regions that would surely fail allocation 664 if (has_no_alloc_capacity(region)) continue; 665 666 _capacity += alloc_capacity(region); 667 assert(_used <= _capacity, "must not use more than we have"); 668 669 assert(!is_mutator_free(idx), "We are about to add it, it shouldn't be there already"); 670 _mutator_free_bitmap.set_bit(idx); 671 672 log_debug(gc)(" Setting Region " SIZE_FORMAT " _mutator_free_bitmap bit to true", idx); 673 } 674 } 675 676 // Evac reserve: reserve trailing space for evacuations 677 if (!_heap->mode()->is_generational()) { 678 size_t to_reserve = (_heap->max_capacity() / 100) * ShenandoahEvacReserve; 679 reserve_regions(to_reserve); 680 } else { 681 size_t young_reserve = (_heap->young_generation()->max_capacity() / 100) * ShenandoahEvacReserve; 682 // Note that all allocations performed from old-gen are performed by GC, generally using PLABs for both 683 // promotions and evacuations. The partition between which old memory is reserved for evacuation and 684 // which is reserved for promotion is enforced using thread-local variables that prescribe intentons within 685 // each PLAB. We do not reserve any of old-gen memory in order to facilitate the loaning of old-gen memory 686 // to young-gen purposes. 687 size_t old_reserve = 0; 688 size_t to_reserve = young_reserve + old_reserve; 689 reserve_regions(to_reserve); 690 } 691 692 recompute_bounds(); 693 assert_bounds(); 694 } 695 696 void ShenandoahFreeSet::reserve_regions(size_t to_reserve) { 697 size_t reserved = 0; 698 699 for (size_t idx = _heap->num_regions() - 1; idx > 0; idx--) { 700 if (reserved >= to_reserve) break; 701 702 ShenandoahHeapRegion* region = _heap->get_region(idx); 703 if (_mutator_free_bitmap.at(idx) && can_allocate_from(region)) { 704 _mutator_free_bitmap.clear_bit(idx); 705 _collector_free_bitmap.set_bit(idx); 706 size_t ac = alloc_capacity(region); 707 _capacity -= ac; 708 reserved += ac; 709 log_debug(gc)(" Shifting region " SIZE_FORMAT " from mutator_free to collector_free", idx); 710 } 711 } 712 } 713 714 void ShenandoahFreeSet::log_status() { 715 shenandoah_assert_heaplocked(); 716 717 LogTarget(Info, gc, ergo) lt; 718 if (lt.is_enabled()) { 719 ResourceMark rm; 720 LogStream ls(lt); 721 722 { 723 size_t last_idx = 0; 724 size_t max = 0; 725 size_t max_contig = 0; 726 size_t empty_contig = 0; 727 728 size_t total_used = 0; 729 size_t total_free = 0; 730 size_t total_free_ext = 0; 731 732 for (size_t idx = _mutator_leftmost; idx <= _mutator_rightmost; idx++) { 733 if (is_mutator_free(idx)) { 734 ShenandoahHeapRegion *r = _heap->get_region(idx); 735 size_t free = alloc_capacity(r); 736 737 max = MAX2(max, free); 738 739 if (r->is_empty()) { 740 total_free_ext += free; 741 if (last_idx + 1 == idx) { 742 empty_contig++; 743 } else { 744 empty_contig = 1; 745 } 746 } else { 747 empty_contig = 0; 748 } 749 750 total_used += r->used(); 751 total_free += free; 752 753 max_contig = MAX2(max_contig, empty_contig); 754 last_idx = idx; 755 } 756 } 757 758 size_t max_humongous = max_contig * ShenandoahHeapRegion::region_size_bytes(); 759 size_t free = capacity() - used(); 760 761 ls.print("Free: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s regular, " SIZE_FORMAT "%s humongous, ", 762 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free), 763 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max), 764 byte_size_in_proper_unit(max_humongous), proper_unit_for_byte_size(max_humongous) 765 ); 766 767 ls.print("Frag: "); 768 size_t frag_ext; 769 if (total_free_ext > 0) { 770 frag_ext = 100 - (100 * max_humongous / total_free_ext); 771 } else { 772 frag_ext = 0; 773 } 774 ls.print(SIZE_FORMAT "%% external, ", frag_ext); 775 776 size_t frag_int; 777 if (mutator_count() > 0) { 778 frag_int = (100 * (total_used / mutator_count()) / ShenandoahHeapRegion::region_size_bytes()); 779 } else { 780 frag_int = 0; 781 } 782 ls.print(SIZE_FORMAT "%% internal; ", frag_int); 783 } 784 785 { 786 size_t max = 0; 787 size_t total_free = 0; 788 789 for (size_t idx = _collector_leftmost; idx <= _collector_rightmost; idx++) { 790 if (is_collector_free(idx)) { 791 ShenandoahHeapRegion *r = _heap->get_region(idx); 792 size_t free = alloc_capacity(r); 793 max = MAX2(max, free); 794 total_free += free; 795 } 796 } 797 798 ls.print_cr("Reserve: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s", 799 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free), 800 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max)); 801 } 802 } 803 } 804 805 HeapWord* ShenandoahFreeSet::allocate(ShenandoahAllocRequest& req, bool& in_new_region) { 806 shenandoah_assert_heaplocked(); 807 assert_bounds(); 808 809 // Allocation request is known to satisfy all memory budgeting constraints. 810 if (req.size() > ShenandoahHeapRegion::humongous_threshold_words()) { 811 switch (req.type()) { 812 case ShenandoahAllocRequest::_alloc_shared: 813 case ShenandoahAllocRequest::_alloc_shared_gc: 814 in_new_region = true; 815 return allocate_contiguous(req); 816 case ShenandoahAllocRequest::_alloc_plab: 817 case ShenandoahAllocRequest::_alloc_gclab: 818 case ShenandoahAllocRequest::_alloc_tlab: 819 in_new_region = false; 820 assert(false, "Trying to allocate TLAB larger than the humongous threshold: " SIZE_FORMAT " > " SIZE_FORMAT, 821 req.size(), ShenandoahHeapRegion::humongous_threshold_words()); 822 return NULL; 823 default: 824 ShouldNotReachHere(); 825 return NULL; 826 } 827 } else { 828 return allocate_single(req, in_new_region); 829 } 830 } 831 832 size_t ShenandoahFreeSet::unsafe_peek_free() const { 833 // Deliberately not locked, this method is unsafe when free set is modified. 834 835 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) { 836 if (index < _max && is_mutator_free(index)) { 837 ShenandoahHeapRegion* r = _heap->get_region(index); 838 if (r->free() >= MinTLABSize) { 839 return r->free(); 840 } 841 } 842 } 843 844 // It appears that no regions left 845 return 0; 846 } 847 848 void ShenandoahFreeSet::print_on(outputStream* out) const { 849 out->print_cr("Mutator Free Set: " SIZE_FORMAT "", mutator_count()); 850 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) { 851 if (is_mutator_free(index)) { 852 _heap->get_region(index)->print_on(out); 853 } 854 } 855 out->print_cr("Collector Free Set: " SIZE_FORMAT "", collector_count()); 856 for (size_t index = _collector_leftmost; index <= _collector_rightmost; index++) { 857 if (is_collector_free(index)) { 858 _heap->get_region(index)->print_on(out); 859 } 860 } 861 } 862 863 /* 864 * Internal fragmentation metric: describes how fragmented the heap regions are. 865 * 866 * It is derived as: 867 * 868 * sum(used[i]^2, i=0..k) 869 * IF = 1 - ------------------------------ 870 * C * sum(used[i], i=0..k) 871 * 872 * ...where k is the number of regions in computation, C is the region capacity, and 873 * used[i] is the used space in the region. 874 * 875 * The non-linearity causes IF to be lower for the cases where the same total heap 876 * used is densely packed. For example: 877 * a) Heap is completely full => IF = 0 878 * b) Heap is half full, first 50% regions are completely full => IF = 0 879 * c) Heap is half full, each region is 50% full => IF = 1/2 880 * d) Heap is quarter full, first 50% regions are completely full => IF = 0 881 * e) Heap is quarter full, each region is 25% full => IF = 3/4 882 * f) Heap has one small object per each region => IF =~ 1 883 */ 884 double ShenandoahFreeSet::internal_fragmentation() { 885 double squared = 0; 886 double linear = 0; 887 int count = 0; 888 889 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) { 890 if (is_mutator_free(index)) { 891 ShenandoahHeapRegion* r = _heap->get_region(index); 892 size_t used = r->used(); 893 squared += used * used; 894 linear += used; 895 count++; 896 } 897 } 898 899 if (count > 0) { 900 double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear); 901 return 1 - s; 902 } else { 903 return 0; 904 } 905 } 906 907 /* 908 * External fragmentation metric: describes how fragmented the heap is. 909 * 910 * It is derived as: 911 * 912 * EF = 1 - largest_contiguous_free / total_free 913 * 914 * For example: 915 * a) Heap is completely empty => EF = 0 916 * b) Heap is completely full => EF = 0 917 * c) Heap is first-half full => EF = 1/2 918 * d) Heap is half full, full and empty regions interleave => EF =~ 1 919 */ 920 double ShenandoahFreeSet::external_fragmentation() { 921 size_t last_idx = 0; 922 size_t max_contig = 0; 923 size_t empty_contig = 0; 924 925 size_t free = 0; 926 927 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) { 928 if (is_mutator_free(index)) { 929 ShenandoahHeapRegion* r = _heap->get_region(index); 930 if (r->is_empty()) { 931 free += ShenandoahHeapRegion::region_size_bytes(); 932 if (last_idx + 1 == index) { 933 empty_contig++; 934 } else { 935 empty_contig = 1; 936 } 937 } else { 938 empty_contig = 0; 939 } 940 941 max_contig = MAX2(max_contig, empty_contig); 942 last_idx = index; 943 } 944 } 945 946 if (free > 0) { 947 return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free); 948 } else { 949 return 0; 950 } 951 } 952 953 #ifdef ASSERT 954 void ShenandoahFreeSet::assert_bounds() const { 955 // Performance invariants. Failing these would not break the free set, but performance 956 // would suffer. 957 assert (_mutator_leftmost <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _mutator_leftmost, _max); 958 assert (_mutator_rightmost < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _mutator_rightmost, _max); 959 960 assert (_mutator_leftmost == _max || is_mutator_free(_mutator_leftmost), "leftmost region should be free: " SIZE_FORMAT, _mutator_leftmost); 961 assert (_mutator_rightmost == 0 || is_mutator_free(_mutator_rightmost), "rightmost region should be free: " SIZE_FORMAT, _mutator_rightmost); 962 963 size_t beg_off = _mutator_free_bitmap.get_next_one_offset(0); 964 size_t end_off = _mutator_free_bitmap.get_next_one_offset(_mutator_rightmost + 1); 965 assert (beg_off >= _mutator_leftmost, "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, _mutator_leftmost); 966 assert (end_off == _max, "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, _mutator_rightmost); 967 968 assert (_collector_leftmost <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _collector_leftmost, _max); 969 assert (_collector_rightmost < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _collector_rightmost, _max); 970 971 assert (_collector_leftmost == _max || is_collector_free(_collector_leftmost), "leftmost region should be free: " SIZE_FORMAT, _collector_leftmost); 972 assert (_collector_rightmost == 0 || is_collector_free(_collector_rightmost), "rightmost region should be free: " SIZE_FORMAT, _collector_rightmost); 973 974 beg_off = _collector_free_bitmap.get_next_one_offset(0); 975 end_off = _collector_free_bitmap.get_next_one_offset(_collector_rightmost + 1); 976 assert (beg_off >= _collector_leftmost, "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, _collector_leftmost); 977 assert (end_off == _max, "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, _collector_rightmost); 978 } 979 #endif