/*

 * Copyright (c) 2001, 2018, 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/g1BarrierSet.hpp"

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

#include "gc/g1/g1CollectorState.hpp"

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

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

#include "gc/g1/g1HeapVerifier.hpp"

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

#include "gc/g1/g1Policy.hpp"

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

#include "gc/g1/g1StringDedup.hpp"

#include "gc/g1/g1ThreadLocalData.hpp"

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

#include "gc/g1/heapRegionRemSet.hpp"

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

#include "gc/shared/adaptiveSizePolicy.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/suspendibleThreadSet.hpp"

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

#include "gc/shared/vmGCOperations.hpp"

#include "gc/shared/weakProcessor.hpp"

#include "include/jvm.h"

#include "logging/log.hpp"

#include "memory/allocation.hpp"

#include "memory/resourceArea.hpp"

#include "oops/access.inline.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/java.hpp"

#include "runtime/prefetch.inline.hpp"

#include "services/memTracker.hpp"

#include "utilities/align.hpp"

#include "utilities/growableArray.hpp"

bool G1CMBitMapClosure::do_addr(HeapWord* const addr) {

  assert(addr < _cm->finger(), "invariant");

  assert(addr >= _task->finger(), "invariant");

  // We move that task's local finger along.

  _task->move_finger_to(addr);

  _task->scan_task_entry(G1TaskQueueEntry::from_oop(oop(addr)));

  // we only partially drain the local queue and global stack

  _task->drain_local_queue(true);

  _task->drain_global_stack(true);

  // if the has_aborted flag has been raised, we need to bail out of

  // the iteration

  return !_task->has_aborted();

}

G1CMMarkStack::G1CMMarkStack() :

  _max_chunk_capacity(0),

  _base(NULL),

  _chunk_capacity(0) {

  set_empty();

}

bool G1CMMarkStack::resize(size_t new_capacity) {

  assert(is_empty(), "Only resize when stack is empty.");

  assert(new_capacity <= _max_chunk_capacity,

         "Trying to resize stack to " SIZE_FORMAT " chunks when the maximum is " SIZE_FORMAT, new_capacity, _max_chunk_capacity);

  TaskQueueEntryChunk* new_base = MmapArrayAllocator<TaskQueueEntryChunk>::allocate_or_null(new_capacity, mtGC);

  if (new_base == NULL) {

    log_warning(gc)("Failed to reserve memory for new overflow mark stack with " SIZE_FORMAT " chunks and size " SIZE_FORMAT "B.", new_capacity, new_capacity * sizeof(TaskQueueEntryChunk));

    return false;

  }

  // Release old mapping.

  if (_base != NULL) {

    MmapArrayAllocator<TaskQueueEntryChunk>::free(_base, _chunk_capacity);

  }

  _base = new_base;

  _chunk_capacity = new_capacity;

  set_empty();

  return true;

}

size_t G1CMMarkStack::capacity_alignment() {

  return (size_t)lcm(os::vm_allocation_granularity(), sizeof(TaskQueueEntryChunk)) / sizeof(G1TaskQueueEntry);

}

bool G1CMMarkStack::initialize(size_t initial_capacity, size_t max_capacity) {

  guarantee(_max_chunk_capacity == 0, "G1CMMarkStack already initialized.");

  size_t const TaskEntryChunkSizeInVoidStar = sizeof(TaskQueueEntryChunk) / sizeof(G1TaskQueueEntry);

  _max_chunk_capacity = align_up(max_capacity, capacity_alignment()) / TaskEntryChunkSizeInVoidStar;

  size_t initial_chunk_capacity = align_up(initial_capacity, capacity_alignment()) / TaskEntryChunkSizeInVoidStar;

  guarantee(initial_chunk_capacity <= _max_chunk_capacity,

            "Maximum chunk capacity " SIZE_FORMAT " smaller than initial capacity " SIZE_FORMAT,

            _max_chunk_capacity,

            initial_chunk_capacity);

  log_debug(gc)("Initialize mark stack with " SIZE_FORMAT " chunks, maximum " SIZE_FORMAT,

                initial_chunk_capacity, _max_chunk_capacity);

  return resize(initial_chunk_capacity);

}

void G1CMMarkStack::expand() {

  if (_chunk_capacity == _max_chunk_capacity) {

    log_debug(gc)("Can not expand overflow mark stack further, already at maximum capacity of " SIZE_FORMAT " chunks.", _chunk_capacity);

    return;

  }

  size_t old_capacity = _chunk_capacity;

  // Double capacity if possible

  size_t new_capacity = MIN2(old_capacity * 2, _max_chunk_capacity);

  if (resize(new_capacity)) {

    log_debug(gc)("Expanded mark stack capacity from " SIZE_FORMAT " to " SIZE_FORMAT " chunks",

                  old_capacity, new_capacity);

  } else {

    log_warning(gc)("Failed to expand mark stack capacity from " SIZE_FORMAT " to " SIZE_FORMAT " chunks",

                    old_capacity, new_capacity);

  }

}

G1CMMarkStack::~G1CMMarkStack() {

  if (_base != NULL) {

    MmapArrayAllocator<TaskQueueEntryChunk>::free(_base, _chunk_capacity);

  }

}

void G1CMMarkStack::add_chunk_to_list(TaskQueueEntryChunk* volatile* list, TaskQueueEntryChunk* elem) {

  elem->next = *list;

  *list = elem;

}

void G1CMMarkStack::add_chunk_to_chunk_list(TaskQueueEntryChunk* elem) {

  MutexLockerEx x(MarkStackChunkList_lock, Mutex::_no_safepoint_check_flag);

  add_chunk_to_list(&_chunk_list, elem);

  _chunks_in_chunk_list++;

}

void G1CMMarkStack::add_chunk_to_free_list(TaskQueueEntryChunk* elem) {

  MutexLockerEx x(MarkStackFreeList_lock, Mutex::_no_safepoint_check_flag);

  add_chunk_to_list(&_free_list, elem);

}

G1CMMarkStack::TaskQueueEntryChunk* G1CMMarkStack::remove_chunk_from_list(TaskQueueEntryChunk* volatile* list) {

  TaskQueueEntryChunk* result = *list;

  if (result != NULL) {

    *list = (*list)->next;

  }

  return result;

}

G1CMMarkStack::TaskQueueEntryChunk* G1CMMarkStack::remove_chunk_from_chunk_list() {

  MutexLockerEx x(MarkStackChunkList_lock, Mutex::_no_safepoint_check_flag);

  TaskQueueEntryChunk* result = remove_chunk_from_list(&_chunk_list);

  if (result != NULL) {

    _chunks_in_chunk_list--;

  }

  return result;

}

G1CMMarkStack::TaskQueueEntryChunk* G1CMMarkStack::remove_chunk_from_free_list() {

  MutexLockerEx x(MarkStackFreeList_lock, Mutex::_no_safepoint_check_flag);

  return remove_chunk_from_list(&_free_list);

}

G1CMMarkStack::TaskQueueEntryChunk* G1CMMarkStack::allocate_new_chunk() {

  // This dirty read of _hwm is okay because we only ever increase the _hwm in parallel code.

  // Further this limits _hwm to a value of _chunk_capacity + #threads, avoiding

  // wraparound of _hwm.

  if (_hwm >= _chunk_capacity) {

    return NULL;

  }

  size_t cur_idx = Atomic::add(1u, &_hwm) - 1;

  if (cur_idx >= _chunk_capacity) {

    return NULL;

  }

  TaskQueueEntryChunk* result = ::new (&_base[cur_idx]) TaskQueueEntryChunk;

  result->next = NULL;

  return result;

}

bool G1CMMarkStack::par_push_chunk(G1TaskQueueEntry* ptr_arr) {

  // Get a new chunk.

  TaskQueueEntryChunk* new_chunk = remove_chunk_from_free_list();

  if (new_chunk == NULL) {

    // Did not get a chunk from the free list. Allocate from backing memory.

    new_chunk = allocate_new_chunk();

    if (new_chunk == NULL) {

      return false;

    }

  }

  Copy::conjoint_memory_atomic(ptr_arr, new_chunk->data, EntriesPerChunk * sizeof(G1TaskQueueEntry));

  add_chunk_to_chunk_list(new_chunk);

  return true;

}

bool G1CMMarkStack::par_pop_chunk(G1TaskQueueEntry* ptr_arr) {

  TaskQueueEntryChunk* cur = remove_chunk_from_chunk_list();

  if (cur == NULL) {

    return false;

  }

  Copy::conjoint_memory_atomic(cur->data, ptr_arr, EntriesPerChunk * sizeof(G1TaskQueueEntry));

  add_chunk_to_free_list(cur);

  return true;

}

void G1CMMarkStack::set_empty() {

  _chunks_in_chunk_list = 0;

  _hwm = 0;

  _chunk_list = NULL;

  _free_list = NULL;

}

G1CMRootRegions::G1CMRootRegions() :

  _survivors(NULL), _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;

}

// Returns the maximum number of workers to be used in a concurrent

// phase based on the number of GC workers being used in a STW

// phase.

static uint scale_concurrent_worker_threads(uint num_gc_workers) {

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

}

G1ConcurrentMark::G1ConcurrentMark(G1CollectedHeap* g1h,

                                   G1RegionToSpaceMapper* prev_bitmap_storage,

                                   G1RegionToSpaceMapper* next_bitmap_storage) :

  // _cm_thread set inside the constructor

  _g1h(g1h),

  _completed_initialization(false),

  _mark_bitmap_1(),

  _mark_bitmap_2(),

  _prev_mark_bitmap(&_mark_bitmap_1),

  _next_mark_bitmap(&_mark_bitmap_2),

  _heap(_g1h->reserved_region()),

  _root_regions(),

  _global_mark_stack(),

  // _finger set in set_non_marking_state

  _worker_id_offset(DirtyCardQueueSet::num_par_ids() + G1ConcRefinementThreads),

  _max_num_tasks(ParallelGCThreads),

  // _num_active_tasks set in set_non_marking_state()

  // _tasks set inside the constructor

  _task_queues(new G1CMTaskQueueSet((int) _max_num_tasks)),

  _terminator(ParallelTaskTerminator((int) _max_num_tasks, _task_queues)),

  _first_overflow_barrier_sync(),

  _second_overflow_barrier_sync(),

  _has_overflown(false),

  _concurrent(false),

  _has_aborted(false),

  _restart_for_overflow(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_cleanup_time(0.0),

  _accum_task_vtime(NULL),

  _concurrent_workers(NULL),

  _num_concurrent_workers(0),

  _max_concurrent_workers(0),

  _region_mark_stats(NEW_C_HEAP_ARRAY(G1RegionMarkStats, _g1h->max_regions(), mtGC)),

  _top_at_rebuild_starts(NEW_C_HEAP_ARRAY(HeapWord*, _g1h->max_regions(), mtGC))

{

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

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

  // Create & start ConcurrentMark thread.

  _cm_thread = new G1ConcurrentMarkThread(this);

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

    vm_shutdown_during_initialization("Could not create ConcurrentMarkThread");

  }

  assert(CGC_lock != NULL, "CGC_lock must be initialized");

  SATBMarkQueueSet& satb_qs = G1BarrierSet::satb_mark_queue_set();

  satb_qs.set_buffer_size(G1SATBBufferSize);

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

  if (FLAG_IS_DEFAULT(ConcGCThreads) || ConcGCThreads == 0) {

    // Calculate the number of concurrent worker threads by scaling

    // the number of parallel GC threads.

    uint marking_thread_num = scale_concurrent_worker_threads(ParallelGCThreads);

    FLAG_SET_ERGO(uint, ConcGCThreads, marking_thread_num);

  }

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

  if (ConcGCThreads > ParallelGCThreads) {

    log_warning(gc)("More ConcGCThreads (%u) than ParallelGCThreads (%u).",

                    ConcGCThreads, ParallelGCThreads);

    return;

  }

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

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

  _num_concurrent_workers = ConcGCThreads;

  _max_concurrent_workers = _num_concurrent_workers;

  _concurrent_workers = new WorkGang("G1 Conc", _max_concurrent_workers, false, true);

  _concurrent_workers->initialize_workers();

  if (FLAG_IS_DEFAULT(MarkStackSize)) {

    size_t mark_stack_size =

      MIN2(MarkStackSizeMax,

          MAX2(MarkStackSize, (size_t) (_max_concurrent_workers * 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;

        }

      }

    }

  }

  if (!_global_mark_stack.initialize(MarkStackSize, MarkStackSizeMax)) {

    vm_exit_during_initialization("Failed to allocate initial concurrent mark overflow mark stack.");

  }

  _tasks = NEW_C_HEAP_ARRAY(G1CMTask*, _max_num_tasks, mtGC);

  _accum_task_vtime = NEW_C_HEAP_ARRAY(double, _max_num_tasks, mtGC);

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

  _num_active_tasks = _max_num_tasks;

  for (uint i = 0; i < _max_num_tasks; ++i) {

    G1CMTaskQueue* task_queue = new G1CMTaskQueue();

    task_queue->initialize();