/*

 * Copyright 2005-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/_psParallelCompact.cpp.incl"

#include <math.h>

// All sizes are in HeapWords.

const size_t ParallelCompactData::Log2RegionSize  = 9; // 512 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 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];

bool      PSParallelCompact::_print_phases = false;

ReferenceProcessor* PSParallelCompact::_ref_processor = NULL;

klassOop            PSParallelCompact::_updated_int_array_klass_obj = 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

#ifdef VALIDATE_MARK_SWEEP

GrowableArray<void*>*   PSParallelCompact::_root_refs_stack = NULL;

GrowableArray<oop> *    PSParallelCompact::_live_oops = NULL;

GrowableArray<oop> *    PSParallelCompact::_live_oops_moved_to = NULL;

GrowableArray<size_t>*  PSParallelCompact::_live_oops_size = NULL;

size_t                  PSParallelCompact::_live_oops_index = 0;

size_t                  PSParallelCompact::_live_oops_index_at_perm = 0;

GrowableArray<void*>*   PSParallelCompact::_other_refs_stack = NULL;

GrowableArray<void*>*   PSParallelCompact::_adjusted_pointers = NULL;

bool                    PSParallelCompact::_pointer_tracking = false;

bool                    PSParallelCompact::_root_tracking = true;

GrowableArray<HeapWord*>* PSParallelCompact::_cur_gc_live_oops = NULL;

GrowableArray<HeapWord*>* PSParallelCompact::_cur_gc_live_oops_moved_to = NULL;

GrowableArray<size_t>   * PSParallelCompact::_cur_gc_live_oops_size = NULL;

GrowableArray<HeapWord*>* PSParallelCompact::_last_gc_live_oops = NULL;

GrowableArray<HeapWord*>* PSParallelCompact::_last_gc_live_oops_moved_to = NULL;

GrowableArray<size_t>   * PSParallelCompact::_last_gc_live_oops_size = NULL;

#endif

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

#ifndef PRODUCT

const char* PSParallelCompact::space_names[] = {

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

};

void PSParallelCompact::print_region_ranges()

{

  tty->print_cr("space  bottom     top        end        new_top");

  tty->print_cr("------ ---------- ---------- ---------- ----------");

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

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

    tty->print_cr("%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;

  tty->print_cr(REGION_IDX_FORMAT " " PTR_FORMAT " "

                REGION_IDX_FORMAT " " PTR_FORMAT " "

                REGION_DATA_FORMAT " " REGION_DATA_FORMAT " "

                REGION_DATA_FORMAT " " REGION_IDX_FORMAT " %d",

                i, c->data_location(), dci, 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;

  }

  tty->print_cr("summary_data_bytes=" SIZE_FORMAT, total_words * HeapWordSize);

}

void

print_generic_summary_data(ParallelCompactData& summary_data,

                           SpaceInfo* space_info)

{

  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_region(size_t i,

                             const ParallelCompactData::RegionData* c,

                             bool newline = true)

{

  tty->print(SIZE_FORMAT_W(5) " " PTR_FORMAT " "

             SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " "

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

             i, c->destination(),

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

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

  if (newline) tty->cr();

}

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) {

    print_initial_summary_region(i, summary_data.region(i));

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

    }

    print_initial_summary_region(i, c, false);

    tty->print_cr(" %12.10f " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10),

                  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) {

    print_initial_summary_region(i, summary_data.region(i));

  }

  tty->print_cr("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) {

  unsigned int id = PSParallelCompact::perm_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);

}

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

  _region_data = 0;

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

  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(raw_bytes, raw_bytes, 10);

  const size_t granularity = os::vm_allocation_granularity();

  const size_t bytes = 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(bytes, rs_align, rs_align > 0);

  os::trace_page_sizes("par compact", raw_bytes, raw_bytes, page_sz, rs.base(),

                       rs.size());

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

  if (vspace != 0) {

    if (vspace->expand_by(bytes)) {

      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;

}

void ParallelCompactData::clear()

{

  memset(_region_data, 0, _region_vspace->committed_size());

}

void ParallelCompactData::clear_range(size_t beg_region, size_t end_region) {

  assert(beg_region <= _region_count, "beg_region out of range");

  assert(end_region <= _region_count, "end_region out of range");

  const size_t region_cnt = end_region - beg_region;

  memset(_region_data + beg_region, 0, region_cnt * sizeof(RegionData));

}

HeapWord* ParallelCompactData::partial_obj_end(size_t region_idx) const

{

  const RegionData* cur_cp = region(region_idx);

  const RegionData* const end_cp = region(region_count() - 1);

  HeapWord* result = region_to_addr(region_idx);

  if (cur_cp < end_cp) {

    do {

      result += cur_cp->partial_obj_size();

    } while (cur_cp->partial_obj_size() == RegionSize && ++cur_cp < end_cp);

  }

  return result;

}

void ParallelCompactData::add_obj(HeapWord* addr, size_t len)

{

  const size_t obj_ofs = pointer_delta(addr, _region_start);

  const size_t beg_region = obj_ofs >> Log2RegionSize;

  const size_t end_region = (obj_ofs + len - 1) >> Log2RegionSize;

  DEBUG_ONLY(Atomic::inc_ptr(&add_obj_count);)

  DEBUG_ONLY(Atomic::add_ptr(len, &add_obj_size);)

  if (beg_region == end_region) {

    // All in one region.

    _region_data[beg_region].add_live_obj(len);

    return;

  }

  // First region.

  const size_t beg_ofs = region_offset(addr);

  _region_data[beg_region].add_live_obj(RegionSize - beg_ofs);

  klassOop klass = ((oop)addr)->klass();

  // Middle regions--completely spanned by this object.

  for (size_t region = beg_region + 1; region < end_region; ++region) {

    _region_data[region].set_partial_obj_size(RegionSize);

    _region_data[region].set_partial_obj_addr(addr);

  }

  // Last region.

  const size_t end_ofs = region_offset(addr + len - 1);

  _region_data[end_region].set_partial_obj_size(end_ofs + 1);

  _region_data[end_region].set_partial_obj_addr(addr);

}

void

ParallelCompactData::summarize_dense_prefix(HeapWord* beg, HeapWord* end)

{

  assert(region_offset(beg) == 0, "not RegionSize aligned");

  assert(region_offset(end) == 0, "not RegionSize aligned");

  size_t cur_region = addr_to_region_idx(beg);

  const size_t end_region = addr_to_region_idx(end);

  HeapWord* addr = beg;

  while (cur_region < end_region) {

    _region_data[cur_region].set_destination(addr);

    _region_data[cur_region].set_destination_count(0);

    _region_data[cur_region].set_source_region(cur_region);

    _region_data[cur_region].set_data_location(addr);

    // Update live_obj_size so the region appears completely full.

    size_t live_size = RegionSize - _region_data[cur_region].partial_obj_size();

    _region_data[cur_region].set_live_obj_size(live_size);

    ++cur_region;

    addr += RegionSize;

  }

}

// Find the point at which a space can be split and, if necessary, record the

// split point.

//

// If the current src region (which overflowed the destination space) doesn't

// have a partial object, the split point is at the beginning of the current src

// region (an "easy" split, no extra bookkeeping required).

//

// If the current src region has a partial object, the split point is in the

// region where that partial object starts (call it the split_region).  If

// split_region has a partial object, then the split point is just after that

// partial object (a "hard" split where we have to record the split data and

// zero the partial_obj_size field).  With a "hard" split, we know that the

// partial_obj ends within split_region because the partial object that caused

// the overflow starts in split_region.  If split_region doesn't have a partial

// obj, then the split is at the beginning of split_region (another "easy"

// split).

HeapWord*

ParallelCompactData::summarize_split_space(size_t src_region,

                                           SplitInfo& split_info,

                                           HeapWord* destination,

                                           HeapWord* target_end,

                                           HeapWord** target_next)