/*

 * Copyright 2001-2008 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

# include "incls/_precompiled.incl"

# include "incls/_compactibleFreeListSpace.cpp.incl"

/////////////////////////////////////////////////////////////////////////

//// CompactibleFreeListSpace

/////////////////////////////////////////////////////////////////////////

// highest ranked  free list lock rank

int CompactibleFreeListSpace::_lockRank = Mutex::leaf + 3;

// Constructor

CompactibleFreeListSpace::CompactibleFreeListSpace(BlockOffsetSharedArray* bs,

  MemRegion mr, bool use_adaptive_freelists,

  FreeBlockDictionary::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)

{

  _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::dictionaryBinaryTree:

      _dictionary = new BinaryTreeDictionary(mr);

      break;

    case FreeBlockDictionary::dictionarySplayTree:

    case FreeBlockDictionary::dictionarySkipList:

    default:

      warning("dictionaryChoice: selected option not understood; using"

              " default BinaryTreeDictionary implementation instead.");

      _dictionary = new BinaryTreeDictionary(mr);

      break;

  }

  splitBirth(mr.word_size());

  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->getChunk(mr.word_size());

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

  }

  checkFreeListConsistency();

  // Initialize locks for parallel case.

  if (ParallelGCThreads > 0) {

    for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {

      _indexedFreeListParLocks[i] = new Mutex(Mutex::leaf - 1, // == ExpandHeap_lock - 1

                                              "a freelist par lock",

                                              true);

      if (_indexedFreeListParLocks[i] == NULL)

        vm_exit_during_initialization("Could not allocate a par lock");

      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");

  }

  VALIDATE_MARK_SWEEP_ONLY(MarkSweep::register_live_oop(q, adjusted_size));

  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 (int 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->setSize(mr.word_size());

    if (mr.word_size() >= IndexSetSize ) {

      returnChunkToDictionary(fc);

    } else {

      _bt.verify_not_unallocated((HeapWord*)fc, fc->size());

      _indexedFreeList[mr.word_size()].returnChunkAtHead(fc);

    }

  }

  _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()->findLargestDict();

    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_returnedBytes(0);

  }

}

size_t CompactibleFreeListSpace::sumIndexedFreeListArrayReturnedBytes() {

  size_t sum = 0;

  for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {

    sum += _indexedFreeList[i].allocation_stats()->returnedBytes();

  }

  return sum;

}

size_t CompactibleFreeListSpace::totalCountInIndexedFreeLists() const {

  size_t count = 0;

  for (int i = MinChunkSize; 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()->totalCount();

  if (_smallLinearAllocBlock._word_size != 0) {

    num++;

  }

  return num;

}

#endif

bool CompactibleFreeListSpace::is_free_block(const HeapWord* p) const {

  FreeChunk* fc = (FreeChunk*) p;

  return fc->isFree();

}

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->totalChunkSize(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->maxChunkSize();

  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 CompactibleFreeListSpace::reportFreeListStatistics() const {

  assert_lock_strong(&_freelistLock);

  assert(PrintFLSStatistics != 0, "Reporting error");

  _dictionary->reportStatistics();

  if (PrintFLSStatistics > 1) {

    reportIndexedFreeListStatistics();

    size_t totalSize = totalSizeInIndexedFreeLists() +

                       _dictionary->totalChunkSize(DEBUG_ONLY(freelistLock()));

    gclog_or_tty->print(" free=%ld frag=%1.4f\n", totalSize, flsFrag());

  }

}

void CompactibleFreeListSpace::reportIndexedFreeListStatistics() const {

  assert_lock_strong(&_freelistLock);

  gclog_or_tty->print("Statistics for IndexedFreeLists:\n"

                      "--------------------------------\n");

  size_t totalSize = totalSizeInIndexedFreeLists();

  size_t   freeBlocks = numFreeBlocksInIndexedFreeLists();

  gclog_or_tty->print("Total Free Space: %d\n", totalSize);

  gclog_or_tty->print("Max   Chunk Size: %d\n", maxChunkSizeInIndexedFreeLists());

  gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks);

  if (freeBlocks != 0) {

    gclog_or_tty->print("Av.  Block  Size: %d\n", totalSize/freeBlocks);

  }

}

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 || 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(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(OopClosure);

  walk_mem_region_with_cl_DECL(FilteringClosure);

public:

  FreeListSpace_DCTOC(CompactibleFreeListSpace* sp,

                      CMSCollector* collector,

                      OopClosure* 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) {             \

   if (SharedHeap::heap()->n_par_threads() > 0) {                               \

     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,            \