/*

 * 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::Log2ChunkSize  = 9; // 512 words

const size_t ParallelCompactData::ChunkSize      = (size_t)1 << Log2ChunkSize;

const size_t ParallelCompactData::ChunkSizeBytes = ChunkSize << LogHeapWordSize;

const size_t ParallelCompactData::ChunkSizeOffsetMask = ChunkSize - 1;

const size_t ParallelCompactData::ChunkAddrOffsetMask = ChunkSizeBytes - 1;

const size_t ParallelCompactData::ChunkAddrMask  = ~ChunkAddrOffsetMask;

// 32-bit:  128 words covers 4 bitmap words

// 64-bit:  128 words covers 2 bitmap words

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

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

const size_t ParallelCompactData::BlockOffsetMask = BlockSize - 1;

const size_t ParallelCompactData::BlockMask       = ~BlockOffsetMask;

const size_t ParallelCompactData::BlocksPerChunk = ChunkSize / BlockSize;

const ParallelCompactData::ChunkData::chunk_sz_t

ParallelCompactData::ChunkData::dc_shift = 27;

const ParallelCompactData::ChunkData::chunk_sz_t

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

const ParallelCompactData::ChunkData::chunk_sz_t

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

const ParallelCompactData::ChunkData::chunk_sz_t

ParallelCompactData::ChunkData::los_mask = ~dc_mask;

const ParallelCompactData::ChunkData::chunk_sz_t

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

const ParallelCompactData::ChunkData::chunk_sz_t

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

#ifdef ASSERT

short   ParallelCompactData::BlockData::_cur_phase = 0;

#endif

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

// XXX beg - verification code; only works while we also mark in object headers

static void

verify_mark_bitmap(ParMarkBitMap& _mark_bitmap)

{

  ParallelScavengeHeap* heap = PSParallelCompact::gc_heap();

  PSPermGen* perm_gen = heap->perm_gen();

  PSOldGen* old_gen = heap->old_gen();

  PSYoungGen* young_gen = heap->young_gen();

  MutableSpace* perm_space = perm_gen->object_space();

  MutableSpace* old_space = old_gen->object_space();

  MutableSpace* eden_space = young_gen->eden_space();

  MutableSpace* from_space = young_gen->from_space();

  MutableSpace* to_space = young_gen->to_space();

  // 'from_space' here is the survivor space at the lower address.

  if (to_space->bottom() < from_space->bottom()) {

    from_space = to_space;

    to_space = young_gen->from_space();

  }

  HeapWord* boundaries[12];

  unsigned int bidx = 0;

  const unsigned int bidx_max = sizeof(boundaries) / sizeof(boundaries[0]);

  boundaries[0] = perm_space->bottom();

  boundaries[1] = perm_space->top();

  boundaries[2] = old_space->bottom();

  boundaries[3] = old_space->top();

  boundaries[4] = eden_space->bottom();

  boundaries[5] = eden_space->top();

  boundaries[6] = from_space->bottom();

  boundaries[7] = from_space->top();

  boundaries[8] = to_space->bottom();

  boundaries[9] = to_space->top();

  boundaries[10] = to_space->end();

  boundaries[11] = to_space->end();

  BitMap::idx_t beg_bit = 0;

  BitMap::idx_t end_bit;

  BitMap::idx_t tmp_bit;

  const BitMap::idx_t last_bit = _mark_bitmap.size();

  do {

    HeapWord* addr = _mark_bitmap.bit_to_addr(beg_bit);

    if (_mark_bitmap.is_marked(beg_bit)) {

      oop obj = (oop)addr;

      assert(obj->is_gc_marked(), "obj header is not marked");

      end_bit = _mark_bitmap.find_obj_end(beg_bit, last_bit);

      const size_t size = _mark_bitmap.obj_size(beg_bit, end_bit);

      assert(size == (size_t)obj->size(), "end bit wrong?");

      beg_bit = _mark_bitmap.find_obj_beg(beg_bit + 1, last_bit);

      assert(beg_bit > end_bit, "bit set in middle of an obj");

    } else {

      if (addr >= boundaries[bidx] && addr < boundaries[bidx + 1]) {

        // a dead object in the current space.

        oop obj = (oop)addr;

        end_bit = _mark_bitmap.addr_to_bit(addr + obj->size());

        assert(!obj->is_gc_marked(), "obj marked in header, not in bitmap");

        tmp_bit = beg_bit + 1;

        beg_bit = _mark_bitmap.find_obj_beg(tmp_bit, end_bit);

        assert(beg_bit == end_bit, "beg bit set in unmarked obj");

        beg_bit = _mark_bitmap.find_obj_end(tmp_bit, end_bit);

        assert(beg_bit == end_bit, "end bit set in unmarked obj");

      } else if (addr < boundaries[bidx + 2]) {

        // addr is between top in the current space and bottom in the next.

        end_bit = beg_bit + pointer_delta(boundaries[bidx + 2], addr);

        tmp_bit = beg_bit;

        beg_bit = _mark_bitmap.find_obj_beg(tmp_bit, end_bit);

        assert(beg_bit == end_bit, "beg bit set above top");

        beg_bit = _mark_bitmap.find_obj_end(tmp_bit, end_bit);

        assert(beg_bit == end_bit, "end bit set above top");

        bidx += 2;

      } else if (bidx < bidx_max - 2) {

        bidx += 2; // ???

      } else {

        tmp_bit = beg_bit;

        beg_bit = _mark_bitmap.find_obj_beg(tmp_bit, last_bit);

        assert(beg_bit == last_bit, "beg bit set outside heap");

        beg_bit = _mark_bitmap.find_obj_end(tmp_bit, last_bit);

        assert(beg_bit == last_bit, "end bit set outside heap");

      }

    }

  } while (beg_bit < last_bit);

}

// XXX end - verification code; only works while we also mark in object headers

#ifndef PRODUCT

const char* PSParallelCompact::space_names[] = {

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

};

void PSParallelCompact::print_chunk_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_chunk_idx(space->bottom()),

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

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

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

  }

}

void

print_generic_summary_chunk(size_t i, const ParallelCompactData::ChunkData* c)

{

#define CHUNK_IDX_FORMAT        SIZE_FORMAT_W("7")

#define CHUNK_DATA_FORMAT       SIZE_FORMAT_W("5")

  ParallelCompactData& sd = PSParallelCompact::summary_data();

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

  tty->print_cr(CHUNK_IDX_FORMAT " " PTR_FORMAT " "

                CHUNK_IDX_FORMAT " " PTR_FORMAT " "

                CHUNK_DATA_FORMAT " " CHUNK_DATA_FORMAT " "

                CHUNK_DATA_FORMAT " " CHUNK_IDX_FORMAT " %d",

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

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

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

#undef  CHUNK_IDX_FORMAT

#undef  CHUNK_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_chunk_idx(beg_addr);

  const size_t last = summary_data.addr_to_chunk_idx(end_addr);

  HeapWord* pdest = 0;

  while (i <= last) {

    ParallelCompactData::ChunkData* c = summary_data.chunk(i);

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

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

                            const ParallelCompactData::ChunkData* 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_chunk(), 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 chunk_size = ParallelCompactData::ChunkSize;

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

  const size_t end_chunk = summary_data.addr_to_chunk_idx(top_aligned_up);

  const ParallelCompactData::ChunkData* c = summary_data.chunk(end_chunk - 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 chunks at the beginning of the space.

  size_t full_chunk_count = 0;

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

  while (i < end_chunk && summary_data.chunk(i)->data_size() == chunk_size) {

    print_initial_summary_chunk(i, summary_data.chunk(i));

    ++full_chunk_count;

    ++i;

  }

  size_t live_to_right = live_in_space - full_chunk_count * chunk_size;

  double max_reclaimed_ratio = 0.0;

  size_t max_reclaimed_ratio_chunk = 0;

  size_t max_dead_to_right = 0;

  size_t max_live_to_right = 0;

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

  // chunk or to the right of it.  The remaining chunks are empty (and

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

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

    c = summary_data.chunk(i);

    HeapWord* const chunk_addr = summary_data.chunk_to_addr(i);

    const size_t used_to_right = pointer_delta(space->top(), chunk_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_chunk = i;

            max_dead_to_right = dead_to_right;

            max_live_to_right = live_to_right;

    }

    print_initial_summary_chunk(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 chunks are empty.  Print one more if there is one.

  if (i < end_chunk) {

    print_initial_summary_chunk(i, summary_data.chunk(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_chunk, 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;

  _chunk_vspace = 0;

  _chunk_data = 0;

  _chunk_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(chunk_align_down(_region_start) == _region_start,

         "region start not aligned");

  assert((region_size & ChunkSizeOffsetMask) == 0,

         "region size not a multiple of ChunkSize");

  bool result = initialize_chunk_data(region_size);

  // Initialize the block data if it will be used for updating pointers, or if

  // this is a debug build.

  if (!UseParallelOldGCChunkPointerCalc || trueInDebug) {

    result = result && initialize_block_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;

  }

  return 0;

}

bool ParallelCompactData::initialize_chunk_data(size_t region_size)

{

  const size_t count = (region_size + ChunkSizeOffsetMask) >> Log2ChunkSize;

  _chunk_vspace = create_vspace(count, sizeof(ChunkData));

  if (_chunk_vspace != 0) {

    _chunk_data = (ChunkData*)_chunk_vspace->reserved_low_addr();

    _chunk_count = count;

    return true;

  }

  return false;

}

bool ParallelCompactData::initialize_block_data(size_t region_size)

{

  const size_t count = (region_size + BlockOffsetMask) >> Log2BlockSize;

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

{

  if (_block_data) {

    memset(_block_data, 0, _block_vspace->committed_size());

  }

  memset(_chunk_data, 0, _chunk_vspace->committed_size());

}

void ParallelCompactData::clear_range(size_t beg_chunk, size_t end_chunk) {

  assert(beg_chunk <= _chunk_count, "beg_chunk out of range");

  assert(end_chunk <= _chunk_count, "end_chunk out of range");

  assert(ChunkSize % BlockSize == 0, "ChunkSize not a multiple of BlockSize");

  const size_t chunk_cnt = end_chunk - beg_chunk;

  if (_block_data) {

    const size_t blocks_per_chunk = ChunkSize / BlockSize;

    const size_t beg_block = beg_chunk * blocks_per_chunk;

    const size_t block_cnt = chunk_cnt * blocks_per_chunk;

    memset(_block_data + beg_block, 0, block_cnt * sizeof(BlockData));

  }

  memset(_chunk_data + beg_chunk, 0, chunk_cnt * sizeof(ChunkData));

}

HeapWord* ParallelCompactData::partial_obj_end(size_t chunk_idx) const

{

  const ChunkData* cur_cp = chunk(chunk_idx);

  const ChunkData* const end_cp = chunk(chunk_count() - 1);

  HeapWord* result = chunk_to_addr(chunk_idx);

  if (cur_cp < end_cp) {

    do {

      result += cur_cp->partial_obj_size();

    } while (cur_cp->partial_obj_size() == ChunkSize && ++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_chunk = obj_ofs >> Log2ChunkSize;

  const size_t end_chunk = (obj_ofs + len - 1) >> Log2ChunkSize;

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

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

  if (beg_chunk == end_chunk) {

    // All in one chunk.

    _chunk_data[beg_chunk].add_live_obj(len);

    return;

  }

  // First chunk.

  const size_t beg_ofs = chunk_offset(addr);

  _chunk_data[beg_chunk].add_live_obj(ChunkSize - beg_ofs);

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

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

  for (size_t chunk = beg_chunk + 1; chunk < end_chunk; ++chunk) {

    _chunk_data[chunk].set_partial_obj_size(ChunkSize);

    _chunk_data[chunk].set_partial_obj_addr(addr);

  }

  // Last chunk.

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

  _chunk_data[end_chunk].set_partial_obj_size(end_ofs + 1);

  _chunk_data[end_chunk].set_partial_obj_addr(addr);

}

void

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

{

  assert(chunk_offset(beg) == 0, "not ChunkSize aligned");