#include "gc/g1/g1CardTableEntryClosure.hpp"

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

#include "gc/g1/sparsePRT.hpp"

#include "gc/shared/ptrQueue.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;

  // Return "optimal" number of chunks per region we want to use for claiming areas

  // within a region to claim. Dependent on the region size as proxy for the heap

  // size, we limit the total number of chunks to limit memory usage and maintenance

  // effort of that table vs. granularity of distributing scanning work.

  // Testing showed that 8 for 1M/2M region, 16 for 4M/8M regions, 32 for 16/32M regions

  // seems to be such a good trade-off.

  static uint get_chunks_per_region(uint log_region_size) {

    // Limit the expected input values to current known possible values of the

    // (log) region size. Adjust as necessary after testing if changing the permissible

    // values for region size.

    assert(log_region_size >= 20 && log_region_size <= 25,

           "expected value in [20,25], but got %u", log_region_size);

    return 1u << (log_region_size / 2 - 7);

  }

  uint _scan_chunks_per_region;         // Number of chunks per region.

  uint8_t _log_scan_chunks_per_region;  // Log of number of chunks per region.

  bool* _region_scan_chunks;

  size_t _num_total_scan_chunks;        // Total number of elements in _region_scan_chunks.

  uint8_t _scan_chunks_shift;           // For conversion between card index and chunk index.

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 << _log_scan_chunks_per_region) + (card_in_region >> _scan_chunks_shift);

    assert(idx < _num_total_scan_chunks, "Index " SIZE_FORMAT " out of bounds " SIZE_FORMAT,

           idx, _num_total_scan_chunks);

    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;

        }

      }

    }

  };

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

      while (_cur_dirty_regions < _regions->size()) {

        uint next = Atomic::add(_chunk_length, &_cur_dirty_regions) - _chunk_length;

        uint max = MIN2(next + _chunk_length, _regions->size());

        for (uint i = next; i < max; i++) {

          HeapRegion* r = _g1h->region_at(_regions->at(i));

  // Clear the card table of "dirty" regions.

  void clear_card_table(WorkGang* workers) {

    uint num_regions = _all_dirty_regions->size();

    if (num_regions == 0) {

      return;

    }

    uint const num_chunks = (uint)(align_up((size_t)num_regions << HeapRegion::LogCardsPerRegion, G1ClearCardTableTask::chunk_size()) / G1ClearCardTableTask::chunk_size());

    uint const num_workers = MIN2(num_chunks, workers->active_workers());

    uint const chunk_length = G1ClearCardTableTask::chunk_size() / (uint)HeapRegion::CardsPerRegion;

    // Iterate over the dirty cards region list.

    G1ClearCardTableTask cl(G1CollectedHeap::heap(), _all_dirty_regions, chunk_length, this);

    log_debug(gc, ergo)("Running %s using %u workers for %u "

                        "units of work for %u regions.",

                        cl.name(), num_workers, num_chunks, num_regions);

    workers->run_task(&cl, num_workers);

#ifndef PRODUCT

    G1CollectedHeap::heap()->verifier()->verify_card_table_cleanup();

#endif

  }

    _collection_set_iter_state(NULL),

    _card_table_scan_state(NULL),

    _scan_chunks_per_region(get_chunks_per_region(HeapRegion::LogOfHRGrainBytes)),

    _log_scan_chunks_per_region(log2_uint(_scan_chunks_per_region)),

    _region_scan_chunks(NULL),

    _num_total_scan_chunks(0),

    _scan_chunks_shift(0),

    _all_dirty_regions(NULL),

    _next_dirty_regions(NULL),

    FREE_C_HEAP_ARRAY(G1RemsetIterState, _collection_set_iter_state);

    FREE_C_HEAP_ARRAY(uint, _card_table_scan_state);

    FREE_C_HEAP_ARRAY(bool, _region_scan_chunks);

    FREE_C_HEAP_ARRAY(HeapWord*, _scan_top);

  void initialize(size_t max_regions) {

    assert(_collection_set_iter_state == NULL, "Must not be initialized twice");

    _collection_set_iter_state = NEW_C_HEAP_ARRAY(G1RemsetIterState, max_regions, mtGC);

    _card_table_scan_state = NEW_C_HEAP_ARRAY(uint, max_regions, mtGC);

    _num_total_scan_chunks = max_regions * _scan_chunks_per_region;

    _region_scan_chunks = NEW_C_HEAP_ARRAY(bool, _num_total_scan_chunks, mtGC);

    _scan_chunks_shift = (uint8_t)log2_intptr(HeapRegion::CardsPerRegion / _scan_chunks_per_region);

  void prepare() {

    for (size_t i = 0; i < _max_regions; i++) {

      _collection_set_iter_state[i] = false;

      clear_scan_top((uint)i);

    _all_dirty_regions = new G1DirtyRegions(_max_regions);

    _next_dirty_regions = new G1DirtyRegions(_max_regions);

    G1ResetScanTopClosure cl(this);

    G1CollectedHeap::heap()->heap_region_iterate(&cl);

  void prepare_for_merge_heap_roots() {

    _all_dirty_regions->merge(_next_dirty_regions);

    _next_dirty_regions->reset();

    for (size_t i = 0; i < _max_regions; i++) {

      _card_table_scan_state[i] = 0;

    ::memset(_region_scan_chunks, false, _num_total_scan_chunks * sizeof(*_region_scan_chunks));

  }

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

  size_t num_visited_cards() const {

    size_t result = 0;

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

      if (_region_scan_chunks[i]) {

        result++;

      }

    return result * (HeapRegion::CardsPerRegion / _scan_chunks_per_region);

  }

  size_t num_cards_in_dirty_regions() const {

    return _next_dirty_regions->size() * HeapRegion::CardsPerRegion;

  }

  void set_chunk_region_dirty(size_t const region_card_idx) {

    size_t chunk_idx = region_card_idx >> _scan_chunks_shift;

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

      _region_scan_chunks[chunk_idx++] = true;

    }

  void set_chunk_dirty(size_t const card_idx) {

    assert((card_idx >> _scan_chunks_shift) < _num_total_scan_chunks,

           "Trying to access index " SIZE_FORMAT " out of bounds " SIZE_FORMAT,

           card_idx >> _scan_chunks_shift, _num_total_scan_chunks);

    size_t const chunk_idx = card_idx >> _scan_chunks_shift;

    if (!_region_scan_chunks[chunk_idx]) {

      _region_scan_chunks[chunk_idx] = true;

    }

  void cleanup(WorkGang* workers) {

    _all_dirty_regions->merge(_next_dirty_regions);

    clear_card_table(workers);

    delete _all_dirty_regions;

    _all_dirty_regions = NULL;

    delete _next_dirty_regions;

    _next_dirty_regions = NULL;

  void iterate_dirty_regions_from(HeapRegionClosure* cl, uint worker_id) {

    uint num_regions = _next_dirty_regions->size();

    if (num_regions == 0) {

    G1CollectedHeap* g1h = G1CollectedHeap::heap();

    WorkGang* workers = g1h->workers();

    uint const max_workers = workers->active_workers();

    uint const start_pos = num_regions * worker_id / max_workers;

    uint cur = start_pos;

    do {

      bool result = cl->do_heap_region(g1h->region_at(_next_dirty_regions->at(cur)));

      guarantee(!result, "Not allowed to ask for early termination.");

      cur++;

      if (cur == _next_dirty_regions->size()) {

        cur = 0;

      }

    } while (cur != start_pos);

  }

  // Attempt to claim the given region in the collection set for iteration. Returns true

  // if this call caused the transition from Unclaimed to Claimed.

  inline bool claim_collection_set_region(uint region) {

    assert(region < _max_regions, "Tried to access invalid region %u", region);

    if (_collection_set_iter_state[region]) {

      return false;

    return !Atomic::cmpxchg(true, &_collection_set_iter_state[region], false);

  }

  bool has_cards_to_scan(uint region) {

    assert(region < _max_regions, "Tried to access invalid region %u", region);

    return _card_table_scan_state[region] < HeapRegion::CardsPerRegion;

  }

  uint claim_cards_to_scan(uint region, uint increment) {

    assert(region < _max_regions, "Tried to access invalid region %u", region);

    return Atomic::add(increment, &_card_table_scan_state[region]) - increment;

  }

  void add_dirty_region(uint const region) {

#ifdef ASSERT

   HeapRegion* hr = G1CollectedHeap::heap()->region_at(region);

   assert(!hr->in_collection_set() && hr->is_old_or_humongous_or_archive(),

          "Region %u is not suitable for scanning, is %sin collection set or %s",

          hr->hrm_index(), hr->in_collection_set() ? "" : "not ", hr->get_short_type_str());

#endif

    _next_dirty_regions->add_dirty_region(region);

  }

  void add_all_dirty_region(uint region) {

#ifdef ASSERT

    HeapRegion* hr = G1CollectedHeap::heap()->region_at(region);

    assert(hr->in_collection_set(),

           "Only add young regions to all dirty regions directly but %u is %s",

           hr->hrm_index(), hr->get_short_type_str());

#endif

    _all_dirty_regions->add_dirty_region(region);

  }

  void set_scan_top(uint region_idx, HeapWord* value) {

    _scan_top[region_idx] = value;

    set_scan_top(region_idx, NULL);