view src/share/vm/gc_implementation/parallelScavenge/psParallelCompact.cpp @ 453:c96030fff130

6684579: SoftReference processing can be made more efficient Summary: For current soft-ref clearing policies, we can decide at marking time if a soft-reference will definitely not be cleared, postponing the decision of whether it will definitely be cleared to the final reference processing phase. This can be especially beneficial in the case of concurrent collectors where the marking is usually concurrent but reference processing is usually not. Reviewed-by: jmasa
author ysr
date Thu, 20 Nov 2008 16:56:09 -0800
parents 0166ac265d53
children 27a80744a83b
line wrap: on
line source
/*
 * 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);
        }
      }
#endif  // #if 0

      _region_data[cur_region].set_destination_count(destination_count);
      _region_data[cur_region].set_data_location(region_to_addr(cur_region));
      dest_addr += words;
    }

    ++cur_region;
  }

  *target_next = dest_addr;
  return true;
}

HeapWord* ParallelCompactData::calc_new_pointer(HeapWord* addr) {
  assert(addr != NULL, "Should detect NULL oop earlier");
  assert(PSParallelCompact::gc_heap()->is_in(addr), "addr not in heap");
#ifdef ASSERT
  if (PSParallelCompact::mark_bitmap()->is_unmarked(addr)) {
    gclog_or_tty->print_cr("calc_new_pointer:: addr " PTR_FORMAT, addr);
  }
#endif
  assert(PSParallelCompact::mark_bitmap()->is_marked(addr), "obj not marked");

  // Region covering the object.
  size_t region_index = addr_to_region_idx(addr);
  const RegionData* const region_ptr = region(region_index);
  HeapWord* const region_addr = region_align_down(addr);

  assert(addr < region_addr + RegionSize, "Region does not cover object");
  assert(addr_to_region_ptr(region_addr) == region_ptr, "sanity check");

  HeapWord* result = region_ptr->destination();

  // If all the data in the region is live, then the new location of the object
  // can be calculated from the destination of the region plus the offset of the
  // object in the region.
  if (region_ptr->data_size() == RegionSize) {
    result += pointer_delta(addr, region_addr);
    return result;
  }

  // The new location of the object is
  //    region destination +
  //    size of the partial object extending onto the region +
  //    sizes of the live objects in the Region that are to the left of addr
  const size_t partial_obj_size = region_ptr->partial_obj_size();
  HeapWord* const search_start = region_addr + partial_obj_size;

  const ParMarkBitMap* bitmap = PSParallelCompact::mark_bitmap();
  size_t live_to_left = bitmap->live_words_in_range(search_start, oop(addr));

  result += partial_obj_size + live_to_left;
  assert(result <= addr, "object cannot move to the right");
  return result;
}

klassOop ParallelCompactData::calc_new_klass(klassOop old_klass) {
  klassOop updated_klass;
  if (PSParallelCompact::should_update_klass(old_klass)) {
    updated_klass = (klassOop) calc_new_pointer(old_klass);
  } else {
    updated_klass = old_klass;
  }

  return updated_klass;
}

#ifdef  ASSERT
void ParallelCompactData::verify_clear(const PSVirtualSpace* vspace)
{
  const size_t* const beg = (const size_t*)vspace->committed_low_addr();
  const size_t* const end = (const size_t*)vspace->committed_high_addr();
  for (const size_t* p = beg; p < end; ++p) {
    assert(*p == 0, "not zero");
  }
}

void ParallelCompactData::verify_clear()
{
  verify_clear(_region_vspace);
}
#endif  // #ifdef ASSERT

#ifdef NOT_PRODUCT
ParallelCompactData::RegionData* debug_region(size_t region_index) {
  ParallelCompactData& sd = PSParallelCompact::summary_data();
  return sd.region(region_index);
}
#endif

elapsedTimer        PSParallelCompact::_accumulated_time;
unsigned int        PSParallelCompact::_total_invocations = 0;
unsigned int        PSParallelCompact::_maximum_compaction_gc_num = 0;
jlong               PSParallelCompact::_time_of_last_gc = 0;
CollectorCounters*  PSParallelCompact::_counters = NULL;
ParMarkBitMap       PSParallelCompact::_mark_bitmap;
ParallelCompactData PSParallelCompact::_summary_data;

PSParallelCompact::IsAliveClosure PSParallelCompact::_is_alive_closure;

void PSParallelCompact::IsAliveClosure::do_object(oop p)   { ShouldNotReachHere(); }
bool PSParallelCompact::IsAliveClosure::do_object_b(oop p) { return mark_bitmap()->is_marked(p); }

void PSParallelCompact::KeepAliveClosure::do_oop(oop* p)       { PSParallelCompact::KeepAliveClosure::do_oop_work(p); }
void PSParallelCompact::KeepAliveClosure::do_oop(narrowOop* p) { PSParallelCompact::KeepAliveClosure::do_oop_work(p); }

PSParallelCompact::AdjustPointerClosure PSParallelCompact::_adjust_root_pointer_closure(true);
PSParallelCompact::AdjustPointerClosure PSParallelCompact::_adjust_pointer_closure(false);

void PSParallelCompact::AdjustPointerClosure::do_oop(oop* p)       { adjust_pointer(p, _is_root); }
void PSParallelCompact::AdjustPointerClosure::do_oop(narrowOop* p) { adjust_pointer(p, _is_root); }

void PSParallelCompact::FollowStackClosure::do_void() { follow_stack(_compaction_manager); }

void PSParallelCompact::MarkAndPushClosure::do_oop(oop* p)       { mark_and_push(_compaction_manager, p); }
void PSParallelCompact::MarkAndPushClosure::do_oop(narrowOop* p) { mark_and_push(_compaction_manager, p); }

void PSParallelCompact::post_initialize() {
  ParallelScavengeHeap* heap = gc_heap();
  assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");

  MemRegion mr = heap->reserved_region();
  _ref_processor = ReferenceProcessor::create_ref_processor(
    mr,                         // span
    true,                       // atomic_discovery
    true,                       // mt_discovery
    &_is_alive_closure,
    ParallelGCThreads,
    ParallelRefProcEnabled);
  _counters = new CollectorCounters("PSParallelCompact", 1);

  // Initialize static fields in ParCompactionManager.
  ParCompactionManager::initialize(mark_bitmap());
}

bool PSParallelCompact::initialize() {
  ParallelScavengeHeap* heap = gc_heap();
  assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
  MemRegion mr = heap->reserved_region();

  // Was the old gen get allocated successfully?
  if (!heap->old_gen()->is_allocated()) {
    return false;
  }

  initialize_space_info();
  initialize_dead_wood_limiter();

  if (!_mark_bitmap.initialize(mr)) {
    vm_shutdown_during_initialization("Unable to allocate bit map for "
      "parallel garbage collection for the requested heap size.");
    return false;
  }

  if (!_summary_data.initialize(mr)) {
    vm_shutdown_during_initialization("Unable to allocate tables for "
      "parallel garbage collection for the requested heap size.");
    return false;
  }

  return true;
}

void PSParallelCompact::initialize_space_info()
{
  memset(&_space_info, 0, sizeof(_space_info));

  ParallelScavengeHeap* heap = gc_heap();
  PSYoungGen* young_gen = heap->young_gen();
  MutableSpace* perm_space = heap->perm_gen()->object_space();

  _space_info[perm_space_id].set_space(perm_space);
  _space_info[old_space_id].set_space(heap->old_gen()->object_space());
  _space_info[eden_space_id].set_space(young_gen->eden_space());
  _space_info[from_space_id].set_space(young_gen->from_space());
  _space_info[to_space_id].set_space(young_gen->to_space());

  _space_info[perm_space_id].set_start_array(heap->perm_gen()->start_array());
  _space_info[old_space_id].set_start_array(heap->old_gen()->start_array());

  _space_info[perm_space_id].set_min_dense_prefix(perm_space->top());
  if (TraceParallelOldGCDensePrefix) {
    tty->print_cr("perm min_dense_prefix=" PTR_FORMAT,
                  _space_info[perm_space_id].min_dense_prefix());
  }
}

void PSParallelCompact::initialize_dead_wood_limiter()
{
  const size_t max = 100;
  _dwl_mean = double(MIN2(ParallelOldDeadWoodLimiterMean, max)) / 100.0;
  _dwl_std_dev = double(MIN2(ParallelOldDeadWoodLimiterStdDev, max)) / 100.0;
  _dwl_first_term = 1.0 / (sqrt(2.0 * M_PI) * _dwl_std_dev);
  DEBUG_ONLY(_dwl_initialized = true;)
  _dwl_adjustment = normal_distribution(1.0);
}

// Simple class for storing info about the heap at the start of GC, to be used
// after GC for comparison/printing.
class PreGCValues {
public:
  PreGCValues() { }
  PreGCValues(ParallelScavengeHeap* heap) { fill(heap); }

  void fill(ParallelScavengeHeap* heap) {
    _heap_used      = heap->used();
    _young_gen_used = heap->young_gen()->used_in_bytes();
    _old_gen_used   = heap->old_gen()->used_in_bytes();
    _perm_gen_used  = heap->perm_gen()->used_in_bytes();
  };

  size_t heap_used() const      { return _heap_used; }
  size_t young_gen_used() const { return _young_gen_used; }
  size_t old_gen_used() const   { return _old_gen_used; }
  size_t perm_gen_used() const  { return _perm_gen_used; }

private:
  size_t _heap_used;
  size_t _young_gen_used;
  size_t _old_gen_used;
  size_t _perm_gen_used;
};

void
PSParallelCompact::clear_data_covering_space(SpaceId id)
{
  // At this point, top is the value before GC, new_top() is the value that will
  // be set at the end of GC.  The marking bitmap is cleared to top; nothing
  // should be marked above top.  The summary data is cleared to the larger of
  // top & new_top.
  MutableSpace* const space = _space_info[id].space();
  HeapWord* const bot = space->bottom();
  HeapWord* const top = space->top();
  HeapWord* const max_top = MAX2(top, _space_info[id].new_top());

  const idx_t beg_bit = _mark_bitmap.addr_to_bit(bot);
  const idx_t end_bit = BitMap::word_align_up(_mark_bitmap.addr_to_bit(top));
  _mark_bitmap.clear_range(beg_bit, end_bit);

  const size_t beg_region = _summary_data.addr_to_region_idx(bot);
  const size_t end_region =
    _summary_data.addr_to_region_idx(_summary_data.region_align_up(max_top));
  _summary_data.clear_range(beg_region, end_region);
}

void PSParallelCompact::pre_compact(PreGCValues* pre_gc_values)
{
  // Update the from & to space pointers in space_info, since they are swapped
  // at each young gen gc.  Do the update unconditionally (even though a
  // promotion failure does not swap spaces) because an unknown number of minor
  // collections will have swapped the spaces an unknown number of times.
  TraceTime tm("pre compact", print_phases(), true, gclog_or_tty);
  ParallelScavengeHeap* heap = gc_heap();
  _space_info[from_space_id].set_space(heap->young_gen()->from_space());
  _space_info[to_space_id].set_space(heap->young_gen()->to_space());

  pre_gc_values->fill(heap);

  ParCompactionManager::reset();
  NOT_PRODUCT(_mark_bitmap.reset_counters());
  DEBUG_ONLY(add_obj_count = add_obj_size = 0;)
  DEBUG_ONLY(mark_bitmap_count = mark_bitmap_size = 0;)

  // Increment the invocation count
  heap->increment_total_collections(true);

  // We need to track unique mark sweep invocations as well.
  _total_invocations++;

  if (PrintHeapAtGC) {
    Universe::print_heap_before_gc();
  }

  // Fill in TLABs
  heap->accumulate_statistics_all_tlabs();
  heap->ensure_parsability(true);  // retire TLABs

  if (VerifyBeforeGC && heap->total_collections() >= VerifyGCStartAt) {
    HandleMark hm;  // Discard invalid handles created during verification
    gclog_or_tty->print(" VerifyBeforeGC:");
    Universe::verify(true);
  }

  // Verify object start arrays
  if (VerifyObjectStartArray &&
      VerifyBeforeGC) {
    heap->old_gen()->verify_object_start_array();
    heap->perm_gen()->verify_object_start_array();
  }

  DEBUG_ONLY(mark_bitmap()->verify_clear();)
  DEBUG_ONLY(summary_data().verify_clear();)

  // Have worker threads release resources the next time they run a task.
  gc_task_manager()->release_all_resources();
}

void PSParallelCompact::post_compact()
{
  TraceTime tm("post compact", print_phases(), true, gclog_or_tty);

  // Clear the marking bitmap and summary data and update top() in each space.
  for (unsigned int id = perm_space_id; id < last_space_id; ++id) {
    clear_data_covering_space(SpaceId(id));
    _space_info[id].space()->set_top(_space_info[id].new_top());
  }

  MutableSpace* const eden_space = _space_info[eden_space_id].space();
  MutableSpace* const from_space = _space_info[from_space_id].space();
  MutableSpace* const to_space   = _space_info[to_space_id].space();

  ParallelScavengeHeap* heap = gc_heap();
  bool eden_empty = eden_space->is_empty();
  if (!eden_empty) {
    eden_empty = absorb_live_data_from_eden(heap->size_policy(),
                                            heap->young_gen(), heap->old_gen());
  }

  // Update heap occupancy information which is used as input to the soft ref
  // clearing policy at the next gc.
  Universe::update_heap_info_at_gc();

  bool young_gen_empty = eden_empty && from_space->is_empty() &&
    to_space->is_empty();

  BarrierSet* bs = heap->barrier_set();
  if (bs->is_a(BarrierSet::ModRef)) {
    ModRefBarrierSet* modBS = (ModRefBarrierSet*)bs;
    MemRegion old_mr = heap->old_gen()->reserved();
    MemRegion perm_mr = heap->perm_gen()->reserved();
    assert(perm_mr.end() <= old_mr.start(), "Generations out of order");

    if (young_gen_empty) {
      modBS->clear(MemRegion(perm_mr.start(), old_mr.end()));
    } else {
      modBS->invalidate(MemRegion(perm_mr.start(), old_mr.end()));
    }
  }

  Threads::gc_epilogue();
  CodeCache::gc_epilogue();

  COMPILER2_PRESENT(DerivedPointerTable::update_pointers());

  ref_processor()->enqueue_discovered_references(NULL);

  if (ZapUnusedHeapArea) {
    heap->gen_mangle_unused_area();
  }

  // Update time of last GC
  reset_millis_since_last_gc();
}

HeapWord*
PSParallelCompact::compute_dense_prefix_via_density(const SpaceId id,
                                                    bool maximum_compaction)
{
  const size_t region_size = ParallelCompactData::RegionSize;
  const ParallelCompactData& sd = summary_data();

  const MutableSpace* const space = _space_info[id].space();
  HeapWord* const top_aligned_up = sd.region_align_up(space->top());
  const RegionData* const beg_cp = sd.addr_to_region_ptr(space->bottom());
  const RegionData* const end_cp = sd.addr_to_region_ptr(top_aligned_up);

  // Skip full regions at the beginning of the space--they are necessarily part
  // of the dense prefix.
  size_t full_count = 0;
  const RegionData* cp;
  for (cp = beg_cp; cp < end_cp && cp->data_size() == region_size; ++cp) {
    ++full_count;
  }

  assert(total_invocations() >= _maximum_compaction_gc_num, "sanity");
  const size_t gcs_since_max = total_invocations() - _maximum_compaction_gc_num;
  const bool interval_ended = gcs_since_max > HeapMaximumCompactionInterval;
  if (maximum_compaction || cp == end_cp || interval_ended) {
    _maximum_compaction_gc_num = total_invocations();
    return sd.region_to_addr(cp);
  }

  HeapWord* const new_top = _space_info[id].new_top();
  const size_t space_live = pointer_delta(new_top, space->bottom());
  const size_t space_used = space->used_in_words();
  const size_t space_capacity = space->capacity_in_words();

  const double cur_density = double(space_live) / space_capacity;
  const double deadwood_density =
    (1.0 - cur_density) * (1.0 - cur_density) * cur_density * cur_density;
  const size_t deadwood_goal = size_t(space_capacity * deadwood_density);

  if (TraceParallelOldGCDensePrefix) {
    tty->print_cr("cur_dens=%5.3f dw_dens=%5.3f dw_goal=" SIZE_FORMAT,
                  cur_density, deadwood_density, deadwood_goal);
    tty->print_cr("space_live=" SIZE_FORMAT " " "space_used=" SIZE_FORMAT " "
                  "space_cap=" SIZE_FORMAT,
                  space_live, space_used,
                  space_capacity);
  }

  // XXX - Use binary search?
  HeapWord* dense_prefix = sd.region_to_addr(cp);
  const RegionData* full_cp = cp;
  const RegionData* const top_cp = sd.addr_to_region_ptr(space->top() - 1);
  while (cp < end_cp) {
    HeapWord* region_destination = cp->destination();
    const size_t cur_deadwood = pointer_delta(dense_prefix, region_destination);
    if (TraceParallelOldGCDensePrefix && Verbose) {
      tty->print_cr("c#=" SIZE_FORMAT_W(4) " dst=" PTR_FORMAT " "
                    "dp=" SIZE_FORMAT_W(8) " " "cdw=" SIZE_FORMAT_W(8),
                    sd.region(cp), region_destination,
                    dense_prefix, cur_deadwood);
    }

    if (cur_deadwood >= deadwood_goal) {
      // Found the region that has the correct amount of deadwood to the left.
      // This typically occurs after crossing a fairly sparse set of regions, so
      // iterate backwards over those sparse regions, looking for the region
      // that has the lowest density of live objects 'to the right.'
      size_t space_to_left = sd.region(cp) * region_size;
      size_t live_to_left = space_to_left - cur_deadwood;
      size_t space_to_right = space_capacity - space_to_left;
      size_t live_to_right = space_live - live_to_left;
      double density_to_right = double(live_to_right) / space_to_right;
      while (cp > full_cp) {
        --cp;
        const size_t prev_region_live_to_right = live_to_right -
          cp->data_size();
        const size_t prev_region_space_to_right = space_to_right + region_size;
        double prev_region_density_to_right =
          double(prev_region_live_to_right) / prev_region_space_to_right;
        if (density_to_right <= prev_region_density_to_right) {
          return dense_prefix;
        }
        if (TraceParallelOldGCDensePrefix && Verbose) {
          tty->print_cr("backing up from c=" SIZE_FORMAT_W(4) " d2r=%10.8f "
                        "pc_d2r=%10.8f", sd.region(cp), density_to_right,
                        prev_region_density_to_right);
        }
        dense_prefix -= region_size;
        live_to_right = prev_region_live_to_right;
        space_to_right = prev_region_space_to_right;
        density_to_right = prev_region_density_to_right;
      }
      return dense_prefix;
    }

    dense_prefix += region_size;
    ++cp;
  }

  return dense_prefix;
}

#ifndef PRODUCT
void PSParallelCompact::print_dense_prefix_stats(const char* const algorithm,
                                                 const SpaceId id,
                                                 const bool maximum_compaction,
                                                 HeapWord* const addr)
{
  const size_t region_idx = summary_data().addr_to_region_idx(addr);
  RegionData* const cp = summary_data().region(region_idx);
  const MutableSpace* const space = _space_info[id].space();
  HeapWord* const new_top = _space_info[id].new_top();

  const size_t space_live = pointer_delta(new_top, space->bottom());
  const size_t dead_to_left = pointer_delta(addr, cp->destination());
  const size_t space_cap = space->capacity_in_words();
  const double dead_to_left_pct = double(dead_to_left) / space_cap;
  const size_t live_to_right = new_top - cp->destination();
  const size_t dead_to_right = space->top() - addr - live_to_right;

  tty->print_cr("%s=" PTR_FORMAT " dpc=" SIZE_FORMAT_W(5) " "
                "spl=" SIZE_FORMAT " "
                "d2l=" SIZE_FORMAT " d2l%%=%6.4f "
                "d2r=" SIZE_FORMAT " l2r=" SIZE_FORMAT
                " ratio=%10.8f",
                algorithm, addr, region_idx,
                space_live,
                dead_to_left, dead_to_left_pct,
                dead_to_right, live_to_right,
                double(dead_to_right) / live_to_right);
}
#endif  // #ifndef PRODUCT

// Return a fraction indicating how much of the generation can be treated as
// "dead wood" (i.e., not reclaimed).  The function uses a normal distribution
// based on the density of live objects in the generation to determine a limit,
// which is then adjusted so the return value is min_percent when the density is
// 1.
//
// The following table shows some return values for a different values of the
// standard deviation (ParallelOldDeadWoodLimiterStdDev); the mean is 0.5 and
// min_percent is 1.
//
//                          fraction allowed as dead wood
//         -----------------------------------------------------------------
// density std_dev=70 std_dev=75 std_dev=80 std_dev=85 std_dev=90 std_dev=95
// ------- ---------- ---------- ---------- ---------- ---------- ----------
// 0.00000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000
// 0.05000 0.03193096 0.02836880 0.02550828 0.02319280 0.02130337 0.01974941
// 0.10000 0.05247504 0.04547452 0.03988045 0.03537016 0.03170171 0.02869272
// 0.15000 0.07135702 0.06111390 0.05296419 0.04641639 0.04110601 0.03676066
// 0.20000 0.08831616 0.07509618 0.06461766 0.05622444 0.04943437 0.04388975
// 0.25000 0.10311208 0.08724696 0.07471205 0.06469760 0.05661313 0.05002313
// 0.30000 0.11553050 0.09741183 0.08313394 0.07175114 0.06257797 0.05511132
// 0.35000 0.12538832 0.10545958 0.08978741 0.07731366 0.06727491 0.05911289
// 0.40000 0.13253818 0.11128511 0.09459590 0.08132834 0.07066107 0.06199500
// 0.45000 0.13687208 0.11481163 0.09750361 0.08375387 0.07270534 0.06373386
// 0.50000 0.13832410 0.11599237 0.09847664 0.08456518 0.07338887 0.06431510
// 0.55000 0.13687208 0.11481163 0.09750361 0.08375387 0.07270534 0.06373386
// 0.60000 0.13253818 0.11128511 0.09459590 0.08132834 0.07066107 0.06199500
// 0.65000 0.12538832 0.10545958 0.08978741 0.07731366 0.06727491 0.05911289
// 0.70000 0.11553050 0.09741183 0.08313394 0.07175114 0.06257797 0.05511132
// 0.75000 0.10311208 0.08724696 0.07471205 0.06469760 0.05661313 0.05002313
// 0.80000 0.08831616 0.07509618 0.06461766 0.05622444 0.04943437 0.04388975
// 0.85000 0.07135702 0.06111390 0.05296419 0.04641639 0.04110601 0.03676066
// 0.90000 0.05247504 0.04547452 0.03988045 0.03537016 0.03170171 0.02869272
// 0.95000 0.03193096 0.02836880 0.02550828 0.02319280 0.02130337 0.01974941
// 1.00000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000

double PSParallelCompact::dead_wood_limiter(double density, size_t min_percent)
{
  assert(_dwl_initialized, "uninitialized");

  // The raw limit is the value of the normal distribution at x = density.
  const double raw_limit = normal_distribution(density);

  // Adjust the raw limit so it becomes the minimum when the density is 1.
  //
  // First subtract the adjustment value (which is simply the precomputed value
  // normal_distribution(1.0)); this yields a value of 0 when the density is 1.
  // Then add the minimum value, so the minimum is returned when the density is
  // 1.  Finally, prevent negative values, which occur when the mean is not 0.5.
  const double min = double(min_percent) / 100.0;
  const double limit = raw_limit - _dwl_adjustment + min;
  return MAX2(limit, 0.0);
}

ParallelCompactData::RegionData*
PSParallelCompact::first_dead_space_region(const RegionData* beg,
                                           const RegionData* end)
{
  const size_t region_size = ParallelCompactData::RegionSize;
  ParallelCompactData& sd = summary_data();
  size_t left = sd.region(beg);
  size_t right = end > beg ? sd.region(end) - 1 : left;

  // Binary search.
  while (left < right) {
    // Equivalent to (left + right) / 2, but does not overflow.
    const size_t middle = left + (right - left) / 2;
    RegionData* const middle_ptr = sd.region(middle);
    HeapWord* const dest = middle_ptr->destination();
    HeapWord* const addr = sd.region_to_addr(middle);
    assert(dest != NULL, "sanity");
    assert(dest <= addr, "must move left");

    if (middle > left && dest < addr) {
      right = middle - 1;
    } else if (middle < right && middle_ptr->data_size() == region_size) {
      left = middle + 1;
    } else {
      return middle_ptr;
    }
  }
  return sd.region(left);
}

ParallelCompactData::RegionData*
PSParallelCompact::dead_wood_limit_region(const RegionData* beg,
                                          const RegionData* end,
                                          size_t dead_words)
{
  ParallelCompactData& sd = summary_data();
  size_t left = sd.region(beg);
  size_t right = end > beg ? sd.region(end) - 1 : left;

  // Binary search.
  while (left < right) {
    // Equivalent to (left + right) / 2, but does not overflow.
    const size_t middle = left + (right - left) / 2;
    RegionData* const middle_ptr = sd.region(middle);
    HeapWord* const dest = middle_ptr->destination();
    HeapWord* const addr = sd.region_to_addr(middle);
    assert(dest != NULL, "sanity");
    assert(dest <= addr, "must move left");

    const size_t dead_to_left = pointer_delta(addr, dest);
    if (middle > left && dead_to_left > dead_words) {
      right = middle - 1;
    } else if (middle < right && dead_to_left < dead_words) {
      left = middle + 1;
    } else {
      return middle_ptr;
    }
  }
  return sd.region(left);
}

// The result is valid during the summary phase, after the initial summarization
// of each space into itself, and before final summarization.
inline double
PSParallelCompact::reclaimed_ratio(const RegionData* const cp,
                                   HeapWord* const bottom,
                                   HeapWord* const top,
                                   HeapWord* const new_top)
{
  ParallelCompactData& sd = summary_data();

  assert(cp != NULL, "sanity");
  assert(bottom != NULL, "sanity");
  assert(top != NULL, "sanity");
  assert(new_top != NULL, "sanity");
  assert(top >= new_top, "summary data problem?");
  assert(new_top > bottom, "space is empty; should not be here");
  assert(new_top >= cp->destination(), "sanity");
  assert(top >= sd.region_to_addr(cp), "sanity");

  HeapWord* const destination = cp->destination();
  const size_t dense_prefix_live  = pointer_delta(destination, bottom);
  const size_t compacted_region_live = pointer_delta(new_top, destination);
  const size_t compacted_region_used = pointer_delta(top,
                                                     sd.region_to_addr(cp));
  const size_t reclaimable = compacted_region_used - compacted_region_live;

  const double divisor = dense_prefix_live + 1.25 * compacted_region_live;
  return double(reclaimable) / divisor;
}

// Return the address of the end of the dense prefix, a.k.a. the start of the
// compacted region.  The address is always on a region boundary.
//
// Completely full regions at the left are skipped, since no compaction can
// occur in those regions.  Then the maximum amount of dead wood to allow is
// computed, based on the density (amount live / capacity) of the generation;
// the region with approximately that amount of dead space to the left is
// identified as the limit region.  Regions between the last completely full
// region and the limit region are scanned and the one that has the best
// (maximum) reclaimed_ratio() is selected.
HeapWord*
PSParallelCompact::compute_dense_prefix(const SpaceId id,
                                        bool maximum_compaction)
{
  const size_t region_size = ParallelCompactData::RegionSize;
  const ParallelCompactData& sd = summary_data();

  const MutableSpace* const space = _space_info[id].space();
  HeapWord* const top = space->top();
  HeapWord* const top_aligned_up = sd.region_align_up(top);
  HeapWord* const new_top = _space_info[id].new_top();
  HeapWord* const new_top_aligned_up = sd.region_align_up(new_top);
  HeapWord* const bottom = space->bottom();
  const RegionData* const beg_cp = sd.addr_to_region_ptr(bottom);
  const RegionData* const top_cp = sd.addr_to_region_ptr(top_aligned_up);
  const RegionData* const new_top_cp =
    sd.addr_to_region_ptr(new_top_aligned_up);

  // Skip full regions at the beginning of the space--they are necessarily part
  // of the dense prefix.
  const RegionData* const full_cp = first_dead_space_region(beg_cp, new_top_cp);
  assert(full_cp->destination() == sd.region_to_addr(full_cp) ||
         space->is_empty(), "no dead space allowed to the left");
  assert(full_cp->data_size() < region_size || full_cp == new_top_cp - 1,
         "region must have dead space");

  // The gc number is saved whenever a maximum compaction is done, and used to
  // determine when the maximum compaction interval has expired.  This avoids
  // successive max compactions for different reasons.
  assert(total_invocations() >= _maximum_compaction_gc_num, "sanity");
  const size_t gcs_since_max = total_invocations() - _maximum_compaction_gc_num;
  const bool interval_ended = gcs_since_max > HeapMaximumCompactionInterval ||
    total_invocations() == HeapFirstMaximumCompactionCount;
  if (maximum_compaction || full_cp == top_cp || interval_ended) {
    _maximum_compaction_gc_num = total_invocations();
    return sd.region_to_addr(full_cp);
  }

  const size_t space_live = pointer_delta(new_top, bottom);
  const size_t space_used = space->used_in_words();
  const size_t space_capacity = space->capacity_in_words();

  const double density = double(space_live) / double(space_capacity);
  const size_t min_percent_free =
          id == perm_space_id ? PermMarkSweepDeadRatio : MarkSweepDeadRatio;
  const double limiter = dead_wood_limiter(density, min_percent_free);
  const size_t dead_wood_max = space_used - space_live;
  const size_t dead_wood_limit = MIN2(size_t(space_capacity * limiter),
                                      dead_wood_max);

  if (TraceParallelOldGCDensePrefix) {
    tty->print_cr("space_live=" SIZE_FORMAT " " "space_used=" SIZE_FORMAT " "
                  "space_cap=" SIZE_FORMAT,
                  space_live, space_used,
                  space_capacity);
    tty->print_cr("dead_wood_limiter(%6.4f, %d)=%6.4f "
                  "dead_wood_max=" SIZE_FORMAT " dead_wood_limit=" SIZE_FORMAT,
                  density, min_percent_free, limiter,
                  dead_wood_max, dead_wood_limit);
  }

  // Locate the region with the desired amount of dead space to the left.
  const RegionData* const limit_cp =
    dead_wood_limit_region(full_cp, top_cp, dead_wood_limit);

  // Scan from the first region with dead space to the limit region and find the
  // one with the best (largest) reclaimed ratio.
  double best_ratio = 0.0;
  const RegionData* best_cp = full_cp;
  for (const RegionData* cp = full_cp; cp < limit_cp; ++cp) {
    double tmp_ratio = reclaimed_ratio(cp, bottom, top, new_top);
    if (tmp_ratio > best_ratio) {
      best_cp = cp;
      best_ratio = tmp_ratio;
    }
  }

#if     0
  // Something to consider:  if the region with the best ratio is 'close to' the
  // first region w/free space, choose the first region with free space
  // ("first-free").  The first-free region is usually near the start of the
  // heap, which means we are copying most of the heap already, so copy a bit
  // more to get complete compaction.
  if (pointer_delta(best_cp, full_cp, sizeof(RegionData)) < 4) {
    _maximum_compaction_gc_num = total_invocations();
    best_cp = full_cp;
  }
#endif  // #if 0

  return sd.region_to_addr(best_cp);
}

void PSParallelCompact::summarize_spaces_quick()
{
  for (unsigned int i = 0; i < last_space_id; ++i) {
    const MutableSpace* space = _space_info[i].space();
    bool result = _summary_data.summarize(space->bottom(), space->end(),
                                          space->bottom(), space->top(),
                                          _space_info[i].new_top_addr());
    assert(result, "should never fail");
    _space_info[i].set_dense_prefix(space->bottom());
  }
}

void PSParallelCompact::fill_dense_prefix_end(SpaceId id)
{
  HeapWord* const dense_prefix_end = dense_prefix(id);
  const RegionData* region = _summary_data.addr_to_region_ptr(dense_prefix_end);
  const idx_t dense_prefix_bit = _mark_bitmap.addr_to_bit(dense_prefix_end);
  if (dead_space_crosses_boundary(region, dense_prefix_bit)) {
    // Only enough dead space is filled so that any remaining dead space to the
    // left is larger than the minimum filler object.  (The remainder is filled
    // during the copy/update phase.)
    //
    // The size of the dead space to the right of the boundary is not a
    // concern, since compaction will be able to use whatever space is
    // available.
    //
    // Here '||' is the boundary, 'x' represents a don't care bit and a box
    // surrounds the space to be filled with an object.
    //
    // In the 32-bit VM, each bit represents two 32-bit words:
    //                              +---+
    // a) beg_bits:  ...  x   x   x | 0 | ||   0   x  x  ...
    //    end_bits:  ...  x   x   x | 0 | ||   0   x  x  ...
    //                              +---+
    //
    // In the 64-bit VM, each bit represents one 64-bit word:
    //                              +------------+
    // b) beg_bits:  ...  x   x   x | 0   ||   0 | x  x  ...
    //    end_bits:  ...  x   x   1 | 0   ||   0 | x  x  ...
    //                              +------------+
    //                          +-------+
    // c) beg_bits:  ...  x   x | 0   0 | ||   0   x  x  ...
    //    end_bits:  ...  x   1 | 0   0 | ||   0   x  x  ...
    //                          +-------+
    //                      +-----------+
    // d) beg_bits:  ...  x | 0   0   0 | ||   0   x  x  ...
    //    end_bits:  ...  1 | 0   0   0 | ||   0   x  x  ...
    //                      +-----------+
    //                          +-------+
    // e) beg_bits:  ...  0   0 | 0   0 | ||   0   x  x  ...
    //    end_bits:  ...  0   0 | 0   0 | ||   0   x  x  ...
    //                          +-------+

    // Initially assume case a, c or e will apply.
    size_t obj_len = (size_t)oopDesc::header_size();
    HeapWord* obj_beg = dense_prefix_end - obj_len;

#ifdef  _LP64
    if (_mark_bitmap.is_obj_end(dense_prefix_bit - 2)) {
      // Case b above.
      obj_beg = dense_prefix_end - 1;
    } else if (!_mark_bitmap.is_obj_end(dense_prefix_bit - 3) &&
               _mark_bitmap.is_obj_end(dense_prefix_bit - 4)) {
      // Case d above.
      obj_beg = dense_prefix_end - 3;
      obj_len = 3;
    }
#endif  // #ifdef _LP64

    MemRegion region(obj_beg, obj_len);
    SharedHeap::fill_region_with_object(region);
    _mark_bitmap.mark_obj(obj_beg, obj_len);
    _summary_data.add_obj(obj_beg, obj_len);
    assert(start_array(id) != NULL, "sanity");
    start_array(id)->allocate_block(obj_beg);
  }
}

void
PSParallelCompact::summarize_space(SpaceId id, bool maximum_compaction)
{
  assert(id < last_space_id, "id out of range");
  assert(_space_info[id].dense_prefix() == _space_info[id].space()->bottom(),
         "should have been set in summarize_spaces_quick()");

  const MutableSpace* space = _space_info[id].space();
  if (_space_info[id].new_top() != space->bottom()) {
    HeapWord* dense_prefix_end = compute_dense_prefix(id, maximum_compaction);
    _space_info[id].set_dense_prefix(dense_prefix_end);

#ifndef PRODUCT
    if (TraceParallelOldGCDensePrefix) {
      print_dense_prefix_stats("ratio", id, maximum_compaction,
                               dense_prefix_end);
      HeapWord* addr = compute_dense_prefix_via_density(id, maximum_compaction);
      print_dense_prefix_stats("density", id, maximum_compaction, addr);
    }
#endif  // #ifndef PRODUCT

    // If dead space crosses the dense prefix boundary, it is (at least
    // partially) filled with a dummy object, marked live and added to the
    // summary data.  This simplifies the copy/update phase and must be done
    // before the final locations of objects are determined, to prevent leaving
    // a fragment of dead space that is too small to fill with an object.
    if (!maximum_compaction && dense_prefix_end != space->bottom()) {
      fill_dense_prefix_end(id);
    }

    // Compute the destination of each Region, and thus each object.
    _summary_data.summarize_dense_prefix(space->bottom(), dense_prefix_end);
    _summary_data.summarize(dense_prefix_end, space->end(),
                            dense_prefix_end, space->top(),
                            _space_info[id].new_top_addr());
  }

  if (TraceParallelOldGCSummaryPhase) {
    const size_t region_size = ParallelCompactData::RegionSize;
    HeapWord* const dense_prefix_end = _space_info[id].dense_prefix();
    const size_t dp_region = _summary_data.addr_to_region_idx(dense_prefix_end);
    const size_t dp_words = pointer_delta(dense_prefix_end, space->bottom());
    HeapWord* const new_top = _space_info[id].new_top();
    const HeapWord* nt_aligned_up = _summary_data.region_align_up(new_top);
    const size_t cr_words = pointer_delta(nt_aligned_up, dense_prefix_end);
    tty->print_cr("id=%d cap=" SIZE_FORMAT " dp=" PTR_FORMAT " "
                  "dp_region=" SIZE_FORMAT " " "dp_count=" SIZE_FORMAT " "
                  "cr_count=" SIZE_FORMAT " " "nt=" PTR_FORMAT,
                  id, space->capacity_in_words(), dense_prefix_end,
                  dp_region, dp_words / region_size,
                  cr_words / region_size, new_top);
  }
}

void PSParallelCompact::summary_phase(ParCompactionManager* cm,
                                      bool maximum_compaction)
{
  EventMark m("2 summarize");
  TraceTime tm("summary phase", print_phases(), true, gclog_or_tty);
  // trace("2");

#ifdef  ASSERT
  if (TraceParallelOldGCMarkingPhase) {
    tty->print_cr("add_obj_count=" SIZE_FORMAT " "
                  "add_obj_bytes=" SIZE_FORMAT,
                  add_obj_count, add_obj_size * HeapWordSize);
    tty->print_cr("mark_bitmap_count=" SIZE_FORMAT " "
                  "mark_bitmap_bytes=" SIZE_FORMAT,
                  mark_bitmap_count, mark_bitmap_size * HeapWordSize);
  }
#endif  // #ifdef ASSERT

  // Quick summarization of each space into itself, to see how much is live.
  summarize_spaces_quick();

  if (TraceParallelOldGCSummaryPhase) {
    tty->print_cr("summary_phase:  after summarizing each space to self");
    Universe::print();
    NOT_PRODUCT(print_region_ranges());
    if (Verbose) {
      NOT_PRODUCT(print_initial_summary_data(_summary_data, _space_info));
    }
  }

  // The amount of live data that will end up in old space (assuming it fits).
  size_t old_space_total_live = 0;
  unsigned int id;
  for (id = old_space_id; id < last_space_id; ++id) {
    old_space_total_live += pointer_delta(_space_info[id].new_top(),
                                          _space_info[id].space()->bottom());
  }

  const MutableSpace* old_space = _space_info[old_space_id].space();
  if (old_space_total_live > old_space->capacity_in_words()) {
    // XXX - should also try to expand
    maximum_compaction = true;
  } else if (!UseParallelOldGCDensePrefix) {
    maximum_compaction = true;
  }

  // Permanent and Old generations.
  summarize_space(perm_space_id, maximum_compaction);
  summarize_space(old_space_id, maximum_compaction);

  // Summarize the remaining spaces (those in the young gen) into old space.  If
  // the live data from a space doesn't fit, the existing summarization is left
  // intact, so the data is compacted down within the space itself.
  HeapWord** new_top_addr = _space_info[old_space_id].new_top_addr();
  HeapWord* const target_space_end = old_space->end();
  for (id = eden_space_id; id < last_space_id; ++id) {
    const MutableSpace* space = _space_info[id].space();
    const size_t live = pointer_delta(_space_info[id].new_top(),
                                      space->bottom());
    const size_t available = pointer_delta(target_space_end, *new_top_addr);
    if (live > 0 && live <= available) {
      // All the live data will fit.
      if (TraceParallelOldGCSummaryPhase) {
        tty->print_cr("summarizing %d into old_space @ " PTR_FORMAT,
                      id, *new_top_addr);
      }
      _summary_data.summarize(*new_top_addr, target_space_end,
                              space->bottom(), space->top(),
                              new_top_addr);

      // Clear the source_region field for each region in the space.
      HeapWord* const new_top = _space_info[id].new_top();
      HeapWord* const clear_end = _summary_data.region_align_up(new_top);
      RegionData* beg_region =
        _summary_data.addr_to_region_ptr(space->bottom());
      RegionData* end_region = _summary_data.addr_to_region_ptr(clear_end);
      while (beg_region < end_region) {
        beg_region->set_source_region(0);
        ++beg_region;
      }

      // Reset the new_top value for the space.
      _space_info[id].set_new_top(space->bottom());
    }
  }

  if (TraceParallelOldGCSummaryPhase) {
    tty->print_cr("summary_phase:  after final summarization");
    Universe::print();
    NOT_PRODUCT(print_region_ranges());
    if (Verbose) {
      NOT_PRODUCT(print_generic_summary_data(_summary_data, _space_info));
    }
  }
}

// This method should contain all heap-specific policy for invoking a full
// collection.  invoke_no_policy() will only attempt to compact the heap; it
// will do nothing further.  If we need to bail out for policy reasons, scavenge
// before full gc, or any other specialized behavior, it needs to be added here.
//
// Note that this method should only be called from the vm_thread while at a
// safepoint.
void PSParallelCompact::invoke(bool maximum_heap_compaction) {
  assert(SafepointSynchronize::is_at_safepoint(), "should be at safepoint");
  assert(Thread::current() == (Thread*)VMThread::vm_thread(),
         "should be in vm thread");
  ParallelScavengeHeap* heap = gc_heap();
  GCCause::Cause gc_cause = heap->gc_cause();
  assert(!heap->is_gc_active(), "not reentrant");

  PSAdaptiveSizePolicy* policy = heap->size_policy();

  // Before each allocation/collection attempt, find out from the
  // policy object if GCs are, on the whole, taking too long. If so,
  // bail out without attempting a collection.  The exceptions are
  // for explicitly requested GC's.
  if (!policy->gc_time_limit_exceeded() ||
      GCCause::is_user_requested_gc(gc_cause) ||
      GCCause::is_serviceability_requested_gc(gc_cause)) {
    IsGCActiveMark mark;

    if (ScavengeBeforeFullGC) {
      PSScavenge::invoke_no_policy();
    }

    PSParallelCompact::invoke_no_policy(maximum_heap_compaction);
  }
}

bool ParallelCompactData::region_contains(size_t region_index, HeapWord* addr) {
  size_t addr_region_index = addr_to_region_idx(addr);
  return region_index == addr_region_index;
}

// This method contains no policy. You should probably
// be calling invoke() instead.
void PSParallelCompact::invoke_no_policy(bool maximum_heap_compaction) {
  assert(SafepointSynchronize::is_at_safepoint(), "must be at a safepoint");
  assert(ref_processor() != NULL, "Sanity");

  if (GC_locker::check_active_before_gc()) {
    return;
  }

  TimeStamp marking_start;
  TimeStamp compaction_start;
  TimeStamp collection_exit;

  ParallelScavengeHeap* heap = gc_heap();
  GCCause::Cause gc_cause = heap->gc_cause();
  PSYoungGen* young_gen = heap->young_gen();
  PSOldGen* old_gen = heap->old_gen();
  PSPermGen* perm_gen = heap->perm_gen();
  PSAdaptiveSizePolicy* size_policy = heap->size_policy();

  if (ZapUnusedHeapArea) {
    // Save information needed to minimize mangling
    heap->record_gen_tops_before_GC();
  }

  _print_phases = PrintGCDetails && PrintParallelOldGCPhaseTimes;

  // Make sure data structures are sane, make the heap parsable, and do other
  // miscellaneous bookkeeping.
  PreGCValues pre_gc_values;
  pre_compact(&pre_gc_values);

  // Get the compaction manager reserved for the VM thread.
  ParCompactionManager* const vmthread_cm =
    ParCompactionManager::manager_array(gc_task_manager()->workers());

  // Place after pre_compact() where the number of invocations is incremented.
  AdaptiveSizePolicyOutput(size_policy, heap->total_collections());

  {
    ResourceMark rm;
    HandleMark hm;

    const bool is_system_gc = gc_cause == GCCause::_java_lang_system_gc;

    // This is useful for debugging but don't change the output the
    // the customer sees.
    const char* gc_cause_str = "Full GC";
    if (is_system_gc && PrintGCDetails) {
      gc_cause_str = "Full GC (System)";
    }
    gclog_or_tty->date_stamp(PrintGC && PrintGCDateStamps);
    TraceCPUTime tcpu(PrintGCDetails, true, gclog_or_tty);
    TraceTime t1(gc_cause_str, PrintGC, !PrintGCDetails, gclog_or_tty);
    TraceCollectorStats tcs(counters());
    TraceMemoryManagerStats tms(true /* Full GC */);

    if (TraceGen1Time) accumulated_time()->start();

    // Let the size policy know we're starting
    size_policy->major_collection_begin();

    // When collecting the permanent generation methodOops may be moving,
    // so we either have to flush all bcp data or convert it into bci.
    CodeCache::gc_prologue();
    Threads::gc_prologue();

    NOT_PRODUCT(ref_processor()->verify_no_references_recorded());
    COMPILER2_PRESENT(DerivedPointerTable::clear());

    ref_processor()->enable_discovery();
    ref_processor()->snap_policy(maximum_heap_compaction);

    bool marked_for_unloading = false;

    marking_start.update();
    marking_phase(vmthread_cm, maximum_heap_compaction);

