Java example source code file (compactibleFreeListSpace.cpp)
The compactibleFreeListSpace.cpp Java example source code
/*
* Copyright (c) 2001, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "gc_implementation/concurrentMarkSweep/cmsLockVerifier.hpp"
#include "gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp"
#include "gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.inline.hpp"
#include "gc_implementation/concurrentMarkSweep/concurrentMarkSweepThread.hpp"
#include "gc_implementation/shared/liveRange.hpp"
#include "gc_implementation/shared/spaceDecorator.hpp"
#include "gc_interface/collectedHeap.inline.hpp"
#include "memory/allocation.inline.hpp"
#include "memory/blockOffsetTable.inline.hpp"
#include "memory/resourceArea.hpp"
#include "memory/universe.inline.hpp"
#include "oops/oop.inline.hpp"
#include "runtime/globals.hpp"
#include "runtime/handles.inline.hpp"
#include "runtime/init.hpp"
#include "runtime/java.hpp"
#include "runtime/vmThread.hpp"
#include "utilities/copy.hpp"
/////////////////////////////////////////////////////////////////////////
//// CompactibleFreeListSpace
/////////////////////////////////////////////////////////////////////////
// highest ranked free list lock rank
int CompactibleFreeListSpace::_lockRank = Mutex::leaf + 3;
// Defaults are 0 so things will break badly if incorrectly initialized.
size_t CompactibleFreeListSpace::IndexSetStart = 0;
size_t CompactibleFreeListSpace::IndexSetStride = 0;
size_t MinChunkSize = 0;
void CompactibleFreeListSpace::set_cms_values() {
// Set CMS global values
assert(MinChunkSize == 0, "already set");
// MinChunkSize should be a multiple of MinObjAlignment and be large enough
// for chunks to contain a FreeChunk.
size_t min_chunk_size_in_bytes = align_size_up(sizeof(FreeChunk), MinObjAlignmentInBytes);
MinChunkSize = min_chunk_size_in_bytes / BytesPerWord;
assert(IndexSetStart == 0 && IndexSetStride == 0, "already set");
IndexSetStart = MinChunkSize;
IndexSetStride = MinObjAlignment;
}
// Constructor
CompactibleFreeListSpace::CompactibleFreeListSpace(BlockOffsetSharedArray* bs,
MemRegion mr, bool use_adaptive_freelists,
FreeBlockDictionary<FreeChunk>::DictionaryChoice dictionaryChoice) :
_dictionaryChoice(dictionaryChoice),
_adaptive_freelists(use_adaptive_freelists),
_bt(bs, mr),
// free list locks are in the range of values taken by _lockRank
// This range currently is [_leaf+2, _leaf+3]
// Note: this requires that CFLspace c'tors
// are called serially in the order in which the locks are
// are acquired in the program text. This is true today.
_freelistLock(_lockRank--, "CompactibleFreeListSpace._lock", true),
_parDictionaryAllocLock(Mutex::leaf - 1, // == rank(ExpandHeap_lock) - 1
"CompactibleFreeListSpace._dict_par_lock", true),
_rescan_task_size(CardTableModRefBS::card_size_in_words * BitsPerWord *
CMSRescanMultiple),
_marking_task_size(CardTableModRefBS::card_size_in_words * BitsPerWord *
CMSConcMarkMultiple),
_collector(NULL)
{
assert(sizeof(FreeChunk) / BytesPerWord <= MinChunkSize,
"FreeChunk is larger than expected");
_bt.set_space(this);
initialize(mr, SpaceDecorator::Clear, SpaceDecorator::Mangle);
// We have all of "mr", all of which we place in the dictionary
// as one big chunk. We'll need to decide here which of several
// possible alternative dictionary implementations to use. For
// now the choice is easy, since we have only one working
// implementation, namely, the simple binary tree (splaying
// temporarily disabled).
switch (dictionaryChoice) {
case FreeBlockDictionary<FreeChunk>::dictionaryBinaryTree:
_dictionary = new AFLBinaryTreeDictionary(mr);
break;
case FreeBlockDictionary<FreeChunk>::dictionarySplayTree:
case FreeBlockDictionary<FreeChunk>::dictionarySkipList:
default:
warning("dictionaryChoice: selected option not understood; using"
" default BinaryTreeDictionary implementation instead.");
}
assert(_dictionary != NULL, "CMS dictionary initialization");
// The indexed free lists are initially all empty and are lazily
// filled in on demand. Initialize the array elements to NULL.
initializeIndexedFreeListArray();
// Not using adaptive free lists assumes that allocation is first
// from the linAB's. Also a cms perm gen which can be compacted
// has to have the klass's klassKlass allocated at a lower
// address in the heap than the klass so that the klassKlass is
// moved to its new location before the klass is moved.
// Set the _refillSize for the linear allocation blocks
if (!use_adaptive_freelists) {
FreeChunk* fc = _dictionary->get_chunk(mr.word_size(),
FreeBlockDictionary<FreeChunk>::atLeast);
// The small linAB initially has all the space and will allocate
// a chunk of any size.
HeapWord* addr = (HeapWord*) fc;
_smallLinearAllocBlock.set(addr, fc->size() ,
1024*SmallForLinearAlloc, fc->size());
// Note that _unallocated_block is not updated here.
// Allocations from the linear allocation block should
// update it.
} else {
_smallLinearAllocBlock.set(0, 0, 1024*SmallForLinearAlloc,
SmallForLinearAlloc);
}
// CMSIndexedFreeListReplenish should be at least 1
CMSIndexedFreeListReplenish = MAX2((uintx)1, CMSIndexedFreeListReplenish);
_promoInfo.setSpace(this);
if (UseCMSBestFit) {
_fitStrategy = FreeBlockBestFitFirst;
} else {
_fitStrategy = FreeBlockStrategyNone;
}
check_free_list_consistency();
// Initialize locks for parallel case.
if (CollectedHeap::use_parallel_gc_threads()) {
for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
_indexedFreeListParLocks[i] = new Mutex(Mutex::leaf - 1, // == ExpandHeap_lock - 1
"a freelist par lock",
true);
DEBUG_ONLY(
_indexedFreeList[i].set_protecting_lock(_indexedFreeListParLocks[i]);
)
}
_dictionary->set_par_lock(&_parDictionaryAllocLock);
}
}
// Like CompactibleSpace forward() but always calls cross_threshold() to
// update the block offset table. Removed initialize_threshold call because
// CFLS does not use a block offset array for contiguous spaces.
HeapWord* CompactibleFreeListSpace::forward(oop q, size_t size,
CompactPoint* cp, HeapWord* compact_top) {
// q is alive
// First check if we should switch compaction space
assert(this == cp->space, "'this' should be current compaction space.");
size_t compaction_max_size = pointer_delta(end(), compact_top);
assert(adjustObjectSize(size) == cp->space->adjust_object_size_v(size),
"virtual adjustObjectSize_v() method is not correct");
size_t adjusted_size = adjustObjectSize(size);
assert(compaction_max_size >= MinChunkSize || compaction_max_size == 0,
"no small fragments allowed");
assert(minimum_free_block_size() == MinChunkSize,
"for de-virtualized reference below");
// Can't leave a nonzero size, residual fragment smaller than MinChunkSize
if (adjusted_size + MinChunkSize > compaction_max_size &&
adjusted_size != compaction_max_size) {
do {
// switch to next compaction space
cp->space->set_compaction_top(compact_top);
cp->space = cp->space->next_compaction_space();
if (cp->space == NULL) {
cp->gen = GenCollectedHeap::heap()->prev_gen(cp->gen);
assert(cp->gen != NULL, "compaction must succeed");
cp->space = cp->gen->first_compaction_space();
assert(cp->space != NULL, "generation must have a first compaction space");
}
compact_top = cp->space->bottom();
cp->space->set_compaction_top(compact_top);
// The correct adjusted_size may not be the same as that for this method
// (i.e., cp->space may no longer be "this" so adjust the size again.
// Use the virtual method which is not used above to save the virtual
// dispatch.
adjusted_size = cp->space->adjust_object_size_v(size);
compaction_max_size = pointer_delta(cp->space->end(), compact_top);
assert(cp->space->minimum_free_block_size() == 0, "just checking");
} while (adjusted_size > compaction_max_size);
}
// store the forwarding pointer into the mark word
if ((HeapWord*)q != compact_top) {
q->forward_to(oop(compact_top));
assert(q->is_gc_marked(), "encoding the pointer should preserve the mark");
} else {
// if the object isn't moving we can just set the mark to the default
// mark and handle it specially later on.
q->init_mark();
assert(q->forwardee() == NULL, "should be forwarded to NULL");
}
compact_top += adjusted_size;
// we need to update the offset table so that the beginnings of objects can be
// found during scavenge. Note that we are updating the offset table based on
// where the object will be once the compaction phase finishes.
// Always call cross_threshold(). A contiguous space can only call it when
// the compaction_top exceeds the current threshold but not for an
// non-contiguous space.
cp->threshold =
cp->space->cross_threshold(compact_top - adjusted_size, compact_top);
return compact_top;
}
// A modified copy of OffsetTableContigSpace::cross_threshold() with _offsets -> _bt
// and use of single_block instead of alloc_block. The name here is not really
// appropriate - maybe a more general name could be invented for both the
// contiguous and noncontiguous spaces.
HeapWord* CompactibleFreeListSpace::cross_threshold(HeapWord* start, HeapWord* the_end) {
_bt.single_block(start, the_end);
return end();
}
// Initialize them to NULL.
void CompactibleFreeListSpace::initializeIndexedFreeListArray() {
for (size_t i = 0; i < IndexSetSize; i++) {
// Note that on platforms where objects are double word aligned,
// the odd array elements are not used. It is convenient, however,
// to map directly from the object size to the array element.
_indexedFreeList[i].reset(IndexSetSize);
_indexedFreeList[i].set_size(i);
assert(_indexedFreeList[i].count() == 0, "reset check failed");
assert(_indexedFreeList[i].head() == NULL, "reset check failed");
assert(_indexedFreeList[i].tail() == NULL, "reset check failed");
assert(_indexedFreeList[i].hint() == IndexSetSize, "reset check failed");
}
}
void CompactibleFreeListSpace::resetIndexedFreeListArray() {
for (size_t i = 1; i < IndexSetSize; i++) {
assert(_indexedFreeList[i].size() == (size_t) i,
"Indexed free list sizes are incorrect");
_indexedFreeList[i].reset(IndexSetSize);
assert(_indexedFreeList[i].count() == 0, "reset check failed");
assert(_indexedFreeList[i].head() == NULL, "reset check failed");
assert(_indexedFreeList[i].tail() == NULL, "reset check failed");
assert(_indexedFreeList[i].hint() == IndexSetSize, "reset check failed");
}
}
void CompactibleFreeListSpace::reset(MemRegion mr) {
resetIndexedFreeListArray();
dictionary()->reset();
if (BlockOffsetArrayUseUnallocatedBlock) {
assert(end() == mr.end(), "We are compacting to the bottom of CMS gen");
// Everything's allocated until proven otherwise.
_bt.set_unallocated_block(end());
}
if (!mr.is_empty()) {
assert(mr.word_size() >= MinChunkSize, "Chunk size is too small");
_bt.single_block(mr.start(), mr.word_size());
FreeChunk* fc = (FreeChunk*) mr.start();
fc->set_size(mr.word_size());
if (mr.word_size() >= IndexSetSize ) {
returnChunkToDictionary(fc);
} else {
_bt.verify_not_unallocated((HeapWord*)fc, fc->size());
_indexedFreeList[mr.word_size()].return_chunk_at_head(fc);
}
coalBirth(mr.word_size());
}
_promoInfo.reset();
_smallLinearAllocBlock._ptr = NULL;
_smallLinearAllocBlock._word_size = 0;
}
void CompactibleFreeListSpace::reset_after_compaction() {
// Reset the space to the new reality - one free chunk.
MemRegion mr(compaction_top(), end());
reset(mr);
// Now refill the linear allocation block(s) if possible.
if (_adaptive_freelists) {
refillLinearAllocBlocksIfNeeded();
} else {
// Place as much of mr in the linAB as we can get,
// provided it was big enough to go into the dictionary.
FreeChunk* fc = dictionary()->find_largest_dict();
if (fc != NULL) {
assert(fc->size() == mr.word_size(),
"Why was the chunk broken up?");
removeChunkFromDictionary(fc);
HeapWord* addr = (HeapWord*) fc;
_smallLinearAllocBlock.set(addr, fc->size() ,
1024*SmallForLinearAlloc, fc->size());
// Note that _unallocated_block is not updated here.
}
}
}
// Walks the entire dictionary, returning a coterminal
// chunk, if it exists. Use with caution since it involves
// a potentially complete walk of a potentially large tree.
FreeChunk* CompactibleFreeListSpace::find_chunk_at_end() {
assert_lock_strong(&_freelistLock);
return dictionary()->find_chunk_ends_at(end());
}
#ifndef PRODUCT
void CompactibleFreeListSpace::initializeIndexedFreeListArrayReturnedBytes() {
for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
_indexedFreeList[i].allocation_stats()->set_returned_bytes(0);
}
}
size_t CompactibleFreeListSpace::sumIndexedFreeListArrayReturnedBytes() {
size_t sum = 0;
for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
sum += _indexedFreeList[i].allocation_stats()->returned_bytes();
}
return sum;
}
size_t CompactibleFreeListSpace::totalCountInIndexedFreeLists() const {
size_t count = 0;
for (size_t i = IndexSetStart; i < IndexSetSize; i++) {
debug_only(
ssize_t total_list_count = 0;
for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
fc = fc->next()) {
total_list_count++;
}
assert(total_list_count == _indexedFreeList[i].count(),
"Count in list is incorrect");
)
count += _indexedFreeList[i].count();
}
return count;
}
size_t CompactibleFreeListSpace::totalCount() {
size_t num = totalCountInIndexedFreeLists();
num += dictionary()->total_count();
if (_smallLinearAllocBlock._word_size != 0) {
num++;
}
return num;
}
#endif
bool CompactibleFreeListSpace::is_free_block(const HeapWord* p) const {
FreeChunk* fc = (FreeChunk*) p;
return fc->is_free();
}
size_t CompactibleFreeListSpace::used() const {
return capacity() - free();
}
size_t CompactibleFreeListSpace::free() const {
// "MT-safe, but not MT-precise"(TM), if you will: i.e.
// if you do this while the structures are in flux you
// may get an approximate answer only; for instance
// because there is concurrent allocation either
// directly by mutators or for promotion during a GC.
// It's "MT-safe", however, in the sense that you are guaranteed
// not to crash and burn, for instance, because of walking
// pointers that could disappear as you were walking them.
// The approximation is because the various components
// that are read below are not read atomically (and
// further the computation of totalSizeInIndexedFreeLists()
// is itself a non-atomic computation. The normal use of
// this is during a resize operation at the end of GC
// and at that time you are guaranteed to get the
// correct actual value. However, for instance, this is
// also read completely asynchronously by the "perf-sampler"
// that supports jvmstat, and you are apt to see the values
// flicker in such cases.
assert(_dictionary != NULL, "No _dictionary?");
return (_dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())) +
totalSizeInIndexedFreeLists() +
_smallLinearAllocBlock._word_size) * HeapWordSize;
}
size_t CompactibleFreeListSpace::max_alloc_in_words() const {
assert(_dictionary != NULL, "No _dictionary?");
assert_locked();
size_t res = _dictionary->max_chunk_size();
res = MAX2(res, MIN2(_smallLinearAllocBlock._word_size,
(size_t) SmallForLinearAlloc - 1));
// XXX the following could potentially be pretty slow;
// should one, pesimally for the rare cases when res
// caclulated above is less than IndexSetSize,
// just return res calculated above? My reasoning was that
// those cases will be so rare that the extra time spent doesn't
// really matter....
// Note: do not change the loop test i >= res + IndexSetStride
// to i > res below, because i is unsigned and res may be zero.
for (size_t i = IndexSetSize - 1; i >= res + IndexSetStride;
i -= IndexSetStride) {
if (_indexedFreeList[i].head() != NULL) {
assert(_indexedFreeList[i].count() != 0, "Inconsistent FreeList");
return i;
}
}
return res;
}
void LinearAllocBlock::print_on(outputStream* st) const {
st->print_cr(" LinearAllocBlock: ptr = " PTR_FORMAT ", word_size = " SIZE_FORMAT
", refillsize = " SIZE_FORMAT ", allocation_size_limit = " SIZE_FORMAT,
_ptr, _word_size, _refillSize, _allocation_size_limit);
}
void CompactibleFreeListSpace::print_on(outputStream* st) const {
st->print_cr("COMPACTIBLE FREELIST SPACE");
st->print_cr(" Space:");
Space::print_on(st);
st->print_cr("promoInfo:");
_promoInfo.print_on(st);
st->print_cr("_smallLinearAllocBlock");
_smallLinearAllocBlock.print_on(st);
// dump_memory_block(_smallLinearAllocBlock->_ptr, 128);
st->print_cr(" _fitStrategy = %s, _adaptive_freelists = %s",
_fitStrategy?"true":"false", _adaptive_freelists?"true":"false");
}
void CompactibleFreeListSpace::print_indexed_free_lists(outputStream* st)
const {
reportIndexedFreeListStatistics();
gclog_or_tty->print_cr("Layout of Indexed Freelists");
gclog_or_tty->print_cr("---------------------------");
AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size");
for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
_indexedFreeList[i].print_on(gclog_or_tty);
for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
fc = fc->next()) {
gclog_or_tty->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s",
fc, (HeapWord*)fc + i,
fc->cantCoalesce() ? "\t CC" : "");
}
}
}
void CompactibleFreeListSpace::print_promo_info_blocks(outputStream* st)
const {
_promoInfo.print_on(st);
}
void CompactibleFreeListSpace::print_dictionary_free_lists(outputStream* st)
const {
_dictionary->report_statistics();
st->print_cr("Layout of Freelists in Tree");
st->print_cr("---------------------------");
_dictionary->print_free_lists(st);
}
class BlkPrintingClosure: public BlkClosure {
const CMSCollector* _collector;
const CompactibleFreeListSpace* _sp;
const CMSBitMap* _live_bit_map;
const bool _post_remark;
outputStream* _st;
public:
BlkPrintingClosure(const CMSCollector* collector,
const CompactibleFreeListSpace* sp,
const CMSBitMap* live_bit_map,
outputStream* st):
_collector(collector),
_sp(sp),
_live_bit_map(live_bit_map),
_post_remark(collector->abstract_state() > CMSCollector::FinalMarking),
_st(st) { }
size_t do_blk(HeapWord* addr);
};
size_t BlkPrintingClosure::do_blk(HeapWord* addr) {
size_t sz = _sp->block_size_no_stall(addr, _collector);
assert(sz != 0, "Should always be able to compute a size");
if (_sp->block_is_obj(addr)) {
const bool dead = _post_remark && !_live_bit_map->isMarked(addr);
_st->print_cr(PTR_FORMAT ": %s object of size " SIZE_FORMAT "%s",
addr,
dead ? "dead" : "live",
sz,
(!dead && CMSPrintObjectsInDump) ? ":" : ".");
if (CMSPrintObjectsInDump && !dead) {
oop(addr)->print_on(_st);
_st->print_cr("--------------------------------------");
}
} else { // free block
_st->print_cr(PTR_FORMAT ": free block of size " SIZE_FORMAT "%s",
addr, sz, CMSPrintChunksInDump ? ":" : ".");
if (CMSPrintChunksInDump) {
((FreeChunk*)addr)->print_on(_st);
_st->print_cr("--------------------------------------");
}
}
return sz;
}
void CompactibleFreeListSpace::dump_at_safepoint_with_locks(CMSCollector* c,
outputStream* st) {
st->print_cr("\n=========================");
st->print_cr("Block layout in CMS Heap:");
st->print_cr("=========================");
BlkPrintingClosure bpcl(c, this, c->markBitMap(), st);
blk_iterate(&bpcl);
st->print_cr("\n=======================================");
st->print_cr("Order & Layout of Promotion Info Blocks");
st->print_cr("=======================================");
print_promo_info_blocks(st);
st->print_cr("\n===========================");
st->print_cr("Order of Indexed Free Lists");
st->print_cr("=========================");
print_indexed_free_lists(st);
st->print_cr("\n=================================");
st->print_cr("Order of Free Lists in Dictionary");
st->print_cr("=================================");
print_dictionary_free_lists(st);
}
void CompactibleFreeListSpace::reportFreeListStatistics() const {
assert_lock_strong(&_freelistLock);
assert(PrintFLSStatistics != 0, "Reporting error");
_dictionary->report_statistics();
if (PrintFLSStatistics > 1) {
reportIndexedFreeListStatistics();
size_t total_size = totalSizeInIndexedFreeLists() +
_dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
gclog_or_tty->print(" free=" SIZE_FORMAT " frag=%1.4f\n", total_size, flsFrag());
}
}
void CompactibleFreeListSpace::reportIndexedFreeListStatistics() const {
assert_lock_strong(&_freelistLock);
gclog_or_tty->print("Statistics for IndexedFreeLists:\n"
"--------------------------------\n");
size_t total_size = totalSizeInIndexedFreeLists();
size_t free_blocks = numFreeBlocksInIndexedFreeLists();
gclog_or_tty->print("Total Free Space: %d\n", total_size);
gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSizeInIndexedFreeLists());
gclog_or_tty->print("Number of Blocks: %d\n", free_blocks);
if (free_blocks != 0) {
gclog_or_tty->print("Av. Block Size: %d\n", total_size/free_blocks);
}
}
size_t CompactibleFreeListSpace::numFreeBlocksInIndexedFreeLists() const {
size_t res = 0;
for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
debug_only(
ssize_t recount = 0;
for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
fc = fc->next()) {
recount += 1;
}
assert(recount == _indexedFreeList[i].count(),
"Incorrect count in list");
)
res += _indexedFreeList[i].count();
}
return res;
}
size_t CompactibleFreeListSpace::maxChunkSizeInIndexedFreeLists() const {
for (size_t i = IndexSetSize - 1; i != 0; i -= IndexSetStride) {
if (_indexedFreeList[i].head() != NULL) {
assert(_indexedFreeList[i].count() != 0, "Inconsistent FreeList");
return (size_t)i;
}
}
return 0;
}
void CompactibleFreeListSpace::set_end(HeapWord* value) {
HeapWord* prevEnd = end();
assert(prevEnd != value, "unnecessary set_end call");
assert(prevEnd == NULL || !BlockOffsetArrayUseUnallocatedBlock || value >= unallocated_block(),
"New end is below unallocated block");
_end = value;
if (prevEnd != NULL) {
// Resize the underlying block offset table.
_bt.resize(pointer_delta(value, bottom()));
if (value <= prevEnd) {
assert(!BlockOffsetArrayUseUnallocatedBlock || value >= unallocated_block(),
"New end is below unallocated block");
} else {
// Now, take this new chunk and add it to the free blocks.
// Note that the BOT has not yet been updated for this block.
size_t newFcSize = pointer_delta(value, prevEnd);
// XXX This is REALLY UGLY and should be fixed up. XXX
if (!_adaptive_freelists && _smallLinearAllocBlock._ptr == NULL) {
// Mark the boundary of the new block in BOT
_bt.mark_block(prevEnd, value);
// put it all in the linAB
if (ParallelGCThreads == 0) {
_smallLinearAllocBlock._ptr = prevEnd;
_smallLinearAllocBlock._word_size = newFcSize;
repairLinearAllocBlock(&_smallLinearAllocBlock);
} else { // ParallelGCThreads > 0
MutexLockerEx x(parDictionaryAllocLock(),
Mutex::_no_safepoint_check_flag);
_smallLinearAllocBlock._ptr = prevEnd;
_smallLinearAllocBlock._word_size = newFcSize;
repairLinearAllocBlock(&_smallLinearAllocBlock);
}
// Births of chunks put into a LinAB are not recorded. Births
// of chunks as they are allocated out of a LinAB are.
} else {
// Add the block to the free lists, if possible coalescing it
// with the last free block, and update the BOT and census data.
addChunkToFreeListsAtEndRecordingStats(prevEnd, newFcSize);
}
}
}
}
class FreeListSpace_DCTOC : public Filtering_DCTOC {
CompactibleFreeListSpace* _cfls;
CMSCollector* _collector;
protected:
// Override.
#define walk_mem_region_with_cl_DECL(ClosureType) \
virtual void walk_mem_region_with_cl(MemRegion mr, \
HeapWord* bottom, HeapWord* top, \
ClosureType* cl); \
void walk_mem_region_with_cl_par(MemRegion mr, \
HeapWord* bottom, HeapWord* top, \
ClosureType* cl); \
void walk_mem_region_with_cl_nopar(MemRegion mr, \
HeapWord* bottom, HeapWord* top, \
ClosureType* cl)
walk_mem_region_with_cl_DECL(ExtendedOopClosure);
walk_mem_region_with_cl_DECL(FilteringClosure);
public:
FreeListSpace_DCTOC(CompactibleFreeListSpace* sp,
CMSCollector* collector,
ExtendedOopClosure* cl,
CardTableModRefBS::PrecisionStyle precision,
HeapWord* boundary) :
Filtering_DCTOC(sp, cl, precision, boundary),
_cfls(sp), _collector(collector) {}
};
// We de-virtualize the block-related calls below, since we know that our
// space is a CompactibleFreeListSpace.
#define FreeListSpace_DCTOC__walk_mem_region_with_cl_DEFN(ClosureType) \
void FreeListSpace_DCTOC::walk_mem_region_with_cl(MemRegion mr, \
HeapWord* bottom, \
HeapWord* top, \
ClosureType* cl) { \
bool is_par = SharedHeap::heap()->n_par_threads() > 0; \
if (is_par) { \
assert(SharedHeap::heap()->n_par_threads() == \
SharedHeap::heap()->workers()->active_workers(), "Mismatch"); \
walk_mem_region_with_cl_par(mr, bottom, top, cl); \
} else { \
walk_mem_region_with_cl_nopar(mr, bottom, top, cl); \
} \
} \
void FreeListSpace_DCTOC::walk_mem_region_with_cl_par(MemRegion mr, \
HeapWord* bottom, \
HeapWord* top, \
ClosureType* cl) { \
/* Skip parts that are before "mr", in case "block_start" sent us \
back too far. */ \
HeapWord* mr_start = mr.start(); \
size_t bot_size = _cfls->CompactibleFreeListSpace::block_size(bottom); \
HeapWord* next = bottom + bot_size; \
while (next < mr_start) { \
bottom = next; \
bot_size = _cfls->CompactibleFreeListSpace::block_size(bottom); \
next = bottom + bot_size; \
} \
\
while (bottom < top) { \
if (_cfls->CompactibleFreeListSpace::block_is_obj(bottom) && \
!_cfls->CompactibleFreeListSpace::obj_allocated_since_save_marks( \
oop(bottom)) && \
!_collector->CMSCollector::is_dead_obj(oop(bottom))) { \
size_t word_sz = oop(bottom)->oop_iterate(cl, mr); \
bottom += _cfls->adjustObjectSize(word_sz); \
} else { \
bottom += _cfls->CompactibleFreeListSpace::block_size(bottom); \
} \
} \
} \
void FreeListSpace_DCTOC::walk_mem_region_with_cl_nopar(MemRegion mr, \
HeapWord* bottom, \
HeapWord* top, \
ClosureType* cl) { \
/* Skip parts that are before "mr", in case "block_start" sent us \
back too far. */ \
HeapWord* mr_start = mr.start(); \
size_t bot_size = _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \
HeapWord* next = bottom + bot_size; \
while (next < mr_start) { \
bottom = next; \
bot_size = _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \
next = bottom + bot_size; \
} \
\
while (bottom < top) { \
if (_cfls->CompactibleFreeListSpace::block_is_obj_nopar(bottom) && \
!_cfls->CompactibleFreeListSpace::obj_allocated_since_save_marks( \
oop(bottom)) && \
!_collector->CMSCollector::is_dead_obj(oop(bottom))) { \
size_t word_sz = oop(bottom)->oop_iterate(cl, mr); \
bottom += _cfls->adjustObjectSize(word_sz); \
} else { \
bottom += _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \
} \
} \
}
// (There are only two of these, rather than N, because the split is due
// only to the introduction of the FilteringClosure, a local part of the
// impl of this abstraction.)
FreeListSpace_DCTOC__walk_mem_region_with_cl_DEFN(ExtendedOopClosure)
FreeListSpace_DCTOC__walk_mem_region_with_cl_DEFN(FilteringClosure)
DirtyCardToOopClosure*
CompactibleFreeListSpace::new_dcto_cl(ExtendedOopClosure* cl,
CardTableModRefBS::PrecisionStyle precision,
HeapWord* boundary) {
return new FreeListSpace_DCTOC(this, _collector, cl, precision, boundary);
}
// Note on locking for the space iteration functions:
// since the collector's iteration activities are concurrent with
// allocation activities by mutators, absent a suitable mutual exclusion
// mechanism the iterators may go awry. For instace a block being iterated
// may suddenly be allocated or divided up and part of it allocated and
// so on.
// Apply the given closure to each block in the space.
void CompactibleFreeListSpace::blk_iterate_careful(BlkClosureCareful* cl) {
assert_lock_strong(freelistLock());
HeapWord *cur, *limit;
for (cur = bottom(), limit = end(); cur < limit;
cur += cl->do_blk_careful(cur));
}
// Apply the given closure to each block in the space.
void CompactibleFreeListSpace::blk_iterate(BlkClosure* cl) {
assert_lock_strong(freelistLock());
HeapWord *cur, *limit;
for (cur = bottom(), limit = end(); cur < limit;
cur += cl->do_blk(cur));
}
// Apply the given closure to each oop in the space.
void CompactibleFreeListSpace::oop_iterate(ExtendedOopClosure* cl) {
assert_lock_strong(freelistLock());
HeapWord *cur, *limit;
size_t curSize;
for (cur = bottom(), limit = end(); cur < limit;
cur += curSize) {
curSize = block_size(cur);
if (block_is_obj(cur)) {
oop(cur)->oop_iterate(cl);
}
}
}
// Apply the given closure to each oop in the space \intersect memory region.
void CompactibleFreeListSpace::oop_iterate(MemRegion mr, ExtendedOopClosure* cl) {
assert_lock_strong(freelistLock());
if (is_empty()) {
return;
}
MemRegion cur = MemRegion(bottom(), end());
mr = mr.intersection(cur);
if (mr.is_empty()) {
return;
}
if (mr.equals(cur)) {
oop_iterate(cl);
return;
}
assert(mr.end() <= end(), "just took an intersection above");
HeapWord* obj_addr = block_start(mr.start());
HeapWord* t = mr.end();
SpaceMemRegionOopsIterClosure smr_blk(cl, mr);
if (block_is_obj(obj_addr)) {
// Handle first object specially.
oop obj = oop(obj_addr);
obj_addr += adjustObjectSize(obj->oop_iterate(&smr_blk));
} else {
FreeChunk* fc = (FreeChunk*)obj_addr;
obj_addr += fc->size();
}
while (obj_addr < t) {
HeapWord* obj = obj_addr;
obj_addr += block_size(obj_addr);
// If "obj_addr" is not greater than top, then the
// entire object "obj" is within the region.
if (obj_addr <= t) {
if (block_is_obj(obj)) {
oop(obj)->oop_iterate(cl);
}
} else {
// "obj" extends beyond end of region
if (block_is_obj(obj)) {
oop(obj)->oop_iterate(&smr_blk);
}
break;
}
}
}
// NOTE: In the following methods, in order to safely be able to
// apply the closure to an object, we need to be sure that the
// object has been initialized. We are guaranteed that an object
// is initialized if we are holding the Heap_lock with the
// world stopped.
void CompactibleFreeListSpace::verify_objects_initialized() const {
if (is_init_completed()) {
assert_locked_or_safepoint(Heap_lock);
if (Universe::is_fully_initialized()) {
guarantee(SafepointSynchronize::is_at_safepoint(),
"Required for objects to be initialized");
}
} // else make a concession at vm start-up
}
// Apply the given closure to each object in the space
void CompactibleFreeListSpace::object_iterate(ObjectClosure* blk) {
assert_lock_strong(freelistLock());
NOT_PRODUCT(verify_objects_initialized());
HeapWord *cur, *limit;
size_t curSize;
for (cur = bottom(), limit = end(); cur < limit;
cur += curSize) {
curSize = block_size(cur);
if (block_is_obj(cur)) {
blk->do_object(oop(cur));
}
}
}
// Apply the given closure to each live object in the space
// The usage of CompactibleFreeListSpace
// by the ConcurrentMarkSweepGeneration for concurrent GC's allows
// objects in the space with references to objects that are no longer
// valid. For example, an object may reference another object
// that has already been sweep up (collected). This method uses
// obj_is_alive() to determine whether it is safe to apply the closure to
// an object. See obj_is_alive() for details on how liveness of an
// object is decided.
void CompactibleFreeListSpace::safe_object_iterate(ObjectClosure* blk) {
assert_lock_strong(freelistLock());
NOT_PRODUCT(verify_objects_initialized());
HeapWord *cur, *limit;
size_t curSize;
for (cur = bottom(), limit = end(); cur < limit;
cur += curSize) {
curSize = block_size(cur);
if (block_is_obj(cur) && obj_is_alive(cur)) {
blk->do_object(oop(cur));
}
}
}
void CompactibleFreeListSpace::object_iterate_mem(MemRegion mr,
UpwardsObjectClosure* cl) {
assert_locked(freelistLock());
NOT_PRODUCT(verify_objects_initialized());
Space::object_iterate_mem(mr, cl);
}
// Callers of this iterator beware: The closure application should
// be robust in the face of uninitialized objects and should (always)
// return a correct size so that the next addr + size below gives us a
// valid block boundary. [See for instance,
// ScanMarkedObjectsAgainCarefullyClosure::do_object_careful()
// in ConcurrentMarkSweepGeneration.cpp.]
HeapWord*
CompactibleFreeListSpace::object_iterate_careful(ObjectClosureCareful* cl) {
assert_lock_strong(freelistLock());
HeapWord *addr, *last;
size_t size;
for (addr = bottom(), last = end();
addr < last; addr += size) {
FreeChunk* fc = (FreeChunk*)addr;
if (fc->is_free()) {
// Since we hold the free list lock, which protects direct
// allocation in this generation by mutators, a free object
// will remain free throughout this iteration code.
size = fc->size();
} else {
// Note that the object need not necessarily be initialized,
// because (for instance) the free list lock does NOT protect
// object initialization. The closure application below must
// therefore be correct in the face of uninitialized objects.
size = cl->do_object_careful(oop(addr));
if (size == 0) {
// An unparsable object found. Signal early termination.
return addr;
}
}
}
return NULL;
}
// Callers of this iterator beware: The closure application should
// be robust in the face of uninitialized objects and should (always)
// return a correct size so that the next addr + size below gives us a
// valid block boundary. [See for instance,
// ScanMarkedObjectsAgainCarefullyClosure::do_object_careful()
// in ConcurrentMarkSweepGeneration.cpp.]
HeapWord*
CompactibleFreeListSpace::object_iterate_careful_m(MemRegion mr,
ObjectClosureCareful* cl) {
assert_lock_strong(freelistLock());
// Can't use used_region() below because it may not necessarily
// be the same as [bottom(),end()); although we could
// use [used_region().start(),round_to(used_region().end(),CardSize)),
// that appears too cumbersome, so we just do the simpler check
// in the assertion below.
assert(!mr.is_empty() && MemRegion(bottom(),end()).contains(mr),
"mr should be non-empty and within used space");
HeapWord *addr, *end;
size_t size;
for (addr = block_start_careful(mr.start()), end = mr.end();
addr < end; addr += size) {
FreeChunk* fc = (FreeChunk*)addr;
if (fc->is_free()) {
// Since we hold the free list lock, which protects direct
// allocation in this generation by mutators, a free object
// will remain free throughout this iteration code.
size = fc->size();
} else {
// Note that the object need not necessarily be initialized,
// because (for instance) the free list lock does NOT protect
// object initialization. The closure application below must
// therefore be correct in the face of uninitialized objects.
size = cl->do_object_careful_m(oop(addr), mr);
if (size == 0) {
// An unparsable object found. Signal early termination.
return addr;
}
}
}
return NULL;
}
HeapWord* CompactibleFreeListSpace::block_start_const(const void* p) const {
NOT_PRODUCT(verify_objects_initialized());
return _bt.block_start(p);
}
HeapWord* CompactibleFreeListSpace::block_start_careful(const void* p) const {
return _bt.block_start_careful(p);
}
size_t CompactibleFreeListSpace::block_size(const HeapWord* p) const {
NOT_PRODUCT(verify_objects_initialized());
// This must be volatile, or else there is a danger that the compiler
// will compile the code below into a sometimes-infinite loop, by keeping
// the value read the first time in a register.
while (true) {
// We must do this until we get a consistent view of the object.
if (FreeChunk::indicatesFreeChunk(p)) {
volatile FreeChunk* fc = (volatile FreeChunk*)p;
size_t res = fc->size();
// If the object is still a free chunk, return the size, else it
// has been allocated so try again.
if (FreeChunk::indicatesFreeChunk(p)) {
assert(res != 0, "Block size should not be 0");
return res;
}
} else {
// must read from what 'p' points to in each loop.
Klass* k = ((volatile oopDesc*)p)->klass_or_null();
if (k != NULL) {
assert(k->is_klass(), "Should really be klass oop.");
oop o = (oop)p;
assert(o->is_oop(true /* ignore mark word */), "Should be an oop.");
size_t res = o->size_given_klass(k);
res = adjustObjectSize(res);
assert(res != 0, "Block size should not be 0");
return res;
}
}
}
}
// TODO: Now that is_parsable is gone, we should combine these two functions.
// A variant of the above that uses the Printezis bits for
// unparsable but allocated objects. This avoids any possible
// stalls waiting for mutators to initialize objects, and is
// thus potentially faster than the variant above. However,
// this variant may return a zero size for a block that is
// under mutation and for which a consistent size cannot be
// inferred without stalling; see CMSCollector::block_size_if_printezis_bits().
size_t CompactibleFreeListSpace::block_size_no_stall(HeapWord* p,
const CMSCollector* c)
const {
assert(MemRegion(bottom(), end()).contains(p), "p not in space");
// This must be volatile, or else there is a danger that the compiler
// will compile the code below into a sometimes-infinite loop, by keeping
// the value read the first time in a register.
DEBUG_ONLY(uint loops = 0;)
while (true) {
// We must do this until we get a consistent view of the object.
if (FreeChunk::indicatesFreeChunk(p)) {
volatile FreeChunk* fc = (volatile FreeChunk*)p;
size_t res = fc->size();
if (FreeChunk::indicatesFreeChunk(p)) {
assert(res != 0, "Block size should not be 0");
assert(loops == 0, "Should be 0");
return res;
}
} else {
// must read from what 'p' points to in each loop.
Klass* k = ((volatile oopDesc*)p)->klass_or_null();
// We trust the size of any object that has a non-NULL
// klass and (for those in the perm gen) is parsable
// -- irrespective of its conc_safe-ty.
if (k != NULL) {
assert(k->is_klass(), "Should really be klass oop.");
oop o = (oop)p;
assert(o->is_oop(), "Should be an oop");
size_t res = o->size_given_klass(k);
res = adjustObjectSize(res);
assert(res != 0, "Block size should not be 0");
return res;
} else {
// May return 0 if P-bits not present.
return c->block_size_if_printezis_bits(p);
}
}
assert(loops == 0, "Can loop at most once");
DEBUG_ONLY(loops++;)
}
}
size_t CompactibleFreeListSpace::block_size_nopar(const HeapWord* p) const {
NOT_PRODUCT(verify_objects_initialized());
assert(MemRegion(bottom(), end()).contains(p), "p not in space");
FreeChunk* fc = (FreeChunk*)p;
if (fc->is_free()) {
return fc->size();
} else {
// Ignore mark word because this may be a recently promoted
// object whose mark word is used to chain together grey
// objects (the last one would have a null value).
assert(oop(p)->is_oop(true), "Should be an oop");
return adjustObjectSize(oop(p)->size());
}
}
// This implementation assumes that the property of "being an object" is
// stable. But being a free chunk may not be (because of parallel
// promotion.)
bool CompactibleFreeListSpace::block_is_obj(const HeapWord* p) const {
FreeChunk* fc = (FreeChunk*)p;
assert(is_in_reserved(p), "Should be in space");
// When doing a mark-sweep-compact of the CMS generation, this
// assertion may fail because prepare_for_compaction() uses
// space that is garbage to maintain information on ranges of
// live objects so that these live ranges can be moved as a whole.
// Comment out this assertion until that problem can be solved
// (i.e., that the block start calculation may look at objects
// at address below "p" in finding the object that contains "p"
// and those objects (if garbage) may have been modified to hold
// live range information.
// assert(CollectedHeap::use_parallel_gc_threads() || _bt.block_start(p) == p,
// "Should be a block boundary");
if (FreeChunk::indicatesFreeChunk(p)) return false;
Klass* k = oop(p)->klass_or_null();
if (k != NULL) {
// Ignore mark word because it may have been used to
// chain together promoted objects (the last one
// would have a null value).
assert(oop(p)->is_oop(true), "Should be an oop");
return true;
} else {
return false; // Was not an object at the start of collection.
}
}
// Check if the object is alive. This fact is checked either by consulting
// the main marking bitmap in the sweeping phase or, if it's a permanent
// generation and we're not in the sweeping phase, by checking the
// perm_gen_verify_bit_map where we store the "deadness" information if
// we did not sweep the perm gen in the most recent previous GC cycle.
bool CompactibleFreeListSpace::obj_is_alive(const HeapWord* p) const {
assert(SafepointSynchronize::is_at_safepoint() || !is_init_completed(),
"Else races are possible");
assert(block_is_obj(p), "The address should point to an object");
// If we're sweeping, we use object liveness information from the main bit map
// for both perm gen and old gen.
// We don't need to lock the bitmap (live_map or dead_map below), because
// EITHER we are in the middle of the sweeping phase, and the
// main marking bit map (live_map below) is locked,
// OR we're in other phases and perm_gen_verify_bit_map (dead_map below)
// is stable, because it's mutated only in the sweeping phase.
// NOTE: This method is also used by jmap where, if class unloading is
// off, the results can return "false" for legitimate perm objects,
// when we are not in the midst of a sweeping phase, which can result
// in jmap not reporting certain perm gen objects. This will be moot
// if/when the perm gen goes away in the future.
if (_collector->abstract_state() == CMSCollector::Sweeping) {
CMSBitMap* live_map = _collector->markBitMap();
return live_map->par_isMarked((HeapWord*) p);
}
return true;
}
bool CompactibleFreeListSpace::block_is_obj_nopar(const HeapWord* p) const {
FreeChunk* fc = (FreeChunk*)p;
assert(is_in_reserved(p), "Should be in space");
assert(_bt.block_start(p) == p, "Should be a block boundary");
if (!fc->is_free()) {
// Ignore mark word because it may have been used to
// chain together promoted objects (the last one
// would have a null value).
assert(oop(p)->is_oop(true), "Should be an oop");
return true;
}
return false;
}
// "MT-safe but not guaranteed MT-precise" (TM); you may get an
// approximate answer if you don't hold the freelistlock when you call this.
size_t CompactibleFreeListSpace::totalSizeInIndexedFreeLists() const {
size_t size = 0;
for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
debug_only(
// We may be calling here without the lock in which case we
// won't do this modest sanity check.
if (freelistLock()->owned_by_self()) {
size_t total_list_size = 0;
for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
fc = fc->next()) {
total_list_size += i;
}
assert(total_list_size == i * _indexedFreeList[i].count(),
"Count in list is incorrect");
}
)
size += i * _indexedFreeList[i].count();
}
return size;
}
HeapWord* CompactibleFreeListSpace::par_allocate(size_t size) {
MutexLockerEx x(freelistLock(), Mutex::_no_safepoint_check_flag);
return allocate(size);
}
HeapWord*
CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlockRemainder(size_t size) {
return getChunkFromLinearAllocBlockRemainder(&_smallLinearAllocBlock, size);
}
HeapWord* CompactibleFreeListSpace::allocate(size_t size) {
assert_lock_strong(freelistLock());
HeapWord* res = NULL;
assert(size == adjustObjectSize(size),
"use adjustObjectSize() before calling into allocate()");
if (_adaptive_freelists) {
res = allocate_adaptive_freelists(size);
} else { // non-adaptive free lists
res = allocate_non_adaptive_freelists(size);
}
if (res != NULL) {
// check that res does lie in this space!
assert(is_in_reserved(res), "Not in this space!");
assert(is_aligned((void*)res), "alignment check");
FreeChunk* fc = (FreeChunk*)res;
fc->markNotFree();
assert(!fc->is_free(), "shouldn't be marked free");
assert(oop(fc)->klass_or_null() == NULL, "should look uninitialized");
// Verify that the block offset table shows this to
// be a single block, but not one which is unallocated.
_bt.verify_single_block(res, size);
_bt.verify_not_unallocated(res, size);
// mangle a just allocated object with a distinct pattern.
debug_only(fc->mangleAllocated(size));
}
return res;
}
HeapWord* CompactibleFreeListSpace::allocate_non_adaptive_freelists(size_t size) {
HeapWord* res = NULL;
// try and use linear allocation for smaller blocks
if (size < _smallLinearAllocBlock._allocation_size_limit) {
// if successful, the following also adjusts block offset table
res = getChunkFromSmallLinearAllocBlock(size);
}
// Else triage to indexed lists for smaller sizes
if (res == NULL) {
if (size < SmallForDictionary) {
res = (HeapWord*) getChunkFromIndexedFreeList(size);
} else {
// else get it from the big dictionary; if even this doesn't
// work we are out of luck.
res = (HeapWord*)getChunkFromDictionaryExact(size);
}
}
return res;
}
HeapWord* CompactibleFreeListSpace::allocate_adaptive_freelists(size_t size) {
assert_lock_strong(freelistLock());
HeapWord* res = NULL;
assert(size == adjustObjectSize(size),
"use adjustObjectSize() before calling into allocate()");
// Strategy
// if small
// exact size from small object indexed list if small
// small or large linear allocation block (linAB) as appropriate
// take from lists of greater sized chunks
// else
// dictionary
// small or large linear allocation block if it has the space
// Try allocating exact size from indexTable first
if (size < IndexSetSize) {
res = (HeapWord*) getChunkFromIndexedFreeList(size);
if(res != NULL) {
assert(res != (HeapWord*)_indexedFreeList[size].head(),
"Not removed from free list");
// no block offset table adjustment is necessary on blocks in
// the indexed lists.
// Try allocating from the small LinAB
} else if (size < _smallLinearAllocBlock._allocation_size_limit &&
(res = getChunkFromSmallLinearAllocBlock(size)) != NULL) {
// if successful, the above also adjusts block offset table
// Note that this call will refill the LinAB to
// satisfy the request. This is different that
// evm.
// Don't record chunk off a LinAB? smallSplitBirth(size);
} else {
// Raid the exact free lists larger than size, even if they are not
// overpopulated.
res = (HeapWord*) getChunkFromGreater(size);
}
} else {
// Big objects get allocated directly from the dictionary.
res = (HeapWord*) getChunkFromDictionaryExact(size);
if (res == NULL) {
// Try hard not to fail since an allocation failure will likely
// trigger a synchronous GC. Try to get the space from the
// allocation blocks.
res = getChunkFromSmallLinearAllocBlockRemainder(size);
}
}
return res;
}
// A worst-case estimate of the space required (in HeapWords) to expand the heap
// when promoting obj.
size_t CompactibleFreeListSpace::expansionSpaceRequired(size_t obj_size) const {
// Depending on the object size, expansion may require refilling either a
// bigLAB or a smallLAB plus refilling a PromotionInfo object. MinChunkSize
// is added because the dictionary may over-allocate to avoid fragmentation.
size_t space = obj_size;
if (!_adaptive_freelists) {
space = MAX2(space, _smallLinearAllocBlock._refillSize);
}
space += _promoInfo.refillSize() + 2 * MinChunkSize;
return space;
}
FreeChunk* CompactibleFreeListSpace::getChunkFromGreater(size_t numWords) {
FreeChunk* ret;
assert(numWords >= MinChunkSize, "Size is less than minimum");
assert(linearAllocationWouldFail() || bestFitFirst(),
"Should not be here");
size_t i;
size_t currSize = numWords + MinChunkSize;
assert(currSize % MinObjAlignment == 0, "currSize should be aligned");
for (i = currSize; i < IndexSetSize; i += IndexSetStride) {
AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i];
if (fl->head()) {
ret = getFromListGreater(fl, numWords);
assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
return ret;
}
}
currSize = MAX2((size_t)SmallForDictionary,
(size_t)(numWords + MinChunkSize));
/* Try to get a chunk that satisfies request, while avoiding
fragmentation that can't be handled. */
{
ret = dictionary()->get_chunk(currSize);
if (ret != NULL) {
assert(ret->size() - numWords >= MinChunkSize,
"Chunk is too small");
_bt.allocated((HeapWord*)ret, ret->size());
/* Carve returned chunk. */
(void) splitChunkAndReturnRemainder(ret, numWords);
/* Label this as no longer a free chunk. */
assert(ret->is_free(), "This chunk should be free");
ret->link_prev(NULL);
}
assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
return ret;
}
ShouldNotReachHere();
}
bool CompactibleFreeListSpace::verifyChunkInIndexedFreeLists(FreeChunk* fc) const {
assert(fc->size() < IndexSetSize, "Size of chunk is too large");
return _indexedFreeList[fc->size()].verify_chunk_in_free_list(fc);
}
bool CompactibleFreeListSpace::verify_chunk_is_linear_alloc_block(FreeChunk* fc) const {
assert((_smallLinearAllocBlock._ptr != (HeapWord*)fc) ||
(_smallLinearAllocBlock._word_size == fc->size()),
"Linear allocation block shows incorrect size");
return ((_smallLinearAllocBlock._ptr == (HeapWord*)fc) &&
(_smallLinearAllocBlock._word_size == fc->size()));
}
// Check if the purported free chunk is present either as a linear
// allocation block, the size-indexed table of (smaller) free blocks,
// or the larger free blocks kept in the binary tree dictionary.
bool CompactibleFreeListSpace::verify_chunk_in_free_list(FreeChunk* fc) const {
if (verify_chunk_is_linear_alloc_block(fc)) {
return true;
} else if (fc->size() < IndexSetSize) {
return verifyChunkInIndexedFreeLists(fc);
} else {
return dictionary()->verify_chunk_in_free_list(fc);
}
}
#ifndef PRODUCT
void CompactibleFreeListSpace::assert_locked() const {
CMSLockVerifier::assert_locked(freelistLock(), parDictionaryAllocLock());
}
void CompactibleFreeListSpace::assert_locked(const Mutex* lock) const {
CMSLockVerifier::assert_locked(lock);
}
#endif
FreeChunk* CompactibleFreeListSpace::allocateScratch(size_t size) {
// In the parallel case, the main thread holds the free list lock
// on behalf the parallel threads.
FreeChunk* fc;
{
// If GC is parallel, this might be called by several threads.
// This should be rare enough that the locking overhead won't affect
// the sequential code.
MutexLockerEx x(parDictionaryAllocLock(),
Mutex::_no_safepoint_check_flag);
fc = getChunkFromDictionary(size);
}
if (fc != NULL) {
fc->dontCoalesce();
assert(fc->is_free(), "Should be free, but not coalescable");
// Verify that the block offset table shows this to
// be a single block, but not one which is unallocated.
_bt.verify_single_block((HeapWord*)fc, fc->size());
_bt.verify_not_unallocated((HeapWord*)fc, fc->size());
}
return fc;
}
oop CompactibleFreeListSpace::promote(oop obj, size_t obj_size) {
assert(obj_size == (size_t)obj->size(), "bad obj_size passed in");
assert_locked();
// if we are tracking promotions, then first ensure space for
// promotion (including spooling space for saving header if necessary).
// then allocate and copy, then track promoted info if needed.
// When tracking (see PromotionInfo::track()), the mark word may
// be displaced and in this case restoration of the mark word
// occurs in the (oop_since_save_marks_)iterate phase.
if (_promoInfo.tracking() && !_promoInfo.ensure_spooling_space()) {
return NULL;
}
// Call the allocate(size_t, bool) form directly to avoid the
// additional call through the allocate(size_t) form. Having
// the compile inline the call is problematic because allocate(size_t)
// is a virtual method.
HeapWord* res = allocate(adjustObjectSize(obj_size));
if (res != NULL) {
Copy::aligned_disjoint_words((HeapWord*)obj, res, obj_size);
// if we should be tracking promotions, do so.
if (_promoInfo.tracking()) {
_promoInfo.track((PromotedObject*)res);
}
}
return oop(res);
}
HeapWord*
CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlock(size_t size) {
assert_locked();
assert(size >= MinChunkSize, "minimum chunk size");
assert(size < _smallLinearAllocBlock._allocation_size_limit,
"maximum from smallLinearAllocBlock");
return getChunkFromLinearAllocBlock(&_smallLinearAllocBlock, size);
}
HeapWord*
CompactibleFreeListSpace::getChunkFromLinearAllocBlock(LinearAllocBlock *blk,
size_t size) {
assert_locked();
assert(size >= MinChunkSize, "too small");
HeapWord* res = NULL;
// Try to do linear allocation from blk, making sure that
if (blk->_word_size == 0) {
// We have probably been unable to fill this either in the prologue or
// when it was exhausted at the last linear allocation. Bail out until
// next time.
assert(blk->_ptr == NULL, "consistency check");
return NULL;
}
assert(blk->_word_size != 0 && blk->_ptr != NULL, "consistency check");
res = getChunkFromLinearAllocBlockRemainder(blk, size);
if (res != NULL) return res;
// about to exhaust this linear allocation block
if (blk->_word_size == size) { // exactly satisfied
res = blk->_ptr;
_bt.allocated(res, blk->_word_size);
} else if (size + MinChunkSize <= blk->_refillSize) {
size_t sz = blk->_word_size;
// Update _unallocated_block if the size is such that chunk would be
// returned to the indexed free list. All other chunks in the indexed
// free lists are allocated from the dictionary so that _unallocated_block
// has already been adjusted for them. Do it here so that the cost
// for all chunks added back to the indexed free lists.
if (sz < SmallForDictionary) {
_bt.allocated(blk->_ptr, sz);
}
// Return the chunk that isn't big enough, and then refill below.
addChunkToFreeLists(blk->_ptr, sz);
split_birth(sz);
// Don't keep statistics on adding back chunk from a LinAB.
} else {
// A refilled block would not satisfy the request.
return NULL;
}
blk->_ptr = NULL; blk->_word_size = 0;
refillLinearAllocBlock(blk);
assert(blk->_ptr == NULL || blk->_word_size >= size + MinChunkSize,
"block was replenished");
if (res != NULL) {
split_birth(size);
repairLinearAllocBlock(blk);
} else if (blk->_ptr != NULL) {
res = blk->_ptr;
size_t blk_size = blk->_word_size;
blk->_word_size -= size;
blk->_ptr += size;
split_birth(size);
repairLinearAllocBlock(blk);
// Update BOT last so that other (parallel) GC threads see a consistent
// view of the BOT and free blocks.
// Above must occur before BOT is updated below.
OrderAccess::storestore();
_bt.split_block(res, blk_size, size); // adjust block offset table
}
return res;
}
HeapWord* CompactibleFreeListSpace::getChunkFromLinearAllocBlockRemainder(
LinearAllocBlock* blk,
size_t size) {
assert_locked();
assert(size >= MinChunkSize, "too small");
HeapWord* res = NULL;
// This is the common case. Keep it simple.
if (blk->_word_size >= size + MinChunkSize) {
assert(blk->_ptr != NULL, "consistency check");
res = blk->_ptr;
// Note that the BOT is up-to-date for the linAB before allocation. It
// indicates the start of the linAB. The split_block() updates the
// BOT for the linAB after the allocation (indicates the start of the
// next chunk to be allocated).
size_t blk_size = blk->_word_size;
blk->_word_size -= size;
blk->_ptr += size;
split_birth(size);
repairLinearAllocBlock(blk);
// Update BOT last so that other (parallel) GC threads see a consistent
// view of the BOT and free blocks.
// Above must occur before BOT is updated below.
OrderAccess::storestore();
_bt.split_block(res, blk_size, size); // adjust block offset table
_bt.allocated(res, size);
}
return res;
}
FreeChunk*
CompactibleFreeListSpace::getChunkFromIndexedFreeList(size_t size) {
assert_locked();
assert(size < SmallForDictionary, "just checking");
FreeChunk* res;
res = _indexedFreeList[size].get_chunk_at_head();
if (res == NULL) {
res = getChunkFromIndexedFreeListHelper(size);
}
_bt.verify_not_unallocated((HeapWord*) res, size);
assert(res == NULL || res->size() == size, "Incorrect block size");
return res;
}
FreeChunk*
CompactibleFreeListSpace::getChunkFromIndexedFreeListHelper(size_t size,
bool replenish) {
assert_locked();
FreeChunk* fc = NULL;
if (size < SmallForDictionary) {
assert(_indexedFreeList[size].head() == NULL ||
_indexedFreeList[size].surplus() <= 0,
"List for this size should be empty or under populated");
// Try best fit in exact lists before replenishing the list
if (!bestFitFirst() || (fc = bestFitSmall(size)) == NULL) {
// Replenish list.
//
// Things tried that failed.
// Tried allocating out of the two LinAB's first before
// replenishing lists.
// Tried small linAB of size 256 (size in indexed list)
// and replenishing indexed lists from the small linAB.
//
FreeChunk* newFc = NULL;
const size_t replenish_size = CMSIndexedFreeListReplenish * size;
if (replenish_size < SmallForDictionary) {
// Do not replenish from an underpopulated size.
if (_indexedFreeList[replenish_size].surplus() > 0 &&
_indexedFreeList[replenish_size].head() != NULL) {
newFc = _indexedFreeList[replenish_size].get_chunk_at_head();
} else if (bestFitFirst()) {
newFc = bestFitSmall(replenish_size);
}
}
if (newFc == NULL && replenish_size > size) {
assert(CMSIndexedFreeListReplenish > 1, "ctl pt invariant");
newFc = getChunkFromIndexedFreeListHelper(replenish_size, false);
}
// Note: The stats update re split-death of block obtained above
// will be recorded below precisely when we know we are going to
// be actually splitting it into more than one pieces below.
if (newFc != NULL) {
if (replenish || CMSReplenishIntermediate) {
// Replenish this list and return one block to caller.
size_t i;
FreeChunk *curFc, *nextFc;
size_t num_blk = newFc->size() / size;
assert(num_blk >= 1, "Smaller than requested?");
assert(newFc->size() % size == 0, "Should be integral multiple of request");
if (num_blk > 1) {
// we are sure we will be splitting the block just obtained
// into multiple pieces; record the split-death of the original
splitDeath(replenish_size);
}
// carve up and link blocks 0, ..., num_blk - 2
// The last chunk is not added to the lists but is returned as the
// free chunk.
for (curFc = newFc, nextFc = (FreeChunk*)((HeapWord*)curFc + size),
i = 0;
i < (num_blk - 1);
curFc = nextFc, nextFc = (FreeChunk*)((HeapWord*)nextFc + size),
i++) {
curFc->set_size(size);
// Don't record this as a return in order to try and
// determine the "returns" from a GC.
_bt.verify_not_unallocated((HeapWord*) fc, size);
_indexedFreeList[size].return_chunk_at_tail(curFc, false);
_bt.mark_block((HeapWord*)curFc, size);
split_birth(size);
// Don't record the initial population of the indexed list
// as a split birth.
}
// check that the arithmetic was OK above
assert((HeapWord*)nextFc == (HeapWord*)newFc + num_blk*size,
"inconsistency in carving newFc");
curFc->set_size(size);
_bt.mark_block((HeapWord*)curFc, size);
split_birth(size);
fc = curFc;
} else {
// Return entire block to caller
fc = newFc;
}
}
}
} else {
// Get a free chunk from the free chunk dictionary to be returned to
// replenish the indexed free list.
fc = getChunkFromDictionaryExact(size);
}
// assert(fc == NULL || fc->is_free(), "Should be returning a free chunk");
return fc;
}
FreeChunk*
CompactibleFreeListSpace::getChunkFromDictionary(size_t size) {
assert_locked();
FreeChunk* fc = _dictionary->get_chunk(size,
FreeBlockDictionary<FreeChunk>::atLeast);
if (fc == NULL) {
return NULL;
}
_bt.allocated((HeapWord*)fc, fc->size());
if (fc->size() >= size + MinChunkSize) {
fc = splitChunkAndReturnRemainder(fc, size);
}
assert(fc->size() >= size, "chunk too small");
assert(fc->size() < size + MinChunkSize, "chunk too big");
_bt.verify_single_block((HeapWord*)fc, fc->size());
return fc;
}
FreeChunk*
CompactibleFreeListSpace::getChunkFromDictionaryExact(size_t size) {
assert_locked();
FreeChunk* fc = _dictionary->get_chunk(size,
FreeBlockDictionary<FreeChunk>::atLeast);
if (fc == NULL) {
return fc;
}
_bt.allocated((HeapWord*)fc, fc->size());
if (fc->size() == size) {
_bt.verify_single_block((HeapWord*)fc, size);
return fc;
}
assert(fc->size() > size, "get_chunk() guarantee");
if (fc->size() < size + MinChunkSize) {
// Return the chunk to the dictionary and go get a bigger one.
returnChunkToDictionary(fc);
fc = _dictionary->get_chunk(size + MinChunkSize,
FreeBlockDictionary<FreeChunk>::atLeast);
if (fc == NULL) {
return NULL;
}
_bt.allocated((HeapWord*)fc, fc->size());
}
assert(fc->size() >= size + MinChunkSize, "tautology");
fc = splitChunkAndReturnRemainder(fc, size);
assert(fc->size() == size, "chunk is wrong size");
_bt.verify_single_block((HeapWord*)fc, size);
return fc;
}
void
CompactibleFreeListSpace::returnChunkToDictionary(FreeChunk* chunk) {
assert_locked();
size_t size = chunk->size();
_bt.verify_single_block((HeapWord*)chunk, size);
// adjust _unallocated_block downward, as necessary
_bt.freed((HeapWord*)chunk, size);
_dictionary->return_chunk(chunk);
#ifndef PRODUCT
if (CMSCollector::abstract_state() != CMSCollector::Sweeping) {
TreeChunk<FreeChunk, AdaptiveFreeList>* tc = TreeChunk
Other Java examples (source code examples)Here is a short list of links related to this Java compactibleFreeListSpace.cpp source code file: |
The search page
Other Java source code examples at this package level
Click here to learn more about this project
