/*****************************************************************************

Copyright (c) 1996, 2016, Oracle and/or its affiliates. All Rights Reserved.
Copyright (c) 2017, 2022, MariaDB Corporation.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program 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 for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA

*****************************************************************************/

/********************************************************************//**
@file include/btr0sea.h
The index tree adaptive search

Created 2/17/1996 Heikki Tuuri
*************************************************************************/

#pragma once

#include "dict0dict.h"
#ifdef BTR_CUR_HASH_ADAPT
# include "buf0buf.h"

# ifdef UNIV_PFS_RWLOCK
extern mysql_pfs_key_t btr_search_latch_key;
# endif /* UNIV_PFS_RWLOCK */

# define btr_search_sys_create() btr_search.create()
# define btr_search_sys_free() btr_search.free()

ATTRIBUTE_COLD void btr_search_lazy_free(dict_index_t *index) noexcept;

/** Tries to guess the right search position based on the hash search info
of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
and the function returns TRUE, then cursor->up_match and cursor->low_match
both have sensible values.
@param[in,out] index  index
@param[in] tuple  logical record
@param[in] ge  false=PAGE_CUR_LE, true=PAGE_CUR_GE
@param[in] latch_mode BTR_SEARCH_LEAF, ...
@param[out] cursor  tree cursor
@param[in] mtr  mini-transaction
@return whether the search succeeded */
bool
btr_search_guess_on_hash(
 dict_index_t* index,
 const dtuple_t* tuple,
 bool  ge,
 btr_latch_mode latch_mode,
 btr_cur_t* cursor,
 mtr_t*  mtr) noexcept;

/** Move or delete hash entries for moved records, usually in a page split.
If new_block is already hashed, then any hash index for block is dropped.
If new_block is not hashed, and block is hashed, then a new hash index is
built to new_block with the same parameters as block.
@param new_block   destination page
@param block       source page (subject to deletion later)
@param mtr         mini-transaction (to update trx AHI statistics) */
void btr_search_move_or_delete_hash_entries(buf_block_t *new_block,
                                            buf_block_t *block,
                                            const mtr_t &mtr) noexcept;

/** Drop any adaptive hash index entries that point to an index page.
@param block        latched block containing index page, or a buffer-unfixed
                    index page or a block in state BUF_BLOCK_REMOVE_HASH
@param not_garbage  drop only if the index is set and NOT this */
void btr_search_drop_page_hash_index(buf_block_t *block,
                                     const dict_index_t *not_garbage) noexcept;

/** Drop possible adaptive hash index entries when a page is evicted
from the buffer pool or freed in a file, or the index is being dropped.
@param mtr       mini-transaction
@param page_id   page identifier of the being-dropped page */
void btr_search_drop_page_hash_when_freed(mtr_t *mtr, const page_id_t page_id)
  noexcept;

/** Update the page hash index after a single record is inserted on a page.
@param cursor cursor which was positioned before the inserted record
@param reorg  whether the page was reorganized
@param mtr    mini-transaction (to update trx AHI statistics) */
void btr_search_update_hash_on_insert(btr_cur_t *cursor, bool reorg,
                                      const mtr_t &mtr) noexcept;

/** Updates the page hash index before a single record is deleted from a page.
@param cursor   cursor positioned on the to-be-deleted record */
void btr_search_update_hash_on_delete(btr_cur_t *cursor) noexcept;

/** Validates the search system.
@param thd   connection, for checking if CHECK TABLE has been killed
@return true if ok */
bool btr_search_validate(THD *thd) noexcept;

# ifdef UNIV_DEBUG
/** @return if the index is marked as freed */
bool btr_search_check_marked_free_index(const buf_block_t *block) noexcept;
# endif /* UNIV_DEBUG */

struct ahi_node;

/** The possible AHI enabled values: disabled, enabled, enabled
but active only when specifically enabled by index or table option.

Matches innodb_ahi_names from ha_innodb.cc */
enum ahi_status : ulong
{
  /** Disabled */
  AHI_OFF= 0,
  /** Enabled */
  AHI_ON= 1,
  /** Enabled, active only where index or table option specifically
  enabled AHI */
  AHI_IF_SPECIFIED= 2
};

static_assert(
  uint8_t{dict_index_t::ahi::AHI_INDEX_FORCE_DISABLED} == AHI_OFF &&
  uint8_t{dict_index_t::ahi::AHI_INDEX_NO_PREFERENCE} == AHI_ON &&
  uint8_t{dict_index_t::ahi::AHI_INDEX_PREFER_ENABLED} == AHI_IF_SPECIFIED,
  "ahi_status / dict_index_t::ahi::preference numeric values must match");

