/*

 * 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, pessimistically for the rare cases when res

  // calculated 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