/*

 * Copyright 2001-2009 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/_concurrentMark.cpp.incl"

//

// CMS Bit Map Wrapper

CMBitMapRO::CMBitMapRO(ReservedSpace rs, int shifter):

  _bm((uintptr_t*)NULL,0),

  _shifter(shifter) {

  _bmStartWord = (HeapWord*)(rs.base());

  _bmWordSize  = rs.size()/HeapWordSize;    // rs.size() is in bytes

  ReservedSpace brs(ReservedSpace::allocation_align_size_up(

                     (_bmWordSize >> (_shifter + LogBitsPerByte)) + 1));

  guarantee(brs.is_reserved(), "couldn't allocate CMS bit map");

  // For now we'll just commit all of the bit map up fromt.

  // Later on we'll try to be more parsimonious with swap.

  guarantee(_virtual_space.initialize(brs, brs.size()),

            "couldn't reseve backing store for CMS bit map");

  assert(_virtual_space.committed_size() == brs.size(),

         "didn't reserve backing store for all of CMS bit map?");

  _bm.set_map((uintptr_t*)_virtual_space.low());

  assert(_virtual_space.committed_size() << (_shifter + LogBitsPerByte) >=

         _bmWordSize, "inconsistency in bit map sizing");

  _bm.set_size(_bmWordSize >> _shifter);

}

HeapWord* CMBitMapRO::getNextMarkedWordAddress(HeapWord* addr,

                                               HeapWord* limit) const {

  // First we must round addr *up* to a possible object boundary.

  addr = (HeapWord*)align_size_up((intptr_t)addr,

                                  HeapWordSize << _shifter);

  size_t addrOffset = heapWordToOffset(addr);

  if (limit == NULL) limit = _bmStartWord + _bmWordSize;

  size_t limitOffset = heapWordToOffset(limit);

  size_t nextOffset = _bm.get_next_one_offset(addrOffset, limitOffset);

  HeapWord* nextAddr = offsetToHeapWord(nextOffset);

  assert(nextAddr >= addr, "get_next_one postcondition");

  assert(nextAddr == limit || isMarked(nextAddr),

         "get_next_one postcondition");

  return nextAddr;

}

HeapWord* CMBitMapRO::getNextUnmarkedWordAddress(HeapWord* addr,

                                                 HeapWord* limit) const {

  size_t addrOffset = heapWordToOffset(addr);

  if (limit == NULL) limit = _bmStartWord + _bmWordSize;

  size_t limitOffset = heapWordToOffset(limit);

  size_t nextOffset = _bm.get_next_zero_offset(addrOffset, limitOffset);

  HeapWord* nextAddr = offsetToHeapWord(nextOffset);

  assert(nextAddr >= addr, "get_next_one postcondition");

  assert(nextAddr == limit || !isMarked(nextAddr),

         "get_next_one postcondition");

  return nextAddr;

}

int CMBitMapRO::heapWordDiffToOffsetDiff(size_t diff) const {

  assert((diff & ((1 << _shifter) - 1)) == 0, "argument check");

  return (int) (diff >> _shifter);

}

bool CMBitMapRO::iterate(BitMapClosure* cl, MemRegion mr) {

  HeapWord* left  = MAX2(_bmStartWord, mr.start());

  HeapWord* right = MIN2(_bmStartWord + _bmWordSize, mr.end());

  if (right > left) {

    // Right-open interval [leftOffset, rightOffset).

    return _bm.iterate(cl, heapWordToOffset(left), heapWordToOffset(right));

  } else {

    return true;

  }

}

void CMBitMapRO::mostly_disjoint_range_union(BitMap*   from_bitmap,

                                             size_t    from_start_index,

                                             HeapWord* to_start_word,

                                             size_t    word_num) {

  _bm.mostly_disjoint_range_union(from_bitmap,

                                  from_start_index,

                                  heapWordToOffset(to_start_word),

                                  word_num);

}

#ifndef PRODUCT

bool CMBitMapRO::covers(ReservedSpace rs) const {

  // assert(_bm.map() == _virtual_space.low(), "map inconsistency");

  assert(((size_t)_bm.size() * (size_t)(1 << _shifter)) == _bmWordSize,

         "size inconsistency");

  return _bmStartWord == (HeapWord*)(rs.base()) &&

         _bmWordSize  == rs.size()>>LogHeapWordSize;

}

#endif

void CMBitMap::clearAll() {

  _bm.clear();

  return;

}

void CMBitMap::markRange(MemRegion mr) {

  mr.intersection(MemRegion(_bmStartWord, _bmWordSize));

  assert(!mr.is_empty(), "unexpected empty region");

  assert((offsetToHeapWord(heapWordToOffset(mr.end())) ==

          ((HeapWord *) mr.end())),

         "markRange memory region end is not card aligned");

  // convert address range into offset range

  _bm.at_put_range(heapWordToOffset(mr.start()),

                   heapWordToOffset(mr.end()), true);

}

void CMBitMap::clearRange(MemRegion mr) {

  mr.intersection(MemRegion(_bmStartWord, _bmWordSize));

  assert(!mr.is_empty(), "unexpected empty region");

  // convert address range into offset range

  _bm.at_put_range(heapWordToOffset(mr.start()),

                   heapWordToOffset(mr.end()), false);

}

MemRegion CMBitMap::getAndClearMarkedRegion(HeapWord* addr,

                                            HeapWord* end_addr) {

  HeapWord* start = getNextMarkedWordAddress(addr);

  start = MIN2(start, end_addr);

  HeapWord* end   = getNextUnmarkedWordAddress(start);

  end = MIN2(end, end_addr);

  assert(start <= end, "Consistency check");

  MemRegion mr(start, end);

  if (!mr.is_empty()) {

    clearRange(mr);

  }

  return mr;

}

CMMarkStack::CMMarkStack(ConcurrentMark* cm) :

  _base(NULL), _cm(cm)

#ifdef ASSERT

  , _drain_in_progress(false)

  , _drain_in_progress_yields(false)

#endif

{}

void CMMarkStack::allocate(size_t size) {

  _base = NEW_C_HEAP_ARRAY(oop, size);

  if (_base == NULL)

    vm_exit_during_initialization("Failed to allocate "

                                  "CM region mark stack");

  _index = 0;

  // QQQQ cast ...

  _capacity = (jint) size;

  _oops_do_bound = -1;

  NOT_PRODUCT(_max_depth = 0);

}

CMMarkStack::~CMMarkStack() {

  if (_base != NULL) FREE_C_HEAP_ARRAY(oop, _base);

}

void CMMarkStack::par_push(oop ptr) {

  while (true) {

    if (isFull()) {

      _overflow = true;

      return;

    }

    // Otherwise...

    jint index = _index;

    jint next_index = index+1;

    jint res = Atomic::cmpxchg(next_index, &_index, index);

    if (res == index) {

      _base[index] = ptr;

      // Note that we don't maintain this atomically.  We could, but it

      // doesn't seem necessary.

      NOT_PRODUCT(_max_depth = MAX2(_max_depth, next_index));

      return;

    }

    // Otherwise, we need to try again.

  }

}

void CMMarkStack::par_adjoin_arr(oop* ptr_arr, int n) {

  while (true) {

    if (isFull()) {

      _overflow = true;

      return;

    }

    // Otherwise...

    jint index = _index;

    jint next_index = index + n;

    if (next_index > _capacity) {

      _overflow = true;

      return;

    }

    jint res = Atomic::cmpxchg(next_index, &_index, index);

    if (res == index) {

      for (int i = 0; i < n; i++) {

        int ind = index + i;

        assert(ind < _capacity, "By overflow test above.");

        _base[ind] = ptr_arr[i];

      }

      NOT_PRODUCT(_max_depth = MAX2(_max_depth, next_index));

      return;

    }

    // Otherwise, we need to try again.

  }

}

void CMMarkStack::par_push_arr(oop* ptr_arr, int n) {

  MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

  jint start = _index;

  jint next_index = start + n;

  if (next_index > _capacity) {

    _overflow = true;

    return;

  }

  // Otherwise.

  _index = next_index;

  for (int i = 0; i < n; i++) {

    int ind = start + i;

    assert(ind < _capacity, "By overflow test above.");

    _base[ind] = ptr_arr[i];

  }

}

bool CMMarkStack::par_pop_arr(oop* ptr_arr, int max, int* n) {

  MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

  jint index = _index;

  if (index == 0) {

    *n = 0;

    return false;

  } else {

    int k = MIN2(max, index);

    jint new_ind = index - k;

    for (int j = 0; j < k; j++) {

      ptr_arr[j] = _base[new_ind + j];

    }

    _index = new_ind;

    *n = k;

    return true;

  }

}

CMRegionStack::CMRegionStack() : _base(NULL) {}

void CMRegionStack::allocate(size_t size) {

  _base = NEW_C_HEAP_ARRAY(MemRegion, size);

  if (_base == NULL)

    vm_exit_during_initialization("Failed to allocate "

                                  "CM region mark stack");

  _index = 0;

  // QQQQ cast ...

  _capacity = (jint) size;

}

CMRegionStack::~CMRegionStack() {

  if (_base != NULL) FREE_C_HEAP_ARRAY(oop, _base);

}

void CMRegionStack::push(MemRegion mr) {

  assert(mr.word_size() > 0, "Precondition");

  while (true) {

    if (isFull()) {

      _overflow = true;

      return;

    }

    // Otherwise...

    jint index = _index;

    jint next_index = index+1;

    jint res = Atomic::cmpxchg(next_index, &_index, index);

    if (res == index) {

      _base[index] = mr;

      return;

    }

    // Otherwise, we need to try again.

  }

}

MemRegion CMRegionStack::pop() {

  while (true) {

    // Otherwise...

    jint index = _index;

    if (index == 0) {

      return MemRegion();

    }

    jint next_index = index-1;

    jint res = Atomic::cmpxchg(next_index, &_index, index);

    if (res == index) {

      MemRegion mr = _base[next_index];

      if (mr.start() != NULL) {

        assert(mr.end() != NULL, "invariant");

        assert(mr.word_size() > 0, "invariant");

        return mr;

      } else {

        // that entry was invalidated... let's skip it

        assert(mr.end() == NULL, "invariant");

      }

    }

    // Otherwise, we need to try again.

  }

}

bool CMRegionStack::invalidate_entries_into_cset() {

  bool result = false;

  G1CollectedHeap* g1h = G1CollectedHeap::heap();

  for (int i = 0; i < _oops_do_bound; ++i) {

    MemRegion mr = _base[i];

    if (mr.start() != NULL) {

      assert(mr.end() != NULL, "invariant");

      assert(mr.word_size() > 0, "invariant");

      HeapRegion* hr = g1h->heap_region_containing(mr.start());

      assert(hr != NULL, "invariant");

      if (hr->in_collection_set()) {

        // The region points into the collection set

        _base[i] = MemRegion();

        result = true;

      }

    } else {

      // that entry was invalidated... let's skip it

      assert(mr.end() == NULL, "invariant");

    }

  }

  return result;

}

template<class OopClosureClass>

bool CMMarkStack::drain(OopClosureClass* cl, CMBitMap* bm, bool yield_after) {

  assert(!_drain_in_progress || !_drain_in_progress_yields || yield_after

         || SafepointSynchronize::is_at_safepoint(),

         "Drain recursion must be yield-safe.");

  bool res = true;

  debug_only(_drain_in_progress = true);

  debug_only(_drain_in_progress_yields = yield_after);

  while (!isEmpty()) {

    oop newOop = pop();

    assert(G1CollectedHeap::heap()->is_in_reserved(newOop), "Bad pop");

    assert(newOop->is_oop(), "Expected an oop");

    assert(bm == NULL || bm->isMarked((HeapWord*)newOop),

           "only grey objects on this stack");

    // iterate over the oops in this oop, marking and pushing

    // the ones in CMS generation.

    newOop->oop_iterate(cl);

    if (yield_after && _cm->do_yield_check()) {

      res = false; break;

    }

  }

  debug_only(_drain_in_progress = false);

  return res;

}

void CMMarkStack::oops_do(OopClosure* f) {

  if (_index == 0) return;

  assert(_oops_do_bound != -1 && _oops_do_bound <= _index,

         "Bound must be set.");

  for (int i = 0; i < _oops_do_bound; i++) {

    f->do_oop(&_base[i]);

  }

  _oops_do_bound = -1;

}

bool ConcurrentMark::not_yet_marked(oop obj) const {

  return (_g1h->is_obj_ill(obj)

          || (_g1h->is_in_permanent(obj)

              && !nextMarkBitMap()->isMarked((HeapWord*)obj)));

}

#ifdef _MSC_VER // the use of 'this' below gets a warning, make it go away

#pragma warning( disable:4355 ) // 'this' : used in base member initializer list

#endif // _MSC_VER

ConcurrentMark::ConcurrentMark(ReservedSpace rs,

                               int max_regions) :

  _markBitMap1(rs, MinObjAlignment - 1),

  _markBitMap2(rs, MinObjAlignment - 1),

  _parallel_marking_threads(0),

  _sleep_factor(0.0),

  _marking_task_overhead(1.0),

  _cleanup_sleep_factor(0.0),

  _cleanup_task_overhead(1.0),

  _region_bm(max_regions, false /* in_resource_area*/),

  _card_bm((rs.size() + CardTableModRefBS::card_size - 1) >>

           CardTableModRefBS::card_shift,

           false /* in_resource_area*/),

  _prevMarkBitMap(&_markBitMap1),

  _nextMarkBitMap(&_markBitMap2),

  _at_least_one_mark_complete(false),

  _markStack(this),

  _regionStack(),

  // _finger set in set_non_marking_state

  _max_task_num(MAX2(ParallelGCThreads, (size_t)1)),

  // _active_tasks set in set_non_marking_state

  // _tasks set inside the constructor

  _task_queues(new CMTaskQueueSet((int) _max_task_num)),

  _terminator(ParallelTaskTerminator((int) _max_task_num, _task_queues)),

  _has_overflown(false),

  _concurrent(false),

  _has_aborted(false),

  _restart_for_overflow(false),

  _concurrent_marking_in_progress(false),

  _should_gray_objects(false),

  // _verbose_level set below

  _init_times(),

  _remark_times(), _remark_mark_times(), _remark_weak_ref_times(),

  _cleanup_times(),

  _total_counting_time(0.0),

  _total_rs_scrub_time(0.0),

  _parallel_workers(NULL)

