/*
 * Copyright (c) 2021, 2024, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "precompiled.hpp"
#include "gc/g1/g1CardSet.inline.hpp"
#include "gc/g1/g1CardSetContainers.inline.hpp"
#include "gc/g1/g1CardSetMemory.inline.hpp"
#include "gc/g1/heapRegion.inline.hpp"
#include "gc/shared/gcLogPrecious.hpp"
#include "gc/shared/gcTraceTime.inline.hpp"
#include "memory/allocation.inline.hpp"
#include "runtime/atomic.hpp"
#include "runtime/globals_extension.hpp"
#include "runtime/java.hpp"
#include "utilities/bitMap.inline.hpp"
#include "utilities/concurrentHashTable.inline.hpp"
#include "utilities/concurrentHashTableTasks.inline.hpp"
#include "utilities/globalDefinitions.hpp"

G1CardSet::ContainerPtr G1CardSet::FullCardSet = (G1CardSet::ContainerPtr)-1;
uint G1CardSet::_split_card_shift = 0;
size_t G1CardSet::_split_card_mask = 0;

class G1CardSetHashTableConfig : public StackObj {
public:
  using Value = G1CardSetHashTableValue;

  static uintx get_hash(Value const& value, bool* is_dead);
  static void* allocate_node(void* context, size_t size, Value const& value);
  static void free_node(void* context, void* memory, Value const& value);
};

using CardSetHash = ConcurrentHashTable<G1CardSetHashTableConfig, mtGCCardSet>;

static uint default_log2_card_regions_per_region() {
  uint log2_card_regions_per_heap_region = 0;

  const uint card_container_limit = G1CardSetContainer::LogCardsPerRegionLimit;
  if (card_container_limit < (uint)HeapRegion::LogCardsPerRegion) {
    log2_card_regions_per_heap_region = (uint)HeapRegion::LogCardsPerRegion - card_container_limit;
  }

  return log2_card_regions_per_heap_region;
}

G1CardSetConfiguration::G1CardSetConfiguration() :
  G1CardSetConfiguration(HeapRegion::LogCardsPerRegion - default_log2_card_regions_per_region(),                                                                                   /* inline_ptr_bits_per_card */
                         G1RemSetArrayOfCardsEntries,                               /* max_cards_in_array */
                         (double)G1RemSetCoarsenHowlBitmapToHowlFullPercent / 100,  /* cards_in_bitmap_threshold_percent */
                         G1RemSetHowlNumBuckets,                                    /* num_buckets_in_howl */
                         (double)G1RemSetCoarsenHowlToFullPercent / 100,            /* cards_in_howl_threshold_percent */
                         (uint)HeapRegion::CardsPerRegion >> default_log2_card_regions_per_region(),
                                                                                    /* max_cards_in_card_set */
                         default_log2_card_regions_per_region())                    /* log2_card_regions_per_region */
{
  assert((_log2_card_regions_per_heap_region + _log2_cards_per_card_region) == (uint)HeapRegion::LogCardsPerRegion,
         "inconsistent heap region virtualization setup");
}

G1CardSetConfiguration::G1CardSetConfiguration(uint max_cards_in_array,
                                               double cards_in_bitmap_threshold_percent,
                                               uint max_buckets_in_howl,
                                               double cards_in_howl_threshold_percent,
                                               uint max_cards_in_card_set,
                                               uint log2_card_regions_per_region) :
  G1CardSetConfiguration(log2i_exact(max_cards_in_card_set),                   /* inline_ptr_bits_per_card */
                         max_cards_in_array,                                   /* max_cards_in_array */
                         cards_in_bitmap_threshold_percent,                    /* cards_in_bitmap_threshold_percent */
                         G1CardSetHowl::num_buckets(max_cards_in_card_set,     /* num_buckets_in_howl */
                                                    max_cards_in_array,
                                                    max_buckets_in_howl),
                         cards_in_howl_threshold_percent,                      /* cards_in_howl_threshold_percent */
                         max_cards_in_card_set,                                /* max_cards_in_card_set */
                         log2_card_regions_per_region)
{ }

