< prev index next >

src/share/vm/gc/cms/compactibleFreeListSpace.cpp

Print this page




 383 }
 384 
 385 void CompactibleFreeListSpace::print_on(outputStream* st) const {
 386   st->print_cr("COMPACTIBLE FREELIST SPACE");
 387   st->print_cr(" Space:");
 388   Space::print_on(st);
 389 
 390   st->print_cr("promoInfo:");
 391   _promoInfo.print_on(st);
 392 
 393   st->print_cr("_smallLinearAllocBlock");
 394   _smallLinearAllocBlock.print_on(st);
 395 
 396   // dump_memory_block(_smallLinearAllocBlock->_ptr, 128);
 397 
 398   st->print_cr(" _fitStrategy = %s", BOOL_TO_STR(_fitStrategy));
 399 }
 400 
 401 void CompactibleFreeListSpace::print_indexed_free_lists(outputStream* st)
 402 const {
 403   reportIndexedFreeListStatistics();
 404   gclog_or_tty->print_cr("Layout of Indexed Freelists");
 405   gclog_or_tty->print_cr("---------------------------");
 406   AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size");
 407   for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
 408     _indexedFreeList[i].print_on(gclog_or_tty);
 409     for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
 410          fc = fc->next()) {
 411       gclog_or_tty->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ")  %s",
 412                           p2i(fc), p2i((HeapWord*)fc + i),
 413                           fc->cantCoalesce() ? "\t CC" : "");
 414     }
 415   }
 416 }
 417 
 418 void CompactibleFreeListSpace::print_promo_info_blocks(outputStream* st)
 419 const {
 420   _promoInfo.print_on(st);
 421 }
 422 
 423 void CompactibleFreeListSpace::print_dictionary_free_lists(outputStream* st)
 424 const {
 425   _dictionary->report_statistics();
 426   st->print_cr("Layout of Freelists in Tree");
 427   st->print_cr("---------------------------");
 428   _dictionary->print_free_lists(st);
 429 }
 430 
 431 class BlkPrintingClosure: public BlkClosure {
 432   const CMSCollector*             _collector;
 433   const CompactibleFreeListSpace* _sp;
 434   const CMSBitMap*                _live_bit_map;
 435   const bool                      _post_remark;
 436   outputStream*                   _st;
 437 public:
 438   BlkPrintingClosure(const CMSCollector* collector,
 439                      const CompactibleFreeListSpace* sp,
 440                      const CMSBitMap* live_bit_map,
 441                      outputStream* st):
 442     _collector(collector),
 443     _sp(sp),
 444     _live_bit_map(live_bit_map),
 445     _post_remark(collector->abstract_state() > CMSCollector::FinalMarking),


 455     _st->print_cr(PTR_FORMAT ": %s object of size " SIZE_FORMAT "%s",
 456       p2i(addr),
 457       dead ? "dead" : "live",
 458       sz,
 459       (!dead && CMSPrintObjectsInDump) ? ":" : ".");
 460     if (CMSPrintObjectsInDump && !dead) {
 461       oop(addr)->print_on(_st);
 462       _st->print_cr("--------------------------------------");
 463     }
 464   } else { // free block
 465     _st->print_cr(PTR_FORMAT ": free block of size " SIZE_FORMAT "%s",
 466       p2i(addr), sz, CMSPrintChunksInDump ? ":" : ".");
 467     if (CMSPrintChunksInDump) {
 468       ((FreeChunk*)addr)->print_on(_st);
 469       _st->print_cr("--------------------------------------");
 470     }
 471   }
 472   return sz;
 473 }
 474 
 475 void CompactibleFreeListSpace::dump_at_safepoint_with_locks(CMSCollector* c,
 476   outputStream* st) {
 477   st->print_cr("\n=========================");
 478   st->print_cr("Block layout in CMS Heap:");
 479   st->print_cr("=========================");
 480   BlkPrintingClosure  bpcl(c, this, c->markBitMap(), st);
 481   blk_iterate(&bpcl);
 482 
 483   st->print_cr("\n=======================================");
 484   st->print_cr("Order & Layout of Promotion Info Blocks");
 485   st->print_cr("=======================================");
 486   print_promo_info_blocks(st);
 487 
 488   st->print_cr("\n===========================");
 489   st->print_cr("Order of Indexed Free Lists");
 490   st->print_cr("=========================");
 491   print_indexed_free_lists(st);
 492 
 493   st->print_cr("\n=================================");
 494   st->print_cr("Order of Free Lists in Dictionary");
 495   st->print_cr("=================================");
 496   print_dictionary_free_lists(st);
 497 }
 498 
 499 
 500 void CompactibleFreeListSpace::reportFreeListStatistics() const {
 501   assert_lock_strong(&_freelistLock);
 502   assert(PrintFLSStatistics != 0, "Reporting error");
 503   _dictionary->report_statistics();
 504   if (PrintFLSStatistics > 1) {
 505     reportIndexedFreeListStatistics();





 506     size_t total_size = totalSizeInIndexedFreeLists() +
 507                        _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
 508     gclog_or_tty->print(" free=" SIZE_FORMAT " frag=%1.4f\n", total_size, flsFrag());
 509   }
 510 }
 511 
 512 void CompactibleFreeListSpace::reportIndexedFreeListStatistics() const {
 513   assert_lock_strong(&_freelistLock);
 514   gclog_or_tty->print("Statistics for IndexedFreeLists:\n"
 515                       "--------------------------------\n");
 516   size_t total_size = totalSizeInIndexedFreeLists();
 517   size_t   free_blocks = numFreeBlocksInIndexedFreeLists();
 518   gclog_or_tty->print("Total Free Space: " SIZE_FORMAT "\n", total_size);
 519   gclog_or_tty->print("Max   Chunk Size: " SIZE_FORMAT "\n", maxChunkSizeInIndexedFreeLists());
 520   gclog_or_tty->print("Number of Blocks: " SIZE_FORMAT "\n", free_blocks);
 521   if (free_blocks != 0) {
 522     gclog_or_tty->print("Av.  Block  Size: " SIZE_FORMAT "\n", total_size/free_blocks);
 523   }
 524 }
 525 
 526 size_t CompactibleFreeListSpace::numFreeBlocksInIndexedFreeLists() const {
 527   size_t res = 0;
 528   for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
 529     debug_only(
 530       ssize_t recount = 0;
 531       for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
 532          fc = fc->next()) {
 533         recount += 1;
 534       }
 535       assert(recount == _indexedFreeList[i].count(),
 536         "Incorrect count in list");
 537     )
 538     res += _indexedFreeList[i].count();
 539   }
 540   return res;
 541 }
 542 


