1 /* 2 * Copyright (c) 2001, 2019, Oracle and/or its affiliates. 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/cms/cmsHeap.hpp" 27 #include "gc/cms/cmsLockVerifier.hpp" 28 #include "gc/cms/compactibleFreeListSpace.hpp" 29 #include "gc/cms/concurrentMarkSweepGeneration.inline.hpp" 30 #include "gc/cms/concurrentMarkSweepThread.hpp" 31 #include "gc/shared/blockOffsetTable.inline.hpp" 32 #include "gc/shared/collectedHeap.inline.hpp" 33 #include "gc/shared/genOopClosures.inline.hpp" 34 #include "gc/shared/space.inline.hpp" 35 #include "gc/shared/spaceDecorator.hpp" 36 #include "logging/log.hpp" 37 #include "logging/logStream.hpp" 38 #include "memory/allocation.inline.hpp" 39 #include "memory/binaryTreeDictionary.inline.hpp" 40 #include "memory/iterator.inline.hpp" 41 #include "memory/resourceArea.hpp" 42 #include "memory/universe.hpp" 43 #include "oops/access.inline.hpp" 44 #include "oops/compressedOops.inline.hpp" 45 #include "oops/oop.inline.hpp" 46 #include "runtime/globals.hpp" 47 #include "runtime/handles.inline.hpp" 48 #include "runtime/init.hpp" 49 #include "runtime/java.hpp" 50 #include "runtime/orderAccess.hpp" 51 #include "runtime/vmThread.hpp" 52 #include "utilities/align.hpp" 53 #include "utilities/copy.hpp" 54 55 // Specialize for AdaptiveFreeList which tries to avoid 56 // splitting a chunk of a size that is under populated in favor of 57 // an over populated size. The general get_better_list() just returns 58 // the current list. 59 template <> 60 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* 61 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list( 62 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) { 63 // A candidate chunk has been found. If it is already under 64 // populated, get a chunk associated with the hint for this 65 // chunk. 66 67 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this; 68 if (curTL->surplus() <= 0) { 69 /* Use the hint to find a size with a surplus, and reset the hint. */ 70 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this; 71 while (hintTL->hint() != 0) { 72 assert(hintTL->hint() > hintTL->size(), 73 "hint points in the wrong direction"); 74 hintTL = dictionary->find_list(hintTL->hint()); 75 assert(curTL != hintTL, "Infinite loop"); 76 if (hintTL == NULL || 77 hintTL == curTL /* Should not happen but protect against it */ ) { 78 // No useful hint. Set the hint to NULL and go on. 79 curTL->set_hint(0); 80 break; 81 } 82 assert(hintTL->size() > curTL->size(), "hint is inconsistent"); 83 if (hintTL->surplus() > 0) { 84 // The hint led to a list that has a surplus. Use it. 85 // Set the hint for the candidate to an overpopulated 86 // size. 87 curTL->set_hint(hintTL->size()); 88 // Change the candidate. 89 curTL = hintTL; 90 break; 91 } 92 } 93 } 94 return curTL; 95 } 96 97 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth) { 98 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* nd = find_list(size); 99 if (nd) { 100 if (split) { 101 if (birth) { 102 nd->increment_split_births(); 103 nd->increment_surplus(); 104 } else { 105 nd->increment_split_deaths(); 106 nd->decrement_surplus(); 107 } 108 } else { 109 if (birth) { 110 nd->increment_coal_births(); 111 nd->increment_surplus(); 112 } else { 113 nd->increment_coal_deaths(); 114 nd->decrement_surplus(); 115 } 116 } 117 } 118 // A list for this size may not be found (nd == 0) if 119 // This is a death where the appropriate list is now 120 // empty and has been removed from the list. 121 // This is a birth associated with a LinAB. The chunk 122 // for the LinAB is not in the dictionary. 123 } 124 125 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { 126 if (FLSAlwaysCoalesceLarge) return true; 127 128 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* list_of_size = find_list(size); 129 // None of requested size implies overpopulated. 130 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || 131 list_of_size->count() > list_of_size->coal_desired(); 132 } 133 134 // For each list in the tree, calculate the desired, desired 135 // coalesce, count before sweep, and surplus before sweep. 136 class BeginSweepClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > { 137 double _percentage; 138 float _inter_sweep_current; 139 float _inter_sweep_estimate; 140 float _intra_sweep_estimate; 141 142 public: 143 BeginSweepClosure(double p, float inter_sweep_current, 144 float inter_sweep_estimate, 145 float intra_sweep_estimate) : 146 _percentage(p), 147 _inter_sweep_current(inter_sweep_current), 148 _inter_sweep_estimate(inter_sweep_estimate), 149 _intra_sweep_estimate(intra_sweep_estimate) { } 150 151 void do_list(AdaptiveFreeList<FreeChunk>* fl) { 152 double coalSurplusPercent = _percentage; 153 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); 154 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); 155 fl->set_before_sweep(fl->count()); 156 fl->set_bfr_surp(fl->surplus()); 157 } 158 }; 159 160 void AFLBinaryTreeDictionary::begin_sweep_dict_census(double coalSurplusPercent, 161 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { 162 BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current, 163 inter_sweep_estimate, 164 intra_sweep_estimate); 165 bsc.do_tree(root()); 166 } 167 168 // Calculate surpluses for the lists in the tree. 169 class setTreeSurplusClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > { 170 double percentage; 171 public: 172 setTreeSurplusClosure(double v) { percentage = v; } 173 174 void do_list(AdaptiveFreeList<FreeChunk>* fl) { 175 double splitSurplusPercent = percentage; 176 fl->set_surplus(fl->count() - 177 (ssize_t)((double)fl->desired() * splitSurplusPercent)); 178 } 179 }; 180 181 void AFLBinaryTreeDictionary::set_tree_surplus(double splitSurplusPercent) { 182 setTreeSurplusClosure sts(splitSurplusPercent); 183 sts.do_tree(root()); 184 } 185 186 // Set hints for the lists in the tree. 187 class setTreeHintsClosure : public DescendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > { 188 size_t hint; 189 public: 190 setTreeHintsClosure(size_t v) { hint = v; } 191 192 void do_list(AdaptiveFreeList<FreeChunk>* fl) { 193 fl->set_hint(hint); 194 assert(fl->hint() == 0 || fl->hint() > fl->size(), 195 "Current hint is inconsistent"); 196 if (fl->surplus() > 0) { 197 hint = fl->size(); 198 } 199 } 200 }; 201 202 void AFLBinaryTreeDictionary::set_tree_hints(void) { 203 setTreeHintsClosure sth(0); 204 sth.do_tree(root()); 205 } 206 207 // Save count before previous sweep and splits and coalesces. 208 class clearTreeCensusClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > { 209 void do_list(AdaptiveFreeList<FreeChunk>* fl) { 210 fl->set_prev_sweep(fl->count()); 211 fl->set_coal_births(0); 212 fl->set_coal_deaths(0); 213 fl->set_split_births(0); 214 fl->set_split_deaths(0); 215 } 216 }; 217 218 void AFLBinaryTreeDictionary::clear_tree_census(void) { 219 clearTreeCensusClosure ctc; 220 ctc.do_tree(root()); 221 } 222 223 // Do reporting and post sweep clean up. 224 void AFLBinaryTreeDictionary::end_sweep_dict_census(double splitSurplusPercent) { 225 // Does walking the tree 3 times hurt? 226 set_tree_surplus(splitSurplusPercent); 227 set_tree_hints(); 228 LogTarget(Trace, gc, freelist, stats) log; 229 if (log.is_enabled()) { 230 LogStream out(log); 231 report_statistics(&out); 232 } 233 clear_tree_census(); 234 } 235 236 // Print census information - counts, births, deaths, etc. 237 // for each list in the tree. Also print some summary 238 // information. 239 class PrintTreeCensusClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > { 240 int _print_line; 241 size_t _total_free; 242 AdaptiveFreeList<FreeChunk> _total; 243 244 public: 245 PrintTreeCensusClosure() { 246 _print_line = 0; 247 _total_free = 0; 248 } 249 AdaptiveFreeList<FreeChunk>* total() { return &_total; } 250 size_t total_free() { return _total_free; } 251 252 void do_list(AdaptiveFreeList<FreeChunk>* fl) { 253 LogStreamHandle(Debug, gc, freelist, census) out; 254 255 if (++_print_line >= 40) { 256 AdaptiveFreeList<FreeChunk>::print_labels_on(&out, "size"); 257 _print_line = 0; 258 } 259 fl->print_on(&out); 260 _total_free += fl->count() * fl->size() ; 261 total()->set_count( total()->count() + fl->count() ); 262 total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() ); 263 total()->set_surplus( total()->split_deaths() + fl->surplus() ); 264 total()->set_desired( total()->desired() + fl->desired() ); 265 total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() ); 266 total()->set_before_sweep(total()->before_sweep() + fl->before_sweep()); 267 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); 268 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); 269 total()->set_split_births(total()->split_births() + fl->split_births()); 270 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); 271 } 272 }; 273 274 void AFLBinaryTreeDictionary::print_dict_census(outputStream* st) const { 275 276 st->print_cr("BinaryTree"); 277 AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size"); 278 PrintTreeCensusClosure ptc; 279 ptc.do_tree(root()); 280 281 AdaptiveFreeList<FreeChunk>* total = ptc.total(); 282 AdaptiveFreeList<FreeChunk>::print_labels_on(st, " "); 283 total->print_on(st, "TOTAL\t"); 284 st->print_cr("total_free(words): " SIZE_FORMAT_W(16) " growth: %8.5f deficit: %8.5f", 285 ptc.total_free(), 286 (double)(total->split_births() + total->coal_births() 287 - total->split_deaths() - total->coal_deaths()) 288 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), 289 (double)(total->desired() - total->count()) 290 /(total->desired() != 0 ? (double)total->desired() : 1.0)); 291 } 292 293 ///////////////////////////////////////////////////////////////////////// 294 //// CompactibleFreeListSpace 295 ///////////////////////////////////////////////////////////////////////// 296 297 // highest ranked free list lock rank 298 int CompactibleFreeListSpace::_lockRank = Mutex::leaf + 3; 299 300 // Defaults are 0 so things will break badly if incorrectly initialized. 301 size_t CompactibleFreeListSpace::IndexSetStart = 0; 302 size_t CompactibleFreeListSpace::IndexSetStride = 0; 303 size_t CompactibleFreeListSpace::_min_chunk_size_in_bytes = 0; 304 305 size_t MinChunkSize = 0; 306 307 void CompactibleFreeListSpace::set_cms_values() { 308 // Set CMS global values 309 assert(MinChunkSize == 0, "already set"); 310 311 // MinChunkSize should be a multiple of MinObjAlignment and be large enough 312 // for chunks to contain a FreeChunk. 313 _min_chunk_size_in_bytes = align_up(sizeof(FreeChunk), MinObjAlignmentInBytes); 314 MinChunkSize = _min_chunk_size_in_bytes / BytesPerWord; 315 316 assert(IndexSetStart == 0 && IndexSetStride == 0, "already set"); 317 IndexSetStart = MinChunkSize; 318 IndexSetStride = MinObjAlignment; 319 } 320 321 // Constructor 322 CompactibleFreeListSpace::CompactibleFreeListSpace(BlockOffsetSharedArray* bs, MemRegion mr) : 323 _rescan_task_size(CardTable::card_size_in_words * BitsPerWord * 324 CMSRescanMultiple), 325 _marking_task_size(CardTable::card_size_in_words * BitsPerWord * 326 CMSConcMarkMultiple), 327 _bt(bs, mr), 328 _collector(NULL), 329 // free list locks are in the range of values taken by _lockRank 330 // This range currently is [_leaf+2, _leaf+3] 331 // Note: this requires that CFLspace c'tors 332 // are called serially in the order in which the locks are 333 // are acquired in the program text. This is true today. 334 _freelistLock(_lockRank--, "CompactibleFreeListSpace_lock", true, 335 Monitor::_safepoint_check_never), 336 _preconsumptionDirtyCardClosure(NULL), 337 _parDictionaryAllocLock(Mutex::leaf - 1, // == rank(ExpandHeap_lock) - 1 338 "CompactibleFreeListSpace_dict_par_lock", true, 339 Monitor::_safepoint_check_never) 340 { 341 assert(sizeof(FreeChunk) / BytesPerWord <= MinChunkSize, 342 "FreeChunk is larger than expected"); 343 _bt.set_space(this); 344 initialize(mr, SpaceDecorator::Clear, SpaceDecorator::Mangle); 345 346 _dictionary = new AFLBinaryTreeDictionary(mr); 347 348 assert(_dictionary != NULL, "CMS dictionary initialization"); 349 // The indexed free lists are initially all empty and are lazily 350 // filled in on demand. Initialize the array elements to NULL. 351 initializeIndexedFreeListArray(); 352 353 _smallLinearAllocBlock.set(0, 0, 1024*SmallForLinearAlloc, 354 SmallForLinearAlloc); 355 356 // CMSIndexedFreeListReplenish should be at least 1 357 CMSIndexedFreeListReplenish = MAX2((uintx)1, CMSIndexedFreeListReplenish); 358 _promoInfo.setSpace(this); 359 if (UseCMSBestFit) { 360 _fitStrategy = FreeBlockBestFitFirst; 361 } else { 362 _fitStrategy = FreeBlockStrategyNone; 363 } 364 check_free_list_consistency(); 365 366 // Initialize locks for parallel case. 367 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 368 _indexedFreeListParLocks[i] = new Mutex(Mutex::leaf - 1, // == ExpandHeap_lock - 1 369 "a freelist par lock", true, Mutex::_safepoint_check_never); 370 DEBUG_ONLY( 371 _indexedFreeList[i].set_protecting_lock(_indexedFreeListParLocks[i]); 372 ) 373 } 374 _dictionary->set_par_lock(&_parDictionaryAllocLock); 375 376 _used_stable = 0; 377 } 378 379 // Like CompactibleSpace forward() but always calls cross_threshold() to 380 // update the block offset table. Removed initialize_threshold call because 381 // CFLS does not use a block offset array for contiguous spaces. 382 HeapWord* CompactibleFreeListSpace::forward(oop q, size_t size, 383 CompactPoint* cp, HeapWord* compact_top) { 384 // q is alive 385 // First check if we should switch compaction space 386 assert(this == cp->space, "'this' should be current compaction space."); 387 size_t compaction_max_size = pointer_delta(end(), compact_top); 388 assert(adjustObjectSize(size) == cp->space->adjust_object_size_v(size), 389 "virtual adjustObjectSize_v() method is not correct"); 390 size_t adjusted_size = adjustObjectSize(size); 391 assert(compaction_max_size >= MinChunkSize || compaction_max_size == 0, 392 "no small fragments allowed"); 393 assert(minimum_free_block_size() == MinChunkSize, 394 "for de-virtualized reference below"); 395 // Can't leave a nonzero size, residual fragment smaller than MinChunkSize 396 if (adjusted_size + MinChunkSize > compaction_max_size && 397 adjusted_size != compaction_max_size) { 398 do { 399 // switch to next compaction space 400 cp->space->set_compaction_top(compact_top); 401 cp->space = cp->space->next_compaction_space(); 402 if (cp->space == NULL) { 403 cp->gen = CMSHeap::heap()->young_gen(); 404 assert(cp->gen != NULL, "compaction must succeed"); 405 cp->space = cp->gen->first_compaction_space(); 406 assert(cp->space != NULL, "generation must have a first compaction space"); 407 } 408 compact_top = cp->space->bottom(); 409 cp->space->set_compaction_top(compact_top); 410 // The correct adjusted_size may not be the same as that for this method 411 // (i.e., cp->space may no longer be "this" so adjust the size again. 412 // Use the virtual method which is not used above to save the virtual 413 // dispatch. 414 adjusted_size = cp->space->adjust_object_size_v(size); 415 compaction_max_size = pointer_delta(cp->space->end(), compact_top); 416 assert(cp->space->minimum_free_block_size() == 0, "just checking"); 417 } while (adjusted_size > compaction_max_size); 418 } 419 420 // store the forwarding pointer into the mark word 421 if ((HeapWord*)q != compact_top) { 422 q->forward_to(oop(compact_top)); 423 assert(q->is_gc_marked(), "encoding the pointer should preserve the mark"); 424 } else { 425 // if the object isn't moving we can just set the mark to the default 426 // mark and handle it specially later on. 427 q->init_mark_raw(); 428 assert(q->forwardee() == NULL, "should be forwarded to NULL"); 429 } 430 431 compact_top += adjusted_size; 432 433 // we need to update the offset table so that the beginnings of objects can be 434 // found during scavenge. Note that we are updating the offset table based on 435 // where the object will be once the compaction phase finishes. 436 437 // Always call cross_threshold(). A contiguous space can only call it when 438 // the compaction_top exceeds the current threshold but not for an 439 // non-contiguous space. 440 cp->threshold = 441 cp->space->cross_threshold(compact_top - adjusted_size, compact_top); 442 return compact_top; 443 } 444 445 // A modified copy of OffsetTableContigSpace::cross_threshold() with _offsets -> _bt 446 // and use of single_block instead of alloc_block. The name here is not really 447 // appropriate - maybe a more general name could be invented for both the 448 // contiguous and noncontiguous spaces. 449 450 HeapWord* CompactibleFreeListSpace::cross_threshold(HeapWord* start, HeapWord* the_end) { 451 _bt.single_block(start, the_end); 452 return end(); 453 } 454 455 // Initialize them to NULL. 456 void CompactibleFreeListSpace::initializeIndexedFreeListArray() { 457 for (size_t i = 0; i < IndexSetSize; i++) { 458 // Note that on platforms where objects are double word aligned, 459 // the odd array elements are not used. It is convenient, however, 460 // to map directly from the object size to the array element. 461 _indexedFreeList[i].reset(IndexSetSize); 462 _indexedFreeList[i].set_size(i); 463 assert(_indexedFreeList[i].count() == 0, "reset check failed"); 464 assert(_indexedFreeList[i].head() == NULL, "reset check failed"); 465 assert(_indexedFreeList[i].tail() == NULL, "reset check failed"); 466 assert(_indexedFreeList[i].hint() == IndexSetSize, "reset check failed"); 467 } 468 } 469 470 size_t CompactibleFreeListSpace::obj_size(const HeapWord* addr) const { 471 return adjustObjectSize(oop(addr)->size()); 472 } 473 474 void CompactibleFreeListSpace::resetIndexedFreeListArray() { 475 for (size_t i = 1; i < IndexSetSize; i++) { 476 assert(_indexedFreeList[i].size() == (size_t) i, 477 "Indexed free list sizes are incorrect"); 478 _indexedFreeList[i].reset(IndexSetSize); 479 assert(_indexedFreeList[i].count() == 0, "reset check failed"); 480 assert(_indexedFreeList[i].head() == NULL, "reset check failed"); 481 assert(_indexedFreeList[i].tail() == NULL, "reset check failed"); 482 assert(_indexedFreeList[i].hint() == IndexSetSize, "reset check failed"); 483 } 484 } 485 486 void CompactibleFreeListSpace::reset(MemRegion mr) { 487 resetIndexedFreeListArray(); 488 dictionary()->reset(); 489 if (BlockOffsetArrayUseUnallocatedBlock) { 490 assert(end() == mr.end(), "We are compacting to the bottom of CMS gen"); 491 // Everything's allocated until proven otherwise. 492 _bt.set_unallocated_block(end()); 493 } 494 if (!mr.is_empty()) { 495 assert(mr.word_size() >= MinChunkSize, "Chunk size is too small"); 496 _bt.single_block(mr.start(), mr.word_size()); 497 FreeChunk* fc = (FreeChunk*) mr.start(); 498 fc->set_size(mr.word_size()); 499 if (mr.word_size() >= IndexSetSize ) { 500 returnChunkToDictionary(fc); 501 } else { 502 _bt.verify_not_unallocated((HeapWord*)fc, fc->size()); 503 _indexedFreeList[mr.word_size()].return_chunk_at_head(fc); 504 } 505 coalBirth(mr.word_size()); 506 } 507 _promoInfo.reset(); 508 _smallLinearAllocBlock._ptr = NULL; 509 _smallLinearAllocBlock._word_size = 0; 510 } 511 512 void CompactibleFreeListSpace::reset_after_compaction() { 513 // Reset the space to the new reality - one free chunk. 514 MemRegion mr(compaction_top(), end()); 515 reset(mr); 516 // Now refill the linear allocation block(s) if possible. 517 refillLinearAllocBlocksIfNeeded(); 518 } 519 520 // Walks the entire dictionary, returning a coterminal 521 // chunk, if it exists. Use with caution since it involves 522 // a potentially complete walk of a potentially large tree. 523 FreeChunk* CompactibleFreeListSpace::find_chunk_at_end() { 524 525 assert_lock_strong(&_freelistLock); 526 527 return dictionary()->find_chunk_ends_at(end()); 528 } 529 530 531 #ifndef PRODUCT 532 void CompactibleFreeListSpace::initializeIndexedFreeListArrayReturnedBytes() { 533 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 534 _indexedFreeList[i].allocation_stats()->set_returned_bytes(0); 535 } 536 } 537 538 size_t CompactibleFreeListSpace::sumIndexedFreeListArrayReturnedBytes() { 539 size_t sum = 0; 540 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 541 sum += _indexedFreeList[i].allocation_stats()->returned_bytes(); 542 } 543 return sum; 544 } 545 546 size_t CompactibleFreeListSpace::totalCountInIndexedFreeLists() const { 547 size_t count = 0; 548 for (size_t i = IndexSetStart; i < IndexSetSize; i++) { 549 debug_only( 550 ssize_t total_list_count = 0; 551 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL; 552 fc = fc->next()) { 553 total_list_count++; 554 } 555 assert(total_list_count == _indexedFreeList[i].count(), 556 "Count in list is incorrect"); 557 ) 558 count += _indexedFreeList[i].count(); 559 } 560 return count; 561 } 562 563 size_t CompactibleFreeListSpace::totalCount() { 564 size_t num = totalCountInIndexedFreeLists(); 565 num += dictionary()->total_count(); 566 if (_smallLinearAllocBlock._word_size != 0) { 567 num++; 568 } 569 return num; 570 } 571 #endif 572 573 bool CompactibleFreeListSpace::is_free_block(const HeapWord* p) const { 574 FreeChunk* fc = (FreeChunk*) p; 575 return fc->is_free(); 576 } 577 578 size_t CompactibleFreeListSpace::used() const { 579 return capacity() - free(); 580 } 581 582 size_t CompactibleFreeListSpace::used_stable() const { 583 return _used_stable; 584 } 585 586 void CompactibleFreeListSpace::recalculate_used_stable() { 587 _used_stable = used(); 588 } 589 590 size_t CompactibleFreeListSpace::free() const { 591 // "MT-safe, but not MT-precise"(TM), if you will: i.e. 592 // if you do this while the structures are in flux you 593 // may get an approximate answer only; for instance 594 // because there is concurrent allocation either 595 // directly by mutators or for promotion during a GC. 596 // It's "MT-safe", however, in the sense that you are guaranteed 597 // not to crash and burn, for instance, because of walking 598 // pointers that could disappear as you were walking them. 599 // The approximation is because the various components 600 // that are read below are not read atomically (and 601 // further the computation of totalSizeInIndexedFreeLists() 602 // is itself a non-atomic computation. The normal use of 603 // this is during a resize operation at the end of GC 604 // and at that time you are guaranteed to get the 605 // correct actual value. However, for instance, this is 606 // also read completely asynchronously by the "perf-sampler" 607 // that supports jvmstat, and you are apt to see the values 608 // flicker in such cases. 609 assert(_dictionary != NULL, "No _dictionary?"); 610 return (_dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())) + 611 totalSizeInIndexedFreeLists() + 612 _smallLinearAllocBlock._word_size) * HeapWordSize; 613 } 614 615 size_t CompactibleFreeListSpace::max_alloc_in_words() const { 616 assert(_dictionary != NULL, "No _dictionary?"); 617 assert_locked(); 618 size_t res = _dictionary->max_chunk_size(); 619 res = MAX2(res, MIN2(_smallLinearAllocBlock._word_size, 620 (size_t) SmallForLinearAlloc - 1)); 621 // XXX the following could potentially be pretty slow; 622 // should one, pessimistically for the rare cases when res 623 // calculated above is less than IndexSetSize, 624 // just return res calculated above? My reasoning was that 625 // those cases will be so rare that the extra time spent doesn't 626 // really matter.... 627 // Note: do not change the loop test i >= res + IndexSetStride 628 // to i > res below, because i is unsigned and res may be zero. 629 for (size_t i = IndexSetSize - 1; i >= res + IndexSetStride; 630 i -= IndexSetStride) { 631 if (_indexedFreeList[i].head() != NULL) { 632 assert(_indexedFreeList[i].count() != 0, "Inconsistent FreeList"); 633 return i; 634 } 635 } 636 return res; 637 } 638 639 void LinearAllocBlock::print_on(outputStream* st) const { 640 st->print_cr(" LinearAllocBlock: ptr = " PTR_FORMAT ", word_size = " SIZE_FORMAT 641 ", refillsize = " SIZE_FORMAT ", allocation_size_limit = " SIZE_FORMAT, 642 p2i(_ptr), _word_size, _refillSize, _allocation_size_limit); 643 } 644 645 void CompactibleFreeListSpace::print_on(outputStream* st) const { 646 st->print_cr("COMPACTIBLE FREELIST SPACE"); 647 st->print_cr(" Space:"); 648 Space::print_on(st); 649 650 st->print_cr("promoInfo:"); 651 _promoInfo.print_on(st); 652 653 st->print_cr("_smallLinearAllocBlock"); 654 _smallLinearAllocBlock.print_on(st); 655 656 // dump_memory_block(_smallLinearAllocBlock->_ptr, 128); 657 658 st->print_cr(" _fitStrategy = %s", BOOL_TO_STR(_fitStrategy)); 659 } 660 661 void CompactibleFreeListSpace::print_indexed_free_lists(outputStream* st) 662 const { 663 reportIndexedFreeListStatistics(st); 664 st->print_cr("Layout of Indexed Freelists"); 665 st->print_cr("---------------------------"); 666 AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size"); 667 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 668 _indexedFreeList[i].print_on(st); 669 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL; fc = fc->next()) { 670 st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", 671 p2i(fc), p2i((HeapWord*)fc + i), 672 fc->cantCoalesce() ? "\t CC" : ""); 673 } 674 } 675 } 676 677 void CompactibleFreeListSpace::print_promo_info_blocks(outputStream* st) 678 const { 679 _promoInfo.print_on(st); 680 } 681 682 void CompactibleFreeListSpace::print_dictionary_free_lists(outputStream* st) 683 const { 684 _dictionary->report_statistics(st); 685 st->print_cr("Layout of Freelists in Tree"); 686 st->print_cr("---------------------------"); 687 _dictionary->print_free_lists(st); 688 } 689 690 class BlkPrintingClosure: public BlkClosure { 691 const CMSCollector* _collector; 692 const CompactibleFreeListSpace* _sp; 693 const CMSBitMap* _live_bit_map; 694 const bool _post_remark; 695 outputStream* _st; 696 public: 697 BlkPrintingClosure(const CMSCollector* collector, 698 const CompactibleFreeListSpace* sp, 699 const CMSBitMap* live_bit_map, 700 outputStream* st): 701 _collector(collector), 702 _sp(sp), 703 _live_bit_map(live_bit_map), 704 _post_remark(collector->abstract_state() > CMSCollector::FinalMarking), 705 _st(st) { } 706 size_t do_blk(HeapWord* addr); 707 }; 708 709 size_t BlkPrintingClosure::do_blk(HeapWord* addr) { 710 size_t sz = _sp->block_size_no_stall(addr, _collector); 711 assert(sz != 0, "Should always be able to compute a size"); 712 if (_sp->block_is_obj(addr)) { 713 const bool dead = _post_remark && !_live_bit_map->isMarked(addr); 714 _st->print_cr(PTR_FORMAT ": %s object of size " SIZE_FORMAT "%s", 715 p2i(addr), 716 dead ? "dead" : "live", 717 sz, 718 (!dead && CMSPrintObjectsInDump) ? ":" : "."); 719 if (CMSPrintObjectsInDump && !dead) { 720 oop(addr)->print_on(_st); 721 _st->print_cr("--------------------------------------"); 722 } 723 } else { // free block 724 _st->print_cr(PTR_FORMAT ": free block of size " SIZE_FORMAT "%s", 725 p2i(addr), sz, CMSPrintChunksInDump ? ":" : "."); 726 if (CMSPrintChunksInDump) { 727 ((FreeChunk*)addr)->print_on(_st); 728 _st->print_cr("--------------------------------------"); 729 } 730 } 731 return sz; 732 } 733 734 void CompactibleFreeListSpace::dump_at_safepoint_with_locks(CMSCollector* c, outputStream* st) { 735 st->print_cr("========================="); 736 st->print_cr("Block layout in CMS Heap:"); 737 st->print_cr("========================="); 738 BlkPrintingClosure bpcl(c, this, c->markBitMap(), st); 739 blk_iterate(&bpcl); 740 741 st->print_cr("======================================="); 742 st->print_cr("Order & Layout of Promotion Info Blocks"); 743 st->print_cr("======================================="); 744 print_promo_info_blocks(st); 745 746 st->print_cr("==========================="); 747 st->print_cr("Order of Indexed Free Lists"); 748 st->print_cr("========================="); 749 print_indexed_free_lists(st); 750 751 st->print_cr("================================="); 752 st->print_cr("Order of Free Lists in Dictionary"); 753 st->print_cr("================================="); 754 print_dictionary_free_lists(st); 755 } 756 757 758 void CompactibleFreeListSpace::reportFreeListStatistics(const char* title) const { 759 assert_lock_strong(&_freelistLock); 760 Log(gc, freelist, stats) log; 761 if (!log.is_debug()) { 762 return; 763 } 764 log.debug("%s", title); 765 766 LogStream out(log.debug()); 767 _dictionary->report_statistics(&out); 768 769 if (log.is_trace()) { 770 LogStream trace_out(log.trace()); 771 reportIndexedFreeListStatistics(&trace_out); 772 size_t total_size = totalSizeInIndexedFreeLists() + 773 _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())); 774 log.trace(" free=" SIZE_FORMAT " frag=%1.4f", total_size, flsFrag()); 775 } 776 } 777 778 void CompactibleFreeListSpace::reportIndexedFreeListStatistics(outputStream* st) const { 779 assert_lock_strong(&_freelistLock); 780 st->print_cr("Statistics for IndexedFreeLists:"); 781 st->print_cr("--------------------------------"); 782 size_t total_size = totalSizeInIndexedFreeLists(); 783 size_t free_blocks = numFreeBlocksInIndexedFreeLists(); 784 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size); 785 st->print_cr("Max Chunk Size: " SIZE_FORMAT, maxChunkSizeInIndexedFreeLists()); 786 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks); 787 if (free_blocks != 0) { 788 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks); 789 } 790 } 791 792 size_t CompactibleFreeListSpace::numFreeBlocksInIndexedFreeLists() const { 793 size_t res = 0; 794 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 795 debug_only( 796 ssize_t recount = 0; 797 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL; 798 fc = fc->next()) { 799 recount += 1; 800 } 801 assert(recount == _indexedFreeList[i].count(), 802 "Incorrect count in list"); 803 ) 804 res += _indexedFreeList[i].count(); 805 } 806 return res; 807 } 808 809 size_t CompactibleFreeListSpace::maxChunkSizeInIndexedFreeLists() const { 810 for (size_t i = IndexSetSize - 1; i != 0; i -= IndexSetStride) { 811 if (_indexedFreeList[i].head() != NULL) { 812 assert(_indexedFreeList[i].count() != 0, "Inconsistent FreeList"); 813 return (size_t)i; 814 } 815 } 816 return 0; 817 } 818 819 void CompactibleFreeListSpace::set_end(HeapWord* value) { 820 HeapWord* prevEnd = end(); 821 assert(prevEnd != value, "unnecessary set_end call"); 822 assert(prevEnd == NULL || !BlockOffsetArrayUseUnallocatedBlock || value >= unallocated_block(), 823 "New end is below unallocated block"); 824 _end = value; 825 if (prevEnd != NULL) { 826 // Resize the underlying block offset table. 827 _bt.resize(pointer_delta(value, bottom())); 828 if (value <= prevEnd) { 829 assert(!BlockOffsetArrayUseUnallocatedBlock || value >= unallocated_block(), 830 "New end is below unallocated block"); 831 } else { 832 // Now, take this new chunk and add it to the free blocks. 833 // Note that the BOT has not yet been updated for this block. 834 size_t newFcSize = pointer_delta(value, prevEnd); 835 // Add the block to the free lists, if possible coalescing it 836 // with the last free block, and update the BOT and census data. 837 addChunkToFreeListsAtEndRecordingStats(prevEnd, newFcSize); 838 } 839 } 840 } 841 842 class FreeListSpaceDCTOC : public FilteringDCTOC { 843 CompactibleFreeListSpace* _cfls; 844 CMSCollector* _collector; 845 bool _parallel; 846 protected: 847 // Override. 848 #define walk_mem_region_with_cl_DECL(ClosureType) \ 849 virtual void walk_mem_region_with_cl(MemRegion mr, \ 850 HeapWord* bottom, HeapWord* top, \ 851 ClosureType* cl); \ 852 void walk_mem_region_with_cl_par(MemRegion mr, \ 853 HeapWord* bottom, HeapWord* top, \ 854 ClosureType* cl); \ 855 void walk_mem_region_with_cl_nopar(MemRegion mr, \ 856 HeapWord* bottom, HeapWord* top, \ 857 ClosureType* cl) 858 walk_mem_region_with_cl_DECL(OopIterateClosure); 859 walk_mem_region_with_cl_DECL(FilteringClosure); 860 861 public: 862 FreeListSpaceDCTOC(CompactibleFreeListSpace* sp, 863 CMSCollector* collector, 864 OopIterateClosure* cl, 865 CardTable::PrecisionStyle precision, 866 HeapWord* boundary, 867 bool parallel) : 868 FilteringDCTOC(sp, cl, precision, boundary), 869 _cfls(sp), _collector(collector), _parallel(parallel) {} 870 }; 871 872 // We de-virtualize the block-related calls below, since we know that our 873 // space is a CompactibleFreeListSpace. 874 875 #define FreeListSpaceDCTOC__walk_mem_region_with_cl_DEFN(ClosureType) \ 876 void FreeListSpaceDCTOC::walk_mem_region_with_cl(MemRegion mr, \ 877 HeapWord* bottom, \ 878 HeapWord* top, \ 879 ClosureType* cl) { \ 880 if (_parallel) { \ 881 walk_mem_region_with_cl_par(mr, bottom, top, cl); \ 882 } else { \ 883 walk_mem_region_with_cl_nopar(mr, bottom, top, cl); \ 884 } \ 885 } \ 886 void FreeListSpaceDCTOC::walk_mem_region_with_cl_par(MemRegion mr, \ 887 HeapWord* bottom, \ 888 HeapWord* top, \ 889 ClosureType* cl) { \ 890 /* Skip parts that are before "mr", in case "block_start" sent us \ 891 back too far. */ \ 892 HeapWord* mr_start = mr.start(); \ 893 size_t bot_size = _cfls->CompactibleFreeListSpace::block_size(bottom); \ 894 HeapWord* next = bottom + bot_size; \ 895 while (next < mr_start) { \ 896 bottom = next; \ 897 bot_size = _cfls->CompactibleFreeListSpace::block_size(bottom); \ 898 next = bottom + bot_size; \ 899 } \ 900 \ 901 while (bottom < top) { \ 902 if (_cfls->CompactibleFreeListSpace::block_is_obj(bottom) && \ 903 !_cfls->CompactibleFreeListSpace::obj_allocated_since_save_marks( \ 904 oop(bottom)) && \ 905 !_collector->CMSCollector::is_dead_obj(oop(bottom))) { \ 906 size_t word_sz = oop(bottom)->oop_iterate_size(cl, mr); \ 907 bottom += _cfls->adjustObjectSize(word_sz); \ 908 } else { \ 909 bottom += _cfls->CompactibleFreeListSpace::block_size(bottom); \ 910 } \ 911 } \ 912 } \ 913 void FreeListSpaceDCTOC::walk_mem_region_with_cl_nopar(MemRegion mr, \ 914 HeapWord* bottom, \ 915 HeapWord* top, \ 916 ClosureType* cl) { \ 917 /* Skip parts that are before "mr", in case "block_start" sent us \ 918 back too far. */ \ 919 HeapWord* mr_start = mr.start(); \ 920 size_t bot_size = _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \ 921 HeapWord* next = bottom + bot_size; \ 922 while (next < mr_start) { \ 923 bottom = next; \ 924 bot_size = _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \ 925 next = bottom + bot_size; \ 926 } \ 927 \ 928 while (bottom < top) { \ 929 if (_cfls->CompactibleFreeListSpace::block_is_obj_nopar(bottom) && \ 930 !_cfls->CompactibleFreeListSpace::obj_allocated_since_save_marks( \ 931 oop(bottom)) && \ 932 !_collector->CMSCollector::is_dead_obj(oop(bottom))) { \ 933 size_t word_sz = oop(bottom)->oop_iterate_size(cl, mr); \ 934 bottom += _cfls->adjustObjectSize(word_sz); \ 935 } else { \ 936 bottom += _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \ 937 } \ 938 } \ 939 } 940 941 // (There are only two of these, rather than N, because the split is due 942 // only to the introduction of the FilteringClosure, a local part of the 943 // impl of this abstraction.) 944 FreeListSpaceDCTOC__walk_mem_region_with_cl_DEFN(OopIterateClosure) 945 FreeListSpaceDCTOC__walk_mem_region_with_cl_DEFN(FilteringClosure) 946 947 DirtyCardToOopClosure* 948 CompactibleFreeListSpace::new_dcto_cl(OopIterateClosure* cl, 949 CardTable::PrecisionStyle precision, 950 HeapWord* boundary, 951 bool parallel) { 952 return new FreeListSpaceDCTOC(this, _collector, cl, precision, boundary, parallel); 953 } 954 955 956 // Note on locking for the space iteration functions: 957 // since the collector's iteration activities are concurrent with 958 // allocation activities by mutators, absent a suitable mutual exclusion 959 // mechanism the iterators may go awry. For instance a block being iterated 960 // may suddenly be allocated or divided up and part of it allocated and 961 // so on. 962 963 // Apply the given closure to each block in the space. 964 void CompactibleFreeListSpace::blk_iterate_careful(BlkClosureCareful* cl) { 965 assert_lock_strong(freelistLock()); 966 HeapWord *cur, *limit; 967 for (cur = bottom(), limit = end(); cur < limit; 968 cur += cl->do_blk_careful(cur)); 969 } 970 971 // Apply the given closure to each block in the space. 972 void CompactibleFreeListSpace::blk_iterate(BlkClosure* cl) { 973 assert_lock_strong(freelistLock()); 974 HeapWord *cur, *limit; 975 for (cur = bottom(), limit = end(); cur < limit; 976 cur += cl->do_blk(cur)); 977 } 978 979 // Apply the given closure to each oop in the space. 980 void CompactibleFreeListSpace::oop_iterate(OopIterateClosure* cl) { 981 assert_lock_strong(freelistLock()); 982 HeapWord *cur, *limit; 983 size_t curSize; 984 for (cur = bottom(), limit = end(); cur < limit; 985 cur += curSize) { 986 curSize = block_size(cur); 987 if (block_is_obj(cur)) { 988 oop(cur)->oop_iterate(cl); 989 } 990 } 991 } 992 993 // NOTE: In the following methods, in order to safely be able to 994 // apply the closure to an object, we need to be sure that the 995 // object has been initialized. We are guaranteed that an object 996 // is initialized if we are holding the Heap_lock with the 997 // world stopped. 998 void CompactibleFreeListSpace::verify_objects_initialized() const { 999 if (is_init_completed()) { 1000 assert_locked_or_safepoint(Heap_lock); 1001 if (Universe::is_fully_initialized()) { 1002 guarantee(SafepointSynchronize::is_at_safepoint(), 1003 "Required for objects to be initialized"); 1004 } 1005 } // else make a concession at vm start-up 1006 } 1007 1008 // Apply the given closure to each object in the space 1009 void CompactibleFreeListSpace::object_iterate(ObjectClosure* blk) { 1010 assert_lock_strong(freelistLock()); 1011 NOT_PRODUCT(verify_objects_initialized()); 1012 HeapWord *cur, *limit; 1013 size_t curSize; 1014 for (cur = bottom(), limit = end(); cur < limit; 1015 cur += curSize) { 1016 curSize = block_size(cur); 1017 if (block_is_obj(cur)) { 1018 blk->do_object(oop(cur)); 1019 } 1020 } 1021 } 1022 1023 // Apply the given closure to each live object in the space 1024 // The usage of CompactibleFreeListSpace 1025 // by the ConcurrentMarkSweepGeneration for concurrent GC's allows 1026 // objects in the space with references to objects that are no longer 1027 // valid. For example, an object may reference another object 1028 // that has already been sweep up (collected). This method uses 1029 // obj_is_alive() to determine whether it is safe to apply the closure to 1030 // an object. See obj_is_alive() for details on how liveness of an 1031 // object is decided. 1032 1033 void CompactibleFreeListSpace::safe_object_iterate(ObjectClosure* blk) { 1034 assert_lock_strong(freelistLock()); 1035 NOT_PRODUCT(verify_objects_initialized()); 1036 HeapWord *cur, *limit; 1037 size_t curSize; 1038 for (cur = bottom(), limit = end(); cur < limit; 1039 cur += curSize) { 1040 curSize = block_size(cur); 1041 if (block_is_obj(cur) && obj_is_alive(cur)) { 1042 blk->do_object(oop(cur)); 1043 } 1044 } 1045 } 1046 1047 void CompactibleFreeListSpace::object_iterate_mem(MemRegion mr, 1048 UpwardsObjectClosure* cl) { 1049 assert_locked(freelistLock()); 1050 NOT_PRODUCT(verify_objects_initialized()); 1051 assert(!mr.is_empty(), "Should be non-empty"); 1052 // We use MemRegion(bottom(), end()) rather than used_region() below 1053 // because the two are not necessarily equal for some kinds of 1054 // spaces, in particular, certain kinds of free list spaces. 1055 // We could use the more complicated but more precise: 1056 // MemRegion(used_region().start(), align_up(used_region().end(), CardSize)) 1057 // but the slight imprecision seems acceptable in the assertion check. 1058 assert(MemRegion(bottom(), end()).contains(mr), 1059 "Should be within used space"); 1060 HeapWord* prev = cl->previous(); // max address from last time 1061 if (prev >= mr.end()) { // nothing to do 1062 return; 1063 } 1064 // This assert will not work when we go from cms space to perm 1065 // space, and use same closure. Easy fix deferred for later. XXX YSR 1066 // assert(prev == NULL || contains(prev), "Should be within space"); 1067 1068 bool last_was_obj_array = false; 1069 HeapWord *blk_start_addr, *region_start_addr; 1070 if (prev > mr.start()) { 1071 region_start_addr = prev; 1072 blk_start_addr = prev; 1073 // The previous invocation may have pushed "prev" beyond the 1074 // last allocated block yet there may be still be blocks 1075 // in this region due to a particular coalescing policy. 1076 // Relax the assertion so that the case where the unallocated 1077 // block is maintained and "prev" is beyond the unallocated 1078 // block does not cause the assertion to fire. 1079 assert((BlockOffsetArrayUseUnallocatedBlock && 1080 (!is_in(prev))) || 1081 (blk_start_addr == block_start(region_start_addr)), "invariant"); 1082 } else { 1083 region_start_addr = mr.start(); 1084 blk_start_addr = block_start(region_start_addr); 1085 } 1086 HeapWord* region_end_addr = mr.end(); 1087 MemRegion derived_mr(region_start_addr, region_end_addr); 1088 while (blk_start_addr < region_end_addr) { 1089 const size_t size = block_size(blk_start_addr); 1090 if (block_is_obj(blk_start_addr)) { 1091 last_was_obj_array = cl->do_object_bm(oop(blk_start_addr), derived_mr); 1092 } else { 1093 last_was_obj_array = false; 1094 } 1095 blk_start_addr += size; 1096 } 1097 if (!last_was_obj_array) { 1098 assert((bottom() <= blk_start_addr) && (blk_start_addr <= end()), 1099 "Should be within (closed) used space"); 1100 assert(blk_start_addr > prev, "Invariant"); 1101 cl->set_previous(blk_start_addr); // min address for next time 1102 } 1103 } 1104 1105 // Callers of this iterator beware: The closure application should 1106 // be robust in the face of uninitialized objects and should (always) 1107 // return a correct size so that the next addr + size below gives us a 1108 // valid block boundary. [See for instance, 1109 // ScanMarkedObjectsAgainCarefullyClosure::do_object_careful() 1110 // in ConcurrentMarkSweepGeneration.cpp.] 1111 HeapWord* 1112 CompactibleFreeListSpace::object_iterate_careful_m(MemRegion mr, 1113 ObjectClosureCareful* cl) { 1114 assert_lock_strong(freelistLock()); 1115 // Can't use used_region() below because it may not necessarily 1116 // be the same as [bottom(),end()); although we could 1117 // use [used_region().start(),align_up(used_region().end(),CardSize)), 1118 // that appears too cumbersome, so we just do the simpler check 1119 // in the assertion below. 1120 assert(!mr.is_empty() && MemRegion(bottom(),end()).contains(mr), 1121 "mr should be non-empty and within used space"); 1122 HeapWord *addr, *end; 1123 size_t size; 1124 for (addr = block_start_careful(mr.start()), end = mr.end(); 1125 addr < end; addr += size) { 1126 FreeChunk* fc = (FreeChunk*)addr; 1127 if (fc->is_free()) { 1128 // Since we hold the free list lock, which protects direct 1129 // allocation in this generation by mutators, a free object 1130 // will remain free throughout this iteration code. 1131 size = fc->size(); 1132 } else { 1133 // Note that the object need not necessarily be initialized, 1134 // because (for instance) the free list lock does NOT protect 1135 // object initialization. The closure application below must 1136 // therefore be correct in the face of uninitialized objects. 1137 size = cl->do_object_careful_m(oop(addr), mr); 1138 if (size == 0) { 1139 // An unparsable object found. Signal early termination. 1140 return addr; 1141 } 1142 } 1143 } 1144 return NULL; 1145 } 1146 1147 1148 HeapWord* CompactibleFreeListSpace::block_start_const(const void* p) const { 1149 NOT_PRODUCT(verify_objects_initialized()); 1150 return _bt.block_start(p); 1151 } 1152 1153 HeapWord* CompactibleFreeListSpace::block_start_careful(const void* p) const { 1154 return _bt.block_start_careful(p); 1155 } 1156 1157 size_t CompactibleFreeListSpace::block_size(const HeapWord* p) const { 1158 NOT_PRODUCT(verify_objects_initialized()); 1159 // This must be volatile, or else there is a danger that the compiler 1160 // will compile the code below into a sometimes-infinite loop, by keeping 1161 // the value read the first time in a register. 1162 while (true) { 1163 // We must do this until we get a consistent view of the object. 1164 if (FreeChunk::indicatesFreeChunk(p)) { 1165 volatile FreeChunk* fc = (volatile FreeChunk*)p; 1166 size_t res = fc->size(); 1167 1168 // Bugfix for systems with weak memory model (PPC64/IA64). The 1169 // block's free bit was set and we have read the size of the 1170 // block. Acquire and check the free bit again. If the block is 1171 // still free, the read size is correct. 1172 OrderAccess::acquire(); 1173 1174 // If the object is still a free chunk, return the size, else it 1175 // has been allocated so try again. 1176 if (FreeChunk::indicatesFreeChunk(p)) { 1177 assert(res != 0, "Block size should not be 0"); 1178 return res; 1179 } 1180 } else { 1181 // Ensure klass read before size. 1182 Klass* k = oop(p)->klass_or_null_acquire(); 1183 if (k != NULL) { 1184 assert(k->is_klass(), "Should really be klass oop."); 1185 oop o = (oop)p; 1186 assert(oopDesc::is_oop(o, true /* ignore mark word */), "Should be an oop."); 1187 1188 size_t res = o->size_given_klass(k); 1189 res = adjustObjectSize(res); 1190 assert(res != 0, "Block size should not be 0"); 1191 return res; 1192 } 1193 } 1194 } 1195 } 1196 1197 // TODO: Now that is_parsable is gone, we should combine these two functions. 1198 // A variant of the above that uses the Printezis bits for 1199 // unparsable but allocated objects. This avoids any possible 1200 // stalls waiting for mutators to initialize objects, and is 1201 // thus potentially faster than the variant above. However, 1202 // this variant may return a zero size for a block that is 1203 // under mutation and for which a consistent size cannot be 1204 // inferred without stalling; see CMSCollector::block_size_if_printezis_bits(). 1205 size_t CompactibleFreeListSpace::block_size_no_stall(HeapWord* p, 1206 const CMSCollector* c) 1207 const { 1208 assert(MemRegion(bottom(), end()).contains(p), "p not in space"); 1209 // This must be volatile, or else there is a danger that the compiler 1210 // will compile the code below into a sometimes-infinite loop, by keeping 1211 // the value read the first time in a register. 1212 DEBUG_ONLY(uint loops = 0;) 1213 while (true) { 1214 // We must do this until we get a consistent view of the object. 1215 if (FreeChunk::indicatesFreeChunk(p)) { 1216 volatile FreeChunk* fc = (volatile FreeChunk*)p; 1217 size_t res = fc->size(); 1218 1219 // Bugfix for systems with weak memory model (PPC64/IA64). The 1220 // free bit of the block was set and we have read the size of 1221 // the block. Acquire and check the free bit again. If the 1222 // block is still free, the read size is correct. 1223 OrderAccess::acquire(); 1224 1225 if (FreeChunk::indicatesFreeChunk(p)) { 1226 assert(res != 0, "Block size should not be 0"); 1227 assert(loops == 0, "Should be 0"); 1228 return res; 1229 } 1230 } else { 1231 // Ensure klass read before size. 1232 Klass* k = oop(p)->klass_or_null_acquire(); 1233 if (k != NULL) { 1234 assert(k->is_klass(), "Should really be klass oop."); 1235 oop o = (oop)p; 1236 assert(oopDesc::is_oop(o), "Should be an oop"); 1237 1238 size_t res = o->size_given_klass(k); 1239 res = adjustObjectSize(res); 1240 assert(res != 0, "Block size should not be 0"); 1241 return res; 1242 } else { 1243 // May return 0 if P-bits not present. 1244 return c->block_size_if_printezis_bits(p); 1245 } 1246 } 1247 assert(loops == 0, "Can loop at most once"); 1248 DEBUG_ONLY(loops++;) 1249 } 1250 } 1251 1252 size_t CompactibleFreeListSpace::block_size_nopar(const HeapWord* p) const { 1253 NOT_PRODUCT(verify_objects_initialized()); 1254 assert(MemRegion(bottom(), end()).contains(p), "p not in space"); 1255 FreeChunk* fc = (FreeChunk*)p; 1256 if (fc->is_free()) { 1257 return fc->size(); 1258 } else { 1259 // Ignore mark word because this may be a recently promoted 1260 // object whose mark word is used to chain together grey 1261 // objects (the last one would have a null value). 1262 assert(oopDesc::is_oop(oop(p), true), "Should be an oop"); 1263 return adjustObjectSize(oop(p)->size()); 1264 } 1265 } 1266 1267 // This implementation assumes that the property of "being an object" is 1268 // stable. But being a free chunk may not be (because of parallel 1269 // promotion.) 1270 bool CompactibleFreeListSpace::block_is_obj(const HeapWord* p) const { 1271 FreeChunk* fc = (FreeChunk*)p; 1272 assert(is_in_reserved(p), "Should be in space"); 1273 if (FreeChunk::indicatesFreeChunk(p)) return false; 1274 Klass* k = oop(p)->klass_or_null_acquire(); 1275 if (k != NULL) { 1276 // Ignore mark word because it may have been used to 1277 // chain together promoted objects (the last one 1278 // would have a null value). 1279 assert(oopDesc::is_oop(oop(p), true), "Should be an oop"); 1280 return true; 1281 } else { 1282 return false; // Was not an object at the start of collection. 1283 } 1284 } 1285 1286 // Check if the object is alive. This fact is checked either by consulting 1287 // the main marking bitmap in the sweeping phase or, if it's a permanent 1288 // generation and we're not in the sweeping phase, by checking the 1289 // perm_gen_verify_bit_map where we store the "deadness" information if 1290 // we did not sweep the perm gen in the most recent previous GC cycle. 1291 bool CompactibleFreeListSpace::obj_is_alive(const HeapWord* p) const { 1292 assert(SafepointSynchronize::is_at_safepoint() || !is_init_completed(), 1293 "Else races are possible"); 1294 assert(block_is_obj(p), "The address should point to an object"); 1295 1296 // If we're sweeping, we use object liveness information from the main bit map 1297 // for both perm gen and old gen. 1298 // We don't need to lock the bitmap (live_map or dead_map below), because 1299 // EITHER we are in the middle of the sweeping phase, and the 1300 // main marking bit map (live_map below) is locked, 1301 // OR we're in other phases and perm_gen_verify_bit_map (dead_map below) 1302 // is stable, because it's mutated only in the sweeping phase. 1303 // NOTE: This method is also used by jmap where, if class unloading is 1304 // off, the results can return "false" for legitimate perm objects, 1305 // when we are not in the midst of a sweeping phase, which can result 1306 // in jmap not reporting certain perm gen objects. This will be moot 1307 // if/when the perm gen goes away in the future. 1308 if (_collector->abstract_state() == CMSCollector::Sweeping) { 1309 CMSBitMap* live_map = _collector->markBitMap(); 1310 return live_map->par_isMarked((HeapWord*) p); 1311 } 1312 return true; 1313 } 1314 1315 bool CompactibleFreeListSpace::block_is_obj_nopar(const HeapWord* p) const { 1316 FreeChunk* fc = (FreeChunk*)p; 1317 assert(is_in_reserved(p), "Should be in space"); 1318 assert(_bt.block_start(p) == p, "Should be a block boundary"); 1319 if (!fc->is_free()) { 1320 // Ignore mark word because it may have been used to 1321 // chain together promoted objects (the last one 1322 // would have a null value). 1323 assert(oopDesc::is_oop(oop(p), true), "Should be an oop"); 1324 return true; 1325 } 1326 return false; 1327 } 1328 1329 // "MT-safe but not guaranteed MT-precise" (TM); you may get an 1330 // approximate answer if you don't hold the freelistlock when you call this. 1331 size_t CompactibleFreeListSpace::totalSizeInIndexedFreeLists() const { 1332 size_t size = 0; 1333 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 1334 debug_only( 1335 // We may be calling here without the lock in which case we 1336 // won't do this modest sanity check. 1337 if (freelistLock()->owned_by_self()) { 1338 size_t total_list_size = 0; 1339 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL; 1340 fc = fc->next()) { 1341 total_list_size += i; 1342 } 1343 assert(total_list_size == i * _indexedFreeList[i].count(), 1344 "Count in list is incorrect"); 1345 } 1346 ) 1347 size += i * _indexedFreeList[i].count(); 1348 } 1349 return size; 1350 } 1351 1352 HeapWord* CompactibleFreeListSpace::par_allocate(size_t size) { 1353 MutexLocker x(freelistLock(), Mutex::_no_safepoint_check_flag); 1354 return allocate(size); 1355 } 1356 1357 HeapWord* 1358 CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlockRemainder(size_t size) { 1359 return getChunkFromLinearAllocBlockRemainder(&_smallLinearAllocBlock, size); 1360 } 1361 1362 HeapWord* CompactibleFreeListSpace::allocate(size_t size) { 1363 assert_lock_strong(freelistLock()); 1364 HeapWord* res = NULL; 1365 assert(size == adjustObjectSize(size), 1366 "use adjustObjectSize() before calling into allocate()"); 1367 1368 res = allocate_adaptive_freelists(size); 1369 1370 if (res != NULL) { 1371 // check that res does lie in this space! 1372 assert(is_in_reserved(res), "Not in this space!"); 1373 assert(is_aligned((void*)res), "alignment check"); 1374 1375 FreeChunk* fc = (FreeChunk*)res; 1376 fc->markNotFree(); 1377 assert(!fc->is_free(), "shouldn't be marked free"); 1378 assert(oop(fc)->klass_or_null() == NULL, "should look uninitialized"); 1379 // Verify that the block offset table shows this to 1380 // be a single block, but not one which is unallocated. 1381 _bt.verify_single_block(res, size); 1382 _bt.verify_not_unallocated(res, size); 1383 // mangle a just allocated object with a distinct pattern. 1384 debug_only(fc->mangleAllocated(size)); 1385 } 1386 1387 // During GC we do not need to recalculate the stable used value for 1388 // every allocation in old gen. It is done once at the end of GC instead 1389 // for performance reasons. 1390 if (!CMSHeap::heap()->is_gc_active()) { 1391 recalculate_used_stable(); 1392 } 1393 1394 return res; 1395 } 1396 1397 HeapWord* CompactibleFreeListSpace::allocate_adaptive_freelists(size_t size) { 1398 assert_lock_strong(freelistLock()); 1399 HeapWord* res = NULL; 1400 assert(size == adjustObjectSize(size), 1401 "use adjustObjectSize() before calling into allocate()"); 1402 1403 // Strategy 1404 // if small 1405 // exact size from small object indexed list if small 1406 // small or large linear allocation block (linAB) as appropriate 1407 // take from lists of greater sized chunks 1408 // else 1409 // dictionary 1410 // small or large linear allocation block if it has the space 1411 // Try allocating exact size from indexTable first 1412 if (size < IndexSetSize) { 1413 res = (HeapWord*) getChunkFromIndexedFreeList(size); 1414 if(res != NULL) { 1415 assert(res != (HeapWord*)_indexedFreeList[size].head(), 1416 "Not removed from free list"); 1417 // no block offset table adjustment is necessary on blocks in 1418 // the indexed lists. 1419 1420 // Try allocating from the small LinAB 1421 } else if (size < _smallLinearAllocBlock._allocation_size_limit && 1422 (res = getChunkFromSmallLinearAllocBlock(size)) != NULL) { 1423 // if successful, the above also adjusts block offset table 1424 // Note that this call will refill the LinAB to 1425 // satisfy the request. This is different that 1426 // evm. 1427 // Don't record chunk off a LinAB? smallSplitBirth(size); 1428 } else { 1429 // Raid the exact free lists larger than size, even if they are not 1430 // overpopulated. 1431 res = (HeapWord*) getChunkFromGreater(size); 1432 } 1433 } else { 1434 // Big objects get allocated directly from the dictionary. 1435 res = (HeapWord*) getChunkFromDictionaryExact(size); 1436 if (res == NULL) { 1437 // Try hard not to fail since an allocation failure will likely 1438 // trigger a synchronous GC. Try to get the space from the 1439 // allocation blocks. 1440 res = getChunkFromSmallLinearAllocBlockRemainder(size); 1441 } 1442 } 1443 1444 return res; 1445 } 1446 1447 // A worst-case estimate of the space required (in HeapWords) to expand the heap 1448 // when promoting obj. 1449 size_t CompactibleFreeListSpace::expansionSpaceRequired(size_t obj_size) const { 1450 // Depending on the object size, expansion may require refilling either a 1451 // bigLAB or a smallLAB plus refilling a PromotionInfo object. MinChunkSize 1452 // is added because the dictionary may over-allocate to avoid fragmentation. 1453 size_t space = obj_size; 1454 space += _promoInfo.refillSize() + 2 * MinChunkSize; 1455 return space; 1456 } 1457 1458 FreeChunk* CompactibleFreeListSpace::getChunkFromGreater(size_t numWords) { 1459 FreeChunk* ret; 1460 1461 assert(numWords >= MinChunkSize, "Size is less than minimum"); 1462 assert(linearAllocationWouldFail() || bestFitFirst(), 1463 "Should not be here"); 1464 1465 size_t i; 1466 size_t currSize = numWords + MinChunkSize; 1467 assert(is_object_aligned(currSize), "currSize should be aligned"); 1468 for (i = currSize; i < IndexSetSize; i += IndexSetStride) { 1469 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i]; 1470 if (fl->head()) { 1471 ret = getFromListGreater(fl, numWords); 1472 assert(ret == NULL || ret->is_free(), "Should be returning a free chunk"); 1473 return ret; 1474 } 1475 } 1476 1477 currSize = MAX2((size_t)SmallForDictionary, 1478 (size_t)(numWords + MinChunkSize)); 1479 1480 /* Try to get a chunk that satisfies request, while avoiding 1481 fragmentation that can't be handled. */ 1482 { 1483 ret = dictionary()->get_chunk(currSize); 1484 if (ret != NULL) { 1485 assert(ret->size() - numWords >= MinChunkSize, 1486 "Chunk is too small"); 1487 _bt.allocated((HeapWord*)ret, ret->size()); 1488 /* Carve returned chunk. */ 1489 (void) splitChunkAndReturnRemainder(ret, numWords); 1490 /* Label this as no longer a free chunk. */ 1491 assert(ret->is_free(), "This chunk should be free"); 1492 ret->link_prev(NULL); 1493 } 1494 assert(ret == NULL || ret->is_free(), "Should be returning a free chunk"); 1495 return ret; 1496 } 1497 ShouldNotReachHere(); 1498 } 1499 1500 bool CompactibleFreeListSpace::verifyChunkInIndexedFreeLists(FreeChunk* fc) const { 1501 assert(fc->size() < IndexSetSize, "Size of chunk is too large"); 1502 return _indexedFreeList[fc->size()].verify_chunk_in_free_list(fc); 1503 } 1504 1505 bool CompactibleFreeListSpace::verify_chunk_is_linear_alloc_block(FreeChunk* fc) const { 1506 assert((_smallLinearAllocBlock._ptr != (HeapWord*)fc) || 1507 (_smallLinearAllocBlock._word_size == fc->size()), 1508 "Linear allocation block shows incorrect size"); 1509 return ((_smallLinearAllocBlock._ptr == (HeapWord*)fc) && 1510 (_smallLinearAllocBlock._word_size == fc->size())); 1511 } 1512 1513 // Check if the purported free chunk is present either as a linear 1514 // allocation block, the size-indexed table of (smaller) free blocks, 1515 // or the larger free blocks kept in the binary tree dictionary. 1516 bool CompactibleFreeListSpace::verify_chunk_in_free_list(FreeChunk* fc) const { 1517 if (verify_chunk_is_linear_alloc_block(fc)) { 1518 return true; 1519 } else if (fc->size() < IndexSetSize) { 1520 return verifyChunkInIndexedFreeLists(fc); 1521 } else { 1522 return dictionary()->verify_chunk_in_free_list(fc); 1523 } 1524 } 1525 1526 #ifndef PRODUCT 1527 void CompactibleFreeListSpace::assert_locked() const { 1528 CMSLockVerifier::assert_locked(freelistLock(), parDictionaryAllocLock()); 1529 } 1530 1531 void CompactibleFreeListSpace::assert_locked(const Mutex* lock) const { 1532 CMSLockVerifier::assert_locked(lock); 1533 } 1534 #endif 1535 1536 FreeChunk* CompactibleFreeListSpace::allocateScratch(size_t size) { 1537 // In the parallel case, the main thread holds the free list lock 1538 // on behalf the parallel threads. 1539 FreeChunk* fc; 1540 { 1541 // If GC is parallel, this might be called by several threads. 1542 // This should be rare enough that the locking overhead won't affect 1543 // the sequential code. 1544 MutexLocker x(parDictionaryAllocLock(), 1545 Mutex::_no_safepoint_check_flag); 1546 fc = getChunkFromDictionary(size); 1547 } 1548 if (fc != NULL) { 1549 fc->dontCoalesce(); 1550 assert(fc->is_free(), "Should be free, but not coalescable"); 1551 // Verify that the block offset table shows this to 1552 // be a single block, but not one which is unallocated. 1553 _bt.verify_single_block((HeapWord*)fc, fc->size()); 1554 _bt.verify_not_unallocated((HeapWord*)fc, fc->size()); 1555 } 1556 return fc; 1557 } 1558 1559 oop CompactibleFreeListSpace::promote(oop obj, size_t obj_size) { 1560 assert(obj_size == (size_t)obj->size(), "bad obj_size passed in"); 1561 assert_locked(); 1562 1563 // if we are tracking promotions, then first ensure space for 1564 // promotion (including spooling space for saving header if necessary). 1565 // then allocate and copy, then track promoted info if needed. 1566 // When tracking (see PromotionInfo::track()), the mark word may 1567 // be displaced and in this case restoration of the mark word 1568 // occurs in the (oop_since_save_marks_)iterate phase. 1569 if (_promoInfo.tracking() && !_promoInfo.ensure_spooling_space()) { 1570 return NULL; 1571 } 1572 // Call the allocate(size_t, bool) form directly to avoid the 1573 // additional call through the allocate(size_t) form. Having 1574 // the compile inline the call is problematic because allocate(size_t) 1575 // is a virtual method. 1576 HeapWord* res = allocate(adjustObjectSize(obj_size)); 1577 if (res != NULL) { 1578 Copy::aligned_disjoint_words((HeapWord*)obj, res, obj_size); 1579 // if we should be tracking promotions, do so. 1580 if (_promoInfo.tracking()) { 1581 _promoInfo.track((PromotedObject*)res); 1582 } 1583 } 1584 return oop(res); 1585 } 1586 1587 HeapWord* 1588 CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlock(size_t size) { 1589 assert_locked(); 1590 assert(size >= MinChunkSize, "minimum chunk size"); 1591 assert(size < _smallLinearAllocBlock._allocation_size_limit, 1592 "maximum from smallLinearAllocBlock"); 1593 return getChunkFromLinearAllocBlock(&_smallLinearAllocBlock, size); 1594 } 1595 1596 HeapWord* 1597 CompactibleFreeListSpace::getChunkFromLinearAllocBlock(LinearAllocBlock *blk, 1598 size_t size) { 1599 assert_locked(); 1600 assert(size >= MinChunkSize, "too small"); 1601 HeapWord* res = NULL; 1602 // Try to do linear allocation from blk, making sure that 1603 if (blk->_word_size == 0) { 1604 // We have probably been unable to fill this either in the prologue or 1605 // when it was exhausted at the last linear allocation. Bail out until 1606 // next time. 1607 assert(blk->_ptr == NULL, "consistency check"); 1608 return NULL; 1609 } 1610 assert(blk->_word_size != 0 && blk->_ptr != NULL, "consistency check"); 1611 res = getChunkFromLinearAllocBlockRemainder(blk, size); 1612 if (res != NULL) return res; 1613 1614 // about to exhaust this linear allocation block 1615 if (blk->_word_size == size) { // exactly satisfied 1616 res = blk->_ptr; 1617 _bt.allocated(res, blk->_word_size); 1618 } else if (size + MinChunkSize <= blk->_refillSize) { 1619 size_t sz = blk->_word_size; 1620 // Update _unallocated_block if the size is such that chunk would be 1621 // returned to the indexed free list. All other chunks in the indexed 1622 // free lists are allocated from the dictionary so that _unallocated_block 1623 // has already been adjusted for them. Do it here so that the cost 1624 // for all chunks added back to the indexed free lists. 1625 if (sz < SmallForDictionary) { 1626 _bt.allocated(blk->_ptr, sz); 1627 } 1628 // Return the chunk that isn't big enough, and then refill below. 1629 addChunkToFreeLists(blk->_ptr, sz); 1630 split_birth(sz); 1631 // Don't keep statistics on adding back chunk from a LinAB. 1632 } else { 1633 // A refilled block would not satisfy the request. 1634 return NULL; 1635 } 1636 1637 blk->_ptr = NULL; blk->_word_size = 0; 1638 refillLinearAllocBlock(blk); 1639 assert(blk->_ptr == NULL || blk->_word_size >= size + MinChunkSize, 1640 "block was replenished"); 1641 if (res != NULL) { 1642 split_birth(size); 1643 repairLinearAllocBlock(blk); 1644 } else if (blk->_ptr != NULL) { 1645 res = blk->_ptr; 1646 size_t blk_size = blk->_word_size; 1647 blk->_word_size -= size; 1648 blk->_ptr += size; 1649 split_birth(size); 1650 repairLinearAllocBlock(blk); 1651 // Update BOT last so that other (parallel) GC threads see a consistent 1652 // view of the BOT and free blocks. 1653 // Above must occur before BOT is updated below. 1654 OrderAccess::storestore(); 1655 _bt.split_block(res, blk_size, size); // adjust block offset table 1656 } 1657 return res; 1658 } 1659 1660 HeapWord* CompactibleFreeListSpace::getChunkFromLinearAllocBlockRemainder( 1661 LinearAllocBlock* blk, 1662 size_t size) { 1663 assert_locked(); 1664 assert(size >= MinChunkSize, "too small"); 1665 1666 HeapWord* res = NULL; 1667 // This is the common case. Keep it simple. 1668 if (blk->_word_size >= size + MinChunkSize) { 1669 assert(blk->_ptr != NULL, "consistency check"); 1670 res = blk->_ptr; 1671 // Note that the BOT is up-to-date for the linAB before allocation. It 1672 // indicates the start of the linAB. The split_block() updates the 1673 // BOT for the linAB after the allocation (indicates the start of the 1674 // next chunk to be allocated). 1675 size_t blk_size = blk->_word_size; 1676 blk->_word_size -= size; 1677 blk->_ptr += size; 1678 split_birth(size); 1679 repairLinearAllocBlock(blk); 1680 // Update BOT last so that other (parallel) GC threads see a consistent 1681 // view of the BOT and free blocks. 1682 // Above must occur before BOT is updated below. 1683 OrderAccess::storestore(); 1684 _bt.split_block(res, blk_size, size); // adjust block offset table 1685 _bt.allocated(res, size); 1686 } 1687 return res; 1688 } 1689 1690 FreeChunk* 1691 CompactibleFreeListSpace::getChunkFromIndexedFreeList(size_t size) { 1692 assert_locked(); 1693 assert(size < SmallForDictionary, "just checking"); 1694 FreeChunk* res; 1695 res = _indexedFreeList[size].get_chunk_at_head(); 1696 if (res == NULL) { 1697 res = getChunkFromIndexedFreeListHelper(size); 1698 } 1699 _bt.verify_not_unallocated((HeapWord*) res, size); 1700 assert(res == NULL || res->size() == size, "Incorrect block size"); 1701 return res; 1702 } 1703 1704 FreeChunk* 1705 CompactibleFreeListSpace::getChunkFromIndexedFreeListHelper(size_t size, 1706 bool replenish) { 1707 assert_locked(); 1708 FreeChunk* fc = NULL; 1709 if (size < SmallForDictionary) { 1710 assert(_indexedFreeList[size].head() == NULL || 1711 _indexedFreeList[size].surplus() <= 0, 1712 "List for this size should be empty or under populated"); 1713 // Try best fit in exact lists before replenishing the list 1714 if (!bestFitFirst() || (fc = bestFitSmall(size)) == NULL) { 1715 // Replenish list. 1716 // 1717 // Things tried that failed. 1718 // Tried allocating out of the two LinAB's first before 1719 // replenishing lists. 1720 // Tried small linAB of size 256 (size in indexed list) 1721 // and replenishing indexed lists from the small linAB. 1722 // 1723 FreeChunk* newFc = NULL; 1724 const size_t replenish_size = CMSIndexedFreeListReplenish * size; 1725 if (replenish_size < SmallForDictionary) { 1726 // Do not replenish from an underpopulated size. 1727 if (_indexedFreeList[replenish_size].surplus() > 0 && 1728 _indexedFreeList[replenish_size].head() != NULL) { 1729 newFc = _indexedFreeList[replenish_size].get_chunk_at_head(); 1730 } else if (bestFitFirst()) { 1731 newFc = bestFitSmall(replenish_size); 1732 } 1733 } 1734 if (newFc == NULL && replenish_size > size) { 1735 assert(CMSIndexedFreeListReplenish > 1, "ctl pt invariant"); 1736 newFc = getChunkFromIndexedFreeListHelper(replenish_size, false); 1737 } 1738 // Note: The stats update re split-death of block obtained above 1739 // will be recorded below precisely when we know we are going to 1740 // be actually splitting it into more than one pieces below. 1741 if (newFc != NULL) { 1742 if (replenish || CMSReplenishIntermediate) { 1743 // Replenish this list and return one block to caller. 1744 size_t i; 1745 FreeChunk *curFc, *nextFc; 1746 size_t num_blk = newFc->size() / size; 1747 assert(num_blk >= 1, "Smaller than requested?"); 1748 assert(newFc->size() % size == 0, "Should be integral multiple of request"); 1749 if (num_blk > 1) { 1750 // we are sure we will be splitting the block just obtained 1751 // into multiple pieces; record the split-death of the original 1752 splitDeath(replenish_size); 1753 } 1754 // carve up and link blocks 0, ..., num_blk - 2 1755 // The last chunk is not added to the lists but is returned as the 1756 // free chunk. 1757 for (curFc = newFc, nextFc = (FreeChunk*)((HeapWord*)curFc + size), 1758 i = 0; 1759 i < (num_blk - 1); 1760 curFc = nextFc, nextFc = (FreeChunk*)((HeapWord*)nextFc + size), 1761 i++) { 1762 curFc->set_size(size); 1763 // Don't record this as a return in order to try and 1764 // determine the "returns" from a GC. 1765 _bt.verify_not_unallocated((HeapWord*) fc, size); 1766 _indexedFreeList[size].return_chunk_at_tail(curFc, false); 1767 _bt.mark_block((HeapWord*)curFc, size); 1768 split_birth(size); 1769 // Don't record the initial population of the indexed list 1770 // as a split birth. 1771 } 1772 1773 // check that the arithmetic was OK above 1774 assert((HeapWord*)nextFc == (HeapWord*)newFc + num_blk*size, 1775 "inconsistency in carving newFc"); 1776 curFc->set_size(size); 1777 _bt.mark_block((HeapWord*)curFc, size); 1778 split_birth(size); 1779 fc = curFc; 1780 } else { 1781 // Return entire block to caller 1782 fc = newFc; 1783 } 1784 } 1785 } 1786 } else { 1787 // Get a free chunk from the free chunk dictionary to be returned to 1788 // replenish the indexed free list. 1789 fc = getChunkFromDictionaryExact(size); 1790 } 1791 // assert(fc == NULL || fc->is_free(), "Should be returning a free chunk"); 1792 return fc; 1793 } 1794 1795 FreeChunk* 1796 CompactibleFreeListSpace::getChunkFromDictionary(size_t size) { 1797 assert_locked(); 1798 FreeChunk* fc = _dictionary->get_chunk(size); 1799 if (fc == NULL) { 1800 return NULL; 1801 } 1802 _bt.allocated((HeapWord*)fc, fc->size()); 1803 if (fc->size() >= size + MinChunkSize) { 1804 fc = splitChunkAndReturnRemainder(fc, size); 1805 } 1806 assert(fc->size() >= size, "chunk too small"); 1807 assert(fc->size() < size + MinChunkSize, "chunk too big"); 1808 _bt.verify_single_block((HeapWord*)fc, fc->size()); 1809 return fc; 1810 } 1811 1812 FreeChunk* 1813 CompactibleFreeListSpace::getChunkFromDictionaryExact(size_t size) { 1814 assert_locked(); 1815 FreeChunk* fc = _dictionary->get_chunk(size); 1816 if (fc == NULL) { 1817 return fc; 1818 } 1819 _bt.allocated((HeapWord*)fc, fc->size()); 1820 if (fc->size() == size) { 1821 _bt.verify_single_block((HeapWord*)fc, size); 1822 return fc; 1823 } 1824 assert(fc->size() > size, "get_chunk() guarantee"); 1825 if (fc->size() < size + MinChunkSize) { 1826 // Return the chunk to the dictionary and go get a bigger one. 1827 returnChunkToDictionary(fc); 1828 fc = _dictionary->get_chunk(size + MinChunkSize); 1829 if (fc == NULL) { 1830 return NULL; 1831 } 1832 _bt.allocated((HeapWord*)fc, fc->size()); 1833 } 1834 assert(fc->size() >= size + MinChunkSize, "tautology"); 1835 fc = splitChunkAndReturnRemainder(fc, size); 1836 assert(fc->size() == size, "chunk is wrong size"); 1837 _bt.verify_single_block((HeapWord*)fc, size); 1838 return fc; 1839 } 1840 1841 void 1842 CompactibleFreeListSpace::returnChunkToDictionary(FreeChunk* chunk) { 1843 assert_locked(); 1844 1845 size_t size = chunk->size(); 1846 _bt.verify_single_block((HeapWord*)chunk, size); 1847 // adjust _unallocated_block downward, as necessary 1848 _bt.freed((HeapWord*)chunk, size); 1849 _dictionary->return_chunk(chunk); 1850 #ifndef PRODUCT 1851 if (CMSCollector::abstract_state() != CMSCollector::Sweeping) { 1852 TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >* tc = TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::as_TreeChunk(chunk); 1853 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* tl = tc->list(); 1854 tl->verify_stats(); 1855 } 1856 #endif // PRODUCT 1857 } 1858 1859 void 1860 CompactibleFreeListSpace::returnChunkToFreeList(FreeChunk* fc) { 1861 assert_locked(); 1862 size_t size = fc->size(); 1863 _bt.verify_single_block((HeapWord*) fc, size); 1864 _bt.verify_not_unallocated((HeapWord*) fc, size); 1865 _indexedFreeList[size].return_chunk_at_tail(fc); 1866 #ifndef PRODUCT 1867 if (CMSCollector::abstract_state() != CMSCollector::Sweeping) { 1868 _indexedFreeList[size].verify_stats(); 1869 } 1870 #endif // PRODUCT 1871 } 1872 1873 // Add chunk to end of last block -- if it's the largest 1874 // block -- and update BOT and census data. We would 1875 // of course have preferred to coalesce it with the 1876 // last block, but it's currently less expensive to find the 1877 // largest block than it is to find the last. 1878 void 1879 CompactibleFreeListSpace::addChunkToFreeListsAtEndRecordingStats( 1880 HeapWord* chunk, size_t size) { 1881 // check that the chunk does lie in this space! 1882 assert(chunk != NULL && is_in_reserved(chunk), "Not in this space!"); 1883 // One of the parallel gc task threads may be here 1884 // whilst others are allocating. 1885 Mutex* lock = &_parDictionaryAllocLock; 1886 FreeChunk* ec; 1887 { 1888 MutexLocker x(lock, Mutex::_no_safepoint_check_flag); 1889 ec = dictionary()->find_largest_dict(); // get largest block 1890 if (ec != NULL && ec->end() == (uintptr_t*) chunk) { 1891 // It's a coterminal block - we can coalesce. 1892 size_t old_size = ec->size(); 1893 coalDeath(old_size); 1894 removeChunkFromDictionary(ec); 1895 size += old_size; 1896 } else { 1897 ec = (FreeChunk*)chunk; 1898 } 1899 } 1900 ec->set_size(size); 1901 debug_only(ec->mangleFreed(size)); 1902 if (size < SmallForDictionary) { 1903 lock = _indexedFreeListParLocks[size]; 1904 } 1905 MutexLocker x(lock, Mutex::_no_safepoint_check_flag); 1906 addChunkAndRepairOffsetTable((HeapWord*)ec, size, true); 1907 // record the birth under the lock since the recording involves 1908 // manipulation of the list on which the chunk lives and 1909 // if the chunk is allocated and is the last on the list, 1910 // the list can go away. 1911 coalBirth(size); 1912 } 1913 1914 void 1915 CompactibleFreeListSpace::addChunkToFreeLists(HeapWord* chunk, 1916 size_t size) { 1917 // check that the chunk does lie in this space! 1918 assert(chunk != NULL && is_in_reserved(chunk), "Not in this space!"); 1919 assert_locked(); 1920 _bt.verify_single_block(chunk, size); 1921 1922 FreeChunk* fc = (FreeChunk*) chunk; 1923 fc->set_size(size); 1924 debug_only(fc->mangleFreed(size)); 1925 if (size < SmallForDictionary) { 1926 returnChunkToFreeList(fc); 1927 } else { 1928 returnChunkToDictionary(fc); 1929 } 1930 } 1931 1932 void 1933 CompactibleFreeListSpace::addChunkAndRepairOffsetTable(HeapWord* chunk, 1934 size_t size, bool coalesced) { 1935 assert_locked(); 1936 assert(chunk != NULL, "null chunk"); 1937 if (coalesced) { 1938 // repair BOT 1939 _bt.single_block(chunk, size); 1940 } 1941 addChunkToFreeLists(chunk, size); 1942 } 1943 1944 // We _must_ find the purported chunk on our free lists; 1945 // we assert if we don't. 1946 void 1947 CompactibleFreeListSpace::removeFreeChunkFromFreeLists(FreeChunk* fc) { 1948 size_t size = fc->size(); 1949 assert_locked(); 1950 debug_only(verifyFreeLists()); 1951 if (size < SmallForDictionary) { 1952 removeChunkFromIndexedFreeList(fc); 1953 } else { 1954 removeChunkFromDictionary(fc); 1955 } 1956 _bt.verify_single_block((HeapWord*)fc, size); 1957 debug_only(verifyFreeLists()); 1958 } 1959 1960 void 1961 CompactibleFreeListSpace::removeChunkFromDictionary(FreeChunk* fc) { 1962 size_t size = fc->size(); 1963 assert_locked(); 1964 assert(fc != NULL, "null chunk"); 1965 _bt.verify_single_block((HeapWord*)fc, size); 1966 _dictionary->remove_chunk(fc); 1967 // adjust _unallocated_block upward, as necessary 1968 _bt.allocated((HeapWord*)fc, size); 1969 } 1970 1971 void 1972 CompactibleFreeListSpace::removeChunkFromIndexedFreeList(FreeChunk* fc) { 1973 assert_locked(); 1974 size_t size = fc->size(); 1975 _bt.verify_single_block((HeapWord*)fc, size); 1976 NOT_PRODUCT( 1977 if (FLSVerifyIndexTable) { 1978 verifyIndexedFreeList(size); 1979 } 1980 ) 1981 _indexedFreeList[size].remove_chunk(fc); 1982 NOT_PRODUCT( 1983 if (FLSVerifyIndexTable) { 1984 verifyIndexedFreeList(size); 1985 } 1986 ) 1987 } 1988 1989 FreeChunk* CompactibleFreeListSpace::bestFitSmall(size_t numWords) { 1990 /* A hint is the next larger size that has a surplus. 1991 Start search at a size large enough to guarantee that 1992 the excess is >= MIN_CHUNK. */ 1993 size_t start = align_object_size(numWords + MinChunkSize); 1994 if (start < IndexSetSize) { 1995 AdaptiveFreeList<FreeChunk>* it = _indexedFreeList; 1996 size_t hint = _indexedFreeList[start].hint(); 1997 while (hint < IndexSetSize) { 1998 assert(is_object_aligned(hint), "hint should be aligned"); 1999 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[hint]; 2000 if (fl->surplus() > 0 && fl->head() != NULL) { 2001 // Found a list with surplus, reset original hint 2002 // and split out a free chunk which is returned. 2003 _indexedFreeList[start].set_hint(hint); 2004 FreeChunk* res = getFromListGreater(fl, numWords); 2005 assert(res == NULL || res->is_free(), 2006 "Should be returning a free chunk"); 2007 return res; 2008 } 2009 hint = fl->hint(); /* keep looking */ 2010 } 2011 /* None found. */ 2012 it[start].set_hint(IndexSetSize); 2013 } 2014 return NULL; 2015 } 2016 2017 /* Requires fl->size >= numWords + MinChunkSize */ 2018 FreeChunk* CompactibleFreeListSpace::getFromListGreater(AdaptiveFreeList<FreeChunk>* fl, 2019 size_t numWords) { 2020 FreeChunk *curr = fl->head(); 2021 size_t oldNumWords = curr->size(); 2022 assert(numWords >= MinChunkSize, "Word size is too small"); 2023 assert(curr != NULL, "List is empty"); 2024 assert(oldNumWords >= numWords + MinChunkSize, 2025 "Size of chunks in the list is too small"); 2026 2027 fl->remove_chunk(curr); 2028 // recorded indirectly by splitChunkAndReturnRemainder - 2029 // smallSplit(oldNumWords, numWords); 2030 FreeChunk* new_chunk = splitChunkAndReturnRemainder(curr, numWords); 2031 // Does anything have to be done for the remainder in terms of 2032 // fixing the card table? 2033 assert(new_chunk == NULL || new_chunk->is_free(), 2034 "Should be returning a free chunk"); 2035 return new_chunk; 2036 } 2037 2038 FreeChunk* 2039 CompactibleFreeListSpace::splitChunkAndReturnRemainder(FreeChunk* chunk, 2040 size_t new_size) { 2041 assert_locked(); 2042 size_t size = chunk->size(); 2043 assert(size > new_size, "Split from a smaller block?"); 2044 assert(is_aligned(chunk), "alignment problem"); 2045 assert(size == adjustObjectSize(size), "alignment problem"); 2046 size_t rem_sz = size - new_size; 2047 assert(rem_sz == adjustObjectSize(rem_sz), "alignment problem"); 2048 assert(rem_sz >= MinChunkSize, "Free chunk smaller than minimum"); 2049 FreeChunk* ffc = (FreeChunk*)((HeapWord*)chunk + new_size); 2050 assert(is_aligned(ffc), "alignment problem"); 2051 ffc->set_size(rem_sz); 2052 ffc->link_next(NULL); 2053 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. 2054 // Above must occur before BOT is updated below. 2055 // adjust block offset table 2056 OrderAccess::storestore(); 2057 assert(chunk->is_free() && ffc->is_free(), "Error"); 2058 _bt.split_block((HeapWord*)chunk, chunk->size(), new_size); 2059 if (rem_sz < SmallForDictionary) { 2060 // The freeList lock is held, but multiple GC task threads might be executing in parallel. 2061 bool is_par = Thread::current()->is_GC_task_thread(); 2062 if (is_par) _indexedFreeListParLocks[rem_sz]->lock_without_safepoint_check(); 2063 returnChunkToFreeList(ffc); 2064 split(size, rem_sz); 2065 if (is_par) _indexedFreeListParLocks[rem_sz]->unlock(); 2066 } else { 2067 returnChunkToDictionary(ffc); 2068 split(size, rem_sz); 2069 } 2070 chunk->set_size(new_size); 2071 return chunk; 2072 } 2073 2074 void 2075 CompactibleFreeListSpace::sweep_completed() { 2076 // Now that space is probably plentiful, refill linear 2077 // allocation blocks as needed. 2078 refillLinearAllocBlocksIfNeeded(); 2079 } 2080 2081 void 2082 CompactibleFreeListSpace::gc_prologue() { 2083 assert_locked(); 2084 reportFreeListStatistics("Before GC:"); 2085 refillLinearAllocBlocksIfNeeded(); 2086 } 2087 2088 void 2089 CompactibleFreeListSpace::gc_epilogue() { 2090 assert_locked(); 2091 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency"); 2092 _promoInfo.stopTrackingPromotions(); 2093 repairLinearAllocationBlocks(); 2094 reportFreeListStatistics("After GC:"); 2095 } 2096 2097 // Iteration support, mostly delegated from a CMS generation 2098 2099 void CompactibleFreeListSpace::save_marks() { 2100 assert(Thread::current()->is_VM_thread(), 2101 "Global variable should only be set when single-threaded"); 2102 // Mark the "end" of the used space at the time of this call; 2103 // note, however, that promoted objects from this point 2104 // on are tracked in the _promoInfo below. 2105 set_saved_mark_word(unallocated_block()); 2106 #ifdef ASSERT 2107 // Check the sanity of save_marks() etc. 2108 MemRegion ur = used_region(); 2109 MemRegion urasm = used_region_at_save_marks(); 2110 assert(ur.contains(urasm), 2111 " Error at save_marks(): [" PTR_FORMAT "," PTR_FORMAT ")" 2112 " should contain [" PTR_FORMAT "," PTR_FORMAT ")", 2113 p2i(ur.start()), p2i(ur.end()), p2i(urasm.start()), p2i(urasm.end())); 2114 #endif 2115 // inform allocator that promotions should be tracked. 2116 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency"); 2117 _promoInfo.startTrackingPromotions(); 2118 } 2119 2120 bool CompactibleFreeListSpace::no_allocs_since_save_marks() { 2121 assert(_promoInfo.tracking(), "No preceding save_marks?"); 2122 return _promoInfo.noPromotions(); 2123 } 2124 2125 bool CompactibleFreeListSpace::linearAllocationWouldFail() const { 2126 return _smallLinearAllocBlock._word_size == 0; 2127 } 2128 2129 void CompactibleFreeListSpace::repairLinearAllocationBlocks() { 2130 // Fix up linear allocation blocks to look like free blocks 2131 repairLinearAllocBlock(&_smallLinearAllocBlock); 2132 } 2133 2134 void CompactibleFreeListSpace::repairLinearAllocBlock(LinearAllocBlock* blk) { 2135 assert_locked(); 2136 if (blk->_ptr != NULL) { 2137 assert(blk->_word_size != 0 && blk->_word_size >= MinChunkSize, 2138 "Minimum block size requirement"); 2139 FreeChunk* fc = (FreeChunk*)(blk->_ptr); 2140 fc->set_size(blk->_word_size); 2141 fc->link_prev(NULL); // mark as free 2142 fc->dontCoalesce(); 2143 assert(fc->is_free(), "just marked it free"); 2144 assert(fc->cantCoalesce(), "just marked it uncoalescable"); 2145 } 2146 } 2147 2148 void CompactibleFreeListSpace::refillLinearAllocBlocksIfNeeded() { 2149 assert_locked(); 2150 if (_smallLinearAllocBlock._ptr == NULL) { 2151 assert(_smallLinearAllocBlock._word_size == 0, 2152 "Size of linAB should be zero if the ptr is NULL"); 2153 // Reset the linAB refill and allocation size limit. 2154 _smallLinearAllocBlock.set(0, 0, 1024*SmallForLinearAlloc, SmallForLinearAlloc); 2155 } 2156 refillLinearAllocBlockIfNeeded(&_smallLinearAllocBlock); 2157 } 2158 2159 void 2160 CompactibleFreeListSpace::refillLinearAllocBlockIfNeeded(LinearAllocBlock* blk) { 2161 assert_locked(); 2162 assert((blk->_ptr == NULL && blk->_word_size == 0) || 2163 (blk->_ptr != NULL && blk->_word_size >= MinChunkSize), 2164 "blk invariant"); 2165 if (blk->_ptr == NULL) { 2166 refillLinearAllocBlock(blk); 2167 } 2168 } 2169 2170 void 2171 CompactibleFreeListSpace::refillLinearAllocBlock(LinearAllocBlock* blk) { 2172 assert_locked(); 2173 assert(blk->_word_size == 0 && blk->_ptr == NULL, 2174 "linear allocation block should be empty"); 2175 FreeChunk* fc; 2176 if (blk->_refillSize < SmallForDictionary && 2177 (fc = getChunkFromIndexedFreeList(blk->_refillSize)) != NULL) { 2178 // A linAB's strategy might be to use small sizes to reduce 2179 // fragmentation but still get the benefits of allocation from a 2180 // linAB. 2181 } else { 2182 fc = getChunkFromDictionary(blk->_refillSize); 2183 } 2184 if (fc != NULL) { 2185 blk->_ptr = (HeapWord*)fc; 2186 blk->_word_size = fc->size(); 2187 fc->dontCoalesce(); // to prevent sweeper from sweeping us up 2188 } 2189 } 2190 2191 // Support for compaction 2192 void CompactibleFreeListSpace::prepare_for_compaction(CompactPoint* cp) { 2193 scan_and_forward(this, cp); 2194 // Prepare_for_compaction() uses the space between live objects 2195 // so that later phase can skip dead space quickly. So verification 2196 // of the free lists doesn't work after. 2197 } 2198 2199 void CompactibleFreeListSpace::adjust_pointers() { 2200 // In other versions of adjust_pointers(), a bail out 2201 // based on the amount of live data in the generation 2202 // (i.e., if 0, bail out) may be used. 2203 // Cannot test used() == 0 here because the free lists have already 2204 // been mangled by the compaction. 2205 2206 scan_and_adjust_pointers(this); 2207 // See note about verification in prepare_for_compaction(). 2208 } 2209 2210 void CompactibleFreeListSpace::compact() { 2211 scan_and_compact(this); 2212 } 2213 2214 // Fragmentation metric = 1 - [sum of (fbs**2) / (sum of fbs)**2] 2215 // where fbs is free block sizes 2216 double CompactibleFreeListSpace::flsFrag() const { 2217 size_t itabFree = totalSizeInIndexedFreeLists(); 2218 double frag = 0.0; 2219 size_t i; 2220 2221 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2222 double sz = i; 2223 frag += _indexedFreeList[i].count() * (sz * sz); 2224 } 2225 2226 double totFree = itabFree + 2227 _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())); 2228 if (totFree > 0) { 2229 frag = ((frag + _dictionary->sum_of_squared_block_sizes()) / 2230 (totFree * totFree)); 2231 frag = (double)1.0 - frag; 2232 } else { 2233 assert(frag == 0.0, "Follows from totFree == 0"); 2234 } 2235 return frag; 2236 } 2237 2238 void CompactibleFreeListSpace::beginSweepFLCensus( 2239 float inter_sweep_current, 2240 float inter_sweep_estimate, 2241 float intra_sweep_estimate) { 2242 assert_locked(); 2243 size_t i; 2244 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2245 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i]; 2246 log_trace(gc, freelist)("size[" SIZE_FORMAT "] : ", i); 2247 fl->compute_desired(inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate); 2248 fl->set_coal_desired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent)); 2249 fl->set_before_sweep(fl->count()); 2250 fl->set_bfr_surp(fl->surplus()); 2251 } 2252 _dictionary->begin_sweep_dict_census(CMSLargeCoalSurplusPercent, 2253 inter_sweep_current, 2254 inter_sweep_estimate, 2255 intra_sweep_estimate); 2256 } 2257 2258 void CompactibleFreeListSpace::setFLSurplus() { 2259 assert_locked(); 2260 size_t i; 2261 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2262 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2263 fl->set_surplus(fl->count() - 2264 (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent)); 2265 } 2266 } 2267 2268 void CompactibleFreeListSpace::setFLHints() { 2269 assert_locked(); 2270 size_t i; 2271 size_t h = IndexSetSize; 2272 for (i = IndexSetSize - 1; i != 0; i -= IndexSetStride) { 2273 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2274 fl->set_hint(h); 2275 if (fl->surplus() > 0) { 2276 h = i; 2277 } 2278 } 2279 } 2280 2281 void CompactibleFreeListSpace::clearFLCensus() { 2282 assert_locked(); 2283 size_t i; 2284 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2285 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2286 fl->set_prev_sweep(fl->count()); 2287 fl->set_coal_births(0); 2288 fl->set_coal_deaths(0); 2289 fl->set_split_births(0); 2290 fl->set_split_deaths(0); 2291 } 2292 } 2293 2294 void CompactibleFreeListSpace::endSweepFLCensus(size_t sweep_count) { 2295 log_debug(gc, freelist)("CMS: Large block " PTR_FORMAT, p2i(dictionary()->find_largest_dict())); 2296 setFLSurplus(); 2297 setFLHints(); 2298 printFLCensus(sweep_count); 2299 clearFLCensus(); 2300 assert_locked(); 2301 _dictionary->end_sweep_dict_census(CMSLargeSplitSurplusPercent); 2302 } 2303 2304 bool CompactibleFreeListSpace::coalOverPopulated(size_t size) { 2305 if (size < SmallForDictionary) { 2306 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2307 return (fl->coal_desired() < 0) || 2308 ((int)fl->count() > fl->coal_desired()); 2309 } else { 2310 return dictionary()->coal_dict_over_populated(size); 2311 } 2312 } 2313 2314 void CompactibleFreeListSpace::smallCoalBirth(size_t size) { 2315 assert(size < SmallForDictionary, "Size too large for indexed list"); 2316 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2317 fl->increment_coal_births(); 2318 fl->increment_surplus(); 2319 } 2320 2321 void CompactibleFreeListSpace::smallCoalDeath(size_t size) { 2322 assert(size < SmallForDictionary, "Size too large for indexed list"); 2323 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2324 fl->increment_coal_deaths(); 2325 fl->decrement_surplus(); 2326 } 2327 2328 void CompactibleFreeListSpace::coalBirth(size_t size) { 2329 if (size < SmallForDictionary) { 2330 smallCoalBirth(size); 2331 } else { 2332 dictionary()->dict_census_update(size, 2333 false /* split */, 2334 true /* birth */); 2335 } 2336 } 2337 2338 void CompactibleFreeListSpace::coalDeath(size_t size) { 2339 if(size < SmallForDictionary) { 2340 smallCoalDeath(size); 2341 } else { 2342 dictionary()->dict_census_update(size, 2343 false /* split */, 2344 false /* birth */); 2345 } 2346 } 2347 2348 void CompactibleFreeListSpace::smallSplitBirth(size_t size) { 2349 assert(size < SmallForDictionary, "Size too large for indexed list"); 2350 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2351 fl->increment_split_births(); 2352 fl->increment_surplus(); 2353 } 2354 2355 void CompactibleFreeListSpace::smallSplitDeath(size_t size) { 2356 assert(size < SmallForDictionary, "Size too large for indexed list"); 2357 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2358 fl->increment_split_deaths(); 2359 fl->decrement_surplus(); 2360 } 2361 2362 void CompactibleFreeListSpace::split_birth(size_t size) { 2363 if (size < SmallForDictionary) { 2364 smallSplitBirth(size); 2365 } else { 2366 dictionary()->dict_census_update(size, 2367 true /* split */, 2368 true /* birth */); 2369 } 2370 } 2371 2372 void CompactibleFreeListSpace::splitDeath(size_t size) { 2373 if (size < SmallForDictionary) { 2374 smallSplitDeath(size); 2375 } else { 2376 dictionary()->dict_census_update(size, 2377 true /* split */, 2378 false /* birth */); 2379 } 2380 } 2381 2382 void CompactibleFreeListSpace::split(size_t from, size_t to1) { 2383 size_t to2 = from - to1; 2384 splitDeath(from); 2385 split_birth(to1); 2386 split_birth(to2); 2387 } 2388 2389 void CompactibleFreeListSpace::print() const { 2390 print_on(tty); 2391 } 2392 2393 void CompactibleFreeListSpace::prepare_for_verify() { 2394 assert_locked(); 2395 repairLinearAllocationBlocks(); 2396 // Verify that the SpoolBlocks look like free blocks of 2397 // appropriate sizes... To be done ... 2398 } 2399 2400 class VerifyAllBlksClosure: public BlkClosure { 2401 private: 2402 const CompactibleFreeListSpace* _sp; 2403 const MemRegion _span; 2404 HeapWord* _last_addr; 2405 size_t _last_size; 2406 bool _last_was_obj; 2407 bool _last_was_live; 2408 2409 public: 2410 VerifyAllBlksClosure(const CompactibleFreeListSpace* sp, 2411 MemRegion span) : _sp(sp), _span(span), 2412 _last_addr(NULL), _last_size(0), 2413 _last_was_obj(false), _last_was_live(false) { } 2414 2415 virtual size_t do_blk(HeapWord* addr) { 2416 size_t res; 2417 bool was_obj = false; 2418 bool was_live = false; 2419 if (_sp->block_is_obj(addr)) { 2420 was_obj = true; 2421 oop p = oop(addr); 2422 guarantee(oopDesc::is_oop(p), "Should be an oop"); 2423 res = _sp->adjustObjectSize(p->size()); 2424 if (_sp->obj_is_alive(addr)) { 2425 was_live = true; 2426 oopDesc::verify(p); 2427 } 2428 } else { 2429 FreeChunk* fc = (FreeChunk*)addr; 2430 res = fc->size(); 2431 if (FLSVerifyLists && !fc->cantCoalesce()) { 2432 guarantee(_sp->verify_chunk_in_free_list(fc), 2433 "Chunk should be on a free list"); 2434 } 2435 } 2436 if (res == 0) { 2437 Log(gc, verify) log; 2438 log.error("Livelock: no rank reduction!"); 2439 log.error(" Current: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n" 2440 " Previous: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n", 2441 p2i(addr), res, was_obj ?"true":"false", was_live ?"true":"false", 2442 p2i(_last_addr), _last_size, _last_was_obj?"true":"false", _last_was_live?"true":"false"); 2443 LogStream ls(log.error()); 2444 _sp->print_on(&ls); 2445 guarantee(false, "Verification failed."); 2446 } 2447 _last_addr = addr; 2448 _last_size = res; 2449 _last_was_obj = was_obj; 2450 _last_was_live = was_live; 2451 return res; 2452 } 2453 }; 2454 2455 class VerifyAllOopsClosure: public BasicOopIterateClosure { 2456 private: 2457 const CMSCollector* _collector; 2458 const CompactibleFreeListSpace* _sp; 2459 const MemRegion _span; 2460 const bool _past_remark; 2461 const CMSBitMap* _bit_map; 2462 2463 protected: 2464 void do_oop(void* p, oop obj) { 2465 if (_span.contains(obj)) { // the interior oop points into CMS heap 2466 if (!_span.contains(p)) { // reference from outside CMS heap 2467 // Should be a valid object; the first disjunct below allows 2468 // us to sidestep an assertion in block_is_obj() that insists 2469 // that p be in _sp. Note that several generations (and spaces) 2470 // are spanned by _span (CMS heap) above. 2471 guarantee(!_sp->is_in_reserved(obj) || 2472 _sp->block_is_obj((HeapWord*)obj), 2473 "Should be an object"); 2474 guarantee(oopDesc::is_oop(obj), "Should be an oop"); 2475 oopDesc::verify(obj); 2476 if (_past_remark) { 2477 // Remark has been completed, the object should be marked 2478 _bit_map->isMarked((HeapWord*)obj); 2479 } 2480 } else { // reference within CMS heap 2481 if (_past_remark) { 2482 // Remark has been completed -- so the referent should have 2483 // been marked, if referring object is. 2484 if (_bit_map->isMarked(_collector->block_start(p))) { 2485 guarantee(_bit_map->isMarked((HeapWord*)obj), "Marking error?"); 2486 } 2487 } 2488 } 2489 } else if (_sp->is_in_reserved(p)) { 2490 // the reference is from FLS, and points out of FLS 2491 guarantee(oopDesc::is_oop(obj), "Should be an oop"); 2492 oopDesc::verify(obj); 2493 } 2494 } 2495 2496 template <class T> void do_oop_work(T* p) { 2497 T heap_oop = RawAccess<>::oop_load(p); 2498 if (!CompressedOops::is_null(heap_oop)) { 2499 oop obj = CompressedOops::decode_not_null(heap_oop); 2500 do_oop(p, obj); 2501 } 2502 } 2503 2504 public: 2505 VerifyAllOopsClosure(const CMSCollector* collector, 2506 const CompactibleFreeListSpace* sp, MemRegion span, 2507 bool past_remark, CMSBitMap* bit_map) : 2508 _collector(collector), _sp(sp), _span(span), 2509 _past_remark(past_remark), _bit_map(bit_map) { } 2510 2511 virtual void do_oop(oop* p) { VerifyAllOopsClosure::do_oop_work(p); } 2512 virtual void do_oop(narrowOop* p) { VerifyAllOopsClosure::do_oop_work(p); } 2513 }; 2514 2515 void CompactibleFreeListSpace::verify() const { 2516 assert_lock_strong(&_freelistLock); 2517 verify_objects_initialized(); 2518 MemRegion span = _collector->_span; 2519 bool past_remark = (_collector->abstract_state() == 2520 CMSCollector::Sweeping); 2521 2522 ResourceMark rm; 2523 HandleMark hm; 2524 2525 // Check integrity of CFL data structures 2526 _promoInfo.verify(); 2527 _dictionary->verify(); 2528 if (FLSVerifyIndexTable) { 2529 verifyIndexedFreeLists(); 2530 } 2531 // Check integrity of all objects and free blocks in space 2532 { 2533 VerifyAllBlksClosure cl(this, span); 2534 ((CompactibleFreeListSpace*)this)->blk_iterate(&cl); // cast off const 2535 } 2536 // Check that all references in the heap to FLS 2537 // are to valid objects in FLS or that references in 2538 // FLS are to valid objects elsewhere in the heap 2539 if (FLSVerifyAllHeapReferences) 2540 { 2541 VerifyAllOopsClosure cl(_collector, this, span, past_remark, 2542 _collector->markBitMap()); 2543 2544 // Iterate over all oops in the heap. 2545 CMSHeap::heap()->oop_iterate(&cl); 2546 } 2547 2548 if (VerifyObjectStartArray) { 2549 // Verify the block offset table 2550 _bt.verify(); 2551 } 2552 } 2553 2554 #ifndef PRODUCT 2555 void CompactibleFreeListSpace::verifyFreeLists() const { 2556 if (FLSVerifyLists) { 2557 _dictionary->verify(); 2558 verifyIndexedFreeLists(); 2559 } else { 2560 if (FLSVerifyDictionary) { 2561 _dictionary->verify(); 2562 } 2563 if (FLSVerifyIndexTable) { 2564 verifyIndexedFreeLists(); 2565 } 2566 } 2567 } 2568 #endif 2569 2570 void CompactibleFreeListSpace::verifyIndexedFreeLists() const { 2571 size_t i = 0; 2572 for (; i < IndexSetStart; i++) { 2573 guarantee(_indexedFreeList[i].head() == NULL, "should be NULL"); 2574 } 2575 for (; i < IndexSetSize; i++) { 2576 verifyIndexedFreeList(i); 2577 } 2578 } 2579 2580 void CompactibleFreeListSpace::verifyIndexedFreeList(size_t size) const { 2581 FreeChunk* fc = _indexedFreeList[size].head(); 2582 FreeChunk* tail = _indexedFreeList[size].tail(); 2583 size_t num = _indexedFreeList[size].count(); 2584 size_t n = 0; 2585 guarantee(((size >= IndexSetStart) && (size % IndexSetStride == 0)) || fc == NULL, 2586 "Slot should have been empty"); 2587 for (; fc != NULL; fc = fc->next(), n++) { 2588 guarantee(fc->size() == size, "Size inconsistency"); 2589 guarantee(fc->is_free(), "!free?"); 2590 guarantee(fc->next() == NULL || fc->next()->prev() == fc, "Broken list"); 2591 guarantee((fc->next() == NULL) == (fc == tail), "Incorrect tail"); 2592 } 2593 guarantee(n == num, "Incorrect count"); 2594 } 2595 2596 #ifndef PRODUCT 2597 void CompactibleFreeListSpace::check_free_list_consistency() const { 2598 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size() <= IndexSetSize), 2599 "Some sizes can't be allocated without recourse to" 2600 " linear allocation buffers"); 2601 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size()*HeapWordSize == sizeof(TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >)), 2602 "else MIN_TREE_CHUNK_SIZE is wrong"); 2603 assert(IndexSetStart != 0, "IndexSetStart not initialized"); 2604 assert(IndexSetStride != 0, "IndexSetStride not initialized"); 2605 } 2606 #endif 2607 2608 void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const { 2609 assert_lock_strong(&_freelistLock); 2610 LogTarget(Debug, gc, freelist, census) log; 2611 if (!log.is_enabled()) { 2612 return; 2613 } 2614 AdaptiveFreeList<FreeChunk> total; 2615 log.print("end sweep# " SIZE_FORMAT, sweep_count); 2616 ResourceMark rm; 2617 LogStream ls(log); 2618 outputStream* out = &ls; 2619 AdaptiveFreeList<FreeChunk>::print_labels_on(out, "size"); 2620 size_t total_free = 0; 2621 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2622 const AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2623 total_free += fl->count() * fl->size(); 2624 if (i % (40*IndexSetStride) == 0) { 2625 AdaptiveFreeList<FreeChunk>::print_labels_on(out, "size"); 2626 } 2627 fl->print_on(out); 2628 total.set_bfr_surp( total.bfr_surp() + fl->bfr_surp() ); 2629 total.set_surplus( total.surplus() + fl->surplus() ); 2630 total.set_desired( total.desired() + fl->desired() ); 2631 total.set_prev_sweep( total.prev_sweep() + fl->prev_sweep() ); 2632 total.set_before_sweep(total.before_sweep() + fl->before_sweep()); 2633 total.set_count( total.count() + fl->count() ); 2634 total.set_coal_births( total.coal_births() + fl->coal_births() ); 2635 total.set_coal_deaths( total.coal_deaths() + fl->coal_deaths() ); 2636 total.set_split_births(total.split_births() + fl->split_births()); 2637 total.set_split_deaths(total.split_deaths() + fl->split_deaths()); 2638 } 2639 total.print_on(out, "TOTAL"); 2640 log.print("Total free in indexed lists " SIZE_FORMAT " words", total_free); 2641 log.print("growth: %8.5f deficit: %8.5f", 2642 (double)(total.split_births()+total.coal_births()-total.split_deaths()-total.coal_deaths())/ 2643 (total.prev_sweep() != 0 ? (double)total.prev_sweep() : 1.0), 2644 (double)(total.desired() - total.count())/(total.desired() != 0 ? (double)total.desired() : 1.0)); 2645 _dictionary->print_dict_census(out); 2646 } 2647 2648 /////////////////////////////////////////////////////////////////////////// 2649 // CompactibleFreeListSpaceLAB 2650 /////////////////////////////////////////////////////////////////////////// 2651 2652 #define VECTOR_257(x) \ 2653 /* 1 2 3 4 5 6 7 8 9 1x 11 12 13 14 15 16 17 18 19 2x 21 22 23 24 25 26 27 28 29 3x 31 32 */ \ 2654 { x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2655 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2656 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2657 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2658 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2659 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2660 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2661 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \ 2662 x } 2663 2664 // Initialize with default setting for CMS, _not_ 2665 // generic OldPLABSize, whose static default is different; if overridden at the 2666 // command-line, this will get reinitialized via a call to 2667 // modify_initialization() below. 2668 AdaptiveWeightedAverage CompactibleFreeListSpaceLAB::_blocks_to_claim[] = 2669 VECTOR_257(AdaptiveWeightedAverage(OldPLABWeight, (float)CompactibleFreeListSpaceLAB::_default_dynamic_old_plab_size)); 2670 size_t CompactibleFreeListSpaceLAB::_global_num_blocks[] = VECTOR_257(0); 2671 uint CompactibleFreeListSpaceLAB::_global_num_workers[] = VECTOR_257(0); 2672 2673 CompactibleFreeListSpaceLAB::CompactibleFreeListSpaceLAB(CompactibleFreeListSpace* cfls) : 2674 _cfls(cfls) 2675 { 2676 assert(CompactibleFreeListSpace::IndexSetSize == 257, "Modify VECTOR_257() macro above"); 2677 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2678 i < CompactibleFreeListSpace::IndexSetSize; 2679 i += CompactibleFreeListSpace::IndexSetStride) { 2680 _indexedFreeList[i].set_size(i); 2681 _num_blocks[i] = 0; 2682 } 2683 } 2684 2685 static bool _CFLS_LAB_modified = false; 2686 2687 void CompactibleFreeListSpaceLAB::modify_initialization(size_t n, unsigned wt) { 2688 assert(!_CFLS_LAB_modified, "Call only once"); 2689 _CFLS_LAB_modified = true; 2690 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2691 i < CompactibleFreeListSpace::IndexSetSize; 2692 i += CompactibleFreeListSpace::IndexSetStride) { 2693 _blocks_to_claim[i].modify(n, wt, true /* force */); 2694 } 2695 } 2696 2697 HeapWord* CompactibleFreeListSpaceLAB::alloc(size_t word_sz) { 2698 FreeChunk* res; 2699 assert(word_sz == _cfls->adjustObjectSize(word_sz), "Error"); 2700 if (word_sz >= CompactibleFreeListSpace::IndexSetSize) { 2701 // This locking manages sync with other large object allocations. 2702 MutexLocker x(_cfls->parDictionaryAllocLock(), 2703 Mutex::_no_safepoint_check_flag); 2704 res = _cfls->getChunkFromDictionaryExact(word_sz); 2705 if (res == NULL) return NULL; 2706 } else { 2707 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[word_sz]; 2708 if (fl->count() == 0) { 2709 // Attempt to refill this local free list. 2710 get_from_global_pool(word_sz, fl); 2711 // If it didn't work, give up. 2712 if (fl->count() == 0) return NULL; 2713 } 2714 res = fl->get_chunk_at_head(); 2715 assert(res != NULL, "Why was count non-zero?"); 2716 } 2717 res->markNotFree(); 2718 assert(!res->is_free(), "shouldn't be marked free"); 2719 assert(oop(res)->klass_or_null() == NULL, "should look uninitialized"); 2720 // mangle a just allocated object with a distinct pattern. 2721 debug_only(res->mangleAllocated(word_sz)); 2722 return (HeapWord*)res; 2723 } 2724 2725 // Get a chunk of blocks of the right size and update related 2726 // book-keeping stats 2727 void CompactibleFreeListSpaceLAB::get_from_global_pool(size_t word_sz, AdaptiveFreeList<FreeChunk>* fl) { 2728 // Get the #blocks we want to claim 2729 size_t n_blks = (size_t)_blocks_to_claim[word_sz].average(); 2730 assert(n_blks > 0, "Error"); 2731 assert(ResizeOldPLAB || n_blks == OldPLABSize, "Error"); 2732 // In some cases, when the application has a phase change, 2733 // there may be a sudden and sharp shift in the object survival 2734 // profile, and updating the counts at the end of a scavenge 2735 // may not be quick enough, giving rise to large scavenge pauses 2736 // during these phase changes. It is beneficial to detect such 2737 // changes on-the-fly during a scavenge and avoid such a phase-change 2738 // pothole. The following code is a heuristic attempt to do that. 2739 // It is protected by a product flag until we have gained 2740 // enough experience with this heuristic and fine-tuned its behavior. 2741 // WARNING: This might increase fragmentation if we overreact to 2742 // small spikes, so some kind of historical smoothing based on 2743 // previous experience with the greater reactivity might be useful. 2744 // Lacking sufficient experience, CMSOldPLABResizeQuicker is disabled by 2745 // default. 2746 if (ResizeOldPLAB && CMSOldPLABResizeQuicker) { 2747 // 2748 // On a 32-bit VM, the denominator can become zero because of integer overflow, 2749 // which is why there is a cast to double. 2750 // 2751 size_t multiple = (size_t) (_num_blocks[word_sz]/(((double)CMSOldPLABToleranceFactor)*CMSOldPLABNumRefills*n_blks)); 2752 n_blks += CMSOldPLABReactivityFactor*multiple*n_blks; 2753 n_blks = MIN2(n_blks, CMSOldPLABMax); 2754 } 2755 assert(n_blks > 0, "Error"); 2756 _cfls->par_get_chunk_of_blocks(word_sz, n_blks, fl); 2757 // Update stats table entry for this block size 2758 _num_blocks[word_sz] += fl->count(); 2759 } 2760 2761 void CompactibleFreeListSpaceLAB::compute_desired_plab_size() { 2762 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2763 i < CompactibleFreeListSpace::IndexSetSize; 2764 i += CompactibleFreeListSpace::IndexSetStride) { 2765 assert((_global_num_workers[i] == 0) == (_global_num_blocks[i] == 0), 2766 "Counter inconsistency"); 2767 if (_global_num_workers[i] > 0) { 2768 // Need to smooth wrt historical average 2769 if (ResizeOldPLAB) { 2770 _blocks_to_claim[i].sample( 2771 MAX2(CMSOldPLABMin, 2772 MIN2(CMSOldPLABMax, 2773 _global_num_blocks[i]/_global_num_workers[i]/CMSOldPLABNumRefills))); 2774 } 2775 // Reset counters for next round 2776 _global_num_workers[i] = 0; 2777 _global_num_blocks[i] = 0; 2778 log_trace(gc, plab)("[" SIZE_FORMAT "]: " SIZE_FORMAT, i, (size_t)_blocks_to_claim[i].average()); 2779 } 2780 } 2781 } 2782 2783 // If this is changed in the future to allow parallel 2784 // access, one would need to take the FL locks and, 2785 // depending on how it is used, stagger access from 2786 // parallel threads to reduce contention. 2787 void CompactibleFreeListSpaceLAB::retire(int tid) { 2788 // We run this single threaded with the world stopped; 2789 // so no need for locks and such. 2790 NOT_PRODUCT(Thread* t = Thread::current();) 2791 assert(Thread::current()->is_VM_thread(), "Error"); 2792 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2793 i < CompactibleFreeListSpace::IndexSetSize; 2794 i += CompactibleFreeListSpace::IndexSetStride) { 2795 assert(_num_blocks[i] >= (size_t)_indexedFreeList[i].count(), 2796 "Can't retire more than what we obtained"); 2797 if (_num_blocks[i] > 0) { 2798 size_t num_retire = _indexedFreeList[i].count(); 2799 assert(_num_blocks[i] > num_retire, "Should have used at least one"); 2800 { 2801 // MutexLocker x(_cfls->_indexedFreeListParLocks[i], 2802 // Mutex::_no_safepoint_check_flag); 2803 2804 // Update globals stats for num_blocks used 2805 _global_num_blocks[i] += (_num_blocks[i] - num_retire); 2806 _global_num_workers[i]++; 2807 assert(_global_num_workers[i] <= ParallelGCThreads, "Too big"); 2808 if (num_retire > 0) { 2809 _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]); 2810 // Reset this list. 2811 _indexedFreeList[i] = AdaptiveFreeList<FreeChunk>(); 2812 _indexedFreeList[i].set_size(i); 2813 } 2814 } 2815 log_trace(gc, plab)("%d[" SIZE_FORMAT "]: " SIZE_FORMAT "/" SIZE_FORMAT "/" SIZE_FORMAT, 2816 tid, i, num_retire, _num_blocks[i], (size_t)_blocks_to_claim[i].average()); 2817 // Reset stats for next round 2818 _num_blocks[i] = 0; 2819 } 2820 } 2821 } 2822 2823 // Used by par_get_chunk_of_blocks() for the chunks from the 2824 // indexed_free_lists. Looks for a chunk with size that is a multiple 2825 // of "word_sz" and if found, splits it into "word_sz" chunks and add 2826 // to the free list "fl". "n" is the maximum number of chunks to 2827 // be added to "fl". 2828 bool CompactibleFreeListSpace:: par_get_chunk_of_blocks_IFL(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) { 2829 2830 // We'll try all multiples of word_sz in the indexed set, starting with 2831 // word_sz itself and, if CMSSplitIndexedFreeListBlocks, try larger multiples, 2832 // then try getting a big chunk and splitting it. 2833 { 2834 bool found; 2835 int k; 2836 size_t cur_sz; 2837 for (k = 1, cur_sz = k * word_sz, found = false; 2838 (cur_sz < CompactibleFreeListSpace::IndexSetSize) && 2839 (CMSSplitIndexedFreeListBlocks || k <= 1); 2840 k++, cur_sz = k * word_sz) { 2841 AdaptiveFreeList<FreeChunk> fl_for_cur_sz; // Empty. 2842 fl_for_cur_sz.set_size(cur_sz); 2843 { 2844 MutexLocker x(_indexedFreeListParLocks[cur_sz], 2845 Mutex::_no_safepoint_check_flag); 2846 AdaptiveFreeList<FreeChunk>* gfl = &_indexedFreeList[cur_sz]; 2847 if (gfl->count() != 0) { 2848 // nn is the number of chunks of size cur_sz that 2849 // we'd need to split k-ways each, in order to create 2850 // "n" chunks of size word_sz each. 2851 const size_t nn = MAX2(n/k, (size_t)1); 2852 gfl->getFirstNChunksFromList(nn, &fl_for_cur_sz); 2853 found = true; 2854 if (k > 1) { 2855 // Update split death stats for the cur_sz-size blocks list: 2856 // we increment the split death count by the number of blocks 2857 // we just took from the cur_sz-size blocks list and which 2858 // we will be splitting below. 2859 ssize_t deaths = gfl->split_deaths() + 2860 fl_for_cur_sz.count(); 2861 gfl->set_split_deaths(deaths); 2862 } 2863 } 2864 } 2865 // Now transfer fl_for_cur_sz to fl. Common case, we hope, is k = 1. 2866 if (found) { 2867 if (k == 1) { 2868 fl->prepend(&fl_for_cur_sz); 2869 } else { 2870 // Divide each block on fl_for_cur_sz up k ways. 2871 FreeChunk* fc; 2872 while ((fc = fl_for_cur_sz.get_chunk_at_head()) != NULL) { 2873 // Must do this in reverse order, so that anybody attempting to 2874 // access the main chunk sees it as a single free block until we 2875 // change it. 2876 size_t fc_size = fc->size(); 2877 assert(fc->is_free(), "Error"); 2878 for (int i = k-1; i >= 0; i--) { 2879 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz); 2880 assert((i != 0) || 2881 ((fc == ffc) && ffc->is_free() && 2882 (ffc->size() == k*word_sz) && (fc_size == word_sz)), 2883 "Counting error"); 2884 ffc->set_size(word_sz); 2885 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. 2886 ffc->link_next(NULL); 2887 // Above must occur before BOT is updated below. 2888 OrderAccess::storestore(); 2889 // splitting from the right, fc_size == i * word_sz 2890 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */); 2891 fc_size -= word_sz; 2892 assert(fc_size == i*word_sz, "Error"); 2893 _bt.verify_not_unallocated((HeapWord*)ffc, word_sz); 2894 _bt.verify_single_block((HeapWord*)fc, fc_size); 2895 _bt.verify_single_block((HeapWord*)ffc, word_sz); 2896 // Push this on "fl". 2897 fl->return_chunk_at_head(ffc); 2898 } 2899 // TRAP 2900 assert(fl->tail()->next() == NULL, "List invariant."); 2901 } 2902 } 2903 // Update birth stats for this block size. 2904 size_t num = fl->count(); 2905 MutexLocker x(_indexedFreeListParLocks[word_sz], 2906 Mutex::_no_safepoint_check_flag); 2907 ssize_t births = _indexedFreeList[word_sz].split_births() + num; 2908 _indexedFreeList[word_sz].set_split_births(births); 2909 return true; 2910 } 2911 } 2912 return found; 2913 } 2914 } 2915 2916 FreeChunk* CompactibleFreeListSpace::get_n_way_chunk_to_split(size_t word_sz, size_t n) { 2917 2918 FreeChunk* fc = NULL; 2919 FreeChunk* rem_fc = NULL; 2920 size_t rem; 2921 { 2922 MutexLocker x(parDictionaryAllocLock(), 2923 Mutex::_no_safepoint_check_flag); 2924 while (n > 0) { 2925 fc = dictionary()->get_chunk(MAX2(n * word_sz, _dictionary->min_size())); 2926 if (fc != NULL) { 2927 break; 2928 } else { 2929 n--; 2930 } 2931 } 2932 if (fc == NULL) return NULL; 2933 // Otherwise, split up that block. 2934 assert((ssize_t)n >= 1, "Control point invariant"); 2935 assert(fc->is_free(), "Error: should be a free block"); 2936 _bt.verify_single_block((HeapWord*)fc, fc->size()); 2937 const size_t nn = fc->size() / word_sz; 2938 n = MIN2(nn, n); 2939 assert((ssize_t)n >= 1, "Control point invariant"); 2940 rem = fc->size() - n * word_sz; 2941 // If there is a remainder, and it's too small, allocate one fewer. 2942 if (rem > 0 && rem < MinChunkSize) { 2943 n--; rem += word_sz; 2944 } 2945 // Note that at this point we may have n == 0. 2946 assert((ssize_t)n >= 0, "Control point invariant"); 2947 2948 // If n is 0, the chunk fc that was found is not large 2949 // enough to leave a viable remainder. We are unable to 2950 // allocate even one block. Return fc to the 2951 // dictionary and return, leaving "fl" empty. 2952 if (n == 0) { 2953 returnChunkToDictionary(fc); 2954 return NULL; 2955 } 2956 2957 _bt.allocated((HeapWord*)fc, fc->size(), true /* reducing */); // update _unallocated_blk 2958 dictionary()->dict_census_update(fc->size(), 2959 true /*split*/, 2960 false /*birth*/); 2961 2962 // First return the remainder, if any. 2963 // Note that we hold the lock until we decide if we're going to give 2964 // back the remainder to the dictionary, since a concurrent allocation 2965 // may otherwise see the heap as empty. (We're willing to take that 2966 // hit if the block is a small block.) 2967 if (rem > 0) { 2968 size_t prefix_size = n * word_sz; 2969 rem_fc = (FreeChunk*)((HeapWord*)fc + prefix_size); 2970 rem_fc->set_size(rem); 2971 rem_fc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. 2972 rem_fc->link_next(NULL); 2973 // Above must occur before BOT is updated below. 2974 assert((ssize_t)n > 0 && prefix_size > 0 && rem_fc > fc, "Error"); 2975 OrderAccess::storestore(); 2976 _bt.split_block((HeapWord*)fc, fc->size(), prefix_size); 2977 assert(fc->is_free(), "Error"); 2978 fc->set_size(prefix_size); 2979 if (rem >= IndexSetSize) { 2980 returnChunkToDictionary(rem_fc); 2981 dictionary()->dict_census_update(rem, true /*split*/, true /*birth*/); 2982 rem_fc = NULL; 2983 } 2984 // Otherwise, return it to the small list below. 2985 } 2986 } 2987 if (rem_fc != NULL) { 2988 MutexLocker x(_indexedFreeListParLocks[rem], 2989 Mutex::_no_safepoint_check_flag); 2990 _bt.verify_not_unallocated((HeapWord*)rem_fc, rem_fc->size()); 2991 _indexedFreeList[rem].return_chunk_at_head(rem_fc); 2992 smallSplitBirth(rem); 2993 } 2994 assert(n * word_sz == fc->size(), 2995 "Chunk size " SIZE_FORMAT " is not exactly splittable by " 2996 SIZE_FORMAT " sized chunks of size " SIZE_FORMAT, 2997 fc->size(), n, word_sz); 2998 return fc; 2999 } 3000 3001 void CompactibleFreeListSpace:: par_get_chunk_of_blocks_dictionary(size_t word_sz, size_t targetted_number_of_chunks, AdaptiveFreeList<FreeChunk>* fl) { 3002 3003 FreeChunk* fc = get_n_way_chunk_to_split(word_sz, targetted_number_of_chunks); 3004 3005 if (fc == NULL) { 3006 return; 3007 } 3008 3009 size_t n = fc->size() / word_sz; 3010 3011 assert((ssize_t)n > 0, "Consistency"); 3012 // Now do the splitting up. 3013 // Must do this in reverse order, so that anybody attempting to 3014 // access the main chunk sees it as a single free block until we 3015 // change it. 3016 size_t fc_size = n * word_sz; 3017 // All but first chunk in this loop 3018 for (ssize_t i = n-1; i > 0; i--) { 3019 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz); 3020 ffc->set_size(word_sz); 3021 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. 3022 ffc->link_next(NULL); 3023 // Above must occur before BOT is updated below. 3024 OrderAccess::storestore(); 3025 // splitting from the right, fc_size == (n - i + 1) * wordsize 3026 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */); 3027 fc_size -= word_sz; 3028 _bt.verify_not_unallocated((HeapWord*)ffc, ffc->size()); 3029 _bt.verify_single_block((HeapWord*)ffc, ffc->size()); 3030 _bt.verify_single_block((HeapWord*)fc, fc_size); 3031 // Push this on "fl". 3032 fl->return_chunk_at_head(ffc); 3033 } 3034 // First chunk 3035 assert(fc->is_free() && fc->size() == n*word_sz, "Error: should still be a free block"); 3036 // The blocks above should show their new sizes before the first block below 3037 fc->set_size(word_sz); 3038 fc->link_prev(NULL); // idempotent wrt free-ness, see assert above 3039 fc->link_next(NULL); 3040 _bt.verify_not_unallocated((HeapWord*)fc, fc->size()); 3041 _bt.verify_single_block((HeapWord*)fc, fc->size()); 3042 fl->return_chunk_at_head(fc); 3043 3044 assert((ssize_t)n > 0 && (ssize_t)n == fl->count(), "Incorrect number of blocks"); 3045 { 3046 // Update the stats for this block size. 3047 MutexLocker x(_indexedFreeListParLocks[word_sz], 3048 Mutex::_no_safepoint_check_flag); 3049 const ssize_t births = _indexedFreeList[word_sz].split_births() + n; 3050 _indexedFreeList[word_sz].set_split_births(births); 3051 // ssize_t new_surplus = _indexedFreeList[word_sz].surplus() + n; 3052 // _indexedFreeList[word_sz].set_surplus(new_surplus); 3053 } 3054 3055 // TRAP 3056 assert(fl->tail()->next() == NULL, "List invariant."); 3057 } 3058 3059 void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) { 3060 assert(fl->count() == 0, "Precondition."); 3061 assert(word_sz < CompactibleFreeListSpace::IndexSetSize, 3062 "Precondition"); 3063 3064 if (par_get_chunk_of_blocks_IFL(word_sz, n, fl)) { 3065 // Got it 3066 return; 3067 } 3068 3069 // Otherwise, we'll split a block from the dictionary. 3070 par_get_chunk_of_blocks_dictionary(word_sz, n, fl); 3071 } 3072 3073 const size_t CompactibleFreeListSpace::max_flag_size_for_task_size() const { 3074 const size_t ergo_max = _old_gen->reserved().word_size() / (CardTable::card_size_in_words * BitsPerWord); 3075 return ergo_max; 3076 } 3077 3078 // Set up the space's par_seq_tasks structure for work claiming 3079 // for parallel rescan. See CMSParRemarkTask where this is currently used. 3080 // XXX Need to suitably abstract and generalize this and the next 3081 // method into one. 3082 void 3083 CompactibleFreeListSpace:: 3084 initialize_sequential_subtasks_for_rescan(int n_threads) { 3085 // The "size" of each task is fixed according to rescan_task_size. 3086 assert(n_threads > 0, "Unexpected n_threads argument"); 3087 const size_t task_size = rescan_task_size(); 3088 size_t n_tasks = (used_region().word_size() + task_size - 1)/task_size; 3089 assert((n_tasks == 0) == used_region().is_empty(), "n_tasks incorrect"); 3090 assert(n_tasks == 0 || 3091 ((used_region().start() + (n_tasks - 1)*task_size < used_region().end()) && 3092 (used_region().start() + n_tasks*task_size >= used_region().end())), 3093 "n_tasks calculation incorrect"); 3094 SequentialSubTasksDone* pst = conc_par_seq_tasks(); 3095 assert(!pst->valid(), "Clobbering existing data?"); 3096 // Sets the condition for completion of the subtask (how many threads 3097 // need to finish in order to be done). 3098 pst->set_n_threads(n_threads); 3099 pst->set_n_tasks((int)n_tasks); 3100 } 3101 3102 // Set up the space's par_seq_tasks structure for work claiming 3103 // for parallel concurrent marking. See CMSConcMarkTask where this is currently used. 3104 void 3105 CompactibleFreeListSpace:: 3106 initialize_sequential_subtasks_for_marking(int n_threads, 3107 HeapWord* low) { 3108 // The "size" of each task is fixed according to rescan_task_size. 3109 assert(n_threads > 0, "Unexpected n_threads argument"); 3110 const size_t task_size = marking_task_size(); 3111 assert(task_size > CardTable::card_size_in_words && 3112 (task_size % CardTable::card_size_in_words == 0), 3113 "Otherwise arithmetic below would be incorrect"); 3114 MemRegion span = _old_gen->reserved(); 3115 if (low != NULL) { 3116 if (span.contains(low)) { 3117 // Align low down to a card boundary so that 3118 // we can use block_offset_careful() on span boundaries. 3119 HeapWord* aligned_low = align_down(low, CardTable::card_size); 3120 // Clip span prefix at aligned_low 3121 span = span.intersection(MemRegion(aligned_low, span.end())); 3122 } else if (low > span.end()) { 3123 span = MemRegion(low, low); // Null region 3124 } // else use entire span 3125 } 3126 assert(span.is_empty() || 3127 ((uintptr_t)span.start() % CardTable::card_size == 0), 3128 "span should start at a card boundary"); 3129 size_t n_tasks = (span.word_size() + task_size - 1)/task_size; 3130 assert((n_tasks == 0) == span.is_empty(), "Inconsistency"); 3131 assert(n_tasks == 0 || 3132 ((span.start() + (n_tasks - 1)*task_size < span.end()) && 3133 (span.start() + n_tasks*task_size >= span.end())), 3134 "n_tasks calculation incorrect"); 3135 SequentialSubTasksDone* pst = conc_par_seq_tasks(); 3136 assert(!pst->valid(), "Clobbering existing data?"); 3137 // Sets the condition for completion of the subtask (how many threads 3138 // need to finish in order to be done). 3139 pst->set_n_threads(n_threads); 3140 pst->set_n_tasks((int)n_tasks); 3141 }