/*

 * Copyright 2001-2009 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/_parNewGeneration.cpp.incl"

#ifdef _MSC_VER

#pragma warning( push )

#pragma warning( disable:4355 ) // 'this' : used in base member initializer list

#endif

ParScanThreadState::ParScanThreadState(Space* to_space_,

                                       ParNewGeneration* gen_,

                                       Generation* old_gen_,

                                       int thread_num_,

                                       ObjToScanQueueSet* work_queue_set_,

                                       size_t desired_plab_sz_,

                                       ParallelTaskTerminator& term_) :

  _to_space(to_space_), _old_gen(old_gen_), _young_gen(gen_), _thread_num(thread_num_),

  _work_queue(work_queue_set_->queue(thread_num_)), _to_space_full(false),

  _ageTable(false), // false ==> not the global age table, no perf data.

  _to_space_alloc_buffer(desired_plab_sz_),

  _to_space_closure(gen_, this), _old_gen_closure(gen_, this),

  _to_space_root_closure(gen_, this), _old_gen_root_closure(gen_, this),

  _older_gen_closure(gen_, this),

  _evacuate_followers(this, &_to_space_closure, &_old_gen_closure,

                      &_to_space_root_closure, gen_, &_old_gen_root_closure,

                      work_queue_set_, &term_),

  _is_alive_closure(gen_), _scan_weak_ref_closure(gen_, this),

  _keep_alive_closure(&_scan_weak_ref_closure),

  _pushes(0), _pops(0), _steals(0), _steal_attempts(0), _term_attempts(0),

  _strong_roots_time(0.0), _term_time(0.0)

{

  _survivor_chunk_array =

    (ChunkArray*) old_gen()->get_data_recorder(thread_num());

  _hash_seed = 17;  // Might want to take time-based random value.

  _start = os::elapsedTime();

  _old_gen_closure.set_generation(old_gen_);

  _old_gen_root_closure.set_generation(old_gen_);

}

#ifdef _MSC_VER

#pragma warning( pop )

#endif

void ParScanThreadState::record_survivor_plab(HeapWord* plab_start,

                                              size_t plab_word_size) {

  ChunkArray* sca = survivor_chunk_array();

  if (sca != NULL) {

    // A non-null SCA implies that we want the PLAB data recorded.

    sca->record_sample(plab_start, plab_word_size);

  }

}

bool ParScanThreadState::should_be_partially_scanned(oop new_obj, oop old_obj) const {

  return new_obj->is_objArray() &&

         arrayOop(new_obj)->length() > ParGCArrayScanChunk &&

         new_obj != old_obj;

}

void ParScanThreadState::scan_partial_array_and_push_remainder(oop old) {

  assert(old->is_objArray(), "must be obj array");

  assert(old->is_forwarded(), "must be forwarded");

  assert(Universe::heap()->is_in_reserved(old), "must be in heap.");

  assert(!old_gen()->is_in(old), "must be in young generation.");

  objArrayOop obj = objArrayOop(old->forwardee());

  // Process ParGCArrayScanChunk elements now

  // and push the remainder back onto queue

  int start     = arrayOop(old)->length();

  int end       = obj->length();

  int remainder = end - start;

  assert(start <= end, "just checking");

  if (remainder > 2 * ParGCArrayScanChunk) {

    // Test above combines last partial chunk with a full chunk

    end = start + ParGCArrayScanChunk;

    arrayOop(old)->set_length(end);

    // Push remainder.

    bool ok = work_queue()->push(old);

    assert(ok, "just popped, push must be okay");

    note_push();

  } else {

    // Restore length so that it can be used if there

    // is a promotion failure and forwarding pointers

    // must be removed.

    arrayOop(old)->set_length(end);

  }

  // process our set of indices (include header in first chunk)

  // should make sure end is even (aligned to HeapWord in case of compressed oops)

  if ((HeapWord *)obj < young_old_boundary()) {

    // object is in to_space

    obj->oop_iterate_range(&_to_space_closure, start, end);

  } else {

    // object is in old generation

    obj->oop_iterate_range(&_old_gen_closure, start, end);

  }

}

void ParScanThreadState::trim_queues(int max_size) {

  ObjToScanQueue* queue = work_queue();

  do {

    while (queue->size() > (juint)max_size) {

      oop obj_to_scan;

      if (queue->pop_local(obj_to_scan)) {

        note_pop();

        if ((HeapWord *)obj_to_scan < young_old_boundary()) {

          if (obj_to_scan->is_objArray() &&

              obj_to_scan->is_forwarded() &&

              obj_to_scan->forwardee() != obj_to_scan) {

            scan_partial_array_and_push_remainder(obj_to_scan);

          } else {

            // object is in to_space

            obj_to_scan->oop_iterate(&_to_space_closure);

          }

        } else {

          // object is in old generation

          obj_to_scan->oop_iterate(&_old_gen_closure);

        }

      }

    }

    // For the  case of compressed oops, we have a private, non-shared

    // overflow stack, so we eagerly drain it so as to more evenly

    // distribute load early. Note: this may be good to do in

    // general rather than delay for the final stealing phase.

    // If applicable, we'll transfer a set of objects over to our

    // work queue, allowing them to be stolen and draining our

    // private overflow stack.

  } while (ParGCTrimOverflow && young_gen()->take_from_overflow_list(this));

}

bool ParScanThreadState::take_from_overflow_stack() {

  assert(young_gen()->overflow_list() == NULL, "Error");

  ObjToScanQueue* queue = work_queue();

  GrowableArray<oop>* of_stack = overflow_stack();

  uint num_overflow_elems = of_stack->length();

  uint num_take_elems     = MIN2(MIN2((queue->max_elems() - queue->size())/4,

                                      (juint)ParGCDesiredObjsFromOverflowList),

                                 num_overflow_elems);

  // Transfer the most recent num_take_elems from the overflow

  // stack to our work queue.

  for (size_t i = 0; i != num_take_elems; i++) {

    oop cur = of_stack->pop();

    oop obj_to_push = cur->forwardee();

    assert(Universe::heap()->is_in_reserved(cur), "Should be in heap");

    assert(!old_gen()->is_in_reserved(cur), "Should be in young gen");

    assert(Universe::heap()->is_in_reserved(obj_to_push), "Should be in heap");

    if (should_be_partially_scanned(obj_to_push, cur)) {

      assert(arrayOop(cur)->length() == 0, "entire array remaining to be scanned");

      obj_to_push = cur;

    }

    bool ok = queue->push(obj_to_push);

    assert(ok, "Should have succeeded");

  }

  assert(young_gen()->overflow_list() == NULL, "Error");

  return num_take_elems > 0;  // was something transferred?

}

void ParScanThreadState::push_on_overflow_stack(oop p) {

  overflow_stack()->push(p);

  assert(young_gen()->overflow_list() == NULL, "Error");

}

HeapWord* ParScanThreadState::alloc_in_to_space_slow(size_t word_sz) {

  // Otherwise, if the object is small enough, try to reallocate the

  // buffer.

  HeapWord* obj = NULL;

  if (!_to_space_full) {

    ParGCAllocBuffer* const plab = to_space_alloc_buffer();

    Space*            const sp   = to_space();

    if (word_sz * 100 <

        ParallelGCBufferWastePct * plab->word_sz()) {

      // Is small enough; abandon this buffer and start a new one.

      plab->retire(false, false);

      size_t buf_size = plab->word_sz();

      HeapWord* buf_space = sp->par_allocate(buf_size);

      if (buf_space == NULL) {

        const size_t min_bytes =

          ParGCAllocBuffer::min_size() << LogHeapWordSize;

        size_t free_bytes = sp->free();

        while(buf_space == NULL && free_bytes >= min_bytes) {

          buf_size = free_bytes >> LogHeapWordSize;

          assert(buf_size == (size_t)align_object_size(buf_size),

                 "Invariant");

          buf_space  = sp->par_allocate(buf_size);

          free_bytes = sp->free();

        }

      }

      if (buf_space != NULL) {

        plab->set_word_size(buf_size);

        plab->set_buf(buf_space);

        record_survivor_plab(buf_space, buf_size);

        obj = plab->allocate(word_sz);

        // Note that we cannot compare buf_size < word_sz below

        // because of AlignmentReserve (see ParGCAllocBuffer::allocate()).

        assert(obj != NULL || plab->words_remaining() < word_sz,

               "Else should have been able to allocate");

        // It's conceivable that we may be able to use the

        // buffer we just grabbed for subsequent small requests

        // even if not for this one.

      } else {

        // We're used up.

        _to_space_full = true;

      }

    } else {

      // Too large; allocate the object individually.

      obj = sp->par_allocate(word_sz);

    }

  }

  return obj;

}

void ParScanThreadState::undo_alloc_in_to_space(HeapWord* obj,

                                                size_t word_sz) {

  // Is the alloc in the current alloc buffer?

  if (to_space_alloc_buffer()->contains(obj)) {

    assert(to_space_alloc_buffer()->contains(obj + word_sz - 1),

           "Should contain whole object.");

    to_space_alloc_buffer()->undo_allocation(obj, word_sz);

  } else {

    CollectedHeap::fill_with_object(obj, word_sz);

  }

}

class ParScanThreadStateSet: private ResourceArray {

public:

  // Initializes states for the specified number of threads;

  ParScanThreadStateSet(int                     num_threads,

                        Space&                  to_space,

                        ParNewGeneration&       gen,

                        Generation&             old_gen,

                        ObjToScanQueueSet&      queue_set,

                        size_t                  desired_plab_sz,

                        ParallelTaskTerminator& term);

  inline ParScanThreadState& thread_sate(int i);

  int pushes() { return _pushes; }

  int pops()   { return _pops; }

  int steals() { return _steals; }

  void reset();

  void flush();

private:

  ParallelTaskTerminator& _term;

  ParNewGeneration&       _gen;

  Generation&             _next_gen;

  // staticstics

  int _pushes;

  int _pops;

  int _steals;

};

ParScanThreadStateSet::ParScanThreadStateSet(

  int num_threads, Space& to_space, ParNewGeneration& gen,

  Generation& old_gen, ObjToScanQueueSet& queue_set,

  size_t desired_plab_sz, ParallelTaskTerminator& term)

  : ResourceArray(sizeof(ParScanThreadState), num_threads),

    _gen(gen), _next_gen(old_gen), _term(term),

    _pushes(0), _pops(0), _steals(0)

{

  assert(num_threads > 0, "sanity check!");

  // Initialize states.

  for (int i = 0; i < num_threads; ++i) {

    new ((ParScanThreadState*)_data + i)

        ParScanThreadState(&to_space, &gen, &old_gen, i, &queue_set,

  }

}

inline ParScanThreadState& ParScanThreadStateSet::thread_sate(int i)

{

  assert(i >= 0 && i < length(), "sanity check!");

  return ((ParScanThreadState*)_data)[i];

}

void ParScanThreadStateSet::reset()

{

  _term.reset_for_reuse();

}

void ParScanThreadStateSet::flush()

{

  for (int i = 0; i < length(); ++i) {

    ParScanThreadState& par_scan_state = thread_sate(i);

    // Flush stats related to To-space PLAB activity and

    // retire the last buffer.

    par_scan_state.to_space_alloc_buffer()->

      flush_stats_and_retire(_gen.plab_stats(),

                             false /* !retain */);

    // Every thread has its own age table.  We need to merge

    // them all into one.

    ageTable *local_table = par_scan_state.age_table();

    _gen.age_table()->merge(local_table);

    // Inform old gen that we're done.

    _next_gen.par_promote_alloc_done(i);

    _next_gen.par_oop_since_save_marks_iterate_done(i);

    // Flush stats related to work queue activity (push/pop/steal)

    // This could conceivably become a bottleneck; if so, we'll put the

    // stat's gathering under the flag.

    if (PAR_STATS_ENABLED) {

      _pushes += par_scan_state.pushes();

      _pops   += par_scan_state.pops();

      _steals += par_scan_state.steals();

      if (ParallelGCVerbose) {

        gclog_or_tty->print("Thread %d complete:\n"

                            "  Pushes: %7d    Pops: %7d    Steals %7d (in %d attempts)\n",

                            i, par_scan_state.pushes(), par_scan_state.pops(),

                            par_scan_state.steals(), par_scan_state.steal_attempts());

        if (par_scan_state.overflow_pushes() > 0 ||

            par_scan_state.overflow_refills() > 0) {

          gclog_or_tty->print("  Overflow pushes: %7d    "

                              "Overflow refills: %7d for %d objs.\n",

                              par_scan_state.overflow_pushes(),

                              par_scan_state.overflow_refills(),

                              par_scan_state.overflow_refill_objs());

        }

        double elapsed = par_scan_state.elapsed();

        double strong_roots = par_scan_state.strong_roots_time();

        double term = par_scan_state.term_time();

        gclog_or_tty->print(

                            "  Elapsed: %7.2f ms.\n"

                            "    Strong roots: %7.2f ms (%6.2f%%)\n"

                            "    Termination:  %7.2f ms (%6.2f%%) (in %d entries)\n",

                           elapsed * 1000.0,

                           strong_roots * 1000.0, (strong_roots*100.0/elapsed),

                           term * 1000.0, (term*100.0/elapsed),

                           par_scan_state.term_attempts());

      }

    }

  }

}

