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