/*

 * 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/javaClasses.inline.hpp"

#include "classfile/systemDictionary.hpp"

#include "gc/shared/collectedHeap.hpp"

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

#include "gc/shared/gcTimer.hpp"

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

#include "gc/shared/referencePolicy.hpp"

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

#include "gc/shared/referenceProcessorPhaseTimes.hpp"

#include "logging/log.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/resourceArea.hpp"

#include "oops/access.inline.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/java.hpp"

ReferencePolicy* ReferenceProcessor::_always_clear_soft_ref_policy = NULL;

ReferencePolicy* ReferenceProcessor::_default_soft_ref_policy      = NULL;

jlong            ReferenceProcessor::_soft_ref_timestamp_clock = 0;

void referenceProcessor_init() {

  ReferenceProcessor::init_statics();

}

void ReferenceProcessor::init_statics() {

  // We need a monotonically non-decreasing time in ms but

  // os::javaTimeMillis() does not guarantee monotonicity.

  jlong now = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;

  // Initialize the soft ref timestamp clock.

  _soft_ref_timestamp_clock = now;

  // Also update the soft ref clock in j.l.r.SoftReference

  java_lang_ref_SoftReference::set_clock(_soft_ref_timestamp_clock);

  _always_clear_soft_ref_policy = new AlwaysClearPolicy();

  if (is_server_compilation_mode_vm()) {

    _default_soft_ref_policy = new LRUMaxHeapPolicy();

  } else {

    _default_soft_ref_policy = new LRUCurrentHeapPolicy();

  }

  if (_always_clear_soft_ref_policy == NULL || _default_soft_ref_policy == NULL) {

    vm_exit_during_initialization("Could not allocate reference policy object");

  }

  guarantee(RefDiscoveryPolicy == ReferenceBasedDiscovery ||

            RefDiscoveryPolicy == ReferentBasedDiscovery,

            "Unrecognized RefDiscoveryPolicy");

}

void ReferenceProcessor::enable_discovery(bool check_no_refs) {

#ifdef ASSERT

  // Verify that we're not currently discovering refs

  assert(!_discovering_refs, "nested call?");

  if (check_no_refs) {

    // Verify that the discovered lists are empty

    verify_no_references_recorded();

  }

#endif // ASSERT

  // Someone could have modified the value of the static

  // field in the j.l.r.SoftReference class that holds the

  // soft reference timestamp clock using reflection or

  // Unsafe between GCs. Unconditionally update the static

  // field in ReferenceProcessor here so that we use the new

  // value during reference discovery.

  _soft_ref_timestamp_clock = java_lang_ref_SoftReference::clock();

  _discovering_refs = true;

}

ReferenceProcessor::ReferenceProcessor(BoolObjectClosure* is_subject_to_discovery,

                                       bool      mt_processing,

                                       uint      mt_processing_degree,

                                       bool      mt_discovery,

                                       uint      mt_discovery_degree,

                                       bool      atomic_discovery,

                                       BoolObjectClosure* is_alive_non_header,

                                       bool      adjust_no_of_processing_threads)  :

  _is_subject_to_discovery(is_subject_to_discovery),

  _discovering_refs(false),

  _enqueuing_is_done(false),

  _processing_is_mt(mt_processing),

  _next_id(0),

  _adjust_no_of_processing_threads(adjust_no_of_processing_threads),

  _is_alive_non_header(is_alive_non_header)

{

  assert(is_subject_to_discovery != NULL, "must be set");

  _discovery_is_atomic = atomic_discovery;

  _discovery_is_mt     = mt_discovery;

  _num_queues          = MAX2(1U, mt_processing_degree);

  _max_num_queues      = MAX2(_num_queues, mt_discovery_degree);

  _discovered_refs     = NEW_C_HEAP_ARRAY(DiscoveredList,

            _max_num_queues * number_of_subclasses_of_ref(), mtGC);

  if (_discovered_refs == NULL) {

    vm_exit_during_initialization("Could not allocated RefProc Array");

  }

  _discoveredSoftRefs    = &_discovered_refs[0];

  _discoveredWeakRefs    = &_discoveredSoftRefs[_max_num_queues];

  _discoveredFinalRefs   = &_discoveredWeakRefs[_max_num_queues];

  _discoveredPhantomRefs = &_discoveredFinalRefs[_max_num_queues];

  // Initialize all entries to NULL

  for (uint i = 0; i < _max_num_queues * number_of_subclasses_of_ref(); i++) {

    _discovered_refs[i].clear();

  }

  setup_policy(false /* default soft ref policy */);

}

#ifndef PRODUCT

