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