/*

 * 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 "gc/cms/compactibleFreeListSpace.hpp"

#include "gc/cms/concurrentMarkSweepGeneration.hpp"

#include "gc/cms/parNewGeneration.inline.hpp"

#include "gc/cms/parOopClosures.inline.hpp"

#include "gc/serial/defNewGeneration.inline.hpp"

#include "gc/shared/adaptiveSizePolicy.hpp"

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

#include "gc/shared/copyFailedInfo.hpp"

#include "gc/shared/gcHeapSummary.hpp"

#include "gc/shared/gcTimer.hpp"

#include "gc/shared/gcTrace.hpp"

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

#include "gc/shared/genCollectedHeap.hpp"

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

#include "gc/shared/generation.hpp"

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

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

#include "gc/shared/referencePolicy.hpp"

#include "gc/shared/space.hpp"

#include "gc/shared/spaceDecorator.hpp"

#include "gc/shared/strongRootsScope.hpp"

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

#include "gc/shared/workgroup.hpp"

#include "logging/log.hpp"

#include "memory/resourceArea.hpp"

#include "oops/objArrayOop.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.inline.hpp"

#include "runtime/handles.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/java.hpp"

#include "runtime/thread.inline.hpp"

#include "utilities/copy.hpp"

#include "utilities/globalDefinitions.hpp"

#include "utilities/stack.inline.hpp"

ParScanThreadState::ParScanThreadState(Space* to_space_,

                                       ParNewGeneration* young_gen_,

                                       Generation* old_gen_,

                                       int thread_num_,

                                       ObjToScanQueueSet* work_queue_set_,

                                       Stack<oop, mtGC>* overflow_stacks_,

                                       PreservedMarks* preserved_marks_,

                                       size_t desired_plab_sz_,

                                       ParallelTaskTerminator& term_) :

  _to_space(to_space_),

  _old_gen(old_gen_),

  _young_gen(young_gen_),

  _thread_num(thread_num_),

  _work_queue(work_queue_set_->queue(thread_num_)),

  _to_space_full(false),

  _overflow_stack(overflow_stacks_ ? overflow_stacks_ + thread_num_ : NULL),

  _preserved_marks(preserved_marks_),

  _ageTable(false), // false ==> not the global age table, no perf data.

  _to_space_alloc_buffer(desired_plab_sz_),

  _to_space_closure(young_gen_, this),

  _old_gen_closure(young_gen_, this),

  _to_space_root_closure(young_gen_, this),

  _old_gen_root_closure(young_gen_, this),

  _older_gen_closure(young_gen_, this),

  _evacuate_followers(this, &_to_space_closure, &_old_gen_closure,

                      &_to_space_root_closure, young_gen_, &_old_gen_root_closure,

                      work_queue_set_, &term_),

  _is_alive_closure(young_gen_),

  _scan_weak_ref_closure(young_gen_, this),

  _keep_alive_closure(&_scan_weak_ref_closure),

  _strong_roots_time(0.0),

  _term_time(0.0)

{

  #if TASKQUEUE_STATS

  _term_attempts = 0;

  _overflow_refills = 0;

  _overflow_refill_objs = 0;

  #endif // TASKQUEUE_STATS

  _survivor_chunk_array = (ChunkArray*) old_gen()->get_data_recorder(thread_num());

  _hash_seed = 17;  // Might want to take time-based random value.

  _start = os::elapsedTime();

  _old_gen_closure.set_generation(old_gen_);

  _old_gen_root_closure.set_generation(old_gen_);

}

void ParScanThreadState::record_survivor_plab(HeapWord* plab_start,

                                              size_t plab_word_size) {

  ChunkArray* sca = survivor_chunk_array();

  if (sca != NULL) {

    // A non-null SCA implies that we want the PLAB data recorded.

    sca->record_sample(plab_start, plab_word_size);

  }

}

bool ParScanThreadState::should_be_partially_scanned(oop new_obj, oop old_obj) const {

  return new_obj->is_objArray() &&

         arrayOop(new_obj)->length() > ParGCArrayScanChunk &&

         new_obj != old_obj;

}

void ParScanThreadState::scan_partial_array_and_push_remainder(oop old) {

  assert(old->is_objArray(), "must be obj array");

  assert(old->is_forwarded(), "must be forwarded");

  assert(GenCollectedHeap::heap()->is_in_reserved(old), "must be in heap.");

  assert(!old_gen()->is_in(old), "must be in young generation.");

  objArrayOop obj = objArrayOop(old->forwardee());

  // Process ParGCArrayScanChunk elements now

  // and push the remainder back onto queue

  int start     = arrayOop(old)->length();

  int end       = obj->length();

  int remainder = end - start;

  assert(start <= end, "just checking");

  if (remainder > 2 * ParGCArrayScanChunk) {

    // Test above combines last partial chunk with a full chunk

    end = start + ParGCArrayScanChunk;

    arrayOop(old)->set_length(end);

    // Push remainder.

    bool ok = work_queue()->push(old);

    assert(ok, "just popped, push must be okay");

  } else {

    // Restore length so that it can be used if there

    // is a promotion failure and forwarding pointers

    // must be removed.

    arrayOop(old)->set_length(end);

  }

  // process our set of indices (include header in first chunk)

  // should make sure end is even (aligned to HeapWord in case of compressed oops)

  if ((HeapWord *)obj < young_old_boundary()) {

    // object is in to_space

    obj->oop_iterate_range(&_to_space_closure, start, end);

  } else {

    // object is in old generation

    obj->oop_iterate_range(&_old_gen_closure, start, end);

  }

}

void ParScanThreadState::trim_queues(int max_size) {

  ObjToScanQueue* queue = work_queue();

  do {

    while (queue->size() > (juint)max_size) {

      oop obj_to_scan;

      if (queue->pop_local(obj_to_scan)) {

        if ((HeapWord *)obj_to_scan < young_old_boundary()) {

          if (obj_to_scan->is_objArray() &&

              obj_to_scan->is_forwarded() &&

              obj_to_scan->forwardee() != obj_to_scan) {

            scan_partial_array_and_push_remainder(obj_to_scan);

          } else {

            // object is in to_space

            obj_to_scan->oop_iterate(&_to_space_closure);

          }

        } else {

          // object is in old generation

          obj_to_scan->oop_iterate(&_old_gen_closure);

        }

      }

    }

    // For the  case of compressed oops, we have a private, non-shared

    // overflow stack, so we eagerly drain it so as to more evenly

    // distribute load early. Note: this may be good to do in

    // general rather than delay for the final stealing phase.

    // If applicable, we'll transfer a set of objects over to our

    // work queue, allowing them to be stolen and draining our

    // private overflow stack.

  } while (ParGCTrimOverflow && young_gen()->take_from_overflow_list(this));

}

bool ParScanThreadState::take_from_overflow_stack() {

  assert(ParGCUseLocalOverflow, "Else should not call");

  assert(young_gen()->overflow_list() == NULL, "Error");

  ObjToScanQueue* queue = work_queue();

  Stack<oop, mtGC>* const of_stack = overflow_stack();

  const size_t num_overflow_elems = of_stack->size();

  const size_t space_available = queue->max_elems() - queue->size();

  const size_t num_take_elems = MIN3(space_available / 4,

                                     ParGCDesiredObjsFromOverflowList,

                                     num_overflow_elems);

  // Transfer the most recent num_take_elems from the overflow

  // stack to our work queue.

  for (size_t i = 0; i != num_take_elems; i++) {

    oop cur = of_stack->pop();

    oop obj_to_push = cur->forwardee();

    assert(GenCollectedHeap::heap()->is_in_reserved(cur), "Should be in heap");

    assert(!old_gen()->is_in_reserved(cur), "Should be in young gen");

    assert(GenCollectedHeap::heap()->is_in_reserved(obj_to_push), "Should be in heap");

    if (should_be_partially_scanned(obj_to_push, cur)) {

      assert(arrayOop(cur)->length() == 0, "entire array remaining to be scanned");

      obj_to_push = cur;

    }

    bool ok = queue->push(obj_to_push);

    assert(ok, "Should have succeeded");

  }

  assert(young_gen()->overflow_list() == NULL, "Error");

  return num_take_elems > 0;  // was something transferred?

}

void ParScanThreadState::push_on_overflow_stack(oop p) {

  assert(ParGCUseLocalOverflow, "Else should not call");

  overflow_stack()->push(p);

  assert(young_gen()->overflow_list() == NULL, "Error");

}

HeapWord* ParScanThreadState::alloc_in_to_space_slow(size_t word_sz) {

  // If the object is small enough, try to reallocate the buffer.

  HeapWord* obj = NULL;

  if (!_to_space_full) {

    PLAB* const plab = to_space_alloc_buffer();

    Space* const sp  = to_space();

    if (word_sz * 100 < ParallelGCBufferWastePct * plab->word_sz()) {

      // Is small enough; abandon this buffer and start a new one.

      plab->retire();

      // The minimum size has to be twice SurvivorAlignmentInBytes to

      // allow for padding used in the alignment of 1 word.  A padding

      // of 1 is too small for a filler word so the padding size will

      // be increased by SurvivorAlignmentInBytes.

      size_t min_usable_size = 2 * static_cast<size_t>(SurvivorAlignmentInBytes >> LogHeapWordSize);

      size_t buf_size = MAX2(plab->word_sz(), min_usable_size);

      HeapWord* buf_space = sp->par_allocate(buf_size);

      if (buf_space == NULL) {

        const size_t min_bytes = MAX2(PLAB::min_size(), min_usable_size) << LogHeapWordSize;

        size_t free_bytes = sp->free();

        while(buf_space == NULL && free_bytes >= min_bytes) {

          buf_size = free_bytes >> LogHeapWordSize;

          assert(buf_size == (size_t)align_object_size(buf_size), "Invariant");

          buf_space  = sp->par_allocate(buf_size);

          free_bytes = sp->free();

        }

      }

      if (buf_space != NULL) {

        plab->set_buf(buf_space, buf_size);

        record_survivor_plab(buf_space, buf_size);

        obj = plab->allocate_aligned(word_sz, SurvivorAlignmentInBytes);

        // Note that we cannot compare buf_size < word_sz below

        // because of AlignmentReserve (see PLAB::allocate()).

        assert(obj != NULL || plab->words_remaining() < word_sz,

               "Else should have been able to allocate requested object size "

               SIZE_FORMAT ", PLAB size " SIZE_FORMAT ", SurvivorAlignmentInBytes "

               SIZE_FORMAT ", words_remaining " SIZE_FORMAT,

               word_sz, buf_size, SurvivorAlignmentInBytes, plab->words_remaining());

        // It's conceivable that we may be able to use the

        // buffer we just grabbed for subsequent small requests

        // even if not for this one.

      } else {

        // We're used up.

        _to_space_full = true;

      }

    } else {

      // Too large; allocate the object individually.

      obj = sp->par_allocate(word_sz);

    }

  }

  return obj;

}

void ParScanThreadState::undo_alloc_in_to_space(HeapWord* obj, size_t word_sz) {

  to_space_alloc_buffer()->undo_allocation(obj, word_sz);

}

void ParScanThreadState::print_promotion_failure_size() {

  if (_promotion_failed_info.has_failed()) {

    log_trace(gc, promotion)(" (%d: promotion failure size = " SIZE_FORMAT ") ",

                             _thread_num, _promotion_failed_info.first_size());

  }

}

class ParScanThreadStateSet: StackObj {

public:

  // Initializes states for the specified number of threads;

  ParScanThreadStateSet(int                     num_threads,

                        Space&                  to_space,

                        ParNewGeneration&       young_gen,

                        Generation&             old_gen,

                        ObjToScanQueueSet&      queue_set,

                        Stack<oop, mtGC>*       overflow_stacks_,

                        PreservedMarksSet&      preserved_marks_set,

                        size_t                  desired_plab_sz,

                        ParallelTaskTerminator& term);

  ~ParScanThreadStateSet() { TASKQUEUE_STATS_ONLY(reset_stats()); }

  inline ParScanThreadState& thread_state(int i);

  void trace_promotion_failed(const YoungGCTracer* gc_tracer);

  void reset(uint active_workers, bool promotion_failed);

  void flush();

  #if TASKQUEUE_STATS

  static void

    print_termination_stats_hdr(outputStream* const st);

  void print_termination_stats();

  static void

    print_taskqueue_stats_hdr(outputStream* const st);

  void print_taskqueue_stats();

  void reset_stats();

  #endif // TASKQUEUE_STATS

private:

  ParallelTaskTerminator& _term;

  ParNewGeneration&       _young_gen;

  Generation&             _old_gen;

  ParScanThreadState*     _per_thread_states;

  const int               _num_threads;

 public:

  bool is_valid(int id) const { return id < _num_threads; }

  ParallelTaskTerminator* terminator() { return &_term; }

};

ParScanThreadStateSet::ParScanThreadStateSet(int num_threads,

                                             Space& to_space,

                                             ParNewGeneration& young_gen,

                                             Generation& old_gen,

                                             ObjToScanQueueSet& queue_set,

                                             Stack<oop, mtGC>* overflow_stacks,

                                             PreservedMarksSet& preserved_marks_set,

                                             size_t desired_plab_sz,

                                             ParallelTaskTerminator& term)

  : _young_gen(young_gen),

    _old_gen(old_gen),

    _term(term),

    _per_thread_states(NEW_RESOURCE_ARRAY(ParScanThreadState, num_threads)),

    _num_threads(num_threads)

{

  assert(num_threads > 0, "sanity check!");

  assert(ParGCUseLocalOverflow == (overflow_stacks != NULL),

         "overflow_stack allocation mismatch");

  // Initialize states.

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

    new(_per_thread_states + i)

      ParScanThreadState(&to_space, &young_gen, &old_gen, i, &queue_set,

                         overflow_stacks, preserved_marks_set.get(i),

                         desired_plab_sz, term);

  }

}

inline ParScanThreadState& ParScanThreadStateSet::thread_state(int i) {

  assert(i >= 0 && i < _num_threads, "sanity check!");

  return _per_thread_states[i];

}

void ParScanThreadStateSet::trace_promotion_failed(const YoungGCTracer* gc_tracer) {

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

    if (thread_state(i).promotion_failed()) {

      gc_tracer->report_promotion_failed(thread_state(i).promotion_failed_info());

      thread_state(i).promotion_failed_info().reset();

    }

  }

}

void ParScanThreadStateSet::reset(uint active_threads, bool promotion_failed) {

  _term.reset_for_reuse(active_threads);

  if (promotion_failed) {

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

      thread_state(i).print_promotion_failure_size();

    }

  }

}

#if TASKQUEUE_STATS

void ParScanThreadState::reset_stats() {

  taskqueue_stats().reset();

  _term_attempts = 0;

  _overflow_refills = 0;

  _overflow_refill_objs = 0;

}

void ParScanThreadStateSet::reset_stats() {

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

    thread_state(i).reset_stats();

  }

}

void ParScanThreadStateSet::print_termination_stats_hdr(outputStream* const st) {

  st->print_raw_cr("GC Termination Stats");

  st->print_raw_cr("     elapsed  --strong roots-- -------termination-------");

  st->print_raw_cr("thr     ms        ms       %       ms       %   attempts");

  st->print_raw_cr("--- --------- --------- ------ --------- ------ --------");

}

void ParScanThreadStateSet::print_termination_stats() {

  Log(gc, task, stats) log;

  if (!log.is_debug()) {

    return;

  }

  ResourceMark rm;

  outputStream* st = log.debug_stream();

  print_termination_stats_hdr(st);

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

    const ParScanThreadState & pss = thread_state(i);

    const double elapsed_ms = pss.elapsed_time() * 1000.0;

    const double s_roots_ms = pss.strong_roots_time() * 1000.0;

    const double term_ms = pss.term_time() * 1000.0;

    st->print_cr("%3d %9.2f %9.2f %6.2f %9.2f %6.2f " SIZE_FORMAT_W(8),

                 i, elapsed_ms, s_roots_ms, s_roots_ms * 100 / elapsed_ms,

                 term_ms, term_ms * 100 / elapsed_ms, pss.term_attempts());

  }

}

// Print stats related to work queue activity.

void ParScanThreadStateSet::print_taskqueue_stats_hdr(outputStream* const st) {

  st->print_raw_cr("GC Task Stats");

  st->print_raw("thr "); TaskQueueStats::print_header(1, st); st->cr();

  st->print_raw("--- "); TaskQueueStats::print_header(2, st); st->cr();

}

void ParScanThreadStateSet::print_taskqueue_stats() {

  if (!log_develop_is_enabled(Trace, gc, task, stats)) {

    return;

  }

  Log(gc, task, stats) log;

  ResourceMark rm;

  outputStream* st = log.trace_stream();

  print_taskqueue_stats_hdr(st);

  TaskQueueStats totals;

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

    const ParScanThreadState & pss = thread_state(i);

    const TaskQueueStats & stats = pss.taskqueue_stats();

    st->print("%3d ", i); stats.print(st); st->cr();

    totals += stats;

    if (pss.overflow_refills() > 0) {

      st->print_cr("    " SIZE_FORMAT_W(10) " overflow refills    "

                   SIZE_FORMAT_W(10) " overflow objects",

                   pss.overflow_refills(), pss.overflow_refill_objs());

    }

  }

  st->print("tot "); totals.print(st); st->cr();

  DEBUG_ONLY(totals.verify());

}

#endif // TASKQUEUE_STATS

void ParScanThreadStateSet::flush() {

  // Work in this loop should be kept as lightweight as

  // possible since this might otherwise become a bottleneck

  // to scaling. Should we add heavy-weight work into this

  // loop, consider parallelizing the loop into the worker threads.

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

    ParScanThreadState& par_scan_state = thread_state(i);

    // Flush stats related to To-space PLAB activity and

    // retire the last buffer.

    par_scan_state.to_space_alloc_buffer()->flush_and_retire_stats(_young_gen.plab_stats());

    // Every thread has its own age table.  We need to merge

    // them all into one.

    AgeTable *local_table = par_scan_state.age_table();

    _young_gen.age_table()->merge(local_table);

    // Inform old gen that we're done.

    _old_gen.par_promote_alloc_done(i);

  }

  if (UseConcMarkSweepGC) {

    // We need to call this even when ResizeOldPLAB is disabled

    // so as to avoid breaking some asserts. While we may be able

    // to avoid this by reorganizing the code a bit, I am loathe

    // to do that unless we find cases where ergo leads to bad

    // performance.

    CompactibleFreeListSpaceLAB::compute_desired_plab_size();

  }

}

ParScanClosure::ParScanClosure(ParNewGeneration* g,

                               ParScanThreadState* par_scan_state) :

  OopsInKlassOrGenClosure(g), _par_scan_state(par_scan_state), _g(g) {