/*

 * 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/_heapRegionRemSet.cpp.incl"

#define HRRS_VERBOSE 0

#define PRT_COUNT_OCCUPIED 1

// OtherRegionsTable

class PerRegionTable: public CHeapObj {

  friend class OtherRegionsTable;

  friend class HeapRegionRemSetIterator;

  HeapRegion*     _hr;

  BitMap          _bm;

#if PRT_COUNT_OCCUPIED

  jint            _occupied;

#endif

  PerRegionTable* _next_free;

  PerRegionTable* next_free() { return _next_free; }

  void set_next_free(PerRegionTable* prt) { _next_free = prt; }

  static PerRegionTable* _free_list;

#ifdef _MSC_VER

  // For some reason even though the classes are marked as friend they are unable

  // to access CardsPerRegion when private/protected. Only the windows c++ compiler

  // says this Sun CC and linux gcc don't have a problem with access when private

  public:

#endif // _MSC_VER

  enum SomePrivateConstants {

    CardsPerRegion = HeapRegion::GrainBytes >> CardTableModRefBS::card_shift

  };

protected:

  // We need access in order to union things into the base table.

  BitMap* bm() { return &_bm; }

  void recount_occupied() {

    _occupied = (jint) bm()->count_one_bits();

  }

  PerRegionTable(HeapRegion* hr) :

    _hr(hr),

#if PRT_COUNT_OCCUPIED

    _occupied(0),

#endif

    _bm(CardsPerRegion, false /* in-resource-area */)

  {}

  static void free(PerRegionTable* prt) {

    while (true) {

      PerRegionTable* fl = _free_list;

      prt->set_next_free(fl);

      PerRegionTable* res =

        (PerRegionTable*)

        Atomic::cmpxchg_ptr(prt, &_free_list, fl);

      if (res == fl) return;

    }

    ShouldNotReachHere();

  }

  static PerRegionTable* alloc(HeapRegion* hr) {

    PerRegionTable* fl = _free_list;

    while (fl != NULL) {

      PerRegionTable* nxt = fl->next_free();

      PerRegionTable* res =

        (PerRegionTable*)

        Atomic::cmpxchg_ptr(nxt, &_free_list, fl);

      if (res == fl) {

        fl->init(hr);

        return fl;

      } else {

        fl = _free_list;

      }

    }

    assert(fl == NULL, "Loop condition.");

    return new PerRegionTable(hr);

  }

  void add_card_work(short from_card, bool par) {

    if (!_bm.at(from_card)) {

      if (par) {

        if (_bm.par_at_put(from_card, 1)) {

#if PRT_COUNT_OCCUPIED

          Atomic::inc(&_occupied);

#endif

        }

      } else {

        _bm.at_put(from_card, 1);

#if PRT_COUNT_OCCUPIED

        _occupied++;

#endif

      }

    }

  }

  void add_reference_work(oop* from, bool par) {

    // Must make this robust in case "from" is not in "_hr", because of

    // concurrency.

#if HRRS_VERBOSE

    gclog_or_tty->print_cr("    PRT::Add_reference_work(" PTR_FORMAT "->" PTR_FORMAT").",

                           from, *from);

#endif

    HeapRegion* loc_hr = hr();

    // If the test below fails, then this table was reused concurrently

    // with this operation.  This is OK, since the old table was coarsened,

    // and adding a bit to the new table is never incorrect.

    if (loc_hr->is_in_reserved(from)) {

      size_t hw_offset = pointer_delta((HeapWord*)from, loc_hr->bottom());

      size_t from_card =

        hw_offset >>

        (CardTableModRefBS::card_shift - LogHeapWordSize);

      add_card_work((short) from_card, par);

    }

  }

public:

  HeapRegion* hr() const { return _hr; }

#if PRT_COUNT_OCCUPIED

  jint occupied() const {

    // Overkill, but if we ever need it...

    // guarantee(_occupied == _bm.count_one_bits(), "Check");

    return _occupied;

  }

#else

  jint occupied() const {

    return _bm.count_one_bits();

  }

