1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2016 Intel Corporation
3 * Copyright(c) 2018 Arm Limited
7 * This file hold Cuckoo Hash private data structures to allows include from
8 * platform specific files like rte_cuckoo_hash_x86.h
11 #ifndef _RTE_CUCKOO_HASH_H_
12 #define _RTE_CUCKOO_HASH_H_
14 #if defined(RTE_ARCH_X86)
15 #include "rte_cmp_x86.h"
18 #if defined(RTE_ARCH_ARM64)
19 #include "rte_cmp_arm64.h"
22 /* Macro to enable/disable run-time checking of function parameters */
23 #if defined(RTE_LIBRTE_HASH_DEBUG)
24 #define RETURN_IF_TRUE(cond, retval) do { \
29 #define RETURN_IF_TRUE(cond, retval)
32 #if defined(RTE_LIBRTE_HASH_DEBUG)
33 #define ERR_IF_TRUE(cond, fmt, args...) do { \
35 RTE_LOG(ERR, HASH, fmt, ##args); \
40 #define ERR_IF_TRUE(cond, fmt, args...)
43 #include <rte_hash_crc.h>
44 #include <rte_jhash.h>
46 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
48 * All different options to select a key compare function,
49 * based on the key size and custom function.
51 enum cmp_jump_table_case {
66 * Table storing all different key compare functions
67 * (multi-process supported)
69 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
83 * All different options to select a key compare function,
84 * based on the key size and custom function.
86 enum cmp_jump_table_case {
93 * Table storing all different key compare functions
94 * (multi-process supported)
96 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
105 * Number of items per bucket.
106 * 8 is a tradeoff between performance and memory consumption.
107 * When it is equal to 8, multiple 'struct rte_hash_bucket' can be fit
108 * on a single cache line (64 or 128 bytes long) without any gaps
109 * in memory between them due to alignment.
111 #define RTE_HASH_BUCKET_ENTRIES 8
113 #if !RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES)
114 #error RTE_HASH_BUCKET_ENTRIES must be a power of 2
117 #define NULL_SIGNATURE 0
121 #define KEY_ALIGNMENT 16
123 #define LCORE_CACHE_SIZE 64
125 #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000
127 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4
129 #define RTE_HASH_TSX_MAX_RETRY 10
132 unsigned len; /**< Cache len */
133 uint32_t objs[LCORE_CACHE_SIZE]; /**< Cache objects */
134 } __rte_cache_aligned;
136 /* Structure that stores key-value pair */
137 struct rte_hash_key {
142 /* Variable key size */
146 /* All different signature compare functions */
147 enum rte_hash_sig_compare_function {
148 RTE_HASH_COMPARE_SCALAR = 0,
149 RTE_HASH_COMPARE_SSE,
150 RTE_HASH_COMPARE_NEON,
154 /** Bucket structure */
155 struct rte_hash_bucket {
156 uint16_t sig_current[RTE_HASH_BUCKET_ENTRIES];
158 uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];
160 uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
163 } __rte_cache_aligned;
165 /** A hash table structure. */
167 char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */
168 uint32_t entries; /**< Total table entries. */
169 uint32_t num_buckets; /**< Number of buckets in table. */
171 struct rte_ring *free_slots;
172 /**< Ring that stores all indexes of the free slots in the key table */
174 struct lcore_cache *local_free_slots;
175 /**< Local cache per lcore, storing some indexes of the free slots */
178 struct rte_hash_rcu_config *hash_rcu_cfg;
179 /**< HASH RCU QSBR configuration structure */
180 struct rte_rcu_qsbr_dq *dq; /**< RCU QSBR defer queue. */
182 /* Fields used in lookup */
184 uint32_t key_len __rte_cache_aligned;
185 /**< Length of hash key. */
186 uint8_t hw_trans_mem_support;
187 /**< If hardware transactional memory is used. */
188 uint8_t use_local_cache;
189 /**< If multi-writer support is enabled, use local cache
190 * to allocate key-store slots.
192 uint8_t readwrite_concur_support;
193 /**< If read-write concurrency support is enabled */
194 uint8_t ext_table_support; /**< Enable extendable bucket table */
195 uint8_t no_free_on_del;
196 /**< If key index should be freed on calling rte_hash_del_xxx APIs.
197 * If this is set, rte_hash_free_key_with_position must be called to
198 * free the key index associated with the deleted entry.
199 * This flag is enabled by default.
201 uint8_t readwrite_concur_lf_support;
202 /**< If read-write concurrency lock free support is enabled */
203 uint8_t writer_takes_lock;
204 /**< Indicates if the writer threads need to take lock */
205 rte_hash_function hash_func; /**< Function used to calculate hash. */
206 uint32_t hash_func_init_val; /**< Init value used by hash_func. */
207 rte_hash_cmp_eq_t rte_hash_custom_cmp_eq;
208 /**< Custom function used to compare keys. */
209 enum cmp_jump_table_case cmp_jump_table_idx;
210 /**< Indicates which compare function to use. */
211 enum rte_hash_sig_compare_function sig_cmp_fn;
212 /**< Indicates which signature compare function to use. */
213 uint32_t bucket_bitmask;
214 /**< Bitmask for getting bucket index from hash signature. */
215 uint32_t key_entry_size; /**< Size of each key entry. */
217 void *key_store; /**< Table storing all keys and data */
218 struct rte_hash_bucket *buckets;
219 /**< Table with buckets storing all the hash values and key indexes
222 rte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */
223 struct rte_hash_bucket *buckets_ext; /**< Extra buckets array */
224 struct rte_ring *free_ext_bkts; /**< Ring of indexes of free buckets */
225 /* Stores index of an empty ext bkt to be recycled on calling
226 * rte_hash_del_xxx APIs. When lock free read-write concurrency is
227 * enabled, an empty ext bkt cannot be put into free list immediately
228 * (as readers might be using it still). Hence freeing of the ext bkt
229 * is piggy-backed to freeing of the key index.
231 uint32_t *ext_bkt_to_free;
232 uint32_t *tbl_chng_cnt;
233 /**< Indicates if the hash table changed from last read. */
234 } __rte_cache_aligned;
237 struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */
238 uint32_t cur_bkt_idx;
240 struct queue_node *prev; /* Parent(bucket) in search path */
241 int prev_slot; /* Parent(slot) in search path */
244 /** @internal Default RCU defer queue entries to reclaim in one go. */
245 #define RTE_HASH_RCU_DQ_RECLAIM_MAX 16