{

  CMVerboseLevel verbose_level =

    (CMVerboseLevel) G1MarkingVerboseLevel;

  if (verbose_level < no_verbose)

    verbose_level = no_verbose;

  if (verbose_level > high_verbose)

    verbose_level = high_verbose;

  _verbose_level = verbose_level;

  if (verbose_low())

    gclog_or_tty->print_cr("[global] init, heap start = "PTR_FORMAT", "

                           "heap end = "PTR_FORMAT, _heap_start, _heap_end);

  _markStack.allocate(MarkStackSize);

  _regionStack.allocate(G1MarkRegionStackSize);

  // Create & start a ConcurrentMark thread.

  _cmThread = new ConcurrentMarkThread(this);

  assert(cmThread() != NULL, "CM Thread should have been created");

  assert(cmThread()->cm() != NULL, "CM Thread should refer to this cm");

  _g1h = G1CollectedHeap::heap();

  assert(CGC_lock != NULL, "Where's the CGC_lock?");

  assert(_markBitMap1.covers(rs), "_markBitMap1 inconsistency");

  assert(_markBitMap2.covers(rs), "_markBitMap2 inconsistency");

  SATBMarkQueueSet& satb_qs = JavaThread::satb_mark_queue_set();

  satb_qs.set_buffer_size(G1SATBBufferSize);

  int size = (int) MAX2(ParallelGCThreads, (size_t)1);

  _par_cleanup_thread_state = NEW_C_HEAP_ARRAY(ParCleanupThreadState*, size);

  for (int i = 0 ; i < size; i++) {

    _par_cleanup_thread_state[i] = new ParCleanupThreadState;

  }

  _tasks = NEW_C_HEAP_ARRAY(CMTask*, _max_task_num);

  _accum_task_vtime = NEW_C_HEAP_ARRAY(double, _max_task_num);

  // so that the assertion in MarkingTaskQueue::task_queue doesn't fail

  _active_tasks = _max_task_num;

  for (int i = 0; i < (int) _max_task_num; ++i) {

    CMTaskQueue* task_queue = new CMTaskQueue();

    task_queue->initialize();

    _task_queues->register_queue(i, task_queue);

    _tasks[i] = new CMTask(i, this, task_queue, _task_queues);

    _accum_task_vtime[i] = 0.0;

  }

  if (ConcGCThreads > ParallelGCThreads) {

    vm_exit_during_initialization("Can't have more ConcGCThreads "

                                  "than ParallelGCThreads.");

  }

  if (ParallelGCThreads == 0) {

    // if we are not running with any parallel GC threads we will not

    // spawn any marking threads either

    _parallel_marking_threads =   0;

    _sleep_factor             = 0.0;

    _marking_task_overhead    = 1.0;

  } else {

    if (ConcGCThreads > 0) {

      // notice that ConcGCThreads overwrites G1MarkingOverheadPercent

      // if both are set

      _parallel_marking_threads = ConcGCThreads;

      _sleep_factor             = 0.0;

      _marking_task_overhead    = 1.0;

    } else if (G1MarkingOverheadPercent > 0) {

      // we will calculate the number of parallel marking threads

      // based on a target overhead with respect to the soft real-time

      // goal

      double marking_overhead = (double) G1MarkingOverheadPercent / 100.0;

      double overall_cm_overhead =

        (double) MaxGCPauseMillis * marking_overhead /

        (double) GCPauseIntervalMillis;

      double cpu_ratio = 1.0 / (double) os::processor_count();

      double marking_thread_num = ceil(overall_cm_overhead / cpu_ratio);

      double marking_task_overhead =

        overall_cm_overhead / marking_thread_num *

                                                (double) os::processor_count();

      double sleep_factor =

                         (1.0 - marking_task_overhead) / marking_task_overhead;

      _parallel_marking_threads = (size_t) marking_thread_num;

      _sleep_factor             = sleep_factor;

      _marking_task_overhead    = marking_task_overhead;

    } else {