/** The hash index system */
struct btr_sea
{
  /** the actual value of innodb_adaptive_hash_index, protected by
  all partition::latch. Note that if buf_block_t::index is not nullptr
  while a thread is holding a partition::latch, then also this must hold. */
  Atomic_relaxed<ahi_status> enabled;

  /** Number of successful adaptive hash index lookups */
  union {
    Atomic_counter<size_t> hit_count;
    size_t hit_count_nonatomic;
  };

  /** Number of searches down the B-tree (adaptive hash index misses) */
  union {
    Atomic_counter<size_t> miss_count;
    size_t miss_count_nonatomic;
  };

  /** Number of rows added to the adaptive hash index */
  union {
    Atomic_counter<size_t> rows_added;
    size_t rows_added_nonatomic;
  };

  /** Number of pages added to the adaptive hash index */
  union {
    Atomic_counter<size_t> pages_added;
    size_t pages_added_nonatomic;
  };

  /** Snapshots for calculating per-second rates; protected by
  srv_innodb_monitor_mutex */
  size_t hit_count_old;
  size_t miss_count_old;

private:
  /** Disable the adaptive hash search system and empty the index.
  @return the AHI enabled value before the operation is performed */
  ATTRIBUTE_COLD ahi_status disable_and_lock() noexcept;

  /** Unlock the adaptive hash search system. */
  ATTRIBUTE_COLD void unlock() noexcept;

public:
#ifdef _MSC_VER
  btr_sea();
#endif

  /** Check if AHI is enabled for an index.
  @param index the index
  @return true if AHI enabled for the index */
  bool is_enabled(const dict_index_t *index) const noexcept
  {
    /* Index is enabled if global AHI is enabled and index can be enabled.
    If enabled is set to 2 (AHI_IF_SPECIFIED), only enable indexes declared
    with AHI enabled on (uint8_t{index->search_info.get_enabled()} == 2).
    We don't have to check if uint8_t{index->search_info.get_enabled()} != 0
    as the test enabled <= uint8_t{index->search_info.get_enabled()} will
    not be true in this case.

    All combinations of (btr_sea::enabled, index->search_info.get_enabled())
    and the resulting return value:

      (AHI_OFF,          AHI_INDEX_FORCE_DISABLED) -> false
      (AHI_OFF,          AHI_INDEX_NO_PREFERENCE ) -> false
      (AHI_OFF,          AHI_INDEX_PREFER_ENABLED) -> false
      (AHI_ON,           AHI_INDEX_FORCE_DISABLED) -> false
      (AHI_ON,           AHI_INDEX_NO_PREFERENCE ) -> true
      (AHI_ON,           AHI_INDEX_PREFER_ENABLED) -> true
      (AHI_IF_SPECIFIED, AHI_INDEX_FORCE_DISABLED) -> false
      (AHI_IF_SPECIFIED, AHI_INDEX_NO_PREFERENCE ) -> false
      (AHI_IF_SPECIFIED, AHI_INDEX_PREFER_ENABLED) -> true */
    const ahi_status enabled{get_enabled()};
    return (unlikely(enabled != AHI_OFF) &&
            enabled <= uint8_t{index->search_info.get_enabled()});
  }

  /** Check if AHI is enabled for an index, supposing it is enabled for
  a nullptr index. This to handle the case where we do not yet know if
  AHI for the index is enabled or not.
  @see btr_sea::is_enabled(), equivalent when index is not nullptr.
  @param index the index (can be nullptr)
  @return true if AHI may be enabled for the index */
  bool may_be_enabled(const dict_index_t *index) const noexcept
  {
    const ahi_status enabled{get_enabled()};
    return (unlikely(enabled != AHI_OFF) &&
            (!index || enabled <= uint8_t{index->search_info.get_enabled()}));
  }

  ahi_status get_enabled() const noexcept { return enabled; }

  /** Disable the adaptive hash search system and empty the index.
  @return the AHI enabled value before the operation is performed */
  ATTRIBUTE_COLD ahi_status disable() noexcept;

  /** Enable the adaptive hash search system.
  @param resize whether buf_pool_t::resize() is the caller
  @param enable_kind the requested AHI enablement kind */
  ATTRIBUTE_COLD void enable(bool resize, ahi_status enable_kind) noexcept;

  /** Hash cell chain in hash_table */
  struct hash_chain
  {
    /** pointer to the first block */
    ahi_node *first;

    /** Find an element.
    @param u   unary predicate
    @return the first matching element
    @retval nullptr if not found */
    template<typename UnaryPred>
    inline ahi_node *find(UnaryPred u) const noexcept;

