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