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