/*

 * Copyright (c) 2001, 2015, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "classfile/metadataOnStackMark.hpp"

#include "classfile/symbolTable.hpp"

#include "code/codeCache.hpp"

#include "gc/g1/concurrentMark.inline.hpp"

#include "gc/g1/concurrentMarkThread.inline.hpp"

#include "gc/g1/g1CollectedHeap.inline.hpp"

#include "gc/g1/g1CollectorPolicy.hpp"

#include "gc/g1/g1CollectorState.hpp"

#include "gc/g1/g1ErgoVerbose.hpp"

#include "gc/g1/g1Log.hpp"

#include "gc/g1/g1OopClosures.inline.hpp"

#include "gc/g1/g1RemSet.hpp"

#include "gc/g1/g1StringDedup.hpp"

#include "gc/g1/heapRegion.inline.hpp"

#include "gc/g1/heapRegionManager.inline.hpp"

#include "gc/g1/heapRegionRemSet.hpp"

#include "gc/g1/heapRegionSet.inline.hpp"

#include "gc/g1/suspendibleThreadSet.hpp"

#include "gc/shared/gcId.hpp"

#include "gc/shared/gcTimer.hpp"

#include "gc/shared/gcTrace.hpp"

#include "gc/shared/gcTraceTime.hpp"

#include "gc/shared/genOopClosures.inline.hpp"

#include "gc/shared/referencePolicy.hpp"

#include "gc/shared/strongRootsScope.hpp"

#include "gc/shared/taskqueue.inline.hpp"

#include "gc/shared/vmGCOperations.hpp"

#include "memory/allocation.hpp"

#include "memory/resourceArea.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.inline.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/java.hpp"

#include "runtime/prefetch.inline.hpp"

#include "services/memTracker.hpp"

// Concurrent marking bit map wrapper

CMBitMapRO::CMBitMapRO(int shifter) :

  _bm(),

  _shifter(shifter) {

  _bmStartWord = 0;

  _bmWordSize = 0;

}

HeapWord* CMBitMapRO::getNextMarkedWordAddress(const HeapWord* addr,

                                               const 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(const HeapWord* addr,

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

}

#ifndef PRODUCT

bool CMBitMapRO::covers(MemRegion heap_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*)(heap_rs.start()) &&

         _bmWordSize  == heap_rs.word_size();

}

#endif

void CMBitMapRO::print_on_error(outputStream* st, const char* prefix) const {

  _bm.print_on_error(st, prefix);

}

size_t CMBitMap::compute_size(size_t heap_size) {

  return ReservedSpace::allocation_align_size_up(heap_size / mark_distance());

}

size_t CMBitMap::mark_distance() {

  return MinObjAlignmentInBytes * BitsPerByte;

}

void CMBitMap::initialize(MemRegion heap, G1RegionToSpaceMapper* storage) {

  _bmStartWord = heap.start();

  _bmWordSize = heap.word_size();

  _bm.set_map((BitMap::bm_word_t*) storage->reserved().start());

  _bm.set_size(_bmWordSize >> _shifter);

  storage->set_mapping_changed_listener(&_listener);

}

void CMBitMapMappingChangedListener::on_commit(uint start_region, size_t num_regions, bool zero_filled) {

  if (zero_filled) {

    return;

  }

  // We need to clear the bitmap on commit, removing any existing information.

  MemRegion mr(G1CollectedHeap::heap()->bottom_addr_for_region(start_region), num_regions * HeapRegion::GrainWords);

  _bm->clearRange(mr);

}

// Closure used for clearing the given mark bitmap.

class ClearBitmapHRClosure : public HeapRegionClosure {

 private:

  ConcurrentMark* _cm;

  CMBitMap* _bitmap;

  bool _may_yield;      // The closure may yield during iteration. If yielded, abort the iteration.

 public:

  ClearBitmapHRClosure(ConcurrentMark* cm, CMBitMap* bitmap, bool may_yield) : HeapRegionClosure(), _cm(cm), _bitmap(bitmap), _may_yield(may_yield) {

    assert(!may_yield || cm != NULL, "CM must be non-NULL if this closure is expected to yield.");

  }

  virtual bool doHeapRegion(HeapRegion* r) {

    size_t const chunk_size_in_words = M / HeapWordSize;

    HeapWord* cur = r->bottom();

    HeapWord* const end = r->end();

    while (cur < end) {

      MemRegion mr(cur, MIN2(cur + chunk_size_in_words, end));

      _bitmap->clearRange(mr);

      cur += chunk_size_in_words;

      // Abort iteration if after yielding the marking has been aborted.

      if (_may_yield && _cm->do_yield_check() && _cm->has_aborted()) {

        return true;

      }

      // Repeat the asserts from before the start of the closure. We will do them

      // as asserts here to minimize their overhead on the product. However, we

      // will have them as guarantees at the beginning / end of the bitmap

      // clearing to get some checking in the product.

      assert(!_may_yield || _cm->cmThread()->during_cycle(), "invariant");

      assert(!_may_yield || !G1CollectedHeap::heap()->collector_state()->mark_in_progress(), "invariant");

    }

    return false;

  }

};

class ParClearNextMarkBitmapTask : public AbstractGangTask {

  ClearBitmapHRClosure* _cl;

  HeapRegionClaimer     _hrclaimer;

  bool                  _suspendible; // If the task is suspendible, workers must join the STS.

public:

  ParClearNextMarkBitmapTask(ClearBitmapHRClosure *cl, uint n_workers, bool suspendible) :

      _cl(cl), _suspendible(suspendible), AbstractGangTask("Parallel Clear Bitmap Task"), _hrclaimer(n_workers) {}

  void work(uint worker_id) {

    SuspendibleThreadSetJoiner sts_join(_suspendible);

    G1CollectedHeap::heap()->heap_region_par_iterate(_cl, worker_id, &_hrclaimer, true);

  }

};

void CMBitMap::clearAll() {

  G1CollectedHeap* g1h = G1CollectedHeap::heap();

  ClearBitmapHRClosure cl(NULL, this, false /* may_yield */);

  uint n_workers = g1h->workers()->active_workers();

  ParClearNextMarkBitmapTask task(&cl, n_workers, false);

  g1h->workers()->run_task(&task);

  guarantee(cl.complete(), "Must have completed iteration.");

  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)

