/*

 * 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.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)  :

  _is_subject_to_discovery(is_subject_to_discovery),

  _discovering_refs(false),

  _enqueuing_is_done(false),

  _is_alive_non_header(is_alive_non_header),

  _processing_is_mt(mt_processing),

  _next_id(0)

{

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

}

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

  NOT_PRODUCT(_removed++);

  _refs_list.dec_length(1);

}

void DiscoveredListIterator::clear_referent() {

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

}

void DiscoveredListIterator::enqueue() {

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

  java_lang_ref_Reference::set_next_raw(_current_discovered, _current_discovered);

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

  }

}

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

}

void ReferenceProcessor::process_phase2(DiscoveredList&    refs_list,

                                        BoolObjectClosure* is_alive,

                                        OopClosure*        keep_alive,

                                        VoidClosure*       complete_gc) {

  if (discovery_is_atomic()) {

    // complete_gc is ignored in this case for this phase

    pp2_work(refs_list, is_alive, keep_alive);

  } else {

    assert(complete_gc != NULL, "Error");

    pp2_work_concurrent_discovery(refs_list, is_alive,

                                  keep_alive, complete_gc);

  }

}

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

  while (iter.has_next()) {

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

    HeapWord* next_addr = java_lang_ref_Reference::next_addr_raw(iter.obj());

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

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

         next != NULL)) {

      assert(oopDesc::is_oop_or_null(next), "Expected an oop or NULL for next field at " PTR_FORMAT, p2i(next));

      // Remove Reference object from list

      iter.remove();

      // Trace the cohorts

      iter.make_referent_alive();

      if (UseCompressedOops) {

        keep_alive->do_oop((narrowOop*)next_addr);

      } else {

        keep_alive->do_oop((oop*)next_addr);

      }

      iter.move_to_next();

    } else {

      iter.next();

    }

  }

  // Now close the newly reachable set

  complete_gc->do_void();

  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::process_phase3(DiscoveredList&    refs_list,

                                        bool               clear_referent,

                                        BoolObjectClosure* is_alive,

                                        OopClosure*        keep_alive,

                                        VoidClosure*       complete_gc) {

  ResourceMark rm;

  DiscoveredListIterator iter(refs_list, keep_alive, is_alive);

  while (iter.has_next()) {

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

    if (clear_referent) {

      // NULL out referent pointer

      iter.clear_referent();

    } else {

      // keep the referent around

      iter.make_referent_alive();

    }

    iter.enqueue();

    log_develop_trace(gc, ref)("Adding %sreference (" INTPTR_FORMAT ": %s) as pending",

                               clear_referent ? "cleared " : "", p2i(iter.obj()), iter.obj()->klass()->internal_name());

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

    iter.next();

  }

  iter.complete_enqueue();

  // Close the reachable set

  complete_gc->do_void();

  // Clear the list.

  refs_list.set_head(NULL);

  refs_list.set_length(0);

}

void

ReferenceProcessor::clear_discovered_references(DiscoveredList& refs_list) {

  oop obj = NULL;

  oop next = refs_list.head();

  while (next != obj) {

    obj = next;

    next = java_lang_ref_Reference::discovered(obj);

    java_lang_ref_Reference::set_discovered_raw(obj, NULL);

  }

  refs_list.set_head(NULL);