#ifndef PRODUCT
    if (TraceParallelOldGCMarkingPhase) {
      gclog_or_tty->print_cr("marking_phase: cas_tries %d  cas_retries %d "
        "cas_by_another %d",
        mark_bitmap()->cas_tries(), mark_bitmap()->cas_retries(),
        mark_bitmap()->cas_by_another());
    }
#endif  // #ifndef PRODUCT

    bool max_on_system_gc = UseMaximumCompactionOnSystemGC && is_system_gc;
    summary_phase(vmthread_cm, maximum_heap_compaction || max_on_system_gc);

    COMPILER2_PRESENT(assert(DerivedPointerTable::is_active(), "Sanity"));
    COMPILER2_PRESENT(DerivedPointerTable::set_active(false));

    // adjust_roots() updates Universe::_intArrayKlassObj which is
    // needed by the compaction for filling holes in the dense prefix.
    adjust_roots();

    compaction_start.update();
    // Does the perm gen always have to be done serially because
    // klasses are used in the update of an object?
    compact_perm(vmthread_cm);

    if (UseParallelOldGCCompacting) {
      compact();
    } else {
      compact_serial(vmthread_cm);
    }

    // Reset the mark bitmap, summary data, and do other bookkeeping.  Must be
    // done before resizing.
    post_compact();

    // Let the size policy know we're done
    size_policy->major_collection_end(old_gen->used_in_bytes(), gc_cause);

    if (UseAdaptiveSizePolicy) {
      if (PrintAdaptiveSizePolicy) {
        gclog_or_tty->print("AdaptiveSizeStart: ");
        gclog_or_tty->stamp();
        gclog_or_tty->print_cr(" collection: %d ",
                       heap->total_collections());
        if (Verbose) {
          gclog_or_tty->print("old_gen_capacity: %d young_gen_capacity: %d"
            " perm_gen_capacity: %d ",
            old_gen->capacity_in_bytes(), young_gen->capacity_in_bytes(),
            perm_gen->capacity_in_bytes());
        }
      }

      // Don't check if the size_policy is ready here.  Let
      // the size_policy check that internally.
      if (UseAdaptiveGenerationSizePolicyAtMajorCollection &&
          ((gc_cause != GCCause::_java_lang_system_gc) ||
            UseAdaptiveSizePolicyWithSystemGC)) {
        // Calculate optimal free space amounts
        assert(young_gen->max_size() >
          young_gen->from_space()->capacity_in_bytes() +
          young_gen->to_space()->capacity_in_bytes(),
          "Sizes of space in young gen are out-of-bounds");
        size_t max_eden_size = young_gen->max_size() -
          young_gen->from_space()->capacity_in_bytes() -
          young_gen->to_space()->capacity_in_bytes();
        size_policy->compute_generation_free_space(
                              young_gen->used_in_bytes(),
                              young_gen->eden_space()->used_in_bytes(),
                              old_gen->used_in_bytes(),
                              perm_gen->used_in_bytes(),
                              young_gen->eden_space()->capacity_in_bytes(),
                              old_gen->max_gen_size(),
                              max_eden_size,
                              true /* full gc*/,
                              gc_cause);

        heap->resize_old_gen(
          size_policy->calculated_old_free_size_in_bytes());

        // Don't resize the young generation at an major collection.  A
        // desired young generation size may have been calculated but
        // resizing the young generation complicates the code because the
        // resizing of the old generation may have moved the boundary
        // between the young generation and the old generation.  Let the
        // young generation resizing happen at the minor collections.
      }
      if (PrintAdaptiveSizePolicy) {
        gclog_or_tty->print_cr("AdaptiveSizeStop: collection: %d ",
                       heap->total_collections());
      }
    }

    if (UsePerfData) {
      PSGCAdaptivePolicyCounters* const counters = heap->gc_policy_counters();
      counters->update_counters();
      counters->update_old_capacity(old_gen->capacity_in_bytes());
      counters->update_young_capacity(young_gen->capacity_in_bytes());
    }

    heap->resize_all_tlabs();

    // We collected the perm gen, so we'll resize it here.
    perm_gen->compute_new_size(pre_gc_values.perm_gen_used());

    if (TraceGen1Time) accumulated_time()->stop();

    if (PrintGC) {
      if (PrintGCDetails) {
        // No GC timestamp here.  This is after GC so it would be confusing.
        young_gen->print_used_change(pre_gc_values.young_gen_used());
        old_gen->print_used_change(pre_gc_values.old_gen_used());
        heap->print_heap_change(pre_gc_values.heap_used());
        // Print perm gen last (print_heap_change() excludes the perm gen).
        perm_gen->print_used_change(pre_gc_values.perm_gen_used());
      } else {
        heap->print_heap_change(pre_gc_values.heap_used());
      }
    }

    // Track memory usage and detect low memory
    MemoryService::track_memory_usage();
    heap->update_counters();

    if (PrintGCDetails) {
      if (size_policy->print_gc_time_limit_would_be_exceeded()) {
        if (size_policy->gc_time_limit_exceeded()) {
          gclog_or_tty->print_cr("      GC time is exceeding GCTimeLimit "
            "of %d%%", GCTimeLimit);
        } else {
          gclog_or_tty->print_cr("      GC time would exceed GCTimeLimit "
            "of %d%%", GCTimeLimit);
        }
      }
      size_policy->set_print_gc_time_limit_would_be_exceeded(false);
    }
  }

  if (VerifyAfterGC && heap->total_collections() >= VerifyGCStartAt) {
    HandleMark hm;  // Discard invalid handles created during verification
    gclog_or_tty->print(" VerifyAfterGC:");
    Universe::verify(false);
  }

  // Re-verify object start arrays
  if (VerifyObjectStartArray &&
      VerifyAfterGC) {
    old_gen->verify_object_start_array();
    perm_gen->verify_object_start_array();
  }

  if (ZapUnusedHeapArea) {
    old_gen->object_space()->check_mangled_unused_area_complete();
    perm_gen->object_space()->check_mangled_unused_area_complete();
  }

  NOT_PRODUCT(ref_processor()->verify_no_references_recorded());

  collection_exit.update();

  if (PrintHeapAtGC) {
    Universe::print_heap_after_gc();
  }
  if (PrintGCTaskTimeStamps) {
    gclog_or_tty->print_cr("VM-Thread " INT64_FORMAT " " INT64_FORMAT " "
                           INT64_FORMAT,
                           marking_start.ticks(), compaction_start.ticks(),
                           collection_exit.ticks());
    gc_task_manager()->print_task_time_stamps();
  }
}