G1CardSetConfiguration::G1CardSetConfiguration(uint inline_ptr_bits_per_card,
                                               uint max_cards_in_array,
                                               double cards_in_bitmap_threshold_percent,
                                               uint num_buckets_in_howl,
                                               double cards_in_howl_threshold_percent,
                                               uint max_cards_in_card_set,
                                               uint log2_card_regions_per_heap_region) :
  _inline_ptr_bits_per_card(inline_ptr_bits_per_card),
  _max_cards_in_array(max_cards_in_array),
  _num_buckets_in_howl(num_buckets_in_howl),
  _max_cards_in_card_set(max_cards_in_card_set),
  _cards_in_howl_threshold(max_cards_in_card_set * cards_in_howl_threshold_percent),
  _max_cards_in_howl_bitmap(G1CardSetHowl::bitmap_size(_max_cards_in_card_set, _num_buckets_in_howl)),
  _cards_in_howl_bitmap_threshold(_max_cards_in_howl_bitmap * cards_in_bitmap_threshold_percent),
  _log2_max_cards_in_howl_bitmap(log2i_exact(_max_cards_in_howl_bitmap)),
  _bitmap_hash_mask(~(~(0) << _log2_max_cards_in_howl_bitmap)),
  _log2_card_regions_per_heap_region(log2_card_regions_per_heap_region),
  _log2_cards_per_card_region(log2i_exact(_max_cards_in_card_set)) {

  assert(_inline_ptr_bits_per_card <= G1CardSetContainer::LogCardsPerRegionLimit,
         "inline_ptr_bits_per_card (%u) is wasteful, can represent more than maximum possible card indexes (%u)",
         _inline_ptr_bits_per_card, G1CardSetContainer::LogCardsPerRegionLimit);
  assert(_inline_ptr_bits_per_card >= _log2_cards_per_card_region,
         "inline_ptr_bits_per_card (%u) must be larger than possible card indexes (%u)",
         _inline_ptr_bits_per_card, _log2_cards_per_card_region);

  assert(cards_in_bitmap_threshold_percent >= 0.0 && cards_in_bitmap_threshold_percent <= 1.0,
         "cards_in_bitmap_threshold_percent (%1.2f) out of range", cards_in_bitmap_threshold_percent);

  assert(cards_in_howl_threshold_percent >= 0.0 && cards_in_howl_threshold_percent <= 1.0,
         "cards_in_howl_threshold_percent (%1.2f) out of range", cards_in_howl_threshold_percent);

  assert(is_power_of_2(_max_cards_in_card_set),
         "max_cards_in_card_set must be a power of 2: %u", _max_cards_in_card_set);
  assert(_max_cards_in_card_set <= G1CardSetContainer::cards_per_region_limit(),
         "Specified number of cards (%u) exceeds maximum representable (%u)",
         _max_cards_in_card_set, G1CardSetContainer::cards_per_region_limit());

  assert(_cards_in_howl_bitmap_threshold <= _max_cards_in_howl_bitmap,
         "Threshold to coarsen Howl Bitmap to Howl Full (%u) must be "
         "smaller than or equal to max number of cards in Howl bitmap (%u)",
         _cards_in_howl_bitmap_threshold, _max_cards_in_howl_bitmap);
  assert(_cards_in_howl_threshold <= _max_cards_in_card_set,
         "Threshold to coarsen Howl to Full (%u) must be "
         "smaller than or equal to max number of cards in card region (%u)",
         _cards_in_howl_threshold, _max_cards_in_card_set);

  init_card_set_alloc_options();
  log_configuration();
}

G1CardSetConfiguration::~G1CardSetConfiguration() {
  FREE_C_HEAP_ARRAY(size_t, _card_set_alloc_options);
}

void G1CardSetConfiguration::init_card_set_alloc_options() {
  _card_set_alloc_options = NEW_C_HEAP_ARRAY(G1CardSetAllocOptions, num_mem_object_types(), mtGC);
  new (&_card_set_alloc_options[0]) G1CardSetAllocOptions((uint)CardSetHash::get_node_size());
  new (&_card_set_alloc_options[1]) G1CardSetAllocOptions((uint)G1CardSetArray::size_in_bytes(_max_cards_in_array), 2, 256);
  new (&_card_set_alloc_options[2]) G1CardSetAllocOptions((uint)G1CardSetBitMap::size_in_bytes(_max_cards_in_howl_bitmap), 2, 256);
  new (&_card_set_alloc_options[3]) G1CardSetAllocOptions((uint)G1CardSetHowl::size_in_bytes(_num_buckets_in_howl), 2, 256);
}

void G1CardSetConfiguration::log_configuration() {
  log_debug_p(gc, remset)("Card Set container configuration: "
                          "InlinePtr #cards %u size %zu "
                          "Array Of Cards #cards %u size %zu "
                          "Howl #buckets %u coarsen threshold %u "
                          "Howl Bitmap #cards %u size %zu coarsen threshold %u "
                          "Card regions per heap region %u cards per card region %u",
                          max_cards_in_inline_ptr(), sizeof(void*),
                          max_cards_in_array(), G1CardSetArray::size_in_bytes(max_cards_in_array()),
                          num_buckets_in_howl(), cards_in_howl_threshold(),
                          max_cards_in_howl_bitmap(), G1CardSetBitMap::size_in_bytes(max_cards_in_howl_bitmap()), cards_in_howl_bitmap_threshold(),
                          (uint)1 << log2_card_regions_per_heap_region(),
                          max_cards_in_region());
}

uint G1CardSetConfiguration::max_cards_in_inline_ptr() const {
  return max_cards_in_inline_ptr(_inline_ptr_bits_per_card);
}

uint G1CardSetConfiguration::max_cards_in_inline_ptr(uint bits_per_card) {
  return G1CardSetInlinePtr::max_cards_in_inline_ptr(bits_per_card);
}

const G1CardSetAllocOptions* G1CardSetConfiguration::mem_object_alloc_options(uint idx) {
  return &_card_set_alloc_options[idx];
}

