/*

 * 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 "logging/log.hpp"

#include "memory/allocation.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(MemRegion span,

                                       bool      mt_processing,

                                       uint      mt_processing_degree,

                                       bool      mt_discovery,

                                       uint      mt_discovery_degree,

                                       bool      atomic_discovery,

                                       BoolObjectClosure* is_alive_non_header)  :

  _discovering_refs(false),

  _enqueuing_is_done(false),

  _is_alive_non_header(is_alive_non_header),

  _processing_is_mt(mt_processing),

  _next_id(0)

{

  _span = span;

  _discovery_is_atomic = atomic_discovery;

  _discovery_is_mt     = mt_discovery;

  _num_q               = MAX2(1U, mt_processing_degree);

  _max_num_q           = MAX2(_num_q, mt_discovery_degree);

  _discovered_refs     = NEW_C_HEAP_ARRAY(DiscoveredList,

            _max_num_q * 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_q];

  _discoveredFinalRefs   = &_discoveredWeakRefs[_max_num_q];

  _discoveredPhantomRefs = &_discoveredFinalRefs[_max_num_q];

  // Initialize all entries to NULL

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

    _discovered_refs[i].set_head(NULL);

    _discovered_refs[i].set_length(0);

  }

  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_q * 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_q * 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_q; ++i) {

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

  }

  return total;

}

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

  // Soft references

  {

    RefProcPhaseTimesTracker tt(REF_SOFT, phase_times, this);

    process_discovered_reflist(_discoveredSoftRefs, _current_soft_ref_policy, true,

                               is_alive, keep_alive, complete_gc, task_executor, phase_times);

  }

  update_soft_ref_master_clock();

  // Weak references

  {

    RefProcPhaseTimesTracker tt(REF_WEAK, phase_times, this);

    process_discovered_reflist(_discoveredWeakRefs, NULL, true,

                               is_alive, keep_alive, complete_gc, task_executor, phase_times);

  }

  // Final references

  {

    RefProcPhaseTimesTracker tt(REF_FINAL, phase_times, this);

    process_discovered_reflist(_discoveredFinalRefs, NULL, false,

                               is_alive, keep_alive, complete_gc, task_executor, phase_times);

  }

  // Phantom references

  {

    RefProcPhaseTimesTracker tt(REF_PHANTOM, phase_times, this);

    process_discovered_reflist(_discoveredPhantomRefs, NULL, true,

                               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 ReferenceProcessor::enqueue_discovered_references(AbstractRefProcTaskExecutor*  task_executor,

                                                       ReferenceProcessorPhaseTimes* phase_times) {

  // Enqueue references that are not made active again, and

  // clear the decks for the next collection (cycle).

  enqueue_discovered_reflists(task_executor, phase_times);

  // Stop treating discovered references specially.

  disable_discovery();

}

void ReferenceProcessor::enqueue_discovered_reflist(DiscoveredList& refs_list) {

  // Given a list of refs linked through the "discovered" field

  // (java.lang.ref.Reference.discovered), self-loop their "next" field

  // thus distinguishing them from active References, then

  // prepend them to the pending list.

  //

  // The Java threads will see the Reference objects linked together through

  // the discovered field. Instead of trying to do the write barrier updates

  // in all places in the reference processor where we manipulate the discovered

  // field we make sure to do the barrier here where we anyway iterate through

  // all linked Reference objects. Note that it is important to not dirty any

  // cards during reference processing since this will cause card table

  // verification to fail for G1.

  log_develop_trace(gc, ref)("ReferenceProcessor::enqueue_discovered_reflist list " INTPTR_FORMAT, p2i(&refs_list));

  oop obj = NULL;

  oop next_d = refs_list.head();

  // Walk down the list, self-looping the next field

  // so that the References are not considered active.

  while (obj != next_d) {

    obj = next_d;

    assert(obj->is_instance(), "should be an instance object");

    assert(InstanceKlass::cast(obj->klass())->is_reference_instance_klass(), "should be reference object");

    next_d = java_lang_ref_Reference::discovered(obj);

    log_develop_trace(gc, ref)("        obj " INTPTR_FORMAT "/next_d " INTPTR_FORMAT, p2i(obj), p2i(next_d));

    assert(java_lang_ref_Reference::next(obj) == NULL,

           "Reference not active; should not be discovered");

    // Self-loop next, so as to make Ref not active.

    java_lang_ref_Reference::set_next_raw(obj, obj);

    if (next_d != obj) {

      HeapAccess<AS_NO_KEEPALIVE>::oop_store_at(obj, java_lang_ref_Reference::discovered_offset, next_d);

    } else {

      // 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(obj, java_lang_ref_Reference::discovered_offset, old);

    }

  }

}

// Parallel enqueue task

class RefProcEnqueueTask: public AbstractRefProcTaskExecutor::EnqueueTask {

public:

  RefProcEnqueueTask(ReferenceProcessor&           ref_processor,

                     DiscoveredList                discovered_refs[],

                     int                           n_queues,

                     ReferenceProcessorPhaseTimes* phase_times)

    : EnqueueTask(ref_processor, discovered_refs, n_queues, phase_times)

  { }

  virtual void work(unsigned int work_id) {

    RefProcWorkerTimeTracker tt(ReferenceProcessorPhaseTimes::RefEnqueue, _phase_times, work_id);

    assert(work_id < (unsigned int)_ref_processor.max_num_q(), "Index out-of-bounds");

    // Simplest first cut: static partitioning.

    int index = work_id;

    // The increment on "index" must correspond to the maximum number of queues

    // (n_queues) with which that ReferenceProcessor was created.  That

    // is because of the "clever" way the discovered references lists were

    // allocated and are indexed into.

    assert(_n_queues == (int) _ref_processor.max_num_q(), "Different number not expected");

    for (int j = 0;

         j < ReferenceProcessor::number_of_subclasses_of_ref();

         j++, index += _n_queues) {

      _ref_processor.enqueue_discovered_reflist(_refs_lists[index]);

      _refs_lists[index].set_head(NULL);

      _refs_lists[index].set_length(0);

    }

  }

};

// Enqueue references that are not made active again

void ReferenceProcessor::enqueue_discovered_reflists(AbstractRefProcTaskExecutor*  task_executor,

                                                     ReferenceProcessorPhaseTimes* phase_times) {

  ReferenceProcessorStats stats(total_count(_discoveredSoftRefs),

                                total_count(_discoveredWeakRefs),

                                total_count(_discoveredFinalRefs),

                                total_count(_discoveredPhantomRefs));

  RefProcEnqueueTimeTracker tt(phase_times, stats);

  if (_processing_is_mt && task_executor != NULL) {

    // Parallel code

    RefProcEnqueueTask tsk(*this, _discovered_refs, _max_num_q, phase_times);

    task_executor->execute(tsk);

  } else {

    // Serial code: call the parent class's implementation

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

      enqueue_discovered_reflist(_discovered_refs[i]);

      _discovered_refs[i].set_head(NULL);

      _discovered_refs[i].set_length(0);

    }

  }

}

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

  _discovered_addr = java_lang_ref_Reference::discovered_addr_raw(_ref);

  oop discovered = java_lang_ref_Reference::discovered(_ref);

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

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

  _next = discovered;

  _referent_addr = java_lang_ref_Reference::referent_addr_raw(_ref);

  _referent = java_lang_ref_Reference::referent(_ref);

  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(_ref), "Dropping a bad reference");

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

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

  oop new_next;

  if (_next == _ref) {

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

  } else {

    new_next = _next;

  }

  // 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_next, new_next);

  NOT_PRODUCT(_removed++);

  _refs_list.dec_length(1);

}

void DiscoveredListIterator::clear_referent() {

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

}

// NOTE: process_phase*() are largely similar, and at a high level

// merely iterate over the extant list applying a predicate to

// each of its elements and possibly removing that element from the

// list and applying some further closures to that element.

// We should consider the possibility of replacing these

// process_phase*() methods by abstracting them into

// a single general iterator invocation that receives appropriate

// closures that accomplish this work.

// (SoftReferences only) Traverse the list and remove any SoftReferences whose

// referents are not alive, but that should be kept alive for policy reasons.

// Keep alive the transitive closure of all such referents.

void

ReferenceProcessor::process_phase1(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_develop_trace(gc, ref)("Dropping reference (" INTPTR_FORMAT ": %s"  ") by policy",

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

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

}

// Traverse the list and remove any Refs that are not active, or

// whose referents are either alive or NULL.

void

ReferenceProcessor::pp2_work(DiscoveredList&    refs_list,

                             BoolObjectClosure* is_alive,

                             OopClosure*        keep_alive) {

  assert(discovery_is_atomic(), "Error");

  DiscoveredListIterator iter(refs_list, keep_alive, is_alive);

  while (iter.has_next()) {

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

    DEBUG_ONLY(oop next = java_lang_ref_Reference::next(iter.obj());)

    assert(next == NULL, "Should not discover inactive Reference");

    if (iter.is_referent_alive()) {

      log_develop_trace(gc, ref)("Dropping strongly reachable reference (" INTPTR_FORMAT ": %s)",

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

      // The referent is reachable after all.

      // Remove Reference object from list.

      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 {

      iter.next();

    }

  }

  NOT_PRODUCT(

    if (iter.processed() > 0) {

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

    }

  )

}

void

ReferenceProcessor::pp2_work_concurrent_discovery(DiscoveredList&    refs_list,

                                                  BoolObjectClosure* is_alive,

                                                  OopClosure*        keep_alive,

                                                  VoidClosure*       complete_gc) {

  assert(!discovery_is_atomic(), "Error");

  DiscoveredListIterator iter(refs_list, keep_alive, is_alive);