bool PSParallelCompact::absorb_live_data_from_eden(PSAdaptiveSizePolicy* size_policy,
                                             PSYoungGen* young_gen,
                                             PSOldGen* old_gen) {
  MutableSpace* const eden_space = young_gen->eden_space();
  assert(!eden_space->is_empty(), "eden must be non-empty");
  assert(young_gen->virtual_space()->alignment() ==
         old_gen->virtual_space()->alignment(), "alignments do not match");

  if (!(UseAdaptiveSizePolicy && UseAdaptiveGCBoundary)) {
    return false;
  }

  // Both generations must be completely committed.
  if (young_gen->virtual_space()->uncommitted_size() != 0) {
    return false;
  }
  if (old_gen->virtual_space()->uncommitted_size() != 0) {
    return false;
  }

  // Figure out how much to take from eden.  Include the average amount promoted
  // in the total; otherwise the next young gen GC will simply bail out to a
  // full GC.
  const size_t alignment = old_gen->virtual_space()->alignment();
  const size_t eden_used = eden_space->used_in_bytes();
  const size_t promoted = (size_t)size_policy->avg_promoted()->padded_average();
  const size_t absorb_size = align_size_up(eden_used + promoted, alignment);
  const size_t eden_capacity = eden_space->capacity_in_bytes();

  if (absorb_size >= eden_capacity) {
    return false; // Must leave some space in eden.
  }

  const size_t new_young_size = young_gen->capacity_in_bytes() - absorb_size;
  if (new_young_size < young_gen->min_gen_size()) {
    return false; // Respect young gen minimum size.
  }

  if (TraceAdaptiveGCBoundary && Verbose) {
    gclog_or_tty->print(" absorbing " SIZE_FORMAT "K:  "
                        "eden " SIZE_FORMAT "K->" SIZE_FORMAT "K "
                        "from " SIZE_FORMAT "K, to " SIZE_FORMAT "K "
                        "young_gen " SIZE_FORMAT "K->" SIZE_FORMAT "K ",
                        absorb_size / K,
                        eden_capacity / K, (eden_capacity - absorb_size) / K,
                        young_gen->from_space()->used_in_bytes() / K,
                        young_gen->to_space()->used_in_bytes() / K,
                        young_gen->capacity_in_bytes() / K, new_young_size / K);
  }

  // Fill the unused part of the old gen.
  MutableSpace* const old_space = old_gen->object_space();
  MemRegion old_gen_unused(old_space->top(), old_space->end());
  if (!old_gen_unused.is_empty()) {
    SharedHeap::fill_region_with_object(old_gen_unused);
  }

  // Take the live data from eden and set both top and end in the old gen to
  // eden top.  (Need to set end because reset_after_change() mangles the region
  // from end to virtual_space->high() in debug builds).
  HeapWord* const new_top = eden_space->top();
  old_gen->virtual_space()->expand_into(young_gen->virtual_space(),
                                        absorb_size);
  young_gen->reset_after_change();
  old_space->set_top(new_top);
  old_space->set_end(new_top);
  old_gen->reset_after_change();

  // Update the object start array for the filler object and the data from eden.
  ObjectStartArray* const start_array = old_gen->start_array();
  HeapWord* const start = old_gen_unused.start();
  for (HeapWord* addr = start; addr < new_top; addr += oop(addr)->size()) {
    start_array->allocate_block(addr);
  }

  // Could update the promoted average here, but it is not typically updated at
  // full GCs and the value to use is unclear.  Something like
  //
  // cur_promoted_avg + absorb_size / number_of_scavenges_since_last_full_gc.

  size_policy->set_bytes_absorbed_from_eden(absorb_size);
  return true;
}