1807     split(size, rem_sz);
1808     if (is_par) _indexedFreeListParLocks[rem_sz]->unlock();
1809   } else {
1810     returnChunkToDictionary(ffc);
1811     split(size, rem_sz);
1812   }
1813   chunk->set_size(new_size);
1814   return chunk;
1815 }
1816 
1817 void
1818 CompactibleFreeListSpace::sweep_completed() {
1819   // Now that space is probably plentiful, refill linear
1820   // allocation blocks as needed.
1821   refillLinearAllocBlocksIfNeeded();
1822 }
1823 
1824 void
1825 CompactibleFreeListSpace::gc_prologue() {
1826   assert_locked();
1827   if (PrintFLSStatistics != 0) {
1828     gclog_or_tty->print("Before GC:\n");
1829     reportFreeListStatistics();
1830   }
1831   refillLinearAllocBlocksIfNeeded();
1832 }
1833 
1834 void
1835 CompactibleFreeListSpace::gc_epilogue() {
1836   assert_locked();
1837   assert(_promoInfo.noPromotions(), "_promoInfo inconsistency");
1838   _promoInfo.stopTrackingPromotions();
1839   repairLinearAllocationBlocks();
1840   // Print Space's stats
1841   if (PrintFLSStatistics != 0) {
1842     gclog_or_tty->print("After GC:\n");
1843     reportFreeListStatistics();
1844   }
1845 }
1846 
1847 // Iteration support, mostly delegated from a CMS generation
1848 
1849 void CompactibleFreeListSpace::save_marks() {
1850   assert(Thread::current()->is_VM_thread(),
1851          "Global variable should only be set when single-threaded");
1852   // Mark the "end" of the used space at the time of this call;
1853   // note, however, that promoted objects from this point
1854   // on are tracked in the _promoInfo below.
1855   set_saved_mark_word(unallocated_block());
1856 #ifdef ASSERT
1857   // Check the sanity of save_marks() etc.
1858   MemRegion ur    = used_region();
1859   MemRegion urasm = used_region_at_save_marks();
1860   assert(ur.contains(urasm),
1861          " Error at save_marks(): [" PTR_FORMAT "," PTR_FORMAT ")"
1862          " should contain [" PTR_FORMAT "," PTR_FORMAT ")",
1863          p2i(ur.start()), p2i(ur.end()), p2i(urasm.start()), p2i(urasm.end()));
1864 #endif


1997   double totFree = itabFree +
1998                    _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
1999   if (totFree > 0) {
2000     frag = ((frag + _dictionary->sum_of_squared_block_sizes()) /
2001             (totFree * totFree));
2002     frag = (double)1.0  - frag;
2003   } else {
2004     assert(frag == 0.0, "Follows from totFree == 0");
2005   }
2006   return frag;
2007 }
2008 
2009 void CompactibleFreeListSpace::beginSweepFLCensus(
2010   float inter_sweep_current,
2011   float inter_sweep_estimate,
2012   float intra_sweep_estimate) {
2013   assert_locked();
2014   size_t i;
2015   for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2016     AdaptiveFreeList<FreeChunk>* fl    = &_indexedFreeList[i];
2017     if (PrintFLSStatistics > 1) {
2018       gclog_or_tty->print("size[" SIZE_FORMAT "] : ", i);
2019     }
2020     fl->compute_desired(inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate);
2021     fl->set_coal_desired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent));
2022     fl->set_before_sweep(fl->count());
2023     fl->set_bfr_surp(fl->surplus());
2024   }
2025   _dictionary->begin_sweep_dict_census(CMSLargeCoalSurplusPercent,
2026                                     inter_sweep_current,
2027                                     inter_sweep_estimate,
2028                                     intra_sweep_estimate);
2029 }
2030 
2031 void CompactibleFreeListSpace::setFLSurplus() {
2032   assert_locked();
2033   size_t i;
2034   for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2035     AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2036     fl->set_surplus(fl->count() -
2037                     (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent));
2038   }
2039 }