ParScanClosure::ParScanClosure(ParNewGeneration* g,

                               ParScanThreadState* par_scan_state) :

  OopsInGenClosure(g), _par_scan_state(par_scan_state), _g(g)

{

  assert(_g->level() == 0, "Optimized for youngest generation");

  _boundary = _g->reserved().end();

}

void ParScanWithBarrierClosure::do_oop(oop* p)       { ParScanClosure::do_oop_work(p, true, false); }

void ParScanWithBarrierClosure::do_oop(narrowOop* p) { ParScanClosure::do_oop_work(p, true, false); }

void ParScanWithoutBarrierClosure::do_oop(oop* p)       { ParScanClosure::do_oop_work(p, false, false); }

void ParScanWithoutBarrierClosure::do_oop(narrowOop* p) { ParScanClosure::do_oop_work(p, false, false); }

void ParRootScanWithBarrierTwoGensClosure::do_oop(oop* p)       { ParScanClosure::do_oop_work(p, true, true); }

void ParRootScanWithBarrierTwoGensClosure::do_oop(narrowOop* p) { ParScanClosure::do_oop_work(p, true, true); }

void ParRootScanWithoutBarrierClosure::do_oop(oop* p)       { ParScanClosure::do_oop_work(p, false, true); }

void ParRootScanWithoutBarrierClosure::do_oop(narrowOop* p) { ParScanClosure::do_oop_work(p, false, true); }