const char* G1CardSetConfiguration::mem_object_type_name_str(uint index) {
  const char* names[] = { "Node", "Array", "Bitmap", "Howl" };
  return names[index];
}

void G1CardSetCoarsenStats::reset() {
  STATIC_ASSERT(ARRAY_SIZE(_coarsen_from) == ARRAY_SIZE(_coarsen_collision));
  for (uint i = 0; i < ARRAY_SIZE(_coarsen_from); i++) {
    _coarsen_from[i] = 0;
    _coarsen_collision[i] = 0;
  }
}

void G1CardSetCoarsenStats::set(G1CardSetCoarsenStats& other) {
  STATIC_ASSERT(ARRAY_SIZE(_coarsen_from) == ARRAY_SIZE(_coarsen_collision));
  for (uint i = 0; i < ARRAY_SIZE(_coarsen_from); i++) {
    _coarsen_from[i] = other._coarsen_from[i];
    _coarsen_collision[i] = other._coarsen_collision[i];
  }
}

void G1CardSetCoarsenStats::subtract_from(G1CardSetCoarsenStats& other) {
  STATIC_ASSERT(ARRAY_SIZE(_coarsen_from) == ARRAY_SIZE(_coarsen_collision));
  for (uint i = 0; i < ARRAY_SIZE(_coarsen_from); i++) {
    _coarsen_from[i] = other._coarsen_from[i] - _coarsen_from[i];
    _coarsen_collision[i] = other._coarsen_collision[i] - _coarsen_collision[i];
  }
}

void G1CardSetCoarsenStats::record_coarsening(uint tag, bool collision) {
  assert(tag < ARRAY_SIZE(_coarsen_from), "tag %u out of bounds", tag);
  Atomic::inc(&_coarsen_from[tag], memory_order_relaxed);
  if (collision) {
    Atomic::inc(&_coarsen_collision[tag], memory_order_relaxed);
  }
}

void G1CardSetCoarsenStats::print_on(outputStream* out) {
  out->print_cr("Inline->AoC %zu (%zu) "
                "AoC->Howl %zu (%zu) "
                "Howl->Full %zu (%zu) "
                "Inline->AoC %zu (%zu) "
                "AoC->BitMap %zu (%zu) "
                "BitMap->Full %zu (%zu) ",
                _coarsen_from[0], _coarsen_collision[0],
                _coarsen_from[1], _coarsen_collision[1],
                // There is no BitMap at the first level so we can't .
                _coarsen_from[3], _coarsen_collision[3],
                _coarsen_from[4], _coarsen_collision[4],
                _coarsen_from[5], _coarsen_collision[5],
                _coarsen_from[6], _coarsen_collision[6]
               );
}

class G1CardSetHashTable : public CHeapObj<mtGCCardSet> {
  using ContainerPtr = G1CardSet::ContainerPtr;
  using CHTScanTask = CardSetHash::ScanTask;

  const static uint BucketClaimSize = 16;
  // Did we insert at least one card in the table?
  bool volatile _inserted_card;

  G1CardSetMemoryManager* _mm;
  CardSetHash _table;
  CHTScanTask _table_scanner;

  class G1CardSetHashTableLookUp : public StackObj {
    uint _region_idx;
  public:
    explicit G1CardSetHashTableLookUp(uint region_idx) : _region_idx(region_idx) { }

    uintx get_hash() const { return G1CardSetHashTable::get_hash(_region_idx); }

    bool equals(G1CardSetHashTableValue* value) {
      return value->_region_idx == _region_idx;
    }

    bool is_dead(G1CardSetHashTableValue*) {
      return false;
    }
  };

  class G1CardSetHashTableFound : public StackObj {
    G1CardSetHashTableValue* _value;
  public:
    G1CardSetHashTableFound() : _value(nullptr) { }

    void operator()(G1CardSetHashTableValue* value) {
      _value = value;
    }

    G1CardSetHashTableValue* value() const { return _value; }
  };

public:
  static const size_t InitialLogTableSize = 2;

  G1CardSetHashTable(G1CardSetMemoryManager* mm,
                     size_t initial_log_table_size = InitialLogTableSize) :
    _inserted_card(false),
    _mm(mm),
    _table(Mutex::service-1,
           mm,
           initial_log_table_size,
           false /* enable_statistics */),
    _table_scanner(&_table, BucketClaimSize) {
  }

  ~G1CardSetHashTable() {
    reset();
  }

  G1CardSetHashTableValue* get_or_add(uint region_idx, bool* should_grow) {
    G1CardSetHashTableLookUp lookup(region_idx);
    G1CardSetHashTableFound found;

    if (_table.get(Thread::current(), lookup, found)) {
      return found.value();
    }

    G1CardSetHashTableValue value(region_idx, G1CardSetInlinePtr());
    bool inserted = _table.insert_get(Thread::current(), lookup, value, found, should_grow);

    if (!_inserted_card && inserted) {
      // It does not matter to us who is setting the flag so a regular atomic store
      // is sufficient.
      Atomic::store(&_inserted_card, true);
    }

    return found.value();
  }

  static uint get_hash(uint region_idx) {
    return region_idx;
  }

