1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2016 Intel Corporation
10 #include <sys/queue.h>
12 #include <rte_common.h>
13 #include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */
15 #include <rte_memcpy.h>
16 #include <rte_prefetch.h>
17 #include <rte_branch_prediction.h>
18 #include <rte_malloc.h>
20 #include <rte_eal_memconfig.h>
21 #include <rte_per_lcore.h>
22 #include <rte_errno.h>
23 #include <rte_string_fns.h>
24 #include <rte_cpuflags.h>
25 #include <rte_rwlock.h>
26 #include <rte_spinlock.h>
28 #include <rte_compat.h>
29 #include <rte_pause.h>
32 #include "rte_cuckoo_hash.h"
34 #if defined(RTE_ARCH_X86)
35 #include "rte_cuckoo_hash_x86.h"
38 TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
40 static struct rte_tailq_elem rte_hash_tailq = {
43 EAL_REGISTER_TAILQ(rte_hash_tailq)
46 rte_hash_find_existing(const char *name)
48 struct rte_hash *h = NULL;
49 struct rte_tailq_entry *te;
50 struct rte_hash_list *hash_list;
52 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
54 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
55 TAILQ_FOREACH(te, hash_list, next) {
56 h = (struct rte_hash *) te->data;
57 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
60 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
69 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
71 h->cmp_jump_table_idx = KEY_CUSTOM;
72 h->rte_hash_custom_cmp_eq = func;
76 rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)
78 if (h->cmp_jump_table_idx == KEY_CUSTOM)
79 return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len);
81 return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);
85 rte_hash_create(const struct rte_hash_parameters *params)
87 struct rte_hash *h = NULL;
88 struct rte_tailq_entry *te = NULL;
89 struct rte_hash_list *hash_list;
90 struct rte_ring *r = NULL;
91 char hash_name[RTE_HASH_NAMESIZE];
94 char ring_name[RTE_RING_NAMESIZE];
95 unsigned num_key_slots;
96 unsigned hw_trans_mem_support = 0;
99 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
101 if (params == NULL) {
102 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
106 /* Check for valid parameters */
107 if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
108 (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
109 !rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) ||
110 (params->key_len == 0)) {
112 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
116 /* Check extra flags field to check extra options. */
117 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
118 hw_trans_mem_support = 1;
120 /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
121 if (hw_trans_mem_support)
123 * Increase number of slots by total number of indices
124 * that can be stored in the lcore caches
125 * except for the first cache
127 num_key_slots = params->entries + (RTE_MAX_LCORE - 1) *
128 LCORE_CACHE_SIZE + 1;
130 num_key_slots = params->entries + 1;
132 snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
133 /* Create ring (Dummy slot index is not enqueued) */
134 r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots - 1),
135 params->socket_id, 0);
137 RTE_LOG(ERR, HASH, "memory allocation failed\n");
141 snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
143 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
145 /* guarantee there's no existing: this is normally already checked
146 * by ring creation above */
147 TAILQ_FOREACH(te, hash_list, next) {
148 h = (struct rte_hash *) te->data;
149 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
159 te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
161 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
165 h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
166 RTE_CACHE_LINE_SIZE, params->socket_id);
169 RTE_LOG(ERR, HASH, "memory allocation failed\n");
173 const uint32_t num_buckets = rte_align32pow2(params->entries)
174 / RTE_HASH_BUCKET_ENTRIES;
176 buckets = rte_zmalloc_socket(NULL,
177 num_buckets * sizeof(struct rte_hash_bucket),
178 RTE_CACHE_LINE_SIZE, params->socket_id);
180 if (buckets == NULL) {
181 RTE_LOG(ERR, HASH, "memory allocation failed\n");
185 const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;
186 const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
188 k = rte_zmalloc_socket(NULL, key_tbl_size,
189 RTE_CACHE_LINE_SIZE, params->socket_id);
192 RTE_LOG(ERR, HASH, "memory allocation failed\n");
197 * If x86 architecture is used, select appropriate compare function,
198 * which may use x86 intrinsics, otherwise use memcmp
200 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
201 /* Select function to compare keys */
202 switch (params->key_len) {
204 h->cmp_jump_table_idx = KEY_16_BYTES;
207 h->cmp_jump_table_idx = KEY_32_BYTES;
210 h->cmp_jump_table_idx = KEY_48_BYTES;
213 h->cmp_jump_table_idx = KEY_64_BYTES;
216 h->cmp_jump_table_idx = KEY_80_BYTES;
219 h->cmp_jump_table_idx = KEY_96_BYTES;
222 h->cmp_jump_table_idx = KEY_112_BYTES;
225 h->cmp_jump_table_idx = KEY_128_BYTES;
228 /* If key is not multiple of 16, use generic memcmp */
229 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
232 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
235 if (hw_trans_mem_support) {
236 h->local_free_slots = rte_zmalloc_socket(NULL,
237 sizeof(struct lcore_cache) * RTE_MAX_LCORE,
238 RTE_CACHE_LINE_SIZE, params->socket_id);
241 /* Setup hash context */
242 snprintf(h->name, sizeof(h->name), "%s", params->name);
243 h->entries = params->entries;
244 h->key_len = params->key_len;
245 h->key_entry_size = key_entry_size;
246 h->hash_func_init_val = params->hash_func_init_val;
248 h->num_buckets = num_buckets;
249 h->bucket_bitmask = h->num_buckets - 1;
250 h->buckets = buckets;
251 h->hash_func = (params->hash_func == NULL) ?
252 DEFAULT_HASH_FUNC : params->hash_func;
255 h->hw_trans_mem_support = hw_trans_mem_support;
257 #if defined(RTE_ARCH_X86)
258 if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))
259 h->sig_cmp_fn = RTE_HASH_COMPARE_AVX2;
260 else if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))
261 h->sig_cmp_fn = RTE_HASH_COMPARE_SSE;
264 h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR;
266 /* Turn on multi-writer only with explicit flat from user and TM
269 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) {
270 if (h->hw_trans_mem_support) {
271 h->add_key = ADD_KEY_MULTIWRITER_TM;
273 h->add_key = ADD_KEY_MULTIWRITER;
274 h->multiwriter_lock = rte_malloc(NULL,
275 sizeof(rte_spinlock_t),
277 rte_spinlock_init(h->multiwriter_lock);
280 h->add_key = ADD_KEY_SINGLEWRITER;
282 /* Populate free slots ring. Entry zero is reserved for key misses. */
283 for (i = 1; i < params->entries + 1; i++)
284 rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
286 te->data = (void *) h;
287 TAILQ_INSERT_TAIL(hash_list, te, next);
288 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
292 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
303 rte_hash_free(struct rte_hash *h)
305 struct rte_tailq_entry *te;
306 struct rte_hash_list *hash_list;
311 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
313 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
315 /* find out tailq entry */
316 TAILQ_FOREACH(te, hash_list, next) {
317 if (te->data == (void *) h)
322 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
326 TAILQ_REMOVE(hash_list, te, next);
328 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
330 if (h->hw_trans_mem_support)
331 rte_free(h->local_free_slots);
333 if (h->add_key == ADD_KEY_MULTIWRITER)
334 rte_free(h->multiwriter_lock);
335 rte_ring_free(h->free_slots);
336 rte_free(h->key_store);
337 rte_free(h->buckets);
343 rte_hash_hash(const struct rte_hash *h, const void *key)
345 /* calc hash result by key */
346 return h->hash_func(key, h->key_len, h->hash_func_init_val);
349 /* Calc the secondary hash value from the primary hash value of a given key */
350 static inline hash_sig_t
351 rte_hash_secondary_hash(const hash_sig_t primary_hash)
353 static const unsigned all_bits_shift = 12;
354 static const unsigned alt_bits_xor = 0x5bd1e995;
356 uint32_t tag = primary_hash >> all_bits_shift;
358 return primary_hash ^ ((tag + 1) * alt_bits_xor);
362 rte_hash_reset(struct rte_hash *h)
370 memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket));
371 memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
373 /* clear the free ring */
374 while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
377 /* Repopulate the free slots ring. Entry zero is reserved for key misses */
378 for (i = 1; i < h->entries + 1; i++)
379 rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));
381 if (h->hw_trans_mem_support) {
382 /* Reset local caches per lcore */
383 for (i = 0; i < RTE_MAX_LCORE; i++)
384 h->local_free_slots[i].len = 0;
388 /* Search for an entry that can be pushed to its alternative location */
390 make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt,
391 unsigned int *nr_pushes)
395 uint32_t next_bucket_idx;
396 struct rte_hash_bucket *next_bkt[RTE_HASH_BUCKET_ENTRIES];
399 * Push existing item (search for bucket with space in
400 * alternative locations) to its alternative location
402 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
403 /* Search for space in alternative locations */
404 next_bucket_idx = bkt->sig_alt[i] & h->bucket_bitmask;
405 next_bkt[i] = &h->buckets[next_bucket_idx];
406 for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
407 if (next_bkt[i]->key_idx[j] == EMPTY_SLOT)
411 if (j != RTE_HASH_BUCKET_ENTRIES)
415 /* Alternative location has spare room (end of recursive function) */
416 if (i != RTE_HASH_BUCKET_ENTRIES) {
417 next_bkt[i]->sig_alt[j] = bkt->sig_current[i];
418 next_bkt[i]->sig_current[j] = bkt->sig_alt[i];
419 next_bkt[i]->key_idx[j] = bkt->key_idx[i];
423 /* Pick entry that has not been pushed yet */
424 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++)
425 if (bkt->flag[i] == 0)
428 /* All entries have been pushed, so entry cannot be added */
429 if (i == RTE_HASH_BUCKET_ENTRIES || ++(*nr_pushes) > RTE_HASH_MAX_PUSHES)
432 /* Set flag to indicate that this entry is going to be pushed */
435 /* Need room in alternative bucket to insert the pushed entry */
436 ret = make_space_bucket(h, next_bkt[i], nr_pushes);
438 * After recursive function.
439 * Clear flags and insert the pushed entry
440 * in its alternative location if successful,
445 next_bkt[i]->sig_alt[ret] = bkt->sig_current[i];
446 next_bkt[i]->sig_current[ret] = bkt->sig_alt[i];
447 next_bkt[i]->key_idx[ret] = bkt->key_idx[i];
455 * Function called to enqueue back an index in the cache/ring,
456 * as slot has not being used and it can be used in the
457 * next addition attempt.
460 enqueue_slot_back(const struct rte_hash *h,
461 struct lcore_cache *cached_free_slots,
464 if (h->hw_trans_mem_support) {
465 cached_free_slots->objs[cached_free_slots->len] = slot_id;
466 cached_free_slots->len++;
468 rte_ring_sp_enqueue(h->free_slots, slot_id);
471 static inline int32_t
472 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
473 hash_sig_t sig, void *data)
476 uint32_t prim_bucket_idx, sec_bucket_idx;
478 struct rte_hash_bucket *prim_bkt, *sec_bkt;
479 struct rte_hash_key *new_k, *k, *keys = h->key_store;
480 void *slot_id = NULL;
485 struct lcore_cache *cached_free_slots = NULL;
486 unsigned int nr_pushes = 0;
488 if (h->add_key == ADD_KEY_MULTIWRITER)
489 rte_spinlock_lock(h->multiwriter_lock);
491 prim_bucket_idx = sig & h->bucket_bitmask;
492 prim_bkt = &h->buckets[prim_bucket_idx];
493 rte_prefetch0(prim_bkt);
495 alt_hash = rte_hash_secondary_hash(sig);
496 sec_bucket_idx = alt_hash & h->bucket_bitmask;
497 sec_bkt = &h->buckets[sec_bucket_idx];
498 rte_prefetch0(sec_bkt);
500 /* Get a new slot for storing the new key */
501 if (h->hw_trans_mem_support) {
502 lcore_id = rte_lcore_id();
503 cached_free_slots = &h->local_free_slots[lcore_id];
504 /* Try to get a free slot from the local cache */
505 if (cached_free_slots->len == 0) {
506 /* Need to get another burst of free slots from global ring */
507 n_slots = rte_ring_mc_dequeue_burst(h->free_slots,
508 cached_free_slots->objs,
509 LCORE_CACHE_SIZE, NULL);
515 cached_free_slots->len += n_slots;
518 /* Get a free slot from the local cache */
519 cached_free_slots->len--;
520 slot_id = cached_free_slots->objs[cached_free_slots->len];
522 if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) {
528 new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
529 rte_prefetch0(new_k);
530 new_idx = (uint32_t)((uintptr_t) slot_id);
532 /* Check if key is already inserted in primary location */
533 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
534 if (prim_bkt->sig_current[i] == sig &&
535 prim_bkt->sig_alt[i] == alt_hash) {
536 k = (struct rte_hash_key *) ((char *)keys +
537 prim_bkt->key_idx[i] * h->key_entry_size);
538 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
539 /* Enqueue index of free slot back in the ring. */
540 enqueue_slot_back(h, cached_free_slots, slot_id);
544 * Return index where key is stored,
545 * subtracting the first dummy index
547 return prim_bkt->key_idx[i] - 1;
552 /* Check if key is already inserted in secondary location */
553 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
554 if (sec_bkt->sig_alt[i] == sig &&
555 sec_bkt->sig_current[i] == alt_hash) {
556 k = (struct rte_hash_key *) ((char *)keys +
557 sec_bkt->key_idx[i] * h->key_entry_size);
558 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
559 /* Enqueue index of free slot back in the ring. */
560 enqueue_slot_back(h, cached_free_slots, slot_id);
564 * Return index where key is stored,
565 * subtracting the first dummy index
567 return sec_bkt->key_idx[i] - 1;
573 rte_memcpy(new_k->key, key, h->key_len);
576 #if defined(RTE_ARCH_X86) /* currently only x86 support HTM */
577 if (h->add_key == ADD_KEY_MULTIWRITER_TM) {
578 ret = rte_hash_cuckoo_insert_mw_tm(prim_bkt,
579 sig, alt_hash, new_idx);
583 /* Primary bucket full, need to make space for new entry */
584 ret = rte_hash_cuckoo_make_space_mw_tm(h, prim_bkt, sig,
590 /* Also search secondary bucket to get better occupancy */
591 ret = rte_hash_cuckoo_make_space_mw_tm(h, sec_bkt, sig,
598 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
599 /* Check if slot is available */
600 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
601 prim_bkt->sig_current[i] = sig;
602 prim_bkt->sig_alt[i] = alt_hash;
603 prim_bkt->key_idx[i] = new_idx;
608 if (i != RTE_HASH_BUCKET_ENTRIES) {
609 if (h->add_key == ADD_KEY_MULTIWRITER)
610 rte_spinlock_unlock(h->multiwriter_lock);
614 /* Primary bucket full, need to make space for new entry
615 * After recursive function.
616 * Insert the new entry in the position of the pushed entry
617 * if successful or return error and
618 * store the new slot back in the ring
620 ret = make_space_bucket(h, prim_bkt, &nr_pushes);
622 prim_bkt->sig_current[ret] = sig;
623 prim_bkt->sig_alt[ret] = alt_hash;
624 prim_bkt->key_idx[ret] = new_idx;
625 if (h->add_key == ADD_KEY_MULTIWRITER)
626 rte_spinlock_unlock(h->multiwriter_lock);
629 #if defined(RTE_ARCH_X86)
632 /* Error in addition, store new slot back in the ring and return error */
633 enqueue_slot_back(h, cached_free_slots, (void *)((uintptr_t) new_idx));
636 if (h->add_key == ADD_KEY_MULTIWRITER)
637 rte_spinlock_unlock(h->multiwriter_lock);
642 rte_hash_add_key_with_hash(const struct rte_hash *h,
643 const void *key, hash_sig_t sig)
645 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
646 return __rte_hash_add_key_with_hash(h, key, sig, 0);
650 rte_hash_add_key(const struct rte_hash *h, const void *key)
652 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
653 return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
657 rte_hash_add_key_with_hash_data(const struct rte_hash *h,
658 const void *key, hash_sig_t sig, void *data)
662 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
663 ret = __rte_hash_add_key_with_hash(h, key, sig, data);
671 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)
675 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
677 ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data);
683 static inline int32_t
684 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
685 hash_sig_t sig, void **data)
690 struct rte_hash_bucket *bkt;
691 struct rte_hash_key *k, *keys = h->key_store;
693 bucket_idx = sig & h->bucket_bitmask;
694 bkt = &h->buckets[bucket_idx];
696 /* Check if key is in primary location */
697 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
698 if (bkt->sig_current[i] == sig &&
699 bkt->key_idx[i] != EMPTY_SLOT) {
700 k = (struct rte_hash_key *) ((char *)keys +
701 bkt->key_idx[i] * h->key_entry_size);
702 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
706 * Return index where key is stored,
707 * subtracting the first dummy index
709 return bkt->key_idx[i] - 1;
714 /* Calculate secondary hash */
715 alt_hash = rte_hash_secondary_hash(sig);
716 bucket_idx = alt_hash & h->bucket_bitmask;
717 bkt = &h->buckets[bucket_idx];
719 /* Check if key is in secondary location */
720 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
721 if (bkt->sig_current[i] == alt_hash &&
722 bkt->sig_alt[i] == sig) {
723 k = (struct rte_hash_key *) ((char *)keys +
724 bkt->key_idx[i] * h->key_entry_size);
725 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
729 * Return index where key is stored,
730 * subtracting the first dummy index
732 return bkt->key_idx[i] - 1;
741 rte_hash_lookup_with_hash(const struct rte_hash *h,
742 const void *key, hash_sig_t sig)
744 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
745 return __rte_hash_lookup_with_hash(h, key, sig, NULL);
749 rte_hash_lookup(const struct rte_hash *h, const void *key)
751 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
752 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
756 rte_hash_lookup_with_hash_data(const struct rte_hash *h,
757 const void *key, hash_sig_t sig, void **data)
759 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
760 return __rte_hash_lookup_with_hash(h, key, sig, data);
764 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)
766 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
767 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
771 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
773 unsigned lcore_id, n_slots;
774 struct lcore_cache *cached_free_slots;
776 bkt->sig_current[i] = NULL_SIGNATURE;
777 bkt->sig_alt[i] = NULL_SIGNATURE;
778 if (h->hw_trans_mem_support) {
779 lcore_id = rte_lcore_id();
780 cached_free_slots = &h->local_free_slots[lcore_id];
781 /* Cache full, need to free it. */
782 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
783 /* Need to enqueue the free slots in global ring. */
784 n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
785 cached_free_slots->objs,
786 LCORE_CACHE_SIZE, NULL);
787 cached_free_slots->len -= n_slots;
789 /* Put index of new free slot in cache. */
790 cached_free_slots->objs[cached_free_slots->len] =
791 (void *)((uintptr_t)bkt->key_idx[i]);
792 cached_free_slots->len++;
794 rte_ring_sp_enqueue(h->free_slots,
795 (void *)((uintptr_t)bkt->key_idx[i]));
799 static inline int32_t
800 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
806 struct rte_hash_bucket *bkt;
807 struct rte_hash_key *k, *keys = h->key_store;
810 bucket_idx = sig & h->bucket_bitmask;
811 bkt = &h->buckets[bucket_idx];
813 /* Check if key is in primary location */
814 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
815 if (bkt->sig_current[i] == sig &&
816 bkt->key_idx[i] != EMPTY_SLOT) {
817 k = (struct rte_hash_key *) ((char *)keys +
818 bkt->key_idx[i] * h->key_entry_size);
819 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
820 remove_entry(h, bkt, i);
823 * Return index where key is stored,
824 * subtracting the first dummy index
826 ret = bkt->key_idx[i] - 1;
827 bkt->key_idx[i] = EMPTY_SLOT;
833 /* Calculate secondary hash */
834 alt_hash = rte_hash_secondary_hash(sig);
835 bucket_idx = alt_hash & h->bucket_bitmask;
836 bkt = &h->buckets[bucket_idx];
838 /* Check if key is in secondary location */
839 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
840 if (bkt->sig_current[i] == alt_hash &&
841 bkt->key_idx[i] != EMPTY_SLOT) {
842 k = (struct rte_hash_key *) ((char *)keys +
843 bkt->key_idx[i] * h->key_entry_size);
844 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
845 remove_entry(h, bkt, i);
848 * Return index where key is stored,
849 * subtracting the first dummy index
851 ret = bkt->key_idx[i] - 1;
852 bkt->key_idx[i] = EMPTY_SLOT;
862 rte_hash_del_key_with_hash(const struct rte_hash *h,
863 const void *key, hash_sig_t sig)
865 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
866 return __rte_hash_del_key_with_hash(h, key, sig);
870 rte_hash_del_key(const struct rte_hash *h, const void *key)
872 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
873 return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
877 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
880 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
882 struct rte_hash_key *k, *keys = h->key_store;
883 k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
888 __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
897 compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
898 const struct rte_hash_bucket *prim_bkt,
899 const struct rte_hash_bucket *sec_bkt,
900 hash_sig_t prim_hash, hash_sig_t sec_hash,
901 enum rte_hash_sig_compare_function sig_cmp_fn)
905 switch (sig_cmp_fn) {
906 #ifdef RTE_MACHINE_CPUFLAG_AVX2
907 case RTE_HASH_COMPARE_AVX2:
908 *prim_hash_matches = _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32(
910 (__m256i const *)prim_bkt->sig_current),
911 _mm256_set1_epi32(prim_hash)));
912 *sec_hash_matches = _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32(
914 (__m256i const *)sec_bkt->sig_current),
915 _mm256_set1_epi32(sec_hash)));
918 #ifdef RTE_MACHINE_CPUFLAG_SSE2
919 case RTE_HASH_COMPARE_SSE:
920 /* Compare the first 4 signatures in the bucket */
921 *prim_hash_matches = _mm_movemask_ps((__m128)_mm_cmpeq_epi16(
923 (__m128i const *)prim_bkt->sig_current),
924 _mm_set1_epi32(prim_hash)));
925 *prim_hash_matches |= (_mm_movemask_ps((__m128)_mm_cmpeq_epi16(
927 (__m128i const *)&prim_bkt->sig_current[4]),
928 _mm_set1_epi32(prim_hash)))) << 4;
929 /* Compare the first 4 signatures in the bucket */
930 *sec_hash_matches = _mm_movemask_ps((__m128)_mm_cmpeq_epi16(
932 (__m128i const *)sec_bkt->sig_current),
933 _mm_set1_epi32(sec_hash)));
934 *sec_hash_matches |= (_mm_movemask_ps((__m128)_mm_cmpeq_epi16(
936 (__m128i const *)&sec_bkt->sig_current[4]),
937 _mm_set1_epi32(sec_hash)))) << 4;
941 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
942 *prim_hash_matches |=
943 ((prim_hash == prim_bkt->sig_current[i]) << i);
945 ((sec_hash == sec_bkt->sig_current[i]) << i);
951 #define PREFETCH_OFFSET 4
953 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
954 int32_t num_keys, int32_t *positions,
955 uint64_t *hit_mask, void *data[])
959 uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
960 uint32_t sec_hash[RTE_HASH_LOOKUP_BULK_MAX];
961 const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
962 const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
963 uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
964 uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
966 /* Prefetch first keys */
967 for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
968 rte_prefetch0(keys[i]);
971 * Prefetch rest of the keys, calculate primary and
972 * secondary bucket and prefetch them
974 for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
975 rte_prefetch0(keys[i + PREFETCH_OFFSET]);
977 prim_hash[i] = rte_hash_hash(h, keys[i]);
978 sec_hash[i] = rte_hash_secondary_hash(prim_hash[i]);
980 primary_bkt[i] = &h->buckets[prim_hash[i] & h->bucket_bitmask];
981 secondary_bkt[i] = &h->buckets[sec_hash[i] & h->bucket_bitmask];
983 rte_prefetch0(primary_bkt[i]);
984 rte_prefetch0(secondary_bkt[i]);
987 /* Calculate and prefetch rest of the buckets */
988 for (; i < num_keys; i++) {
989 prim_hash[i] = rte_hash_hash(h, keys[i]);
990 sec_hash[i] = rte_hash_secondary_hash(prim_hash[i]);
992 primary_bkt[i] = &h->buckets[prim_hash[i] & h->bucket_bitmask];
993 secondary_bkt[i] = &h->buckets[sec_hash[i] & h->bucket_bitmask];
995 rte_prefetch0(primary_bkt[i]);
996 rte_prefetch0(secondary_bkt[i]);
999 /* Compare signatures and prefetch key slot of first hit */
1000 for (i = 0; i < num_keys; i++) {
1001 compare_signatures(&prim_hitmask[i], &sec_hitmask[i],
1002 primary_bkt[i], secondary_bkt[i],
1003 prim_hash[i], sec_hash[i], h->sig_cmp_fn);
1005 if (prim_hitmask[i]) {
1006 uint32_t first_hit = __builtin_ctzl(prim_hitmask[i]);
1007 uint32_t key_idx = primary_bkt[i]->key_idx[first_hit];
1008 const struct rte_hash_key *key_slot =
1009 (const struct rte_hash_key *)(
1010 (const char *)h->key_store +
1011 key_idx * h->key_entry_size);
1012 rte_prefetch0(key_slot);
1016 if (sec_hitmask[i]) {
1017 uint32_t first_hit = __builtin_ctzl(sec_hitmask[i]);
1018 uint32_t key_idx = secondary_bkt[i]->key_idx[first_hit];
1019 const struct rte_hash_key *key_slot =
1020 (const struct rte_hash_key *)(
1021 (const char *)h->key_store +
1022 key_idx * h->key_entry_size);
1023 rte_prefetch0(key_slot);
1027 /* Compare keys, first hits in primary first */
1028 for (i = 0; i < num_keys; i++) {
1029 positions[i] = -ENOENT;
1030 while (prim_hitmask[i]) {
1031 uint32_t hit_index = __builtin_ctzl(prim_hitmask[i]);
1033 uint32_t key_idx = primary_bkt[i]->key_idx[hit_index];
1034 const struct rte_hash_key *key_slot =
1035 (const struct rte_hash_key *)(
1036 (const char *)h->key_store +
1037 key_idx * h->key_entry_size);
1039 * If key index is 0, do not compare key,
1040 * as it is checking the dummy slot
1042 if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {
1044 data[i] = key_slot->pdata;
1047 positions[i] = key_idx - 1;
1050 prim_hitmask[i] &= ~(1 << (hit_index));
1053 while (sec_hitmask[i]) {
1054 uint32_t hit_index = __builtin_ctzl(sec_hitmask[i]);
1056 uint32_t key_idx = secondary_bkt[i]->key_idx[hit_index];
1057 const struct rte_hash_key *key_slot =
1058 (const struct rte_hash_key *)(
1059 (const char *)h->key_store +
1060 key_idx * h->key_entry_size);
1062 * If key index is 0, do not compare key,
1063 * as it is checking the dummy slot
1066 if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {
1068 data[i] = key_slot->pdata;
1071 positions[i] = key_idx - 1;
1074 sec_hitmask[i] &= ~(1 << (hit_index));
1081 if (hit_mask != NULL)
1086 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1087 uint32_t num_keys, int32_t *positions)
1089 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1090 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1091 (positions == NULL)), -EINVAL);
1093 __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL);
1098 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
1099 uint32_t num_keys, uint64_t *hit_mask, void *data[])
1101 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1102 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1103 (hit_mask == NULL)), -EINVAL);
1105 int32_t positions[num_keys];
1107 __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data);
1109 /* Return number of hits */
1110 return __builtin_popcountl(*hit_mask);
1114 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
1116 uint32_t bucket_idx, idx, position;
1117 struct rte_hash_key *next_key;
1119 RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
1121 const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
1123 if (*next >= total_entries)
1126 /* Calculate bucket and index of current iterator */
1127 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1128 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1130 /* If current position is empty, go to the next one */
1131 while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {
1134 if (*next == total_entries)
1136 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1137 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1140 /* Get position of entry in key table */
1141 position = h->buckets[bucket_idx].key_idx[idx];
1142 next_key = (struct rte_hash_key *) ((char *)h->key_store +
1143 position * h->key_entry_size);
1144 /* Return key and data */
1145 *key = next_key->key;
1146 *data = next_key->pdata;
1148 /* Increment iterator */
1151 return position - 1;