/*

 * 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

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

  }

}

bool ParallelCompactData::summarize(HeapWord* target_beg, HeapWord* target_end,

                                    HeapWord* source_beg, HeapWord* source_end,

                                    HeapWord** target_next,

                                    HeapWord** source_next) {

  // This is too strict.

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

  if (TraceParallelOldGCSummaryPhase) {

    tty->print_cr("tb=" PTR_FORMAT " te=" PTR_FORMAT " "

                  "sb=" PTR_FORMAT " se=" PTR_FORMAT " "

                  "tn=" PTR_FORMAT " sn=" PTR_FORMAT,

                  target_beg, target_end,

                  source_beg, source_end,

                  target_next != 0 ? *target_next : (HeapWord*) 0,

                  source_next != 0 ? *source_next : (HeapWord*) 0);

  }

  size_t cur_region = addr_to_region_idx(source_beg);

  const size_t end_region = addr_to_region_idx(region_align_up(source_end));

  HeapWord *dest_addr = target_beg;

  while (cur_region < end_region) {

    size_t words = _region_data[cur_region].data_size();

#if     1

    assert(pointer_delta(target_end, dest_addr) >= words,

           "source region does not fit into target region");

#else

    // XXX - need some work on the corner cases here.  If the region does not

    // fit, then must either make sure any partial_obj from the region fits, or

    // "undo" the initial part of the partial_obj that is in the previous

    // region.

    if (dest_addr + words >= target_end) {

      // Let the caller know where to continue.

      *target_next = dest_addr;

      *source_next = region_to_addr(cur_region);

      return false;

    }

#endif  // #if 1

    _region_data[cur_region].set_destination(dest_addr);

    // Set the destination_count for cur_region, and if necessary, update

    // source_region for a destination region.  The source_region field is

    // updated if cur_region is the first (left-most) region to be copied to a

    // destination region.

    //

    // The destination_count calculation is a bit subtle.  A region that has

    // data that compacts into itself does not count itself as a destination.

    // This maintains the invariant that a zero count means the region is

    // available and can be claimed and then filled.

    if (words > 0) {

      HeapWord* const last_addr = dest_addr + words - 1;

      const size_t dest_region_1 = addr_to_region_idx(dest_addr);

      const size_t dest_region_2 = addr_to_region_idx(last_addr);

#if     0

      // Initially assume that the destination regions will be the same and

      // adjust the value below if necessary.  Under this assumption, if

      // cur_region == dest_region_2, then cur_region will be compacted

      // completely into itself.

      uint destination_count = cur_region == dest_region_2 ? 0 : 1;

      if (dest_region_1 != dest_region_2) {

        // Destination regions differ; adjust destination_count.

        destination_count += 1;

        // Data from cur_region will be copied to the start of dest_region_2.

        _region_data[dest_region_2].set_source_region(cur_region);

      } else if (region_offset(dest_addr) == 0) {

        // Data from cur_region will be copied to the start of the destination

        // region.

        _region_data[dest_region_1].set_source_region(cur_region);

      }

#else

      // Initially assume that the destination regions will be different and

      // adjust the value below if necessary.  Under this assumption, if

      // cur_region == dest_region2, then cur_region will be compacted partially

      // into dest_region_1 and partially into itself.

      uint destination_count = cur_region == dest_region_2 ? 1 : 2;

      if (dest_region_1 != dest_region_2) {

        // Data from cur_region will be copied to the start of dest_region_2.

        _region_data[dest_region_2].set_source_region(cur_region);

      } else {

        // Destination regions are the same; adjust destination_count.

        destination_count -= 1;

        if (region_offset(dest_addr) == 0) {

          // Data from cur_region will be copied to the start of the destination

          // region.

          _region_data[dest_region_1].set_source_region(cur_region);

        }

      }