ParScanWeakRefClosure::ParScanWeakRefClosure(ParNewGeneration* g,

                                             ParScanThreadState* par_scan_state)

  : ScanWeakRefClosure(g), _par_scan_state(par_scan_state)

{}

void ParScanWeakRefClosure::do_oop(oop* p)       { ParScanWeakRefClosure::do_oop_work(p); }

void ParScanWeakRefClosure::do_oop(narrowOop* p) { ParScanWeakRefClosure::do_oop_work(p); }

#ifdef WIN32

#pragma warning(disable: 4786) /* identifier was truncated to '255' characters in the browser information */

#endif

ParEvacuateFollowersClosure::ParEvacuateFollowersClosure(

    ParScanThreadState* par_scan_state_,

    ParScanWithoutBarrierClosure* to_space_closure_,

    ParScanWithBarrierClosure* old_gen_closure_,

    ParRootScanWithoutBarrierClosure* to_space_root_closure_,

    ParNewGeneration* par_gen_,

    ParRootScanWithBarrierTwoGensClosure* old_gen_root_closure_,

    ObjToScanQueueSet* task_queues_,

    ParallelTaskTerminator* terminator_) :

    _par_scan_state(par_scan_state_),

    _to_space_closure(to_space_closure_),

    _old_gen_closure(old_gen_closure_),

    _to_space_root_closure(to_space_root_closure_),

    _old_gen_root_closure(old_gen_root_closure_),

    _par_gen(par_gen_),

    _task_queues(task_queues_),

    _terminator(terminator_)