{}

bool CMMarkStack::allocate(size_t capacity) {

  // allocate a stack of the requisite depth

  ReservedSpace rs(ReservedSpace::allocation_align_size_up(capacity * sizeof(oop)));

  if (!rs.is_reserved()) {

    warning("ConcurrentMark MarkStack allocation failure");

    return false;

  }

  MemTracker::record_virtual_memory_type((address)rs.base(), mtGC);

  if (!_virtual_space.initialize(rs, rs.size())) {

    warning("ConcurrentMark MarkStack backing store failure");

    // Release the virtual memory reserved for the marking stack

    rs.release();

    return false;

  }

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

         "Didn't reserve backing store for all of ConcurrentMark stack?");

  _base = (oop*) _virtual_space.low();

  setEmpty();

  _capacity = (jint) capacity;

  _saved_index = -1;

  _should_expand = false;

  return true;

}

void CMMarkStack::expand() {

  // Called, during remark, if we've overflown the marking stack during marking.

  assert(isEmpty(), "stack should been emptied while handling overflow");

  assert(_capacity <= (jint) MarkStackSizeMax, "stack bigger than permitted");

  // Clear expansion flag

  _should_expand = false;

  if (_capacity == (jint) MarkStackSizeMax) {

    if (PrintGCDetails && Verbose) {

      gclog_or_tty->print_cr(" (benign) Can't expand marking stack capacity, at max size limit");

    }

    return;

  }

  // Double capacity if possible

  jint new_capacity = MIN2(_capacity*2, (jint) MarkStackSizeMax);

  // Do not give up existing stack until we have managed to

  // get the double capacity that we desired.

  ReservedSpace rs(ReservedSpace::allocation_align_size_up(new_capacity *

                                                           sizeof(oop)));

  if (rs.is_reserved()) {

    // Release the backing store associated with old stack

    _virtual_space.release();

    // Reinitialize virtual space for new stack

    if (!_virtual_space.initialize(rs, rs.size())) {

      fatal("Not enough swap for expanded marking stack capacity");

    }

    _base = (oop*)(_virtual_space.low());

    _index = 0;

    _capacity = new_capacity;

  } else {

    if (PrintGCDetails && Verbose) {

      // Failed to double capacity, continue;

      gclog_or_tty->print(" (benign) Failed to expand marking stack capacity from "

                          SIZE_FORMAT "K to " SIZE_FORMAT "K",

                          _capacity / K, new_capacity / K);

    }

  }

}

void CMMarkStack::set_should_expand() {

  // If we're resetting the marking state because of an

  // marking stack overflow, record that we should, if

  // possible, expand the stack.

  _should_expand = _cm->has_overflown();

}

CMMarkStack::~CMMarkStack() {

  if (_base != NULL) {

    _base = NULL;

    _virtual_space.release();

  }

}

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;

  }

}

