/*

 * Copyright (c) 2005, 2016, 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 "classfile/stringTable.hpp"

#include "classfile/symbolTable.hpp"

#include "classfile/systemDictionary.hpp"

#include "code/codeCache.hpp"

#include "gc/parallel/gcTaskManager.hpp"

#include "gc/parallel/parallelScavengeHeap.inline.hpp"

#include "gc/parallel/pcTasks.hpp"

#include "gc/parallel/psAdaptiveSizePolicy.hpp"

#include "gc/parallel/psCompactionManager.inline.hpp"

#include "gc/parallel/psMarkSweep.hpp"

#include "gc/parallel/psMarkSweepDecorator.hpp"

#include "gc/parallel/psOldGen.hpp"

#include "gc/parallel/psParallelCompact.inline.hpp"

#include "gc/parallel/psPromotionManager.inline.hpp"

#include "gc/parallel/psScavenge.hpp"

#include "gc/parallel/psYoungGen.hpp"

#include "gc/shared/gcCause.hpp"

#include "gc/shared/gcHeapSummary.hpp"

#include "gc/shared/gcId.hpp"

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

#include "gc/shared/gcTimer.hpp"

#include "gc/shared/gcTrace.hpp"

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

#include "gc/shared/isGCActiveMark.hpp"

#include "gc/shared/referencePolicy.hpp"

#include "gc/shared/referenceProcessor.hpp"

#include "gc/shared/spaceDecorator.hpp"

#include "logging/log.hpp"

#include "memory/resourceArea.hpp"

#include "oops/instanceKlass.inline.hpp"

#include "oops/instanceMirrorKlass.inline.hpp"

#include "oops/methodData.hpp"

#include "oops/objArrayKlass.inline.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.inline.hpp"

#include "runtime/fprofiler.hpp"

#include "runtime/safepoint.hpp"

#include "runtime/vmThread.hpp"

#include "services/management.hpp"

#include "services/memTracker.hpp"

#include "services/memoryService.hpp"

#include "utilities/events.hpp"

#include "utilities/stack.inline.hpp"

#include <math.h>

// All sizes are in HeapWords.

const size_t ParallelCompactData::Log2RegionSize  = 16; // 64K words

const size_t ParallelCompactData::RegionSize      = (size_t)1 << Log2RegionSize;

const size_t ParallelCompactData::RegionSizeBytes =

  RegionSize << LogHeapWordSize;

const size_t ParallelCompactData::RegionSizeOffsetMask = RegionSize - 1;

const size_t ParallelCompactData::RegionAddrOffsetMask = RegionSizeBytes - 1;

const size_t ParallelCompactData::RegionAddrMask       = ~RegionAddrOffsetMask;

const size_t ParallelCompactData::Log2BlockSize   = 7; // 128 words

const size_t ParallelCompactData::BlockSize       = (size_t)1 << Log2BlockSize;

const size_t ParallelCompactData::BlockSizeBytes  =

  BlockSize << LogHeapWordSize;

const size_t ParallelCompactData::BlockSizeOffsetMask = BlockSize - 1;

const size_t ParallelCompactData::BlockAddrOffsetMask = BlockSizeBytes - 1;

const size_t ParallelCompactData::BlockAddrMask       = ~BlockAddrOffsetMask;

const size_t ParallelCompactData::BlocksPerRegion = RegionSize / BlockSize;

const size_t ParallelCompactData::Log2BlocksPerRegion =

  Log2RegionSize - Log2BlockSize;

const ParallelCompactData::RegionData::region_sz_t

ParallelCompactData::RegionData::dc_shift = 27;

const ParallelCompactData::RegionData::region_sz_t

ParallelCompactData::RegionData::dc_mask = ~0U << dc_shift;

const ParallelCompactData::RegionData::region_sz_t

ParallelCompactData::RegionData::dc_one = 0x1U << dc_shift;

const ParallelCompactData::RegionData::region_sz_t

ParallelCompactData::RegionData::los_mask = ~dc_mask;

const ParallelCompactData::RegionData::region_sz_t

ParallelCompactData::RegionData::dc_claimed = 0x8U << dc_shift;

const ParallelCompactData::RegionData::region_sz_t

ParallelCompactData::RegionData::dc_completed = 0xcU << dc_shift;

SpaceInfo PSParallelCompact::_space_info[PSParallelCompact::last_space_id];

ReferenceProcessor* PSParallelCompact::_ref_processor = NULL;

double PSParallelCompact::_dwl_mean;

double PSParallelCompact::_dwl_std_dev;

double PSParallelCompact::_dwl_first_term;

double PSParallelCompact::_dwl_adjustment;

#ifdef  ASSERT

bool   PSParallelCompact::_dwl_initialized = false;

#endif  // #ifdef ASSERT

void SplitInfo::record(size_t src_region_idx, size_t partial_obj_size,

                       HeapWord* destination)

{

  assert(src_region_idx != 0, "invalid src_region_idx");

  assert(partial_obj_size != 0, "invalid partial_obj_size argument");

  assert(destination != NULL, "invalid destination argument");

  _src_region_idx = src_region_idx;

  _partial_obj_size = partial_obj_size;

  _destination = destination;

  // These fields may not be updated below, so make sure they're clear.

  assert(_dest_region_addr == NULL, "should have been cleared");

  assert(_first_src_addr == NULL, "should have been cleared");

  // Determine the number of destination regions for the partial object.

  HeapWord* const last_word = destination + partial_obj_size - 1;

  const ParallelCompactData& sd = PSParallelCompact::summary_data();

  HeapWord* const beg_region_addr = sd.region_align_down(destination);

  HeapWord* const end_region_addr = sd.region_align_down(last_word);

  if (beg_region_addr == end_region_addr) {

    // One destination region.

    _destination_count = 1;

    if (end_region_addr == destination) {

      // The destination falls on a region boundary, thus the first word of the

      // partial object will be the first word copied to the destination region.

      _dest_region_addr = end_region_addr;

      _first_src_addr = sd.region_to_addr(src_region_idx);

    }

  } else {

    // Two destination regions.  When copied, the partial object will cross a

    // destination region boundary, so a word somewhere within the partial

    // object will be the first word copied to the second destination region.

    _destination_count = 2;

    _dest_region_addr = end_region_addr;

    const size_t ofs = pointer_delta(end_region_addr, destination);

    assert(ofs < _partial_obj_size, "sanity");

    _first_src_addr = sd.region_to_addr(src_region_idx) + ofs;

  }

}

void SplitInfo::clear()

{

  _src_region_idx = 0;

  _partial_obj_size = 0;

  _destination = NULL;

  _destination_count = 0;

  _dest_region_addr = NULL;

  _first_src_addr = NULL;

  assert(!is_valid(), "sanity");

}

#ifdef  ASSERT

void SplitInfo::verify_clear()

{

  assert(_src_region_idx == 0, "not clear");

  assert(_partial_obj_size == 0, "not clear");

  assert(_destination == NULL, "not clear");

  assert(_destination_count == 0, "not clear");

  assert(_dest_region_addr == NULL, "not clear");

  assert(_first_src_addr == NULL, "not clear");

}

#endif  // #ifdef ASSERT

void PSParallelCompact::print_on_error(outputStream* st) {

  _mark_bitmap.print_on_error(st);

}

#ifndef PRODUCT

const char* PSParallelCompact::space_names[] = {

  "old ", "eden", "from", "to  "

};

void PSParallelCompact::print_region_ranges() {

  if (!log_develop_is_enabled(Trace, gc, compaction)) {

    return;

  }

  Log(gc, compaction) log;

  ResourceMark rm;

  Universe::print_on(log.trace_stream());

  log.trace("space  bottom     top        end        new_top");

  log.trace("------ ---------- ---------- ---------- ----------");

  for (unsigned int id = 0; id < last_space_id; ++id) {

    const MutableSpace* space = _space_info[id].space();

    log.trace("%u %s "

              SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) " "

              SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) " ",

              id, space_names[id],

              summary_data().addr_to_region_idx(space->bottom()),

              summary_data().addr_to_region_idx(space->top()),

              summary_data().addr_to_region_idx(space->end()),

              summary_data().addr_to_region_idx(_space_info[id].new_top()));

  }

}

void

print_generic_summary_region(size_t i, const ParallelCompactData::RegionData* c)

{

#define REGION_IDX_FORMAT        SIZE_FORMAT_W(7)

#define REGION_DATA_FORMAT       SIZE_FORMAT_W(5)

  ParallelCompactData& sd = PSParallelCompact::summary_data();

  size_t dci = c->destination() ? sd.addr_to_region_idx(c->destination()) : 0;

  log_develop_trace(gc, compaction)(

      REGION_IDX_FORMAT " " PTR_FORMAT " "

      REGION_IDX_FORMAT " " PTR_FORMAT " "

      REGION_DATA_FORMAT " " REGION_DATA_FORMAT " "

      REGION_DATA_FORMAT " " REGION_IDX_FORMAT " %d",

      i, p2i(c->data_location()), dci, p2i(c->destination()),

      c->partial_obj_size(), c->live_obj_size(),

      c->data_size(), c->source_region(), c->destination_count());

#undef  REGION_IDX_FORMAT

#undef  REGION_DATA_FORMAT

}

void

print_generic_summary_data(ParallelCompactData& summary_data,

                           HeapWord* const beg_addr,

                           HeapWord* const end_addr)

{

  size_t total_words = 0;

  size_t i = summary_data.addr_to_region_idx(beg_addr);

  const size_t last = summary_data.addr_to_region_idx(end_addr);

  HeapWord* pdest = 0;

  while (i < last) {

    ParallelCompactData::RegionData* c = summary_data.region(i);

    if (c->data_size() != 0 || c->destination() != pdest) {

      print_generic_summary_region(i, c);

      total_words += c->data_size();

      pdest = c->destination();

    }

    ++i;

  }

  log_develop_trace(gc, compaction)("summary_data_bytes=" SIZE_FORMAT, total_words * HeapWordSize);

}

void

print_generic_summary_data(ParallelCompactData& summary_data,

                           SpaceInfo* space_info)

{

  if (!log_develop_is_enabled(Trace, gc, compaction)) {

    return;

  }

  for (unsigned int id = 0; id < PSParallelCompact::last_space_id; ++id) {

    const MutableSpace* space = space_info[id].space();

    print_generic_summary_data(summary_data, space->bottom(),

                               MAX2(space->top(), space_info[id].new_top()));

  }

}

void

print_initial_summary_data(ParallelCompactData& summary_data,

                           const MutableSpace* space) {

  if (space->top() == space->bottom()) {

    return;

  }

  const size_t region_size = ParallelCompactData::RegionSize;

  typedef ParallelCompactData::RegionData RegionData;

  HeapWord* const top_aligned_up = summary_data.region_align_up(space->top());

  const size_t end_region = summary_data.addr_to_region_idx(top_aligned_up);

  const RegionData* c = summary_data.region(end_region - 1);

  HeapWord* end_addr = c->destination() + c->data_size();

  const size_t live_in_space = pointer_delta(end_addr, space->bottom());

  // Print (and count) the full regions at the beginning of the space.

  size_t full_region_count = 0;

  size_t i = summary_data.addr_to_region_idx(space->bottom());

  while (i < end_region && summary_data.region(i)->data_size() == region_size) {

    ParallelCompactData::RegionData* c = summary_data.region(i);

    log_develop_trace(gc, compaction)(

        SIZE_FORMAT_W(5) " " PTR_FORMAT " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " %d",

        i, p2i(c->destination()),

        c->partial_obj_size(), c->live_obj_size(),

        c->data_size(), c->source_region(), c->destination_count());

    ++full_region_count;

    ++i;

  }

  size_t live_to_right = live_in_space - full_region_count * region_size;

  double max_reclaimed_ratio = 0.0;

  size_t max_reclaimed_ratio_region = 0;

  size_t max_dead_to_right = 0;

  size_t max_live_to_right = 0;

  // Print the 'reclaimed ratio' for regions while there is something live in

  // the region or to the right of it.  The remaining regions are empty (and

  // uninteresting), and computing the ratio will result in division by 0.

  while (i < end_region && live_to_right > 0) {

    c = summary_data.region(i);

    HeapWord* const region_addr = summary_data.region_to_addr(i);

    const size_t used_to_right = pointer_delta(space->top(), region_addr);

    const size_t dead_to_right = used_to_right - live_to_right;

    const double reclaimed_ratio = double(dead_to_right) / live_to_right;

    if (reclaimed_ratio > max_reclaimed_ratio) {

            max_reclaimed_ratio = reclaimed_ratio;

            max_reclaimed_ratio_region = i;

            max_dead_to_right = dead_to_right;

            max_live_to_right = live_to_right;

    }

    ParallelCompactData::RegionData* c = summary_data.region(i);

    log_develop_trace(gc, compaction)(

        SIZE_FORMAT_W(5) " " PTR_FORMAT " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " %d"

        "%12.10f " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10),

        i, p2i(c->destination()),

        c->partial_obj_size(), c->live_obj_size(),

        c->data_size(), c->source_region(), c->destination_count(),

        reclaimed_ratio, dead_to_right, live_to_right);

    live_to_right -= c->data_size();

    ++i;

  }

  // Any remaining regions are empty.  Print one more if there is one.

  if (i < end_region) {

    ParallelCompactData::RegionData* c = summary_data.region(i);

    log_develop_trace(gc, compaction)(

        SIZE_FORMAT_W(5) " " PTR_FORMAT " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " %d",

         i, p2i(c->destination()),

         c->partial_obj_size(), c->live_obj_size(),

         c->data_size(), c->source_region(), c->destination_count());

  }

  log_develop_trace(gc, compaction)("max:  " SIZE_FORMAT_W(4) " d2r=" SIZE_FORMAT_W(10) " l2r=" SIZE_FORMAT_W(10) " max_ratio=%14.12f",

                                    max_reclaimed_ratio_region, max_dead_to_right, max_live_to_right, max_reclaimed_ratio);

}

void

print_initial_summary_data(ParallelCompactData& summary_data,

                           SpaceInfo* space_info) {

  if (!log_develop_is_enabled(Trace, gc, compaction)) {

    return;

  }

  unsigned int id = PSParallelCompact::old_space_id;

  const MutableSpace* space;

  do {

    space = space_info[id].space();

    print_initial_summary_data(summary_data, space);

  } while (++id < PSParallelCompact::eden_space_id);

  do {

    space = space_info[id].space();

    print_generic_summary_data(summary_data, space->bottom(), space->top());

  } while (++id < PSParallelCompact::last_space_id);

}

void ParallelCompact_test() {

  if (!UseParallelOldGC) {

    return;

  }

  // Check that print_generic_summary_data() does not print the

  // end region by placing a bad value in the destination of the

  // end region.  The end region should not be printed because it

  // corresponds to the space after the end of the heap.

  ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();

  ParCompactionManager* const vmthread_cm =

    ParCompactionManager::manager_array(ParallelGCThreads);

  HeapWord* begin_heap =

    (HeapWord*) heap->old_gen()->virtual_space()->low_boundary();

  HeapWord* end_heap =

    (HeapWord*) heap->young_gen()->virtual_space()->high_boundary();

  size_t end_index =

    PSParallelCompact::summary_data().addr_to_region_idx(end_heap);

  ParallelCompactData::RegionData* c = PSParallelCompact::summary_data().region(end_index);

  // Initialize the end region with a bad destination.

  c->set_destination(begin_heap - 1);

  print_generic_summary_data(PSParallelCompact::summary_data(),

    begin_heap, end_heap);

}

#endif  // #ifndef PRODUCT

#ifdef  ASSERT

size_t add_obj_count;

size_t add_obj_size;

size_t mark_bitmap_count;

size_t mark_bitmap_size;

#endif  // #ifdef ASSERT

ParallelCompactData::ParallelCompactData()

{

  _region_start = 0;

  _region_vspace = 0;

  _reserved_byte_size = 0;

  _region_data = 0;

  _region_count = 0;

  _block_vspace = 0;

  _block_data = 0;

  _block_count = 0;

}

bool ParallelCompactData::initialize(MemRegion covered_region)

{

  _region_start = covered_region.start();

  const size_t region_size = covered_region.word_size();

  DEBUG_ONLY(_region_end = _region_start + region_size;)

  assert(region_align_down(_region_start) == _region_start,

         "region start not aligned");

  assert((region_size & RegionSizeOffsetMask) == 0,

         "region size not a multiple of RegionSize");

  bool result = initialize_region_data(region_size) && initialize_block_data();

  return result;

}

PSVirtualSpace*

ParallelCompactData::create_vspace(size_t count, size_t element_size)

{

  const size_t raw_bytes = count * element_size;

  const size_t page_sz = os::page_size_for_region_aligned(raw_bytes, 10);

  const size_t granularity = os::vm_allocation_granularity();

  _reserved_byte_size = align_size_up(raw_bytes, MAX2(page_sz, granularity));

  const size_t rs_align = page_sz == (size_t) os::vm_page_size() ? 0 :

    MAX2(page_sz, granularity);

  ReservedSpace rs(_reserved_byte_size, rs_align, rs_align > 0);

  os::trace_page_sizes("Parallel Compact Data", raw_bytes, raw_bytes, page_sz, rs.base(),

                       rs.size());

  MemTracker::record_virtual_memory_type((address)rs.base(), mtGC);

  PSVirtualSpace* vspace = new PSVirtualSpace(rs, page_sz);

  if (vspace != 0) {

    if (vspace->expand_by(_reserved_byte_size)) {

      return vspace;

    }

    delete vspace;

    // Release memory reserved in the space.

    rs.release();

  }

  return 0;

}

bool ParallelCompactData::initialize_region_data(size_t region_size)

{

  const size_t count = (region_size + RegionSizeOffsetMask) >> Log2RegionSize;

  _region_vspace = create_vspace(count, sizeof(RegionData));

  if (_region_vspace != 0) {

    _region_data = (RegionData*)_region_vspace->reserved_low_addr();

    _region_count = count;

    return true;

  }

  return false;

}

bool ParallelCompactData::initialize_block_data()

{

  assert(_region_count != 0, "region data must be initialized first");

  const size_t count = _region_count << Log2BlocksPerRegion;

  _block_vspace = create_vspace(count, sizeof(BlockData));

  if (_block_vspace != 0) {

    _block_data = (BlockData*)_block_vspace->reserved_low_addr();

    _block_count = count;

    return true;

  }

  return false;

}

void ParallelCompactData::clear()