/*

 * Copyright (c) 2001, 2011, 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_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;

oop              ReferenceProcessor::_sentinelRef = NULL;

const int        subclasses_of_ref                = REF_PHANTOM - REF_OTHER;

// List of discovered references.

class DiscoveredList {

public:

  DiscoveredList() : _len(0), _compressed_head(0), _oop_head(NULL) { }

  oop head() const     {

     return UseCompressedOops ?  oopDesc::decode_heap_oop_not_null(_compressed_head) :

                                _oop_head;

  }

  HeapWord* adr_head() {

    return UseCompressedOops ? (HeapWord*)&_compressed_head :

                               (HeapWord*)&_oop_head;

  }

  void   set_head(oop o) {

    if (UseCompressedOops) {

      // Must compress the head ptr.

      _compressed_head = oopDesc::encode_heap_oop_not_null(o);

    } else {

      _oop_head = o;

    }

  }

  bool   empty() const          { return head() == ReferenceProcessor::sentinel_ref(); }

  size_t length()               { return _len; }

  void   set_length(size_t len) { _len = len;  }

  void   inc_length(size_t inc) { _len += inc; assert(_len > 0, "Error"); }

  void   dec_length(size_t dec) { _len -= dec; }

private:

  // Set value depending on UseCompressedOops. This could be a template class

  // but then we have to fix all the instantiations and declarations that use this class.

  oop       _oop_head;

  narrowOop _compressed_head;

  size_t _len;

};

void referenceProcessor_init() {

  ReferenceProcessor::init_statics();

}

void ReferenceProcessor::init_statics() {

  assert(_sentinelRef == NULL, "should be initialized precisely once");

  EXCEPTION_MARK;

  _sentinelRef = instanceKlass::cast(

                    SystemDictionary::Reference_klass())->

                      allocate_permanent_instance(THREAD);

  // Initialize the master soft ref clock.

  java_lang_ref_SoftReference::set_clock(os::javaTimeMillis());

  if (HAS_PENDING_EXCEPTION) {

      Handle ex(THREAD, PENDING_EXCEPTION);

      vm_exit_during_initialization(ex);

  }

  assert(_sentinelRef != NULL && _sentinelRef->is_oop(),

         "Just constructed it!");

  _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,

            "Unrecongnized RefDiscoveryPolicy");

}

ReferenceProcessor::ReferenceProcessor(MemRegion span,

                                       bool      mt_processing,

                                       int       mt_processing_degree,

                                       bool      mt_discovery,

                                       int       mt_discovery_degree,

                                       bool      atomic_discovery,

                                       BoolObjectClosure* is_alive_non_header,

                                       bool      discovered_list_needs_barrier)  :

  _discovering_refs(false),

  _enqueuing_is_done(false),

  _is_alive_non_header(is_alive_non_header),

  _discovered_list_needs_barrier(discovered_list_needs_barrier),

  _bs(NULL),

  _processing_is_mt(mt_processing),

  _next_id(0)

{

  _span = span;

  _discovery_is_atomic = atomic_discovery;

  _discovery_is_mt     = mt_discovery;

  _num_q               = MAX2(1, mt_processing_degree);

  _max_num_q           = MAX2(_num_q, mt_discovery_degree);

  _discoveredSoftRefs  = NEW_C_HEAP_ARRAY(DiscoveredList, _max_num_q * subclasses_of_ref);

  if (_discoveredSoftRefs == NULL) {

    vm_exit_during_initialization("Could not allocated RefProc Array");

  }

  _discoveredWeakRefs    = &_discoveredSoftRefs[_max_num_q];

  _discoveredFinalRefs   = &_discoveredWeakRefs[_max_num_q];

  _discoveredPhantomRefs = &_discoveredFinalRefs[_max_num_q];

  assert(sentinel_ref() != NULL, "_sentinelRef is NULL");

  // Initialized all entries to _sentinelRef

  for (int i = 0; i < _max_num_q * subclasses_of_ref; i++) {

        _discoveredSoftRefs[i].set_head(sentinel_ref());

    _discoveredSoftRefs[i].set_length(0);

  }

  // If we do barreirs, cache a copy of the barrier set.

  if (discovered_list_needs_barrier) {

    _bs = Universe::heap()->barrier_set();

  }

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

}

#ifndef PRODUCT

void ReferenceProcessor::verify_no_references_recorded() {

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

  for (int i = 0; i < _max_num_q * subclasses_of_ref; i++) {

    guarantee(_discoveredSoftRefs[i].empty(),

              "Found non-empty discovered list");

  }

}

#endif

void ReferenceProcessor::weak_oops_do(OopClosure* f) {

  // Should this instead be

  // for (int i = 0; i < subclasses_of_ref; i++_ {

  //   for (int j = 0; j < _num_q; j++) {

  //     int index = i * _max_num_q + j;

  for (int i = 0; i < _max_num_q * subclasses_of_ref; i++) {

    if (UseCompressedOops) {

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

    } else {

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

    }

  }

}

void ReferenceProcessor::oops_do(OopClosure* f) {

  f->do_oop(adr_sentinel_ref());

}

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.

  jlong now = os::javaTimeMillis();

  jlong clock = java_lang_ref_SoftReference::clock();

  NOT_PRODUCT(

  if (now < clock) {

    warning("time warp: %d to %d", clock, now);

  }

  )

  // In product mode, protect ourselves from system time being adjusted

  // externally and going backward; see note in the implementation of

  // GenCollectedHeap::time_since_last_gc() for the right way to fix

  // this uniformly throughout the VM; see bug-id 4741166. XXX

  if (now > clock) {

    java_lang_ref_SoftReference::set_clock(now);

  }

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

  // past clock value.

}

void ReferenceProcessor::process_discovered_references(

  BoolObjectClosure*           is_alive,

  OopClosure*                  keep_alive,

  VoidClosure*                 complete_gc,

  AbstractRefProcTaskExecutor* task_executor) {

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

  bool trace_time = PrintGCDetails && PrintReferenceGC;

  // Soft references

  {

    TraceTime tt("SoftReference", trace_time, false, gclog_or_tty);

    process_discovered_reflist(_discoveredSoftRefs, _current_soft_ref_policy, true,

                               is_alive, keep_alive, complete_gc, task_executor);

  }

  update_soft_ref_master_clock();

  // Weak references

  {

    TraceTime tt("WeakReference", trace_time, false, gclog_or_tty);

    process_discovered_reflist(_discoveredWeakRefs, NULL, true,

                               is_alive, keep_alive, complete_gc, task_executor);

  }

  // Final references

  {

    TraceTime tt("FinalReference", trace_time, false, gclog_or_tty);

    process_discovered_reflist(_discoveredFinalRefs, NULL, false,

                               is_alive, keep_alive, complete_gc, task_executor);

  }

  // Phantom references

  {

    TraceTime tt("PhantomReference", trace_time, false, gclog_or_tty);

    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.

  {

    TraceTime tt("JNI Weak Reference", trace_time, false, gclog_or_tty);

    if (task_executor != NULL) {

      task_executor->set_single_threaded_mode();

    }

    process_phaseJNI(is_alive, keep_alive, complete_gc);

  }

}

#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; }

    virtual void do_object(oop obj) { assert(false, "Don't call"); }

  };

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

  // Finally remember to keep sentinel around

  keep_alive->do_oop(adr_sentinel_ref());

  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 oop-check on pending_list_addr missed in

  // enqueue_discovered_reflist. We should probably

  // do a raw oop_check so that future such idempotent

  // oop_stores relying on the oop-check side-effect

  // may be elided automatically and safely without

  // affecting correctness.

  oop_store(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) chain them through the

  // "next" field (java.lang.ref.Reference.next) and prepend

  // to the pending list.

  if (TraceReferenceGC && PrintGCDetails) {

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

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

  }

  oop obj = refs_list.head();

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

  // the next field and clearing it (except for the last

  // non-sentinel object which is treated specially to avoid

  // confusion with an active reference).

  while (obj != sentinel_ref()) {

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

    oop next = java_lang_ref_Reference::discovered(obj);

    if (TraceReferenceGC && PrintGCDetails) {

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

                             obj, next);

    }

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

           "The reference should not be enqueued");

    if (next == sentinel_ref()) {  // obj is last

      // Swap refs_list into pendling_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);

    }

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

    obj = next;

  }

}

// Parallel enqueue task

class RefProcEnqueueTask: public AbstractRefProcTaskExecutor::EnqueueTask {

public:

  RefProcEnqueueTask(ReferenceProcessor& ref_processor,

                     DiscoveredList      discovered_refs[],

                     HeapWord*           pending_list_addr,

                     oop                 sentinel_ref,

                     int                 n_queues)

    : EnqueueTask(ref_processor, discovered_refs,

                  pending_list_addr, sentinel_ref, 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 < subclasses_of_ref;

         j++, index += _n_queues) {

      _ref_processor.enqueue_discovered_reflist(

        _refs_lists[index], _pending_list_addr);

      _refs_lists[index].set_head(_sentinel_ref);

      _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, _discoveredSoftRefs,

                           pending_list_addr, sentinel_ref(), _max_num_q);

    task_executor->execute(tsk);

  } else {

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

    for (int i = 0; i < _max_num_q * subclasses_of_ref; i++) {

      enqueue_discovered_reflist(_discoveredSoftRefs[i], pending_list_addr);

      _discoveredSoftRefs[i].set_head(sentinel_ref());

      _discoveredSoftRefs[i].set_length(0);

    }

  }

}

// Iterator for the list of discovered references.

class DiscoveredListIterator {

public:

  inline DiscoveredListIterator(DiscoveredList&    refs_list,

                                OopClosure*        keep_alive,

                                BoolObjectClosure* is_alive);

  // End Of List.

  inline bool has_next() const { return _next != ReferenceProcessor::sentinel_ref(); }

  // Get oop to the Reference object.

  inline oop obj() const { return _ref; }

  // Get oop to the referent object.

  inline oop referent() const { return _referent; }

  // Returns true if referent is alive.

  inline bool is_referent_alive() const;

  // Loads data for the current reference.

  // The "allow_null_referent" argument tells us to allow for the possibility

  // of a NULL referent in the discovered Reference object. This typically

  // happens in the case of concurrent collectors that may have done the

  // discovery concurrently, or interleaved, with mutator execution.

  inline void load_ptrs(DEBUG_ONLY(bool allow_null_referent));

  // Move to the next discovered reference.

  inline void next();

  // Remove the current reference from the list

  inline void remove();

  // Make the Reference object active again.

  inline void make_active() { java_lang_ref_Reference::set_next(_ref, NULL); }

  // Make the referent alive.

  inline void make_referent_alive() {

    if (UseCompressedOops) {

      _keep_alive->do_oop((narrowOop*)_referent_addr);

    } else {

      _keep_alive->do_oop((oop*)_referent_addr);

    }

  }

  // Update the discovered field.

  inline void update_discovered() {

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

    if (UseCompressedOops) {

      _keep_alive->do_oop((narrowOop*)_prev_next);

    } else {

      _keep_alive->do_oop((oop*)_prev_next);

    }

  }

  // NULL out referent pointer.

  inline void clear_referent() { oop_store_raw(_referent_addr, NULL); }

  // Statistics

  NOT_PRODUCT(

  inline size_t processed() const { return _processed; }

  inline size_t removed() const   { return _removed; }

  )

  inline void move_to_next();

private:

  DiscoveredList&    _refs_list;

  HeapWord*          _prev_next;

  oop                _ref;

  HeapWord*          _discovered_addr;

  oop                _next;

  HeapWord*          _referent_addr;

  oop                _referent;

  OopClosure*        _keep_alive;

  BoolObjectClosure* _is_alive;

  DEBUG_ONLY(

  oop                _first_seen; // cyclic linked list check

  )

  NOT_PRODUCT(

  size_t             _processed;

  size_t             _removed;

  )

};

inline DiscoveredListIterator::DiscoveredListIterator(DiscoveredList&    refs_list,

                                                      OopClosure*        keep_alive,

                                                      BoolObjectClosure* is_alive)