File: | home/bhubbard/working/src/ceph/src/spdk/dpdk/lib/librte_hash/rte_cuckoo_hash.c |
Warning: | line 631, column 27 Access to field 'len' results in a dereference of a null pointer (loaded from variable 'cached_free_slots') |
[?] Use j/k keys for keyboard navigation
1 | /* SPDX-License-Identifier: BSD-3-Clause | |||
2 | * Copyright(c) 2010-2016 Intel Corporation | |||
3 | * Copyright(c) 2018 Arm Limited | |||
4 | */ | |||
5 | ||||
6 | #include <string.h> | |||
7 | #include <stdint.h> | |||
8 | #include <errno(*__errno_location ()).h> | |||
9 | #include <stdio.h> | |||
10 | #include <stdarg.h> | |||
11 | #include <sys/queue.h> | |||
12 | ||||
13 | #include <rte_common.h> | |||
14 | #include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */ | |||
15 | #include <rte_log.h> | |||
16 | #include <rte_prefetch.h> | |||
17 | #include <rte_branch_prediction.h> | |||
18 | #include <rte_malloc.h> | |||
19 | #include <rte_eal.h> | |||
20 | #include <rte_eal_memconfig.h> | |||
21 | #include <rte_per_lcore.h> | |||
22 | #include <rte_errno(per_lcore__rte_errno).h> | |||
23 | #include <rte_string_fns.h> | |||
24 | #include <rte_cpuflags.h> | |||
25 | #include <rte_rwlock.h> | |||
26 | #include <rte_spinlock.h> | |||
27 | #include <rte_ring.h> | |||
28 | #include <rte_compat.h> | |||
29 | #include <rte_vect.h> | |||
30 | ||||
31 | #include "rte_hash.h" | |||
32 | #include "rte_cuckoo_hash.h" | |||
33 | ||||
34 | #define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET)for (CURRENT_BKT = START_BUCKET; CURRENT_BKT != ((void*)0); CURRENT_BKT = CURRENT_BKT->next) \ | |||
35 | for (CURRENT_BKT = START_BUCKET; \ | |||
36 | CURRENT_BKT != NULL((void*)0); \ | |||
37 | CURRENT_BKT = CURRENT_BKT->next) | |||
38 | ||||
39 | TAILQ_HEAD(rte_hash_list, rte_tailq_entry)struct rte_hash_list { struct rte_tailq_entry *tqh_first; struct rte_tailq_entry * *tqh_last; }; | |||
40 | ||||
41 | static struct rte_tailq_elem rte_hash_tailq = { | |||
42 | .name = "RTE_HASH", | |||
43 | }; | |||
44 | EAL_REGISTER_TAILQ(rte_hash_tailq)static void __attribute__((constructor(65535), used)) tailqinitfn_rte_hash_tailq (void) { if (rte_eal_tailq_register(&rte_hash_tailq) < 0) __rte_panic(__func__, "Cannot initialize tailq: %s\n" "%.0s" , rte_hash_tailq.name, "dummy"); } | |||
45 | ||||
46 | struct rte_hash * | |||
47 | rte_hash_find_existing(const char *name) | |||
48 | { | |||
49 | struct rte_hash *h = NULL((void*)0); | |||
50 | struct rte_tailq_entry *te; | |||
51 | struct rte_hash_list *hash_list; | |||
52 | ||||
53 | hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list)(struct rte_hash_list *)&(rte_hash_tailq.head)->tailq_head; | |||
54 | ||||
55 | rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
56 | TAILQ_FOREACH(te, hash_list, next)for ((te) = ((hash_list)->tqh_first); (te); (te) = ((te)-> next.tqe_next)) { | |||
57 | h = (struct rte_hash *) te->data; | |||
58 | if (strncmp(name, h->name, RTE_HASH_NAMESIZE)(__extension__ (__builtin_constant_p (32) && ((__builtin_constant_p (name) && strlen (name) < ((size_t) (32))) || (__builtin_constant_p (h->name) && strlen (h->name) < ((size_t) ( 32)))) ? __extension__ ({ size_t __s1_len, __s2_len; (__builtin_constant_p (name) && __builtin_constant_p (h->name) && (__s1_len = __builtin_strlen (name), __s2_len = __builtin_strlen (h->name), (!((size_t)(const void *)((name) + 1) - (size_t )(const void *)(name) == 1) || __s1_len >= 4) && ( !((size_t)(const void *)((h->name) + 1) - (size_t)(const void *)(h->name) == 1) || __s2_len >= 4)) ? __builtin_strcmp (name, h->name) : (__builtin_constant_p (name) && ((size_t)(const void *)((name) + 1) - (size_t)(const void *) (name) == 1) && (__s1_len = __builtin_strlen (name), __s1_len < 4) ? (__builtin_constant_p (h->name) && ((size_t )(const void *)((h->name) + 1) - (size_t)(const void *)(h-> name) == 1) ? __builtin_strcmp (name, h->name) : (__extension__ ({ const unsigned char *__s2 = (const unsigned char *) (const char *) (h->name); int __result = (((const unsigned char * ) (const char *) (name))[0] - __s2[0]); if (__s1_len > 0 && __result == 0) { __result = (((const unsigned char *) (const char *) (name))[1] - __s2[1]); if (__s1_len > 1 && __result == 0) { __result = (((const unsigned char *) (const char *) (name))[2] - __s2[2]); if (__s1_len > 2 && __result == 0) __result = (((const unsigned char *) (const char *) (name))[3] - __s2[3]); } } __result; }))) : (__builtin_constant_p (h->name) && ((size_t)(const void *)((h->name) + 1) - (size_t)(const void *)(h->name) == 1) && ( __s2_len = __builtin_strlen (h->name), __s2_len < 4) ? ( __builtin_constant_p (name) && ((size_t)(const void * )((name) + 1) - (size_t)(const void *)(name) == 1) ? __builtin_strcmp (name, h->name) : (- (__extension__ ({ const unsigned char *__s2 = (const unsigned char *) (const char *) (name); int __result = (((const unsigned char *) (const char *) (h->name))[0] - __s2[0]); if (__s2_len > 0 && __result == 0) { __result = (((const unsigned char *) (const char *) (h->name))[1] - __s2[1]); if (__s2_len > 1 && __result == 0) { __result = (((const unsigned char *) (const char *) (h->name))[2] - __s2[2]); if (__s2_len > 2 && __result == 0) __result = (((const unsigned char *) (const char *) (h->name))[3] - __s2[3]); } } __result; })))) : __builtin_strcmp (name, h-> name)))); }) : strncmp (name, h->name, 32))) == 0) | |||
59 | break; | |||
60 | } | |||
61 | rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
62 | ||||
63 | if (te == NULL((void*)0)) { | |||
64 | rte_errno(per_lcore__rte_errno) = ENOENT2; | |||
65 | return NULL((void*)0); | |||
66 | } | |||
67 | return h; | |||
68 | } | |||
69 | ||||
70 | static inline struct rte_hash_bucket * | |||
71 | rte_hash_get_last_bkt(struct rte_hash_bucket *lst_bkt) | |||
72 | { | |||
73 | while (lst_bkt->next != NULL((void*)0)) | |||
74 | lst_bkt = lst_bkt->next; | |||
75 | return lst_bkt; | |||
76 | } | |||
77 | ||||
78 | void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func) | |||
79 | { | |||
80 | h->cmp_jump_table_idx = KEY_CUSTOM; | |||
81 | h->rte_hash_custom_cmp_eq = func; | |||
82 | } | |||
83 | ||||
84 | static inline int | |||
85 | rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h) | |||
86 | { | |||
87 | if (h->cmp_jump_table_idx == KEY_CUSTOM) | |||
88 | return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len); | |||
89 | else | |||
90 | return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len); | |||
91 | } | |||
92 | ||||
93 | /* | |||
94 | * We use higher 16 bits of hash as the signature value stored in table. | |||
95 | * We use the lower bits for the primary bucket | |||
96 | * location. Then we XOR primary bucket location and the signature | |||
97 | * to get the secondary bucket location. This is same as | |||
98 | * proposed in Bin Fan, et al's paper | |||
99 | * "MemC3: Compact and Concurrent MemCache with Dumber Caching and | |||
100 | * Smarter Hashing". The benefit to use | |||
101 | * XOR is that one could derive the alternative bucket location | |||
102 | * by only using the current bucket location and the signature. | |||
103 | */ | |||
104 | static inline uint16_t | |||
105 | get_short_sig(const hash_sig_t hash) | |||
106 | { | |||
107 | return hash >> 16; | |||
108 | } | |||
109 | ||||
110 | static inline uint32_t | |||
111 | get_prim_bucket_index(const struct rte_hash *h, const hash_sig_t hash) | |||
112 | { | |||
113 | return hash & h->bucket_bitmask; | |||
114 | } | |||
115 | ||||
116 | static inline uint32_t | |||
117 | get_alt_bucket_index(const struct rte_hash *h, | |||
118 | uint32_t cur_bkt_idx, uint16_t sig) | |||
119 | { | |||
120 | return (cur_bkt_idx ^ sig) & h->bucket_bitmask; | |||
121 | } | |||
122 | ||||
123 | struct rte_hash * | |||
124 | rte_hash_create(const struct rte_hash_parameters *params) | |||
125 | { | |||
126 | struct rte_hash *h = NULL((void*)0); | |||
127 | struct rte_tailq_entry *te = NULL((void*)0); | |||
128 | struct rte_hash_list *hash_list; | |||
129 | struct rte_ring *r = NULL((void*)0); | |||
130 | struct rte_ring *r_ext = NULL((void*)0); | |||
131 | char hash_name[RTE_HASH_NAMESIZE32]; | |||
132 | void *k = NULL((void*)0); | |||
133 | void *buckets = NULL((void*)0); | |||
134 | void *buckets_ext = NULL((void*)0); | |||
135 | char ring_name[RTE_RING_NAMESIZE(32 - sizeof("RG_") + 1)]; | |||
136 | char ext_ring_name[RTE_RING_NAMESIZE(32 - sizeof("RG_") + 1)]; | |||
137 | unsigned num_key_slots; | |||
138 | unsigned i; | |||
139 | unsigned int hw_trans_mem_support = 0, use_local_cache = 0; | |||
140 | unsigned int ext_table_support = 0; | |||
141 | unsigned int readwrite_concur_support = 0; | |||
142 | unsigned int writer_takes_lock = 0; | |||
143 | unsigned int no_free_on_del = 0; | |||
144 | uint32_t *ext_bkt_to_free = NULL((void*)0); | |||
145 | uint32_t *tbl_chng_cnt = NULL((void*)0); | |||
146 | unsigned int readwrite_concur_lf_support = 0; | |||
147 | ||||
148 | rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; | |||
149 | ||||
150 | hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list)(struct rte_hash_list *)&(rte_hash_tailq.head)->tailq_head; | |||
151 | ||||
152 | if (params == NULL((void*)0)) { | |||
153 | RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n")rte_log(4U, 6, "HASH" ": " "rte_hash_create has no parameters\n" ); | |||
154 | return NULL((void*)0); | |||
155 | } | |||
156 | ||||
157 | /* Check for valid parameters */ | |||
158 | if ((params->entries > RTE_HASH_ENTRIES_MAX(1 << 30)) || | |||
159 | (params->entries < RTE_HASH_BUCKET_ENTRIES8) || | |||
160 | (params->key_len == 0)) { | |||
161 | rte_errno(per_lcore__rte_errno) = EINVAL22; | |||
162 | RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n")rte_log(4U, 6, "HASH" ": " "rte_hash_create has invalid parameters\n" ); | |||
163 | return NULL((void*)0); | |||
164 | } | |||
165 | ||||
166 | /* Validate correct usage of extra options */ | |||
167 | if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY0x04) && | |||
168 | (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF0x20)) { | |||
169 | rte_errno(per_lcore__rte_errno) = EINVAL22; | |||
170 | RTE_LOG(ERR, HASH, "rte_hash_create: choose rw concurrency or "rte_log(4U, 6, "HASH" ": " "rte_hash_create: choose rw concurrency or " "rw concurrency lock free\n") | |||
171 | "rw concurrency lock free\n")rte_log(4U, 6, "HASH" ": " "rte_hash_create: choose rw concurrency or " "rw concurrency lock free\n"); | |||
172 | return NULL((void*)0); | |||
173 | } | |||
174 | ||||
175 | /* Check extra flags field to check extra options. */ | |||
176 | if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT0x01) | |||
177 | hw_trans_mem_support = 1; | |||
178 | ||||
179 | if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD0x02) { | |||
180 | use_local_cache = 1; | |||
181 | writer_takes_lock = 1; | |||
182 | } | |||
183 | ||||
184 | if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY0x04) { | |||
185 | readwrite_concur_support = 1; | |||
186 | writer_takes_lock = 1; | |||
187 | } | |||
188 | ||||
189 | if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE0x08) | |||
190 | ext_table_support = 1; | |||
191 | ||||
192 | if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL0x10) | |||
193 | no_free_on_del = 1; | |||
194 | ||||
195 | if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF0x20) { | |||
196 | readwrite_concur_lf_support = 1; | |||
197 | /* Enable not freeing internal memory/index on delete */ | |||
198 | no_free_on_del = 1; | |||
199 | } | |||
200 | ||||
201 | /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ | |||
202 | if (use_local_cache) | |||
203 | /* | |||
204 | * Increase number of slots by total number of indices | |||
205 | * that can be stored in the lcore caches | |||
206 | * except for the first cache | |||
207 | */ | |||
208 | num_key_slots = params->entries + (RTE_MAX_LCORE128 - 1) * | |||
209 | (LCORE_CACHE_SIZE64 - 1) + 1; | |||
210 | else | |||
211 | num_key_slots = params->entries + 1; | |||
212 | ||||
213 | snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name); | |||
214 | /* Create ring (Dummy slot index is not enqueued) */ | |||
215 | r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots), | |||
216 | params->socket_id, 0); | |||
217 | if (r == NULL((void*)0)) { | |||
218 | RTE_LOG(ERR, HASH, "memory allocation failed\n")rte_log(4U, 6, "HASH" ": " "memory allocation failed\n"); | |||
219 | goto err; | |||
220 | } | |||
221 | ||||
222 | const uint32_t num_buckets = rte_align32pow2(params->entries) / | |||
223 | RTE_HASH_BUCKET_ENTRIES8; | |||
224 | ||||
225 | /* Create ring for extendable buckets. */ | |||
226 | if (ext_table_support) { | |||
227 | snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s", | |||
228 | params->name); | |||
229 | r_ext = rte_ring_create(ext_ring_name, | |||
230 | rte_align32pow2(num_buckets + 1), | |||
231 | params->socket_id, 0); | |||
232 | ||||
233 | if (r_ext == NULL((void*)0)) { | |||
234 | RTE_LOG(ERR, HASH, "ext buckets memory allocation "rte_log(4U, 6, "HASH" ": " "ext buckets memory allocation " "failed\n" ) | |||
235 | "failed\n")rte_log(4U, 6, "HASH" ": " "ext buckets memory allocation " "failed\n" ); | |||
236 | goto err; | |||
237 | } | |||
238 | } | |||
239 | ||||
240 | snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); | |||
241 | ||||
242 | rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
243 | ||||
244 | /* guarantee there's no existing: this is normally already checked | |||
245 | * by ring creation above */ | |||
246 | TAILQ_FOREACH(te, hash_list, next)for ((te) = ((hash_list)->tqh_first); (te); (te) = ((te)-> next.tqe_next)) { | |||
247 | h = (struct rte_hash *) te->data; | |||
248 | if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE)(__extension__ (__builtin_constant_p (32) && ((__builtin_constant_p (params->name) && strlen (params->name) < ( (size_t) (32))) || (__builtin_constant_p (h->name) && strlen (h->name) < ((size_t) (32)))) ? __extension__ ( { size_t __s1_len, __s2_len; (__builtin_constant_p (params-> name) && __builtin_constant_p (h->name) && (__s1_len = __builtin_strlen (params->name), __s2_len = __builtin_strlen (h->name), (!((size_t)(const void *)((params->name) + 1 ) - (size_t)(const void *)(params->name) == 1) || __s1_len >= 4) && (!((size_t)(const void *)((h->name) + 1) - (size_t)(const void *)(h->name) == 1) || __s2_len >= 4)) ? __builtin_strcmp (params->name, h->name) : (__builtin_constant_p (params->name) && ((size_t)(const void *)((params ->name) + 1) - (size_t)(const void *)(params->name) == 1 ) && (__s1_len = __builtin_strlen (params->name), __s1_len < 4) ? (__builtin_constant_p (h->name) && ((size_t )(const void *)((h->name) + 1) - (size_t)(const void *)(h-> name) == 1) ? __builtin_strcmp (params->name, h->name) : (__extension__ ({ const unsigned char *__s2 = (const unsigned char *) (const char *) (h->name); int __result = (((const unsigned char *) (const char *) (params->name))[0] - __s2 [0]); if (__s1_len > 0 && __result == 0) { __result = (((const unsigned char *) (const char *) (params->name) )[1] - __s2[1]); if (__s1_len > 1 && __result == 0 ) { __result = (((const unsigned char *) (const char *) (params ->name))[2] - __s2[2]); if (__s1_len > 2 && __result == 0) __result = (((const unsigned char *) (const char *) (params ->name))[3] - __s2[3]); } } __result; }))) : (__builtin_constant_p (h->name) && ((size_t)(const void *)((h->name) + 1) - (size_t)(const void *)(h->name) == 1) && ( __s2_len = __builtin_strlen (h->name), __s2_len < 4) ? ( __builtin_constant_p (params->name) && ((size_t)(const void *)((params->name) + 1) - (size_t)(const void *)(params ->name) == 1) ? __builtin_strcmp (params->name, h->name ) : (- (__extension__ ({ const unsigned char *__s2 = (const unsigned char *) (const char *) (params->name); int __result = ((( const unsigned char *) (const char *) (h->name))[0] - __s2 [0]); if (__s2_len > 0 && __result == 0) { __result = (((const unsigned char *) (const char *) (h->name))[1] - __s2[1]); if (__s2_len > 1 && __result == 0) { __result = (((const unsigned char *) (const char *) (h->name))[2] - __s2[2]); if (__s2_len > 2 && __result == 0) __result = (((const unsigned char *) (const char *) (h->name))[3] - __s2[3]); } } __result; })))) : __builtin_strcmp (params-> name, h->name)))); }) : strncmp (params->name, h->name , 32))) == 0) | |||
249 | break; | |||
250 | } | |||
251 | h = NULL((void*)0); | |||
252 | if (te != NULL((void*)0)) { | |||
253 | rte_errno(per_lcore__rte_errno) = EEXIST17; | |||
254 | te = NULL((void*)0); | |||
255 | goto err_unlock; | |||
256 | } | |||
257 | ||||
258 | te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0); | |||
259 | if (te == NULL((void*)0)) { | |||
260 | RTE_LOG(ERR, HASH, "tailq entry allocation failed\n")rte_log(4U, 6, "HASH" ": " "tailq entry allocation failed\n"); | |||
261 | goto err_unlock; | |||
262 | } | |||
263 | ||||
264 | h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash), | |||
265 | RTE_CACHE_LINE_SIZE64, params->socket_id); | |||
266 | ||||
267 | if (h == NULL((void*)0)) { | |||
268 | RTE_LOG(ERR, HASH, "memory allocation failed\n")rte_log(4U, 6, "HASH" ": " "memory allocation failed\n"); | |||
269 | goto err_unlock; | |||
270 | } | |||
271 | ||||
272 | buckets = rte_zmalloc_socket(NULL((void*)0), | |||
273 | num_buckets * sizeof(struct rte_hash_bucket), | |||
274 | RTE_CACHE_LINE_SIZE64, params->socket_id); | |||
275 | ||||
276 | if (buckets == NULL((void*)0)) { | |||
277 | RTE_LOG(ERR, HASH, "buckets memory allocation failed\n")rte_log(4U, 6, "HASH" ": " "buckets memory allocation failed\n" ); | |||
278 | goto err_unlock; | |||
279 | } | |||
280 | ||||
281 | /* Allocate same number of extendable buckets */ | |||
282 | if (ext_table_support) { | |||
283 | buckets_ext = rte_zmalloc_socket(NULL((void*)0), | |||
284 | num_buckets * sizeof(struct rte_hash_bucket), | |||
285 | RTE_CACHE_LINE_SIZE64, params->socket_id); | |||
286 | if (buckets_ext == NULL((void*)0)) { | |||
287 | RTE_LOG(ERR, HASH, "ext buckets memory allocation "rte_log(4U, 6, "HASH" ": " "ext buckets memory allocation " "failed\n" ) | |||
288 | "failed\n")rte_log(4U, 6, "HASH" ": " "ext buckets memory allocation " "failed\n" ); | |||
289 | goto err_unlock; | |||
290 | } | |||
291 | /* Populate ext bkt ring. We reserve 0 similar to the | |||
292 | * key-data slot, just in case in future we want to | |||
293 | * use bucket index for the linked list and 0 means NULL | |||
294 | * for next bucket | |||
295 | */ | |||
296 | for (i = 1; i <= num_buckets; i++) | |||
297 | rte_ring_sp_enqueue(r_ext, (void *)((uintptr_t) i)); | |||
298 | ||||
299 | if (readwrite_concur_lf_support) { | |||
300 | ext_bkt_to_free = rte_zmalloc(NULL((void*)0), sizeof(uint32_t) * | |||
301 | num_key_slots, 0); | |||
302 | if (ext_bkt_to_free == NULL((void*)0)) { | |||
303 | RTE_LOG(ERR, HASH, "ext bkt to free memory allocation "rte_log(4U, 6, "HASH" ": " "ext bkt to free memory allocation " "failed\n") | |||
304 | "failed\n")rte_log(4U, 6, "HASH" ": " "ext bkt to free memory allocation " "failed\n"); | |||
305 | goto err_unlock; | |||
306 | } | |||
307 | } | |||
308 | } | |||
309 | ||||
310 | const uint32_t key_entry_size = | |||
311 | RTE_ALIGN(sizeof(struct rte_hash_key) + params->key_len,(__typeof__(((sizeof(struct rte_hash_key) + params->key_len ) + ((__typeof__(sizeof(struct rte_hash_key) + params->key_len )) (16) - 1))))((((sizeof(struct rte_hash_key) + params->key_len ) + ((__typeof__(sizeof(struct rte_hash_key) + params->key_len )) (16) - 1))) & (~((__typeof__(((sizeof(struct rte_hash_key ) + params->key_len) + ((__typeof__(sizeof(struct rte_hash_key ) + params->key_len)) (16) - 1))))((16) - 1)))) | |||
312 | KEY_ALIGNMENT)(__typeof__(((sizeof(struct rte_hash_key) + params->key_len ) + ((__typeof__(sizeof(struct rte_hash_key) + params->key_len )) (16) - 1))))((((sizeof(struct rte_hash_key) + params->key_len ) + ((__typeof__(sizeof(struct rte_hash_key) + params->key_len )) (16) - 1))) & (~((__typeof__(((sizeof(struct rte_hash_key ) + params->key_len) + ((__typeof__(sizeof(struct rte_hash_key ) + params->key_len)) (16) - 1))))((16) - 1)))); | |||
313 | const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots; | |||
314 | ||||
315 | k = rte_zmalloc_socket(NULL((void*)0), key_tbl_size, | |||
316 | RTE_CACHE_LINE_SIZE64, params->socket_id); | |||
317 | ||||
318 | if (k == NULL((void*)0)) { | |||
319 | RTE_LOG(ERR, HASH, "memory allocation failed\n")rte_log(4U, 6, "HASH" ": " "memory allocation failed\n"); | |||
320 | goto err_unlock; | |||
321 | } | |||
322 | ||||
323 | tbl_chng_cnt = rte_zmalloc_socket(NULL((void*)0), sizeof(uint32_t), | |||
324 | RTE_CACHE_LINE_SIZE64, params->socket_id); | |||
325 | ||||
326 | if (tbl_chng_cnt == NULL((void*)0)) { | |||
327 | RTE_LOG(ERR, HASH, "memory allocation failed\n")rte_log(4U, 6, "HASH" ": " "memory allocation failed\n"); | |||
328 | goto err_unlock; | |||
329 | } | |||
330 | ||||
331 | /* | |||
332 | * If x86 architecture is used, select appropriate compare function, | |||
333 | * which may use x86 intrinsics, otherwise use memcmp | |||
334 | */ | |||
335 | #if defined(RTE_ARCH_X861) || defined(RTE_ARCH_ARM64) | |||
336 | /* Select function to compare keys */ | |||
337 | switch (params->key_len) { | |||
338 | case 16: | |||
339 | h->cmp_jump_table_idx = KEY_16_BYTES; | |||
340 | break; | |||
341 | case 32: | |||
342 | h->cmp_jump_table_idx = KEY_32_BYTES; | |||
343 | break; | |||
344 | case 48: | |||
345 | h->cmp_jump_table_idx = KEY_48_BYTES; | |||
346 | break; | |||
347 | case 64: | |||
348 | h->cmp_jump_table_idx = KEY_64_BYTES; | |||
349 | break; | |||
350 | case 80: | |||
351 | h->cmp_jump_table_idx = KEY_80_BYTES; | |||
352 | break; | |||
353 | case 96: | |||
354 | h->cmp_jump_table_idx = KEY_96_BYTES; | |||
355 | break; | |||
356 | case 112: | |||
357 | h->cmp_jump_table_idx = KEY_112_BYTES; | |||
358 | break; | |||
359 | case 128: | |||
360 | h->cmp_jump_table_idx = KEY_128_BYTES; | |||
361 | break; | |||
362 | default: | |||
363 | /* If key is not multiple of 16, use generic memcmp */ | |||
364 | h->cmp_jump_table_idx = KEY_OTHER_BYTES; | |||
365 | } | |||
366 | #else | |||
367 | h->cmp_jump_table_idx = KEY_OTHER_BYTES; | |||
368 | #endif | |||
369 | ||||
370 | if (use_local_cache) { | |||
371 | h->local_free_slots = rte_zmalloc_socket(NULL((void*)0), | |||
372 | sizeof(struct lcore_cache) * RTE_MAX_LCORE128, | |||
373 | RTE_CACHE_LINE_SIZE64, params->socket_id); | |||
374 | } | |||
375 | ||||
376 | /* Default hash function */ | |||
377 | #if defined(RTE_ARCH_X861) | |||
378 | default_hash_func = (rte_hash_function)rte_hash_crc; | |||
379 | #elif defined(RTE_ARCH_ARM64) | |||
380 | if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32)) | |||
381 | default_hash_func = (rte_hash_function)rte_hash_crc; | |||
382 | #endif | |||
383 | /* Setup hash context */ | |||
384 | strlcpy(h->name, params->name, sizeof(h->name))rte_strlcpy(h->name, params->name, sizeof(h->name)); | |||
385 | h->entries = params->entries; | |||
386 | h->key_len = params->key_len; | |||
387 | h->key_entry_size = key_entry_size; | |||
388 | h->hash_func_init_val = params->hash_func_init_val; | |||
389 | ||||
390 | h->num_buckets = num_buckets; | |||
391 | h->bucket_bitmask = h->num_buckets - 1; | |||
392 | h->buckets = buckets; | |||
393 | h->buckets_ext = buckets_ext; | |||
394 | h->free_ext_bkts = r_ext; | |||
395 | h->hash_func = (params->hash_func == NULL((void*)0)) ? | |||
396 | default_hash_func : params->hash_func; | |||
397 | h->key_store = k; | |||
398 | h->free_slots = r; | |||
399 | h->ext_bkt_to_free = ext_bkt_to_free; | |||
400 | h->tbl_chng_cnt = tbl_chng_cnt; | |||
401 | *h->tbl_chng_cnt = 0; | |||
402 | h->hw_trans_mem_support = hw_trans_mem_support; | |||
403 | h->use_local_cache = use_local_cache; | |||
404 | h->readwrite_concur_support = readwrite_concur_support; | |||
405 | h->ext_table_support = ext_table_support; | |||
406 | h->writer_takes_lock = writer_takes_lock; | |||
407 | h->no_free_on_del = no_free_on_del; | |||
408 | h->readwrite_concur_lf_support = readwrite_concur_lf_support; | |||
409 | ||||
410 | #if defined(RTE_ARCH_X861) | |||
411 | if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2)) | |||
412 | h->sig_cmp_fn = RTE_HASH_COMPARE_SSE; | |||
413 | else | |||
414 | #elif defined(RTE_ARCH_ARM64) | |||
415 | if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON)) | |||
416 | h->sig_cmp_fn = RTE_HASH_COMPARE_NEON; | |||
417 | else | |||
418 | #endif | |||
419 | h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR; | |||
420 | ||||
421 | /* Writer threads need to take the lock when: | |||
422 | * 1) RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY is enabled OR | |||
423 | * 2) RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD is enabled | |||
424 | */ | |||
425 | if (h->writer_takes_lock) { | |||
426 | h->readwrite_lock = rte_malloc(NULL((void*)0), sizeof(rte_rwlock_t), | |||
427 | RTE_CACHE_LINE_SIZE64); | |||
428 | if (h->readwrite_lock == NULL((void*)0)) | |||
429 | goto err_unlock; | |||
430 | ||||
431 | rte_rwlock_init(h->readwrite_lock); | |||
432 | } | |||
433 | ||||
434 | /* Populate free slots ring. Entry zero is reserved for key misses. */ | |||
435 | for (i = 1; i < num_key_slots; i++) | |||
436 | rte_ring_sp_enqueue(r, (void *)((uintptr_t) i)); | |||
437 | ||||
438 | te->data = (void *) h; | |||
439 | TAILQ_INSERT_TAIL(hash_list, te, next)do { (te)->next.tqe_next = ((void*)0); (te)->next.tqe_prev = (hash_list)->tqh_last; *(hash_list)->tqh_last = (te) ; (hash_list)->tqh_last = &(te)->next.tqe_next; } while ( 0); | |||
440 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
441 | ||||
442 | return h; | |||
443 | err_unlock: | |||
444 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
445 | err: | |||
446 | rte_ring_free(r); | |||
447 | rte_ring_free(r_ext); | |||
448 | rte_free(te); | |||
449 | rte_free(h); | |||
450 | rte_free(buckets); | |||
451 | rte_free(buckets_ext); | |||
452 | rte_free(k); | |||
453 | rte_free(tbl_chng_cnt); | |||
454 | rte_free(ext_bkt_to_free); | |||
455 | return NULL((void*)0); | |||
456 | } | |||
457 | ||||
458 | void | |||
459 | rte_hash_free(struct rte_hash *h) | |||
460 | { | |||
461 | struct rte_tailq_entry *te; | |||
462 | struct rte_hash_list *hash_list; | |||
463 | ||||
464 | if (h == NULL((void*)0)) | |||
465 | return; | |||
466 | ||||
467 | hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list)(struct rte_hash_list *)&(rte_hash_tailq.head)->tailq_head; | |||
468 | ||||
469 | rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
470 | ||||
471 | /* find out tailq entry */ | |||
472 | TAILQ_FOREACH(te, hash_list, next)for ((te) = ((hash_list)->tqh_first); (te); (te) = ((te)-> next.tqe_next)) { | |||
473 | if (te->data == (void *) h) | |||
474 | break; | |||
475 | } | |||
476 | ||||
477 | if (te == NULL((void*)0)) { | |||
478 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
479 | return; | |||
480 | } | |||
481 | ||||
482 | TAILQ_REMOVE(hash_list, te, next)do { if (((te)->next.tqe_next) != ((void*)0)) (te)->next .tqe_next->next.tqe_prev = (te)->next.tqe_prev; else (hash_list )->tqh_last = (te)->next.tqe_prev; *(te)->next.tqe_prev = (te)->next.tqe_next; } while ( 0); | |||
483 | ||||
484 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK(&rte_eal_get_configuration()->mem_config->qlock)); | |||
485 | ||||
486 | if (h->use_local_cache) | |||
487 | rte_free(h->local_free_slots); | |||
488 | if (h->writer_takes_lock) | |||
489 | rte_free(h->readwrite_lock); | |||
490 | rte_ring_free(h->free_slots); | |||
491 | rte_ring_free(h->free_ext_bkts); | |||
492 | rte_free(h->key_store); | |||
493 | rte_free(h->buckets); | |||
494 | rte_free(h->buckets_ext); | |||
495 | rte_free(h->tbl_chng_cnt); | |||
496 | rte_free(h->ext_bkt_to_free); | |||
497 | rte_free(h); | |||
498 | rte_free(te); | |||
499 | } | |||
500 | ||||
501 | hash_sig_t | |||
502 | rte_hash_hash(const struct rte_hash *h, const void *key) | |||
503 | { | |||
504 | /* calc hash result by key */ | |||
505 | return h->hash_func(key, h->key_len, h->hash_func_init_val); | |||
506 | } | |||
507 | ||||
508 | int32_t | |||
509 | rte_hash_count(const struct rte_hash *h) | |||
510 | { | |||
511 | uint32_t tot_ring_cnt, cached_cnt = 0; | |||
512 | uint32_t i, ret; | |||
513 | ||||
514 | if (h == NULL((void*)0)) | |||
515 | return -EINVAL22; | |||
516 | ||||
517 | if (h->use_local_cache) { | |||
518 | tot_ring_cnt = h->entries + (RTE_MAX_LCORE128 - 1) * | |||
519 | (LCORE_CACHE_SIZE64 - 1); | |||
520 | for (i = 0; i < RTE_MAX_LCORE128; i++) | |||
521 | cached_cnt += h->local_free_slots[i].len; | |||
522 | ||||
523 | ret = tot_ring_cnt - rte_ring_count(h->free_slots) - | |||
524 | cached_cnt; | |||
525 | } else { | |||
526 | tot_ring_cnt = h->entries; | |||
527 | ret = tot_ring_cnt - rte_ring_count(h->free_slots); | |||
528 | } | |||
529 | return ret; | |||
530 | } | |||
531 | ||||
532 | /* Read write locks implemented using rte_rwlock */ | |||
533 | static inline void | |||
534 | __hash_rw_writer_lock(const struct rte_hash *h) | |||
535 | { | |||
536 | if (h->writer_takes_lock && h->hw_trans_mem_support) | |||
537 | rte_rwlock_write_lock_tm(h->readwrite_lock); | |||
538 | else if (h->writer_takes_lock) | |||
539 | rte_rwlock_write_lock(h->readwrite_lock); | |||
540 | } | |||
541 | ||||
542 | static inline void | |||
543 | __hash_rw_reader_lock(const struct rte_hash *h) | |||
544 | { | |||
545 | if (h->readwrite_concur_support && h->hw_trans_mem_support) | |||
546 | rte_rwlock_read_lock_tm(h->readwrite_lock); | |||
547 | else if (h->readwrite_concur_support) | |||
548 | rte_rwlock_read_lock(h->readwrite_lock); | |||
549 | } | |||
550 | ||||
551 | static inline void | |||
552 | __hash_rw_writer_unlock(const struct rte_hash *h) | |||
553 | { | |||
554 | if (h->writer_takes_lock && h->hw_trans_mem_support) | |||
555 | rte_rwlock_write_unlock_tm(h->readwrite_lock); | |||
556 | else if (h->writer_takes_lock) | |||
557 | rte_rwlock_write_unlock(h->readwrite_lock); | |||
558 | } | |||
559 | ||||
560 | static inline void | |||
561 | __hash_rw_reader_unlock(const struct rte_hash *h) | |||
562 | { | |||
563 | if (h->readwrite_concur_support && h->hw_trans_mem_support) | |||
564 | rte_rwlock_read_unlock_tm(h->readwrite_lock); | |||
565 | else if (h->readwrite_concur_support) | |||
566 | rte_rwlock_read_unlock(h->readwrite_lock); | |||
567 | } | |||
568 | ||||
569 | void | |||
570 | rte_hash_reset(struct rte_hash *h) | |||
571 | { | |||
572 | void *ptr; | |||
573 | uint32_t tot_ring_cnt, i; | |||
574 | ||||
575 | if (h == NULL((void*)0)) | |||
576 | return; | |||
577 | ||||
578 | __hash_rw_writer_lock(h); | |||
579 | memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket)); | |||
580 | memset(h->key_store, 0, h->key_entry_size * (h->entries + 1)); | |||
581 | *h->tbl_chng_cnt = 0; | |||
582 | ||||
583 | /* clear the free ring */ | |||
584 | while (rte_ring_dequeue(h->free_slots, &ptr) == 0) | |||
585 | continue; | |||
586 | ||||
587 | /* clear free extendable bucket ring and memory */ | |||
588 | if (h->ext_table_support) { | |||
589 | memset(h->buckets_ext, 0, h->num_buckets * | |||
590 | sizeof(struct rte_hash_bucket)); | |||
591 | while (rte_ring_dequeue(h->free_ext_bkts, &ptr) == 0) | |||
592 | continue; | |||
593 | } | |||
594 | ||||
595 | /* Repopulate the free slots ring. Entry zero is reserved for key misses */ | |||
596 | if (h->use_local_cache) | |||
597 | tot_ring_cnt = h->entries + (RTE_MAX_LCORE128 - 1) * | |||
598 | (LCORE_CACHE_SIZE64 - 1); | |||
599 | else | |||
600 | tot_ring_cnt = h->entries; | |||
601 | ||||
602 | for (i = 1; i < tot_ring_cnt + 1; i++) | |||
603 | rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i)); | |||
604 | ||||
605 | /* Repopulate the free ext bkt ring. */ | |||
606 | if (h->ext_table_support) { | |||
607 | for (i = 1; i <= h->num_buckets; i++) | |||
608 | rte_ring_sp_enqueue(h->free_ext_bkts, | |||
609 | (void *)((uintptr_t) i)); | |||
610 | } | |||
611 | ||||
612 | if (h->use_local_cache) { | |||
613 | /* Reset local caches per lcore */ | |||
614 | for (i = 0; i < RTE_MAX_LCORE128; i++) | |||
615 | h->local_free_slots[i].len = 0; | |||
616 | } | |||
617 | __hash_rw_writer_unlock(h); | |||
618 | } | |||
619 | ||||
620 | /* | |||
621 | * Function called to enqueue back an index in the cache/ring, | |||
622 | * as slot has not being used and it can be used in the | |||
623 | * next addition attempt. | |||
624 | */ | |||
625 | static inline void | |||
626 | enqueue_slot_back(const struct rte_hash *h, | |||
627 | struct lcore_cache *cached_free_slots, | |||
628 | void *slot_id) | |||
629 | { | |||
630 | if (h->use_local_cache) { | |||
631 | cached_free_slots->objs[cached_free_slots->len] = slot_id; | |||
| ||||
632 | cached_free_slots->len++; | |||
633 | } else | |||
634 | rte_ring_sp_enqueue(h->free_slots, slot_id); | |||
635 | } | |||
636 | ||||
637 | /* Search a key from bucket and update its data. | |||
638 | * Writer holds the lock before calling this. | |||
639 | */ | |||
640 | static inline int32_t | |||
641 | search_and_update(const struct rte_hash *h, void *data, const void *key, | |||
642 | struct rte_hash_bucket *bkt, uint16_t sig) | |||
643 | { | |||
644 | int i; | |||
645 | struct rte_hash_key *k, *keys = h->key_store; | |||
646 | ||||
647 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
648 | if (bkt->sig_current[i] == sig) { | |||
649 | k = (struct rte_hash_key *) ((char *)keys + | |||
650 | bkt->key_idx[i] * h->key_entry_size); | |||
651 | if (rte_hash_cmp_eq(key, k->key, h) == 0) { | |||
652 | /* 'pdata' acts as the synchronization point | |||
653 | * when an existing hash entry is updated. | |||
654 | * Key is not updated in this case. | |||
655 | */ | |||
656 | __atomic_store_n(&k->pdata, | |||
657 | data, | |||
658 | __ATOMIC_RELEASE3); | |||
659 | /* | |||
660 | * Return index where key is stored, | |||
661 | * subtracting the first dummy index | |||
662 | */ | |||
663 | return bkt->key_idx[i] - 1; | |||
664 | } | |||
665 | } | |||
666 | } | |||
667 | return -1; | |||
668 | } | |||
669 | ||||
670 | /* Only tries to insert at one bucket (@prim_bkt) without trying to push | |||
671 | * buckets around. | |||
672 | * return 1 if matching existing key, return 0 if succeeds, return -1 for no | |||
673 | * empty entry. | |||
674 | */ | |||
675 | static inline int32_t | |||
676 | rte_hash_cuckoo_insert_mw(const struct rte_hash *h, | |||
677 | struct rte_hash_bucket *prim_bkt, | |||
678 | struct rte_hash_bucket *sec_bkt, | |||
679 | const struct rte_hash_key *key, void *data, | |||
680 | uint16_t sig, uint32_t new_idx, | |||
681 | int32_t *ret_val) | |||
682 | { | |||
683 | unsigned int i; | |||
684 | struct rte_hash_bucket *cur_bkt; | |||
685 | int32_t ret; | |||
686 | ||||
687 | __hash_rw_writer_lock(h); | |||
688 | /* Check if key was inserted after last check but before this | |||
689 | * protected region in case of inserting duplicated keys. | |||
690 | */ | |||
691 | ret = search_and_update(h, data, key, prim_bkt, sig); | |||
692 | if (ret != -1) { | |||
693 | __hash_rw_writer_unlock(h); | |||
694 | *ret_val = ret; | |||
695 | return 1; | |||
696 | } | |||
697 | ||||
698 | FOR_EACH_BUCKET(cur_bkt, sec_bkt)for (cur_bkt = sec_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
699 | ret = search_and_update(h, data, key, cur_bkt, sig); | |||
700 | if (ret != -1) { | |||
701 | __hash_rw_writer_unlock(h); | |||
702 | *ret_val = ret; | |||
703 | return 1; | |||
704 | } | |||
705 | } | |||
706 | ||||
707 | /* Insert new entry if there is room in the primary | |||
708 | * bucket. | |||
709 | */ | |||
710 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
711 | /* Check if slot is available */ | |||
712 | if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)__builtin_expect(!!(prim_bkt->key_idx[i] == 0), 1)) { | |||
713 | prim_bkt->sig_current[i] = sig; | |||
714 | /* Key can be of arbitrary length, so it is | |||
715 | * not possible to store it atomically. | |||
716 | * Hence the new key element's memory stores | |||
717 | * (key as well as data) should be complete | |||
718 | * before it is referenced. | |||
719 | */ | |||
720 | __atomic_store_n(&prim_bkt->key_idx[i], | |||
721 | new_idx, | |||
722 | __ATOMIC_RELEASE3); | |||
723 | break; | |||
724 | } | |||
725 | } | |||
726 | __hash_rw_writer_unlock(h); | |||
727 | ||||
728 | if (i != RTE_HASH_BUCKET_ENTRIES8) | |||
729 | return 0; | |||
730 | ||||
731 | /* no empty entry */ | |||
732 | return -1; | |||
733 | } | |||
734 | ||||
735 | /* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill | |||
736 | * the path head with new entry (sig, alt_hash, new_idx) | |||
737 | * return 1 if matched key found, return -1 if cuckoo path invalided and fail, | |||
738 | * return 0 if succeeds. | |||
739 | */ | |||
740 | static inline int | |||
741 | rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, | |||
742 | struct rte_hash_bucket *bkt, | |||
743 | struct rte_hash_bucket *alt_bkt, | |||
744 | const struct rte_hash_key *key, void *data, | |||
745 | struct queue_node *leaf, uint32_t leaf_slot, | |||
746 | uint16_t sig, uint32_t new_idx, | |||
747 | int32_t *ret_val) | |||
748 | { | |||
749 | uint32_t prev_alt_bkt_idx; | |||
750 | struct rte_hash_bucket *cur_bkt; | |||
751 | struct queue_node *prev_node, *curr_node = leaf; | |||
752 | struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt; | |||
753 | uint32_t prev_slot, curr_slot = leaf_slot; | |||
754 | int32_t ret; | |||
755 | ||||
756 | __hash_rw_writer_lock(h); | |||
757 | ||||
758 | /* In case empty slot was gone before entering protected region */ | |||
759 | if (curr_bkt->key_idx[curr_slot] != EMPTY_SLOT0) { | |||
760 | __hash_rw_writer_unlock(h); | |||
761 | return -1; | |||
762 | } | |||
763 | ||||
764 | /* Check if key was inserted after last check but before this | |||
765 | * protected region. | |||
766 | */ | |||
767 | ret = search_and_update(h, data, key, bkt, sig); | |||
768 | if (ret != -1) { | |||
769 | __hash_rw_writer_unlock(h); | |||
770 | *ret_val = ret; | |||
771 | return 1; | |||
772 | } | |||
773 | ||||
774 | FOR_EACH_BUCKET(cur_bkt, alt_bkt)for (cur_bkt = alt_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
775 | ret = search_and_update(h, data, key, cur_bkt, sig); | |||
776 | if (ret != -1) { | |||
777 | __hash_rw_writer_unlock(h); | |||
778 | *ret_val = ret; | |||
779 | return 1; | |||
780 | } | |||
781 | } | |||
782 | ||||
783 | while (likely(curr_node->prev != NULL)__builtin_expect(!!(curr_node->prev != ((void*)0)), 1)) { | |||
784 | prev_node = curr_node->prev; | |||
785 | prev_bkt = prev_node->bkt; | |||
786 | prev_slot = curr_node->prev_slot; | |||
787 | ||||
788 | prev_alt_bkt_idx = get_alt_bucket_index(h, | |||
789 | prev_node->cur_bkt_idx, | |||
790 | prev_bkt->sig_current[prev_slot]); | |||
791 | ||||
792 | if (unlikely(&h->buckets[prev_alt_bkt_idx]__builtin_expect(!!(&h->buckets[prev_alt_bkt_idx] != curr_bkt ), 0) | |||
793 | != curr_bkt)__builtin_expect(!!(&h->buckets[prev_alt_bkt_idx] != curr_bkt ), 0)) { | |||
794 | /* revert it to empty, otherwise duplicated keys */ | |||
795 | __atomic_store_n(&curr_bkt->key_idx[curr_slot], | |||
796 | EMPTY_SLOT0, | |||
797 | __ATOMIC_RELEASE3); | |||
798 | __hash_rw_writer_unlock(h); | |||
799 | return -1; | |||
800 | } | |||
801 | ||||
802 | if (h->readwrite_concur_lf_support) { | |||
803 | /* Inform the previous move. The current move need | |||
804 | * not be informed now as the current bucket entry | |||
805 | * is present in both primary and secondary. | |||
806 | * Since there is one writer, load acquires on | |||
807 | * tbl_chng_cnt are not required. | |||
808 | */ | |||
809 | __atomic_store_n(h->tbl_chng_cnt, | |||
810 | *h->tbl_chng_cnt + 1, | |||
811 | __ATOMIC_RELEASE3); | |||
812 | /* The store to sig_current should not | |||
813 | * move above the store to tbl_chng_cnt. | |||
814 | */ | |||
815 | __atomic_thread_fence(__ATOMIC_RELEASE3); | |||
816 | } | |||
817 | ||||
818 | /* Need to swap current/alt sig to allow later | |||
819 | * Cuckoo insert to move elements back to its | |||
820 | * primary bucket if available | |||
821 | */ | |||
822 | curr_bkt->sig_current[curr_slot] = | |||
823 | prev_bkt->sig_current[prev_slot]; | |||
824 | /* Release the updated bucket entry */ | |||
825 | __atomic_store_n(&curr_bkt->key_idx[curr_slot], | |||
826 | prev_bkt->key_idx[prev_slot], | |||
827 | __ATOMIC_RELEASE3); | |||
828 | ||||
829 | curr_slot = prev_slot; | |||
830 | curr_node = prev_node; | |||
831 | curr_bkt = curr_node->bkt; | |||
832 | } | |||
833 | ||||
834 | if (h->readwrite_concur_lf_support) { | |||
835 | /* Inform the previous move. The current move need | |||
836 | * not be informed now as the current bucket entry | |||
837 | * is present in both primary and secondary. | |||
838 | * Since there is one writer, load acquires on | |||
839 | * tbl_chng_cnt are not required. | |||
840 | */ | |||
841 | __atomic_store_n(h->tbl_chng_cnt, | |||
842 | *h->tbl_chng_cnt + 1, | |||
843 | __ATOMIC_RELEASE3); | |||
844 | /* The store to sig_current should not | |||
845 | * move above the store to tbl_chng_cnt. | |||
846 | */ | |||
847 | __atomic_thread_fence(__ATOMIC_RELEASE3); | |||
848 | } | |||
849 | ||||
850 | curr_bkt->sig_current[curr_slot] = sig; | |||
851 | /* Release the new bucket entry */ | |||
852 | __atomic_store_n(&curr_bkt->key_idx[curr_slot], | |||
853 | new_idx, | |||
854 | __ATOMIC_RELEASE3); | |||
855 | ||||
856 | __hash_rw_writer_unlock(h); | |||
857 | ||||
858 | return 0; | |||
859 | ||||
860 | } | |||
861 | ||||
862 | /* | |||
863 | * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe | |||
864 | * Cuckoo | |||
865 | */ | |||
866 | static inline int | |||
867 | rte_hash_cuckoo_make_space_mw(const struct rte_hash *h, | |||
868 | struct rte_hash_bucket *bkt, | |||
869 | struct rte_hash_bucket *sec_bkt, | |||
870 | const struct rte_hash_key *key, void *data, | |||
871 | uint16_t sig, uint32_t bucket_idx, | |||
872 | uint32_t new_idx, int32_t *ret_val) | |||
873 | { | |||
874 | unsigned int i; | |||
875 | struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN1000]; | |||
876 | struct queue_node *tail, *head; | |||
877 | struct rte_hash_bucket *curr_bkt, *alt_bkt; | |||
878 | uint32_t cur_idx, alt_idx; | |||
879 | ||||
880 | tail = queue; | |||
881 | head = queue + 1; | |||
882 | tail->bkt = bkt; | |||
883 | tail->prev = NULL((void*)0); | |||
884 | tail->prev_slot = -1; | |||
885 | tail->cur_bkt_idx = bucket_idx; | |||
886 | ||||
887 | /* Cuckoo bfs Search */ | |||
888 | while (likely(tail != head && head <__builtin_expect(!!(tail != head && head < queue + 1000 - 8), 1) | |||
889 | queue + RTE_HASH_BFS_QUEUE_MAX_LEN -__builtin_expect(!!(tail != head && head < queue + 1000 - 8), 1) | |||
890 | RTE_HASH_BUCKET_ENTRIES)__builtin_expect(!!(tail != head && head < queue + 1000 - 8), 1)) { | |||
891 | curr_bkt = tail->bkt; | |||
892 | cur_idx = tail->cur_bkt_idx; | |||
893 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
894 | if (curr_bkt->key_idx[i] == EMPTY_SLOT0) { | |||
895 | int32_t ret = rte_hash_cuckoo_move_insert_mw(h, | |||
896 | bkt, sec_bkt, key, data, | |||
897 | tail, i, sig, | |||
898 | new_idx, ret_val); | |||
899 | if (likely(ret != -1)__builtin_expect(!!(ret != -1), 1)) | |||
900 | return ret; | |||
901 | } | |||
902 | ||||
903 | /* Enqueue new node and keep prev node info */ | |||
904 | alt_idx = get_alt_bucket_index(h, cur_idx, | |||
905 | curr_bkt->sig_current[i]); | |||
906 | alt_bkt = &(h->buckets[alt_idx]); | |||
907 | head->bkt = alt_bkt; | |||
908 | head->cur_bkt_idx = alt_idx; | |||
909 | head->prev = tail; | |||
910 | head->prev_slot = i; | |||
911 | head++; | |||
912 | } | |||
913 | tail++; | |||
914 | } | |||
915 | ||||
916 | return -ENOSPC28; | |||
917 | } | |||
918 | ||||
919 | static inline int32_t | |||
920 | __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, | |||
921 | hash_sig_t sig, void *data) | |||
922 | { | |||
923 | uint16_t short_sig; | |||
924 | uint32_t prim_bucket_idx, sec_bucket_idx; | |||
925 | struct rte_hash_bucket *prim_bkt, *sec_bkt, *cur_bkt; | |||
926 | struct rte_hash_key *new_k, *keys = h->key_store; | |||
927 | void *slot_id = NULL((void*)0); | |||
928 | void *ext_bkt_id = NULL((void*)0); | |||
929 | uint32_t new_idx, bkt_id; | |||
930 | int ret; | |||
931 | unsigned n_slots; | |||
932 | unsigned lcore_id; | |||
933 | unsigned int i; | |||
934 | struct lcore_cache *cached_free_slots = NULL((void*)0); | |||
935 | int32_t ret_val; | |||
936 | struct rte_hash_bucket *last; | |||
937 | ||||
938 | short_sig = get_short_sig(sig); | |||
939 | prim_bucket_idx = get_prim_bucket_index(h, sig); | |||
940 | sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); | |||
941 | prim_bkt = &h->buckets[prim_bucket_idx]; | |||
942 | sec_bkt = &h->buckets[sec_bucket_idx]; | |||
943 | rte_prefetch0(prim_bkt); | |||
944 | rte_prefetch0(sec_bkt); | |||
945 | ||||
946 | /* Check if key is already inserted in primary location */ | |||
947 | __hash_rw_writer_lock(h); | |||
948 | ret = search_and_update(h, data, key, prim_bkt, short_sig); | |||
949 | if (ret != -1) { | |||
950 | __hash_rw_writer_unlock(h); | |||
951 | return ret; | |||
952 | } | |||
953 | ||||
954 | /* Check if key is already inserted in secondary location */ | |||
955 | FOR_EACH_BUCKET(cur_bkt, sec_bkt)for (cur_bkt = sec_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
956 | ret = search_and_update(h, data, key, cur_bkt, short_sig); | |||
957 | if (ret != -1) { | |||
958 | __hash_rw_writer_unlock(h); | |||
959 | return ret; | |||
960 | } | |||
961 | } | |||
962 | ||||
963 | __hash_rw_writer_unlock(h); | |||
964 | ||||
965 | /* Did not find a match, so get a new slot for storing the new key */ | |||
966 | if (h->use_local_cache) { | |||
967 | lcore_id = rte_lcore_id(); | |||
968 | cached_free_slots = &h->local_free_slots[lcore_id]; | |||
969 | /* Try to get a free slot from the local cache */ | |||
970 | if (cached_free_slots->len == 0) { | |||
971 | /* Need to get another burst of free slots from global ring */ | |||
972 | n_slots = rte_ring_mc_dequeue_burst(h->free_slots, | |||
973 | cached_free_slots->objs, | |||
974 | LCORE_CACHE_SIZE64, NULL((void*)0)); | |||
975 | if (n_slots == 0) { | |||
976 | return -ENOSPC28; | |||
977 | } | |||
978 | ||||
979 | cached_free_slots->len += n_slots; | |||
980 | } | |||
981 | ||||
982 | /* Get a free slot from the local cache */ | |||
983 | cached_free_slots->len--; | |||
984 | slot_id = cached_free_slots->objs[cached_free_slots->len]; | |||
985 | } else { | |||
986 | if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) { | |||
987 | return -ENOSPC28; | |||
988 | } | |||
989 | } | |||
990 | ||||
991 | new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size)((void*)((uintptr_t)(keys) + ((uintptr_t)slot_id * h->key_entry_size ))); | |||
992 | new_idx = (uint32_t)((uintptr_t) slot_id); | |||
993 | /* Copy key */ | |||
994 | memcpy(new_k->key, key, h->key_len); | |||
995 | /* Key can be of arbitrary length, so it is not possible to store | |||
996 | * it atomically. Hence the new key element's memory stores | |||
997 | * (key as well as data) should be complete before it is referenced. | |||
998 | * 'pdata' acts as the synchronization point when an existing hash | |||
999 | * entry is updated. | |||
1000 | */ | |||
1001 | __atomic_store_n(&new_k->pdata, | |||
1002 | data, | |||
1003 | __ATOMIC_RELEASE3); | |||
1004 | ||||
1005 | /* Find an empty slot and insert */ | |||
1006 | ret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data, | |||
1007 | short_sig, new_idx, &ret_val); | |||
1008 | if (ret == 0) | |||
1009 | return new_idx - 1; | |||
1010 | else if (ret == 1) { | |||
1011 | enqueue_slot_back(h, cached_free_slots, slot_id); | |||
1012 | return ret_val; | |||
1013 | } | |||
1014 | ||||
1015 | /* Primary bucket full, need to make space for new entry */ | |||
1016 | ret = rte_hash_cuckoo_make_space_mw(h, prim_bkt, sec_bkt, key, data, | |||
1017 | short_sig, prim_bucket_idx, new_idx, &ret_val); | |||
1018 | if (ret == 0) | |||
1019 | return new_idx - 1; | |||
1020 | else if (ret == 1) { | |||
1021 | enqueue_slot_back(h, cached_free_slots, slot_id); | |||
1022 | return ret_val; | |||
1023 | } | |||
1024 | ||||
1025 | /* Also search secondary bucket to get better occupancy */ | |||
1026 | ret = rte_hash_cuckoo_make_space_mw(h, sec_bkt, prim_bkt, key, data, | |||
1027 | short_sig, sec_bucket_idx, new_idx, &ret_val); | |||
1028 | ||||
1029 | if (ret == 0) | |||
1030 | return new_idx - 1; | |||
1031 | else if (ret == 1) { | |||
1032 | enqueue_slot_back(h, cached_free_slots, slot_id); | |||
1033 | return ret_val; | |||
1034 | } | |||
1035 | ||||
1036 | /* if ext table not enabled, we failed the insertion */ | |||
1037 | if (!h->ext_table_support) { | |||
1038 | enqueue_slot_back(h, cached_free_slots, slot_id); | |||
1039 | return ret; | |||
1040 | } | |||
1041 | ||||
1042 | /* Now we need to go through the extendable bucket. Protection is needed | |||
1043 | * to protect all extendable bucket processes. | |||
1044 | */ | |||
1045 | __hash_rw_writer_lock(h); | |||
1046 | /* We check for duplicates again since could be inserted before the lock */ | |||
1047 | ret = search_and_update(h, data, key, prim_bkt, short_sig); | |||
1048 | if (ret != -1) { | |||
1049 | enqueue_slot_back(h, cached_free_slots, slot_id); | |||
1050 | goto failure; | |||
1051 | } | |||
1052 | ||||
1053 | FOR_EACH_BUCKET(cur_bkt, sec_bkt)for (cur_bkt = sec_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
1054 | ret = search_and_update(h, data, key, cur_bkt, short_sig); | |||
1055 | if (ret != -1) { | |||
1056 | enqueue_slot_back(h, cached_free_slots, slot_id); | |||
1057 | goto failure; | |||
1058 | } | |||
1059 | } | |||
1060 | ||||
1061 | /* Search sec and ext buckets to find an empty entry to insert. */ | |||
1062 | FOR_EACH_BUCKET(cur_bkt, sec_bkt)for (cur_bkt = sec_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
1063 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
1064 | /* Check if slot is available */ | |||
1065 | if (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)__builtin_expect(!!(cur_bkt->key_idx[i] == 0), 1)) { | |||
1066 | cur_bkt->sig_current[i] = short_sig; | |||
1067 | /* Store to signature should not leak after | |||
1068 | * the store to key_idx | |||
1069 | */ | |||
1070 | __atomic_store_n(&cur_bkt->key_idx[i], | |||
1071 | new_idx, | |||
1072 | __ATOMIC_RELEASE3); | |||
1073 | __hash_rw_writer_unlock(h); | |||
1074 | return new_idx - 1; | |||
1075 | } | |||
1076 | } | |||
1077 | } | |||
1078 | ||||
1079 | /* Failed to get an empty entry from extendable buckets. Link a new | |||
1080 | * extendable bucket. We first get a free bucket from ring. | |||
1081 | */ | |||
1082 | if (rte_ring_sc_dequeue(h->free_ext_bkts, &ext_bkt_id) != 0) { | |||
1083 | ret = -ENOSPC28; | |||
1084 | goto failure; | |||
1085 | } | |||
1086 | ||||
1087 | bkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1; | |||
1088 | /* Use the first location of the new bucket */ | |||
1089 | (h->buckets_ext[bkt_id]).sig_current[0] = short_sig; | |||
1090 | /* Store to signature should not leak after | |||
1091 | * the store to key_idx | |||
1092 | */ | |||
1093 | __atomic_store_n(&(h->buckets_ext[bkt_id]).key_idx[0], | |||
1094 | new_idx, | |||
1095 | __ATOMIC_RELEASE3); | |||
1096 | /* Link the new bucket to sec bucket linked list */ | |||
1097 | last = rte_hash_get_last_bkt(sec_bkt); | |||
1098 | last->next = &h->buckets_ext[bkt_id]; | |||
1099 | __hash_rw_writer_unlock(h); | |||
1100 | return new_idx - 1; | |||
1101 | ||||
1102 | failure: | |||
1103 | __hash_rw_writer_unlock(h); | |||
1104 | return ret; | |||
1105 | ||||
1106 | } | |||
1107 | ||||
1108 | int32_t | |||
1109 | rte_hash_add_key_with_hash(const struct rte_hash *h, | |||
1110 | const void *key, hash_sig_t sig) | |||
1111 | { | |||
1112 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1113 | return __rte_hash_add_key_with_hash(h, key, sig, 0); | |||
1114 | } | |||
1115 | ||||
1116 | int32_t | |||
1117 | rte_hash_add_key(const struct rte_hash *h, const void *key) | |||
1118 | { | |||
1119 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1120 | return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0); | |||
1121 | } | |||
1122 | ||||
1123 | int | |||
1124 | rte_hash_add_key_with_hash_data(const struct rte_hash *h, | |||
1125 | const void *key, hash_sig_t sig, void *data) | |||
1126 | { | |||
1127 | int ret; | |||
1128 | ||||
1129 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1130 | ret = __rte_hash_add_key_with_hash(h, key, sig, data); | |||
1131 | if (ret >= 0) | |||
1132 | return 0; | |||
1133 | else | |||
1134 | return ret; | |||
1135 | } | |||
1136 | ||||
1137 | int | |||
1138 | rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data) | |||
1139 | { | |||
1140 | int ret; | |||
1141 | ||||
1142 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1143 | ||||
1144 | ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data); | |||
| ||||
1145 | if (ret >= 0) | |||
1146 | return 0; | |||
1147 | else | |||
1148 | return ret; | |||
1149 | } | |||
1150 | ||||
1151 | /* Search one bucket to find the match key - uses rw lock */ | |||
1152 | static inline int32_t | |||
1153 | search_one_bucket_l(const struct rte_hash *h, const void *key, | |||
1154 | uint16_t sig, void **data, | |||
1155 | const struct rte_hash_bucket *bkt) | |||
1156 | { | |||
1157 | int i; | |||
1158 | struct rte_hash_key *k, *keys = h->key_store; | |||
1159 | ||||
1160 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
1161 | if (bkt->sig_current[i] == sig && | |||
1162 | bkt->key_idx[i] != EMPTY_SLOT0) { | |||
1163 | k = (struct rte_hash_key *) ((char *)keys + | |||
1164 | bkt->key_idx[i] * h->key_entry_size); | |||
1165 | ||||
1166 | if (rte_hash_cmp_eq(key, k->key, h) == 0) { | |||
1167 | if (data != NULL((void*)0)) | |||
1168 | *data = k->pdata; | |||
1169 | /* | |||
1170 | * Return index where key is stored, | |||
1171 | * subtracting the first dummy index | |||
1172 | */ | |||
1173 | return bkt->key_idx[i] - 1; | |||
1174 | } | |||
1175 | } | |||
1176 | } | |||
1177 | return -1; | |||
1178 | } | |||
1179 | ||||
1180 | /* Search one bucket to find the match key */ | |||
1181 | static inline int32_t | |||
1182 | search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig, | |||
1183 | void **data, const struct rte_hash_bucket *bkt) | |||
1184 | { | |||
1185 | int i; | |||
1186 | uint32_t key_idx; | |||
1187 | void *pdata; | |||
1188 | struct rte_hash_key *k, *keys = h->key_store; | |||
1189 | ||||
1190 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
1191 | key_idx = __atomic_load_n(&bkt->key_idx[i], | |||
1192 | __ATOMIC_ACQUIRE2); | |||
1193 | if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT0) { | |||
1194 | k = (struct rte_hash_key *) ((char *)keys + | |||
1195 | key_idx * h->key_entry_size); | |||
1196 | pdata = __atomic_load_n(&k->pdata, | |||
1197 | __ATOMIC_ACQUIRE2); | |||
1198 | ||||
1199 | if (rte_hash_cmp_eq(key, k->key, h) == 0) { | |||
1200 | if (data != NULL((void*)0)) | |||
1201 | *data = pdata; | |||
1202 | /* | |||
1203 | * Return index where key is stored, | |||
1204 | * subtracting the first dummy index | |||
1205 | */ | |||
1206 | return key_idx - 1; | |||
1207 | } | |||
1208 | } | |||
1209 | } | |||
1210 | return -1; | |||
1211 | } | |||
1212 | ||||
1213 | static inline int32_t | |||
1214 | __rte_hash_lookup_with_hash_l(const struct rte_hash *h, const void *key, | |||
1215 | hash_sig_t sig, void **data) | |||
1216 | { | |||
1217 | uint32_t prim_bucket_idx, sec_bucket_idx; | |||
1218 | struct rte_hash_bucket *bkt, *cur_bkt; | |||
1219 | int ret; | |||
1220 | uint16_t short_sig; | |||
1221 | ||||
1222 | short_sig = get_short_sig(sig); | |||
1223 | prim_bucket_idx = get_prim_bucket_index(h, sig); | |||
1224 | sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); | |||
1225 | ||||
1226 | bkt = &h->buckets[prim_bucket_idx]; | |||
1227 | ||||
1228 | __hash_rw_reader_lock(h); | |||
1229 | ||||
1230 | /* Check if key is in primary location */ | |||
1231 | ret = search_one_bucket_l(h, key, short_sig, data, bkt); | |||
1232 | if (ret != -1) { | |||
1233 | __hash_rw_reader_unlock(h); | |||
1234 | return ret; | |||
1235 | } | |||
1236 | /* Calculate secondary hash */ | |||
1237 | bkt = &h->buckets[sec_bucket_idx]; | |||
1238 | ||||
1239 | /* Check if key is in secondary location */ | |||
1240 | FOR_EACH_BUCKET(cur_bkt, bkt)for (cur_bkt = bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt-> next) { | |||
1241 | ret = search_one_bucket_l(h, key, short_sig, | |||
1242 | data, cur_bkt); | |||
1243 | if (ret != -1) { | |||
1244 | __hash_rw_reader_unlock(h); | |||
1245 | return ret; | |||
1246 | } | |||
1247 | } | |||
1248 | ||||
1249 | __hash_rw_reader_unlock(h); | |||
1250 | ||||
1251 | return -ENOENT2; | |||
1252 | } | |||
1253 | ||||
1254 | static inline int32_t | |||
1255 | __rte_hash_lookup_with_hash_lf(const struct rte_hash *h, const void *key, | |||
1256 | hash_sig_t sig, void **data) | |||
1257 | { | |||
1258 | uint32_t prim_bucket_idx, sec_bucket_idx; | |||
1259 | struct rte_hash_bucket *bkt, *cur_bkt; | |||
1260 | uint32_t cnt_b, cnt_a; | |||
1261 | int ret; | |||
1262 | uint16_t short_sig; | |||
1263 | ||||
1264 | short_sig = get_short_sig(sig); | |||
1265 | prim_bucket_idx = get_prim_bucket_index(h, sig); | |||
1266 | sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); | |||
1267 | ||||
1268 | do { | |||
1269 | /* Load the table change counter before the lookup | |||
1270 | * starts. Acquire semantics will make sure that | |||
1271 | * loads in search_one_bucket are not hoisted. | |||
1272 | */ | |||
1273 | cnt_b = __atomic_load_n(h->tbl_chng_cnt, | |||
1274 | __ATOMIC_ACQUIRE2); | |||
1275 | ||||
1276 | /* Check if key is in primary location */ | |||
1277 | bkt = &h->buckets[prim_bucket_idx]; | |||
1278 | ret = search_one_bucket_lf(h, key, short_sig, data, bkt); | |||
1279 | if (ret != -1) { | |||
1280 | __hash_rw_reader_unlock(h); | |||
1281 | return ret; | |||
1282 | } | |||
1283 | /* Calculate secondary hash */ | |||
1284 | bkt = &h->buckets[sec_bucket_idx]; | |||
1285 | ||||
1286 | /* Check if key is in secondary location */ | |||
1287 | FOR_EACH_BUCKET(cur_bkt, bkt)for (cur_bkt = bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt-> next) { | |||
1288 | ret = search_one_bucket_lf(h, key, short_sig, | |||
1289 | data, cur_bkt); | |||
1290 | if (ret != -1) { | |||
1291 | __hash_rw_reader_unlock(h); | |||
1292 | return ret; | |||
1293 | } | |||
1294 | } | |||
1295 | ||||
1296 | /* The loads of sig_current in search_one_bucket | |||
1297 | * should not move below the load from tbl_chng_cnt. | |||
1298 | */ | |||
1299 | __atomic_thread_fence(__ATOMIC_ACQUIRE2); | |||
1300 | /* Re-read the table change counter to check if the | |||
1301 | * table has changed during search. If yes, re-do | |||
1302 | * the search. | |||
1303 | * This load should not get hoisted. The load | |||
1304 | * acquires on cnt_b, key index in primary bucket | |||
1305 | * and key index in secondary bucket will make sure | |||
1306 | * that it does not get hoisted. | |||
1307 | */ | |||
1308 | cnt_a = __atomic_load_n(h->tbl_chng_cnt, | |||
1309 | __ATOMIC_ACQUIRE2); | |||
1310 | } while (cnt_b != cnt_a); | |||
1311 | ||||
1312 | return -ENOENT2; | |||
1313 | } | |||
1314 | ||||
1315 | static inline int32_t | |||
1316 | __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, | |||
1317 | hash_sig_t sig, void **data) | |||
1318 | { | |||
1319 | if (h->readwrite_concur_lf_support) | |||
1320 | return __rte_hash_lookup_with_hash_lf(h, key, sig, data); | |||
1321 | else | |||
1322 | return __rte_hash_lookup_with_hash_l(h, key, sig, data); | |||
1323 | } | |||
1324 | ||||
1325 | int32_t | |||
1326 | rte_hash_lookup_with_hash(const struct rte_hash *h, | |||
1327 | const void *key, hash_sig_t sig) | |||
1328 | { | |||
1329 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1330 | return __rte_hash_lookup_with_hash(h, key, sig, NULL((void*)0)); | |||
1331 | } | |||
1332 | ||||
1333 | int32_t | |||
1334 | rte_hash_lookup(const struct rte_hash *h, const void *key) | |||
1335 | { | |||
1336 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1337 | return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL((void*)0)); | |||
1338 | } | |||
1339 | ||||
1340 | int | |||
1341 | rte_hash_lookup_with_hash_data(const struct rte_hash *h, | |||
1342 | const void *key, hash_sig_t sig, void **data) | |||
1343 | { | |||
1344 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1345 | return __rte_hash_lookup_with_hash(h, key, sig, data); | |||
1346 | } | |||
1347 | ||||
1348 | int | |||
1349 | rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data) | |||
1350 | { | |||
1351 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1352 | return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data); | |||
1353 | } | |||
1354 | ||||
1355 | static inline void | |||
1356 | remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) | |||
1357 | { | |||
1358 | unsigned lcore_id, n_slots; | |||
1359 | struct lcore_cache *cached_free_slots; | |||
1360 | ||||
1361 | if (h->use_local_cache) { | |||
1362 | lcore_id = rte_lcore_id(); | |||
1363 | cached_free_slots = &h->local_free_slots[lcore_id]; | |||
1364 | /* Cache full, need to free it. */ | |||
1365 | if (cached_free_slots->len == LCORE_CACHE_SIZE64) { | |||
1366 | /* Need to enqueue the free slots in global ring. */ | |||
1367 | n_slots = rte_ring_mp_enqueue_burst(h->free_slots, | |||
1368 | cached_free_slots->objs, | |||
1369 | LCORE_CACHE_SIZE64, NULL((void*)0)); | |||
1370 | ERR_IF_TRUE((n_slots == 0), | |||
1371 | "%s: could not enqueue free slots in global ring\n", | |||
1372 | __func__); | |||
1373 | cached_free_slots->len -= n_slots; | |||
1374 | } | |||
1375 | /* Put index of new free slot in cache. */ | |||
1376 | cached_free_slots->objs[cached_free_slots->len] = | |||
1377 | (void *)((uintptr_t)bkt->key_idx[i]); | |||
1378 | cached_free_slots->len++; | |||
1379 | } else { | |||
1380 | rte_ring_sp_enqueue(h->free_slots, | |||
1381 | (void *)((uintptr_t)bkt->key_idx[i])); | |||
1382 | } | |||
1383 | } | |||
1384 | ||||
1385 | /* Compact the linked list by moving key from last entry in linked list to the | |||
1386 | * empty slot. | |||
1387 | */ | |||
1388 | static inline void | |||
1389 | __rte_hash_compact_ll(const struct rte_hash *h, | |||
1390 | struct rte_hash_bucket *cur_bkt, int pos) { | |||
1391 | int i; | |||
1392 | struct rte_hash_bucket *last_bkt; | |||
1393 | ||||
1394 | if (!cur_bkt->next) | |||
1395 | return; | |||
1396 | ||||
1397 | last_bkt = rte_hash_get_last_bkt(cur_bkt); | |||
1398 | ||||
1399 | for (i = RTE_HASH_BUCKET_ENTRIES8 - 1; i >= 0; i--) { | |||
1400 | if (last_bkt->key_idx[i] != EMPTY_SLOT0) { | |||
1401 | cur_bkt->sig_current[pos] = last_bkt->sig_current[i]; | |||
1402 | __atomic_store_n(&cur_bkt->key_idx[pos], | |||
1403 | last_bkt->key_idx[i], | |||
1404 | __ATOMIC_RELEASE3); | |||
1405 | if (h->readwrite_concur_lf_support) { | |||
1406 | /* Inform the readers that the table has changed | |||
1407 | * Since there is one writer, load acquire on | |||
1408 | * tbl_chng_cnt is not required. | |||
1409 | */ | |||
1410 | __atomic_store_n(h->tbl_chng_cnt, | |||
1411 | *h->tbl_chng_cnt + 1, | |||
1412 | __ATOMIC_RELEASE3); | |||
1413 | /* The store to sig_current should | |||
1414 | * not move above the store to tbl_chng_cnt. | |||
1415 | */ | |||
1416 | __atomic_thread_fence(__ATOMIC_RELEASE3); | |||
1417 | } | |||
1418 | last_bkt->sig_current[i] = NULL_SIGNATURE0; | |||
1419 | __atomic_store_n(&last_bkt->key_idx[i], | |||
1420 | EMPTY_SLOT0, | |||
1421 | __ATOMIC_RELEASE3); | |||
1422 | return; | |||
1423 | } | |||
1424 | } | |||
1425 | } | |||
1426 | ||||
1427 | /* Search one bucket and remove the matched key. | |||
1428 | * Writer is expected to hold the lock while calling this | |||
1429 | * function. | |||
1430 | */ | |||
1431 | static inline int32_t | |||
1432 | search_and_remove(const struct rte_hash *h, const void *key, | |||
1433 | struct rte_hash_bucket *bkt, uint16_t sig, int *pos) | |||
1434 | { | |||
1435 | struct rte_hash_key *k, *keys = h->key_store; | |||
1436 | unsigned int i; | |||
1437 | uint32_t key_idx; | |||
1438 | ||||
1439 | /* Check if key is in bucket */ | |||
1440 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
1441 | key_idx = __atomic_load_n(&bkt->key_idx[i], | |||
1442 | __ATOMIC_ACQUIRE2); | |||
1443 | if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT0) { | |||
1444 | k = (struct rte_hash_key *) ((char *)keys + | |||
1445 | key_idx * h->key_entry_size); | |||
1446 | if (rte_hash_cmp_eq(key, k->key, h) == 0) { | |||
1447 | bkt->sig_current[i] = NULL_SIGNATURE0; | |||
1448 | /* Free the key store index if | |||
1449 | * no_free_on_del is disabled. | |||
1450 | */ | |||
1451 | if (!h->no_free_on_del) | |||
1452 | remove_entry(h, bkt, i); | |||
1453 | ||||
1454 | __atomic_store_n(&bkt->key_idx[i], | |||
1455 | EMPTY_SLOT0, | |||
1456 | __ATOMIC_RELEASE3); | |||
1457 | ||||
1458 | *pos = i; | |||
1459 | /* | |||
1460 | * Return index where key is stored, | |||
1461 | * subtracting the first dummy index | |||
1462 | */ | |||
1463 | return key_idx - 1; | |||
1464 | } | |||
1465 | } | |||
1466 | } | |||
1467 | return -1; | |||
1468 | } | |||
1469 | ||||
1470 | static inline int32_t | |||
1471 | __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, | |||
1472 | hash_sig_t sig) | |||
1473 | { | |||
1474 | uint32_t prim_bucket_idx, sec_bucket_idx; | |||
1475 | struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt; | |||
1476 | struct rte_hash_bucket *cur_bkt; | |||
1477 | int pos; | |||
1478 | int32_t ret, i; | |||
1479 | uint16_t short_sig; | |||
1480 | ||||
1481 | short_sig = get_short_sig(sig); | |||
1482 | prim_bucket_idx = get_prim_bucket_index(h, sig); | |||
1483 | sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); | |||
1484 | prim_bkt = &h->buckets[prim_bucket_idx]; | |||
1485 | ||||
1486 | __hash_rw_writer_lock(h); | |||
1487 | /* look for key in primary bucket */ | |||
1488 | ret = search_and_remove(h, key, prim_bkt, short_sig, &pos); | |||
1489 | if (ret != -1) { | |||
1490 | __rte_hash_compact_ll(h, prim_bkt, pos); | |||
1491 | last_bkt = prim_bkt->next; | |||
1492 | prev_bkt = prim_bkt; | |||
1493 | goto return_bkt; | |||
1494 | } | |||
1495 | ||||
1496 | /* Calculate secondary hash */ | |||
1497 | sec_bkt = &h->buckets[sec_bucket_idx]; | |||
1498 | ||||
1499 | FOR_EACH_BUCKET(cur_bkt, sec_bkt)for (cur_bkt = sec_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
1500 | ret = search_and_remove(h, key, cur_bkt, short_sig, &pos); | |||
1501 | if (ret != -1) { | |||
1502 | __rte_hash_compact_ll(h, cur_bkt, pos); | |||
1503 | last_bkt = sec_bkt->next; | |||
1504 | prev_bkt = sec_bkt; | |||
1505 | goto return_bkt; | |||
1506 | } | |||
1507 | } | |||
1508 | ||||
1509 | __hash_rw_writer_unlock(h); | |||
1510 | return -ENOENT2; | |||
1511 | ||||
1512 | /* Search last bucket to see if empty to be recycled */ | |||
1513 | return_bkt: | |||
1514 | if (!last_bkt) { | |||
1515 | __hash_rw_writer_unlock(h); | |||
1516 | return ret; | |||
1517 | } | |||
1518 | while (last_bkt->next) { | |||
1519 | prev_bkt = last_bkt; | |||
1520 | last_bkt = last_bkt->next; | |||
1521 | } | |||
1522 | ||||
1523 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
1524 | if (last_bkt->key_idx[i] != EMPTY_SLOT0) | |||
1525 | break; | |||
1526 | } | |||
1527 | /* found empty bucket and recycle */ | |||
1528 | if (i == RTE_HASH_BUCKET_ENTRIES8) { | |||
1529 | prev_bkt->next = NULL((void*)0); | |||
1530 | uint32_t index = last_bkt - h->buckets_ext + 1; | |||
1531 | /* Recycle the empty bkt if | |||
1532 | * no_free_on_del is disabled. | |||
1533 | */ | |||
1534 | if (h->no_free_on_del) | |||
1535 | /* Store index of an empty ext bkt to be recycled | |||
1536 | * on calling rte_hash_del_xxx APIs. | |||
1537 | * When lock free read-write concurrency is enabled, | |||
1538 | * an empty ext bkt cannot be put into free list | |||
1539 | * immediately (as readers might be using it still). | |||
1540 | * Hence freeing of the ext bkt is piggy-backed to | |||
1541 | * freeing of the key index. | |||
1542 | */ | |||
1543 | h->ext_bkt_to_free[ret] = index; | |||
1544 | else | |||
1545 | rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index); | |||
1546 | } | |||
1547 | __hash_rw_writer_unlock(h); | |||
1548 | return ret; | |||
1549 | } | |||
1550 | ||||
1551 | int32_t | |||
1552 | rte_hash_del_key_with_hash(const struct rte_hash *h, | |||
1553 | const void *key, hash_sig_t sig) | |||
1554 | { | |||
1555 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1556 | return __rte_hash_del_key_with_hash(h, key, sig); | |||
1557 | } | |||
1558 | ||||
1559 | int32_t | |||
1560 | rte_hash_del_key(const struct rte_hash *h, const void *key) | |||
1561 | { | |||
1562 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1563 | return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); | |||
1564 | } | |||
1565 | ||||
1566 | int | |||
1567 | rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, | |||
1568 | void **key) | |||
1569 | { | |||
1570 | RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); | |||
1571 | ||||
1572 | struct rte_hash_key *k, *keys = h->key_store; | |||
1573 | k = (struct rte_hash_key *) ((char *) keys + (position + 1) * | |||
1574 | h->key_entry_size); | |||
1575 | *key = k->key; | |||
1576 | ||||
1577 | if (position != | |||
1578 | __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key), | |||
1579 | NULL((void*)0))) { | |||
1580 | return -ENOENT2; | |||
1581 | } | |||
1582 | ||||
1583 | return 0; | |||
1584 | } | |||
1585 | ||||
1586 | int __rte_experimental__attribute__((deprecated("Symbol is not yet part of stable ABI" ), section(".text.experimental"))) | |||
1587 | rte_hash_free_key_with_position(const struct rte_hash *h, | |||
1588 | const int32_t position) | |||
1589 | { | |||
1590 | /* Key index where key is stored, adding the first dummy index */ | |||
1591 | uint32_t key_idx = position + 1; | |||
1592 | ||||
1593 | RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL); | |||
1594 | ||||
1595 | unsigned int lcore_id, n_slots; | |||
1596 | struct lcore_cache *cached_free_slots; | |||
1597 | const uint32_t total_entries = h->use_local_cache ? | |||
1598 | h->entries + (RTE_MAX_LCORE128 - 1) * (LCORE_CACHE_SIZE64 - 1) + 1 | |||
1599 | : h->entries + 1; | |||
1600 | ||||
1601 | /* Out of bounds */ | |||
1602 | if (key_idx >= total_entries) | |||
1603 | return -EINVAL22; | |||
1604 | if (h->ext_table_support && h->readwrite_concur_lf_support) { | |||
1605 | uint32_t index = h->ext_bkt_to_free[position]; | |||
1606 | if (index) { | |||
1607 | /* Recycle empty ext bkt to free list. */ | |||
1608 | rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index); | |||
1609 | h->ext_bkt_to_free[position] = 0; | |||
1610 | } | |||
1611 | } | |||
1612 | ||||
1613 | if (h->use_local_cache) { | |||
1614 | lcore_id = rte_lcore_id(); | |||
1615 | cached_free_slots = &h->local_free_slots[lcore_id]; | |||
1616 | /* Cache full, need to free it. */ | |||
1617 | if (cached_free_slots->len == LCORE_CACHE_SIZE64) { | |||
1618 | /* Need to enqueue the free slots in global ring. */ | |||
1619 | n_slots = rte_ring_mp_enqueue_burst(h->free_slots, | |||
1620 | cached_free_slots->objs, | |||
1621 | LCORE_CACHE_SIZE64, NULL((void*)0)); | |||
1622 | RETURN_IF_TRUE((n_slots == 0), -EFAULT); | |||
1623 | cached_free_slots->len -= n_slots; | |||
1624 | } | |||
1625 | /* Put index of new free slot in cache. */ | |||
1626 | cached_free_slots->objs[cached_free_slots->len] = | |||
1627 | (void *)((uintptr_t)key_idx); | |||
1628 | cached_free_slots->len++; | |||
1629 | } else { | |||
1630 | rte_ring_sp_enqueue(h->free_slots, | |||
1631 | (void *)((uintptr_t)key_idx)); | |||
1632 | } | |||
1633 | ||||
1634 | return 0; | |||
1635 | } | |||
1636 | ||||
1637 | static inline void | |||
1638 | compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches, | |||
1639 | const struct rte_hash_bucket *prim_bkt, | |||
1640 | const struct rte_hash_bucket *sec_bkt, | |||
1641 | uint16_t sig, | |||
1642 | enum rte_hash_sig_compare_function sig_cmp_fn) | |||
1643 | { | |||
1644 | unsigned int i; | |||
1645 | ||||
1646 | /* For match mask the first bit of every two bits indicates the match */ | |||
1647 | switch (sig_cmp_fn) { | |||
1648 | #if defined(RTE_MACHINE_CPUFLAG_SSE21) | |||
1649 | case RTE_HASH_COMPARE_SSE: | |||
1650 | /* Compare all signatures in the bucket */ | |||
1651 | *prim_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16( | |||
1652 | _mm_load_si128( | |||
1653 | (__m128i const *)prim_bkt->sig_current), | |||
1654 | _mm_set1_epi16(sig))); | |||
1655 | /* Compare all signatures in the bucket */ | |||
1656 | *sec_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16( | |||
1657 | _mm_load_si128( | |||
1658 | (__m128i const *)sec_bkt->sig_current), | |||
1659 | _mm_set1_epi16(sig))); | |||
1660 | break; | |||
1661 | #elif defined(RTE_MACHINE_CPUFLAG_NEON) | |||
1662 | case RTE_HASH_COMPARE_NEON: { | |||
1663 | uint16x8_t vmat, vsig, x; | |||
1664 | uint64x2_t x64; | |||
1665 | int16x8_t shift = {-15, -13, -11, -9, -7, -5, -3, -1}; | |||
1666 | ||||
1667 | vsig = vld1q_dup_u16((uint16_t const *)&sig); | |||
1668 | /* Compare all signatures in the primary bucket */ | |||
1669 | vmat = vceqq_u16(vsig, | |||
1670 | vld1q_u16((uint16_t const *)prim_bkt->sig_current)); | |||
1671 | x = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x8000)), shift); | |||
1672 | x64 = vpaddlq_u32(vpaddlq_u16(x)); | |||
1673 | *prim_hash_matches = (uint32_t)(vgetq_lane_u64(x64, 0) + | |||
1674 | vgetq_lane_u64(x64, 1)); | |||
1675 | /* Compare all signatures in the secondary bucket */ | |||
1676 | vmat = vceqq_u16(vsig, | |||
1677 | vld1q_u16((uint16_t const *)sec_bkt->sig_current)); | |||
1678 | x = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x8000)), shift); | |||
1679 | x64 = vpaddlq_u32(vpaddlq_u16(x)); | |||
1680 | *sec_hash_matches = (uint32_t)(vgetq_lane_u64(x64, 0) + | |||
1681 | vgetq_lane_u64(x64, 1)); } | |||
1682 | break; | |||
1683 | #endif | |||
1684 | default: | |||
1685 | for (i = 0; i < RTE_HASH_BUCKET_ENTRIES8; i++) { | |||
1686 | *prim_hash_matches |= | |||
1687 | ((sig == prim_bkt->sig_current[i]) << (i << 1)); | |||
1688 | *sec_hash_matches |= | |||
1689 | ((sig == sec_bkt->sig_current[i]) << (i << 1)); | |||
1690 | } | |||
1691 | } | |||
1692 | } | |||
1693 | ||||
1694 | #define PREFETCH_OFFSET4 4 | |||
1695 | static inline void | |||
1696 | __rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys, | |||
1697 | int32_t num_keys, int32_t *positions, | |||
1698 | uint64_t *hit_mask, void *data[]) | |||
1699 | { | |||
1700 | uint64_t hits = 0; | |||
1701 | int32_t i; | |||
1702 | int32_t ret; | |||
1703 | uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1704 | uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1705 | uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1706 | uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1707 | const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1708 | const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1709 | uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX64] = {0}; | |||
1710 | uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX64] = {0}; | |||
1711 | struct rte_hash_bucket *cur_bkt, *next_bkt; | |||
1712 | ||||
1713 | /* Prefetch first keys */ | |||
1714 | for (i = 0; i < PREFETCH_OFFSET4 && i < num_keys; i++) | |||
1715 | rte_prefetch0(keys[i]); | |||
1716 | ||||
1717 | /* | |||
1718 | * Prefetch rest of the keys, calculate primary and | |||
1719 | * secondary bucket and prefetch them | |||
1720 | */ | |||
1721 | for (i = 0; i < (num_keys - PREFETCH_OFFSET4); i++) { | |||
1722 | rte_prefetch0(keys[i + PREFETCH_OFFSET4]); | |||
1723 | ||||
1724 | prim_hash[i] = rte_hash_hash(h, keys[i]); | |||
1725 | ||||
1726 | sig[i] = get_short_sig(prim_hash[i]); | |||
1727 | prim_index[i] = get_prim_bucket_index(h, prim_hash[i]); | |||
1728 | sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]); | |||
1729 | ||||
1730 | primary_bkt[i] = &h->buckets[prim_index[i]]; | |||
1731 | secondary_bkt[i] = &h->buckets[sec_index[i]]; | |||
1732 | ||||
1733 | rte_prefetch0(primary_bkt[i]); | |||
1734 | rte_prefetch0(secondary_bkt[i]); | |||
1735 | } | |||
1736 | ||||
1737 | /* Calculate and prefetch rest of the buckets */ | |||
1738 | for (; i < num_keys; i++) { | |||
1739 | prim_hash[i] = rte_hash_hash(h, keys[i]); | |||
1740 | ||||
1741 | sig[i] = get_short_sig(prim_hash[i]); | |||
1742 | prim_index[i] = get_prim_bucket_index(h, prim_hash[i]); | |||
1743 | sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]); | |||
1744 | ||||
1745 | primary_bkt[i] = &h->buckets[prim_index[i]]; | |||
1746 | secondary_bkt[i] = &h->buckets[sec_index[i]]; | |||
1747 | ||||
1748 | rte_prefetch0(primary_bkt[i]); | |||
1749 | rte_prefetch0(secondary_bkt[i]); | |||
1750 | } | |||
1751 | ||||
1752 | __hash_rw_reader_lock(h); | |||
1753 | ||||
1754 | /* Compare signatures and prefetch key slot of first hit */ | |||
1755 | for (i = 0; i < num_keys; i++) { | |||
1756 | compare_signatures(&prim_hitmask[i], &sec_hitmask[i], | |||
1757 | primary_bkt[i], secondary_bkt[i], | |||
1758 | sig[i], h->sig_cmp_fn); | |||
1759 | ||||
1760 | if (prim_hitmask[i]) { | |||
1761 | uint32_t first_hit = | |||
1762 | __builtin_ctzl(prim_hitmask[i]) | |||
1763 | >> 1; | |||
1764 | uint32_t key_idx = | |||
1765 | primary_bkt[i]->key_idx[first_hit]; | |||
1766 | const struct rte_hash_key *key_slot = | |||
1767 | (const struct rte_hash_key *)( | |||
1768 | (const char *)h->key_store + | |||
1769 | key_idx * h->key_entry_size); | |||
1770 | rte_prefetch0(key_slot); | |||
1771 | continue; | |||
1772 | } | |||
1773 | ||||
1774 | if (sec_hitmask[i]) { | |||
1775 | uint32_t first_hit = | |||
1776 | __builtin_ctzl(sec_hitmask[i]) | |||
1777 | >> 1; | |||
1778 | uint32_t key_idx = | |||
1779 | secondary_bkt[i]->key_idx[first_hit]; | |||
1780 | const struct rte_hash_key *key_slot = | |||
1781 | (const struct rte_hash_key *)( | |||
1782 | (const char *)h->key_store + | |||
1783 | key_idx * h->key_entry_size); | |||
1784 | rte_prefetch0(key_slot); | |||
1785 | } | |||
1786 | } | |||
1787 | ||||
1788 | /* Compare keys, first hits in primary first */ | |||
1789 | for (i = 0; i < num_keys; i++) { | |||
1790 | positions[i] = -ENOENT2; | |||
1791 | while (prim_hitmask[i]) { | |||
1792 | uint32_t hit_index = | |||
1793 | __builtin_ctzl(prim_hitmask[i]) | |||
1794 | >> 1; | |||
1795 | uint32_t key_idx = | |||
1796 | primary_bkt[i]->key_idx[hit_index]; | |||
1797 | const struct rte_hash_key *key_slot = | |||
1798 | (const struct rte_hash_key *)( | |||
1799 | (const char *)h->key_store + | |||
1800 | key_idx * h->key_entry_size); | |||
1801 | ||||
1802 | /* | |||
1803 | * If key index is 0, do not compare key, | |||
1804 | * as it is checking the dummy slot | |||
1805 | */ | |||
1806 | if (!!key_idx & | |||
1807 | !rte_hash_cmp_eq( | |||
1808 | key_slot->key, keys[i], h)) { | |||
1809 | if (data != NULL((void*)0)) | |||
1810 | data[i] = key_slot->pdata; | |||
1811 | ||||
1812 | hits |= 1ULL << i; | |||
1813 | positions[i] = key_idx - 1; | |||
1814 | goto next_key; | |||
1815 | } | |||
1816 | prim_hitmask[i] &= ~(3ULL << (hit_index << 1)); | |||
1817 | } | |||
1818 | ||||
1819 | while (sec_hitmask[i]) { | |||
1820 | uint32_t hit_index = | |||
1821 | __builtin_ctzl(sec_hitmask[i]) | |||
1822 | >> 1; | |||
1823 | uint32_t key_idx = | |||
1824 | secondary_bkt[i]->key_idx[hit_index]; | |||
1825 | const struct rte_hash_key *key_slot = | |||
1826 | (const struct rte_hash_key *)( | |||
1827 | (const char *)h->key_store + | |||
1828 | key_idx * h->key_entry_size); | |||
1829 | ||||
1830 | /* | |||
1831 | * If key index is 0, do not compare key, | |||
1832 | * as it is checking the dummy slot | |||
1833 | */ | |||
1834 | ||||
1835 | if (!!key_idx & | |||
1836 | !rte_hash_cmp_eq( | |||
1837 | key_slot->key, keys[i], h)) { | |||
1838 | if (data != NULL((void*)0)) | |||
1839 | data[i] = key_slot->pdata; | |||
1840 | ||||
1841 | hits |= 1ULL << i; | |||
1842 | positions[i] = key_idx - 1; | |||
1843 | goto next_key; | |||
1844 | } | |||
1845 | sec_hitmask[i] &= ~(3ULL << (hit_index << 1)); | |||
1846 | } | |||
1847 | next_key: | |||
1848 | continue; | |||
1849 | } | |||
1850 | ||||
1851 | /* all found, do not need to go through ext bkt */ | |||
1852 | if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) { | |||
1853 | if (hit_mask != NULL((void*)0)) | |||
1854 | *hit_mask = hits; | |||
1855 | __hash_rw_reader_unlock(h); | |||
1856 | return; | |||
1857 | } | |||
1858 | ||||
1859 | /* need to check ext buckets for match */ | |||
1860 | for (i = 0; i < num_keys; i++) { | |||
1861 | if ((hits & (1ULL << i)) != 0) | |||
1862 | continue; | |||
1863 | next_bkt = secondary_bkt[i]->next; | |||
1864 | FOR_EACH_BUCKET(cur_bkt, next_bkt)for (cur_bkt = next_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
1865 | if (data != NULL((void*)0)) | |||
1866 | ret = search_one_bucket_l(h, keys[i], | |||
1867 | sig[i], &data[i], cur_bkt); | |||
1868 | else | |||
1869 | ret = search_one_bucket_l(h, keys[i], | |||
1870 | sig[i], NULL((void*)0), cur_bkt); | |||
1871 | if (ret != -1) { | |||
1872 | positions[i] = ret; | |||
1873 | hits |= 1ULL << i; | |||
1874 | break; | |||
1875 | } | |||
1876 | } | |||
1877 | } | |||
1878 | ||||
1879 | __hash_rw_reader_unlock(h); | |||
1880 | ||||
1881 | if (hit_mask != NULL((void*)0)) | |||
1882 | *hit_mask = hits; | |||
1883 | } | |||
1884 | ||||
1885 | static inline void | |||
1886 | __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys, | |||
1887 | int32_t num_keys, int32_t *positions, | |||
1888 | uint64_t *hit_mask, void *data[]) | |||
1889 | { | |||
1890 | uint64_t hits = 0; | |||
1891 | int32_t i; | |||
1892 | int32_t ret; | |||
1893 | uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1894 | uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1895 | uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1896 | uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1897 | const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1898 | const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1899 | uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX64] = {0}; | |||
1900 | uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX64] = {0}; | |||
1901 | struct rte_hash_bucket *cur_bkt, *next_bkt; | |||
1902 | void *pdata[RTE_HASH_LOOKUP_BULK_MAX64]; | |||
1903 | uint32_t cnt_b, cnt_a; | |||
1904 | ||||
1905 | /* Prefetch first keys */ | |||
1906 | for (i = 0; i < PREFETCH_OFFSET4 && i < num_keys; i++) | |||
1907 | rte_prefetch0(keys[i]); | |||
1908 | ||||
1909 | /* | |||
1910 | * Prefetch rest of the keys, calculate primary and | |||
1911 | * secondary bucket and prefetch them | |||
1912 | */ | |||
1913 | for (i = 0; i < (num_keys - PREFETCH_OFFSET4); i++) { | |||
1914 | rte_prefetch0(keys[i + PREFETCH_OFFSET4]); | |||
1915 | ||||
1916 | prim_hash[i] = rte_hash_hash(h, keys[i]); | |||
1917 | ||||
1918 | sig[i] = get_short_sig(prim_hash[i]); | |||
1919 | prim_index[i] = get_prim_bucket_index(h, prim_hash[i]); | |||
1920 | sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]); | |||
1921 | ||||
1922 | primary_bkt[i] = &h->buckets[prim_index[i]]; | |||
1923 | secondary_bkt[i] = &h->buckets[sec_index[i]]; | |||
1924 | ||||
1925 | rte_prefetch0(primary_bkt[i]); | |||
1926 | rte_prefetch0(secondary_bkt[i]); | |||
1927 | } | |||
1928 | ||||
1929 | /* Calculate and prefetch rest of the buckets */ | |||
1930 | for (; i < num_keys; i++) { | |||
1931 | prim_hash[i] = rte_hash_hash(h, keys[i]); | |||
1932 | ||||
1933 | sig[i] = get_short_sig(prim_hash[i]); | |||
1934 | prim_index[i] = get_prim_bucket_index(h, prim_hash[i]); | |||
1935 | sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]); | |||
1936 | ||||
1937 | primary_bkt[i] = &h->buckets[prim_index[i]]; | |||
1938 | secondary_bkt[i] = &h->buckets[sec_index[i]]; | |||
1939 | ||||
1940 | rte_prefetch0(primary_bkt[i]); | |||
1941 | rte_prefetch0(secondary_bkt[i]); | |||
1942 | } | |||
1943 | ||||
1944 | for (i = 0; i < num_keys; i++) | |||
1945 | positions[i] = -ENOENT2; | |||
1946 | ||||
1947 | do { | |||
1948 | /* Load the table change counter before the lookup | |||
1949 | * starts. Acquire semantics will make sure that | |||
1950 | * loads in compare_signatures are not hoisted. | |||
1951 | */ | |||
1952 | cnt_b = __atomic_load_n(h->tbl_chng_cnt, | |||
1953 | __ATOMIC_ACQUIRE2); | |||
1954 | ||||
1955 | /* Compare signatures and prefetch key slot of first hit */ | |||
1956 | for (i = 0; i < num_keys; i++) { | |||
1957 | compare_signatures(&prim_hitmask[i], &sec_hitmask[i], | |||
1958 | primary_bkt[i], secondary_bkt[i], | |||
1959 | sig[i], h->sig_cmp_fn); | |||
1960 | ||||
1961 | if (prim_hitmask[i]) { | |||
1962 | uint32_t first_hit = | |||
1963 | __builtin_ctzl(prim_hitmask[i]) | |||
1964 | >> 1; | |||
1965 | uint32_t key_idx = | |||
1966 | primary_bkt[i]->key_idx[first_hit]; | |||
1967 | const struct rte_hash_key *key_slot = | |||
1968 | (const struct rte_hash_key *)( | |||
1969 | (const char *)h->key_store + | |||
1970 | key_idx * h->key_entry_size); | |||
1971 | rte_prefetch0(key_slot); | |||
1972 | continue; | |||
1973 | } | |||
1974 | ||||
1975 | if (sec_hitmask[i]) { | |||
1976 | uint32_t first_hit = | |||
1977 | __builtin_ctzl(sec_hitmask[i]) | |||
1978 | >> 1; | |||
1979 | uint32_t key_idx = | |||
1980 | secondary_bkt[i]->key_idx[first_hit]; | |||
1981 | const struct rte_hash_key *key_slot = | |||
1982 | (const struct rte_hash_key *)( | |||
1983 | (const char *)h->key_store + | |||
1984 | key_idx * h->key_entry_size); | |||
1985 | rte_prefetch0(key_slot); | |||
1986 | } | |||
1987 | } | |||
1988 | ||||
1989 | /* Compare keys, first hits in primary first */ | |||
1990 | for (i = 0; i < num_keys; i++) { | |||
1991 | while (prim_hitmask[i]) { | |||
1992 | uint32_t hit_index = | |||
1993 | __builtin_ctzl(prim_hitmask[i]) | |||
1994 | >> 1; | |||
1995 | uint32_t key_idx = | |||
1996 | __atomic_load_n( | |||
1997 | &primary_bkt[i]->key_idx[hit_index], | |||
1998 | __ATOMIC_ACQUIRE2); | |||
1999 | const struct rte_hash_key *key_slot = | |||
2000 | (const struct rte_hash_key *)( | |||
2001 | (const char *)h->key_store + | |||
2002 | key_idx * h->key_entry_size); | |||
2003 | ||||
2004 | if (key_idx != EMPTY_SLOT0) | |||
2005 | pdata[i] = __atomic_load_n( | |||
2006 | &key_slot->pdata, | |||
2007 | __ATOMIC_ACQUIRE2); | |||
2008 | /* | |||
2009 | * If key index is 0, do not compare key, | |||
2010 | * as it is checking the dummy slot | |||
2011 | */ | |||
2012 | if (!!key_idx & | |||
2013 | !rte_hash_cmp_eq( | |||
2014 | key_slot->key, keys[i], h)) { | |||
2015 | if (data != NULL((void*)0)) | |||
2016 | data[i] = pdata[i]; | |||
2017 | ||||
2018 | hits |= 1ULL << i; | |||
2019 | positions[i] = key_idx - 1; | |||
2020 | goto next_key; | |||
2021 | } | |||
2022 | prim_hitmask[i] &= ~(3ULL << (hit_index << 1)); | |||
2023 | } | |||
2024 | ||||
2025 | while (sec_hitmask[i]) { | |||
2026 | uint32_t hit_index = | |||
2027 | __builtin_ctzl(sec_hitmask[i]) | |||
2028 | >> 1; | |||
2029 | uint32_t key_idx = | |||
2030 | __atomic_load_n( | |||
2031 | &secondary_bkt[i]->key_idx[hit_index], | |||
2032 | __ATOMIC_ACQUIRE2); | |||
2033 | const struct rte_hash_key *key_slot = | |||
2034 | (const struct rte_hash_key *)( | |||
2035 | (const char *)h->key_store + | |||
2036 | key_idx * h->key_entry_size); | |||
2037 | ||||
2038 | if (key_idx != EMPTY_SLOT0) | |||
2039 | pdata[i] = __atomic_load_n( | |||
2040 | &key_slot->pdata, | |||
2041 | __ATOMIC_ACQUIRE2); | |||
2042 | /* | |||
2043 | * If key index is 0, do not compare key, | |||
2044 | * as it is checking the dummy slot | |||
2045 | */ | |||
2046 | ||||
2047 | if (!!key_idx & | |||
2048 | !rte_hash_cmp_eq( | |||
2049 | key_slot->key, keys[i], h)) { | |||
2050 | if (data != NULL((void*)0)) | |||
2051 | data[i] = pdata[i]; | |||
2052 | ||||
2053 | hits |= 1ULL << i; | |||
2054 | positions[i] = key_idx - 1; | |||
2055 | goto next_key; | |||
2056 | } | |||
2057 | sec_hitmask[i] &= ~(3ULL << (hit_index << 1)); | |||
2058 | } | |||
2059 | next_key: | |||
2060 | continue; | |||
2061 | } | |||
2062 | ||||
2063 | /* all found, do not need to go through ext bkt */ | |||
2064 | if (hits == ((1ULL << num_keys) - 1)) { | |||
2065 | if (hit_mask != NULL((void*)0)) | |||
2066 | *hit_mask = hits; | |||
2067 | return; | |||
2068 | } | |||
2069 | /* need to check ext buckets for match */ | |||
2070 | if (h->ext_table_support) { | |||
2071 | for (i = 0; i < num_keys; i++) { | |||
2072 | if ((hits & (1ULL << i)) != 0) | |||
2073 | continue; | |||
2074 | next_bkt = secondary_bkt[i]->next; | |||
2075 | FOR_EACH_BUCKET(cur_bkt, next_bkt)for (cur_bkt = next_bkt; cur_bkt != ((void*)0); cur_bkt = cur_bkt ->next) { | |||
2076 | if (data != NULL((void*)0)) | |||
2077 | ret = search_one_bucket_lf(h, | |||
2078 | keys[i], sig[i], | |||
2079 | &data[i], cur_bkt); | |||
2080 | else | |||
2081 | ret = search_one_bucket_lf(h, | |||
2082 | keys[i], sig[i], | |||
2083 | NULL((void*)0), cur_bkt); | |||
2084 | if (ret != -1) { | |||
2085 | positions[i] = ret; | |||
2086 | hits |= 1ULL << i; | |||
2087 | break; | |||
2088 | } | |||
2089 | } | |||
2090 | } | |||
2091 | } | |||
2092 | /* The loads of sig_current in compare_signatures | |||
2093 | * should not move below the load from tbl_chng_cnt. | |||
2094 | */ | |||
2095 | __atomic_thread_fence(__ATOMIC_ACQUIRE2); | |||
2096 | /* Re-read the table change counter to check if the | |||
2097 | * table has changed during search. If yes, re-do | |||
2098 | * the search. | |||
2099 | * This load should not get hoisted. The load | |||
2100 | * acquires on cnt_b, primary key index and secondary | |||
2101 | * key index will make sure that it does not get | |||
2102 | * hoisted. | |||
2103 | */ | |||
2104 | cnt_a = __atomic_load_n(h->tbl_chng_cnt, | |||
2105 | __ATOMIC_ACQUIRE2); | |||
2106 | } while (cnt_b != cnt_a); | |||
2107 | ||||
2108 | if (hit_mask != NULL((void*)0)) | |||
2109 | *hit_mask = hits; | |||
2110 | } | |||
2111 | ||||
2112 | static inline void | |||
2113 | __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, | |||
2114 | int32_t num_keys, int32_t *positions, | |||
2115 | uint64_t *hit_mask, void *data[]) | |||
2116 | { | |||
2117 | if (h->readwrite_concur_lf_support) | |||
2118 | __rte_hash_lookup_bulk_lf(h, keys, num_keys, positions, | |||
2119 | hit_mask, data); | |||
2120 | else | |||
2121 | __rte_hash_lookup_bulk_l(h, keys, num_keys, positions, | |||
2122 | hit_mask, data); | |||
2123 | } | |||
2124 | ||||
2125 | int | |||
2126 | rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, | |||
2127 | uint32_t num_keys, int32_t *positions) | |||
2128 | { | |||
2129 | RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || | |||
2130 | (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || | |||
2131 | (positions == NULL)), -EINVAL); | |||
2132 | ||||
2133 | __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL((void*)0), NULL((void*)0)); | |||
2134 | return 0; | |||
2135 | } | |||
2136 | ||||
2137 | int | |||
2138 | rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, | |||
2139 | uint32_t num_keys, uint64_t *hit_mask, void *data[]) | |||
2140 | { | |||
2141 | RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || | |||
2142 | (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || | |||
2143 | (hit_mask == NULL)), -EINVAL); | |||
2144 | ||||
2145 | int32_t positions[num_keys]; | |||
2146 | ||||
2147 | __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data); | |||
2148 | ||||
2149 | /* Return number of hits */ | |||
2150 | return __builtin_popcountl(*hit_mask); | |||
2151 | } | |||
2152 | ||||
2153 | int32_t | |||
2154 | rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next) | |||
2155 | { | |||
2156 | uint32_t bucket_idx, idx, position; | |||
2157 | struct rte_hash_key *next_key; | |||
2158 | ||||
2159 | RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL); | |||
2160 | ||||
2161 | const uint32_t total_entries_main = h->num_buckets * | |||
2162 | RTE_HASH_BUCKET_ENTRIES8; | |||
2163 | const uint32_t total_entries = total_entries_main << 1; | |||
2164 | ||||
2165 | /* Out of bounds of all buckets (both main table and ext table) */ | |||
2166 | if (*next >= total_entries_main) | |||
2167 | goto extend_table; | |||
2168 | ||||
2169 | /* Calculate bucket and index of current iterator */ | |||
2170 | bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES8; | |||
2171 | idx = *next % RTE_HASH_BUCKET_ENTRIES8; | |||
2172 | ||||
2173 | /* If current position is empty, go to the next one */ | |||
2174 | while ((position = __atomic_load_n(&h->buckets[bucket_idx].key_idx[idx], | |||
2175 | __ATOMIC_ACQUIRE2)) == EMPTY_SLOT0) { | |||
2176 | (*next)++; | |||
2177 | /* End of table */ | |||
2178 | if (*next == total_entries_main) | |||
2179 | goto extend_table; | |||
2180 | bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES8; | |||
2181 | idx = *next % RTE_HASH_BUCKET_ENTRIES8; | |||
2182 | } | |||
2183 | ||||
2184 | __hash_rw_reader_lock(h); | |||
2185 | next_key = (struct rte_hash_key *) ((char *)h->key_store + | |||
2186 | position * h->key_entry_size); | |||
2187 | /* Return key and data */ | |||
2188 | *key = next_key->key; | |||
2189 | *data = next_key->pdata; | |||
2190 | ||||
2191 | __hash_rw_reader_unlock(h); | |||
2192 | ||||
2193 | /* Increment iterator */ | |||
2194 | (*next)++; | |||
2195 | ||||
2196 | return position - 1; | |||
2197 | ||||
2198 | /* Begin to iterate extendable buckets */ | |||
2199 | extend_table: | |||
2200 | /* Out of total bound or if ext bucket feature is not enabled */ | |||
2201 | if (*next >= total_entries || !h->ext_table_support) | |||
2202 | return -ENOENT2; | |||
2203 | ||||
2204 | bucket_idx = (*next - total_entries_main) / RTE_HASH_BUCKET_ENTRIES8; | |||
2205 | idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES8; | |||
2206 | ||||
2207 | while ((position = h->buckets_ext[bucket_idx].key_idx[idx]) == EMPTY_SLOT0) { | |||
2208 | (*next)++; | |||
2209 | if (*next == total_entries) | |||
2210 | return -ENOENT2; | |||
2211 | bucket_idx = (*next - total_entries_main) / | |||
2212 | RTE_HASH_BUCKET_ENTRIES8; | |||
2213 | idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES8; | |||
2214 | } | |||
2215 | __hash_rw_reader_lock(h); | |||
2216 | next_key = (struct rte_hash_key *) ((char *)h->key_store + | |||
2217 | position * h->key_entry_size); | |||
2218 | /* Return key and data */ | |||
2219 | *key = next_key->key; | |||
2220 | *data = next_key->pdata; | |||
2221 | ||||
2222 | __hash_rw_reader_unlock(h); | |||
2223 | ||||
2224 | /* Increment iterator */ | |||
2225 | (*next)++; | |||
2226 | return position - 1; | |||
2227 | } |