void ReferenceProcessor::verify_no_references_recorded() {

  guarantee(!_discovering_refs, "Discovering refs?");

  for (uint i = 0; i < _max_num_queues * number_of_subclasses_of_ref(); i++) {

    guarantee(_discovered_refs[i].is_empty(),

              "Found non-empty discovered list at %u", i);

  }

}

#endif

void ReferenceProcessor::weak_oops_do(OopClosure* f) {

  for (uint i = 0; i < _max_num_queues * number_of_subclasses_of_ref(); i++) {

    if (UseCompressedOops) {

      f->do_oop((narrowOop*)_discovered_refs[i].adr_head());

    } else {

      f->do_oop((oop*)_discovered_refs[i].adr_head());

    }

  }

}

void ReferenceProcessor::update_soft_ref_master_clock() {

  // Update (advance) the soft ref master clock field. This must be done

  // after processing the soft ref list.

  // We need a monotonically non-decreasing time in ms but

  // os::javaTimeMillis() does not guarantee monotonicity.

  jlong now = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;

  jlong soft_ref_clock = java_lang_ref_SoftReference::clock();

  assert(soft_ref_clock == _soft_ref_timestamp_clock, "soft ref clocks out of sync");

  NOT_PRODUCT(

  if (now < _soft_ref_timestamp_clock) {

    log_warning(gc)("time warp: " JLONG_FORMAT " to " JLONG_FORMAT,

                    _soft_ref_timestamp_clock, now);

  }

  )

  // The values of now and _soft_ref_timestamp_clock are set using

  // javaTimeNanos(), which is guaranteed to be monotonically

  // non-decreasing provided the underlying platform provides such

  // a time source (and it is bug free).

  // In product mode, however, protect ourselves from non-monotonicity.

  if (now > _soft_ref_timestamp_clock) {

    _soft_ref_timestamp_clock = now;

    java_lang_ref_SoftReference::set_clock(now);

  }

  // Else leave clock stalled at its old value until time progresses

  // past clock value.

}

size_t ReferenceProcessor::total_count(DiscoveredList lists[]) const {

  size_t total = 0;

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

    total += lists[i].length();

  }

  return total;

}

#ifdef ASSERT

void ReferenceProcessor::verify_total_count_zero(DiscoveredList lists[], const char* type) {

  size_t count = total_count(lists);

  assert(count == 0, "%ss must be empty but has " SIZE_FORMAT " elements", type, count);

}

#endif

ReferenceProcessorStats ReferenceProcessor::process_discovered_references(

  BoolObjectClosure*            is_alive,

  OopClosure*                   keep_alive,

  VoidClosure*                  complete_gc,

  AbstractRefProcTaskExecutor*  task_executor,

  ReferenceProcessorPhaseTimes* phase_times) {

  double start_time = os::elapsedTime();

  assert(!enqueuing_is_done(), "If here enqueuing should not be complete");

  // Stop treating discovered references specially.

  disable_discovery();

  // If discovery was concurrent, someone could have modified

  // the value of the static field in the j.l.r.SoftReference

  // class that holds the soft reference timestamp clock using

  // reflection or Unsafe between when discovery was enabled and

  // now. Unconditionally update the static field in ReferenceProcessor

  // here so that we use the new value during processing of the

  // discovered soft refs.

  _soft_ref_timestamp_clock = java_lang_ref_SoftReference::clock();

  ReferenceProcessorStats stats(total_count(_discoveredSoftRefs),

                                total_count(_discoveredWeakRefs),

                                total_count(_discoveredFinalRefs),

                                total_count(_discoveredPhantomRefs));

  {

    RefProcTotalPhaseTimesTracker tt(RefPhase1, phase_times, this);

    process_soft_ref_reconsider(is_alive, keep_alive, complete_gc,

                                task_executor, phase_times);

  }

  update_soft_ref_master_clock();

  {

    RefProcTotalPhaseTimesTracker tt(RefPhase2, phase_times, this);

    process_soft_weak_final_refs(is_alive, keep_alive, complete_gc, task_executor, phase_times);

  }

  {

    RefProcTotalPhaseTimesTracker tt(RefPhase3, phase_times, this);

    process_final_keep_alive(keep_alive, complete_gc, task_executor, phase_times);

  }

  {

    RefProcTotalPhaseTimesTracker tt(RefPhase4, phase_times, this);

    process_phantom_refs(is_alive, keep_alive, complete_gc, task_executor, phase_times);

  }

  if (task_executor != NULL) {

    // Record the work done by the parallel workers.

    task_executor->set_single_threaded_mode();

  }

  phase_times->set_total_time_ms((os::elapsedTime() - start_time) * 1000);

  return stats;

}