2048     if (fl->surplus() > 0) {
2049       h = i;
2050     }
2051   }
2052 }
2053 
2054 void CompactibleFreeListSpace::clearFLCensus() {
2055   assert_locked();
2056   size_t i;
2057   for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2058     AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2059     fl->set_prev_sweep(fl->count());
2060     fl->set_coal_births(0);
2061     fl->set_coal_deaths(0);
2062     fl->set_split_births(0);
2063     fl->set_split_deaths(0);
2064   }
2065 }
2066 
2067 void CompactibleFreeListSpace::endSweepFLCensus(size_t sweep_count) {
2068   if (PrintFLSStatistics > 0) {
2069     HeapWord* largestAddr = (HeapWord*) dictionary()->find_largest_dict();
2070     gclog_or_tty->print_cr("CMS: Large block " PTR_FORMAT,
2071                            p2i(largestAddr));
2072   }
2073   setFLSurplus();
2074   setFLHints();
2075   if (PrintGC && PrintFLSCensus > 0) {
2076     printFLCensus(sweep_count);
2077   }
2078   clearFLCensus();
2079   assert_locked();
2080   _dictionary->end_sweep_dict_census(CMSLargeSplitSurplusPercent);
2081 }
2082 
2083 bool CompactibleFreeListSpace::coalOverPopulated(size_t size) {
2084   if (size < SmallForDictionary) {
2085     AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2086     return (fl->coal_desired() < 0) ||
2087            ((int)fl->count() > fl->coal_desired());
2088   } else {
2089     return dictionary()->coal_dict_over_populated(size);
2090   }
2091 }
2092 
2093 void CompactibleFreeListSpace::smallCoalBirth(size_t size) {
2094   assert(size < SmallForDictionary, "Size too large for indexed list");
2095   AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2096   fl->increment_coal_births();
2097   fl->increment_surplus();


2196     bool   was_obj  = false;
2197     bool   was_live = false;
2198     if (_sp->block_is_obj(addr)) {
2199       was_obj = true;
2200       oop p = oop(addr);
2201       guarantee(p->is_oop(), "Should be an oop");
2202       res = _sp->adjustObjectSize(p->size());
2203       if (_sp->obj_is_alive(addr)) {
2204         was_live = true;
2205         p->verify();
2206       }
2207     } else {
2208       FreeChunk* fc = (FreeChunk*)addr;
2209       res = fc->size();
2210       if (FLSVerifyLists && !fc->cantCoalesce()) {
2211         guarantee(_sp->verify_chunk_in_free_list(fc),
2212                   "Chunk should be on a free list");
2213       }
2214     }
2215     if (res == 0) {
2216       gclog_or_tty->print_cr("Livelock: no rank reduction!");
2217       gclog_or_tty->print_cr(
2218         " Current:  addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n"
2219         " Previous: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n",
2220         p2i(addr),       res,        was_obj      ?"true":"false", was_live      ?"true":"false",
2221         p2i(_last_addr), _last_size, _last_was_obj?"true":"false", _last_was_live?"true":"false");
2222       _sp->print_on(gclog_or_tty);
2223       guarantee(false, "Seppuku!");

2224     }
2225     _last_addr = addr;
2226     _last_size = res;
2227     _last_was_obj  = was_obj;
2228     _last_was_live = was_live;
2229     return res;
2230   }
2231 };
2232 
2233 class VerifyAllOopsClosure: public OopClosure {
2234  private:
2235   const CMSCollector*             _collector;
2236   const CompactibleFreeListSpace* _sp;
2237   const MemRegion                 _span;
2238   const bool                      _past_remark;
2239   const CMSBitMap*                _bit_map;
2240 
2241  protected:
2242   void do_oop(void* p, oop obj) {
2243     if (_span.contains(obj)) { // the interior oop points into CMS heap


2369     guarantee(fc->next() == NULL || fc->next()->prev() == fc, "Broken list");
2370     guarantee((fc->next() == NULL) == (fc == tail), "Incorrect tail");
2371   }
2372   guarantee(n == num, "Incorrect count");
2373 }
2374 
2375 #ifndef PRODUCT
2376 void CompactibleFreeListSpace::check_free_list_consistency() const {
2377   assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size() <= IndexSetSize),
2378     "Some sizes can't be allocated without recourse to"
2379     " linear allocation buffers");
2380   assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size()*HeapWordSize == sizeof(TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >)),
2381     "else MIN_TREE_CHUNK_SIZE is wrong");
2382   assert(IndexSetStart != 0, "IndexSetStart not initialized");
2383   assert(IndexSetStride != 0, "IndexSetStride not initialized");
2384 }
2385 #endif
2386 
2387 void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const {
2388   assert_lock_strong(&_freelistLock);




2389   AdaptiveFreeList<FreeChunk> total;
2390   gclog_or_tty->print("end sweep# " SIZE_FORMAT "\n", sweep_count);
2391   AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");


2392   size_t total_free = 0;
2393   for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2394     const AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2395     total_free += fl->count() * fl->size();
2396     if (i % (40*IndexSetStride) == 0) {
2397       AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
2398     }
2399     fl->print_on(gclog_or_tty);
2400     total.set_bfr_surp(    total.bfr_surp()     + fl->bfr_surp()    );
2401     total.set_surplus(    total.surplus()     + fl->surplus()    );
2402     total.set_desired(    total.desired()     + fl->desired()    );
2403     total.set_prev_sweep(  total.prev_sweep()   + fl->prev_sweep()  );
2404     total.set_before_sweep(total.before_sweep() + fl->before_sweep());
2405     total.set_count(      total.count()       + fl->count()      );
2406     total.set_coal_births( total.coal_births()  + fl->coal_births() );
2407     total.set_coal_deaths( total.coal_deaths()  + fl->coal_deaths() );
2408     total.set_split_births(total.split_births() + fl->split_births());
2409     total.set_split_deaths(total.split_deaths() + fl->split_deaths());
2410   }
2411   total.print_on(gclog_or_tty, "TOTAL");
2412   gclog_or_tty->print_cr("Total free in indexed lists "
2413                          SIZE_FORMAT " words", total_free);
2414   gclog_or_tty->print("growth: %8.5f  deficit: %8.5f\n",
2415     (double)(total.split_births()+total.coal_births()-total.split_deaths()-total.coal_deaths())/
2416             (total.prev_sweep() != 0 ? (double)total.prev_sweep() : 1.0),
2417     (double)(total.desired() - total.count())/(total.desired() != 0 ? (double)total.desired() : 1.0));
2418   _dictionary->print_dict_census();
2419 }
2420 
2421 ///////////////////////////////////////////////////////////////////////////
2422 // CFLS_LAB
2423 ///////////////////////////////////////////////////////////////////////////
2424 
2425 #define VECTOR_257(x)                                                                                  \
2426   /* 1  2  3  4  5  6  7  8  9 1x 11 12 13 14 15 16 17 18 19 2x 21 22 23 24 25 26 27 28 29 3x 31 32 */ \
2427   {  x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2428      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2429      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2430      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2431      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2432      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2433      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2434      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2435      x }
2436 
2437 // Initialize with default setting for CMS, _not_
2438 // generic OldPLABSize, whose static default is different; if overridden at the