#endif

  void init(HeapRegion* hr) {

    _hr = hr;

#if PRT_COUNT_OCCUPIED

    _occupied = 0;

#endif

    _bm.clear();

  }

  void add_reference(oop* from) {

    add_reference_work(from, /*parallel*/ true);

  }

  void seq_add_reference(oop* from) {

    add_reference_work(from, /*parallel*/ false);

  }

  void scrub(CardTableModRefBS* ctbs, BitMap* card_bm) {

    HeapWord* hr_bot = hr()->bottom();

    int hr_first_card_index = ctbs->index_for(hr_bot);

    bm()->set_intersection_at_offset(*card_bm, hr_first_card_index);

#if PRT_COUNT_OCCUPIED

    recount_occupied();

#endif

  }

  void add_card(short from_card_index) {

    add_card_work(from_card_index, /*parallel*/ true);

  }

  void seq_add_card(short from_card_index) {

    add_card_work(from_card_index, /*parallel*/ false);

  }

  // (Destructively) union the bitmap of the current table into the given

  // bitmap (which is assumed to be of the same size.)

  void union_bitmap_into(BitMap* bm) {

    bm->set_union(_bm);

  }

  // Mem size in bytes.

  size_t mem_size() const {

    return sizeof(this) + _bm.size_in_words() * HeapWordSize;

  }

  static size_t fl_mem_size() {

    PerRegionTable* cur = _free_list;

    size_t res = 0;

    while (cur != NULL) {

      res += sizeof(PerRegionTable);

      cur = cur->next_free();

    }

    return res;

  }

  // Requires "from" to be in "hr()".

  bool contains_reference(oop* from) const {

    assert(hr()->is_in_reserved(from), "Precondition.");

    size_t card_ind = pointer_delta(from, hr()->bottom(),

                                    CardTableModRefBS::card_size);

    return _bm.at(card_ind);

  }

};

PerRegionTable* PerRegionTable::_free_list = NULL;

#define COUNT_PAR_EXPANDS 0

#if COUNT_PAR_EXPANDS

static jint n_par_expands = 0;

static jint n_par_contracts = 0;

static jint par_expand_list_len = 0;

static jint max_par_expand_list_len = 0;

static void print_par_expand() {

  Atomic::inc(&n_par_expands);

  Atomic::inc(&par_expand_list_len);

  if (par_expand_list_len > max_par_expand_list_len) {

    max_par_expand_list_len = par_expand_list_len;

  }

  if ((n_par_expands % 10) == 0) {

    gclog_or_tty->print_cr("\n\n%d par expands: %d contracts, "

                  "len = %d, max_len = %d\n.",

                  n_par_expands, n_par_contracts, par_expand_list_len,

                  max_par_expand_list_len);

  }

}

#endif

class PosParPRT: public PerRegionTable {

  PerRegionTable** _par_tables;

  enum SomePrivateConstants {

    ReserveParTableExpansion = 1

  };

  void par_expand() {

    int n = HeapRegionRemSet::num_par_rem_sets()-1;

    if (n <= 0) return;

    if (_par_tables == NULL) {

      PerRegionTable* res =

        (PerRegionTable*)

        Atomic::cmpxchg_ptr((PerRegionTable*)ReserveParTableExpansion,

                            &_par_tables, NULL);

      if (res != NULL) return;

      // Otherwise, we reserved the right to do the expansion.

      PerRegionTable** ptables = NEW_C_HEAP_ARRAY(PerRegionTable*, n);

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

        PerRegionTable* ptable = PerRegionTable::alloc(hr());

        ptables[i] = ptable;

      }

      // Here we do not need an atomic.

      _par_tables = ptables;

#if COUNT_PAR_EXPANDS

      print_par_expand();

#endif

      // We must put this table on the expanded list.

      PosParPRT* exp_head = _par_expanded_list;

      while (true) {

        set_next_par_expanded(exp_head);

        PosParPRT* res =

          (PosParPRT*)

          Atomic::cmpxchg_ptr(this, &_par_expanded_list, exp_head);

        if (res == exp_head) return;

        // Otherwise.

        exp_head = res;

      }

      ShouldNotReachHere();

    }

  }

  void par_contract() {

    assert(_par_tables != NULL, "Precondition.");

    int n = HeapRegionRemSet::num_par_rem_sets()-1;

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

      _par_tables[i]->union_bitmap_into(bm());

      PerRegionTable::free(_par_tables[i]);

      _par_tables[i] = NULL;

    }

