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 scan_and_forward(this, cp); 2177 // Prepare_for_compaction() uses the space between live objects 2178 // so that later phase can skip dead space quickly. So verification 2179 // of the free lists doesn't work after. 2180 } 2181 2182 void CompactibleFreeListSpace::adjust_pointers() { 2183 // In other versions of adjust_pointers(), a bail out 2184 // based on the amount of live data in the generation 2185 // (i.e., if 0, bail out) may be used. 2186 // Cannot test used() == 0 here because the free lists have already 2187 // been mangled by the compaction. 2188 2189 scan_and_adjust_pointers(this); 2190 // See note about verification in prepare_for_compaction(). 2191 } 2192 2193 void CompactibleFreeListSpace::compact() { 2194 scan_and_compact(this); 2195 } 2196 2197 // Fragmentation metric = 1 - [sum of (fbs**2) / (sum of fbs)**2] 2198 // where fbs is free block sizes 2199 double CompactibleFreeListSpace::flsFrag() const { 2200 size_t itabFree = totalSizeInIndexedFreeLists(); 2201 double frag = 0.0; 2202 size_t i; 2203 2204 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2205 double sz = i; 2206 frag += _indexedFreeList[i].count() * (sz * sz); 2207 } 2208 2209 double totFree = itabFree + 2210 _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())); 2211 if (totFree > 0) { 2212 frag = ((frag + _dictionary->sum_of_squared_block_sizes()) / 2213 (totFree * totFree)); 2214 frag = (double)1.0 - frag; 2215 } else { 2216 assert(frag == 0.0, "Follows from totFree == 0"); 2217 } 2218 return frag; 2219 } 2220 2221 void CompactibleFreeListSpace::beginSweepFLCensus( 2222 float inter_sweep_current, 2223 float inter_sweep_estimate, 2224 float intra_sweep_estimate) { 2225 assert_locked(); 2226 size_t i; 2227 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2228 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i]; 2229 log_trace(gc, freelist)("size[" SIZE_FORMAT "] : ", i); 2230 fl->compute_desired(inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate); 2231 fl->set_coal_desired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent)); 2232 fl->set_before_sweep(fl->count()); 2233 fl->set_bfr_surp(fl->surplus()); 2234 } 2235 _dictionary->begin_sweep_dict_census(CMSLargeCoalSurplusPercent, 2236 inter_sweep_current, 2237 inter_sweep_estimate, 2238 intra_sweep_estimate); 2239 } 2240 2241 void CompactibleFreeListSpace::setFLSurplus() { 2242 assert_locked(); 2243 size_t i; 2244 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2245 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2246 fl->set_surplus(fl->count() - 2247 (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent)); 2248 } 2249 } 2250 2251 void CompactibleFreeListSpace::setFLHints() { 2252 assert_locked(); 2253 size_t i; 2254 size_t h = IndexSetSize; 2255 for (i = IndexSetSize - 1; i != 0; i -= IndexSetStride) { 2256 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2257 fl->set_hint(h); 2258 if (fl->surplus() > 0) { 2259 h = i; 2260 } 2261 } 2262 } 2263 2264 void CompactibleFreeListSpace::clearFLCensus() { 2265 assert_locked(); 2266 size_t i; 2267 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2268 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2269 fl->set_prev_sweep(fl->count()); 2270 fl->set_coal_births(0); 2271 fl->set_coal_deaths(0); 2272 fl->set_split_births(0); 2273 fl->set_split_deaths(0); 2274 } 2275 } 2276 2277 void CompactibleFreeListSpace::endSweepFLCensus(size_t sweep_count) { 2278 log_debug(gc, freelist)("CMS: Large block " PTR_FORMAT, p2i(dictionary()->find_largest_dict())); 2279 setFLSurplus(); 2280 setFLHints(); 2281 printFLCensus(sweep_count); 2282 clearFLCensus(); 2283 assert_locked(); 2284 _dictionary->end_sweep_dict_census(CMSLargeSplitSurplusPercent); 2285 } 2286 2287 bool CompactibleFreeListSpace::coalOverPopulated(size_t size) { 2288 if (size < SmallForDictionary) { 2289 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2290 return (fl->coal_desired() < 0) || 2291 ((int)fl->count() > fl->coal_desired()); 2292 } else { 2293 return dictionary()->coal_dict_over_populated(size); 2294 } 2295 } 2296 2297 void CompactibleFreeListSpace::smallCoalBirth(size_t size) { 2298 assert(size < SmallForDictionary, "Size too large for indexed list"); 2299 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2300 fl->increment_coal_births(); 2301 fl->increment_surplus(); 2302 } 2303 2304 void CompactibleFreeListSpace::smallCoalDeath(size_t size) { 2305 assert(size < SmallForDictionary, "Size too large for indexed list"); 2306 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2307 fl->increment_coal_deaths(); 2308 fl->decrement_surplus(); 2309 } 2310 2311 void CompactibleFreeListSpace::coalBirth(size_t size) { 2312 if (size < SmallForDictionary) { 2313 smallCoalBirth(size); 2314 } else { 2315 dictionary()->dict_census_update(size, 2316 false /* split */, 2317 true /* birth */); 2318 } 2319 } 2320 2321 void CompactibleFreeListSpace::coalDeath(size_t size) { 2322 if(size < SmallForDictionary) { 2323 smallCoalDeath(size); 2324 } else { 2325 dictionary()->dict_census_update(size, 2326 false /* split */, 2327 false /* birth */); 2328 } 2329 } 2330 2331 void CompactibleFreeListSpace::smallSplitBirth(size_t size) { 2332 assert(size < SmallForDictionary, "Size too large for indexed list"); 2333 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2334 fl->increment_split_births(); 2335 fl->increment_surplus(); 2336 } 2337 2338 void CompactibleFreeListSpace::smallSplitDeath(size_t size) { 2339 assert(size < SmallForDictionary, "Size too large for indexed list"); 2340 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size]; 2341 fl->increment_split_deaths(); 2342 fl->decrement_surplus(); 2343 } 2344 2345 void CompactibleFreeListSpace::split_birth(size_t size) { 2346 if (size < SmallForDictionary) { 2347 smallSplitBirth(size); 2348 } else { 2349 dictionary()->dict_census_update(size, 2350 true /* split */, 2351 true /* birth */); 2352 } 2353 } 2354 2355 void CompactibleFreeListSpace::splitDeath(size_t size) { 2356 if (size < SmallForDictionary) { 2357 smallSplitDeath(size); 2358 } else { 2359 dictionary()->dict_census_update(size, 2360 true /* split */, 2361 false /* birth */); 2362 } 2363 } 2364 2365 void CompactibleFreeListSpace::split(size_t from, size_t to1) { 2366 size_t to2 = from - to1; 2367 splitDeath(from); 2368 split_birth(to1); 2369 split_birth(to2); 2370 } 2371 2372 void CompactibleFreeListSpace::print() const { 2373 print_on(tty); 2374 } 2375 2376 void CompactibleFreeListSpace::prepare_for_verify() { 2377 assert_locked(); 2378 repairLinearAllocationBlocks(); 2379 // Verify that the SpoolBlocks look like free blocks of 2380 // appropriate sizes... To be done ... 2381 } 2382 2383 class VerifyAllBlksClosure: public BlkClosure { 2384 private: 2385 const CompactibleFreeListSpace* _sp; 2386 const MemRegion _span; 2387 HeapWord* _last_addr; 2388 size_t _last_size; 2389 bool _last_was_obj; 2390 bool _last_was_live; 2391 2392 public: 2393 VerifyAllBlksClosure(const CompactibleFreeListSpace* sp, 2394 MemRegion span) : _sp(sp), _span(span), 2395 _last_addr(NULL), _last_size(0), 2396 _last_was_obj(false), _last_was_live(false) { } 2397 2398 virtual size_t do_blk(HeapWord* addr) { 2399 size_t res; 2400 bool was_obj = false; 2401 bool was_live = false; 2402 if (_sp->block_is_obj(addr)) { 2403 was_obj = true; 2404 oop p = oop(addr); 2405 guarantee(oopDesc::is_oop(p), "Should be an oop"); 2406 res = _sp->adjustObjectSize(p->size()); 2407 if (_sp->obj_is_alive(addr)) { 2408 was_live = true; 2409 p->verify(); 2410 } 2411 } else { 2412 FreeChunk* fc = (FreeChunk*)addr; 2413 res = fc->size(); 2414 if (FLSVerifyLists && !fc->cantCoalesce()) { 2415 guarantee(_sp->verify_chunk_in_free_list(fc), 2416 "Chunk should be on a free list"); 2417 } 2418 } 2419 if (res == 0) { 2420 Log(gc, verify) log; 2421 log.error("Livelock: no rank reduction!"); 2422 log.error(" Current: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n" 2423 " Previous: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n", 2424 p2i(addr), res, was_obj ?"true":"false", was_live ?"true":"false", 2425 p2i(_last_addr), _last_size, _last_was_obj?"true":"false", _last_was_live?"true":"false"); 2426 LogStream ls(log.error()); 2427 _sp->print_on(&ls); 2428 guarantee(false, "Verification failed."); 2429 } 2430 _last_addr = addr; 2431 _last_size = res; 2432 _last_was_obj = was_obj; 2433 _last_was_live = was_live; 2434 return res; 2435 } 2436 }; 2437 2438 class VerifyAllOopsClosure: public BasicOopIterateClosure { 2439 private: 2440 const CMSCollector* _collector; 2441 const CompactibleFreeListSpace* _sp; 2442 const MemRegion _span; 2443 const bool _past_remark; 2444 const CMSBitMap* _bit_map; 2445 2446 protected: 2447 void do_oop(void* p, oop obj) { 2448 if (_span.contains(obj)) { // the interior oop points into CMS heap 2449 if (!_span.contains(p)) { // reference from outside CMS heap 2450 // Should be a valid object; the first disjunct below allows 2451 // us to sidestep an assertion in block_is_obj() that insists 2452 // that p be in _sp. Note that several generations (and spaces) 2453 // are spanned by _span (CMS heap) above. 2454 guarantee(!_sp->is_in_reserved(obj) || 2455 _sp->block_is_obj((HeapWord*)obj), 2456 "Should be an object"); 2457 guarantee(oopDesc::is_oop(obj), "Should be an oop"); 2458 obj->verify(); 2459 if (_past_remark) { 2460 // Remark has been completed, the object should be marked 2461 _bit_map->isMarked((HeapWord*)obj); 2462 } 2463 } else { // reference within CMS heap 2464 if (_past_remark) { 2465 // Remark has been completed -- so the referent should have 2466 // been marked, if referring object is. 2467 if (_bit_map->isMarked(_collector->block_start(p))) { 2468 guarantee(_bit_map->isMarked((HeapWord*)obj), "Marking error?"); 2469 } 2470 } 2471 } 2472 } else if (_sp->is_in_reserved(p)) { 2473 // the reference is from FLS, and points out of FLS 2474 guarantee(oopDesc::is_oop(obj), "Should be an oop"); 2475 obj->verify(); 2476 } 2477 } 2478 2479 template <class T> void do_oop_work(T* p) { 2480 T heap_oop = RawAccess<>::oop_load(p); 2481 if (!CompressedOops::is_null(heap_oop)) { 2482 oop obj = CompressedOops::decode_not_null(heap_oop); 2483 do_oop(p, obj); 2484 } 2485 } 2486 2487 public: 2488 VerifyAllOopsClosure(const CMSCollector* collector, 2489 const CompactibleFreeListSpace* sp, MemRegion span, 2490 bool past_remark, CMSBitMap* bit_map) : 2491 _collector(collector), _sp(sp), _span(span), 2492 _past_remark(past_remark), _bit_map(bit_map) { } 2493 2494 virtual void do_oop(oop* p) { VerifyAllOopsClosure::do_oop_work(p); } 2495 virtual void do_oop(narrowOop* p) { VerifyAllOopsClosure::do_oop_work(p); } 2496 }; 2497 2498 void CompactibleFreeListSpace::verify() const { 2499 assert_lock_strong(&_freelistLock); 2500 verify_objects_initialized(); 2501 MemRegion span = _collector->_span; 2502 bool past_remark = (_collector->abstract_state() == 2503 CMSCollector::Sweeping); 2504 2505 ResourceMark rm; 2506 HandleMark hm; 2507 2508 // Check integrity of CFL data structures 2509 _promoInfo.verify(); 2510 _dictionary->verify(); 2511 if (FLSVerifyIndexTable) { 2512 verifyIndexedFreeLists(); 2513 } 2514 // Check integrity of all objects and free blocks in space 2515 { 2516 VerifyAllBlksClosure cl(this, span); 2517 ((CompactibleFreeListSpace*)this)->blk_iterate(&cl); // cast off const 2518 } 2519 // Check that all references in the heap to FLS 2520 // are to valid objects in FLS or that references in 2521 // FLS are to valid objects elsewhere in the heap 2522 if (FLSVerifyAllHeapReferences) 2523 { 2524 VerifyAllOopsClosure cl(_collector, this, span, past_remark, 2525 _collector->markBitMap()); 2526 2527 // Iterate over all oops in the heap. 2528 CMSHeap::heap()->oop_iterate(&cl); 2529 } 2530 2531 if (VerifyObjectStartArray) { 2532 // Verify the block offset table 2533 _bt.verify(); 2534 } 2535 } 2536 2537 #ifndef PRODUCT 2538 void CompactibleFreeListSpace::verifyFreeLists() const { 2539 if (FLSVerifyLists) { 2540 _dictionary->verify(); 2541 verifyIndexedFreeLists(); 2542 } else { 2543 if (FLSVerifyDictionary) { 2544 _dictionary->verify(); 2545 } 2546 if (FLSVerifyIndexTable) { 2547 verifyIndexedFreeLists(); 2548 } 2549 } 2550 } 2551 #endif 2552 2553 void CompactibleFreeListSpace::verifyIndexedFreeLists() const { 2554 size_t i = 0; 2555 for (; i < IndexSetStart; i++) { 2556 guarantee(_indexedFreeList[i].head() == NULL, "should be NULL"); 2557 } 2558 for (; i < IndexSetSize; i++) { 2559 verifyIndexedFreeList(i); 2560 } 2561 } 2562 2563 void CompactibleFreeListSpace::verifyIndexedFreeList(size_t size) const { 2564 FreeChunk* fc = _indexedFreeList[size].head(); 2565 FreeChunk* tail = _indexedFreeList[size].tail(); 2566 size_t num = _indexedFreeList[size].count(); 2567 size_t n = 0; 2568 guarantee(((size >= IndexSetStart) && (size % IndexSetStride == 0)) || fc == NULL, 2569 "Slot should have been empty"); 2570 for (; fc != NULL; fc = fc->next(), n++) { 2571 guarantee(fc->size() == size, "Size inconsistency"); 2572 guarantee(fc->is_free(), "!free?"); 2573 guarantee(fc->next() == NULL || fc->next()->prev() == fc, "Broken list"); 2574 guarantee((fc->next() == NULL) == (fc == tail), "Incorrect tail"); 2575 } 2576 guarantee(n == num, "Incorrect count"); 2577 } 2578 2579 #ifndef PRODUCT 2580 void CompactibleFreeListSpace::check_free_list_consistency() const { 2581 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size() <= IndexSetSize), 2582 "Some sizes can't be allocated without recourse to" 2583 " linear allocation buffers"); 2584 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size()*HeapWordSize == sizeof(TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >)), 2585 "else MIN_TREE_CHUNK_SIZE is wrong"); 2586 assert(IndexSetStart != 0, "IndexSetStart not initialized"); 2587 assert(IndexSetStride != 0, "IndexSetStride not initialized"); 2588 } 2589 #endif 2590 2591 void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const { 2592 assert_lock_strong(&_freelistLock); 2593 LogTarget(Debug, gc, freelist, census) log; 2594 if (!log.is_enabled()) { 2595 return; 2596 } 2597 AdaptiveFreeList<FreeChunk> total; 2598 log.print("end sweep# " SIZE_FORMAT, sweep_count); 2599 ResourceMark rm; 2600 LogStream ls(log); 2601 outputStream* out = &ls; 2602 AdaptiveFreeList<FreeChunk>::print_labels_on(out, "size"); 2603 size_t total_free = 0; 2604 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { 2605 const AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i]; 2606 total_free += fl->count() * fl->size(); 2607 if (i % (40*IndexSetStride) == 0) { 2608 AdaptiveFreeList<FreeChunk>::print_labels_on(out, "size"); 2609 } 2610 fl->print_on(out); 2611 total.set_bfr_surp( total.bfr_surp() + fl->bfr_surp() ); 2612 total.set_surplus( total.surplus() + fl->surplus() ); 2613 total.set_desired( total.desired() + fl->desired() ); 2614 total.set_prev_sweep( total.prev_sweep() + fl->prev_sweep() ); 2615 total.set_before_sweep(total.before_sweep() + fl->before_sweep()); 2616 total.set_count( total.count() + fl->count() ); 2617 total.set_coal_births( total.coal_births() + fl->coal_births() ); 2618 total.set_coal_deaths( total.coal_deaths() + fl->coal_deaths() ); 2619 total.set_split_births(total.split_births() + fl->split_births()); 2620 total.set_split_deaths(total.split_deaths() + fl->split_deaths()); 2621 } 2622 total.print_on(out, "TOTAL"); 2623 log.print("Total free in indexed lists " SIZE_FORMAT " words", total_free); 2624 log.print("growth: %8.5f deficit: %8.5f", 2625 (double)(total.split_births()+total.coal_births()-total.split_deaths()-total.coal_deaths())/ 2626 (total.prev_sweep() != 0 ? (double)total.prev_sweep() : 1.0), 2627 (double)(total.desired() - total.count())/(total.desired() != 0 ? (double)total.desired() : 1.0)); 2628 _dictionary->print_dict_census(out); 2629 } 2630 2631 /////////////////////////////////////////////////////////////////////////// 2632 // CompactibleFreeListSpaceLAB 2633 /////////////////////////////////////////////////////////////////////////// 2634 2635 #define VECTOR_257(x) \ 2636 /* 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 */ \ 2637 { 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, \ 2638 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, \ 2639 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, \ 2640 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, \ 2641 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, \ 2642 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, \ 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 } 2646 2647 // Initialize with default setting for CMS, _not_ 2648 // generic OldPLABSize, whose static default is different; if overridden at the 2649 // command-line, this will get reinitialized via a call to 2650 // modify_initialization() below. 2651 AdaptiveWeightedAverage CompactibleFreeListSpaceLAB::_blocks_to_claim[] = 2652 VECTOR_257(AdaptiveWeightedAverage(OldPLABWeight, (float)CompactibleFreeListSpaceLAB::_default_dynamic_old_plab_size)); 2653 size_t CompactibleFreeListSpaceLAB::_global_num_blocks[] = VECTOR_257(0); 2654 uint CompactibleFreeListSpaceLAB::_global_num_workers[] = VECTOR_257(0); 2655 2656 CompactibleFreeListSpaceLAB::CompactibleFreeListSpaceLAB(CompactibleFreeListSpace* cfls) : 2657 _cfls(cfls) 2658 { 2659 assert(CompactibleFreeListSpace::IndexSetSize == 257, "Modify VECTOR_257() macro above"); 2660 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2661 i < CompactibleFreeListSpace::IndexSetSize; 2662 i += CompactibleFreeListSpace::IndexSetStride) { 2663 _indexedFreeList[i].set_size(i); 2664 _num_blocks[i] = 0; 2665 } 2666 } 2667 2668 static bool _CFLS_LAB_modified = false; 2669 2670 void CompactibleFreeListSpaceLAB::modify_initialization(size_t n, unsigned wt) { 2671 assert(!_CFLS_LAB_modified, "Call only once"); 2672 _CFLS_LAB_modified = true; 2673 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2674 i < CompactibleFreeListSpace::IndexSetSize; 2675 i += CompactibleFreeListSpace::IndexSetStride) { 2676 _blocks_to_claim[i].modify(n, wt, true /* force */); 2677 } 2678 } 2679 2680 HeapWord* CompactibleFreeListSpaceLAB::alloc(size_t word_sz) { 2681 FreeChunk* res; 2682 assert(word_sz == _cfls->adjustObjectSize(word_sz), "Error"); 2683 if (word_sz >= CompactibleFreeListSpace::IndexSetSize) { 2684 // This locking manages sync with other large object allocations. 2685 MutexLockerEx x(_cfls->parDictionaryAllocLock(), 2686 Mutex::_no_safepoint_check_flag); 2687 res = _cfls->getChunkFromDictionaryExact(word_sz); 2688 if (res == NULL) return NULL; 2689 } else { 2690 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[word_sz]; 2691 if (fl->count() == 0) { 2692 // Attempt to refill this local free list. 2693 get_from_global_pool(word_sz, fl); 2694 // If it didn't work, give up. 2695 if (fl->count() == 0) return NULL; 2696 } 2697 res = fl->get_chunk_at_head(); 2698 assert(res != NULL, "Why was count non-zero?"); 2699 } 2700 res->markNotFree(); 2701 assert(!res->is_free(), "shouldn't be marked free"); 2702 assert(oop(res)->klass_or_null() == NULL, "should look uninitialized"); 2703 // mangle a just allocated object with a distinct pattern. 2704 debug_only(res->mangleAllocated(word_sz)); 2705 return (HeapWord*)res; 2706 } 2707 2708 // Get a chunk of blocks of the right size and update related 2709 // book-keeping stats 2710 void CompactibleFreeListSpaceLAB::get_from_global_pool(size_t word_sz, AdaptiveFreeList<FreeChunk>* fl) { 2711 // Get the #blocks we want to claim 2712 size_t n_blks = (size_t)_blocks_to_claim[word_sz].average(); 2713 assert(n_blks > 0, "Error"); 2714 assert(ResizeOldPLAB || n_blks == OldPLABSize, "Error"); 2715 // In some cases, when the application has a phase change, 2716 // there may be a sudden and sharp shift in the object survival 2717 // profile, and updating the counts at the end of a scavenge 2718 // may not be quick enough, giving rise to large scavenge pauses 2719 // during these phase changes. It is beneficial to detect such 2720 // changes on-the-fly during a scavenge and avoid such a phase-change 2721 // pothole. The following code is a heuristic attempt to do that. 2722 // It is protected by a product flag until we have gained 2723 // enough experience with this heuristic and fine-tuned its behavior. 2724 // WARNING: This might increase fragmentation if we overreact to 2725 // small spikes, so some kind of historical smoothing based on 2726 // previous experience with the greater reactivity might be useful. 2727 // Lacking sufficient experience, CMSOldPLABResizeQuicker is disabled by 2728 // default. 2729 if (ResizeOldPLAB && CMSOldPLABResizeQuicker) { 2730 // 2731 // On a 32-bit VM, the denominator can become zero because of integer overflow, 2732 // which is why there is a cast to double. 2733 // 2734 size_t multiple = (size_t) (_num_blocks[word_sz]/(((double)CMSOldPLABToleranceFactor)*CMSOldPLABNumRefills*n_blks)); 2735 n_blks += CMSOldPLABReactivityFactor*multiple*n_blks; 2736 n_blks = MIN2(n_blks, CMSOldPLABMax); 2737 } 2738 assert(n_blks > 0, "Error"); 2739 _cfls->par_get_chunk_of_blocks(word_sz, n_blks, fl); 2740 // Update stats table entry for this block size 2741 _num_blocks[word_sz] += fl->count(); 2742 } 2743 2744 void CompactibleFreeListSpaceLAB::compute_desired_plab_size() { 2745 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2746 i < CompactibleFreeListSpace::IndexSetSize; 2747 i += CompactibleFreeListSpace::IndexSetStride) { 2748 assert((_global_num_workers[i] == 0) == (_global_num_blocks[i] == 0), 2749 "Counter inconsistency"); 2750 if (_global_num_workers[i] > 0) { 2751 // Need to smooth wrt historical average 2752 if (ResizeOldPLAB) { 2753 _blocks_to_claim[i].sample( 2754 MAX2(CMSOldPLABMin, 2755 MIN2(CMSOldPLABMax, 2756 _global_num_blocks[i]/_global_num_workers[i]/CMSOldPLABNumRefills))); 2757 } 2758 // Reset counters for next round 2759 _global_num_workers[i] = 0; 2760 _global_num_blocks[i] = 0; 2761 log_trace(gc, plab)("[" SIZE_FORMAT "]: " SIZE_FORMAT, i, (size_t)_blocks_to_claim[i].average()); 2762 } 2763 } 2764 } 2765 2766 // If this is changed in the future to allow parallel 2767 // access, one would need to take the FL locks and, 2768 // depending on how it is used, stagger access from 2769 // parallel threads to reduce contention. 2770 void CompactibleFreeListSpaceLAB::retire(int tid) { 2771 // We run this single threaded with the world stopped; 2772 // so no need for locks and such. 2773 NOT_PRODUCT(Thread* t = Thread::current();) 2774 assert(Thread::current()->is_VM_thread(), "Error"); 2775 for (size_t i = CompactibleFreeListSpace::IndexSetStart; 2776 i < CompactibleFreeListSpace::IndexSetSize; 2777 i += CompactibleFreeListSpace::IndexSetStride) { 2778 assert(_num_blocks[i] >= (size_t)_indexedFreeList[i].count(), 2779 "Can't retire more than what we obtained"); 2780 if (_num_blocks[i] > 0) { 2781 size_t num_retire = _indexedFreeList[i].count(); 2782 assert(_num_blocks[i] > num_retire, "Should have used at least one"); 2783 { 2784 // MutexLockerEx x(_cfls->_indexedFreeListParLocks[i], 2785 // Mutex::_no_safepoint_check_flag); 2786 2787 // Update globals stats for num_blocks used 2788 _global_num_blocks[i] += (_num_blocks[i] - num_retire); 2789 _global_num_workers[i]++; 2790 assert(_global_num_workers[i] <= ParallelGCThreads, "Too big"); 2791 if (num_retire > 0) { 2792 _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]); 2793 // Reset this list. 2794 _indexedFreeList[i] = AdaptiveFreeList<FreeChunk>(); 2795 _indexedFreeList[i].set_size(i); 2796 } 2797 } 2798 log_trace(gc, plab)("%d[" SIZE_FORMAT "]: " SIZE_FORMAT "/" SIZE_FORMAT "/" SIZE_FORMAT, 2799 tid, i, num_retire, _num_blocks[i], (size_t)_blocks_to_claim[i].average()); 2800 // Reset stats for next round 2801 _num_blocks[i] = 0; 2802 } 2803 } 2804 } 2805 2806 // Used by par_get_chunk_of_blocks() for the chunks from the 2807 // indexed_free_lists. Looks for a chunk with size that is a multiple 2808 // of "word_sz" and if found, splits it into "word_sz" chunks and add 2809 // to the free list "fl". "n" is the maximum number of chunks to 2810 // be added to "fl". 2811 bool CompactibleFreeListSpace:: par_get_chunk_of_blocks_IFL(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) { 2812 2813 // We'll try all multiples of word_sz in the indexed set, starting with 2814 // word_sz itself and, if CMSSplitIndexedFreeListBlocks, try larger multiples, 2815 // then try getting a big chunk and splitting it. 2816 { 2817 bool found; 2818 int k; 2819 size_t cur_sz; 2820 for (k = 1, cur_sz = k * word_sz, found = false; 2821 (cur_sz < CompactibleFreeListSpace::IndexSetSize) && 2822 (CMSSplitIndexedFreeListBlocks || k <= 1); 2823 k++, cur_sz = k * word_sz) { 2824 AdaptiveFreeList<FreeChunk> fl_for_cur_sz; // Empty. 2825 fl_for_cur_sz.set_size(cur_sz); 2826 { 2827 MutexLockerEx x(_indexedFreeListParLocks[cur_sz], 2828 Mutex::_no_safepoint_check_flag); 2829 AdaptiveFreeList<FreeChunk>* gfl = &_indexedFreeList[cur_sz]; 2830 if (gfl->count() != 0) { 2831 // nn is the number of chunks of size cur_sz that 2832 // we'd need to split k-ways each, in order to create 2833 // "n" chunks of size word_sz each. 2834 const size_t nn = MAX2(n/k, (size_t)1); 2835 gfl->getFirstNChunksFromList(nn, &fl_for_cur_sz); 2836 found = true; 2837 if (k > 1) { 2838 // Update split death stats for the cur_sz-size blocks list: 2839 // we increment the split death count by the number of blocks 2840 // we just took from the cur_sz-size blocks list and which 2841 // we will be splitting below. 2842 ssize_t deaths = gfl->split_deaths() + 2843 fl_for_cur_sz.count(); 2844 gfl->set_split_deaths(deaths); 2845 } 2846 } 2847 } 2848 // Now transfer fl_for_cur_sz to fl. Common case, we hope, is k = 1. 2849 if (found) { 2850 if (k == 1) { 2851 fl->prepend(&fl_for_cur_sz); 2852 } else { 2853 // Divide each block on fl_for_cur_sz up k ways. 2854 FreeChunk* fc; 2855 while ((fc = fl_for_cur_sz.get_chunk_at_head()) != NULL) { 2856 // Must do this in reverse order, so that anybody attempting to 2857 // access the main chunk sees it as a single free block until we 2858 // change it. 2859 size_t fc_size = fc->size(); 2860 assert(fc->is_free(), "Error"); 2861 for (int i = k-1; i >= 0; i--) { 2862 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz); 2863 assert((i != 0) || 2864 ((fc == ffc) && ffc->is_free() && 2865 (ffc->size() == k*word_sz) && (fc_size == word_sz)), 2866 "Counting error"); 2867 ffc->set_size(word_sz); 2868 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. 2869 ffc->link_next(NULL); 2870 // Above must occur before BOT is updated below. 2871 OrderAccess::storestore(); 2872 // splitting from the right, fc_size == i * word_sz 2873 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */); 2874 fc_size -= word_sz; 2875 assert(fc_size == i*word_sz, "Error"); 2876 _bt.verify_not_unallocated((HeapWord*)ffc, word_sz); 2877 _bt.verify_single_block((HeapWord*)fc, fc_size); 2878 _bt.verify_single_block((HeapWord*)ffc, word_sz); 2879 // Push this on "fl". 2880 fl->return_chunk_at_head(ffc); 2881 } 2882 // TRAP 2883 assert(fl->tail()->next() == NULL, "List invariant."); 2884 } 2885 } 2886 // Update birth stats for this block size. 2887 size_t num = fl->count(); 2888 MutexLockerEx x(_indexedFreeListParLocks[word_sz], 2889 Mutex::_no_safepoint_check_flag); 2890 ssize_t births = _indexedFreeList[word_sz].split_births() + num; 2891 _indexedFreeList[word_sz].set_split_births(births); 2892 return true; 2893 } 2894 } 2895 return found; 2896 } 2897 } 2898 2899 FreeChunk* CompactibleFreeListSpace::get_n_way_chunk_to_split(size_t word_sz, size_t n) { 2900 2901 FreeChunk* fc = NULL; 2902 FreeChunk* rem_fc = NULL; 2903 size_t rem; 2904 { 2905 MutexLockerEx x(parDictionaryAllocLock(), 2906 Mutex::_no_safepoint_check_flag); 2907 while (n > 0) { 2908 fc = dictionary()->get_chunk(MAX2(n * word_sz, _dictionary->min_size())); 2909 if (fc != NULL) { 2910 break; 2911 } else { 2912 n--; 2913 } 2914 } 2915 if (fc == NULL) return NULL; 2916 // Otherwise, split up that block. 2917 assert((ssize_t)n >= 1, "Control point invariant"); 2918 assert(fc->is_free(), "Error: should be a free block"); 2919 _bt.verify_single_block((HeapWord*)fc, fc->size()); 2920 const size_t nn = fc->size() / word_sz; 2921 n = MIN2(nn, n); 2922 assert((ssize_t)n >= 1, "Control point invariant"); 2923 rem = fc->size() - n * word_sz; 2924 // If there is a remainder, and it's too small, allocate one fewer. 2925 if (rem > 0 && rem < MinChunkSize) { 2926 n--; rem += word_sz; 2927 } 2928 // Note that at this point we may have n == 0. 2929 assert((ssize_t)n >= 0, "Control point invariant"); 2930 2931 // If n is 0, the chunk fc that was found is not large 2932 // enough to leave a viable remainder. We are unable to 2933 // allocate even one block. Return fc to the 2934 // dictionary and return, leaving "fl" empty. 2935 if (n == 0) { 2936 returnChunkToDictionary(fc); 2937 return NULL; 2938 } 2939 2940 _bt.allocated((HeapWord*)fc, fc->size(), true /* reducing */); // update _unallocated_blk 2941 dictionary()->dict_census_update(fc->size(), 2942 true /*split*/, 2943 false /*birth*/); 2944 2945 // First return the remainder, if any. 2946 // Note that we hold the lock until we decide if we're going to give 2947 // back the remainder to the dictionary, since a concurrent allocation 2948 // may otherwise see the heap as empty. (We're willing to take that 2949 // hit if the block is a small block.) 2950 if (rem > 0) { 2951 size_t prefix_size = n * word_sz; 2952 rem_fc = (FreeChunk*)((HeapWord*)fc + prefix_size); 2953 rem_fc->set_size(rem); 2954 rem_fc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. 2955 rem_fc->link_next(NULL); 2956 // Above must occur before BOT is updated below. 2957 assert((ssize_t)n > 0 && prefix_size > 0 && rem_fc > fc, "Error"); 2958 OrderAccess::storestore(); 2959 _bt.split_block((HeapWord*)fc, fc->size(), prefix_size); 2960 assert(fc->is_free(), "Error"); 2961 fc->set_size(prefix_size); 2962 if (rem >= IndexSetSize) { 2963 returnChunkToDictionary(rem_fc); 2964 dictionary()->dict_census_update(rem, true /*split*/, true /*birth*/); 2965 rem_fc = NULL; 2966 } 2967 // Otherwise, return it to the small list below. 2968 } 2969 } 2970 if (rem_fc != NULL) { 2971 MutexLockerEx x(_indexedFreeListParLocks[rem], 2972 Mutex::_no_safepoint_check_flag); 2973 _bt.verify_not_unallocated((HeapWord*)rem_fc, rem_fc->size()); 2974 _indexedFreeList[rem].return_chunk_at_head(rem_fc); 2975 smallSplitBirth(rem); 2976 } 2977 assert(n * word_sz == fc->size(), 2978 "Chunk size " SIZE_FORMAT " is not exactly splittable by " 2979 SIZE_FORMAT " sized chunks of size " SIZE_FORMAT, 2980 fc->size(), n, word_sz); 2981 return fc; 2982 } 2983 2984 void CompactibleFreeListSpace:: par_get_chunk_of_blocks_dictionary(size_t word_sz, size_t targetted_number_of_chunks, AdaptiveFreeList<FreeChunk>* fl) { 2985 2986 FreeChunk* fc = get_n_way_chunk_to_split(word_sz, targetted_number_of_chunks); 2987 2988 if (fc == NULL) { 2989 return; 2990 } 2991 2992 size_t n = fc->size() / word_sz; 2993 2994 assert((ssize_t)n > 0, "Consistency"); 2995 // Now do the splitting up. 2996 // Must do this in reverse order, so that anybody attempting to 2997 // access the main chunk sees it as a single free block until we 2998 // change it. 2999 size_t fc_size = n * word_sz; 3000 // All but first chunk in this loop 3001 for (ssize_t i = n-1; i > 0; i--) { 3002 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz); 3003 ffc->set_size(word_sz); 3004 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. 3005 ffc->link_next(NULL); 3006 // Above must occur before BOT is updated below. 3007 OrderAccess::storestore(); 3008 // splitting from the right, fc_size == (n - i + 1) * wordsize 3009 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */); 3010 fc_size -= word_sz; 3011 _bt.verify_not_unallocated((HeapWord*)ffc, ffc->size()); 3012 _bt.verify_single_block((HeapWord*)ffc, ffc->size()); 3013 _bt.verify_single_block((HeapWord*)fc, fc_size); 3014 // Push this on "fl". 3015 fl->return_chunk_at_head(ffc); 3016 } 3017 // First chunk 3018 assert(fc->is_free() && fc->size() == n*word_sz, "Error: should still be a free block"); 3019 // The blocks above should show their new sizes before the first block below 3020 fc->set_size(word_sz); 3021 fc->link_prev(NULL); // idempotent wrt free-ness, see assert above 3022 fc->link_next(NULL); 3023 _bt.verify_not_unallocated((HeapWord*)fc, fc->size()); 3024 _bt.verify_single_block((HeapWord*)fc, fc->size()); 3025 fl->return_chunk_at_head(fc); 3026 3027 assert((ssize_t)n > 0 && (ssize_t)n == fl->count(), "Incorrect number of blocks"); 3028 { 3029 // Update the stats for this block size. 3030 MutexLockerEx x(_indexedFreeListParLocks[word_sz], 3031 Mutex::_no_safepoint_check_flag); 3032 const ssize_t births = _indexedFreeList[word_sz].split_births() + n; 3033 _indexedFreeList[word_sz].set_split_births(births); 3034 // ssize_t new_surplus = _indexedFreeList[word_sz].surplus() + n; 3035 // _indexedFreeList[word_sz].set_surplus(new_surplus); 3036 } 3037 3038 // TRAP 3039 assert(fl->tail()->next() == NULL, "List invariant."); 3040 } 3041 3042 void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) { 3043 assert(fl->count() == 0, "Precondition."); 3044 assert(word_sz < CompactibleFreeListSpace::IndexSetSize, 3045 "Precondition"); 3046 3047 if (par_get_chunk_of_blocks_IFL(word_sz, n, fl)) { 3048 // Got it 3049 return; 3050 } 3051 3052 // Otherwise, we'll split a block from the dictionary. 3053 par_get_chunk_of_blocks_dictionary(word_sz, n, fl); 3054 } 3055 3056 const size_t CompactibleFreeListSpace::max_flag_size_for_task_size() const { 3057 const size_t ergo_max = _old_gen->reserved().word_size() / (CardTable::card_size_in_words * BitsPerWord); 3058 return ergo_max; 3059 } 3060 3061 // Set up the space's par_seq_tasks structure for work claiming 3062 // for parallel rescan. See CMSParRemarkTask where this is currently used. 3063 // XXX Need to suitably abstract and generalize this and the next 3064 // method into one. 3065 void 3066 CompactibleFreeListSpace:: 3067 initialize_sequential_subtasks_for_rescan(int n_threads) { 3068 // The "size" of each task is fixed according to rescan_task_size. 3069 assert(n_threads > 0, "Unexpected n_threads argument"); 3070 const size_t task_size = rescan_task_size(); 3071 size_t n_tasks = (used_region().word_size() + task_size - 1)/task_size; 3072 assert((n_tasks == 0) == used_region().is_empty(), "n_tasks incorrect"); 3073 assert(n_tasks == 0 || 3074 ((used_region().start() + (n_tasks - 1)*task_size < used_region().end()) && 3075 (used_region().start() + n_tasks*task_size >= used_region().end())), 3076 "n_tasks calculation incorrect"); 3077 SequentialSubTasksDone* pst = conc_par_seq_tasks(); 3078 assert(!pst->valid(), "Clobbering existing data?"); 3079 // Sets the condition for completion of the subtask (how many threads 3080 // need to finish in order to be done). 3081 pst->set_n_threads(n_threads); 3082 pst->set_n_tasks((int)n_tasks); 3083 } 3084 3085 // Set up the space's par_seq_tasks structure for work claiming 3086 // for parallel concurrent marking. See CMSConcMarkTask where this is currently used. 3087 void 3088 CompactibleFreeListSpace:: 3089 initialize_sequential_subtasks_for_marking(int n_threads, 3090 HeapWord* low) { 3091 // The "size" of each task is fixed according to rescan_task_size. 3092 assert(n_threads > 0, "Unexpected n_threads argument"); 3093 const size_t task_size = marking_task_size(); 3094 assert(task_size > CardTable::card_size_in_words && 3095 (task_size % CardTable::card_size_in_words == 0), 3096 "Otherwise arithmetic below would be incorrect"); 3097 MemRegion span = _old_gen->reserved(); 3098 if (low != NULL) { 3099 if (span.contains(low)) { 3100 // Align low down to a card boundary so that 3101 // we can use block_offset_careful() on span boundaries. 3102 HeapWord* aligned_low = align_down(low, CardTable::card_size); 3103 // Clip span prefix at aligned_low 3104 span = span.intersection(MemRegion(aligned_low, span.end())); 3105 } else if (low > span.end()) { 3106 span = MemRegion(low, low); // Null region 3107 } // else use entire span 3108 } 3109 assert(span.is_empty() || 3110 ((uintptr_t)span.start() % CardTable::card_size == 0), 3111 "span should start at a card boundary"); 3112 size_t n_tasks = (span.word_size() + task_size - 1)/task_size; 3113 assert((n_tasks == 0) == span.is_empty(), "Inconsistency"); 3114 assert(n_tasks == 0 || 3115 ((span.start() + (n_tasks - 1)*task_size < span.end()) && 3116 (span.start() + n_tasks*task_size >= span.end())), 3117 "n_tasks calculation incorrect"); 3118 SequentialSubTasksDone* pst = conc_par_seq_tasks(); 3119 assert(!pst->valid(), "Clobbering existing data?"); 3120 // Sets the condition for completion of the subtask (how many threads 3121 // need to finish in order to be done). 3122 pst->set_n_threads(n_threads); 3123 pst->set_n_tasks((int)n_tasks); 3124 }