GCTaskManager* const PSParallelCompact::gc_task_manager() {
  assert(ParallelScavengeHeap::gc_task_manager() != NULL,
    "shouldn't return NULL");
  return ParallelScavengeHeap::gc_task_manager();
}

void PSParallelCompact::marking_phase(ParCompactionManager* cm,
                                      bool maximum_heap_compaction) {
  // Recursively traverse all live objects and mark them
  EventMark m("1 mark object");
  TraceTime tm("marking phase", print_phases(), true, gclog_or_tty);

  ParallelScavengeHeap* heap = gc_heap();
  uint parallel_gc_threads = heap->gc_task_manager()->workers();
  TaskQueueSetSuper* qset = ParCompactionManager::region_array();
  ParallelTaskTerminator terminator(parallel_gc_threads, qset);

  PSParallelCompact::MarkAndPushClosure mark_and_push_closure(cm);
  PSParallelCompact::FollowStackClosure follow_stack_closure(cm);

  {
    TraceTime tm_m("par mark", print_phases(), true, gclog_or_tty);

    GCTaskQueue* q = GCTaskQueue::create();

    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::universe));
    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::jni_handles));
    // We scan the thread roots in parallel
    Threads::create_thread_roots_marking_tasks(q);
    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::object_synchronizer));
    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::flat_profiler));
    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::management));
    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::system_dictionary));
    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::jvmti));
    q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::vm_symbols));

    if (parallel_gc_threads > 1) {
      for (uint j = 0; j < parallel_gc_threads; j++) {
        q->enqueue(new StealMarkingTask(&terminator));
      }
    }

    WaitForBarrierGCTask* fin = WaitForBarrierGCTask::create();
    q->enqueue(fin);

    gc_task_manager()->add_list(q);

    fin->wait_for();

    // We have to release the barrier tasks!
    WaitForBarrierGCTask::destroy(fin);
  }

  // Process reference objects found during marking
  {
    TraceTime tm_r("reference processing", print_phases(), true, gclog_or_tty);
    if (ref_processor()->processing_is_mt()) {
      RefProcTaskExecutor task_executor;
      ref_processor()->process_discovered_references(
        is_alive_closure(), &mark_and_push_closure, &follow_stack_closure,
        &task_executor);
    } else {
      ref_processor()->process_discovered_references(
        is_alive_closure(), &mark_and_push_closure, &follow_stack_closure, NULL);
    }
  }

  TraceTime tm_c("class unloading", print_phases(), true, gclog_or_tty);
  // Follow system dictionary roots and unload classes.
  bool purged_class = SystemDictionary::do_unloading(is_alive_closure());

  // Follow code cache roots.
  CodeCache::do_unloading(is_alive_closure(), &mark_and_push_closure,
                          purged_class);
  follow_stack(cm); // Flush marking stack.

  // Update subklass/sibling/implementor links of live klasses
  // revisit_klass_stack is used in follow_weak_klass_links().
  follow_weak_klass_links(cm);

  // Visit symbol and interned string tables and delete unmarked oops
  SymbolTable::unlink(is_alive_closure());
  StringTable::unlink(is_alive_closure());

  assert(cm->marking_stack()->size() == 0, "stack should be empty by now");
  assert(cm->overflow_stack()->is_empty(), "stack should be empty by now");
}

