/*

 * Copyright (c) 2001, 2016, 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/concurrentMarkThread.inline.hpp"

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

#include "gc/g1/g1CollectorState.hpp"

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

#include "gc/g1/g1HeapVerifier.hpp"

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

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

#include "gc/g1/g1Policy.hpp"

#include "gc/g1/g1StringDedup.hpp"

#include "gc/g1/heapRegion.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.inline.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 "logging/log.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"

#include "utilities/growableArray.hpp"

// Concurrent marking bit map wrapper

G1CMBitMapRO::G1CMBitMapRO(int shifter) :

  _bm(),

  _shifter(shifter) {

  _bmStartWord = 0;

  _bmWordSize = 0;

}

HeapWord* G1CMBitMapRO::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);

  assert(limit != NULL, "limit must not be NULL");

  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;

}

#ifndef PRODUCT

bool G1CMBitMapRO::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 G1CMBitMapRO::print_on_error(outputStream* st, const char* prefix) const {

  _bm.print_on_error(st, prefix);

}

size_t G1CMBitMap::compute_size(size_t heap_size) {

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

}

size_t G1CMBitMap::mark_distance() {

  return MinObjAlignmentInBytes * BitsPerByte;

}

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

  _bmStartWord = heap.start();

  _bmWordSize = heap.word_size();

  _bm = BitMapView((BitMap::bm_word_t*) storage->reserved().start(), _bmWordSize >> _shifter);

  storage->set_mapping_changed_listener(&_listener);

}

void G1CMBitMapMappingChangedListener::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->clear_range(mr);

}

void G1CMBitMap::clear_range(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);

}

  if (!rs.is_reserved()) {

    return false;

  }

    rs.release();

    return false;

  }

  _should_expand = false;

  return true;

}

void G1CMMarkStack::expand() {

  // Clear expansion flag

  _should_expand = false;

    return;

  }

  // Double capacity if possible

  } else {

  }

}

G1CMMarkStack::~G1CMMarkStack() {

  if (_base != NULL) {

    _base = NULL;

  }

}

  MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

  if (next_index > _capacity) {

    _overflow = true;

    return;

  }

  // Otherwise.

  _index = next_index;

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

  }

}

  MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);

  if (index == 0) {

    *n = 0;

    return false;

  } else {

    }

    _index = new_ind;

    *n = k;

    return true;

  }

}

void G1CMMarkStack::note_start_of_gc() {

  _saved_index = _index;

}

void G1CMMarkStack::note_end_of_gc() {

}

G1CMRootRegions::G1CMRootRegions() :

  _cm(NULL), _scan_in_progress(false),

  _should_abort(false), _claimed_survivor_index(0) { }

void G1CMRootRegions::init(const G1SurvivorRegions* survivors, G1ConcurrentMark* cm) {

  _survivors = survivors;

  _cm = cm;

}

void G1CMRootRegions::prepare_for_scan() {

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

  // Currently, only survivors can be root regions.

  _claimed_survivor_index = 0;

  _scan_in_progress = _survivors->regions()->is_nonempty();

  _should_abort = false;

}

HeapRegion* G1CMRootRegions::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.

  const GrowableArray<HeapRegion*>* survivor_regions = _survivors->regions();

  int claimed_index = Atomic::add(1, &_claimed_survivor_index) - 1;

  if (claimed_index < survivor_regions->length()) {

    return survivor_regions->at(claimed_index);

  }

  return NULL;

}

uint G1CMRootRegions::num_root_regions() const {

  return (uint)_survivors->regions()->length();

}

void G1CMRootRegions::notify_scan_done() {

  MutexLockerEx x(RootRegionScan_lock, Mutex::_no_safepoint_check_flag);

  _scan_in_progress = false;

  RootRegionScan_lock->notify_all();

}

void G1CMRootRegions::cancel_scan() {

  notify_scan_done();

}

void G1CMRootRegions::scan_finished() {

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

  // Currently, only survivors can be root regions.

  if (!_should_abort) {

    assert(_claimed_survivor_index >= 0, "otherwise comparison is invalid: %d", _claimed_survivor_index);

    assert((uint)_claimed_survivor_index >= _survivors->length(),

           "we should have claimed all survivors, claimed index = %u, length = %u",

           (uint)_claimed_survivor_index, _survivors->length());

  }

  notify_scan_done();

}

bool G1CMRootRegions::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 G1ConcurrentMark::scale_parallel_threads(uint n_par_threads) {

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

}

G1ConcurrentMark::G1ConcurrentMark(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_list("Cleanup List"),

  _prevMarkBitMap(&_markBitMap1),

  _nextMarkBitMap(&_markBitMap2),

  // _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 G1CMTaskQueueSet((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),

  _gc_timer_cm(new (ResourceObj::C_HEAP, mtGC) ConcurrentGCTimer()),

  _gc_tracer_cm(new (ResourceObj::C_HEAP, mtGC) G1OldTracer()),

  // _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),

  _completed_initialization(false) {

  _markBitMap1.initialize(g1h->reserved_region(), prev_bitmap_storage);

  _markBitMap2.initialize(g1h->reserved_region(), next_bitmap_storage);

  // 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");

  if (_cmThread->osthread() == NULL) {

      vm_shutdown_during_initialization("Could not create ConcurrentMarkThread");

  }

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

  assert(_markBitMap1.covers(g1h->reserved_region()), "_markBitMap1 inconsistency");

  assert(_markBitMap2.covers(g1h->reserved_region()), "_markBitMap2 inconsistency");

  SATBMarkQueueSet& satb_qs = JavaThread::satb_mark_queue_set();

  satb_qs.set_buffer_size(G1SATBBufferSize);

  _root_regions.init(_g1h->survivor(), this);

  if (ConcGCThreads > ParallelGCThreads) {

    log_warning(gc)("Can't have more ConcGCThreads (%u) than ParallelGCThreads (%u).",

                    ConcGCThreads, ParallelGCThreads);

    return;

  }

  if (!FLAG_IS_DEFAULT(ConcGCThreads) && ConcGCThreads > 0) {

    // Note: ConcGCThreads has precedence over G1MarkingOverheadPercent

    // if both are set

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

    FLAG_SET_ERGO(uint, ConcGCThreads, (uint) marking_thread_num);

    _sleep_factor             = sleep_factor;

    _marking_task_overhead    = marking_task_overhead;

  } else {

    // Calculate the number of parallel marking threads by scaling

    // the number of parallel GC threads.

    uint marking_thread_num = scale_parallel_threads(ParallelGCThreads);

    FLAG_SET_ERGO(uint, ConcGCThreads, marking_thread_num);

    _sleep_factor             = 0.0;

    _marking_task_overhead    = 1.0;

  }

  assert(ConcGCThreads > 0, "Should have been set");

  log_debug(gc)("ConcGCThreads: %u", ConcGCThreads);

  log_debug(gc)("ParallelGCThreads: %u", ParallelGCThreads);

  _parallel_marking_threads = ConcGCThreads;

  _max_parallel_marking_threads = _parallel_marking_threads;

  _parallel_workers = new WorkGang("G1 Marker",

       _max_parallel_marking_threads, false, true);

  if (_parallel_workers == NULL) {

    vm_exit_during_initialization("Failed necessary allocation.");

  } else {

    _parallel_workers->initialize_workers();

  }

  if (FLAG_IS_DEFAULT(MarkStackSize)) {

    size_t mark_stack_size =

      MIN2(MarkStackSizeMax,

          MAX2(MarkStackSize, (size_t) (parallel_marking_threads() * TASKQUEUE_SIZE)));

    // Verify that the calculated value for MarkStackSize is in range.

    // It would be nice to use the private utility routine from Arguments.

    if (!(mark_stack_size >= 1 && mark_stack_size <= MarkStackSizeMax)) {

      log_warning(gc)("Invalid value calculated for MarkStackSize (" SIZE_FORMAT "): "

                      "must be between 1 and " SIZE_FORMAT,

                      mark_stack_size, MarkStackSizeMax);

      return;

    }

    FLAG_SET_ERGO(size_t, MarkStackSize, mark_stack_size);

  } else {

    // Verify MarkStackSize is in range.

    if (FLAG_IS_CMDLINE(MarkStackSize)) {

      if (FLAG_IS_DEFAULT(MarkStackSizeMax)) {

        if (!(MarkStackSize >= 1 && MarkStackSize <= MarkStackSizeMax)) {

          log_warning(gc)("Invalid value specified for MarkStackSize (" SIZE_FORMAT "): "

                          "must be between 1 and " SIZE_FORMAT,

                          MarkStackSize, MarkStackSizeMax);

          return;

        }

      } else if (FLAG_IS_CMDLINE(MarkStackSizeMax)) {

        if (!(MarkStackSize >= 1 && MarkStackSize <= MarkStackSizeMax)) {

          log_warning(gc)("Invalid value specified for MarkStackSize (" SIZE_FORMAT ")"

                          " or for MarkStackSizeMax (" SIZE_FORMAT ")",

                          MarkStackSize, MarkStackSizeMax);

          return;

        }

      }

    }

  }

    return;