void CMMarkStack::note_start_of_gc() {

  assert(_saved_index == -1,

         "note_start_of_gc()/end_of_gc() bracketed incorrectly");

  _saved_index = _index;

}

void CMMarkStack::note_end_of_gc() {

  // This is intentionally a guarantee, instead of an assert. If we

  // accidentally add something to the mark stack during GC, it

  // will be a correctness issue so it's better if we crash. we'll

  // only check this once per GC anyway, so it won't be a performance

  // issue in any way.

  guarantee(_saved_index == _index,

            "saved index: %d index: %d", _saved_index, _index);

  _saved_index = -1;

}

CMRootRegions::CMRootRegions() :

  _young_list(NULL), _cm(NULL), _scan_in_progress(false),

  _should_abort(false),  _next_survivor(NULL) { }

void CMRootRegions::init(G1CollectedHeap* g1h, ConcurrentMark* cm) {

  _young_list = g1h->young_list();

  _cm = cm;

}

void CMRootRegions::prepare_for_scan() {

  assert(!scan_in_progress(), "pre-condition");

  // Currently, only survivors can be root regions.

  assert(_next_survivor == NULL, "pre-condition");

  _next_survivor = _young_list->first_survivor_region();

  _scan_in_progress = (_next_survivor != NULL);

  _should_abort = false;

}

HeapRegion* CMRootRegions::claim_next() {

  if (_should_abort) {

    // If someone has set the should_abort flag, we return NULL to

    // force the caller to bail out of their loop.

    return NULL;

  }

  // Currently, only survivors can be root regions.

  HeapRegion* res = _next_survivor;

  if (res != NULL) {

    MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);

    // Read it again in case it changed while we were waiting for the lock.

    res = _next_survivor;

    if (res != NULL) {

      if (res == _young_list->last_survivor_region()) {

        // We just claimed the last survivor so store NULL to indicate

        // that we're done.

        _next_survivor = NULL;

      } else {

        _next_survivor = res->get_next_young_region();

      }

    } else {

      // Someone else claimed the last survivor while we were trying

      // to take the lock so nothing else to do.

    }

  }

  assert(res == NULL || res->is_survivor(), "post-condition");

  return res;

}

void CMRootRegions::scan_finished() {

  assert(scan_in_progress(), "pre-condition");

  // Currently, only survivors can be root regions.

  if (!_should_abort) {

    assert(_next_survivor == NULL, "we should have claimed all survivors");

  }

  _next_survivor = NULL;

  {

    MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);

    _scan_in_progress = false;

    RootRegionScan_lock->notify_all();

  }

}

bool CMRootRegions::wait_until_scan_finished() {

  if (!scan_in_progress()) return false;

  {

    MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);

    while (scan_in_progress()) {

      RootRegionScan_lock->wait(Mutex::_no_safepoint_check_flag);

    }

  }

  return true;

}

uint ConcurrentMark::scale_parallel_threads(uint n_par_threads) {

  return MAX2((n_par_threads + 2) / 4, 1U);

}

ConcurrentMark::ConcurrentMark(G1CollectedHeap* g1h, G1RegionToSpaceMapper* prev_bitmap_storage, G1RegionToSpaceMapper* next_bitmap_storage) :

  _g1h(g1h),

  _markBitMap1(),

  _markBitMap2(),

  _parallel_marking_threads(0),

  _max_parallel_marking_threads(0),

  _sleep_factor(0.0),

  _marking_task_overhead(1.0),

  _cleanup_sleep_factor(0.0),

  _cleanup_task_overhead(1.0),

  _cleanup_list("Cleanup List"),

  _region_bm((BitMap::idx_t)(g1h->max_regions()), false /* in_resource_area*/),

  _card_bm((g1h->reserved_region().byte_size() + CardTableModRefBS::card_size - 1) >>

            CardTableModRefBS::card_shift,

            false /* in_resource_area*/),

  _prevMarkBitMap(&_markBitMap1),

  _nextMarkBitMap(&_markBitMap2),

  _markStack(this),

  // _finger set in set_non_marking_state

  _max_worker_id(ParallelGCThreads),

  // _active_tasks set in set_non_marking_state

  // _tasks set inside the constructor

  _task_queues(new CMTaskQueueSet((int) _max_worker_id)),

  _terminator(ParallelTaskTerminator((int) _max_worker_id, _task_queues)),

  _has_overflown(false),

  _concurrent(false),

  _has_aborted(false),

  _restart_for_overflow(false),

  _concurrent_marking_in_progress(false),

  // _verbose_level set below

  _init_times(),

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

  _cleanup_times(),