// This should be moved to the shared markSweep code!
class PSAlwaysTrueClosure: public BoolObjectClosure {
public:
  void do_object(oop p) { ShouldNotReachHere(); }
  bool do_object_b(oop p) { return true; }
};
static PSAlwaysTrueClosure always_true;

void PSParallelCompact::adjust_roots() {
  // Adjust the pointers to reflect the new locations
  EventMark m("3 adjust roots");
  TraceTime tm("adjust roots", print_phases(), true, gclog_or_tty);

  // General strong roots.
  Universe::oops_do(adjust_root_pointer_closure());
  ReferenceProcessor::oops_do(adjust_root_pointer_closure());
  JNIHandles::oops_do(adjust_root_pointer_closure());   // Global (strong) JNI handles
  Threads::oops_do(adjust_root_pointer_closure());
  ObjectSynchronizer::oops_do(adjust_root_pointer_closure());
  FlatProfiler::oops_do(adjust_root_pointer_closure());
  Management::oops_do(adjust_root_pointer_closure());
  JvmtiExport::oops_do(adjust_root_pointer_closure());
  // SO_AllClasses
  SystemDictionary::oops_do(adjust_root_pointer_closure());
  vmSymbols::oops_do(adjust_root_pointer_closure());

  // Now adjust pointers in remaining weak roots.  (All of which should
  // have been cleared if they pointed to non-surviving objects.)
  // Global (weak) JNI handles
  JNIHandles::weak_oops_do(&always_true, adjust_root_pointer_closure());

  CodeCache::oops_do(adjust_pointer_closure());
  SymbolTable::oops_do(adjust_root_pointer_closure());
  StringTable::oops_do(adjust_root_pointer_closure());
  ref_processor()->weak_oops_do(adjust_root_pointer_closure());
  // Roots were visited so references into the young gen in roots
  // may have been scanned.  Process them also.
  // Should the reference processor have a span that excludes
  // young gen objects?
  PSScavenge::reference_processor()->weak_oops_do(
                                              adjust_root_pointer_closure());
}

void PSParallelCompact::compact_perm(ParCompactionManager* cm) {
  EventMark m("4 compact perm");
  TraceTime tm("compact perm gen", print_phases(), true, gclog_or_tty);
  // trace("4");

  gc_heap()->perm_gen()->start_array()->reset();
  move_and_update(cm, perm_space_id);
}

void PSParallelCompact::enqueue_region_draining_tasks(GCTaskQueue* q,
                                                      uint parallel_gc_threads)
{
  TraceTime tm("drain task setup", print_phases(), true, gclog_or_tty);

  const unsigned int task_count = MAX2(parallel_gc_threads, 1U);
  for (unsigned int j = 0; j < task_count; j++) {
    q->enqueue(new DrainStacksCompactionTask());
  }

  // Find all regions that are available (can be filled immediately) and
  // distribute them to the thread stacks.  The iteration is done in reverse
  // order (high to low) so the regions will be removed in ascending order.

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

  size_t fillable_regions = 0;   // A count for diagnostic purposes.
  unsigned int which = 0;       // The worker thread number.

  for (unsigned int id = to_space_id; id > perm_space_id; --id) {
    SpaceInfo* const space_info = _space_info + id;
    MutableSpace* const space = space_info->space();
    HeapWord* const new_top = space_info->new_top();

    const size_t beg_region = sd.addr_to_region_idx(space_info->dense_prefix());
    const size_t end_region =
      sd.addr_to_region_idx(sd.region_align_up(new_top));
    assert(end_region > 0, "perm gen cannot be empty");

    for (size_t cur = end_region - 1; cur >= beg_region; --cur) {
      if (sd.region(cur)->claim_unsafe()) {
        ParCompactionManager* cm = ParCompactionManager::manager_array(which);
        cm->save_for_processing(cur);

        if (TraceParallelOldGCCompactionPhase && Verbose) {
          const size_t count_mod_8 = fillable_regions & 7;
          if (count_mod_8 == 0) gclog_or_tty->print("fillable: ");
          gclog_or_tty->print(" " SIZE_FORMAT_W(7), cur);
          if (count_mod_8 == 7) gclog_or_tty->cr();
        }

        NOT_PRODUCT(++fillable_regions;)

        // Assign regions to threads in round-robin fashion.
        if (++which == task_count) {
          which = 0;
        }
      }
    }
  }

  if (TraceParallelOldGCCompactionPhase) {
    if (Verbose && (fillable_regions & 7) != 0) gclog_or_tty->cr();
    gclog_or_tty->print_cr("%u initially fillable regions", fillable_regions);
  }
}

