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