#if PRT_COUNT_OCCUPIED

    // We must recount the "occupied."

    recount_occupied();

#endif

    FREE_C_HEAP_ARRAY(PerRegionTable*, _par_tables);

    _par_tables = NULL;

#if COUNT_PAR_EXPANDS

    Atomic::inc(&n_par_contracts);

    Atomic::dec(&par_expand_list_len);

#endif

  }

  static PerRegionTable** _par_table_fl;

  PosParPRT* _next;

  static PosParPRT* _free_list;

  PerRegionTable** par_tables() const {

    assert(uintptr_t(NULL) == 0, "Assumption.");

    if (uintptr_t(_par_tables) <= ReserveParTableExpansion)

      return NULL;

    else

      return _par_tables;

  }

  PosParPRT* _next_par_expanded;

  PosParPRT* next_par_expanded() { return _next_par_expanded; }

  void set_next_par_expanded(PosParPRT* ppprt) { _next_par_expanded = ppprt; }

  static PosParPRT* _par_expanded_list;

public:

  PosParPRT(HeapRegion* hr) : PerRegionTable(hr), _par_tables(NULL) {}

  jint occupied() const {

    jint res = PerRegionTable::occupied();

    if (par_tables() != NULL) {

      for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets()-1; i++) {

        res += par_tables()[i]->occupied();

      }

    }

    return res;

  }

  void init(HeapRegion* hr) {

    PerRegionTable::init(hr);

    _next = NULL;

    if (par_tables() != NULL) {

      for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets()-1; i++) {

        par_tables()[i]->init(hr);

      }

    }

  }

  static void free(PosParPRT* prt) {

    while (true) {

      PosParPRT* fl = _free_list;

      prt->set_next(fl);

      PosParPRT* res =

        (PosParPRT*)

        Atomic::cmpxchg_ptr(prt, &_free_list, fl);

      if (res == fl) return;

    }

    ShouldNotReachHere();

  }

  static PosParPRT* alloc(HeapRegion* hr) {

    PosParPRT* fl = _free_list;

    while (fl != NULL) {

      PosParPRT* nxt = fl->next();

      PosParPRT* res =

        (PosParPRT*)

        Atomic::cmpxchg_ptr(nxt, &_free_list, fl);

      if (res == fl) {

        fl->init(hr);

        return fl;

      } else {

        fl = _free_list;

      }

    }

    assert(fl == NULL, "Loop condition.");

    return new PosParPRT(hr);

  }

  PosParPRT* next() const { return _next; }

  void set_next(PosParPRT* nxt) { _next = nxt; }

  PosParPRT** next_addr() { return &_next; }

  void add_reference(oop* from, int tid) {

    // Expand if necessary.

    PerRegionTable** pt = par_tables();

    if (par_tables() == NULL && tid > 0 && hr()->is_gc_alloc_region()) {

      par_expand();

      pt = par_tables();

    }

    if (pt != NULL) {

      // We always have to assume that mods to table 0 are in parallel,

      // because of the claiming scheme in parallel expansion.  A thread

      // with tid != 0 that finds the table to be NULL, but doesn't succeed

      // in claiming the right of expanding it, will end up in the else

      // clause of the above if test.  That thread could be delayed, and a

      // thread 0 add reference could see the table expanded, and come

      // here.  Both threads would be adding in parallel.  But we get to

      // not use atomics for tids > 0.

      if (tid == 0) {

        PerRegionTable::add_reference(from);

      } else {

        pt[tid-1]->seq_add_reference(from);

      }

    } else {

      // Not expanded -- add to the base table.

      PerRegionTable::add_reference(from);

    }

  }

  void scrub(CardTableModRefBS* ctbs, BitMap* card_bm) {

    assert(_par_tables == NULL, "Precondition");

    PerRegionTable::scrub(ctbs, card_bm);

  }

  size_t mem_size() const {

    size_t res =

      PerRegionTable::mem_size() + sizeof(this) - sizeof(PerRegionTable);

    if (_par_tables != NULL) {

      for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets()-1; i++) {

        res += _par_tables[i]->mem_size();

      }

    }

    return res;

  }

  static size_t fl_mem_size() {

    PosParPRT* cur = _free_list;

    size_t res = 0;

    while (cur != NULL) {

      res += sizeof(PosParPRT);

      cur = cur->next();

    }

    return res;

  }

  bool contains_reference(oop* from) const {

    if (PerRegionTable::contains_reference(from)) return true;

    if (_par_tables != NULL) {

      for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets()-1; i++) {

        if (_par_tables[i]->contains_reference(from)) return true;

      }

    }

    return false;

  }

  static void par_contract_all();

};