#define PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING 4

void PSParallelCompact::enqueue_dense_prefix_tasks(GCTaskQueue* q,
                                                    uint parallel_gc_threads) {
  TraceTime tm("dense prefix task setup", print_phases(), true, gclog_or_tty);

  ParallelCompactData& sd = PSParallelCompact::summary_data();

  // Iterate over all the spaces adding tasks for updating
  // regions in the dense prefix.  Assume that 1 gc thread
  // will work on opening the gaps and the remaining gc threads
  // will work on the dense prefix.
  SpaceId space_id = old_space_id;
  while (space_id != last_space_id) {
    HeapWord* const dense_prefix_end = _space_info[space_id].dense_prefix();
    const MutableSpace* const space = _space_info[space_id].space();

    if (dense_prefix_end == space->bottom()) {
      // There is no dense prefix for this space.
      space_id = next_compaction_space_id(space_id);
      continue;
    }

    // The dense prefix is before this region.
    size_t region_index_end_dense_prefix =
        sd.addr_to_region_idx(dense_prefix_end);
    RegionData* const dense_prefix_cp =
      sd.region(region_index_end_dense_prefix);
    assert(dense_prefix_end == space->end() ||
           dense_prefix_cp->available() ||
           dense_prefix_cp->claimed(),
           "The region after the dense prefix should always be ready to fill");

    size_t region_index_start = sd.addr_to_region_idx(space->bottom());

    // Is there dense prefix work?
    size_t total_dense_prefix_regions =
      region_index_end_dense_prefix - region_index_start;
    // How many regions of the dense prefix should be given to
    // each thread?
    if (total_dense_prefix_regions > 0) {
      uint tasks_for_dense_prefix = 1;
      if (UseParallelDensePrefixUpdate) {
        if (total_dense_prefix_regions <=
            (parallel_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING)) {
          // Don't over partition.  This assumes that
          // PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING is a small integer value
          // so there are not many regions to process.
          tasks_for_dense_prefix = parallel_gc_threads;
        } else {
          // Over partition
          tasks_for_dense_prefix = parallel_gc_threads *
            PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING;
        }
      }
      size_t regions_per_thread = total_dense_prefix_regions /
        tasks_for_dense_prefix;
      // Give each thread at least 1 region.
      if (regions_per_thread == 0) {
        regions_per_thread = 1;
      }

      for (uint k = 0; k < tasks_for_dense_prefix; k++) {
        if (region_index_start >= region_index_end_dense_prefix) {
          break;
        }
        // region_index_end is not processed
        size_t region_index_end = MIN2(region_index_start + regions_per_thread,
                                       region_index_end_dense_prefix);
        q->enqueue(new UpdateDensePrefixTask(
                                 space_id,
                                 region_index_start,
                                 region_index_end));
        region_index_start = region_index_end;
      }
    }
    // This gets any part of the dense prefix that did not
    // fit evenly.
    if (region_index_start < region_index_end_dense_prefix) {
      q->enqueue(new UpdateDensePrefixTask(
                                 space_id,
                                 region_index_start,
                                 region_index_end_dense_prefix));
    }
    space_id = next_compaction_space_id(space_id);
  }  // End tasks for dense prefix
}

void PSParallelCompact::enqueue_region_stealing_tasks(
                                     GCTaskQueue* q,
                                     ParallelTaskTerminator* terminator_ptr,
                                     uint parallel_gc_threads) {
  TraceTime tm("steal task setup", print_phases(), true, gclog_or_tty);

  // Once a thread has drained it's stack, it should try to steal regions from
  // other threads.
  if (parallel_gc_threads > 1) {
    for (uint j = 0; j < parallel_gc_threads; j++) {
      q->enqueue(new StealRegionCompactionTask(terminator_ptr));
    }
  }
}

void PSParallelCompact::compact() {
  EventMark m("5 compact");
  // trace("5");
  TraceTime tm("compaction phase", print_phases(), true, gclog_or_tty);

  ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
  assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
  PSOldGen* old_gen = heap->old_gen();
  old_gen->start_array()->reset();
  uint parallel_gc_threads = heap->gc_task_manager()->workers();
  TaskQueueSetSuper* qset = ParCompactionManager::region_array();
  ParallelTaskTerminator terminator(parallel_gc_threads, qset);

  GCTaskQueue* q = GCTaskQueue::create();
  enqueue_region_draining_tasks(q, parallel_gc_threads);
  enqueue_dense_prefix_tasks(q, parallel_gc_threads);
  enqueue_region_stealing_tasks(q, &terminator, parallel_gc_threads);

  {
    TraceTime tm_pc("par compact", print_phases(), true, gclog_or_tty);

    WaitForBarrierGCTask* fin = WaitForBarrierGCTask::create();
    q->enqueue(fin);

    gc_task_manager()->add_list(q);

    fin->wait_for();

    // We have to release the barrier tasks!
    WaitForBarrierGCTask::destroy(fin);

#ifdef  ASSERT
    // Verify that all regions have been processed before the deferred updates.
    // Note that perm_space_id is skipped; this type of verification is not
    // valid until the perm gen is compacted by regions.
    for (unsigned int id = old_space_id; id < last_space_id; ++id) {
      verify_complete(SpaceId(id));
    }
#endif
  }

  {
    // Update the deferred objects, if any.  Any compaction manager can be used.
    TraceTime tm_du("deferred updates", print_phases(), true, gclog_or_tty);
    ParCompactionManager* cm = ParCompactionManager::manager_array(0);
    for (unsigned int id = old_space_id; id < last_space_id; ++id) {
      update_deferred_objects(cm, SpaceId(id));
    }
  }
}

#ifdef  ASSERT
void PSParallelCompact::verify_complete(SpaceId space_id) {
  // All Regions between space bottom() to new_top() should be marked as filled
  // and all Regions between new_top() and top() should be available (i.e.,
  // should have been emptied).
  ParallelCompactData& sd = summary_data();
  SpaceInfo si = _space_info[space_id];
  HeapWord* new_top_addr = sd.region_align_up(si.new_top());
  HeapWord* old_top_addr = sd.region_align_up(si.space()->top());
  const size_t beg_region = sd.addr_to_region_idx(si.space()->bottom());
  const size_t new_top_region = sd.addr_to_region_idx(new_top_addr);
  const size_t old_top_region = sd.addr_to_region_idx(old_top_addr);

  bool issued_a_warning = false;

  size_t cur_region;
  for (cur_region = beg_region; cur_region < new_top_region; ++cur_region) {
    const RegionData* const c = sd.region(cur_region);
    if (!c->completed()) {
      warning("region " SIZE_FORMAT " not filled:  "
              "destination_count=" SIZE_FORMAT,
              cur_region, c->destination_count());
      issued_a_warning = true;
    }
  }

  for (cur_region = new_top_region; cur_region < old_top_region; ++cur_region) {
    const RegionData* const c = sd.region(cur_region);
    if (!c->available()) {
      warning("region " SIZE_FORMAT " not empty:   "
              "destination_count=" SIZE_FORMAT,
              cur_region, c->destination_count());
      issued_a_warning = true;
    }
  }

  if (issued_a_warning) {
    print_region_ranges();
  }
}
#endif  // #ifdef ASSERT

void PSParallelCompact::compact_serial(ParCompactionManager* cm) {
  EventMark m("5 compact serial");
  TraceTime tm("compact serial", print_phases(), true, gclog_or_tty);

  ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
  assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");

  PSYoungGen* young_gen = heap->young_gen();
  PSOldGen* old_gen = heap->old_gen();

  old_gen->start_array()->reset();
  old_gen->move_and_update(cm);
  young_gen->move_and_update(cm);
}


void PSParallelCompact::follow_stack(ParCompactionManager* cm) {
  while(!cm->overflow_stack()->is_empty()) {
    oop obj = cm->overflow_stack()->pop();
    obj->follow_contents(cm);
  }

  oop obj;
  // obj is a reference!!!
  while (cm->marking_stack()->pop_local(obj)) {
    // It would be nice to assert about the type of objects we might
    // pop, but they can come from anywhere, unfortunately.
    obj->follow_contents(cm);
  }
}

void
PSParallelCompact::follow_weak_klass_links(ParCompactionManager* serial_cm) {
  // All klasses on the revisit stack are marked at this point.
  // Update and follow all subklass, sibling and implementor links.
  for (uint i = 0; i < ParallelGCThreads+1; i++) {
    ParCompactionManager* cm = ParCompactionManager::manager_array(i);
    KeepAliveClosure keep_alive_closure(cm);
    for (int i = 0; i < cm->revisit_klass_stack()->length(); i++) {
      cm->revisit_klass_stack()->at(i)->follow_weak_klass_links(
        is_alive_closure(),
        &keep_alive_closure);
    }
    follow_stack(cm);
  }
}

void
PSParallelCompact::revisit_weak_klass_link(ParCompactionManager* cm, Klass* k) {
  cm->revisit_klass_stack()->push(k);
}

#ifdef VALIDATE_MARK_SWEEP

void PSParallelCompact::track_adjusted_pointer(void* p, bool isroot) {
  if (!ValidateMarkSweep)
    return;

  if (!isroot) {
    if (_pointer_tracking) {
      guarantee(_adjusted_pointers->contains(p), "should have seen this pointer");
      _adjusted_pointers->remove(p);
    }
  } else {
    ptrdiff_t index = _root_refs_stack->find(p);
    if (index != -1) {
      int l = _root_refs_stack->length();
      if (l > 0 && l - 1 != index) {
        void* last = _root_refs_stack->pop();
        assert(last != p, "should be different");
        _root_refs_stack->at_put(index, last);
      } else {
        _root_refs_stack->remove(p);
      }
    }
  }
}


void PSParallelCompact::check_adjust_pointer(void* p) {
  _adjusted_pointers->push(p);
}


class AdjusterTracker: public OopClosure {
 public:
  AdjusterTracker() {};
  void do_oop(oop* o)         { PSParallelCompact::check_adjust_pointer(o); }
  void do_oop(narrowOop* o)   { PSParallelCompact::check_adjust_pointer(o); }
};


void PSParallelCompact::track_interior_pointers(oop obj) {
  if (ValidateMarkSweep) {
    _adjusted_pointers->clear();
    _pointer_tracking = true;

    AdjusterTracker checker;
    obj->oop_iterate(&checker);
  }
}


void PSParallelCompact::check_interior_pointers() {
  if (ValidateMarkSweep) {
    _pointer_tracking = false;
    guarantee(_adjusted_pointers->length() == 0, "should have processed the same pointers");
  }
}


void PSParallelCompact::reset_live_oop_tracking(bool at_perm) {
  if (ValidateMarkSweep) {
    guarantee((size_t)_live_oops->length() == _live_oops_index, "should be at end of live oops");
    _live_oops_index = at_perm ? _live_oops_index_at_perm : 0;
  }
}


void PSParallelCompact::register_live_oop(oop p, size_t size) {
  if (ValidateMarkSweep) {
    _live_oops->push(p);
    _live_oops_size->push(size);
    _live_oops_index++;
  }
}

void PSParallelCompact::validate_live_oop(oop p, size_t size) {
  if (ValidateMarkSweep) {
    oop obj = _live_oops->at((int)_live_oops_index);
    guarantee(obj == p, "should be the same object");
    guarantee(_live_oops_size->at((int)_live_oops_index) == size, "should be the same size");
    _live_oops_index++;
  }
}

void PSParallelCompact::live_oop_moved_to(HeapWord* q, size_t size,
                                  HeapWord* compaction_top) {
  assert(oop(q)->forwardee() == NULL || oop(q)->forwardee() == oop(compaction_top),
         "should be moved to forwarded location");
  if (ValidateMarkSweep) {
    PSParallelCompact::validate_live_oop(oop(q), size);
    _live_oops_moved_to->push(oop(compaction_top));
  }
  if (RecordMarkSweepCompaction) {
    _cur_gc_live_oops->push(q);
    _cur_gc_live_oops_moved_to->push(compaction_top);
    _cur_gc_live_oops_size->push(size);
  }
}


void PSParallelCompact::compaction_complete() {
  if (RecordMarkSweepCompaction) {
    GrowableArray<HeapWord*>* _tmp_live_oops          = _cur_gc_live_oops;
    GrowableArray<HeapWord*>* _tmp_live_oops_moved_to = _cur_gc_live_oops_moved_to;
    GrowableArray<size_t>   * _tmp_live_oops_size     = _cur_gc_live_oops_size;

    _cur_gc_live_oops           = _last_gc_live_oops;
    _cur_gc_live_oops_moved_to  = _last_gc_live_oops_moved_to;
    _cur_gc_live_oops_size      = _last_gc_live_oops_size;
    _last_gc_live_oops          = _tmp_live_oops;
    _last_gc_live_oops_moved_to = _tmp_live_oops_moved_to;
    _last_gc_live_oops_size     = _tmp_live_oops_size;
  }
}