  G1CardSetHashTableValue* get(uint region_idx) {
    G1CardSetHashTableLookUp lookup(region_idx);
    G1CardSetHashTableFound found;

    _table.get(Thread::current(), lookup, found);
    return found.value();
  }

  template <typename SCAN_FUNC>
  void iterate_safepoint(SCAN_FUNC& scan_f) {
    _table_scanner.do_safepoint_scan(scan_f);
  }

  template <typename SCAN_FUNC>
  void iterate(SCAN_FUNC& scan_f) {
    _table.do_scan(Thread::current(), scan_f);
  }

  void reset() {
    if (Atomic::load(&_inserted_card)) {
      _table.unsafe_reset(InitialLogTableSize);
      Atomic::store(&_inserted_card, false);
    }
  }

  void reset_table_scanner() {
    _table_scanner.set(&_table, BucketClaimSize);
  }

  void grow() {
    size_t new_limit = _table.get_size_log2(Thread::current()) + 1;
    _table.grow(Thread::current(), new_limit);
  }

  size_t mem_size() {
    return sizeof(*this) +
      _table.get_mem_size(Thread::current()) - sizeof(_table);
  }

  size_t log_table_size() { return _table.get_size_log2(Thread::current()); }
};

uintx G1CardSetHashTableConfig::get_hash(Value const& value, bool* is_dead) {
  *is_dead = false;
  return G1CardSetHashTable::get_hash(value._region_idx);
}

void* G1CardSetHashTableConfig::allocate_node(void* context, size_t size, Value const& value) {
  G1CardSetMemoryManager* mm = (G1CardSetMemoryManager*)context;
  return mm->allocate_node();
}

void G1CardSetHashTableConfig::free_node(void* context, void* memory, Value const& value) {
  G1CardSetMemoryManager* mm = (G1CardSetMemoryManager*)context;
  mm->free_node(memory);
}

G1CardSetCoarsenStats G1CardSet::_coarsen_stats;
G1CardSetCoarsenStats G1CardSet::_last_coarsen_stats;

G1CardSet::G1CardSet(G1CardSetConfiguration* config, G1CardSetMemoryManager* mm) :
  _mm(mm),
  _config(config),
  _table(new G1CardSetHashTable(mm)),
  _num_occupied(0) {
}

G1CardSet::~G1CardSet() {
  delete _table;
  _mm->flush();
}

void G1CardSet::initialize(MemRegion reserved) {
  const uint BitsInUint = sizeof(uint) * BitsPerByte;
  const uint CardBitsWithinCardRegion = MIN2((uint)HeapRegion::LogCardsPerRegion, G1CardSetContainer::LogCardsPerRegionLimit);

  // Check if the number of cards within a region fits an uint.
  if (CardBitsWithinCardRegion > BitsInUint) {
    vm_exit_during_initialization("Can not represent all cards in a card region within uint.");
  }

  _split_card_shift = CardBitsWithinCardRegion;
  _split_card_mask = ((size_t)1 << _split_card_shift) - 1;

  // Check if the card region/region within cards combination can cover the heap.
  const uint HeapSizeBits = log2i_exact(round_up_power_of_2(reserved.byte_size()));
  if (HeapSizeBits > (BitsInUint + _split_card_shift + G1CardTable::card_shift())) {
    FormatBuffer<> fmt("Can not represent all cards in the heap with card region/card within region. "
                       "Heap %zuB (%u bits) Card set only covers %u bits.",
                       reserved.byte_size(),
                       HeapSizeBits,
                       BitsInUint + _split_card_shift + G1CardTable::card_shift());
    vm_exit_during_initialization(fmt, "Decrease heap size.");
  }
}

uint G1CardSet::container_type_to_mem_object_type(uintptr_t type) const {
  assert(type == G1CardSet::ContainerArrayOfCards ||
         type == G1CardSet::ContainerBitMap ||
         type == G1CardSet::ContainerHowl, "should not allocate container type %zu", type);

  return (uint)type;
}

uint8_t* G1CardSet::allocate_mem_object(uintptr_t type) {
  return _mm->allocate(container_type_to_mem_object_type(type));
}

void G1CardSet::free_mem_object(ContainerPtr container) {
  assert(container != G1CardSet::FreeCardSet, "should not free container FreeCardSet");
  assert(container != G1CardSet::FullCardSet, "should not free container FullCardSet");

  uintptr_t type = container_type(container);
  void* value = strip_container_type(container);

  assert(type == G1CardSet::ContainerArrayOfCards ||
         type == G1CardSet::ContainerBitMap ||
         type == G1CardSet::ContainerHowl, "should not free card set type %zu", type);
  assert(static_cast<G1CardSetContainer*>(value)->refcount() == 1, "must be");

  _mm->free(container_type_to_mem_object_type(type), value);
}