2527   _num_blocks[word_sz] += fl->count();
2528 }
2529 
2530 void CFLS_LAB::compute_desired_plab_size() {
2531   for (size_t i =  CompactibleFreeListSpace::IndexSetStart;
2532        i < CompactibleFreeListSpace::IndexSetSize;
2533        i += CompactibleFreeListSpace::IndexSetStride) {
2534     assert((_global_num_workers[i] == 0) == (_global_num_blocks[i] == 0),
2535            "Counter inconsistency");
2536     if (_global_num_workers[i] > 0) {
2537       // Need to smooth wrt historical average
2538       if (ResizeOldPLAB) {
2539         _blocks_to_claim[i].sample(
2540           MAX2(CMSOldPLABMin,
2541           MIN2(CMSOldPLABMax,
2542                _global_num_blocks[i]/(_global_num_workers[i]*CMSOldPLABNumRefills))));
2543       }
2544       // Reset counters for next round
2545       _global_num_workers[i] = 0;
2546       _global_num_blocks[i] = 0;
2547       if (PrintOldPLAB) {
2548         gclog_or_tty->print_cr("[" SIZE_FORMAT "]: " SIZE_FORMAT,
2549                                i, (size_t)_blocks_to_claim[i].average());
2550       }
2551     }
2552   }
2553 }
2554 
2555 // If this is changed in the future to allow parallel
2556 // access, one would need to take the FL locks and,
2557 // depending on how it is used, stagger access from
2558 // parallel threads to reduce contention.
2559 void CFLS_LAB::retire(int tid) {
2560   // We run this single threaded with the world stopped;
2561   // so no need for locks and such.
2562   NOT_PRODUCT(Thread* t = Thread::current();)
2563   assert(Thread::current()->is_VM_thread(), "Error");
2564   for (size_t i =  CompactibleFreeListSpace::IndexSetStart;
2565        i < CompactibleFreeListSpace::IndexSetSize;
2566        i += CompactibleFreeListSpace::IndexSetStride) {
2567     assert(_num_blocks[i] >= (size_t)_indexedFreeList[i].count(),
2568            "Can't retire more than what we obtained");
2569     if (_num_blocks[i] > 0) {
2570       size_t num_retire =  _indexedFreeList[i].count();
2571       assert(_num_blocks[i] > num_retire, "Should have used at least one");
2572       {
2573         // MutexLockerEx x(_cfls->_indexedFreeListParLocks[i],
2574         //                Mutex::_no_safepoint_check_flag);
2575 
2576         // Update globals stats for num_blocks used
2577         _global_num_blocks[i] += (_num_blocks[i] - num_retire);
2578         _global_num_workers[i]++;
2579         assert(_global_num_workers[i] <= ParallelGCThreads, "Too big");
2580         if (num_retire > 0) {
2581           _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]);
2582           // Reset this list.
2583           _indexedFreeList[i] = AdaptiveFreeList<FreeChunk>();
2584           _indexedFreeList[i].set_size(i);
2585         }
2586       }
2587       if (PrintOldPLAB) {
2588         gclog_or_tty->print_cr("%d[" SIZE_FORMAT "]: " SIZE_FORMAT "/" SIZE_FORMAT "/" SIZE_FORMAT,
2589                                tid, i, num_retire, _num_blocks[i], (size_t)_blocks_to_claim[i].average());
2590       }
2591       // Reset stats for next round
2592       _num_blocks[i]         = 0;
2593     }
2594   }
2595 }
2596 
2597 // Used by par_get_chunk_of_blocks() for the chunks from the
2598 // indexed_free_lists.  Looks for a chunk with size that is a multiple
2599 // of "word_sz" and if found, splits it into "word_sz" chunks and add
2600 // to the free list "fl".  "n" is the maximum number of chunks to
2601 // be added to "fl".
2602 bool CompactibleFreeListSpace:: par_get_chunk_of_blocks_IFL(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) {
2603 
2604   // We'll try all multiples of word_sz in the indexed set, starting with
2605   // word_sz itself and, if CMSSplitIndexedFreeListBlocks, try larger multiples,
2606   // then try getting a big chunk and splitting it.
2607   {
2608     bool found;
2609     int  k;
2610     size_t cur_sz;




 383 }
 384 
 385 void CompactibleFreeListSpace::print_on(outputStream* st) const {
 386   st->print_cr("COMPACTIBLE FREELIST SPACE");
 387   st->print_cr(" Space:");
 388   Space::print_on(st);
 389 
 390   st->print_cr("promoInfo:");
 391   _promoInfo.print_on(st);
 392 
 393   st->print_cr("_smallLinearAllocBlock");
 394   _smallLinearAllocBlock.print_on(st);
 395 
 396   // dump_memory_block(_smallLinearAllocBlock->_ptr, 128);
 397 
 398   st->print_cr(" _fitStrategy = %s", BOOL_TO_STR(_fitStrategy));
 399 }
 400 
 401 void CompactibleFreeListSpace::print_indexed_free_lists(outputStream* st)
 402 const {
 403   reportIndexedFreeListStatistics(st);
 404   st->print_cr("Layout of Indexed Freelists");
 405   st->print_cr("---------------------------");
 406   AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size");
 407   for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
 408     _indexedFreeList[i].print_on(st);
 409     for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL; fc = fc->next()) {
 410       st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ")  %s",

 411                    p2i(fc), p2i((HeapWord*)fc + i),
 412                    fc->cantCoalesce() ? "\t CC" : "");
 413     }
 414   }
 415 }
 416 
 417 void CompactibleFreeListSpace::print_promo_info_blocks(outputStream* st)
 418 const {
 419   _promoInfo.print_on(st);
 420 }
 421 
 422 void CompactibleFreeListSpace::print_dictionary_free_lists(outputStream* st)
 423 const {
 424   _dictionary->report_statistics(st);
 425   st->print_cr("Layout of Freelists in Tree");
 426   st->print_cr("---------------------------");
 427   _dictionary->print_free_lists(st);
 428 }
 429 
 430 class BlkPrintingClosure: public BlkClosure {
 431   const CMSCollector*             _collector;
 432   const CompactibleFreeListSpace* _sp;
 433   const CMSBitMap*                _live_bit_map;
 434   const bool                      _post_remark;
 435   outputStream*                   _st;
 436 public:
 437   BlkPrintingClosure(const CMSCollector* collector,
 438                      const CompactibleFreeListSpace* sp,
 439                      const CMSBitMap* live_bit_map,
 440                      outputStream* st):
 441     _collector(collector),
 442     _sp(sp),
 443     _live_bit_map(live_bit_map),
 444     _post_remark(collector->abstract_state() > CMSCollector::FinalMarking),


 454     _st->print_cr(PTR_FORMAT ": %s object of size " SIZE_FORMAT "%s",
 455       p2i(addr),
 456       dead ? "dead" : "live",
 457       sz,
 458       (!dead && CMSPrintObjectsInDump) ? ":" : ".");
 459     if (CMSPrintObjectsInDump && !dead) {
 460       oop(addr)->print_on(_st);
 461       _st->print_cr("--------------------------------------");
 462     }
 463   } else { // free block
 464     _st->print_cr(PTR_FORMAT ": free block of size " SIZE_FORMAT "%s",
 465       p2i(addr), sz, CMSPrintChunksInDump ? ":" : ".");
 466     if (CMSPrintChunksInDump) {
 467       ((FreeChunk*)addr)->print_on(_st);
 468       _st->print_cr("--------------------------------------");
 469     }
 470   }
 471   return sz;
 472 }
 473 
 474 void CompactibleFreeListSpace::dump_at_safepoint_with_locks(CMSCollector* c, outputStream* st) {
 475   st->print_cr("=========================");

 476   st->print_cr("Block layout in CMS Heap:");
 477   st->print_cr("=========================");
 478   BlkPrintingClosure  bpcl(c, this, c->markBitMap(), st);
 479   blk_iterate(&bpcl);
 480 
 481   st->print_cr("=======================================");
 482   st->print_cr("Order & Layout of Promotion Info Blocks");
 483   st->print_cr("=======================================");
 484   print_promo_info_blocks(st);
 485 
 486   st->print_cr("===========================");
 487   st->print_cr("Order of Indexed Free Lists");
 488   st->print_cr("=========================");
 489   print_indexed_free_lists(st);
 490 
 491   st->print_cr("=================================");
 492   st->print_cr("Order of Free Lists in Dictionary");
 493   st->print_cr("=================================");
 494   print_dictionary_free_lists(st);
 495 }
 496 
 497 
 498 void CompactibleFreeListSpace::reportFreeListStatistics(const char* title) const {
 499   assert_lock_strong(&_freelistLock);
 500   LogHandle(gc, freelist, stats) log;
 501   if (!log.is_debug()) {
 502     return;
 503   }
 504   log.debug("%s", title);
 505   _dictionary->report_statistics(log.debug_stream());
 506   if (log.is_trace()) {
 507     ResourceMark rm;
 508     reportIndexedFreeListStatistics(log.trace_stream());
 509     size_t total_size = totalSizeInIndexedFreeLists() +
 510                        _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
 511     log.trace(" free=" SIZE_FORMAT " frag=%1.4f", total_size, flsFrag());
 512   }
 513 }
 514 
 515 void CompactibleFreeListSpace::reportIndexedFreeListStatistics(outputStream* st) const {
 516   assert_lock_strong(&_freelistLock);
 517   st->print_cr("Statistics for IndexedFreeLists:");
 518   st->print_cr("--------------------------------");
 519   size_t total_size = totalSizeInIndexedFreeLists();
 520   size_t free_blocks = numFreeBlocksInIndexedFreeLists();
 521   st->print_cr("Total Free Space: " SIZE_FORMAT, total_size);
 522   st->print_cr("Max   Chunk Size: " SIZE_FORMAT, maxChunkSizeInIndexedFreeLists());
 523   st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks);
 524   if (free_blocks != 0) {
 525     st->print_cr("Av.  Block  Size: " SIZE_FORMAT, total_size/free_blocks);
 526   }
 527 }
 528 
 529 size_t CompactibleFreeListSpace::numFreeBlocksInIndexedFreeLists() const {
 530   size_t res = 0;
 531   for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
 532     debug_only(
 533       ssize_t recount = 0;
 534       for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
 535          fc = fc->next()) {
 536         recount += 1;
 537       }
 538       assert(recount == _indexedFreeList[i].count(),
 539         "Incorrect count in list");
 540     )
 541     res += _indexedFreeList[i].count();
 542   }
 543   return res;
 544 }
 545 


