33#ifndef ut0lock_free_hash_h
34#define ut0lock_free_hash_h
36#define BOOST_ATOMIC_NO_LIB
63 virtual int64_t
get(uint64_t
key)
const = 0;
69 virtual void set(uint64_t
key, int64_t val) = 0;
85#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
100 for (
size_t i = 0; i <
m_cnt.size(); i++) {
114 other.m_counter =
nullptr;
117 explicit operator bool() const noexcept {
return m_counter !=
nullptr; }
139 for (
size_t i = 0; i <
m_cnt.size(); i++) {
141 std::this_thread::yield();
153 cpu =
static_cast<size_t>(os_getcpu());
158 return cpu %
m_cnt.size();
170 std::array<ut::Cacheline_aligned<std::atomic<uint64_t>>, 256>
m_cnt;
188 ut_ad(n_elements > 0);
192 return ut::aligned_new_withkey<ut_lock_free_list_node_t<T>>(
212 next_t grow(int64_t deleted_val,
bool *grown_by_this_thread) {
229 next_t expected =
nullptr;
236 ut_ad(expected !=
nullptr);
238 *grown_by_this_thread =
false;
242 *grown_by_this_thread =
true;
302 const int64_t val =
m_base[i].m_val.load(std::memory_order_relaxed);
304 if (val == deleted_val) {
383#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
386 m_n_search_iterations(0)
389 ut_a(initial_size > 0);
413 }
while (arr !=
nullptr);
425 int64_t
get(uint64_t
key)
const override {
433 const auto tuple = handle_and_tuple.second;
435 if (tuple ==
nullptr) {
445 int64_t v = tuple->m_val.load(std::memory_order_relaxed);
473 void set(uint64_t
key, int64_t val)
override {
509 const auto tuple = handle_and_tuple.second;
511 if (tuple ==
nullptr) {
516 int64_t v = tuple->m_val.load(std::memory_order_relaxed);
523 if (tuple->m_val.compare_exchange_strong(v,
DELETED)) {
577#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
581 const ulint n_search = m_n_search;
582 const ulint n_search_iterations = m_n_search_iterations;
585 info <<
"Lock free hash usage stats: number of searches=" << n_search
586 <<
", number of search iterations=" << n_search_iterations;
588 info <<
"average iterations per search: "
589 << (double)n_search_iterations / n_search;
596 static const uint64_t
UNUSED = UINT64_MAX;
653 uint64_t
key)
const {
654#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
659 const size_t end =
start + arr_size;
661 for (
size_t i =
start; i <
end; i++) {
662#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
663 ++m_n_search_iterations;
667 const size_t cur_pos = i & (arr_size - 1);
671 const uint64_t cur_key = cur_tuple->
m_key.load(std::memory_order_relaxed);
673 if (cur_key ==
key) {
675 }
else if (cur_key ==
UNUSED || cur_key ==
AVOID) {
691 std::pair<ut_lock_free_cnt_t::handle_t, key_val_t *>
get_tuple(
694 auto handle = (*arr)->begin_access();
702 (*arr)->m_n_base_elements,
key);
705 return {std::move(
handle), t};
708 *arr = (*arr)->
m_next.load();
710 if (*arr ==
nullptr) {
727#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
732 const size_t end =
start + arr_size;
734 for (
size_t i =
start; i <
end; i++) {
735#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
736 ++m_n_search_iterations;
740 const size_t cur_pos = i & (arr_size - 1);
744 const uint64_t cur_key = cur_tuple->
m_key.load(std::memory_order_relaxed);
746 if (cur_key ==
key) {
751 uint64_t expected =
UNUSED;
752 if (cur_tuple->m_key.compare_exchange_strong(expected,
key)) {
760 if (expected ==
key) {
784 uint64_t k = t->
m_key.load(std::memory_order_relaxed);
791 int64_t v = t->
m_val.load(std::memory_order_relaxed);
852 int64_t cur_val = t->
m_val.load(std::memory_order_relaxed);
865 new_val = cur_val + val_to_set;
868 new_val = val_to_set;
871 if (t->
m_val.compare_exchange_strong(cur_val, new_val)) {
896 if (next ==
nullptr) {
913 ut_a(
m_data.compare_exchange_strong(expected, next));
949 arr_node_t *arr,
bool optimize_allowed =
true) {
950 bool call_optimize =
false;
979 if (next !=
nullptr) {
988 bool grown_by_this_thread;
992 if (grown_by_this_thread) {
993 call_optimize =
true;
997 if (optimize_allowed && call_optimize) {
1006 typedef std::list<arr_node_t *, hollow_alloc_t>
hollow_t;
1030#ifdef UT_HASH_IMPLEMENT_PRINT_STATS
1036 mutable std::atomic<uint64_t> m_n_search;
1039 mutable std::atomic<uint64_t> m_n_search_iterations;
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:250
The class info is used to emit informational log messages.
Definition: ut0log.h:188
Allocator that allows std::* containers to manage their memory through ut::malloc* and ut::free libra...
Definition: ut0new.h:2180
An interface class to a basic hash table, that ut_lock_free_hash_t is.
Definition: ut0lock_free_hash.h:51
static const int64_t NOT_FOUND
The value that is returned when the searched for key is not found.
Definition: ut0lock_free_hash.h:55
virtual void del(uint64_t key)=0
Delete a (key, val) pair from the hash.
virtual int64_t get(uint64_t key) const =0
Get the value mapped to a given key.
virtual void dec(uint64_t key)=0
Decrement the value of a given key with 1 or insert a new tuple (key, -1).
virtual void inc(uint64_t key)=0
Increment the value for a given key with 1 or insert a new tuple (key, 1).
virtual void set(uint64_t key, int64_t val)=0
Set the value for a given key, either inserting a new (key, val) tuple or overwriting an existent val...
virtual ~ut_hash_interface_t()=default
Destructor.
Definition: ut0lock_free_hash.h:105
handle_t(handle_t &&other) noexcept
Definition: ut0lock_free_hash.h:113
std::atomic< uint64_t > * m_counter
Definition: ut0lock_free_hash.h:126
handle_t(std::atomic< uint64_t > *counter)
Definition: ut0lock_free_hash.h:109
~handle_t()
Definition: ut0lock_free_hash.h:119
handle_t()
Definition: ut0lock_free_hash.h:107
Lock free ref counter.
Definition: ut0lock_free_hash.h:94
ut_lock_free_cnt_t()
Constructor.
Definition: ut0lock_free_hash.h:97
size_t n_cnt_index() const
Derive an appropriate index in m_cnt[] for the current thread.
Definition: ut0lock_free_hash.h:149
handle_t reference()
Increment the counter.
Definition: ut0lock_free_hash.h:130
void await_release_of_old_references() const
Wait until all previously existing references get released.
Definition: ut0lock_free_hash.h:138
std::array< ut::Cacheline_aligned< std::atomic< uint64_t > >, 256 > m_cnt
The shards of the counter.
Definition: ut0lock_free_hash.h:170
Lock free hash table.
Definition: ut0lock_free_hash.h:373
void set(uint64_t key, int64_t val) override
Set the value for a given key, either inserting a new (key, val) tuple or overwriting an existent val...
Definition: ut0lock_free_hash.h:473
static const int64_t DELETED
A val == DELETED designates that this cell in the array has been used in the past,...
Definition: ut0lock_free_hash.h:608
void inc(uint64_t key) override
Increment the value for a given key with 1 or insert a new tuple (key, 1).
Definition: ut0lock_free_hash.h:556
bool update_tuple(key_val_t *t, int64_t val_to_set, bool is_delta)
Update the value of a given tuple.
Definition: ut0lock_free_hash.h:851
bool m_del_when_zero
True if a tuple should be automatically deleted from the hash if its value becomes 0 after an increme...
Definition: ut0lock_free_hash.h:1028
static const uint64_t UNUSED
A key == UNUSED designates that this cell in the array is empty.
Definition: ut0lock_free_hash.h:596
size_t guess_position(uint64_t key, size_t arr_size) const
A hash function used to map a key to its suggested position in the array.
Definition: ut0lock_free_hash.h:638
ut_lock_free_list_node_t< key_val_t > arr_node_t
An array node in the hash.
Definition: ut0lock_free_hash.h:628
void optimize()
Optimize the hash table.
Definition: ut0lock_free_hash.h:888
void insert_or_update(uint64_t key, int64_t val, bool is_delta, arr_node_t *arr, bool optimize_allowed=true)
Insert a new tuple or update an existent one.
Definition: ut0lock_free_hash.h:948
ib_mutex_t m_optimize_latch
Concurrent copy-all-elements-to-the-next-array, removal of the head of the list and freeing of its m_...
Definition: ut0lock_free_hash.h:1024
void dec(uint64_t key) override
Decrement the value of a given key with 1 or insert a new tuple (key, -1).
Definition: ut0lock_free_hash.h:570
std::pair< ut_lock_free_cnt_t::handle_t, key_val_t * > get_tuple(uint64_t key, arr_node_t **arr) const
Get the array cell of a key.
Definition: ut0lock_free_hash.h:691
static const uint64_t AVOID
A key == AVOID designates an unusable cell.
Definition: ut0lock_free_hash.h:603
key_val_t * insert_or_get_position_in_array(key_val_t *arr, size_t arr_size, uint64_t key)
Insert the given key into a given array or return its cell if already present.
Definition: ut0lock_free_hash.h:725
std::list< arr_node_t *, hollow_alloc_t > hollow_t
Definition: ut0lock_free_hash.h:1006
void del(uint64_t key) override
Delete a (key, val) pair from the hash.
Definition: ut0lock_free_hash.h:501
key_val_t * get_tuple_from_array(key_val_t *arr, size_t arr_size, uint64_t key) const
Get the array cell of a key from a given array.
Definition: ut0lock_free_hash.h:652
int64_t get(uint64_t key) const override
Get the value mapped to a given key.
Definition: ut0lock_free_hash.h:425
hollow_t * m_hollow_objects
Container for hollow (semi-destroyed) objects that have been removed from the list that starts at m_d...
Definition: ut0lock_free_hash.h:1014
void copy_to_another_array(arr_node_t *src_arr, arr_node_t *dst_arr)
Copy all used elements from one array to another.
Definition: ut0lock_free_hash.h:780
ut::allocator< arr_node_t * > hollow_alloc_t
Definition: ut0lock_free_hash.h:1005
ut_lock_free_hash_t(size_t initial_size, bool del_when_zero)
Constructor.
Definition: ut0lock_free_hash.h:381
static const int64_t GOTO_NEXT_ARRAY
A val == GOTO_NEXT_ARRAY designates that this tuple (key, whatever) has been moved to the next array.
Definition: ut0lock_free_hash.h:613
~ut_lock_free_hash_t() override
Destructor.
Definition: ut0lock_free_hash.h:402
std::atomic< arr_node_t * > m_data
Storage for the (key, val) tuples.
Definition: ut0lock_free_hash.h:1003
A node in a linked list of arrays.
Definition: ut0lock_free_hash.h:176
static ut_lock_free_list_node_t * alloc(size_t n_elements)
Definition: ut0lock_free_hash.h:191
std::atomic< next_t > m_next
Pointer to the next node if any or NULL.
Definition: ut0lock_free_hash.h:290
size_t n_deleted(int64_t deleted_val) const
Count the number of deleted elements.
Definition: ut0lock_free_hash.h:298
ut_lock_free_list_node_t< T > * next_t
Definition: ut0lock_free_hash.h:178
ut_lock_free_cnt_t m_n_ref
Counter for the current number of readers and writers to this object.
Definition: ut0lock_free_hash.h:316
std::atomic_bool m_pending_free
Indicate whether some thread is waiting for readers to go away before it can free the memory occupied...
Definition: ut0lock_free_hash.h:285
next_t grow(int64_t deleted_val, bool *grown_by_this_thread)
Create and append a new array to this one and store a pointer to it in 'm_next'.
Definition: ut0lock_free_hash.h:212
ut_lock_free_cnt_t::handle_t begin_access()
Mark the beginning of an access to this object.
Definition: ut0lock_free_hash.h:258
size_t m_n_base_elements
Number of elements in 'm_base'.
Definition: ut0lock_free_hash.h:281
static void dealloc(ut_lock_free_list_node_t *ptr)
Definition: ut0lock_free_hash.h:197
ut_lock_free_list_node_t(size_t n_elements)
Constructor.
Definition: ut0lock_free_hash.h:182
ut::unique_ptr< T[]> m_base
Base array.
Definition: ut0lock_free_hash.h:278
void await_release_of_old_references()
Wait until all previously held references are released.
Definition: ut0lock_free_hash.h:273
static void start(mysql_harness::PluginFuncEnv *env)
Definition: http_auth_backend_plugin.cc:176
uint counter
Definition: mysqlimport.cc:57
std::string print_stats(::recovery_statistics const &internal_stats, ::recovery_statistics const &external_stats)
Composes a string presenting the statistics for the given objects.
Definition: recovery.cc:364
bool load(THD *, const dd::String_type &fname, dd::String_type *buf)
Read an sdi file from disk and store in a buffer.
Definition: sdi_file.cc:307
Unique_ptr< T, std::nullptr_t > make_unique(size_t size)
In-place constructs a new unique pointer with no specific allocator and with array type T.
Cursor end()
A past-the-end Cursor.
Definition: rules_table_service.cc:191
static int handle(int sql_errno, const char *sqlstate, const char *message, void *state)
Bridge function between the C++ API offered by this module and the C API of the parser service.
Definition: services.cc:63
This file contains a set of libraries providing overloads for regular dynamic allocation routines whi...
Definition: aligned_alloc.h:47
const thread_local size_t this_thread_hash
The hash value of the current thread's id.
Definition: os0thread.h:72
static uint64_t hash_uint64(uint64_t value)
Hashes a 64-bit integer.
Definition: ut0rnd.h:217
void delete_(T *ptr) noexcept
Releases storage which has been dynamically allocated through any of the ut::new*() variants.
Definition: ut0new.h:808
T * new_arr(Args &&... args)
Dynamically allocates storage for an array of T's.
Definition: ut0new.h:958
std::conditional_t< !std::is_array< T >::value, std::unique_ptr< T, detail::Deleter< T > >, std::conditional_t< detail::is_unbounded_array_v< T >, std::unique_ptr< T, detail::Array_deleter< std::remove_extent_t< T > > >, void > > unique_ptr
The following is a common type that is returned by all the ut::make_unique (non-aligned) specializati...
Definition: ut0new.h:2437
PSI_memory_key_t make_psi_memory_key(PSI_memory_key key)
Convenience helper function to create type-safe representation of PSI_memory_key.
Definition: ut0new.h:189
void aligned_delete(T *ptr) noexcept
Releases storage which has been dynamically allocated through any of the aligned_new_*() variants.
Definition: ut0new.h:1649
NUMA API wrapper over various operating system specific APIs.
The interface to the operating system process and thread control primitives.
required string key
Definition: replication_asynchronous_connection_failover.proto:59
(key, val) tuple type.
Definition: ut0lock_free_hash.h:616
key_val_t()
Definition: ut0lock_free_hash.h:617
std::atomic< int64_t > m_val
Value.
Definition: ut0lock_free_hash.h:623
std::atomic< uint64_t > m_key
Key.
Definition: ut0lock_free_hash.h:620
@ LATCH_ID_LOCK_FREE_HASH
Definition: sync0types.h:372
Version control for database, common definitions, and include files.
unsigned long int ulint
Definition: univ.i:405
Utilities related to CPU cache.
#define ut_ad(EXPR)
Debug assertion.
Definition: ut0dbg.h:68
#define ut_a(EXPR)
Abort execution if EXPR does not evaluate to nonzero.
Definition: ut0dbg.h:56
void mutex_destroy(Mutex *mutex)
Removes a mutex instance from the mutex list.
Definition: ut0mutex.h:247
#define mutex_exit(M)
Definition: ut0mutex.h:122
#define mutex_enter(M)
Definition: ut0mutex.h:116
#define mutex_create(I, M)
Definition: ut0mutex.h:109
Dynamic memory allocation routines and custom allocators specifically crafted to support memory instr...
PSI_memory_key mem_key_ut_lock_free_hash_t
Definition: ut0new.cc:63
Random numbers and hashing.
#define ut_is_2pow(n)
Determines if a number is zero or a power of two.
Definition: ut0ut.h:202