    /** Search for a pointer to an element.
    @param u   unary predicate
    @return pointer to the first matching element,
    or to the last element in the chain */
    template<typename UnaryPred>
    inline ahi_node **search(UnaryPred u) noexcept;
  };

  /** Hash table with singly-linked overflow lists.
  Based on @see buf_pool_t::page_hash_table */
  struct hash_table
  {
    static_assert(CPU_LEVEL1_DCACHE_LINESIZE >= 64, "less than 64 bytes");
    static_assert(!(CPU_LEVEL1_DCACHE_LINESIZE & 63),
      "not a multiple of 64 bytes");

    /** Number of array[] elements per page_hash_latch.
    Must be one less than a power of 2. */
#if 0
    static constexpr size_t ELEMENTS_PER_LATCH= 64 / sizeof(void*) - 1;

    /** Extra padding. FIXME: Is this ever useful to be nonzero?
    Long time ago, some testing on an ARMv8 implementation seemed
    to suggest so, but this has not been validated recently. */
    static constexpr size_t EMPTY_SLOTS_PER_LATCH=
      ((CPU_LEVEL1_DCACHE_LINESIZE / 64) - 1) * (64 / sizeof(void*));
#else
    static constexpr size_t ELEMENTS_PER_LATCH=
      CPU_LEVEL1_DCACHE_LINESIZE / sizeof(void*) - 1;
    static constexpr size_t EMPTY_SLOTS_PER_LATCH= 0;
#endif

    /** number of payload elements in array[] */
    Atomic_relaxed<size_t> n_cells;
    /** the hash table, with pad(n_cells) elements, aligned to L1 cache size */
    hash_chain *array;

    /** Create the hash table.
    @param n  the lower bound of n_cells
    @return whether the creation succeeded */
    inline bool create(ulint n) noexcept;

    /** Free the hash table. */
    void free() noexcept { aligned_free(array); array= nullptr; }

    /** @return the index of an array element */
    ulint calc_hash(ulint fold) const noexcept
    { return calc_hash(fold, n_cells); }
    /** @return raw array index converted to padded index */
    static ulint pad(ulint h) noexcept
    {
      ulint latches= h / ELEMENTS_PER_LATCH;
      ulint empty_slots= latches * EMPTY_SLOTS_PER_LATCH;
      return 1 + latches + empty_slots + h;
    }
  private:
    /** @return the index of an array element */
    static ulint calc_hash(ulint fold, ulint n_cells) noexcept
    {
      return pad(fold % n_cells);
    }
  public:
    /** @return the latch covering a hash table chain */
    static page_hash_latch &lock_get(hash_chain &chain) noexcept
    {
      static_assert(!((ELEMENTS_PER_LATCH + 1) & ELEMENTS_PER_LATCH),
                    "must be one less than a power of 2");
      const size_t addr= reinterpret_cast<size_t>(&chain);
      ut_ad(addr & (ELEMENTS_PER_LATCH * sizeof chain));
      return *reinterpret_cast<page_hash_latch*>
        (addr & ~(ELEMENTS_PER_LATCH * sizeof chain));
    }

    /** Get a hash table slot. */
    hash_chain &cell_get(ulint fold) const
    { return array[calc_hash(fold, n_cells)]; }
  };

  /** Partition of the hash table */
  struct partition
  {
    /** latch protecting table: either an exclusive latch, or
    a shared latch combined with lock_get() */
    alignas(CPU_LEVEL1_DCACHE_LINESIZE)
    IF_DBUG(srw_lock_debug,srw_spin_lock) latch;
    /** map of CRC-32C of rec prefix to rec_t* in buf_page_t::frame */
    hash_table table;
    /** protects blocks; acquired while holding latch
    and possibly table.lock_get() */
    srw_mutex blocks_mutex;
    /** allocated blocks */
    UT_LIST_BASE_NODE_T(buf_page_t) blocks;
    /** a cached block to extend blocks */
    Atomic_relaxed<buf_block_t*> spare;

    inline void init() noexcept;

    /** @return whether the allocation succeeded */
    inline bool alloc(size_t hash_size) noexcept;

    inline void clear() noexcept;

    inline void free() noexcept;

    /** @return the number of allocated buffer pool blocks */
    TPOOL_SUPPRESS_TSAN size_t get_blocks() const noexcept
    { return UT_LIST_GET_LEN(blocks) + !!spare; }

    /** Ensure that there is a spare block for a future insert() */
    void prepare_insert() noexcept;

