/*

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

#include "classfile/systemDictionary.hpp"

#include "gc_implementation/shared/gcTimer.hpp"

#include "gc_implementation/shared/gcTraceTime.hpp"

#include "gc_interface/collectedHeap.hpp"

#include "gc_interface/collectedHeap.inline.hpp"

#include "memory/referencePolicy.hpp"

#include "memory/referenceProcessor.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/java.hpp"

#include "runtime/jniHandles.hpp"

ReferencePolicy* ReferenceProcessor::_always_clear_soft_ref_policy = NULL;

ReferencePolicy* ReferenceProcessor::_default_soft_ref_policy      = NULL;

bool             ReferenceProcessor::_pending_list_uses_discovered_field = false;

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

  _default_soft_ref_policy      = new COMPILER2_PRESENT(LRUMaxHeapPolicy())

                                      NOT_COMPILER2(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");

  _pending_list_uses_discovered_field = JDK_Version::current().pending_list_uses_discovered_field();

}

void ReferenceProcessor::enable_discovery(bool verify_disabled, bool check_no_refs) {

#ifdef ASSERT

  // Verify that we're not currently discovering refs

  assert(!verify_disabled || !_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,

                                       bool      discovered_list_needs_post_barrier)  :

  _discovering_refs(false),

  _enqueuing_is_done(false),

  _is_alive_non_header(is_alive_non_header),

  _discovered_list_needs_post_barrier(discovered_list_needs_post_barrier),

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

  }

}

#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) {

    warning("time warp: "INT64_FORMAT" to "INT64_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[]) {

  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,

  GCTimer*                     gc_timer) {

  NOT_PRODUCT(verify_ok_to_handle_reflists());

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

  bool trace_time = PrintGCDetails && PrintReferenceGC;

  // Soft references

  size_t soft_count = 0;

  {

    GCTraceTime tt("SoftReference", trace_time, false, gc_timer);

    soft_count =

      process_discovered_reflist(_discoveredSoftRefs, _current_soft_ref_policy, true,

                                 is_alive, keep_alive, complete_gc, task_executor);

  }

  update_soft_ref_master_clock();

  // Weak references

  size_t weak_count = 0;

  {

    GCTraceTime tt("WeakReference", trace_time, false, gc_timer);

    weak_count =

      process_discovered_reflist(_discoveredWeakRefs, NULL, true,

                                 is_alive, keep_alive, complete_gc, task_executor);

  }

  // Final references

  size_t final_count = 0;

  {

    GCTraceTime tt("FinalReference", trace_time, false, gc_timer);

    final_count =

      process_discovered_reflist(_discoveredFinalRefs, NULL, false,

                                 is_alive, keep_alive, complete_gc, task_executor);

  }

  // Phantom references

  size_t phantom_count = 0;

  {

    GCTraceTime tt("PhantomReference", trace_time, false, gc_timer);

    phantom_count =

      process_discovered_reflist(_discoveredPhantomRefs, NULL, false,

                                 is_alive, keep_alive, complete_gc, task_executor);

  }

  // Weak global JNI references. It would make more sense (semantically) to

  // traverse these simultaneously with the regular weak references above, but

  // that is not how the JDK1.2 specification is. See #4126360. Native code can

  // thus use JNI weak references to circumvent the phantom references and

  // resurrect a "post-mortem" object.

  {

    GCTraceTime tt("JNI Weak Reference", trace_time, false, gc_timer);

    if (task_executor != NULL) {

      task_executor->set_single_threaded_mode();

    }

    process_phaseJNI(is_alive, keep_alive, complete_gc);

  }

  return ReferenceProcessorStats(soft_count, weak_count, final_count, phantom_count);

}

#ifndef PRODUCT

// Calculate the number of jni handles.

uint ReferenceProcessor::count_jni_refs() {

  class AlwaysAliveClosure: public BoolObjectClosure {

  public:

    virtual bool do_object_b(oop obj) { return true; }

  };

  class CountHandleClosure: public OopClosure {

  private:

    int _count;

  public:

    CountHandleClosure(): _count(0) {}

    void do_oop(oop* unused)       { _count++; }

    void do_oop(narrowOop* unused) { ShouldNotReachHere(); }

    int count() { return _count; }

  };

  CountHandleClosure global_handle_count;

  AlwaysAliveClosure always_alive;

  JNIHandles::weak_oops_do(&always_alive, &global_handle_count);

  return global_handle_count.count();

}

#endif

void ReferenceProcessor::process_phaseJNI(BoolObjectClosure* is_alive,

                                          OopClosure*        keep_alive,

                                          VoidClosure*       complete_gc) {

#ifndef PRODUCT

  if (PrintGCDetails && PrintReferenceGC) {

    unsigned int count = count_jni_refs();

    gclog_or_tty->print(", %u refs", count);

  }

#endif

  JNIHandles::weak_oops_do(is_alive, keep_alive);

  complete_gc->do_void();

}

template <class T>

bool enqueue_discovered_ref_helper(ReferenceProcessor* ref,

                                   AbstractRefProcTaskExecutor* task_executor) {

  // Remember old value of pending references list

  T* pending_list_addr = (T*)java_lang_ref_Reference::pending_list_addr();

  T old_pending_list_value = *pending_list_addr;

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

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

  ref->enqueue_discovered_reflists((HeapWord*)pending_list_addr, task_executor);

  // Do the post-barrier on pending_list_addr missed in

  // enqueue_discovered_reflist.

  oopDesc::bs()->write_ref_field(pending_list_addr, oopDesc::load_decode_heap_oop(pending_list_addr));

  // Stop treating discovered references specially.

  ref->disable_discovery();

  // Return true if new pending references were added

  return old_pending_list_value != *pending_list_addr;

}

bool ReferenceProcessor::enqueue_discovered_references(AbstractRefProcTaskExecutor* task_executor) {

  NOT_PRODUCT(verify_ok_to_handle_reflists());

  if (UseCompressedOops) {

    return enqueue_discovered_ref_helper<narrowOop>(this, task_executor);

  } else {

    return enqueue_discovered_ref_helper<oop>(this, task_executor);

  }

}

void ReferenceProcessor::enqueue_discovered_reflist(DiscoveredList& refs_list,

                                                    HeapWord* pending_list_addr) {

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

  // BKWRD COMPATIBILITY NOTE: For older JDKs (prior to the fix for 4956777),

  // the "next" field is used to chain the pending list, not the discovered

  // field.

  if (TraceReferenceGC && PrintGCDetails) {

    gclog_or_tty->print_cr("ReferenceProcessor::enqueue_discovered_reflist list "

                           INTPTR_FORMAT, (address)refs_list.head());

  }

  oop obj = NULL;

  oop next_d = refs_list.head();

  if (pending_list_uses_discovered_field()) { // New behavior

    // 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_instanceRef(), "should be reference object");

      next_d = java_lang_ref_Reference::discovered(obj);

      if (TraceReferenceGC && PrintGCDetails) {

        gclog_or_tty->print_cr("        obj " INTPTR_FORMAT "/next_d " INTPTR_FORMAT,

                               (void *)obj, (void *)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.

      // Post-barrier not needed when looping to self.

      java_lang_ref_Reference::set_next_raw(obj, obj);

      if (next_d == obj) {  // obj is last

        // Swap refs_list into pending_list_addr and

        // set obj's discovered to what we read from pending_list_addr.

        oop old = oopDesc::atomic_exchange_oop(refs_list.head(), pending_list_addr);

        // Need post-barrier on pending_list_addr above;

        // see special post-barrier code at the end of

        // enqueue_discovered_reflists() further below.

        java_lang_ref_Reference::set_discovered_raw(obj, old); // old may be NULL

        oopDesc::bs()->write_ref_field(java_lang_ref_Reference::discovered_addr(obj), old);

      }

    }

  } else { // Old behavior

    // Walk down the list, copying the discovered field into

    // the next field and clearing the discovered field.

    while (obj != next_d) {

      obj = next_d;

      assert(obj->is_instanceRef(), "should be reference object");

      next_d = java_lang_ref_Reference::discovered(obj);

      if (TraceReferenceGC && PrintGCDetails) {

        gclog_or_tty->print_cr("        obj " INTPTR_FORMAT "/next_d " INTPTR_FORMAT,

                               (void *)obj, (void *)next_d);

      }

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

             "The reference should not be enqueued");

      if (next_d == obj) {  // obj is last

        // Swap refs_list into pending_list_addr and

        // set obj's next to what we read from pending_list_addr.

        oop old = oopDesc::atomic_exchange_oop(refs_list.head(), pending_list_addr);

        // Need oop_check on pending_list_addr above;

        // see special oop-check code at the end of

        // enqueue_discovered_reflists() further below.

        if (old == NULL) {

          // obj should be made to point to itself, since

          // pending list was empty.

          java_lang_ref_Reference::set_next(obj, obj);

        } else {

          java_lang_ref_Reference::set_next(obj, old);

        }

      } else {

        java_lang_ref_Reference::set_next(obj, next_d);

      }

      java_lang_ref_Reference::set_discovered(obj, (oop) NULL);

    }

  }

}

// Parallel enqueue task

class RefProcEnqueueTask: public AbstractRefProcTaskExecutor::EnqueueTask {

public:

  RefProcEnqueueTask(ReferenceProcessor& ref_processor,

                     DiscoveredList      discovered_refs[],

                     HeapWord*           pending_list_addr,

                     int                 n_queues)

    : EnqueueTask(ref_processor, discovered_refs,

                  pending_list_addr, n_queues)

  { }

  virtual void work(unsigned int 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], _pending_list_addr);

      _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(HeapWord* pending_list_addr,

  AbstractRefProcTaskExecutor* task_executor) {

  if (_processing_is_mt && task_executor != NULL) {

    // Parallel code

    RefProcEnqueueTask tsk(*this, _discovered_refs,

                           pending_list_addr, _max_num_q);

    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], pending_list_addr);

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

  oop discovered = java_lang_ref_Reference::discovered(_ref);

  assert(_discovered_addr && discovered->is_oop_or_null(),

         "discovered field is bad");

  _next = discovered;

  _referent_addr = java_lang_ref_Reference::referent_addr(_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 ?

             _referent->is_oop_or_null()

           : _referent->is_oop(),

         "bad referent");

}

void DiscoveredListIterator::remove() {

  assert(_ref->is_oop(), "Dropping a bad reference");

  oop_store_raw(_discovered_addr, 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.

  oop_store_raw(_prev_next, new_next);

  if (_discovered_list_needs_post_barrier && _prev_next != _refs_list.adr_head()) {