{}

void ParEvacuateFollowersClosure::do_void() {

  ObjToScanQueue* work_q = par_scan_state()->work_queue();

  while (true) {

    // Scan to-space and old-gen objs until we run out of both.

    oop obj_to_scan;

    par_scan_state()->trim_queues(0);

    // We have no local work, attempt to steal from other threads.

    // attempt to steal work from promoted.

    par_scan_state()->note_steal_attempt();

    if (task_queues()->steal(par_scan_state()->thread_num(),

                             par_scan_state()->hash_seed(),

                             obj_to_scan)) {

      par_scan_state()->note_steal();

      bool res = work_q->push(obj_to_scan);

      assert(res, "Empty queue should have room for a push.");

      par_scan_state()->note_push();

      //   if successful, goto Start.

      continue;

      // try global overflow list.

    } else if (par_gen()->take_from_overflow_list(par_scan_state())) {

      continue;

    }

    // Otherwise, offer termination.

    par_scan_state()->start_term_time();

    if (terminator()->offer_termination()) break;

    par_scan_state()->end_term_time();

  }

  assert(par_gen()->_overflow_list == NULL && par_gen()->_num_par_pushes == 0,

         "Broken overflow list?");

  // Finish the last termination pause.

  par_scan_state()->end_term_time();

}

