#include "gc/g1/heapRegionRemSet.inline.hpp"

#include "gc/g1/sparsePRT.hpp"

// Collects information about the overall heap root scan progress during an evacuation.

//

// Scanning the remembered sets works by first merging all sources of cards to be

// scanned (log buffers, hcc, remembered sets) into a single data structure to remove

// duplicates and simplify work distribution.

//

// During the following card scanning we not only scan this combined set of cards, but

// also remember that these were completely scanned. The following evacuation passes

// do not scan these cards again, and so need to be preserved across increments.

//

// The representation for all the cards to scan is the card table: cards can have

// one of three states during GC:

// - clean: these cards will not be scanned in this pass

// - dirty: these cards will be scanned in this pass

// - scanned: these cards have already been scanned in a previous pass

//

// After all evacuation is done, we reset the card table to clean.

//

// Work distribution occurs on "chunk" basis, i.e. contiguous ranges of cards. As an

// additional optimization, during card merging we remember which regions and which

// chunks actually contain cards to be scanned. Threads iterate only across these

// regions, and only compete for chunks containing any cards.

//

// Within these chunks, a worker scans the card table on "blocks" of cards, i.e.

// contiguous ranges of dirty cards to be scanned. These blocks are converted to actual

// memory ranges and then passed on to actual scanning.

  class G1DirtyRegions;

  size_t _max_regions;

  // Has this region that is part of the regions in the collection set been processed yet.

  typedef bool G1RemsetIterState;

  G1RemsetIterState volatile* _collection_set_iter_state;

  // Card table iteration claim for each heap region, from 0 (completely unscanned)

  // to (>=) HeapRegion::CardsPerRegion (completely scanned).

  uint volatile* _card_table_scan_state;

  // Random power of two number of cards we want to claim per thread. This corresponds

  // to a 64k of memory work chunk area for every thread.

  // We use the same claim size as Parallel GC. No particular measurements have been

  // performed to determine an optimal number.

  static const uint CardsPerChunk = 128;

  uint _scan_chunks_per_region;

  bool* _region_scan_chunks;

  uint8_t _scan_chunks_shift;

