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 #include <rte_hash_crc.h>
33 #include <rte_jhash.h>
35 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
37 * All different options to select a key compare function,
38 * based on the key size and custom function.
40 enum cmp_jump_table_case {
55 * Table storing all different key compare functions
56 * (multi-process supported)
58 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
72 * All different options to select a key compare function,
73 * based on the key size and custom function.
75 enum cmp_jump_table_case {
82 * Table storing all different key compare functions
83 * (multi-process supported)
85 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
93 /** Number of items per bucket. */
94 #define RTE_HASH_BUCKET_ENTRIES 8
96 #if !RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES)
97 #error RTE_HASH_BUCKET_ENTRIES must be a power of 2
100 #define NULL_SIGNATURE 0
104 #define KEY_ALIGNMENT 16
106 #define LCORE_CACHE_SIZE 64
108 #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000
110 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4
112 #define RTE_HASH_TSX_MAX_RETRY 10
115 unsigned len; /**< Cache len */
116 void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */
117 } __rte_cache_aligned;
119 /* Structure that stores key-value pair */
120 struct rte_hash_key {
125 /* Variable key size */
129 /* All different signature compare functions */
130 enum rte_hash_sig_compare_function {
131 RTE_HASH_COMPARE_SCALAR = 0,
132 RTE_HASH_COMPARE_SSE,
136 /** Bucket structure */
137 struct rte_hash_bucket {
138 uint16_t sig_current[RTE_HASH_BUCKET_ENTRIES];
140 uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];
142 uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
145 } __rte_cache_aligned;
147 /** A hash table structure. */
149 char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */
150 uint32_t entries; /**< Total table entries. */
151 uint32_t num_buckets; /**< Number of buckets in table. */
153 struct rte_ring *free_slots;
154 /**< Ring that stores all indexes of the free slots in the key table */
156 struct lcore_cache *local_free_slots;
157 /**< Local cache per lcore, storing some indexes of the free slots */
159 /* Fields used in lookup */
161 uint32_t key_len __rte_cache_aligned;
162 /**< Length of hash key. */
163 uint8_t hw_trans_mem_support;
164 /**< If hardware transactional memory is used. */
165 uint8_t use_local_cache;
166 /**< If multi-writer support is enabled, use local cache
167 * to allocate key-store slots.
169 uint8_t readwrite_concur_support;
170 /**< If read-write concurrency support is enabled */
171 uint8_t ext_table_support; /**< Enable extendable bucket table */
172 uint8_t no_free_on_del;
173 /**< If key index should be freed on calling rte_hash_del_xxx APIs.
174 * If this is set, rte_hash_free_key_with_position must be called to
175 * free the key index associated with the deleted entry.
176 * This flag is enabled by default.
178 uint8_t readwrite_concur_lf_support;
179 /**< If read-write concurrency lock free support is enabled */
180 uint8_t writer_takes_lock;
181 /**< Indicates if the writer threads need to take lock */
182 rte_hash_function hash_func; /**< Function used to calculate hash. */
183 uint32_t hash_func_init_val; /**< Init value used by hash_func. */
184 rte_hash_cmp_eq_t rte_hash_custom_cmp_eq;
185 /**< Custom function used to compare keys. */
186 enum cmp_jump_table_case cmp_jump_table_idx;
187 /**< Indicates which compare function to use. */
188 enum rte_hash_sig_compare_function sig_cmp_fn;
189 /**< Indicates which signature compare function to use. */
190 uint32_t bucket_bitmask;
191 /**< Bitmask for getting bucket index from hash signature. */
192 uint32_t key_entry_size; /**< Size of each key entry. */
194 void *key_store; /**< Table storing all keys and data */
195 struct rte_hash_bucket *buckets;
196 /**< Table with buckets storing all the hash values and key indexes
199 rte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */
200 struct rte_hash_bucket *buckets_ext; /**< Extra buckets array */
201 struct rte_ring *free_ext_bkts; /**< Ring of indexes of free buckets */
202 uint32_t *tbl_chng_cnt;
203 /**< Indicates if the hash table changed from last read. */
204 } __rte_cache_aligned;
207 struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */
208 uint32_t cur_bkt_idx;
210 struct queue_node *prev; /* Parent(bucket) in search path */
211 int prev_slot; /* Parent(slot) in search path */