void PSParallelCompact::print_new_location_of_heap_address(HeapWord* q) {
  if (!RecordMarkSweepCompaction) {
    tty->print_cr("Requires RecordMarkSweepCompaction to be enabled");
    return;
  }

  if (_last_gc_live_oops == NULL) {
    tty->print_cr("No compaction information gathered yet");
    return;
  }

  for (int i = 0; i < _last_gc_live_oops->length(); i++) {
    HeapWord* old_oop = _last_gc_live_oops->at(i);
    size_t    sz      = _last_gc_live_oops_size->at(i);
    if (old_oop <= q && q < (old_oop + sz)) {
      HeapWord* new_oop = _last_gc_live_oops_moved_to->at(i);
      size_t offset = (q - old_oop);
      tty->print_cr("Address " PTR_FORMAT, q);
      tty->print_cr(" Was in oop " PTR_FORMAT ", size %d, at offset %d", old_oop, sz, offset);
      tty->print_cr(" Now in oop " PTR_FORMAT ", actual address " PTR_FORMAT, new_oop, new_oop + offset);
      return;
    }
  }

  tty->print_cr("Address " PTR_FORMAT " not found in live oop information from last GC", q);
}
#endif //VALIDATE_MARK_SWEEP

// Update interior oops in the ranges of regions [beg_region, end_region).
void
PSParallelCompact::update_and_deadwood_in_dense_prefix(ParCompactionManager* cm,
                                                       SpaceId space_id,
                                                       size_t beg_region,
                                                       size_t end_region) {
  ParallelCompactData& sd = summary_data();
  ParMarkBitMap* const mbm = mark_bitmap();

  HeapWord* beg_addr = sd.region_to_addr(beg_region);
  HeapWord* const end_addr = sd.region_to_addr(end_region);
  assert(beg_region <= end_region, "bad region range");
  assert(end_addr <= dense_prefix(space_id), "not in the dense prefix");

#ifdef  ASSERT
  // Claim the regions to avoid triggering an assert when they are marked as
  // filled.
  for (size_t claim_region = beg_region; claim_region < end_region; ++claim_region) {
    assert(sd.region(claim_region)->claim_unsafe(), "claim() failed");
  }
#endif  // #ifdef ASSERT

  if (beg_addr != space(space_id)->bottom()) {
    // Find the first live object or block of dead space that *starts* in this
    // range of regions.  If a partial object crosses onto the region, skip it;
    // it will be marked for 'deferred update' when the object head is
    // processed.  If dead space crosses onto the region, it is also skipped; it
    // will be filled when the prior region is processed.  If neither of those
    // apply, the first word in the region is the start of a live object or dead
    // space.
    assert(beg_addr > space(space_id)->bottom(), "sanity");
    const RegionData* const cp = sd.region(beg_region);
    if (cp->partial_obj_size() != 0) {
      beg_addr = sd.partial_obj_end(beg_region);
    } else if (dead_space_crosses_boundary(cp, mbm->addr_to_bit(beg_addr))) {
      beg_addr = mbm->find_obj_beg(beg_addr, end_addr);
    }
  }

  if (beg_addr < end_addr) {
    // A live object or block of dead space starts in this range of Regions.
     HeapWord* const dense_prefix_end = dense_prefix(space_id);

    // Create closures and iterate.
    UpdateOnlyClosure update_closure(mbm, cm, space_id);
    FillClosure fill_closure(cm, space_id);
    ParMarkBitMap::IterationStatus status;
    status = mbm->iterate(&update_closure, &fill_closure, beg_addr, end_addr,
                          dense_prefix_end);
    if (status == ParMarkBitMap::incomplete) {
      update_closure.do_addr(update_closure.source());
    }
  }

  // Mark the regions as filled.
  RegionData* const beg_cp = sd.region(beg_region);
  RegionData* const end_cp = sd.region(end_region);
  for (RegionData* cp = beg_cp; cp < end_cp; ++cp) {
    cp->set_completed();
  }
}

// Return the SpaceId for the space containing addr.  If addr is not in the
// heap, last_space_id is returned.  In debug mode it expects the address to be
// in the heap and asserts such.
PSParallelCompact::SpaceId PSParallelCompact::space_id(HeapWord* addr) {
  assert(Universe::heap()->is_in_reserved(addr), "addr not in the heap");

  for (unsigned int id = perm_space_id; id < last_space_id; ++id) {
    if (_space_info[id].space()->contains(addr)) {
      return SpaceId(id);
    }
  }

  assert(false, "no space contains the addr");
  return last_space_id;
}

void PSParallelCompact::update_deferred_objects(ParCompactionManager* cm,
                                                SpaceId id) {
  assert(id < last_space_id, "bad space id");

  ParallelCompactData& sd = summary_data();
  const SpaceInfo* const space_info = _space_info + id;
  ObjectStartArray* const start_array = space_info->start_array();

  const MutableSpace* const space = space_info->space();
  assert(space_info->dense_prefix() >= space->bottom(), "dense_prefix not set");
  HeapWord* const beg_addr = space_info->dense_prefix();
  HeapWord* const end_addr = sd.region_align_up(space_info->new_top());

  const RegionData* const beg_region = sd.addr_to_region_ptr(beg_addr);
  const RegionData* const end_region = sd.addr_to_region_ptr(end_addr);
  const RegionData* cur_region;
  for (cur_region = beg_region; cur_region < end_region; ++cur_region) {
    HeapWord* const addr = cur_region->deferred_obj_addr();
    if (addr != NULL) {
      if (start_array != NULL) {
        start_array->allocate_block(addr);
      }
      oop(addr)->update_contents(cm);
      assert(oop(addr)->is_oop_or_null(), "should be an oop now");
    }
  }
}

// Skip over count live words starting from beg, and return the address of the
// next live word.  Unless marked, the word corresponding to beg is assumed to
// be dead.  Callers must either ensure beg does not correspond to the middle of
// an object, or account for those live words in some other way.  Callers must
// also ensure that there are enough live words in the range [beg, end) to skip.
HeapWord*
PSParallelCompact::skip_live_words(HeapWord* beg, HeapWord* end, size_t count)
{
  assert(count > 0, "sanity");

  ParMarkBitMap* m = mark_bitmap();
  idx_t bits_to_skip = m->words_to_bits(count);
  idx_t cur_beg = m->addr_to_bit(beg);
  const idx_t search_end = BitMap::word_align_up(m->addr_to_bit(end));

  do {
    cur_beg = m->find_obj_beg(cur_beg, search_end);
    idx_t cur_end = m->find_obj_end(cur_beg, search_end);
    const size_t obj_bits = cur_end - cur_beg + 1;
    if (obj_bits > bits_to_skip) {
      return m->bit_to_addr(cur_beg + bits_to_skip);
    }
    bits_to_skip -= obj_bits;
    cur_beg = cur_end + 1;
  } while (bits_to_skip > 0);

  // Skipping the desired number of words landed just past the end of an object.
  // Find the start of the next object.
  cur_beg = m->find_obj_beg(cur_beg, search_end);
  assert(cur_beg < m->addr_to_bit(end), "not enough live words to skip");
  return m->bit_to_addr(cur_beg);
}

HeapWord*
PSParallelCompact::first_src_addr(HeapWord* const dest_addr,
                                 size_t src_region_idx)
{
  ParMarkBitMap* const bitmap = mark_bitmap();
  const ParallelCompactData& sd = summary_data();
  const size_t RegionSize = ParallelCompactData::RegionSize;

  assert(sd.is_region_aligned(dest_addr), "not aligned");

  const RegionData* const src_region_ptr = sd.region(src_region_idx);
  const size_t partial_obj_size = src_region_ptr->partial_obj_size();
  HeapWord* const src_region_destination = src_region_ptr->destination();

  assert(dest_addr >= src_region_destination, "wrong src region");
  assert(src_region_ptr->data_size() > 0, "src region cannot be empty");

  HeapWord* const src_region_beg = sd.region_to_addr(src_region_idx);
  HeapWord* const src_region_end = src_region_beg + RegionSize;

  HeapWord* addr = src_region_beg;
  if (dest_addr == src_region_destination) {
    // Return the first live word in the source region.
    if (partial_obj_size == 0) {
      addr = bitmap->find_obj_beg(addr, src_region_end);
      assert(addr < src_region_end, "no objects start in src region");
    }
    return addr;
  }

  // Must skip some live data.
  size_t words_to_skip = dest_addr - src_region_destination;
  assert(src_region_ptr->data_size() > words_to_skip, "wrong src region");

  if (partial_obj_size >= words_to_skip) {
    // All the live words to skip are part of the partial object.
    addr += words_to_skip;
    if (partial_obj_size == words_to_skip) {
      // Find the first live word past the partial object.
      addr = bitmap->find_obj_beg(addr, src_region_end);
      assert(addr < src_region_end, "wrong src region");
    }
    return addr;
  }

  // Skip over the partial object (if any).
  if (partial_obj_size != 0) {
    words_to_skip -= partial_obj_size;
    addr += partial_obj_size;
  }

  // Skip over live words due to objects that start in the region.
  addr = skip_live_words(addr, src_region_end, words_to_skip);
  assert(addr < src_region_end, "wrong src region");
  return addr;
}

void PSParallelCompact::decrement_destination_counts(ParCompactionManager* cm,
                                                     size_t beg_region,
                                                     HeapWord* end_addr)
{
  ParallelCompactData& sd = summary_data();
  RegionData* const beg = sd.region(beg_region);
  HeapWord* const end_addr_aligned_up = sd.region_align_up(end_addr);
  RegionData* const end = sd.addr_to_region_ptr(end_addr_aligned_up);
  size_t cur_idx = beg_region;
  for (RegionData* cur = beg; cur < end; ++cur, ++cur_idx) {
    assert(cur->data_size() > 0, "region must have live data");
    cur->decrement_destination_count();
    if (cur_idx <= cur->source_region() && cur->available() && cur->claim()) {
      cm->save_for_processing(cur_idx);
    }
  }
}

size_t PSParallelCompact::next_src_region(MoveAndUpdateClosure& closure,
                                          SpaceId& src_space_id,
                                          HeapWord*& src_space_top,
                                          HeapWord* end_addr)
{
  typedef ParallelCompactData::RegionData RegionData;

  ParallelCompactData& sd = PSParallelCompact::summary_data();
  const size_t region_size = ParallelCompactData::RegionSize;

  size_t src_region_idx = 0;

  // Skip empty regions (if any) up to the top of the space.
  HeapWord* const src_aligned_up = sd.region_align_up(end_addr);
  RegionData* src_region_ptr = sd.addr_to_region_ptr(src_aligned_up);
  HeapWord* const top_aligned_up = sd.region_align_up(src_space_top);
  const RegionData* const top_region_ptr =
    sd.addr_to_region_ptr(top_aligned_up);
  while (src_region_ptr < top_region_ptr && src_region_ptr->data_size() == 0) {
    ++src_region_ptr;
  }

  if (src_region_ptr < top_region_ptr) {
    // The next source region is in the current space.  Update src_region_idx
    // and the source address to match src_region_ptr.
    src_region_idx = sd.region(src_region_ptr);
    HeapWord* const src_region_addr = sd.region_to_addr(src_region_idx);
    if (src_region_addr > closure.source()) {
      closure.set_source(src_region_addr);
    }
    return src_region_idx;
  }

  // Switch to a new source space and find the first non-empty region.
  unsigned int space_id = src_space_id + 1;
  assert(space_id < last_space_id, "not enough spaces");

  HeapWord* const destination = closure.destination();

  do {
    MutableSpace* space = _space_info[space_id].space();
    HeapWord* const bottom = space->bottom();
    const RegionData* const bottom_cp = sd.addr_to_region_ptr(bottom);

    // Iterate over the spaces that do not compact into themselves.
    if (bottom_cp->destination() != bottom) {
      HeapWord* const top_aligned_up = sd.region_align_up(space->top());
      const RegionData* const top_cp = sd.addr_to_region_ptr(top_aligned_up);

      for (const RegionData* src_cp = bottom_cp; src_cp < top_cp; ++src_cp) {
        if (src_cp->live_obj_size() > 0) {
          // Found it.
          assert(src_cp->destination() == destination,
                 "first live obj in the space must match the destination");
          assert(src_cp->partial_obj_size() == 0,
                 "a space cannot begin with a partial obj");

          src_space_id = SpaceId(space_id);
          src_space_top = space->top();
          const size_t src_region_idx = sd.region(src_cp);
          closure.set_source(sd.region_to_addr(src_region_idx));
          return src_region_idx;
        } else {
          assert(src_cp->data_size() == 0, "sanity");
        }
      }
    }
  } while (++space_id < last_space_id);

  assert(false, "no source region was found");
  return 0;
}