public:

  uint scan_chunk_size() const { return (uint)1 << _scan_chunks_shift; }

  // Returns whether the chunk corresponding to the given region/card in region contain a

  // dirty card, i.e. actually needs scanning.

  bool chunk_needs_scan(uint const region_idx, uint const card_in_region) const {

    size_t const idx = (size_t)region_idx * _scan_chunks_per_region + (card_in_region >> _scan_chunks_shift);

    assert(idx < (_max_regions * _scan_chunks_per_region), "Index " SIZE_FORMAT " out of bounds " SIZE_FORMAT,

           idx, _max_regions * _scan_chunks_per_region);

    return _region_scan_chunks[idx];

  }

  // The complete set of regions which card table needs to be cleared at the end of GC because

  // we scribbled all over them.

  G1DirtyRegions* _all_dirty_regions;

  // The set of regions which card table needs to be scanned for new dirty cards

  // in the current evacuation pass.

  G1DirtyRegions* _next_dirty_regions;

  // Set of (unique) regions that can be added to concurrently.

  class G1DirtyRegions : public CHeapObj<mtGC> {

    uint* _buffer;

    uint _cur_idx;

    size_t _max_regions;

    bool* _contains;

  public:

    G1DirtyRegions(size_t max_regions) :

      _buffer(NEW_C_HEAP_ARRAY(uint, max_regions, mtGC)),

      _cur_idx(0),

      _max_regions(max_regions),

      _contains(NEW_C_HEAP_ARRAY(bool, max_regions, mtGC)) {

      reset();

    }

    static size_t chunk_size() { return M; }

    ~G1DirtyRegions() {

      FREE_C_HEAP_ARRAY(uint, _buffer);

      FREE_C_HEAP_ARRAY(bool, _contains);

    }

    void reset() {

      _cur_idx = 0;

      ::memset(_contains, false, _max_regions * sizeof(bool));

    }

    uint size() const { return _cur_idx; }

    uint at(uint idx) const {

      assert(idx < _cur_idx, "Index %u beyond valid regions", idx);

      return _buffer[idx];

    }

    void add_dirty_region(uint region) {

      if (_contains[region]) {

        return;

      }

      bool marked_as_dirty = Atomic::cmpxchg(true, &_contains[region], false) == false;

      if (marked_as_dirty) {

        uint allocated = Atomic::add(1u, &_cur_idx) - 1;

        _buffer[allocated] = region;

      }

    }

    // Creates the union of this and the other G1DirtyRegions.

    void merge(const G1DirtyRegions* other) {

      for (uint i = 0; i < other->size(); i++) {

        uint region = other->at(i);

        if (!_contains[region]) {

          _buffer[_cur_idx++] = region;

          _contains[region] = true;

        }

      }

    }

  };

  // Returns whether the given region contains cards we need to scan. The remembered

  // set and other sources may contain cards that

  // - are in uncommitted regions

  // - are located in the collection set

  // - are located in free regions

  // as we do not clean up remembered sets before merging heap roots.

  bool contains_cards_to_process(uint const region_idx) const {

    HeapRegion* hr = G1CollectedHeap::heap()->region_at_or_null(region_idx);

    return (hr != NULL && !hr->in_collection_set() && hr->is_old_or_humongous_or_archive());

  }

  class G1MergeCardSetClosure : public HeapRegionClosure {

    G1RemSetScanState* _scan_state;

    G1CardTable* _ct;

    uint _merged_sparse;

    uint _merged_fine;

    uint _merged_coarse;

    // Returns if the region contains cards we need to scan. If so, remember that

    // region in the current set of dirty regions.

    bool remember_if_interesting(uint const region_idx) {

      if (!_scan_state->contains_cards_to_process(region_idx)) {

        return false;

      }

      _scan_state->add_dirty_region(region_idx);

      return true;

    }

  public:

    G1MergeCardSetClosure(G1RemSetScanState* scan_state) :

      _scan_state(scan_state),

      _ct(G1CollectedHeap::heap()->card_table()),

      _merged_sparse(0),

      _merged_fine(0),

      _merged_coarse(0) { }

    void next_coarse_prt(uint const region_idx) {

      if (!remember_if_interesting(region_idx)) {

        return;

      }

      _merged_coarse++;

      size_t region_base_idx = (size_t)region_idx << HeapRegion::LogCardsPerRegion;

      _ct->mark_region_dirty(region_base_idx, HeapRegion::CardsPerRegion);

      _scan_state->set_chunk_region_dirty(region_base_idx);

    }

    void next_fine_prt(uint const region_idx, BitMap* bm) {

      if (!remember_if_interesting(region_idx)) {

        return;

      }

      _merged_fine++;

      size_t const region_base_idx = (size_t)region_idx << HeapRegion::LogCardsPerRegion;

      BitMap::idx_t cur = bm->get_next_one_offset(0);

      while (cur != bm->size()) {

        _ct->mark_clean_as_dirty(region_base_idx + cur);

        _scan_state->set_chunk_dirty(region_base_idx + cur);

        cur = bm->get_next_one_offset(cur + 1);

      }

    }

    void next_sparse_prt(uint const region_idx, SparsePRTEntry::card_elem_t* cards, uint const num_cards) {

      if (!remember_if_interesting(region_idx)) {

        return;

      }

      _merged_sparse++;

      size_t const region_base_idx = (size_t)region_idx << HeapRegion::LogCardsPerRegion;

      for (uint i = 0; i < num_cards; i++) {

        size_t card_idx = region_base_idx + cards[i];

        _ct->mark_clean_as_dirty(card_idx);

        _scan_state->set_chunk_dirty(card_idx);

      }

    }

    virtual bool do_heap_region(HeapRegion* r) {

      assert(r->in_collection_set() || r->is_starts_humongous(), "must be");

      HeapRegionRemSet* rem_set = r->rem_set();

      if (!rem_set->is_empty()) {

        rem_set->iterate_prts(*this);

      }

      return false;

    }

    size_t merged_sparse() const { return _merged_sparse; }

    size_t merged_fine() const { return _merged_fine; }

    size_t merged_coarse() const { return _merged_coarse; }

  };

  // Visitor for the remembered sets of humongous candidate regions to merge their

  // remembered set into the card table.

  class G1FlushHumongousCandidateRemSets : public HeapRegionClosure {

    G1MergeCardSetClosure _cl;

  public:

    G1FlushHumongousCandidateRemSets(G1RemSetScanState* scan_state) : _cl(scan_state) { }

    virtual bool do_heap_region(HeapRegion* r) {

      G1CollectedHeap* g1h = G1CollectedHeap::heap();

      if (!r->is_starts_humongous() ||

          !g1h->region_attr(r->hrm_index()).is_humongous() ||

          r->rem_set()->is_empty()) {

        return false;

      }

      guarantee(r->rem_set()->occupancy_less_or_equal_than(G1RSetSparseRegionEntries),

                "Found a not-small remembered set here. This is inconsistent with previous assumptions.");

      _cl.do_heap_region(r);

      // We should only clear the card based remembered set here as we will not

      // implicitly rebuild anything else during eager reclaim. Note that at the moment

      // (and probably never) we do not enter this path if there are other kind of

      // remembered sets for this region.

      r->rem_set()->clear_locked(true /* only_cardset */);

      // Clear_locked() above sets the state to Empty. However we want to continue

      // collecting remembered set entries for humongous regions that were not

      // reclaimed.

      r->rem_set()->set_state_complete();

#ifdef ASSERT

      G1HeapRegionAttr region_attr = g1h->region_attr(r->hrm_index());

      assert(region_attr.needs_remset_update(), "must be");

#endif

      assert(r->rem_set()->is_empty(), "At this point any humongous candidate remembered set must be empty.");

      return false;

    }

    size_t merged_sparse() const { return _cl.merged_sparse(); }

    size_t merged_fine() const { return _cl.merged_fine(); }

    size_t merged_coarse() const { return _cl.merged_coarse(); }

  };

  // Visitor for the log buffer entries to merge them into the card table.

  class G1MergeLogBufferCardsClosure : public G1CardTableEntryClosure {

    G1RemSetScanState* _scan_state;

    G1CardTable* _ct;

    size_t _cards_dirty;

    size_t _cards_skipped;

  public:

    G1MergeLogBufferCardsClosure(G1CollectedHeap* g1h, G1RemSetScanState* scan_state) :

      _scan_state(scan_state), _ct(g1h->card_table()), _cards_dirty(0), _cards_skipped(0)

    {}

    bool do_card_ptr(CardValue* card_ptr, uint worker_i) {

      // The only time we care about recording cards that

      // contain references that point into the collection set

      // is during RSet updating within an evacuation pause.

      // In this case worker_id should be the id of a GC worker thread.

      assert(SafepointSynchronize::is_at_safepoint(), "not during an evacuation pause");

      uint const region_idx = _ct->region_idx_for(card_ptr);

      // The second clause must come after - the log buffers might contain cards to uncommited

      // regions.

      // This code may count duplicate entries in the log buffers (even if rare) multiple

      // times.

      if (_scan_state->contains_cards_to_process(region_idx) && (*card_ptr == G1CardTable::dirty_card_val())) {

        _scan_state->add_dirty_region(region_idx);

        _scan_state->set_chunk_dirty(_ct->index_for_cardvalue(card_ptr));

        _cards_dirty++;

      } else {

        // We may have had dirty cards in the (initial) collection set (or the

        // young regions which are always in the initial collection set). We do

        // not fix their cards here: we already added these regions to the set of

        // regions to clear the card table at the end during the prepare() phase.

        _cards_skipped++;

      }

      return true;

    }

    size_t cards_dirty() const { return _cards_dirty; }

    size_t cards_skipped() const { return _cards_skipped; }

  };

  class G1MergeHeapRootsTask : public AbstractGangTask {

    HeapRegionClaimer _hr_claimer;

    G1RemSetScanState* _scan_state;

    bool _remembered_set_only;

    G1GCPhaseTimes::GCParPhases _merge_phase;

    volatile bool _fast_reclaim_handled;

  public:

    G1MergeHeapRootsTask(G1RemSetScanState* scan_state, uint num_workers, bool remembered_set_only, G1GCPhaseTimes::GCParPhases merge_phase) :

      AbstractGangTask("G1 Merge Heap Roots"),

      _hr_claimer(num_workers),

      _scan_state(scan_state),

      _remembered_set_only(remembered_set_only),

      _merge_phase(merge_phase),

      _fast_reclaim_handled(false) { }

    virtual void work(uint worker_id) {

      G1CollectedHeap* g1h = G1CollectedHeap::heap();

      G1GCPhaseTimes* p = g1h->phase_times();

      // We schedule flushing the remembered sets of humongous fast reclaim candidates

      // onto the card table first to allow the remaining parallelized tasks hide it.

      if (!_remembered_set_only &&

          p->fast_reclaim_humongous_candidates() > 0 &&

          !_fast_reclaim_handled &&

          !Atomic::cmpxchg(true, &_fast_reclaim_handled, false)) {

        G1FlushHumongousCandidateRemSets cl(_scan_state);

        g1h->heap_region_iterate(&cl);

        p->record_or_add_thread_work_item(_merge_phase, worker_id, cl.merged_sparse(), G1GCPhaseTimes::MergeRSMergedSparse);

        p->record_or_add_thread_work_item(_merge_phase, worker_id, cl.merged_fine(), G1GCPhaseTimes::MergeRSMergedFine);

        p->record_or_add_thread_work_item(_merge_phase, worker_id, cl.merged_coarse(), G1GCPhaseTimes::MergeRSMergedCoarse);

      }

      // Merge remembered sets of current candidates.

      {

        G1GCParPhaseTimesTracker x(p, _merge_phase, worker_id, !_remembered_set_only /* must_record */);

        G1MergeCardSetClosure cl(_scan_state);

        g1h->collection_set_iterate_increment_from(&cl, &_hr_claimer, worker_id);

        p->record_or_add_thread_work_item(_merge_phase, worker_id, cl.merged_sparse(), G1GCPhaseTimes::MergeRSMergedSparse);

        p->record_or_add_thread_work_item(_merge_phase, worker_id, cl.merged_fine(), G1GCPhaseTimes::MergeRSMergedFine);

        p->record_or_add_thread_work_item(_merge_phase, worker_id, cl.merged_coarse(), G1GCPhaseTimes::MergeRSMergedCoarse);

      }

      // Apply closure to log entries in the HCC.

      if (!_remembered_set_only && G1HotCardCache::default_use_cache()) {

        assert(_merge_phase == G1GCPhaseTimes::MergeRS, "Wrong merge phase");

        G1GCParPhaseTimesTracker x(p, G1GCPhaseTimes::MergeHCC, worker_id);

        G1MergeLogBufferCardsClosure cl(g1h, _scan_state);

        g1h->iterate_hcc_closure(&cl, worker_id);

      }

      // Now apply the closure to all remaining log entries.

      if (!_remembered_set_only) {

        assert(_merge_phase == G1GCPhaseTimes::MergeRS, "Wrong merge phase");

        G1GCParPhaseTimesTracker x(p, G1GCPhaseTimes::MergeLB, worker_id);

        G1MergeLogBufferCardsClosure cl(g1h, _scan_state);

        g1h->iterate_dirty_card_closure(&cl, worker_id);

        p->record_thread_work_item(G1GCPhaseTimes::MergeLB, worker_id, cl.cards_dirty(), G1GCPhaseTimes::MergeLBDirtyCards);

        p->record_thread_work_item(G1GCPhaseTimes::MergeLB, worker_id, cl.cards_skipped(), G1GCPhaseTimes::MergeLBSkippedCards);

      }

    }

  };

  // Creates a snapshot of the current _top values at the start of collection to

  // filter out card marks that we do not want to scan.

  class G1ResetScanTopClosure : public HeapRegionClosure {

    G1RemSetScanState* _scan_state;

  public:

    G1ResetScanTopClosure(G1RemSetScanState* scan_state) : _scan_state(scan_state) { }

    virtual bool do_heap_region(HeapRegion* r) {

      uint hrm_index = r->hrm_index();

      if (r->in_collection_set()) {

        // Young regions had their card table marked as young at their allocation;

        // we need to make sure that these marks are cleared at the end of GC, *but*

        // they should not be scanned for cards.

        // So directly add them to the "all_dirty_regions".

        // Same for regions in the (initial) collection set: they may contain cards from

        // the log buffers, make sure they are cleaned.

        _scan_state->add_all_dirty_region(hrm_index);

       } else if (r->is_old_or_humongous_or_archive()) {

        _scan_state->set_scan_top(hrm_index, r->top());

       }

       return false;

     }

  };

  // For each region, contains the maximum top() value to be used during this garbage

  // collection. Subsumes common checks like filtering out everything but old and

  // humongous regions outside the collection set.

  // This is valid because we are not interested in scanning stray remembered set

  // entries from free or archive regions.

  HeapWord** _scan_top;

    G1DirtyRegions* _regions;

    uint _chunk_length;

    uint volatile _cur_dirty_regions;

    G1RemSetScanState* _scan_state;

                         G1DirtyRegions* regions,

                         uint chunk_length,

                         G1RemSetScanState* scan_state) :

      _regions(regions),

      _cur_dirty_regions(0),

      _scan_state(scan_state) {

    static uint chunk_size() { return M; }