1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2016 Intel Corporation
3 * Copyright(c) 2018 Arm Limited
11 #include <sys/queue.h>
13 #include <rte_common.h>
14 #include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */
16 #include <rte_memcpy.h>
17 #include <rte_prefetch.h>
18 #include <rte_branch_prediction.h>
19 #include <rte_malloc.h>
21 #include <rte_eal_memconfig.h>
22 #include <rte_per_lcore.h>
23 #include <rte_errno.h>
24 #include <rte_string_fns.h>
25 #include <rte_cpuflags.h>
26 #include <rte_rwlock.h>
27 #include <rte_spinlock.h>
29 #include <rte_compat.h>
30 #include <rte_pause.h>
33 #include "rte_cuckoo_hash.h"
35 #define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET) \
36 for (CURRENT_BKT = START_BUCKET; \
37 CURRENT_BKT != NULL; \
38 CURRENT_BKT = CURRENT_BKT->next)
40 TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
42 static struct rte_tailq_elem rte_hash_tailq = {
45 EAL_REGISTER_TAILQ(rte_hash_tailq)
48 rte_hash_find_existing(const char *name)
50 struct rte_hash *h = NULL;
51 struct rte_tailq_entry *te;
52 struct rte_hash_list *hash_list;
54 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
56 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
57 TAILQ_FOREACH(te, hash_list, next) {
58 h = (struct rte_hash *) te->data;
59 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
62 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
71 static inline struct rte_hash_bucket *
72 rte_hash_get_last_bkt(struct rte_hash_bucket *lst_bkt)
74 while (lst_bkt->next != NULL)
75 lst_bkt = lst_bkt->next;
79 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
81 h->cmp_jump_table_idx = KEY_CUSTOM;
82 h->rte_hash_custom_cmp_eq = func;
86 rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)
88 if (h->cmp_jump_table_idx == KEY_CUSTOM)
89 return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len);
91 return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);
95 * We use higher 16 bits of hash as the signature value stored in table.
96 * We use the lower bits for the primary bucket
97 * location. Then we XOR primary bucket location and the signature
98 * to get the secondary bucket location. This is same as
99 * proposed in Bin Fan, et al's paper
100 * "MemC3: Compact and Concurrent MemCache with Dumber Caching and
101 * Smarter Hashing". The benefit to use
102 * XOR is that one could derive the alternative bucket location
103 * by only using the current bucket location and the signature.
105 static inline uint16_t
106 get_short_sig(const hash_sig_t hash)
111 static inline uint32_t
112 get_prim_bucket_index(const struct rte_hash *h, const hash_sig_t hash)
114 return hash & h->bucket_bitmask;
117 static inline uint32_t
118 get_alt_bucket_index(const struct rte_hash *h,
119 uint32_t cur_bkt_idx, uint16_t sig)
121 return (cur_bkt_idx ^ sig) & h->bucket_bitmask;
125 rte_hash_create(const struct rte_hash_parameters *params)
127 struct rte_hash *h = NULL;
128 struct rte_tailq_entry *te = NULL;
129 struct rte_hash_list *hash_list;
130 struct rte_ring *r = NULL;
131 struct rte_ring *r_ext = NULL;
132 char hash_name[RTE_HASH_NAMESIZE];
134 void *buckets = NULL;
135 void *buckets_ext = NULL;
136 char ring_name[RTE_RING_NAMESIZE];
137 char ext_ring_name[RTE_RING_NAMESIZE];
138 unsigned num_key_slots;
140 unsigned int hw_trans_mem_support = 0, use_local_cache = 0;
141 unsigned int ext_table_support = 0;
142 unsigned int readwrite_concur_support = 0;
143 unsigned int writer_takes_lock = 0;
144 unsigned int no_free_on_del = 0;
145 uint32_t *tbl_chng_cnt = NULL;
146 unsigned int readwrite_concur_lf_support = 0;
148 rte_hash_function default_hash_func = (rte_hash_function)rte_jhash;
150 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
152 if (params == NULL) {
153 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
157 /* Check for valid parameters */
158 if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
159 (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
160 (params->key_len == 0)) {
162 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
166 /* Validate correct usage of extra options */
167 if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) &&
168 (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF)) {
170 RTE_LOG(ERR, HASH, "rte_hash_create: choose rw concurrency or "
171 "rw concurrency lock free\n");
175 if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) &&
176 (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)) {
178 RTE_LOG(ERR, HASH, "rte_hash_create: extendable bucket "
179 "feature not supported with rw concurrency "
184 /* Check extra flags field to check extra options. */
185 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
186 hw_trans_mem_support = 1;
188 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) {
190 writer_takes_lock = 1;
193 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) {
194 readwrite_concur_support = 1;
195 writer_takes_lock = 1;
198 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)
199 ext_table_support = 1;
201 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL)
204 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) {
205 readwrite_concur_lf_support = 1;
206 /* Enable not freeing internal memory/index on delete */
210 /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
213 * Increase number of slots by total number of indices
214 * that can be stored in the lcore caches
215 * except for the first cache
217 num_key_slots = params->entries + (RTE_MAX_LCORE - 1) *
218 (LCORE_CACHE_SIZE - 1) + 1;
220 num_key_slots = params->entries + 1;
222 snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
223 /* Create ring (Dummy slot index is not enqueued) */
224 r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots),
225 params->socket_id, 0);
227 RTE_LOG(ERR, HASH, "memory allocation failed\n");
231 const uint32_t num_buckets = rte_align32pow2(params->entries) /
232 RTE_HASH_BUCKET_ENTRIES;
234 /* Create ring for extendable buckets. */
235 if (ext_table_support) {
236 snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s",
238 r_ext = rte_ring_create(ext_ring_name,
239 rte_align32pow2(num_buckets + 1),
240 params->socket_id, 0);
243 RTE_LOG(ERR, HASH, "ext buckets memory allocation "
249 snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
251 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
253 /* guarantee there's no existing: this is normally already checked
254 * by ring creation above */
255 TAILQ_FOREACH(te, hash_list, next) {
256 h = (struct rte_hash *) te->data;
257 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
267 te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
269 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
273 h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
274 RTE_CACHE_LINE_SIZE, params->socket_id);
277 RTE_LOG(ERR, HASH, "memory allocation failed\n");
281 buckets = rte_zmalloc_socket(NULL,
282 num_buckets * sizeof(struct rte_hash_bucket),
283 RTE_CACHE_LINE_SIZE, params->socket_id);
285 if (buckets == NULL) {
286 RTE_LOG(ERR, HASH, "buckets memory allocation failed\n");
290 /* Allocate same number of extendable buckets */
291 if (ext_table_support) {
292 buckets_ext = rte_zmalloc_socket(NULL,
293 num_buckets * sizeof(struct rte_hash_bucket),
294 RTE_CACHE_LINE_SIZE, params->socket_id);
295 if (buckets_ext == NULL) {
296 RTE_LOG(ERR, HASH, "ext buckets memory allocation "
300 /* Populate ext bkt ring. We reserve 0 similar to the
301 * key-data slot, just in case in future we want to
302 * use bucket index for the linked list and 0 means NULL
305 for (i = 1; i <= num_buckets; i++)
306 rte_ring_sp_enqueue(r_ext, (void *)((uintptr_t) i));
309 const uint32_t key_entry_size =
310 RTE_ALIGN(sizeof(struct rte_hash_key) + params->key_len,
312 const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
314 k = rte_zmalloc_socket(NULL, key_tbl_size,
315 RTE_CACHE_LINE_SIZE, params->socket_id);
318 RTE_LOG(ERR, HASH, "memory allocation failed\n");
322 tbl_chng_cnt = rte_zmalloc_socket(NULL, sizeof(uint32_t),
323 RTE_CACHE_LINE_SIZE, params->socket_id);
325 if (tbl_chng_cnt == NULL) {
326 RTE_LOG(ERR, HASH, "memory allocation failed\n");
331 * If x86 architecture is used, select appropriate compare function,
332 * which may use x86 intrinsics, otherwise use memcmp
334 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
335 /* Select function to compare keys */
336 switch (params->key_len) {
338 h->cmp_jump_table_idx = KEY_16_BYTES;
341 h->cmp_jump_table_idx = KEY_32_BYTES;
344 h->cmp_jump_table_idx = KEY_48_BYTES;
347 h->cmp_jump_table_idx = KEY_64_BYTES;
350 h->cmp_jump_table_idx = KEY_80_BYTES;
353 h->cmp_jump_table_idx = KEY_96_BYTES;
356 h->cmp_jump_table_idx = KEY_112_BYTES;
359 h->cmp_jump_table_idx = KEY_128_BYTES;
362 /* If key is not multiple of 16, use generic memcmp */
363 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
366 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
369 if (use_local_cache) {
370 h->local_free_slots = rte_zmalloc_socket(NULL,
371 sizeof(struct lcore_cache) * RTE_MAX_LCORE,
372 RTE_CACHE_LINE_SIZE, params->socket_id);
375 /* Default hash function */
376 #if defined(RTE_ARCH_X86)
377 default_hash_func = (rte_hash_function)rte_hash_crc;
378 #elif defined(RTE_ARCH_ARM64)
379 if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32))
380 default_hash_func = (rte_hash_function)rte_hash_crc;
382 /* Setup hash context */
383 snprintf(h->name, sizeof(h->name), "%s", params->name);
384 h->entries = params->entries;
385 h->key_len = params->key_len;
386 h->key_entry_size = key_entry_size;
387 h->hash_func_init_val = params->hash_func_init_val;
389 h->num_buckets = num_buckets;
390 h->bucket_bitmask = h->num_buckets - 1;
391 h->buckets = buckets;
392 h->buckets_ext = buckets_ext;
393 h->free_ext_bkts = r_ext;
394 h->hash_func = (params->hash_func == NULL) ?
395 default_hash_func : params->hash_func;
398 h->tbl_chng_cnt = tbl_chng_cnt;
399 *h->tbl_chng_cnt = 0;
400 h->hw_trans_mem_support = hw_trans_mem_support;
401 h->use_local_cache = use_local_cache;
402 h->readwrite_concur_support = readwrite_concur_support;
403 h->ext_table_support = ext_table_support;
404 h->writer_takes_lock = writer_takes_lock;
405 h->no_free_on_del = no_free_on_del;
406 h->readwrite_concur_lf_support = readwrite_concur_lf_support;
408 #if defined(RTE_ARCH_X86)
409 if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))
410 h->sig_cmp_fn = RTE_HASH_COMPARE_SSE;
413 h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR;
415 /* Writer threads need to take the lock when:
416 * 1) RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY is enabled OR
417 * 2) RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD is enabled
419 if (h->writer_takes_lock) {
420 h->readwrite_lock = rte_malloc(NULL, sizeof(rte_rwlock_t),
421 RTE_CACHE_LINE_SIZE);
422 if (h->readwrite_lock == NULL)
425 rte_rwlock_init(h->readwrite_lock);
428 /* Populate free slots ring. Entry zero is reserved for key misses. */
429 for (i = 1; i < num_key_slots; i++)
430 rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
432 te->data = (void *) h;
433 TAILQ_INSERT_TAIL(hash_list, te, next);
434 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
438 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
441 rte_ring_free(r_ext);
445 rte_free(buckets_ext);
447 rte_free(tbl_chng_cnt);
452 rte_hash_free(struct rte_hash *h)
454 struct rte_tailq_entry *te;
455 struct rte_hash_list *hash_list;
460 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
462 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
464 /* find out tailq entry */
465 TAILQ_FOREACH(te, hash_list, next) {
466 if (te->data == (void *) h)
471 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
475 TAILQ_REMOVE(hash_list, te, next);
477 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
479 if (h->use_local_cache)
480 rte_free(h->local_free_slots);
481 if (h->writer_takes_lock)
482 rte_free(h->readwrite_lock);
483 rte_ring_free(h->free_slots);
484 rte_ring_free(h->free_ext_bkts);
485 rte_free(h->key_store);
486 rte_free(h->buckets);
487 rte_free(h->buckets_ext);
488 rte_free(h->tbl_chng_cnt);
494 rte_hash_hash(const struct rte_hash *h, const void *key)
496 /* calc hash result by key */
497 return h->hash_func(key, h->key_len, h->hash_func_init_val);
501 rte_hash_count(const struct rte_hash *h)
503 uint32_t tot_ring_cnt, cached_cnt = 0;
509 if (h->use_local_cache) {
510 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
511 (LCORE_CACHE_SIZE - 1);
512 for (i = 0; i < RTE_MAX_LCORE; i++)
513 cached_cnt += h->local_free_slots[i].len;
515 ret = tot_ring_cnt - rte_ring_count(h->free_slots) -
518 tot_ring_cnt = h->entries;
519 ret = tot_ring_cnt - rte_ring_count(h->free_slots);
524 /* Read write locks implemented using rte_rwlock */
526 __hash_rw_writer_lock(const struct rte_hash *h)
528 if (h->writer_takes_lock && h->hw_trans_mem_support)
529 rte_rwlock_write_lock_tm(h->readwrite_lock);
530 else if (h->writer_takes_lock)
531 rte_rwlock_write_lock(h->readwrite_lock);
535 __hash_rw_reader_lock(const struct rte_hash *h)
537 if (h->readwrite_concur_support && h->hw_trans_mem_support)
538 rte_rwlock_read_lock_tm(h->readwrite_lock);
539 else if (h->readwrite_concur_support)
540 rte_rwlock_read_lock(h->readwrite_lock);
544 __hash_rw_writer_unlock(const struct rte_hash *h)
546 if (h->writer_takes_lock && h->hw_trans_mem_support)
547 rte_rwlock_write_unlock_tm(h->readwrite_lock);
548 else if (h->writer_takes_lock)
549 rte_rwlock_write_unlock(h->readwrite_lock);
553 __hash_rw_reader_unlock(const struct rte_hash *h)
555 if (h->readwrite_concur_support && h->hw_trans_mem_support)
556 rte_rwlock_read_unlock_tm(h->readwrite_lock);
557 else if (h->readwrite_concur_support)
558 rte_rwlock_read_unlock(h->readwrite_lock);
562 rte_hash_reset(struct rte_hash *h)
565 uint32_t tot_ring_cnt, i;
570 __hash_rw_writer_lock(h);
571 memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket));
572 memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
573 *h->tbl_chng_cnt = 0;
575 /* clear the free ring */
576 while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
579 /* clear free extendable bucket ring and memory */
580 if (h->ext_table_support) {
581 memset(h->buckets_ext, 0, h->num_buckets *
582 sizeof(struct rte_hash_bucket));
583 while (rte_ring_dequeue(h->free_ext_bkts, &ptr) == 0)
587 /* Repopulate the free slots ring. Entry zero is reserved for key misses */
588 if (h->use_local_cache)
589 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
590 (LCORE_CACHE_SIZE - 1);
592 tot_ring_cnt = h->entries;
594 for (i = 1; i < tot_ring_cnt + 1; i++)
595 rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));
597 /* Repopulate the free ext bkt ring. */
598 if (h->ext_table_support) {
599 for (i = 1; i <= h->num_buckets; i++)
600 rte_ring_sp_enqueue(h->free_ext_bkts,
601 (void *)((uintptr_t) i));
604 if (h->use_local_cache) {
605 /* Reset local caches per lcore */
606 for (i = 0; i < RTE_MAX_LCORE; i++)
607 h->local_free_slots[i].len = 0;
609 __hash_rw_writer_unlock(h);
613 * Function called to enqueue back an index in the cache/ring,
614 * as slot has not being used and it can be used in the
615 * next addition attempt.
618 enqueue_slot_back(const struct rte_hash *h,
619 struct lcore_cache *cached_free_slots,
622 if (h->use_local_cache) {
623 cached_free_slots->objs[cached_free_slots->len] = slot_id;
624 cached_free_slots->len++;
626 rte_ring_sp_enqueue(h->free_slots, slot_id);
629 /* Search a key from bucket and update its data.
630 * Writer holds the lock before calling this.
632 static inline int32_t
633 search_and_update(const struct rte_hash *h, void *data, const void *key,
634 struct rte_hash_bucket *bkt, uint16_t sig)
637 struct rte_hash_key *k, *keys = h->key_store;
639 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
640 if (bkt->sig_current[i] == sig) {
641 k = (struct rte_hash_key *) ((char *)keys +
642 bkt->key_idx[i] * h->key_entry_size);
643 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
644 /* 'pdata' acts as the synchronization point
645 * when an existing hash entry is updated.
646 * Key is not updated in this case.
648 __atomic_store_n(&k->pdata,
652 * Return index where key is stored,
653 * subtracting the first dummy index
655 return bkt->key_idx[i] - 1;
662 /* Only tries to insert at one bucket (@prim_bkt) without trying to push
664 * return 1 if matching existing key, return 0 if succeeds, return -1 for no
667 static inline int32_t
668 rte_hash_cuckoo_insert_mw(const struct rte_hash *h,
669 struct rte_hash_bucket *prim_bkt,
670 struct rte_hash_bucket *sec_bkt,
671 const struct rte_hash_key *key, void *data,
672 uint16_t sig, uint32_t new_idx,
676 struct rte_hash_bucket *cur_bkt;
679 __hash_rw_writer_lock(h);
680 /* Check if key was inserted after last check but before this
681 * protected region in case of inserting duplicated keys.
683 ret = search_and_update(h, data, key, prim_bkt, sig);
685 __hash_rw_writer_unlock(h);
690 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
691 ret = search_and_update(h, data, key, cur_bkt, sig);
693 __hash_rw_writer_unlock(h);
699 /* Insert new entry if there is room in the primary
702 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
703 /* Check if slot is available */
704 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
705 prim_bkt->sig_current[i] = sig;
706 /* Key can be of arbitrary length, so it is
707 * not possible to store it atomically.
708 * Hence the new key element's memory stores
709 * (key as well as data) should be complete
710 * before it is referenced.
712 __atomic_store_n(&prim_bkt->key_idx[i],
718 __hash_rw_writer_unlock(h);
720 if (i != RTE_HASH_BUCKET_ENTRIES)
727 /* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill
728 * the path head with new entry (sig, alt_hash, new_idx)
729 * return 1 if matched key found, return -1 if cuckoo path invalided and fail,
730 * return 0 if succeeds.
733 rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,
734 struct rte_hash_bucket *bkt,
735 struct rte_hash_bucket *alt_bkt,
736 const struct rte_hash_key *key, void *data,
737 struct queue_node *leaf, uint32_t leaf_slot,
738 uint16_t sig, uint32_t new_idx,
741 uint32_t prev_alt_bkt_idx;
742 struct rte_hash_bucket *cur_bkt;
743 struct queue_node *prev_node, *curr_node = leaf;
744 struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
745 uint32_t prev_slot, curr_slot = leaf_slot;
748 __hash_rw_writer_lock(h);
750 /* In case empty slot was gone before entering protected region */
751 if (curr_bkt->key_idx[curr_slot] != EMPTY_SLOT) {
752 __hash_rw_writer_unlock(h);
756 /* Check if key was inserted after last check but before this
759 ret = search_and_update(h, data, key, bkt, sig);
761 __hash_rw_writer_unlock(h);
766 FOR_EACH_BUCKET(cur_bkt, alt_bkt) {
767 ret = search_and_update(h, data, key, cur_bkt, sig);
769 __hash_rw_writer_unlock(h);
775 while (likely(curr_node->prev != NULL)) {
776 prev_node = curr_node->prev;
777 prev_bkt = prev_node->bkt;
778 prev_slot = curr_node->prev_slot;
780 prev_alt_bkt_idx = get_alt_bucket_index(h,
781 prev_node->cur_bkt_idx,
782 prev_bkt->sig_current[prev_slot]);
784 if (unlikely(&h->buckets[prev_alt_bkt_idx]
786 /* revert it to empty, otherwise duplicated keys */
787 __atomic_store_n(&curr_bkt->key_idx[curr_slot],
790 __hash_rw_writer_unlock(h);
794 if (h->readwrite_concur_lf_support) {
795 /* Inform the previous move. The current move need
796 * not be informed now as the current bucket entry
797 * is present in both primary and secondary.
798 * Since there is one writer, load acquires on
799 * tbl_chng_cnt are not required.
801 __atomic_store_n(h->tbl_chng_cnt,
802 *h->tbl_chng_cnt + 1,
804 /* The stores to sig_alt and sig_current should not
805 * move above the store to tbl_chng_cnt.
807 __atomic_thread_fence(__ATOMIC_RELEASE);
810 /* Need to swap current/alt sig to allow later
811 * Cuckoo insert to move elements back to its
812 * primary bucket if available
814 curr_bkt->sig_current[curr_slot] =
815 prev_bkt->sig_current[prev_slot];
816 /* Release the updated bucket entry */
817 __atomic_store_n(&curr_bkt->key_idx[curr_slot],
818 prev_bkt->key_idx[prev_slot],
821 curr_slot = prev_slot;
822 curr_node = prev_node;
823 curr_bkt = curr_node->bkt;
826 if (h->readwrite_concur_lf_support) {
827 /* Inform the previous move. The current move need
828 * not be informed now as the current bucket entry
829 * is present in both primary and secondary.
830 * Since there is one writer, load acquires on
831 * tbl_chng_cnt are not required.
833 __atomic_store_n(h->tbl_chng_cnt,
834 *h->tbl_chng_cnt + 1,
836 /* The stores to sig_alt and sig_current should not
837 * move above the store to tbl_chng_cnt.
839 __atomic_thread_fence(__ATOMIC_RELEASE);
842 curr_bkt->sig_current[curr_slot] = sig;
843 /* Release the new bucket entry */
844 __atomic_store_n(&curr_bkt->key_idx[curr_slot],
848 __hash_rw_writer_unlock(h);
855 * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
859 rte_hash_cuckoo_make_space_mw(const struct rte_hash *h,
860 struct rte_hash_bucket *bkt,
861 struct rte_hash_bucket *sec_bkt,
862 const struct rte_hash_key *key, void *data,
863 uint16_t sig, uint32_t bucket_idx,
864 uint32_t new_idx, int32_t *ret_val)
867 struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
868 struct queue_node *tail, *head;
869 struct rte_hash_bucket *curr_bkt, *alt_bkt;
870 uint32_t cur_idx, alt_idx;
876 tail->prev_slot = -1;
877 tail->cur_bkt_idx = bucket_idx;
879 /* Cuckoo bfs Search */
880 while (likely(tail != head && head <
881 queue + RTE_HASH_BFS_QUEUE_MAX_LEN -
882 RTE_HASH_BUCKET_ENTRIES)) {
883 curr_bkt = tail->bkt;
884 cur_idx = tail->cur_bkt_idx;
885 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
886 if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
887 int32_t ret = rte_hash_cuckoo_move_insert_mw(h,
888 bkt, sec_bkt, key, data,
891 if (likely(ret != -1))
895 /* Enqueue new node and keep prev node info */
896 alt_idx = get_alt_bucket_index(h, cur_idx,
897 curr_bkt->sig_current[i]);
898 alt_bkt = &(h->buckets[alt_idx]);
900 head->cur_bkt_idx = alt_idx;
911 static inline int32_t
912 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
913 hash_sig_t sig, void *data)
916 uint32_t prim_bucket_idx, sec_bucket_idx;
917 struct rte_hash_bucket *prim_bkt, *sec_bkt, *cur_bkt;
918 struct rte_hash_key *new_k, *keys = h->key_store;
919 void *slot_id = NULL;
920 void *ext_bkt_id = NULL;
921 uint32_t new_idx, bkt_id;
926 struct lcore_cache *cached_free_slots = NULL;
928 struct rte_hash_bucket *last;
930 short_sig = get_short_sig(sig);
931 prim_bucket_idx = get_prim_bucket_index(h, sig);
932 sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
933 prim_bkt = &h->buckets[prim_bucket_idx];
934 sec_bkt = &h->buckets[sec_bucket_idx];
935 rte_prefetch0(prim_bkt);
936 rte_prefetch0(sec_bkt);
938 /* Check if key is already inserted in primary location */
939 __hash_rw_writer_lock(h);
940 ret = search_and_update(h, data, key, prim_bkt, short_sig);
942 __hash_rw_writer_unlock(h);
946 /* Check if key is already inserted in secondary location */
947 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
948 ret = search_and_update(h, data, key, cur_bkt, short_sig);
950 __hash_rw_writer_unlock(h);
955 __hash_rw_writer_unlock(h);
957 /* Did not find a match, so get a new slot for storing the new key */
958 if (h->use_local_cache) {
959 lcore_id = rte_lcore_id();
960 cached_free_slots = &h->local_free_slots[lcore_id];
961 /* Try to get a free slot from the local cache */
962 if (cached_free_slots->len == 0) {
963 /* Need to get another burst of free slots from global ring */
964 n_slots = rte_ring_mc_dequeue_burst(h->free_slots,
965 cached_free_slots->objs,
966 LCORE_CACHE_SIZE, NULL);
971 cached_free_slots->len += n_slots;
974 /* Get a free slot from the local cache */
975 cached_free_slots->len--;
976 slot_id = cached_free_slots->objs[cached_free_slots->len];
978 if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) {
983 new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
984 new_idx = (uint32_t)((uintptr_t) slot_id);
986 rte_memcpy(new_k->key, key, h->key_len);
987 /* Key can be of arbitrary length, so it is not possible to store
988 * it atomically. Hence the new key element's memory stores
989 * (key as well as data) should be complete before it is referenced.
990 * 'pdata' acts as the synchronization point when an existing hash
993 __atomic_store_n(&new_k->pdata,
997 /* Find an empty slot and insert */
998 ret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data,
999 short_sig, new_idx, &ret_val);
1002 else if (ret == 1) {
1003 enqueue_slot_back(h, cached_free_slots, slot_id);
1007 /* Primary bucket full, need to make space for new entry */
1008 ret = rte_hash_cuckoo_make_space_mw(h, prim_bkt, sec_bkt, key, data,
1009 short_sig, prim_bucket_idx, new_idx, &ret_val);
1012 else if (ret == 1) {
1013 enqueue_slot_back(h, cached_free_slots, slot_id);
1017 /* Also search secondary bucket to get better occupancy */
1018 ret = rte_hash_cuckoo_make_space_mw(h, sec_bkt, prim_bkt, key, data,
1019 short_sig, sec_bucket_idx, new_idx, &ret_val);
1023 else if (ret == 1) {
1024 enqueue_slot_back(h, cached_free_slots, slot_id);
1028 /* if ext table not enabled, we failed the insertion */
1029 if (!h->ext_table_support) {
1030 enqueue_slot_back(h, cached_free_slots, slot_id);
1034 /* Now we need to go through the extendable bucket. Protection is needed
1035 * to protect all extendable bucket processes.
1037 __hash_rw_writer_lock(h);
1038 /* We check for duplicates again since could be inserted before the lock */
1039 ret = search_and_update(h, data, key, prim_bkt, short_sig);
1041 enqueue_slot_back(h, cached_free_slots, slot_id);
1045 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1046 ret = search_and_update(h, data, key, cur_bkt, short_sig);
1048 enqueue_slot_back(h, cached_free_slots, slot_id);
1053 /* Search sec and ext buckets to find an empty entry to insert. */
1054 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1055 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1056 /* Check if slot is available */
1057 if (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {
1058 cur_bkt->sig_current[i] = short_sig;
1059 cur_bkt->key_idx[i] = new_idx;
1060 __hash_rw_writer_unlock(h);
1066 /* Failed to get an empty entry from extendable buckets. Link a new
1067 * extendable bucket. We first get a free bucket from ring.
1069 if (rte_ring_sc_dequeue(h->free_ext_bkts, &ext_bkt_id) != 0) {
1074 bkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1;
1075 /* Use the first location of the new bucket */
1076 (h->buckets_ext[bkt_id]).sig_current[0] = short_sig;
1077 (h->buckets_ext[bkt_id]).key_idx[0] = new_idx;
1078 /* Link the new bucket to sec bucket linked list */
1079 last = rte_hash_get_last_bkt(sec_bkt);
1080 last->next = &h->buckets_ext[bkt_id];
1081 __hash_rw_writer_unlock(h);
1085 __hash_rw_writer_unlock(h);
1091 rte_hash_add_key_with_hash(const struct rte_hash *h,
1092 const void *key, hash_sig_t sig)
1094 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1095 return __rte_hash_add_key_with_hash(h, key, sig, 0);
1099 rte_hash_add_key(const struct rte_hash *h, const void *key)
1101 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1102 return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
1106 rte_hash_add_key_with_hash_data(const struct rte_hash *h,
1107 const void *key, hash_sig_t sig, void *data)
1111 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1112 ret = __rte_hash_add_key_with_hash(h, key, sig, data);
1120 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)
1124 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1126 ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data);
1133 /* Search one bucket to find the match key */
1134 static inline int32_t
1135 search_one_bucket(const struct rte_hash *h, const void *key, uint16_t sig,
1136 void **data, const struct rte_hash_bucket *bkt)
1141 struct rte_hash_key *k, *keys = h->key_store;
1143 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1144 key_idx = __atomic_load_n(&bkt->key_idx[i],
1146 if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {
1147 k = (struct rte_hash_key *) ((char *)keys +
1148 key_idx * h->key_entry_size);
1149 pdata = __atomic_load_n(&k->pdata,
1152 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1156 * Return index where key is stored,
1157 * subtracting the first dummy index
1166 static inline int32_t
1167 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
1168 hash_sig_t sig, void **data)
1170 uint32_t prim_bucket_idx, sec_bucket_idx;
1171 struct rte_hash_bucket *bkt, *cur_bkt;
1172 uint32_t cnt_b, cnt_a;
1176 short_sig = get_short_sig(sig);
1177 prim_bucket_idx = get_prim_bucket_index(h, sig);
1178 sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1180 __hash_rw_reader_lock(h);
1183 /* Load the table change counter before the lookup
1184 * starts. Acquire semantics will make sure that
1185 * loads in search_one_bucket are not hoisted.
1187 cnt_b = __atomic_load_n(h->tbl_chng_cnt,
1190 /* Check if key is in primary location */
1191 bkt = &h->buckets[prim_bucket_idx];
1192 ret = search_one_bucket(h, key, short_sig, data, bkt);
1194 __hash_rw_reader_unlock(h);
1197 /* Calculate secondary hash */
1198 bkt = &h->buckets[sec_bucket_idx];
1200 /* Check if key is in secondary location */
1201 FOR_EACH_BUCKET(cur_bkt, bkt) {
1202 ret = search_one_bucket(h, key, short_sig,
1205 __hash_rw_reader_unlock(h);
1210 /* The loads of sig_current in search_one_bucket
1211 * should not move below the load from tbl_chng_cnt.
1213 __atomic_thread_fence(__ATOMIC_ACQUIRE);
1214 /* Re-read the table change counter to check if the
1215 * table has changed during search. If yes, re-do
1217 * This load should not get hoisted. The load
1218 * acquires on cnt_b, key index in primary bucket
1219 * and key index in secondary bucket will make sure
1220 * that it does not get hoisted.
1222 cnt_a = __atomic_load_n(h->tbl_chng_cnt,
1224 } while (cnt_b != cnt_a);
1226 __hash_rw_reader_unlock(h);
1232 rte_hash_lookup_with_hash(const struct rte_hash *h,
1233 const void *key, hash_sig_t sig)
1235 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1236 return __rte_hash_lookup_with_hash(h, key, sig, NULL);
1240 rte_hash_lookup(const struct rte_hash *h, const void *key)
1242 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1243 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
1247 rte_hash_lookup_with_hash_data(const struct rte_hash *h,
1248 const void *key, hash_sig_t sig, void **data)
1250 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1251 return __rte_hash_lookup_with_hash(h, key, sig, data);
1255 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)
1257 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1258 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
1262 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
1264 unsigned lcore_id, n_slots;
1265 struct lcore_cache *cached_free_slots;
1267 if (h->use_local_cache) {
1268 lcore_id = rte_lcore_id();
1269 cached_free_slots = &h->local_free_slots[lcore_id];
1270 /* Cache full, need to free it. */
1271 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
1272 /* Need to enqueue the free slots in global ring. */
1273 n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
1274 cached_free_slots->objs,
1275 LCORE_CACHE_SIZE, NULL);
1276 cached_free_slots->len -= n_slots;
1278 /* Put index of new free slot in cache. */
1279 cached_free_slots->objs[cached_free_slots->len] =
1280 (void *)((uintptr_t)bkt->key_idx[i]);
1281 cached_free_slots->len++;
1283 rte_ring_sp_enqueue(h->free_slots,
1284 (void *)((uintptr_t)bkt->key_idx[i]));
1288 /* Compact the linked list by moving key from last entry in linked list to the
1292 __rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) {
1294 struct rte_hash_bucket *last_bkt;
1299 last_bkt = rte_hash_get_last_bkt(cur_bkt);
1301 for (i = RTE_HASH_BUCKET_ENTRIES - 1; i >= 0; i--) {
1302 if (last_bkt->key_idx[i] != EMPTY_SLOT) {
1303 cur_bkt->key_idx[pos] = last_bkt->key_idx[i];
1304 cur_bkt->sig_current[pos] = last_bkt->sig_current[i];
1305 last_bkt->sig_current[i] = NULL_SIGNATURE;
1306 last_bkt->key_idx[i] = EMPTY_SLOT;
1312 /* Search one bucket and remove the matched key.
1313 * Writer is expected to hold the lock while calling this
1316 static inline int32_t
1317 search_and_remove(const struct rte_hash *h, const void *key,
1318 struct rte_hash_bucket *bkt, uint16_t sig, int *pos)
1320 struct rte_hash_key *k, *keys = h->key_store;
1324 /* Check if key is in bucket */
1325 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1326 key_idx = __atomic_load_n(&bkt->key_idx[i],
1328 if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {
1329 k = (struct rte_hash_key *) ((char *)keys +
1330 key_idx * h->key_entry_size);
1331 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1332 bkt->sig_current[i] = NULL_SIGNATURE;
1333 /* Free the key store index if
1334 * no_free_on_del is disabled.
1336 if (!h->no_free_on_del)
1337 remove_entry(h, bkt, i);
1339 __atomic_store_n(&bkt->key_idx[i],
1345 * Return index where key is stored,
1346 * subtracting the first dummy index
1355 static inline int32_t
1356 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
1359 uint32_t prim_bucket_idx, sec_bucket_idx;
1360 struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt;
1361 struct rte_hash_bucket *cur_bkt;
1366 short_sig = get_short_sig(sig);
1367 prim_bucket_idx = get_prim_bucket_index(h, sig);
1368 sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1369 prim_bkt = &h->buckets[prim_bucket_idx];
1371 __hash_rw_writer_lock(h);
1372 /* look for key in primary bucket */
1373 ret = search_and_remove(h, key, prim_bkt, short_sig, &pos);
1375 __rte_hash_compact_ll(prim_bkt, pos);
1376 last_bkt = prim_bkt->next;
1377 prev_bkt = prim_bkt;
1381 /* Calculate secondary hash */
1382 sec_bkt = &h->buckets[sec_bucket_idx];
1384 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1385 ret = search_and_remove(h, key, cur_bkt, short_sig, &pos);
1387 __rte_hash_compact_ll(cur_bkt, pos);
1388 last_bkt = sec_bkt->next;
1394 __hash_rw_writer_unlock(h);
1397 /* Search last bucket to see if empty to be recycled */
1400 __hash_rw_writer_unlock(h);
1403 while (last_bkt->next) {
1404 prev_bkt = last_bkt;
1405 last_bkt = last_bkt->next;
1408 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1409 if (last_bkt->key_idx[i] != EMPTY_SLOT)
1412 /* found empty bucket and recycle */
1413 if (i == RTE_HASH_BUCKET_ENTRIES) {
1414 prev_bkt->next = last_bkt->next = NULL;
1415 uint32_t index = last_bkt - h->buckets_ext + 1;
1416 rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);
1419 __hash_rw_writer_unlock(h);
1424 rte_hash_del_key_with_hash(const struct rte_hash *h,
1425 const void *key, hash_sig_t sig)
1427 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1428 return __rte_hash_del_key_with_hash(h, key, sig);
1432 rte_hash_del_key(const struct rte_hash *h, const void *key)
1434 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1435 return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
1439 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
1442 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1444 struct rte_hash_key *k, *keys = h->key_store;
1445 k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
1450 __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
1458 int __rte_experimental
1459 rte_hash_free_key_with_position(const struct rte_hash *h,
1460 const int32_t position)
1462 RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
1464 unsigned int lcore_id, n_slots;
1465 struct lcore_cache *cached_free_slots;
1466 const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
1469 if (position >= total_entries)
1472 if (h->use_local_cache) {
1473 lcore_id = rte_lcore_id();
1474 cached_free_slots = &h->local_free_slots[lcore_id];
1475 /* Cache full, need to free it. */
1476 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
1477 /* Need to enqueue the free slots in global ring. */
1478 n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
1479 cached_free_slots->objs,
1480 LCORE_CACHE_SIZE, NULL);
1481 cached_free_slots->len -= n_slots;
1483 /* Put index of new free slot in cache. */
1484 cached_free_slots->objs[cached_free_slots->len] =
1485 (void *)((uintptr_t)position);
1486 cached_free_slots->len++;
1488 rte_ring_sp_enqueue(h->free_slots,
1489 (void *)((uintptr_t)position));
1496 compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
1497 const struct rte_hash_bucket *prim_bkt,
1498 const struct rte_hash_bucket *sec_bkt,
1500 enum rte_hash_sig_compare_function sig_cmp_fn)
1504 /* For match mask the first bit of every two bits indicates the match */
1505 switch (sig_cmp_fn) {
1506 #ifdef RTE_MACHINE_CPUFLAG_SSE2
1507 case RTE_HASH_COMPARE_SSE:
1508 /* Compare all signatures in the bucket */
1509 *prim_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1511 (__m128i const *)prim_bkt->sig_current),
1512 _mm_set1_epi16(sig)));
1513 /* Compare all signatures in the bucket */
1514 *sec_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1516 (__m128i const *)sec_bkt->sig_current),
1517 _mm_set1_epi16(sig)));
1521 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1522 *prim_hash_matches |=
1523 ((sig == prim_bkt->sig_current[i]) << (i << 1));
1524 *sec_hash_matches |=
1525 ((sig == sec_bkt->sig_current[i]) << (i << 1));
1530 #define PREFETCH_OFFSET 4
1532 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1533 int32_t num_keys, int32_t *positions,
1534 uint64_t *hit_mask, void *data[])
1539 uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
1540 uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
1541 uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
1542 uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
1543 const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1544 const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1545 uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1546 uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1547 struct rte_hash_bucket *cur_bkt, *next_bkt;
1548 void *pdata[RTE_HASH_LOOKUP_BULK_MAX];
1549 uint32_t cnt_b, cnt_a;
1551 /* Prefetch first keys */
1552 for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
1553 rte_prefetch0(keys[i]);
1556 * Prefetch rest of the keys, calculate primary and
1557 * secondary bucket and prefetch them
1559 for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
1560 rte_prefetch0(keys[i + PREFETCH_OFFSET]);
1562 prim_hash[i] = rte_hash_hash(h, keys[i]);
1564 sig[i] = get_short_sig(prim_hash[i]);
1565 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1566 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1568 primary_bkt[i] = &h->buckets[prim_index[i]];
1569 secondary_bkt[i] = &h->buckets[sec_index[i]];
1571 rte_prefetch0(primary_bkt[i]);
1572 rte_prefetch0(secondary_bkt[i]);
1575 /* Calculate and prefetch rest of the buckets */
1576 for (; i < num_keys; i++) {
1577 prim_hash[i] = rte_hash_hash(h, keys[i]);
1579 sig[i] = get_short_sig(prim_hash[i]);
1580 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1581 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1583 primary_bkt[i] = &h->buckets[prim_index[i]];
1584 secondary_bkt[i] = &h->buckets[sec_index[i]];
1586 rte_prefetch0(primary_bkt[i]);
1587 rte_prefetch0(secondary_bkt[i]);
1590 __hash_rw_reader_lock(h);
1592 /* Load the table change counter before the lookup
1593 * starts. Acquire semantics will make sure that
1594 * loads in compare_signatures are not hoisted.
1596 cnt_b = __atomic_load_n(h->tbl_chng_cnt,
1599 /* Compare signatures and prefetch key slot of first hit */
1600 for (i = 0; i < num_keys; i++) {
1601 compare_signatures(&prim_hitmask[i], &sec_hitmask[i],
1602 primary_bkt[i], secondary_bkt[i],
1603 sig[i], h->sig_cmp_fn);
1605 if (prim_hitmask[i]) {
1606 uint32_t first_hit =
1607 __builtin_ctzl(prim_hitmask[i])
1610 primary_bkt[i]->key_idx[first_hit];
1611 const struct rte_hash_key *key_slot =
1612 (const struct rte_hash_key *)(
1613 (const char *)h->key_store +
1614 key_idx * h->key_entry_size);
1615 rte_prefetch0(key_slot);
1619 if (sec_hitmask[i]) {
1620 uint32_t first_hit =
1621 __builtin_ctzl(sec_hitmask[i])
1624 secondary_bkt[i]->key_idx[first_hit];
1625 const struct rte_hash_key *key_slot =
1626 (const struct rte_hash_key *)(
1627 (const char *)h->key_store +
1628 key_idx * h->key_entry_size);
1629 rte_prefetch0(key_slot);
1633 /* Compare keys, first hits in primary first */
1634 for (i = 0; i < num_keys; i++) {
1635 positions[i] = -ENOENT;
1636 while (prim_hitmask[i]) {
1637 uint32_t hit_index =
1638 __builtin_ctzl(prim_hitmask[i])
1642 &primary_bkt[i]->key_idx[hit_index],
1644 const struct rte_hash_key *key_slot =
1645 (const struct rte_hash_key *)(
1646 (const char *)h->key_store +
1647 key_idx * h->key_entry_size);
1649 if (key_idx != EMPTY_SLOT)
1650 pdata[i] = __atomic_load_n(
1654 * If key index is 0, do not compare key,
1655 * as it is checking the dummy slot
1659 key_slot->key, keys[i], h)) {
1664 positions[i] = key_idx - 1;
1667 prim_hitmask[i] &= ~(3ULL << (hit_index << 1));
1670 while (sec_hitmask[i]) {
1671 uint32_t hit_index =
1672 __builtin_ctzl(sec_hitmask[i])
1676 &secondary_bkt[i]->key_idx[hit_index],
1678 const struct rte_hash_key *key_slot =
1679 (const struct rte_hash_key *)(
1680 (const char *)h->key_store +
1681 key_idx * h->key_entry_size);
1683 if (key_idx != EMPTY_SLOT)
1684 pdata[i] = __atomic_load_n(
1688 * If key index is 0, do not compare key,
1689 * as it is checking the dummy slot
1694 key_slot->key, keys[i], h)) {
1699 positions[i] = key_idx - 1;
1702 sec_hitmask[i] &= ~(3ULL << (hit_index << 1));
1708 /* The loads of sig_current in compare_signatures
1709 * should not move below the load from tbl_chng_cnt.
1711 __atomic_thread_fence(__ATOMIC_ACQUIRE);
1712 /* Re-read the table change counter to check if the
1713 * table has changed during search. If yes, re-do
1715 * This load should not get hoisted. The load
1716 * acquires on cnt_b, primary key index and secondary
1717 * key index will make sure that it does not get
1720 cnt_a = __atomic_load_n(h->tbl_chng_cnt,
1722 } while (cnt_b != cnt_a);
1724 /* all found, do not need to go through ext bkt */
1725 if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {
1726 if (hit_mask != NULL)
1728 __hash_rw_reader_unlock(h);
1732 /* need to check ext buckets for match */
1733 for (i = 0; i < num_keys; i++) {
1734 if ((hits & (1ULL << i)) != 0)
1736 next_bkt = secondary_bkt[i]->next;
1737 FOR_EACH_BUCKET(cur_bkt, next_bkt) {
1739 ret = search_one_bucket(h, keys[i],
1740 sig[i], &data[i], cur_bkt);
1742 ret = search_one_bucket(h, keys[i],
1743 sig[i], NULL, cur_bkt);
1752 __hash_rw_reader_unlock(h);
1754 if (hit_mask != NULL)
1759 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1760 uint32_t num_keys, int32_t *positions)
1762 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1763 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1764 (positions == NULL)), -EINVAL);
1766 __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL);
1771 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
1772 uint32_t num_keys, uint64_t *hit_mask, void *data[])
1774 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1775 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1776 (hit_mask == NULL)), -EINVAL);
1778 int32_t positions[num_keys];
1780 __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data);
1782 /* Return number of hits */
1783 return __builtin_popcountl(*hit_mask);
1787 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
1789 uint32_t bucket_idx, idx, position;
1790 struct rte_hash_key *next_key;
1792 RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
1794 const uint32_t total_entries_main = h->num_buckets *
1795 RTE_HASH_BUCKET_ENTRIES;
1796 const uint32_t total_entries = total_entries_main << 1;
1798 /* Out of bounds of all buckets (both main table and ext table) */
1799 if (*next >= total_entries_main)
1802 /* Calculate bucket and index of current iterator */
1803 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1804 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1806 /* If current position is empty, go to the next one */
1807 while ((position = __atomic_load_n(&h->buckets[bucket_idx].key_idx[idx],
1808 __ATOMIC_ACQUIRE)) == EMPTY_SLOT) {
1811 if (*next == total_entries_main)
1813 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1814 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1817 __hash_rw_reader_lock(h);
1818 next_key = (struct rte_hash_key *) ((char *)h->key_store +
1819 position * h->key_entry_size);
1820 /* Return key and data */
1821 *key = next_key->key;
1822 *data = next_key->pdata;
1824 __hash_rw_reader_unlock(h);
1826 /* Increment iterator */
1829 return position - 1;
1831 /* Begin to iterate extendable buckets */
1833 /* Out of total bound or if ext bucket feature is not enabled */
1834 if (*next >= total_entries || !h->ext_table_support)
1837 bucket_idx = (*next - total_entries_main) / RTE_HASH_BUCKET_ENTRIES;
1838 idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
1840 while ((position = h->buckets_ext[bucket_idx].key_idx[idx]) == EMPTY_SLOT) {
1842 if (*next == total_entries)
1844 bucket_idx = (*next - total_entries_main) /
1845 RTE_HASH_BUCKET_ENTRIES;
1846 idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
1848 __hash_rw_reader_lock(h);
1849 next_key = (struct rte_hash_key *) ((char *)h->key_store +
1850 position * h->key_entry_size);
1851 /* Return key and data */
1852 *key = next_key->key;
1853 *data = next_key->pdata;
1855 __hash_rw_reader_unlock(h);
1857 /* Increment iterator */
1859 return position - 1;