ParNewGenTask::ParNewGenTask(ParNewGeneration* gen, Generation* next_gen,

                HeapWord* young_old_boundary, ParScanThreadStateSet* state_set) :

    AbstractGangTask("ParNewGeneration collection"),

    _gen(gen), _next_gen(next_gen),

    _young_old_boundary(young_old_boundary),

    _state_set(state_set)

  {}

void ParNewGenTask::work(int i) {

  GenCollectedHeap* gch = GenCollectedHeap::heap();

  // Since this is being done in a separate thread, need new resource

  // and handle marks.

  ResourceMark rm;

  HandleMark hm;

  // We would need multiple old-gen queues otherwise.

  assert(gch->n_gens() == 2, "Par young collection currently only works with one older gen.");

  Generation* old_gen = gch->next_gen(_gen);

  ParScanThreadState& par_scan_state = _state_set->thread_sate(i);

  par_scan_state.set_young_old_boundary(_young_old_boundary);

  par_scan_state.start_strong_roots();

  gch->gen_process_strong_roots(_gen->level(),

                                true, // Process younger gens, if any,

                                      // as strong roots.

                                false,// not collecting perm generation.

                                SharedHeap::SO_AllClasses,

                                &par_scan_state.older_gen_closure(),

                                &par_scan_state.to_space_root_closure());

  par_scan_state.end_strong_roots();

  // "evacuate followers".

  par_scan_state.evacuate_followers_closure().do_void();

}

#ifdef _MSC_VER

#pragma warning( push )

#pragma warning( disable:4355 ) // 'this' : used in base member initializer list

#endif

ParNewGeneration::

ParNewGeneration(ReservedSpace rs, size_t initial_byte_size, int level)

  : DefNewGeneration(rs, initial_byte_size, level, "PCopy"),

  _overflow_list(NULL),

  _is_alive_closure(this),

  _plab_stats(YoungPLABSize, PLABWeight)

{

  NOT_PRODUCT(_overflow_counter = ParGCWorkQueueOverflowInterval;)

  NOT_PRODUCT(_num_par_pushes = 0;)

  _task_queues = new ObjToScanQueueSet(ParallelGCThreads);

  guarantee(_task_queues != NULL, "task_queues allocation failure.");

  for (uint i1 = 0; i1 < ParallelGCThreads; i1++) {

    ObjToScanQueuePadded *q_padded = new ObjToScanQueuePadded();

    guarantee(q_padded != NULL, "work_queue Allocation failure.");

    _task_queues->register_queue(i1, &q_padded->work_queue);

  }

  for (uint i2 = 0; i2 < ParallelGCThreads; i2++)

    _task_queues->queue(i2)->initialize();