/*
 * Copyright (c) 2017, Red Hat, Inc. and/or its affiliates.
 *
 * 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 "gc/shared/gcTraceTime.inline.hpp"
#include "gc/shared/workgroup.hpp"
#include "gc/shared/taskqueue.inline.hpp"
#include "gc/shenandoah/shenandoahBarrierSet.hpp"
#include "gc/shenandoah/shenandoahCollectionSet.hpp"
#include "gc/shenandoah/shenandoahFreeSet.hpp"
#include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
#include "gc/shenandoah/shenandoahHeap.inline.hpp"
#include "gc/shenandoah/shenandoahPartialGC.hpp"
#include "gc/shenandoah/shenandoahRootProcessor.hpp"
#include "gc/shenandoah/shenandoahTaskqueue.hpp"
#include "memory/iterator.hpp"

class PartialEvacuateUpdateRootsClosure : public OopClosure {
  ShenandoahPartialGC* _partial_gc;
  Thread* _thread;
  SCMObjToScanQueue* _queue;
private:
  template <class T>
  void do_oop_work(T* p) { _partial_gc->process_oop(p, _thread, _queue, false); }
public:
  PartialEvacuateUpdateRootsClosure(SCMObjToScanQueue* q) :
    _partial_gc(ShenandoahHeap::heap()->partial_gc()),
    _thread(Thread::current()), _queue(q) {}
  void do_oop(oop* p) { do_oop_work(p); }
  void do_oop(narrowOop* p) { do_oop_work(p); }
};

class PartialEvacuateUpdateHeapClosure : public ExtendedOopClosure {
  ShenandoahPartialGC* _partial_gc;
  Thread* _thread;
  SCMObjToScanQueue* _queue;
private:
  template <class T>
  void do_oop_work(T* p) {
    _partial_gc->process_oop(p, _thread, _queue, true);
  }
public:
  PartialEvacuateUpdateHeapClosure(SCMObjToScanQueue* q) :
    _partial_gc(ShenandoahHeap::heap()->partial_gc()),
    _thread(Thread::current()), _queue(q) {}
  void do_oop(oop* p) { do_oop_work(p); }
  void do_oop(narrowOop* p) { do_oop_work(p); }
};

class ShenandoahPartialCollectionTask : public AbstractGangTask {
private:
  ShenandoahRootProcessor* _rp;
  ShenandoahHeapRegionSet* _root_regions;
  ShenandoahHeap* _heap;
public:
  ShenandoahPartialCollectionTask(ShenandoahRootProcessor* rp,
                                  ShenandoahHeapRegionSet* root_regions) :
    AbstractGangTask("Shenandoah Partial Collection"),
    _rp(rp), _root_regions(root_regions),
    _heap(ShenandoahHeap::heap()) {}

  void work(uint worker_id) {
    SCMObjToScanQueueSet* queues = _heap->partial_gc()->task_queues();
    SCMObjToScanQueue* q = queues->queue(worker_id);
    {
      // First process ordinary GC roots.
      PartialEvacuateUpdateRootsClosure roots_cl(q);
      CLDToOopClosure cld_cl(&roots_cl);
      MarkingCodeBlobClosure code_cl(&roots_cl, CodeBlobToOopClosure::FixRelocations);
      _rp->process_all_roots(&roots_cl, &roots_cl, &cld_cl, &code_cl, worker_id);
    }
    drain_queue(worker_id);
    if (_heap->cancelled_concgc()) { q->set_empty(); return; }
    {
      // Then process root regions.
      PartialEvacuateUpdateHeapClosure cl(q);
      ShenandoahHeapRegion* r = _root_regions->claim_next();
      while (r != NULL) {
        r->oop_iterate(&cl);
        drain_queue(worker_id);
        if (_heap->cancelled_concgc()) { q->set_empty(); return; }
        r = _root_regions->claim_next();
      }
    }
  }

  void drain_queue(uint worker_id) {
    SCMObjToScanQueueSet* queues = _heap->partial_gc()->task_queues();
    SCMObjToScanQueue* q = queues->queue(worker_id);
    PartialEvacuateUpdateHeapClosure cl(q);
    // Empty queue if necessary.
    int seed = 17;
    SCMTask task;
    while ((q->pop_buffer(task) ||
            q->pop_local(task) ||
            q->pop_overflow(task)) &&
           !_heap->cancelled_concgc()) {
      oop obj = task.obj();
      assert(! oopDesc::is_null(obj), "must not be null");
      obj->oop_iterate(&cl);
    }
  }

};

ShenandoahPartialGC::ShenandoahPartialGC(ShenandoahHeap* heap, uint max_regions) :
  _heap(heap),
  _root_regions(new ShenandoahHeapRegionSet(max_regions)),
  _task_queues(new SCMObjToScanQueueSet(heap->max_workers())) {

  uint num_queues = heap->max_workers();
  for (uint i = 0; i < num_queues; ++i) {
    SCMObjToScanQueue* task_queue = new SCMObjToScanQueue();
    task_queue->initialize();
    _task_queues->register_queue(i, task_queue);
  }

}

ShenandoahHeapRegionSet* ShenandoahPartialGC::root_regions() {
  return _root_regions;
}

void ShenandoahPartialGC::prepare() {
  _heap->collection_set()->clear();
  assert(_heap->collection_set()->count() == 0, "collection set not clear");

  _heap->ensure_parsability(true);

  ShenandoahConnectionMatrix* matrix = _heap->connection_matrix();
  ShenandoahHeapRegionSet* regions = _heap->regions();
  ShenandoahCollectionSet* collection_set = _heap->collection_set();
  ShenandoahFreeSet* free_set = _heap->free_regions();
  free_set->clear();
  _root_regions->clear();
  assert(_root_regions->count() == 0, "must be cleared");
  uint num_regions = _heap->num_regions();

  // First pass: find collection set.
  for (uint to_idx = 0; to_idx < num_regions; to_idx++) {
    ShenandoahHeapRegion* region = regions->get(to_idx);
    if (region->is_humongous() || region->is_empty() || region->is_pinned()) continue;
    assert(! _heap->region_in_collection_set(to_idx), "must not be in cset yet");
    uint num_incoming = 0;
    for (uint from_idx = 0; from_idx < num_regions; from_idx++) {
      if (matrix->is_connected(from_idx, to_idx)) {
        num_incoming++;
      }
    }
    if (num_incoming < ShenandoahPartialInboundThreshold) {
      collection_set->add_region(region);
      _heap->set_region_in_collection_set(to_idx, true);
    }
  }
  // Second pass: find all root regions.
  for (uint to_idx = 0; to_idx < num_regions; to_idx++) {
    ShenandoahHeapRegion* region = regions->get(to_idx);
    if (region->is_humongous() || region->is_empty() || region->is_pinned()) continue;
    if (_heap->region_in_collection_set(to_idx)) {
      for (uint from_idx = 0; from_idx < num_regions; from_idx++) {
        if (matrix->is_connected(from_idx, to_idx)) {
          ShenandoahHeapRegion* r = regions->get(from_idx);
          if (! _root_regions->contains(r)) {
            _root_regions->add_region(r);
          }
        }
      }
    }
  }
  // Final pass: free regions.
  for (uint to_idx = 0; to_idx < num_regions; to_idx++) {
    ShenandoahHeapRegion* region = regions->get(to_idx);
    if (! region->is_humongous() &&
        ! region->is_pinned() &&
        ! _root_regions->contains(region) &&
        ! _heap->in_collection_set(region)) {

      free_set->add_region(region);
    }
  }
  log_debug(gc, ergo)("got "SIZE_FORMAT" cset regions", collection_set->count());
  log_debug(gc, ergo)("got "SIZE_FORMAT" root regions", _root_regions->count());
}

void ShenandoahPartialGC::do_partial_collection() {

  _heap->gc_timer()->register_gc_start();
  {
    GCTraceTime(Info, gc) time("Pause Partial", _heap->gc_timer(), GCCause::_no_gc, true);

    COMPILER2_PRESENT(DerivedPointerTable::clear());

    {
      ClassLoaderDataGraph::clear_claimed_marks();
      ShenandoahRootProcessor rp(_heap, _heap->workers()->active_workers());
      ShenandoahPartialCollectionTask partial_task(&rp, _root_regions);
      _heap->workers()->run_task(&partial_task);
    }

    COMPILER2_PRESENT(DerivedPointerTable::update_pointers());

    if (! _heap->cancelled_concgc()) {
      ShenandoahHeap::ShenandoahHeapLock heap_lock(_heap);
      uint num_cset = _heap->collection_set()->count();
      for (uint i = 0; i < num_cset; i++) {
        ShenandoahHeapRegion* r = _heap->collection_set()->get(i);
        _heap->decrease_used(r->used());
        r->recycle();
        _heap->free_regions()->add_region(r);
      }

      reset();
    }
  }
  _heap->gc_timer()->register_gc_end();
}

void ShenandoahPartialGC::reset() {
  _heap->collection_set()->clear();
  _heap->clear_cset_fast_test();
  _root_regions->clear();
}

template <class T>
void ShenandoahPartialGC::process_oop(T* p, Thread* thread, SCMObjToScanQueue* queue, bool update_matrix) {
  T o = oopDesc::load_heap_oop(p);
  if (! oopDesc::is_null(o)) {
    oop obj = oopDesc::decode_heap_oop_not_null(o);
    if (_heap->in_collection_set(obj)) {
      oop forw = ShenandoahBarrierSet::resolve_oop_static_not_null(obj);
      if (oopDesc::unsafe_equals(obj, forw)) {
        forw = _heap->evacuate_object(obj, thread);
      }
      assert(! oopDesc::unsafe_equals(obj, forw) || _heap->cancelled_concgc(), "must be evacuated");
      // oopDesc::encode_store_heap_oop_not_null(p, forw);
      // queue->push(forw);
      // Can use simple store for GC roots.
      if (oopDesc::unsafe_equals(obj, _heap->atomic_compare_exchange_oop(forw, p, obj))) {
        if (update_matrix) {
          uint from_idx = _heap->heap_region_index_containing(p);
          uint to_idx = _heap->heap_region_index_containing(forw);
          _heap->connection_matrix()->set_connected(from_idx, to_idx, true);
        }
        assert(forw->is_oop(), "sanity");
        bool succeeded = queue->push(SCMTask(forw));
        assert(succeeded, "must succeed to push to task queue");
      }
    }
  }
}

bool ShenandoahPartialGC::is_in_root_region(oop obj) {
  // TODO: make this very fast!!
  ShenandoahHeapRegion* r = _heap->heap_region_containing(obj);
  return _root_regions->contains(r);
}

SCMObjToScanQueueSet* ShenandoahPartialGC::task_queues() {
  return _task_queues;
}