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