void PSParallelCompact::fill_region(ParCompactionManager* cm, size_t region_idx)
{
  typedef ParMarkBitMap::IterationStatus IterationStatus;
  const size_t RegionSize = ParallelCompactData::RegionSize;
  ParMarkBitMap* const bitmap = mark_bitmap();
  ParallelCompactData& sd = summary_data();
  RegionData* const region_ptr = sd.region(region_idx);

  // Get the items needed to construct the closure.
  HeapWord* dest_addr = sd.region_to_addr(region_idx);
  SpaceId dest_space_id = space_id(dest_addr);
  ObjectStartArray* start_array = _space_info[dest_space_id].start_array();
  HeapWord* new_top = _space_info[dest_space_id].new_top();
  assert(dest_addr < new_top, "sanity");
  const size_t words = MIN2(pointer_delta(new_top, dest_addr), RegionSize);

  // Get the source region and related info.
  size_t src_region_idx = region_ptr->source_region();
  SpaceId src_space_id = space_id(sd.region_to_addr(src_region_idx));
  HeapWord* src_space_top = _space_info[src_space_id].space()->top();

  MoveAndUpdateClosure closure(bitmap, cm, start_array, dest_addr, words);
  closure.set_source(first_src_addr(dest_addr, src_region_idx));

  // Adjust src_region_idx to prepare for decrementing destination counts (the
  // destination count is not decremented when a region is copied to itself).
  if (src_region_idx == region_idx) {
    src_region_idx += 1;
  }

  if (bitmap->is_unmarked(closure.source())) {
    // The first source word is in the middle of an object; copy the remainder
    // of the object or as much as will fit.  The fact that pointer updates were
    // deferred will be noted when the object header is processed.
    HeapWord* const old_src_addr = closure.source();
    closure.copy_partial_obj();
    if (closure.is_full()) {
      decrement_destination_counts(cm, src_region_idx, closure.source());
      region_ptr->set_deferred_obj_addr(NULL);
      region_ptr->set_completed();
      return;
    }

    HeapWord* const end_addr = sd.region_align_down(closure.source());
    if (sd.region_align_down(old_src_addr) != end_addr) {
      // The partial object was copied from more than one source region.
      decrement_destination_counts(cm, src_region_idx, end_addr);

      // Move to the next source region, possibly switching spaces as well.  All
      // args except end_addr may be modified.
      src_region_idx = next_src_region(closure, src_space_id, src_space_top,
                                       end_addr);
    }
  }

  do {
    HeapWord* const cur_addr = closure.source();
    HeapWord* const end_addr = MIN2(sd.region_align_up(cur_addr + 1),
                                    src_space_top);
    IterationStatus status = bitmap->iterate(&closure, cur_addr, end_addr);

    if (status == ParMarkBitMap::incomplete) {
      // The last obj that starts in the source region does not end in the
      // region.
      assert(closure.source() < end_addr, "sanity")
      HeapWord* const obj_beg = closure.source();
      HeapWord* const range_end = MIN2(obj_beg + closure.words_remaining(),
                                       src_space_top);
      HeapWord* const obj_end = bitmap->find_obj_end(obj_beg, range_end);
      if (obj_end < range_end) {
        // The end was found; the entire object will fit.
        status = closure.do_addr(obj_beg, bitmap->obj_size(obj_beg, obj_end));
        assert(status != ParMarkBitMap::would_overflow, "sanity");
      } else {
        // The end was not found; the object will not fit.
        assert(range_end < src_space_top, "obj cannot cross space boundary");
        status = ParMarkBitMap::would_overflow;
      }
    }

    if (status == ParMarkBitMap::would_overflow) {
      // The last object did not fit.  Note that interior oop updates were
      // deferred, then copy enough of the object to fill the region.
      region_ptr->set_deferred_obj_addr(closure.destination());
      status = closure.copy_until_full(); // copies from closure.source()

      decrement_destination_counts(cm, src_region_idx, closure.source());
      region_ptr->set_completed();
      return;
    }

    if (status == ParMarkBitMap::full) {
      decrement_destination_counts(cm, src_region_idx, closure.source());
      region_ptr->set_deferred_obj_addr(NULL);
      region_ptr->set_completed();
      return;
    }

    decrement_destination_counts(cm, src_region_idx, end_addr);

    // Move to the next source region, possibly switching spaces as well.  All
    // args except end_addr may be modified.
    src_region_idx = next_src_region(closure, src_space_id, src_space_top,
                                     end_addr);
  } while (true);
}

void
PSParallelCompact::move_and_update(ParCompactionManager* cm, SpaceId space_id) {
  const MutableSpace* sp = space(space_id);
  if (sp->is_empty()) {
    return;
  }

  ParallelCompactData& sd = PSParallelCompact::summary_data();
  ParMarkBitMap* const bitmap = mark_bitmap();
  HeapWord* const dp_addr = dense_prefix(space_id);
  HeapWord* beg_addr = sp->bottom();
  HeapWord* end_addr = sp->top();

#ifdef ASSERT
  assert(beg_addr <= dp_addr && dp_addr <= end_addr, "bad dense prefix");
  if (cm->should_verify_only()) {
    VerifyUpdateClosure verify_update(cm, sp);
    bitmap->iterate(&verify_update, beg_addr, end_addr);
    return;
  }

  if (cm->should_reset_only()) {
    ResetObjectsClosure reset_objects(cm);
    bitmap->iterate(&reset_objects, beg_addr, end_addr);
    return;
  }
#endif

  const size_t beg_region = sd.addr_to_region_idx(beg_addr);
  const size_t dp_region = sd.addr_to_region_idx(dp_addr);
  if (beg_region < dp_region) {
    update_and_deadwood_in_dense_prefix(cm, space_id, beg_region, dp_region);
  }

  // The destination of the first live object that starts in the region is one
  // past the end of the partial object entering the region (if any).
  HeapWord* const dest_addr = sd.partial_obj_end(dp_region);
  HeapWord* const new_top = _space_info[space_id].new_top();
  assert(new_top >= dest_addr, "bad new_top value");
  const size_t words = pointer_delta(new_top, dest_addr);

  if (words > 0) {
    ObjectStartArray* start_array = _space_info[space_id].start_array();
    MoveAndUpdateClosure closure(bitmap, cm, start_array, dest_addr, words);

    ParMarkBitMap::IterationStatus status;
    status = bitmap->iterate(&closure, dest_addr, end_addr);
    assert(status == ParMarkBitMap::full, "iteration not complete");
    assert(bitmap->find_obj_beg(closure.source(), end_addr) == end_addr,
           "live objects skipped because closure is full");
  }
}

jlong PSParallelCompact::millis_since_last_gc() {
  jlong ret_val = os::javaTimeMillis() - _time_of_last_gc;
  // XXX See note in genCollectedHeap::millis_since_last_gc().
  if (ret_val < 0) {
    NOT_PRODUCT(warning("time warp: %d", ret_val);)
    return 0;
  }
  return ret_val;
}

void PSParallelCompact::reset_millis_since_last_gc() {
  _time_of_last_gc = os::javaTimeMillis();
}

ParMarkBitMap::IterationStatus MoveAndUpdateClosure::copy_until_full()
{
  if (source() != destination()) {
    assert(source() > destination(), "must copy to the left");
    Copy::aligned_conjoint_words(source(), destination(), words_remaining());
  }
  update_state(words_remaining());
  assert(is_full(), "sanity");
  return ParMarkBitMap::full;
}

void MoveAndUpdateClosure::copy_partial_obj()
{
  size_t words = words_remaining();

  HeapWord* const range_end = MIN2(source() + words, bitmap()->region_end());
  HeapWord* const end_addr = bitmap()->find_obj_end(source(), range_end);
  if (end_addr < range_end) {
    words = bitmap()->obj_size(source(), end_addr);
  }

  // This test is necessary; if omitted, the pointer updates to a partial object
  // that crosses the dense prefix boundary could be overwritten.
  if (source() != destination()) {
    assert(source() > destination(), "must copy to the left");
    Copy::aligned_conjoint_words(source(), destination(), words);
  }
  update_state(words);
}

ParMarkBitMapClosure::IterationStatus
MoveAndUpdateClosure::do_addr(HeapWord* addr, size_t words) {
  assert(destination() != NULL, "sanity");
  assert(bitmap()->obj_size(addr) == words, "bad size");

  _source = addr;
  assert(PSParallelCompact::summary_data().calc_new_pointer(source()) ==
         destination(), "wrong destination");

  if (words > words_remaining()) {
    return ParMarkBitMap::would_overflow;
  }

  // The start_array must be updated even if the object is not moving.
  if (_start_array != NULL) {
    _start_array->allocate_block(destination());
  }

  if (destination() != source()) {
    assert(destination() < source(), "must copy to the left");
    Copy::aligned_conjoint_words(source(), destination(), words);
  }

  oop moved_oop = (oop) destination();
  moved_oop->update_contents(compaction_manager());
  assert(moved_oop->is_oop_or_null(), "Object should be whole at this point");

  update_state(words);
  assert(destination() == (HeapWord*)moved_oop + moved_oop->size(), "sanity");
  return is_full() ? ParMarkBitMap::full : ParMarkBitMap::incomplete;
}

UpdateOnlyClosure::UpdateOnlyClosure(ParMarkBitMap* mbm,
                                     ParCompactionManager* cm,
                                     PSParallelCompact::SpaceId space_id) :
  ParMarkBitMapClosure(mbm, cm),
  _space_id(space_id),
  _start_array(PSParallelCompact::start_array(space_id))
{
}

// Updates the references in the object to their new values.
ParMarkBitMapClosure::IterationStatus
UpdateOnlyClosure::do_addr(HeapWord* addr, size_t words) {
  do_addr(addr);
  return ParMarkBitMap::incomplete;
}

// Verify the new location using the forwarding pointer
// from MarkSweep::mark_sweep_phase2().  Set the mark_word
// to the initial value.
ParMarkBitMapClosure::IterationStatus
PSParallelCompact::VerifyUpdateClosure::do_addr(HeapWord* addr, size_t words) {
  // The second arg (words) is not used.
  oop obj = (oop) addr;
  HeapWord* forwarding_ptr = (HeapWord*) obj->mark()->decode_pointer();
  HeapWord* new_pointer = summary_data().calc_new_pointer(obj);
  if (forwarding_ptr == NULL) {
    // The object is dead or not moving.
    assert(bitmap()->is_unmarked(obj) || (new_pointer == (HeapWord*) obj),
           "Object liveness is wrong.");
    return ParMarkBitMap::incomplete;
  }
  assert(UseParallelOldGCDensePrefix ||
         (HeapMaximumCompactionInterval > 1) ||
         (MarkSweepAlwaysCompactCount > 1) ||
         (forwarding_ptr == new_pointer),
    "Calculation of new location is incorrect");
  return ParMarkBitMap::incomplete;
}

// Reset objects modified for debug checking.
ParMarkBitMapClosure::IterationStatus
PSParallelCompact::ResetObjectsClosure::do_addr(HeapWord* addr, size_t words) {
  // The second arg (words) is not used.
  oop obj = (oop) addr;
  obj->init_mark();
  return ParMarkBitMap::incomplete;
}

// Prepare for compaction.  This method is executed once
// (i.e., by a single thread) before compaction.
// Save the updated location of the intArrayKlassObj for
// filling holes in the dense prefix.
void PSParallelCompact::compact_prologue() {
  _updated_int_array_klass_obj = (klassOop)
    summary_data().calc_new_pointer(Universe::intArrayKlassObj());
}

// The initial implementation of this method created a field
// _next_compaction_space_id in SpaceInfo and initialized
// that field in SpaceInfo::initialize_space_info().  That
// required that _next_compaction_space_id be declared a
// SpaceId in SpaceInfo and that would have required that
// either SpaceId be declared in a separate class or that
// it be declared in SpaceInfo.  It didn't seem consistent
// to declare it in SpaceInfo (didn't really fit logically).
// Alternatively, defining a separate class to define SpaceId
// seem excessive.  This implementation is simple and localizes
// the knowledge.

PSParallelCompact::SpaceId
PSParallelCompact::next_compaction_space_id(SpaceId id) {
  assert(id < last_space_id, "id out of range");
  switch (id) {
    case perm_space_id :
      return last_space_id;
    case old_space_id :
      return eden_space_id;
    case eden_space_id :
      return from_space_id;
    case from_space_id :
      return to_space_id;
    case to_space_id :
      return last_space_id;
    default:
      assert(false, "Bad space id");
      return last_space_id;
  }
}