/*

 * Copyright (c) 2001, 2018, 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/cms/cmsHeap.hpp"

#include "gc/cms/cmsLockVerifier.hpp"

#include "gc/cms/compactibleFreeListSpace.hpp"

#include "gc/cms/concurrentMarkSweepGeneration.inline.hpp"

#include "gc/cms/concurrentMarkSweepThread.hpp"

#include "gc/shared/blockOffsetTable.inline.hpp"

#include "gc/shared/collectedHeap.inline.hpp"

#include "gc/shared/space.inline.hpp"

#include "gc/shared/spaceDecorator.hpp"

#include "logging/log.hpp"

#include "logging/logStream.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/binaryTreeDictionary.inline.hpp"

#include "memory/resourceArea.hpp"

#include "memory/universe.hpp"

#include "oops/access.inline.hpp"

#include "oops/compressedOops.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/align.hpp"

#include "utilities/copy.hpp"

// Specialize for AdaptiveFreeList which tries to avoid

// splitting a chunk of a size that is under populated in favor of

// an over populated size.  The general get_better_list() just returns

// the current list.

template <>

TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >*

TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list(

  BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) {

  // A candidate chunk has been found.  If it is already under

  // populated, get a chunk associated with the hint for this

  // chunk.

  TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this;

  if (curTL->surplus() <= 0) {

    /* Use the hint to find a size with a surplus, and reset the hint. */

    TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this;

    while (hintTL->hint() != 0) {

      assert(hintTL->hint() > hintTL->size(),

        "hint points in the wrong direction");

      hintTL = dictionary->find_list(hintTL->hint());

      assert(curTL != hintTL, "Infinite loop");

      if (hintTL == NULL ||

          hintTL == curTL /* Should not happen but protect against it */ ) {

        // No useful hint.  Set the hint to NULL and go on.

        curTL->set_hint(0);

        break;

      }

      assert(hintTL->size() > curTL->size(), "hint is inconsistent");

      if (hintTL->surplus() > 0) {

        // The hint led to a list that has a surplus.  Use it.

        // Set the hint for the candidate to an overpopulated

        // size.

        curTL->set_hint(hintTL->size());

        // Change the candidate.

        curTL = hintTL;

        break;

      }

    }

  }

  return curTL;

}

void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth) {

  TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* nd = find_list(size);

  if (nd) {

    if (split) {

      if (birth) {

        nd->increment_split_births();

        nd->increment_surplus();

      }  else {

        nd->increment_split_deaths();

        nd->decrement_surplus();

      }

    } else {

      if (birth) {

        nd->increment_coal_births();

        nd->increment_surplus();

      } else {

        nd->increment_coal_deaths();

        nd->decrement_surplus();

      }

    }

  }

  // A list for this size may not be found (nd == 0) if

  //   This is a death where the appropriate list is now

  //     empty and has been removed from the list.

  //   This is a birth associated with a LinAB.  The chunk

  //     for the LinAB is not in the dictionary.

}

bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) {

  if (FLSAlwaysCoalesceLarge) return true;

  TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* list_of_size = find_list(size);

  // None of requested size implies overpopulated.

  return list_of_size == NULL || list_of_size->coal_desired() <= 0 ||

         list_of_size->count() > list_of_size->coal_desired();

}

// For each list in the tree, calculate the desired, desired

// coalesce, count before sweep, and surplus before sweep.

class BeginSweepClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > {

  double _percentage;

  float _inter_sweep_current;

  float _inter_sweep_estimate;

  float _intra_sweep_estimate;

 public:

  BeginSweepClosure(double p, float inter_sweep_current,

                              float inter_sweep_estimate,

                              float intra_sweep_estimate) :

   _percentage(p),

   _inter_sweep_current(inter_sweep_current),

   _inter_sweep_estimate(inter_sweep_estimate),

   _intra_sweep_estimate(intra_sweep_estimate) { }

  void do_list(AdaptiveFreeList<FreeChunk>* fl) {

    double coalSurplusPercent = _percentage;

    fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate);

    fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent));

    fl->set_before_sweep(fl->count());

    fl->set_bfr_surp(fl->surplus());

  }

};

void AFLBinaryTreeDictionary::begin_sweep_dict_census(double coalSurplusPercent,

  float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {

  BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current,

                        inter_sweep_estimate,

                        intra_sweep_estimate);

  bsc.do_tree(root());

}

// Calculate surpluses for the lists in the tree.

class setTreeSurplusClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > {

  double percentage;

 public:

  setTreeSurplusClosure(double v) { percentage = v; }

  void do_list(AdaptiveFreeList<FreeChunk>* fl) {

    double splitSurplusPercent = percentage;

    fl->set_surplus(fl->count() -

                   (ssize_t)((double)fl->desired() * splitSurplusPercent));

  }

};

void AFLBinaryTreeDictionary::set_tree_surplus(double splitSurplusPercent) {

  setTreeSurplusClosure sts(splitSurplusPercent);

  sts.do_tree(root());

}

// Set hints for the lists in the tree.

class setTreeHintsClosure : public DescendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > {

  size_t hint;

 public:

  setTreeHintsClosure(size_t v) { hint = v; }