void DiscoveredListIterator::load_ptrs(DEBUG_ONLY(bool allow_null_referent)) {

  _current_discovered_addr = java_lang_ref_Reference::discovered_addr_raw(_current_discovered);

  oop discovered = java_lang_ref_Reference::discovered(_current_discovered);

  assert(_current_discovered_addr && oopDesc::is_oop_or_null(discovered),

         "Expected an oop or NULL for discovered field at " PTR_FORMAT, p2i(discovered));

  _next_discovered = discovered;

  _referent_addr = java_lang_ref_Reference::referent_addr_raw(_current_discovered);

  _referent = java_lang_ref_Reference::referent(_current_discovered);

  assert(Universe::heap()->is_in_reserved_or_null(_referent),

         "Wrong oop found in java.lang.Reference object");

  assert(allow_null_referent ?

             oopDesc::is_oop_or_null(_referent)

           : oopDesc::is_oop(_referent),

         "Expected an oop%s for referent field at " PTR_FORMAT,

         (allow_null_referent ? " or NULL" : ""),

         p2i(_referent));

}

void DiscoveredListIterator::remove() {

  assert(oopDesc::is_oop(_current_discovered), "Dropping a bad reference");

  RawAccess<>::oop_store(_current_discovered_addr, oop(NULL));

  // First _prev_next ref actually points into DiscoveredList (gross).

  oop new_next;

  if (oopDesc::equals_raw(_next_discovered, _current_discovered)) {

    // At the end of the list, we should make _prev point to itself.

    // If _ref is the first ref, then _prev_next will be in the DiscoveredList,

    // and _prev will be NULL.

    new_next = _prev_discovered;

  } else {

    new_next = _next_discovered;

  }

  // Remove Reference object from discovered list. Note that G1 does not need a

  // pre-barrier here because we know the Reference has already been found/marked,

  // that's how it ended up in the discovered list in the first place.

  RawAccess<>::oop_store(_prev_discovered_addr, new_next);

  _removed++;

  _refs_list.dec_length(1);

}

void DiscoveredListIterator::clear_referent() {

  RawAccess<>::oop_store(_referent_addr, oop(NULL));

}

void DiscoveredListIterator::enqueue() {

  HeapAccess<AS_NO_KEEPALIVE>::oop_store_at(_current_discovered,

                                            java_lang_ref_Reference::discovered_offset,

                                            _next_discovered);

}

void DiscoveredListIterator::complete_enqueue() {

  if (_prev_discovered != NULL) {

    // This is the last object.

    // Swap refs_list into pending list and set obj's

    // discovered to what we read from the pending list.

    oop old = Universe::swap_reference_pending_list(_refs_list.head());

    HeapAccess<AS_NO_KEEPALIVE>::oop_store_at(_prev_discovered, java_lang_ref_Reference::discovered_offset, old);

  }

}

inline void log_dropped_ref(const DiscoveredListIterator& iter, const char* reason) {

  if (log_develop_is_enabled(Trace, gc, ref)) {

    ResourceMark rm;

    log_develop_trace(gc, ref)("Dropping %s reference " PTR_FORMAT ": %s",

                               reason, p2i(iter.obj()),

                               iter.obj()->klass()->internal_name());

  }

}

inline void log_enqueued_ref(const DiscoveredListIterator& iter, const char* reason) {

  if (log_develop_is_enabled(Trace, gc, ref)) {

    ResourceMark rm;

    log_develop_trace(gc, ref)("Enqueue %s reference (" INTPTR_FORMAT ": %s)",

                               reason, p2i(iter.obj()), iter.obj()->klass()->internal_name());

  }

  assert(oopDesc::is_oop(iter.obj(), UseConcMarkSweepGC), "Adding a bad reference");

}

size_t ReferenceProcessor::process_soft_ref_reconsider_work(DiscoveredList&    refs_list,

                                                            ReferencePolicy*   policy,

                                                            BoolObjectClosure* is_alive,

                                                            OopClosure*        keep_alive,

                                                            VoidClosure*       complete_gc) {

  assert(policy != NULL, "Must have a non-NULL policy");

  DiscoveredListIterator iter(refs_list, keep_alive, is_alive);

  // Decide which softly reachable refs should be kept alive.

  while (iter.has_next()) {

    iter.load_ptrs(DEBUG_ONLY(!discovery_is_atomic() /* allow_null_referent */));

    bool referent_is_dead = (iter.referent() != NULL) && !iter.is_referent_alive();

    if (referent_is_dead &&

        !policy->should_clear_reference(iter.obj(), _soft_ref_timestamp_clock)) {

      log_dropped_ref(iter, "by policy");

      // Remove Reference object from list

      iter.remove();

      // keep the referent around

      iter.make_referent_alive();

      iter.move_to_next();

    } else {

      iter.next();

    }

  }

  // Close the reachable set

  complete_gc->do_void();

  log_develop_trace(gc, ref)(" Dropped " SIZE_FORMAT " dead Refs out of " SIZE_FORMAT " discovered Refs by policy, from list " INTPTR_FORMAT,

                             iter.removed(), iter.processed(), p2i(&refs_list));

  return iter.removed();

}