G1CardSet::ContainerPtr G1CardSet::acquire_container(ContainerPtr volatile* container_addr) {
  // Update reference counts under RCU critical section to avoid a
  // use-after-cleapup bug where we increment a reference count for
  // an object whose memory has already been cleaned up and reused.
  GlobalCounter::CriticalSection cs(Thread::current());
  while (true) {
    // Get ContainerPtr and increment refcount atomically wrt to memory reuse.
    ContainerPtr container = Atomic::load_acquire(container_addr);
    uint cs_type = container_type(container);
    if (container == FullCardSet || cs_type == ContainerInlinePtr) {
      return container;
    }

    G1CardSetContainer* container_on_heap = (G1CardSetContainer*)strip_container_type(container);

    if (container_on_heap->try_increment_refcount()) {
      assert(container_on_heap->refcount() >= 3, "Smallest value is 3");
      return container;
    }
  }
}

bool G1CardSet::release_container(ContainerPtr container) {
  uint cs_type = container_type(container);
  if (container == FullCardSet || cs_type == ContainerInlinePtr) {
    return false;
  }

  G1CardSetContainer* container_on_heap = (G1CardSetContainer*)strip_container_type(container);
  return container_on_heap->decrement_refcount() == 1;
}

void G1CardSet::release_and_maybe_free_container(ContainerPtr container) {
  if (release_container(container)) {
    free_mem_object(container);
  }
}

void G1CardSet::release_and_must_free_container(ContainerPtr container) {
  bool should_free = release_container(container);
  assert(should_free, "should have been the only one having a reference");
  free_mem_object(container);
}

class G1ReleaseCardsets : public StackObj {
  G1CardSet* _card_set;
  using ContainerPtr = G1CardSet::ContainerPtr;

  void coarsen_to_full(ContainerPtr* container_addr) {
    while (true) {
      ContainerPtr cur_container = Atomic::load_acquire(container_addr);
      uint cs_type = G1CardSet::container_type(cur_container);
      if (cur_container == G1CardSet::FullCardSet) {
        return;
      }

      ContainerPtr old_value = Atomic::cmpxchg(container_addr, cur_container, G1CardSet::FullCardSet);

      if (old_value == cur_container) {
        _card_set->release_and_maybe_free_container(cur_container);
        return;
      }
    }
  }

public:
  explicit G1ReleaseCardsets(G1CardSet* card_set) : _card_set(card_set) { }

  void operator ()(ContainerPtr* container_addr) {
    coarsen_to_full(container_addr);
  }
};

G1AddCardResult G1CardSet::add_to_array(ContainerPtr container, uint card_in_region) {
  G1CardSetArray* array = container_ptr<G1CardSetArray>(container);
  return array->add(card_in_region);
}

G1AddCardResult G1CardSet::add_to_howl(ContainerPtr parent_container,
                                       uint card_region,
                                       uint card_in_region,
                                       bool increment_total) {
  G1CardSetHowl* howl = container_ptr<G1CardSetHowl>(parent_container);

  G1AddCardResult add_result;
  ContainerPtr to_transfer = nullptr;
  ContainerPtr container;

  uint bucket = _config->howl_bucket_index(card_in_region);
  ContainerPtr volatile* bucket_entry = howl->get_container_addr(bucket);

  while (true) {
    if (Atomic::load(&howl->_num_entries) >= _config->cards_in_howl_threshold()) {
      return Overflow;
    }

    container = acquire_container(bucket_entry);
    add_result = add_to_container(bucket_entry, container, card_region, card_in_region);

    if (add_result != Overflow) {
      break;
    }
    // Card set container has overflown. Coarsen or retry.
    bool coarsened = coarsen_container(bucket_entry, container, card_in_region, true /* within_howl */);
    _coarsen_stats.record_coarsening(container_type(container) + G1CardSetCoarsenStats::CoarsenHowlOffset, !coarsened);
    if (coarsened) {
      // We successful coarsened this card set container (and in the process added the card).
      add_result = Added;
      to_transfer = container;
      break;
    }
    // Somebody else beat us to coarsening. Retry.
    release_and_maybe_free_container(container);
  }

  if (increment_total && add_result == Added) {
    Atomic::inc(&howl->_num_entries, memory_order_relaxed);
  }

  if (to_transfer != nullptr) {
    transfer_cards_in_howl(parent_container, to_transfer, card_region);
  }

  release_and_maybe_free_container(container);
  return add_result;
}

G1AddCardResult G1CardSet::add_to_bitmap(ContainerPtr container, uint card_in_region) {
  G1CardSetBitMap* bitmap = container_ptr<G1CardSetBitMap>(container);
  uint card_offset = _config->howl_bitmap_offset(card_in_region);
  return bitmap->add(card_offset, _config->cards_in_howl_bitmap_threshold(), _config->max_cards_in_howl_bitmap());
}

G1AddCardResult G1CardSet::add_to_inline_ptr(ContainerPtr volatile* container_addr, ContainerPtr container, uint card_in_region) {
  G1CardSetInlinePtr value(container_addr, container);
  return value.add(card_in_region, _config->inline_ptr_bits_per_card(), _config->max_cards_in_inline_ptr());
}