    /** Undo prepare_insert() in case !btr_search.enabled */
    void rollback_insert() noexcept;

  private:
    /** Start cleanup_after_erase()
    @return the last allocated element */
    inline ahi_node *cleanup_after_erase_start() noexcept;
    /** Finish cleanup_after_erase().
    We reduce the allocated size in UT_LIST_GET_LAST(blocks)->free_offset.
    If that size reaches 0, the last block will be removed from blocks,
    and a block may have to be freed by our caller.
    @return buffer block to be freed
    @retval nullptr if no buffer block was freed */
    buf_block_t *cleanup_after_erase_finish() noexcept;
  public:
    __attribute__((nonnull))
    /** Clean up after erasing an AHI node, while the caller is
    holding an exclusive latch. Unless "erase" is the last allocated
    element, we will swap it with the last allocated element.
    Finally, we return via cleanup_after_erase_finish().
    @param erase node being erased
    @return buffer block to be freed
    @retval nullptr if no buffer block was freed */
    buf_block_t *cleanup_after_erase(ahi_node *erase) noexcept;

    __attribute__((nonnull))
    /** Clean up after erasing an AHI node. This is similar to
    cleanup_after_erase(ahi_node*), except that the operation may fail.
    @param erase   node being erased
    @param l       the latch held together with shared latch
    @return buffer block to be freed
    @retval nullptr if no buffer block was freed
    @retval -1     if we fail to shrink the allocation and erasing
                   needs to be retried while holding an exclusive latch */
    buf_block_t *cleanup_after_erase(ahi_node *erase, page_hash_latch *l)
      noexcept;

    __attribute__((nonnull))
# if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
    /** Insert or replace an entry into the hash table.
    @param fold  CRC-32C of rec prefix
    @param rec   B-tree leaf page record
    @param block the buffer block that contains rec */
    void insert(uint32_t fold, const rec_t *rec, buf_block_t *block) noexcept;
# else
    /** Insert or replace an entry into the hash table.
    @param fold  CRC-32C of rec prefix
    @param rec   B-tree leaf page record */
    void insert(uint32_t fold, const rec_t *rec) noexcept;
# endif

    /** erase() return value */
    enum erase_status{
      /** must retry with exclusive latch */
      ERASE_RETRY= -1,
      /** the pointer to the record was erased */
      ERASED= 0,
      /** nothing was erased */
      NOT_ERASED= 1
    };

    /** Delete a pointer to a record if it exists, and release the latch.
    @tparam ex   true=holding exclusive latch, false=shared latch
    @param cell  hash table cell that may contain the CRC-32C of rec prefix
    @param rec   B-tree leaf page record
    @return status */
    template<bool ex>
    erase_status erase(hash_chain &cell, const rec_t *rec) noexcept;
  };

  /** number of hash table entries, to be multiplied by n_parts */
  uint n_cells;
  /** innodb_adaptive_hash_index_parts */
  uint n_parts;
  /** Partitions of the adaptive hash index */
  partition parts[512];

  /** Get an adaptive hash index partition */
  partition &get_part(index_id_t id) noexcept { return parts[id % n_parts]; }

  /** Get an adaptive hash index partition */
  partition &get_part(const dict_index_t &index) noexcept
  { return get_part(index.id); }

  /** Create and initialize at startup */
  void create() noexcept;

  /** @return whether the allocation succeeded */
  bool alloc(size_t hash_size) noexcept;

  /** Change the number of cells */
  void resize(uint n_cells) noexcept;

  /** Clear when disabling the adaptive hash index */
  inline void clear() noexcept;

  /** Free at shutdown */
  void free() noexcept;
};

/** The adaptive hash index */
extern btr_sea btr_search;

# ifdef UNIV_SEARCH_PERF_STAT
/** Number of successful adaptive hash index lookups */
extern ulint btr_search_n_succ;
/** Number of failed adaptive hash index lookups */
extern ulint btr_search_n_hash_fail;
# endif /* UNIV_SEARCH_PERF_STAT */
#else /* BTR_CUR_HASH_ADAPT */
# define btr_search_sys_create()
# define btr_search_sys_free()
# define btr_search_drop_page_hash_index(block, not_garbage)
# define btr_search_move_or_delete_hash_entries(new_block, block, mtr)
# define btr_search_update_hash_on_insert(cursor, ahi_latch, mtr)
# define btr_search_update_hash_on_delete(cursor)
# ifdef UNIV_DEBUG
#  define btr_search_check_marked_free_index(block)
# endif /* UNIV_DEBUG */
#endif /* BTR_CUR_HASH_ADAPT */