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