G1CardSet::ContainerPtr G1CardSet::create_coarsened_array_of_cards(uint card_in_region, bool within_howl) {
  uint8_t* data = nullptr;
  ContainerPtr new_container;
  if (within_howl) {
    uint const size_in_bits = _config->max_cards_in_howl_bitmap();
    uint container_offset = _config->howl_bitmap_offset(card_in_region);
    data = allocate_mem_object(ContainerBitMap);
    new (data) G1CardSetBitMap(container_offset, size_in_bits);
    new_container = make_container_ptr(data, ContainerBitMap);
  } else {
    data = allocate_mem_object(ContainerHowl);
    new (data) G1CardSetHowl(card_in_region, _config);
    new_container = make_container_ptr(data, ContainerHowl);
  }
  return new_container;
}

bool G1CardSet::coarsen_container(ContainerPtr volatile* container_addr,
                                  ContainerPtr cur_container,
                                  uint card_in_region,
                                  bool within_howl) {
  ContainerPtr new_container = nullptr;

  switch (container_type(cur_container)) {
    case ContainerArrayOfCards: {
      new_container = create_coarsened_array_of_cards(card_in_region, within_howl);
      break;
    }
    case ContainerBitMap: {
      new_container = FullCardSet;
      break;
    }
    case ContainerInlinePtr: {
      uint const size = _config->max_cards_in_array();
      uint8_t* data = allocate_mem_object(ContainerArrayOfCards);
      new (data) G1CardSetArray(card_in_region, size);
      new_container = make_container_ptr(data, ContainerArrayOfCards);
      break;
    }
    case ContainerHowl: {
      new_container = FullCardSet; // anything will do at this point.
      break;
    }
    default:
      ShouldNotReachHere();
  }

  ContainerPtr old_value = Atomic::cmpxchg(container_addr, cur_container, new_container); // Memory order?
  if (old_value == cur_container) {
    // Success. Indicate that the cards from the current card set must be transferred
    // by this caller.
    // Release the hash table reference to the card. The caller still holds the
    // reference to this card set, so it can never be released (and we do not need to
    // check its result).
    bool should_free = release_container(cur_container);
    assert(!should_free, "must have had more than one reference");
    // Free containers if cur_container is ContainerHowl
    if (container_type(cur_container) == ContainerHowl) {
      G1ReleaseCardsets rel(this);
      container_ptr<G1CardSetHowl>(cur_container)->iterate(rel, _config->num_buckets_in_howl());
    }
    return true;
  } else {
    // Somebody else beat us to coarsening that card set. Exit, but clean up first.
    if (new_container != FullCardSet) {
      assert(new_container != nullptr, "must not be");
      release_and_must_free_container(new_container);
    }
    return false;
  }
}

class G1TransferCard : public StackObj {
  G1CardSet* _card_set;
  uint _region_idx;
public:
  G1TransferCard(G1CardSet* card_set, uint region_idx) : _card_set(card_set), _region_idx(region_idx) { }

  void operator ()(uint card_idx) {
    _card_set->add_card(_region_idx, card_idx, false);
  }
};

void G1CardSet::transfer_cards(G1CardSetHashTableValue* table_entry, ContainerPtr source_container, uint card_region) {
  assert(source_container != FullCardSet, "Should not need to transfer from FullCardSet");
  // Need to transfer old entries unless there is a Full card set container in place now, i.e.
  // the old type has been ContainerBitMap. "Full" contains all elements anyway.
  if (container_type(source_container) != ContainerHowl) {
    G1TransferCard iter(this, card_region);
    iterate_cards_during_transfer(source_container, iter);
  } else {
    assert(container_type(source_container) == ContainerHowl, "must be");
    // Need to correct for that the Full remembered set occupies more cards than the
    // AoCS before.
    Atomic::add(&_num_occupied, _config->max_cards_in_region() - table_entry->_num_occupied, memory_order_relaxed);
  }
}

void G1CardSet::transfer_cards_in_howl(ContainerPtr parent_container,
                                       ContainerPtr source_container,
                                       uint card_region) {
  assert(container_type(parent_container) == ContainerHowl, "must be");
  assert(source_container != FullCardSet, "Should not need to transfer from full");
  // Need to transfer old entries unless there is a Full card set in place now, i.e.
  // the old type has been ContainerBitMap.
  if (container_type(source_container) != ContainerBitMap) {
    // We only need to transfer from anything below ContainerBitMap.
    G1TransferCard iter(this, card_region);
    iterate_cards_during_transfer(source_container, iter);
  } else {
    uint diff = _config->max_cards_in_howl_bitmap() - container_ptr<G1CardSetBitMap>(source_container)->num_bits_set();

    // Need to correct for that the Full remembered set occupies more cards than the
    // bitmap before.
    // We add 1 card less because the values will be incremented
    // in G1CardSet::add_card for the current addition or where already incremented in
    // G1CardSet::add_to_howl after coarsening.
    diff -= 1;

    G1CardSetHowl* howling_array = container_ptr<G1CardSetHowl>(parent_container);
    Atomic::add(&howling_array->_num_entries, diff, memory_order_relaxed);

    G1CardSetHashTableValue* table_entry = get_container(card_region);
    assert(table_entry != nullptr, "Table entry not found for transferred cards");

    Atomic::add(&table_entry->_num_occupied, diff, memory_order_relaxed);

    Atomic::add(&_num_occupied, diff, memory_order_relaxed);
  }
}