size_t ReferenceProcessor::process_soft_weak_final_refs_work(DiscoveredList&    refs_list,

                                                             BoolObjectClosure* is_alive,

                                                             OopClosure*        keep_alive,

                                                             bool               do_enqueue_and_clear) {

  DiscoveredListIterator iter(refs_list, keep_alive, is_alive);

  while (iter.has_next()) {

    iter.load_ptrs(DEBUG_ONLY(!discovery_is_atomic() /* allow_null_referent */));

    if (iter.referent() == NULL) {

      // Reference has been cleared since discovery; only possible if

      // discovery is not atomic (checked by load_ptrs).  Remove

      // reference from list.

      log_dropped_ref(iter, "cleared");

      iter.remove();

      iter.move_to_next();

    } else if (iter.is_referent_alive()) {

      // The referent is reachable after all.

      // Remove reference from list.

      log_dropped_ref(iter, "reachable");

      iter.remove();

      // Update the referent pointer as necessary.  Note that this

      // should not entail any recursive marking because the

      // referent must already have been traversed.

      iter.make_referent_alive();

      iter.move_to_next();

    } else {

      if (do_enqueue_and_clear) {

        iter.clear_referent();

        iter.enqueue();

        log_enqueued_ref(iter, "cleared");

      }

      // Keep in discovered list

      iter.next();

    }

  }

  if (do_enqueue_and_clear) {

    iter.complete_enqueue();

    refs_list.clear();

  }

  log_develop_trace(gc, ref)(" Dropped " SIZE_FORMAT " active Refs out of " SIZE_FORMAT

                             " Refs in discovered list " INTPTR_FORMAT,

                             iter.removed(), iter.processed(), p2i(&refs_list));

  return iter.removed();

}

size_t ReferenceProcessor::process_final_keep_alive_work(DiscoveredList& refs_list,

                                                         OopClosure*     keep_alive,

                                                         VoidClosure*    complete_gc) {

  DiscoveredListIterator iter(refs_list, keep_alive, NULL);

  while (iter.has_next()) {

    iter.load_ptrs(DEBUG_ONLY(false /* allow_null_referent */));

    // keep the referent and followers around

    iter.make_referent_alive();

    // Self-loop next, to mark the FinalReference not active.

    assert(java_lang_ref_Reference::next(iter.obj()) == NULL, "enqueued FinalReference");

    java_lang_ref_Reference::set_next_raw(iter.obj(), iter.obj());

    iter.enqueue();

    log_enqueued_ref(iter, "Final");

    iter.next();

  }

  iter.complete_enqueue();

  // Close the reachable set

  complete_gc->do_void();

  refs_list.clear();

  assert(iter.removed() == 0, "This phase does not remove anything.");

  return iter.removed();

}

size_t ReferenceProcessor::process_phantom_refs_work(DiscoveredList&    refs_list,

                                          BoolObjectClosure* is_alive,

                                          OopClosure*        keep_alive,

                                          VoidClosure*       complete_gc) {

  DiscoveredListIterator iter(refs_list, keep_alive, is_alive);

  while (iter.has_next()) {

    iter.load_ptrs(DEBUG_ONLY(!discovery_is_atomic() /* allow_null_referent */));

    oop const referent = iter.referent();

    if (referent == NULL || iter.is_referent_alive()) {

      iter.make_referent_alive();

      iter.remove();

      iter.move_to_next();

    } else {

      iter.clear_referent();

      iter.enqueue();

      log_enqueued_ref(iter, "cleared Phantom");

      iter.next();

    }

  }

  iter.complete_enqueue();

  // Close the reachable set; needed for collectors which keep_alive_closure do

  // not immediately complete their work.

  complete_gc->do_void();

  refs_list.clear();

  return iter.removed();

}

void

ReferenceProcessor::clear_discovered_references(DiscoveredList& refs_list) {

  oop obj = NULL;

  oop next = refs_list.head();

  while (!oopDesc::equals_raw(next, obj)) {

    obj = next;

    next = java_lang_ref_Reference::discovered(obj);

    java_lang_ref_Reference::set_discovered_raw(obj, NULL);

  }

  refs_list.clear();

}

void ReferenceProcessor::abandon_partial_discovery() {

  // loop over the lists

  for (uint i = 0; i < _max_num_queues * number_of_subclasses_of_ref(); i++) {

    if ((i % _max_num_queues) == 0) {

      log_develop_trace(gc, ref)("Abandoning %s discovered list", list_name(i));

    }

    clear_discovered_references(_discovered_refs[i]);