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