1810     split(size, rem_sz);
1811     if (is_par) _indexedFreeListParLocks[rem_sz]->unlock();
1812   } else {
1813     returnChunkToDictionary(ffc);
1814     split(size, rem_sz);
1815   }
1816   chunk->set_size(new_size);
1817   return chunk;
1818 }
1819 
1820 void
1821 CompactibleFreeListSpace::sweep_completed() {
1822   // Now that space is probably plentiful, refill linear
1823   // allocation blocks as needed.
1824   refillLinearAllocBlocksIfNeeded();
1825 }
1826 
1827 void
1828 CompactibleFreeListSpace::gc_prologue() {
1829   assert_locked();
1830   reportFreeListStatistics("Before GC:");



1831   refillLinearAllocBlocksIfNeeded();
1832 }
1833 
1834 void
1835 CompactibleFreeListSpace::gc_epilogue() {
1836   assert_locked();
1837   assert(_promoInfo.noPromotions(), "_promoInfo inconsistency");
1838   _promoInfo.stopTrackingPromotions();
1839   repairLinearAllocationBlocks();
1840   reportFreeListStatistics("After GC:");




1841 }
1842 
1843 // Iteration support, mostly delegated from a CMS generation
1844 
1845 void CompactibleFreeListSpace::save_marks() {
1846   assert(Thread::current()->is_VM_thread(),
1847          "Global variable should only be set when single-threaded");
1848   // Mark the "end" of the used space at the time of this call;
1849   // note, however, that promoted objects from this point
1850   // on are tracked in the _promoInfo below.
1851   set_saved_mark_word(unallocated_block());
1852 #ifdef ASSERT
1853   // Check the sanity of save_marks() etc.
1854   MemRegion ur    = used_region();
1855   MemRegion urasm = used_region_at_save_marks();
1856   assert(ur.contains(urasm),
1857          " Error at save_marks(): [" PTR_FORMAT "," PTR_FORMAT ")"
1858          " should contain [" PTR_FORMAT "," PTR_FORMAT ")",
1859          p2i(ur.start()), p2i(ur.end()), p2i(urasm.start()), p2i(urasm.end()));
1860 #endif


1993   double totFree = itabFree +
1994                    _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
1995   if (totFree > 0) {
1996     frag = ((frag + _dictionary->sum_of_squared_block_sizes()) /
1997             (totFree * totFree));
1998     frag = (double)1.0  - frag;
1999   } else {
2000     assert(frag == 0.0, "Follows from totFree == 0");
2001   }
2002   return frag;
2003 }
2004 
2005 void CompactibleFreeListSpace::beginSweepFLCensus(
2006   float inter_sweep_current,
2007   float inter_sweep_estimate,
2008   float intra_sweep_estimate) {
2009   assert_locked();
2010   size_t i;
2011   for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2012     AdaptiveFreeList<FreeChunk>* fl    = &_indexedFreeList[i];
2013     log_trace(gc, freelist, stats)("size[" SIZE_FORMAT "] : ", i);


2014     fl->compute_desired(inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate);
2015     fl->set_coal_desired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent));
2016     fl->set_before_sweep(fl->count());
2017     fl->set_bfr_surp(fl->surplus());
2018   }
2019   _dictionary->begin_sweep_dict_census(CMSLargeCoalSurplusPercent,
2020                                     inter_sweep_current,
2021                                     inter_sweep_estimate,
2022                                     intra_sweep_estimate);
2023 }
2024 
2025 void CompactibleFreeListSpace::setFLSurplus() {
2026   assert_locked();
2027   size_t i;
2028   for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2029     AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2030     fl->set_surplus(fl->count() -
2031                     (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent));
2032   }
2033 }