G1AddCardResult G1CardSet::add_to_container(ContainerPtr volatile* container_addr,
                                            ContainerPtr container,
                                            uint card_region,
                                            uint card_in_region,
                                            bool increment_total) {
  assert(container_addr != nullptr, "must be");

  G1AddCardResult add_result;

  switch (container_type(container)) {
    case ContainerInlinePtr: {
      add_result = add_to_inline_ptr(container_addr, container, card_in_region);
      break;
    }
    case ContainerArrayOfCards: {
      add_result = add_to_array(container, card_in_region);
      break;
    }
    case ContainerBitMap: {
      add_result = add_to_bitmap(container, card_in_region);
      break;
    }
    case ContainerHowl: {
      assert(ContainerHowl == container_type(FullCardSet), "must be");
      if (container == FullCardSet) {
        return Found;
      }
      add_result = add_to_howl(container, card_region, card_in_region, increment_total);
      break;
    }
    default:
      ShouldNotReachHere();
  }
  return add_result;
}

G1CardSetHashTableValue* G1CardSet::get_or_add_container(uint card_region, bool* should_grow_table) {
  return _table->get_or_add(card_region, should_grow_table);
}

G1CardSetHashTableValue* G1CardSet::get_container(uint card_region) {
  return _table->get(card_region);
}

void G1CardSet::split_card(uintptr_t card, uint& card_region, uint& card_within_region) const {
  card_region = (uint)(card >> _split_card_shift);
  card_within_region = (uint)(card & _split_card_mask);
  assert(card_within_region < _config->max_cards_in_region(), "must be");
}

G1AddCardResult G1CardSet::add_card(uintptr_t card) {
  uint card_region;
  uint card_within_region;
  split_card(card, card_region, card_within_region);

  return add_card(card_region, card_within_region, true /* increment_total */);
}

bool G1CardSet::contains_card(uintptr_t card) {
  uint card_region;
  uint card_within_region;
  split_card(card, card_region, card_within_region);

  return contains_card(card_region, card_within_region);
}

G1AddCardResult G1CardSet::add_card(uint card_region, uint card_in_region, bool increment_total) {
  G1AddCardResult add_result;
  ContainerPtr to_transfer = nullptr;
  ContainerPtr container;

  bool should_grow_table = false;
  G1CardSetHashTableValue* table_entry = get_or_add_container(card_region, &should_grow_table);
  while (true) {
    container = acquire_container(&table_entry->_container);
    add_result = add_to_container(&table_entry->_container, container, card_region, card_in_region, increment_total);

    if (add_result != Overflow) {
      break;
    }
    // Card set has overflown. Coarsen or retry.
    bool coarsened = coarsen_container(&table_entry->_container, container, card_in_region);
    _coarsen_stats.record_coarsening(container_type(container), !coarsened);
    if (coarsened) {
      // We successful coarsened this card set container (and in the process added the card).
      add_result = Added;
      to_transfer = container;
      break;
    }
    // Somebody else beat us to coarsening. Retry.
    release_and_maybe_free_container(container);
  }

  if (increment_total && add_result == Added) {
    Atomic::inc(&table_entry->_num_occupied, memory_order_relaxed);
    Atomic::inc(&_num_occupied, memory_order_relaxed);
  }
  if (should_grow_table) {
    _table->grow();
  }
  if (to_transfer != nullptr) {
    transfer_cards(table_entry, to_transfer, card_region);
  }

  release_and_maybe_free_container(container);

  return add_result;
}

bool G1CardSet::contains_card(uint card_region, uint card_in_region) {
  assert(card_in_region < _config->max_cards_in_region(),
         "Card %u is beyond max %u", card_in_region, _config->max_cards_in_region());

  // Protect the card set container from reclamation.
  GlobalCounter::CriticalSection cs(Thread::current());
  G1CardSetHashTableValue* table_entry = get_container(card_region);
  if (table_entry == nullptr) {
    return false;
  }

  ContainerPtr container = table_entry->_container;
  if (container == FullCardSet) {
    // contains_card() is not a performance critical method so we do not hide that
    // case in the switch below.
    return true;
  }

  switch (container_type(container)) {
    case ContainerInlinePtr: {
      G1CardSetInlinePtr ptr(container);
      return ptr.contains(card_in_region, _config->inline_ptr_bits_per_card());
    }
    case ContainerArrayOfCards: return container_ptr<G1CardSetArray>(container)->contains(card_in_region);
    case ContainerBitMap: return container_ptr<G1CardSetBitMap>(container)->contains(card_in_region, _config->max_cards_in_howl_bitmap());
    case ContainerHowl: {
      G1CardSetHowl* howling_array = container_ptr<G1CardSetHowl>(container);

      return howling_array->contains(card_in_region, _config);
    }
  }
  ShouldNotReachHere();
  return false;
}