  void do_list(AdaptiveFreeList<FreeChunk>* fl) {

    fl->set_hint(hint);

    assert(fl->hint() == 0 || fl->hint() > fl->size(),

      "Current hint is inconsistent");

    if (fl->surplus() > 0) {

      hint = fl->size();

    }

  }

};

void AFLBinaryTreeDictionary::set_tree_hints(void) {

  setTreeHintsClosure sth(0);

  sth.do_tree(root());

}

// Save count before previous sweep and splits and coalesces.

class clearTreeCensusClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > {

  void do_list(AdaptiveFreeList<FreeChunk>* fl) {

    fl->set_prev_sweep(fl->count());

    fl->set_coal_births(0);

    fl->set_coal_deaths(0);

    fl->set_split_births(0);

    fl->set_split_deaths(0);

  }

};

void AFLBinaryTreeDictionary::clear_tree_census(void) {

  clearTreeCensusClosure ctc;

  ctc.do_tree(root());

}

// Do reporting and post sweep clean up.

void AFLBinaryTreeDictionary::end_sweep_dict_census(double splitSurplusPercent) {

  // Does walking the tree 3 times hurt?

  set_tree_surplus(splitSurplusPercent);

  set_tree_hints();

  LogTarget(Trace, gc, freelist, stats) log;

  if (log.is_enabled()) {

    LogStream out(log);

    report_statistics(&out);

  }

  clear_tree_census();

}

// Print census information - counts, births, deaths, etc.

// for each list in the tree.  Also print some summary

// information.

class PrintTreeCensusClosure : public AscendTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > {

  int _print_line;

  size_t _total_free;

  AdaptiveFreeList<FreeChunk> _total;

 public:

  PrintTreeCensusClosure() {

    _print_line = 0;

    _total_free = 0;

  }

  AdaptiveFreeList<FreeChunk>* total() { return &_total; }

  size_t total_free() { return _total_free; }

  void do_list(AdaptiveFreeList<FreeChunk>* fl) {

    LogStreamHandle(Debug, gc, freelist, census) out;

    if (++_print_line >= 40) {

      AdaptiveFreeList<FreeChunk>::print_labels_on(&out, "size");

      _print_line = 0;

    }

    fl->print_on(&out);

    _total_free +=           fl->count()             * fl->size()        ;

    total()->set_count(      total()->count()        + fl->count()      );

    total()->set_bfr_surp(   total()->bfr_surp()     + fl->bfr_surp()    );

    total()->set_surplus(    total()->split_deaths() + fl->surplus()    );

    total()->set_desired(    total()->desired()      + fl->desired()    );

    total()->set_prev_sweep(  total()->prev_sweep()   + fl->prev_sweep()  );

    total()->set_before_sweep(total()->before_sweep() + fl->before_sweep());

    total()->set_coal_births( total()->coal_births()  + fl->coal_births() );

    total()->set_coal_deaths( total()->coal_deaths()  + fl->coal_deaths() );

    total()->set_split_births(total()->split_births() + fl->split_births());

    total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());

  }

};

void AFLBinaryTreeDictionary::print_dict_census(outputStream* st) const {

  st->print_cr("BinaryTree");

  AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size");

  PrintTreeCensusClosure ptc;

  ptc.do_tree(root());

  AdaptiveFreeList<FreeChunk>* total = ptc.total();

  AdaptiveFreeList<FreeChunk>::print_labels_on(st, " ");

  total->print_on(st, "TOTAL\t");

  st->print_cr("total_free(words): " SIZE_FORMAT_W(16) " growth: %8.5f  deficit: %8.5f",

               ptc.total_free(),

               (double)(total->split_births() + total->coal_births()

                      - total->split_deaths() - total->coal_deaths())

               /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0),

              (double)(total->desired() - total->count())

              /(total->desired() != 0 ? (double)total->desired() : 1.0));

}

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

//// 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 CompactibleFreeListSpace::_min_chunk_size_in_bytes = 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.

  _min_chunk_size_in_bytes = align_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) :

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

                Monitor::_safepoint_check_sometimes),

  _parDictionaryAllocLock(Mutex::leaf - 1,  // == rank(ExpandHeap_lock) - 1

                          "CompactibleFreeListSpace._dict_par_lock", true,

                          Monitor::_safepoint_check_never),

  _rescan_task_size(CardTable::card_size_in_words * BitsPerWord *

                    CMSRescanMultiple),

  _marking_task_size(CardTable::card_size_in_words * BitsPerWord *

                    CMSConcMarkMultiple),

  _collector(NULL),

  _preconsumptionDirtyCardClosure(NULL)

{

  assert(sizeof(FreeChunk) / BytesPerWord <= MinChunkSize,

         "FreeChunk is larger than expected");

  _bt.set_space(this);

  initialize(mr, SpaceDecorator::Clear, SpaceDecorator::Mangle);

  _dictionary = new AFLBinaryTreeDictionary(mr);

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

  _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.

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

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

                                            "a freelist par lock", true, Mutex::_safepoint_check_sometimes);

    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 = CMSHeap::heap()->young_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_raw();

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

  }

}

size_t CompactibleFreeListSpace::obj_size(const HeapWord* addr) const {

  return adjustObjectSize(oop(addr)->size());

}

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

  }