void PosParPRT::par_contract_all() {

  PosParPRT* hd = _par_expanded_list;

  while (hd != NULL) {

    PosParPRT* nxt = hd->next_par_expanded();

    PosParPRT* res =

      (PosParPRT*)

      Atomic::cmpxchg_ptr(nxt, &_par_expanded_list, hd);

    if (res == hd) {

      // We claimed the right to contract this table.

      hd->set_next_par_expanded(NULL);

      hd->par_contract();

      hd = _par_expanded_list;

    } else {

      hd = res;

    }

  }

}

PosParPRT* PosParPRT::_free_list = NULL;

PosParPRT* PosParPRT::_par_expanded_list = NULL;

jint OtherRegionsTable::_cache_probes = 0;

jint OtherRegionsTable::_cache_hits = 0;

size_t OtherRegionsTable::_max_fine_entries = 0;

size_t OtherRegionsTable::_mod_max_fine_entries_mask = 0;

#if SAMPLE_FOR_EVICTION

size_t OtherRegionsTable::_fine_eviction_stride = 0;

size_t OtherRegionsTable::_fine_eviction_sample_size = 0;

#endif

OtherRegionsTable::OtherRegionsTable(HeapRegion* hr) :

  _g1h(G1CollectedHeap::heap()),

  _m(Mutex::leaf, "An OtherRegionsTable lock", true),

  _hr(hr),

  _coarse_map(G1CollectedHeap::heap()->max_regions(),

              false /* in-resource-area */),

  _fine_grain_regions(NULL),

  _n_fine_entries(0), _n_coarse_entries(0),

#if SAMPLE_FOR_EVICTION

  _fine_eviction_start(0),

#endif

  _sparse_table(hr)

{

  typedef PosParPRT* PosParPRTPtr;

  if (_max_fine_entries == 0) {

    assert(_mod_max_fine_entries_mask == 0, "Both or none.");

    _max_fine_entries = (1 << G1LogRSRegionEntries);

    _mod_max_fine_entries_mask = _max_fine_entries - 1;

#if SAMPLE_FOR_EVICTION

    assert(_fine_eviction_sample_size == 0

           && _fine_eviction_stride == 0, "All init at same time.");

    _fine_eviction_sample_size = MAX2((size_t)4, (size_t)G1LogRSRegionEntries);

    _fine_eviction_stride = _max_fine_entries / _fine_eviction_sample_size;

#endif

  }

  _fine_grain_regions = new PosParPRTPtr[_max_fine_entries];

  if (_fine_grain_regions == NULL)

    vm_exit_out_of_memory(sizeof(void*)*_max_fine_entries,

                          "Failed to allocate _fine_grain_entries.");

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

    _fine_grain_regions[i] = NULL;

  }

}

int** OtherRegionsTable::_from_card_cache = NULL;

size_t OtherRegionsTable::_from_card_cache_max_regions = 0;

size_t OtherRegionsTable::_from_card_cache_mem_size = 0;