2042     if (fl->surplus() > 0) {
2043       h = i;
2044     }
2045   }
2046 }
2047 
2048 void CompactibleFreeListSpace::clearFLCensus() {
2049   assert_locked();
2050   size_t i;
2051   for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2052     AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2053     fl->set_prev_sweep(fl->count());
2054     fl->set_coal_births(0);
2055     fl->set_coal_deaths(0);
2056     fl->set_split_births(0);
2057     fl->set_split_deaths(0);
2058   }
2059 }
2060 
2061 void CompactibleFreeListSpace::endSweepFLCensus(size_t sweep_count) {
2062   log_debug(gc, freelist, stats)("CMS: Large block " PTR_FORMAT, p2i(dictionary()->find_largest_dict()));




2063   setFLSurplus();
2064   setFLHints();

2065   printFLCensus(sweep_count);

2066   clearFLCensus();
2067   assert_locked();
2068   _dictionary->end_sweep_dict_census(CMSLargeSplitSurplusPercent);
2069 }
2070 
2071 bool CompactibleFreeListSpace::coalOverPopulated(size_t size) {
2072   if (size < SmallForDictionary) {
2073     AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2074     return (fl->coal_desired() < 0) ||
2075            ((int)fl->count() > fl->coal_desired());
2076   } else {
2077     return dictionary()->coal_dict_over_populated(size);
2078   }
2079 }
2080 
2081 void CompactibleFreeListSpace::smallCoalBirth(size_t size) {
2082   assert(size < SmallForDictionary, "Size too large for indexed list");
2083   AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2084   fl->increment_coal_births();
2085   fl->increment_surplus();


2184     bool   was_obj  = false;
2185     bool   was_live = false;
2186     if (_sp->block_is_obj(addr)) {
2187       was_obj = true;
2188       oop p = oop(addr);
2189       guarantee(p->is_oop(), "Should be an oop");
2190       res = _sp->adjustObjectSize(p->size());
2191       if (_sp->obj_is_alive(addr)) {
2192         was_live = true;
2193         p->verify();
2194       }
2195     } else {
2196       FreeChunk* fc = (FreeChunk*)addr;
2197       res = fc->size();
2198       if (FLSVerifyLists && !fc->cantCoalesce()) {
2199         guarantee(_sp->verify_chunk_in_free_list(fc),
2200                   "Chunk should be on a free list");
2201       }
2202     }
2203     if (res == 0) {
2204       LogHandle(gc, verify) log;
2205       log.info("Livelock: no rank reduction!");
2206       log.info(" Current:  addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n"
2207                " Previous: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n",
2208         p2i(addr),       res,        was_obj      ?"true":"false", was_live      ?"true":"false",
2209         p2i(_last_addr), _last_size, _last_was_obj?"true":"false", _last_was_live?"true":"false");
2210       ResourceMark rm;
2211       _sp->print_on(log.info_stream());
2212       guarantee(false, "Verification failed.");
2213     }
2214     _last_addr = addr;
2215     _last_size = res;
2216     _last_was_obj  = was_obj;
2217     _last_was_live = was_live;
2218     return res;
2219   }
2220 };
2221 
2222 class VerifyAllOopsClosure: public OopClosure {
2223  private:
2224   const CMSCollector*             _collector;
2225   const CompactibleFreeListSpace* _sp;
2226   const MemRegion                 _span;
2227   const bool                      _past_remark;
2228   const CMSBitMap*                _bit_map;
2229 
2230  protected:
2231   void do_oop(void* p, oop obj) {
2232     if (_span.contains(obj)) { // the interior oop points into CMS heap


2358     guarantee(fc->next() == NULL || fc->next()->prev() == fc, "Broken list");
2359     guarantee((fc->next() == NULL) == (fc == tail), "Incorrect tail");
2360   }
2361   guarantee(n == num, "Incorrect count");
2362 }
2363 
2364 #ifndef PRODUCT
2365 void CompactibleFreeListSpace::check_free_list_consistency() const {
2366   assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size() <= IndexSetSize),
2367     "Some sizes can't be allocated without recourse to"
2368     " linear allocation buffers");
2369   assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size()*HeapWordSize == sizeof(TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >)),
2370     "else MIN_TREE_CHUNK_SIZE is wrong");
2371   assert(IndexSetStart != 0, "IndexSetStart not initialized");
2372   assert(IndexSetStride != 0, "IndexSetStride not initialized");
2373 }
2374 #endif
2375 
2376 void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const {
2377   assert_lock_strong(&_freelistLock);
2378   LogHandle(gc, freelist, census) log;
2379   if (!log.is_debug()) {
2380     return;
2381   }
2382   AdaptiveFreeList<FreeChunk> total;
2383   log.debug("end sweep# " SIZE_FORMAT, sweep_count);
2384   ResourceMark rm;
2385   outputStream* out = log.debug_stream();
2386   AdaptiveFreeList<FreeChunk>::print_labels_on(out, "size");
2387   size_t total_free = 0;
2388   for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2389     const AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2390     total_free += fl->count() * fl->size();
2391     if (i % (40*IndexSetStride) == 0) {
2392       AdaptiveFreeList<FreeChunk>::print_labels_on(out, "size");
2393     }
2394     fl->print_on(out);
2395     total.set_bfr_surp(    total.bfr_surp()     + fl->bfr_surp()    );
2396     total.set_surplus(    total.surplus()     + fl->surplus()    );
2397     total.set_desired(    total.desired()     + fl->desired()    );
2398     total.set_prev_sweep(  total.prev_sweep()   + fl->prev_sweep()  );
2399     total.set_before_sweep(total.before_sweep() + fl->before_sweep());
2400     total.set_count(      total.count()       + fl->count()      );
2401     total.set_coal_births( total.coal_births()  + fl->coal_births() );
2402     total.set_coal_deaths( total.coal_deaths()  + fl->coal_deaths() );
2403     total.set_split_births(total.split_births() + fl->split_births());
2404     total.set_split_deaths(total.split_deaths() + fl->split_deaths());
2405   }
2406   total.print_on(out, "TOTAL");
2407   log.debug("Total free in indexed lists " SIZE_FORMAT " words", total_free);
2408   log.debug("growth: %8.5f  deficit: %8.5f",

2409             (double)(total.split_births()+total.coal_births()-total.split_deaths()-total.coal_deaths())/
2410                     (total.prev_sweep() != 0 ? (double)total.prev_sweep() : 1.0),
2411             (double)(total.desired() - total.count())/(total.desired() != 0 ? (double)total.desired() : 1.0));
2412   _dictionary->print_dict_census(out);
2413 }
2414 
2415 ///////////////////////////////////////////////////////////////////////////
2416 // CFLS_LAB
2417 ///////////////////////////////////////////////////////////////////////////
2418 
2419 #define VECTOR_257(x)                                                                                  \
2420   /* 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 */ \
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, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2428      x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,   \
2429      x }
2430 
2431 // Initialize with default setting for CMS, _not_
2432 // generic OldPLABSize, whose static default is different; if overridden at the


