/*

 * Copyright 2001-2007 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

# include "incls/_precompiled.incl"

# include "incls/_referenceProcessor.cpp.incl"

// List of discovered references.

class DiscoveredList {

public:

         DiscoveredList() : _head(NULL), _len(0) { }

  oop    head() const           { return _head; }

  oop*   head_ptr()             { return &_head; }

  void   set_head(oop o)        { _head = o; }

  bool   empty() const          { return _head == ReferenceProcessor::_sentinelRef; }

  size_t length()               { return _len; }

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

private:

  size_t _len;

  oop   _head;

};

oop  ReferenceProcessor::_sentinelRef = NULL;

const int subclasses_of_ref = REF_PHANTOM - REF_OTHER;

void referenceProcessor_init() {

  ReferenceProcessor::init_statics();

}

void ReferenceProcessor::init_statics() {

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

  EXCEPTION_MARK;

  _sentinelRef = instanceKlass::cast(

                   SystemDictionary::object_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!");

  guarantee(RefDiscoveryPolicy == ReferenceBasedDiscovery ||

            RefDiscoveryPolicy == ReferentBasedDiscovery,

            "Unrecongnized RefDiscoveryPolicy");

}

ReferenceProcessor* ReferenceProcessor::create_ref_processor(

    MemRegion          span,

    bool               atomic_discovery,

    bool               mt_discovery,

    BoolObjectClosure* is_alive_non_header,

    int                parallel_gc_threads,

    bool               mt_processing)

{

  int mt_degree = 1;

  if (parallel_gc_threads > 1) {

    mt_degree = parallel_gc_threads;

  }

  ReferenceProcessor* rp =

    new ReferenceProcessor(span, atomic_discovery,

                           mt_discovery, mt_degree,

                           mt_processing);

  if (rp == NULL) {

    vm_exit_during_initialization("Could not allocate ReferenceProcessor object");

  }

  rp->set_is_alive_non_header(is_alive_non_header);

  return rp;

}

ReferenceProcessor::ReferenceProcessor(MemRegion span,

  bool atomic_discovery, bool mt_discovery, int mt_degree,

  bool mt_processing) :

  _discovering_refs(false),

  _enqueuing_is_done(false),

  _is_alive_non_header(NULL),

  _processing_is_mt(mt_processing),

  _next_id(0)

{

  _span = span;

  _discovery_is_atomic = atomic_discovery;

  _discovery_is_mt     = mt_discovery;

  _num_q               = mt_degree;

  _discoveredSoftRefs  = NEW_C_HEAP_ARRAY(DiscoveredList, _num_q * subclasses_of_ref);

  if (_discoveredSoftRefs == NULL) {

    vm_exit_during_initialization("Could not allocated RefProc Array");

  }

  _discoveredWeakRefs    = &_discoveredSoftRefs[_num_q];

  _discoveredFinalRefs   = &_discoveredWeakRefs[_num_q];

  _discoveredPhantomRefs = &_discoveredFinalRefs[_num_q];

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

  // Initialized all entries to _sentinelRef

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

        _discoveredSoftRefs[i].set_head(_sentinelRef);

    _discoveredSoftRefs[i].set_length(0);

  }

}

#ifndef PRODUCT

void ReferenceProcessor::verify_no_references_recorded() {

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

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

    guarantee(_discoveredSoftRefs[i].empty(),

              "Found non-empty discovered list");

  }

}

#endif

void ReferenceProcessor::weak_oops_do(OopClosure* f) {

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

    f->do_oop(_discoveredSoftRefs[i].head_ptr());

  }

}

void ReferenceProcessor::oops_do(OopClosure* f) {

  f->do_oop(&_sentinelRef);

}

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(

  ReferencePolicy*             policy,

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

unsigned int ReferenceProcessor::count_jni_refs()

{

  class AlwaysAliveClosure: public BoolObjectClosure {

  public:

    bool do_object_b(oop obj) { return true; }

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

    }

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

  complete_gc->do_void();

}

bool ReferenceProcessor::enqueue_discovered_references(AbstractRefProcTaskExecutor* task_executor) {

  NOT_PRODUCT(verify_ok_to_handle_reflists());

  // Remember old value of pending references list

  oop* pending_list_addr = java_lang_ref_Reference::pending_list_addr();

  oop old_pending_list_value = *pending_list_addr;

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

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

  enqueue_discovered_reflists(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, *(pending_list_addr));

  // Stop treating discovered references specially.

  disable_discovery();

  // Return true if new pending references were added

  return old_pending_list_value != *pending_list_addr;

}

void ReferenceProcessor::enqueue_discovered_reflist(DiscoveredList& refs_list,

  oop* 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 != _sentinelRef) {

    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,

                             (oopDesc*) obj, (oopDesc*) next);

    }

    assert(*java_lang_ref_Reference::next_addr(obj) == NULL,

      "The reference should not be enqueued");

    if (next == _sentinelRef) {  // 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 = (oop)Atomic::xchg_ptr(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[],

                     oop*                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.num_q(), "Index out-of-bounds");

    // Simplest first cut: static partitioning.

    int index = work_id;

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

  AbstractRefProcTaskExecutor* task_executor) {

  if (_processing_is_mt && task_executor != NULL) {

    // Parallel code

    RefProcEnqueueTask tsk(*this, _discoveredSoftRefs,

                           pending_list_addr, _sentinelRef, _num_q);

    task_executor->execute(tsk);

  } else {

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

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

      enqueue_discovered_reflist(_discoveredSoftRefs[i], pending_list_addr);

      _discoveredSoftRefs[i].set_head(_sentinelRef);

      _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::_sentinelRef; }

  // 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 and move to the next.

  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() { _keep_alive->do_oop(_referent_addr); }

  // Update the discovered field.

  inline void update_discovered() { _keep_alive->do_oop(_prev_next); }

  // NULL out referent pointer.

  inline void clear_referent() { *_referent_addr = NULL; }

  // Statistics

  NOT_PRODUCT(

  inline size_t processed() const { return _processed; }

  inline size_t removed() const   { return _removed; }

  )

private:

  inline void move_to_next();

private:

  DiscoveredList&    _refs_list;

  oop*               _prev_next;

  oop                _ref;

  oop*               _discovered_addr;

  oop                _next;

  oop*               _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)

  : _refs_list(refs_list),

    _prev_next(refs_list.head_ptr()),

    _ref(refs_list.head()),

#ifdef ASSERT

    _first_seen(refs_list.head()),

#endif

#ifndef PRODUCT

    _processed(0),

    _removed(0),

#endif

    _next(refs_list.head()),

    _keep_alive(keep_alive),

    _is_alive(is_alive)

{ }

inline bool DiscoveredListIterator::is_referent_alive() const

{

  return _is_alive->do_object_b(_referent);

}

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

{

  _discovered_addr = java_lang_ref_Reference::discovered_addr(_ref);

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

         "discovered field is bad");

  _next = *_discovered_addr;

  _referent_addr = java_lang_ref_Reference::referent_addr(_ref);

  _referent = *_referent_addr;

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

}

inline void DiscoveredListIterator::next()

{

  _prev_next = _discovered_addr;

  move_to_next();

}

inline void DiscoveredListIterator::remove()

{

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

  // Clear the discovered_addr field so that the object does

  // not look like it has been discovered.

  *_discovered_addr = NULL;

  // Remove Reference object from list.

  *_prev_next = _next;

  NOT_PRODUCT(_removed++);

  move_to_next();

}

inline void DiscoveredListIterator::move_to_next()

{

  _ref = _next;

  assert(_ref != _first_seen, "cyclic ref_list found");

  NOT_PRODUCT(_processed++);

}

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