1 /*
   2  * Copyright (c) 2001, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "gc/cms/cmsLockVerifier.hpp"
  27 #include "gc/cms/compactibleFreeListSpace.hpp"
  28 #include "gc/cms/concurrentMarkSweepGeneration.inline.hpp"
  29 #include "gc/cms/concurrentMarkSweepThread.hpp"
  30 #include "gc/shared/blockOffsetTable.inline.hpp"
  31 #include "gc/shared/collectedHeap.inline.hpp"
  32 #include "gc/shared/genCollectedHeap.hpp"

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