2521   _num_blocks[word_sz] += fl->count();
2522 }
2523 
2524 void CFLS_LAB::compute_desired_plab_size() {
2525   for (size_t i =  CompactibleFreeListSpace::IndexSetStart;
2526        i < CompactibleFreeListSpace::IndexSetSize;
2527        i += CompactibleFreeListSpace::IndexSetStride) {
2528     assert((_global_num_workers[i] == 0) == (_global_num_blocks[i] == 0),
2529            "Counter inconsistency");
2530     if (_global_num_workers[i] > 0) {
2531       // Need to smooth wrt historical average
2532       if (ResizeOldPLAB) {
2533         _blocks_to_claim[i].sample(
2534           MAX2(CMSOldPLABMin,
2535           MIN2(CMSOldPLABMax,
2536                _global_num_blocks[i]/(_global_num_workers[i]*CMSOldPLABNumRefills))));
2537       }
2538       // Reset counters for next round
2539       _global_num_workers[i] = 0;
2540       _global_num_blocks[i] = 0;
2541       log_trace(gc, plab)("[" SIZE_FORMAT "]: " SIZE_FORMAT,

2542                                i, (size_t)_blocks_to_claim[i].average());
2543     }
2544   }

2545 }
2546 
2547 // If this is changed in the future to allow parallel
2548 // access, one would need to take the FL locks and,
2549 // depending on how it is used, stagger access from
2550 // parallel threads to reduce contention.
2551 void CFLS_LAB::retire(int tid) {
2552   // We run this single threaded with the world stopped;
2553   // so no need for locks and such.
2554   NOT_PRODUCT(Thread* t = Thread::current();)
2555   assert(Thread::current()->is_VM_thread(), "Error");
2556   for (size_t i =  CompactibleFreeListSpace::IndexSetStart;
2557        i < CompactibleFreeListSpace::IndexSetSize;
2558        i += CompactibleFreeListSpace::IndexSetStride) {
2559     assert(_num_blocks[i] >= (size_t)_indexedFreeList[i].count(),
2560            "Can't retire more than what we obtained");
2561     if (_num_blocks[i] > 0) {
2562       size_t num_retire =  _indexedFreeList[i].count();
2563       assert(_num_blocks[i] > num_retire, "Should have used at least one");
2564       {
2565         // MutexLockerEx x(_cfls->_indexedFreeListParLocks[i],
2566         //                Mutex::_no_safepoint_check_flag);
2567 
2568         // Update globals stats for num_blocks used
2569         _global_num_blocks[i] += (_num_blocks[i] - num_retire);
2570         _global_num_workers[i]++;
2571         assert(_global_num_workers[i] <= ParallelGCThreads, "Too big");
2572         if (num_retire > 0) {
2573           _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]);
2574           // Reset this list.
2575           _indexedFreeList[i] = AdaptiveFreeList<FreeChunk>();
2576           _indexedFreeList[i].set_size(i);
2577         }
2578       }
2579       log_trace(gc, plab)("%d[" SIZE_FORMAT "]: " SIZE_FORMAT "/" SIZE_FORMAT "/" SIZE_FORMAT,

2580                           tid, i, num_retire, _num_blocks[i], (size_t)_blocks_to_claim[i].average());

2581       // Reset stats for next round
2582       _num_blocks[i]         = 0;
2583     }
2584   }
2585 }
2586 
2587 // Used by par_get_chunk_of_blocks() for the chunks from the
2588 // indexed_free_lists.  Looks for a chunk with size that is a multiple
2589 // of "word_sz" and if found, splits it into "word_sz" chunks and add
2590 // to the free list "fl".  "n" is the maximum number of chunks to
2591 // be added to "fl".
2592 bool CompactibleFreeListSpace:: par_get_chunk_of_blocks_IFL(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) {
2593 
2594   // We'll try all multiples of word_sz in the indexed set, starting with
2595   // word_sz itself and, if CMSSplitIndexedFreeListBlocks, try larger multiples,
2596   // then try getting a big chunk and splitting it.
2597   {
2598     bool found;
2599     int  k;
2600     size_t cur_sz;


< prev index next >