void G1CardSet::print_info(outputStream* st, uintptr_t card) {
  uint card_region;
  uint card_in_region;

  split_card(card, card_region, card_in_region);

  G1CardSetHashTableValue* table_entry = get_container(card_region);
  if (table_entry == nullptr) {
    st->print("null card set");
    return;
  }

  ContainerPtr container = table_entry->_container;
  if (container == FullCardSet) {
    st->print("FULL card set)");
    return;
  }
  switch (container_type(container)) {
    case ContainerInlinePtr: {
      st->print("InlinePtr not containing %u", card_in_region);
      break;
    }
    case ContainerArrayOfCards: {
      st->print("AoC not containing %u", card_in_region);
      break;
    }
    case ContainerBitMap: {
      st->print("BitMap not containing %u", card_in_region);
      break;
    }
    case ContainerHowl: {
      st->print("ContainerHowl not containing %u", card_in_region);
      break;
    }
    default: st->print("Unknown card set container type %u", container_type(container)); ShouldNotReachHere(); break;
  }
}

template <class CardVisitor>
void G1CardSet::iterate_cards_during_transfer(ContainerPtr const container, CardVisitor& cl) {
  uint type = container_type(container);
  assert(type == ContainerInlinePtr || type == ContainerArrayOfCards,
         "invalid card set type %d to transfer from",
         container_type(container));

  switch (type) {
    case ContainerInlinePtr: {
      G1CardSetInlinePtr ptr(container);
      ptr.iterate(cl, _config->inline_ptr_bits_per_card());
      return;
    }
    case ContainerArrayOfCards: {
      container_ptr<G1CardSetArray>(container)->iterate(cl);
      return;
    }
    default:
      ShouldNotReachHere();
  }
}

void G1CardSet::iterate_containers(ContainerPtrClosure* cl, bool at_safepoint) {
  auto do_value =
    [&] (G1CardSetHashTableValue* value) {
      cl->do_containerptr(value->_region_idx, value->_num_occupied, value->_container);
      return true;
    };

  if (at_safepoint) {
    _table->iterate_safepoint(do_value);
  } else {
    _table->iterate(do_value);
  }
}

// Applied to all card (ranges) of the containers.
template <typename Closure>
class G1ContainerCardsClosure {
  Closure& _cl;
  uint _region_idx;

public:
  G1ContainerCardsClosure(Closure& cl, uint region_idx) : _cl(cl), _region_idx(region_idx) { }

  bool start_iterate(uint tag) { return true; }

  void operator()(uint card_idx) {
    _cl.do_card(_region_idx, card_idx);
  }

  void operator()(uint card_idx, uint length) {
    for (uint i = 0; i < length; i++) {
      _cl.do_card(_region_idx, card_idx);
    }
  }
};

template <typename Closure, template <typename> class CardOrRanges>
class G1CardSetContainersClosure : public G1CardSet::ContainerPtrClosure {
  G1CardSet* _card_set;
  Closure& _cl;

public:

  G1CardSetContainersClosure(G1CardSet* card_set,
                             Closure& cl) :
    _card_set(card_set),
    _cl(cl) { }

  void do_containerptr(uint region_idx, size_t num_occupied, G1CardSet::ContainerPtr container) override {
    CardOrRanges<Closure> cl(_cl, region_idx);
    _card_set->iterate_cards_or_ranges_in_container(container, cl);
  }
};

void G1CardSet::iterate_cards(CardClosure& cl) {
  G1CardSetContainersClosure<CardClosure, G1ContainerCardsClosure> cl2(this, cl);
  iterate_containers(&cl2);
}

bool G1CardSet::occupancy_less_or_equal_to(size_t limit) const {
  return occupied() <= limit;
}

bool G1CardSet::is_empty() const {
  return _num_occupied == 0;
}

size_t G1CardSet::occupied() const {
  return _num_occupied;
}

size_t G1CardSet::num_containers() {
  class GetNumberOfContainers : public ContainerPtrClosure {
  public:
    size_t _count;

    GetNumberOfContainers() : ContainerPtrClosure(), _count(0) { }

    void do_containerptr(uint region_idx, size_t num_occupied, ContainerPtr container) override {
      _count++;
    }
  } cl;

  iterate_containers(&cl);
  return cl._count;
}

G1CardSetCoarsenStats G1CardSet::coarsen_stats() {
  return _coarsen_stats;
}

void G1CardSet::print_coarsen_stats(outputStream* out) {
  _last_coarsen_stats.subtract_from(_coarsen_stats);

  out->print("Coarsening (recent): ");
  _last_coarsen_stats.print_on(out);
  out->print("Coarsening (all): ");
  _coarsen_stats.print_on(out);

  _last_coarsen_stats.set(_coarsen_stats);
}

size_t G1CardSet::mem_size() const {
  return sizeof(*this) +
         _table->mem_size() +
         _mm->mem_size();
}

size_t G1CardSet::unused_mem_size() const {
  return _mm->unused_mem_size();
}

size_t G1CardSet::static_mem_size() {
  return sizeof(FullCardSet) + sizeof(_coarsen_stats);
}

void G1CardSet::clear() {
  _table->reset();
  _num_occupied = 0;
  _mm->flush();
}

void G1CardSet::reset_table_scanner() {
  _table->reset_table_scanner();
}