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_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>
31 #include "rte_cuckoo_hash.h"
33 #define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET) \
34 for (CURRENT_BKT = START_BUCKET; \
35 CURRENT_BKT != NULL; \
36 CURRENT_BKT = CURRENT_BKT->next)
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 static inline struct rte_hash_bucket *
70 rte_hash_get_last_bkt(struct rte_hash_bucket *lst_bkt)
72 while (lst_bkt->next != NULL)
73 lst_bkt = lst_bkt->next;
77 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
79 h->cmp_jump_table_idx = KEY_CUSTOM;
80 h->rte_hash_custom_cmp_eq = func;
84 rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)
86 if (h->cmp_jump_table_idx == KEY_CUSTOM)
87 return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len);
89 return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);
93 * We use higher 16 bits of hash as the signature value stored in table.
94 * We use the lower bits for the primary bucket
95 * location. Then we XOR primary bucket location and the signature
96 * to get the secondary bucket location. This is same as
97 * proposed in Bin Fan, et al's paper
98 * "MemC3: Compact and Concurrent MemCache with Dumber Caching and
99 * Smarter Hashing". The benefit to use
100 * XOR is that one could derive the alternative bucket location
101 * by only using the current bucket location and the signature.
103 static inline uint16_t
104 get_short_sig(const hash_sig_t hash)
109 static inline uint32_t
110 get_prim_bucket_index(const struct rte_hash *h, const hash_sig_t hash)
112 return hash & h->bucket_bitmask;
115 static inline uint32_t
116 get_alt_bucket_index(const struct rte_hash *h,
117 uint32_t cur_bkt_idx, uint16_t sig)
119 return (cur_bkt_idx ^ sig) & h->bucket_bitmask;
123 rte_hash_create(const struct rte_hash_parameters *params)
125 struct rte_hash *h = NULL;
126 struct rte_tailq_entry *te = NULL;
127 struct rte_hash_list *hash_list;
128 struct rte_ring *r = NULL;
129 struct rte_ring *r_ext = NULL;
130 char hash_name[RTE_HASH_NAMESIZE];
132 void *buckets = NULL;
133 void *buckets_ext = NULL;
134 char ring_name[RTE_RING_NAMESIZE];
135 char ext_ring_name[RTE_RING_NAMESIZE];
136 unsigned num_key_slots;
138 unsigned int hw_trans_mem_support = 0, use_local_cache = 0;
139 unsigned int ext_table_support = 0;
140 unsigned int readwrite_concur_support = 0;
141 unsigned int writer_takes_lock = 0;
142 unsigned int no_free_on_del = 0;
143 uint32_t *tbl_chng_cnt = NULL;
144 unsigned int readwrite_concur_lf_support = 0;
146 rte_hash_function default_hash_func = (rte_hash_function)rte_jhash;
148 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
150 if (params == NULL) {
151 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
155 /* Check for valid parameters */
156 if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
157 (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
158 (params->key_len == 0)) {
160 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
164 /* Validate correct usage of extra options */
165 if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) &&
166 (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF)) {
168 RTE_LOG(ERR, HASH, "rte_hash_create: choose rw concurrency or "
169 "rw concurrency lock free\n");
173 if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) &&
174 (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)) {
176 RTE_LOG(ERR, HASH, "rte_hash_create: extendable bucket "
177 "feature not supported with rw concurrency "
182 /* Check extra flags field to check extra options. */
183 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
184 hw_trans_mem_support = 1;
186 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) {
188 writer_takes_lock = 1;
191 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) {
192 readwrite_concur_support = 1;
193 writer_takes_lock = 1;
196 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)
197 ext_table_support = 1;
199 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL)
202 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) {
203 readwrite_concur_lf_support = 1;
204 /* Enable not freeing internal memory/index on delete */
208 /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
211 * Increase number of slots by total number of indices
212 * that can be stored in the lcore caches
213 * except for the first cache
215 num_key_slots = params->entries + (RTE_MAX_LCORE - 1) *
216 (LCORE_CACHE_SIZE - 1) + 1;
218 num_key_slots = params->entries + 1;
220 snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
221 /* Create ring (Dummy slot index is not enqueued) */
222 r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots),
223 params->socket_id, 0);
225 RTE_LOG(ERR, HASH, "memory allocation failed\n");
229 const uint32_t num_buckets = rte_align32pow2(params->entries) /
230 RTE_HASH_BUCKET_ENTRIES;
232 /* Create ring for extendable buckets. */
233 if (ext_table_support) {
234 snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s",
236 r_ext = rte_ring_create(ext_ring_name,
237 rte_align32pow2(num_buckets + 1),
238 params->socket_id, 0);
241 RTE_LOG(ERR, HASH, "ext buckets memory allocation "
247 snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
249 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
251 /* guarantee there's no existing: this is normally already checked
252 * by ring creation above */
253 TAILQ_FOREACH(te, hash_list, next) {
254 h = (struct rte_hash *) te->data;
255 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
265 te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
267 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
271 h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
272 RTE_CACHE_LINE_SIZE, params->socket_id);
275 RTE_LOG(ERR, HASH, "memory allocation failed\n");
279 buckets = rte_zmalloc_socket(NULL,
280 num_buckets * sizeof(struct rte_hash_bucket),
281 RTE_CACHE_LINE_SIZE, params->socket_id);
283 if (buckets == NULL) {
284 RTE_LOG(ERR, HASH, "buckets memory allocation failed\n");
288 /* Allocate same number of extendable buckets */
289 if (ext_table_support) {
290 buckets_ext = rte_zmalloc_socket(NULL,
291 num_buckets * sizeof(struct rte_hash_bucket),
292 RTE_CACHE_LINE_SIZE, params->socket_id);
293 if (buckets_ext == NULL) {
294 RTE_LOG(ERR, HASH, "ext buckets memory allocation "
298 /* Populate ext bkt ring. We reserve 0 similar to the
299 * key-data slot, just in case in future we want to
300 * use bucket index for the linked list and 0 means NULL
303 for (i = 1; i <= num_buckets; i++)
304 rte_ring_sp_enqueue(r_ext, (void *)((uintptr_t) i));
307 const uint32_t key_entry_size =
308 RTE_ALIGN(sizeof(struct rte_hash_key) + params->key_len,
310 const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
312 k = rte_zmalloc_socket(NULL, key_tbl_size,
313 RTE_CACHE_LINE_SIZE, params->socket_id);
316 RTE_LOG(ERR, HASH, "memory allocation failed\n");
320 tbl_chng_cnt = rte_zmalloc_socket(NULL, sizeof(uint32_t),
321 RTE_CACHE_LINE_SIZE, params->socket_id);
323 if (tbl_chng_cnt == NULL) {
324 RTE_LOG(ERR, HASH, "memory allocation failed\n");
329 * If x86 architecture is used, select appropriate compare function,
330 * which may use x86 intrinsics, otherwise use memcmp
332 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
333 /* Select function to compare keys */
334 switch (params->key_len) {
336 h->cmp_jump_table_idx = KEY_16_BYTES;
339 h->cmp_jump_table_idx = KEY_32_BYTES;
342 h->cmp_jump_table_idx = KEY_48_BYTES;
345 h->cmp_jump_table_idx = KEY_64_BYTES;
348 h->cmp_jump_table_idx = KEY_80_BYTES;
351 h->cmp_jump_table_idx = KEY_96_BYTES;
354 h->cmp_jump_table_idx = KEY_112_BYTES;
357 h->cmp_jump_table_idx = KEY_128_BYTES;
360 /* If key is not multiple of 16, use generic memcmp */
361 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
364 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
367 if (use_local_cache) {
368 h->local_free_slots = rte_zmalloc_socket(NULL,
369 sizeof(struct lcore_cache) * RTE_MAX_LCORE,
370 RTE_CACHE_LINE_SIZE, params->socket_id);
373 /* Default hash function */
374 #if defined(RTE_ARCH_X86)
375 default_hash_func = (rte_hash_function)rte_hash_crc;
376 #elif defined(RTE_ARCH_ARM64)
377 if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32))
378 default_hash_func = (rte_hash_function)rte_hash_crc;
380 /* Setup hash context */
381 snprintf(h->name, sizeof(h->name), "%s", params->name);
382 h->entries = params->entries;
383 h->key_len = params->key_len;
384 h->key_entry_size = key_entry_size;
385 h->hash_func_init_val = params->hash_func_init_val;
387 h->num_buckets = num_buckets;
388 h->bucket_bitmask = h->num_buckets - 1;
389 h->buckets = buckets;
390 h->buckets_ext = buckets_ext;
391 h->free_ext_bkts = r_ext;
392 h->hash_func = (params->hash_func == NULL) ?
393 default_hash_func : params->hash_func;
396 h->tbl_chng_cnt = tbl_chng_cnt;
397 *h->tbl_chng_cnt = 0;
398 h->hw_trans_mem_support = hw_trans_mem_support;
399 h->use_local_cache = use_local_cache;
400 h->readwrite_concur_support = readwrite_concur_support;
401 h->ext_table_support = ext_table_support;
402 h->writer_takes_lock = writer_takes_lock;
403 h->no_free_on_del = no_free_on_del;
404 h->readwrite_concur_lf_support = readwrite_concur_lf_support;
406 #if defined(RTE_ARCH_X86)
407 if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))
408 h->sig_cmp_fn = RTE_HASH_COMPARE_SSE;
411 h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR;
413 /* Writer threads need to take the lock when:
414 * 1) RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY is enabled OR
415 * 2) RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD is enabled
417 if (h->writer_takes_lock) {
418 h->readwrite_lock = rte_malloc(NULL, sizeof(rte_rwlock_t),
419 RTE_CACHE_LINE_SIZE);
420 if (h->readwrite_lock == NULL)
423 rte_rwlock_init(h->readwrite_lock);
426 /* Populate free slots ring. Entry zero is reserved for key misses. */
427 for (i = 1; i < num_key_slots; i++)
428 rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
430 te->data = (void *) h;
431 TAILQ_INSERT_TAIL(hash_list, te, next);
432 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
436 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
439 rte_ring_free(r_ext);
443 rte_free(buckets_ext);
445 rte_free(tbl_chng_cnt);
450 rte_hash_free(struct rte_hash *h)
452 struct rte_tailq_entry *te;
453 struct rte_hash_list *hash_list;
458 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
460 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
462 /* find out tailq entry */
463 TAILQ_FOREACH(te, hash_list, next) {
464 if (te->data == (void *) h)
469 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
473 TAILQ_REMOVE(hash_list, te, next);
475 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
477 if (h->use_local_cache)
478 rte_free(h->local_free_slots);
479 if (h->writer_takes_lock)
480 rte_free(h->readwrite_lock);
481 rte_ring_free(h->free_slots);
482 rte_ring_free(h->free_ext_bkts);
483 rte_free(h->key_store);
484 rte_free(h->buckets);
485 rte_free(h->buckets_ext);
486 rte_free(h->tbl_chng_cnt);
492 rte_hash_hash(const struct rte_hash *h, const void *key)
494 /* calc hash result by key */
495 return h->hash_func(key, h->key_len, h->hash_func_init_val);
499 rte_hash_count(const struct rte_hash *h)
501 uint32_t tot_ring_cnt, cached_cnt = 0;
507 if (h->use_local_cache) {
508 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
509 (LCORE_CACHE_SIZE - 1);
510 for (i = 0; i < RTE_MAX_LCORE; i++)
511 cached_cnt += h->local_free_slots[i].len;
513 ret = tot_ring_cnt - rte_ring_count(h->free_slots) -
516 tot_ring_cnt = h->entries;
517 ret = tot_ring_cnt - rte_ring_count(h->free_slots);
522 /* Read write locks implemented using rte_rwlock */
524 __hash_rw_writer_lock(const struct rte_hash *h)
526 if (h->writer_takes_lock && h->hw_trans_mem_support)
527 rte_rwlock_write_lock_tm(h->readwrite_lock);
528 else if (h->writer_takes_lock)
529 rte_rwlock_write_lock(h->readwrite_lock);
533 __hash_rw_reader_lock(const struct rte_hash *h)
535 if (h->readwrite_concur_support && h->hw_trans_mem_support)
536 rte_rwlock_read_lock_tm(h->readwrite_lock);
537 else if (h->readwrite_concur_support)
538 rte_rwlock_read_lock(h->readwrite_lock);
542 __hash_rw_writer_unlock(const struct rte_hash *h)
544 if (h->writer_takes_lock && h->hw_trans_mem_support)
545 rte_rwlock_write_unlock_tm(h->readwrite_lock);
546 else if (h->writer_takes_lock)
547 rte_rwlock_write_unlock(h->readwrite_lock);
551 __hash_rw_reader_unlock(const struct rte_hash *h)
553 if (h->readwrite_concur_support && h->hw_trans_mem_support)
554 rte_rwlock_read_unlock_tm(h->readwrite_lock);
555 else if (h->readwrite_concur_support)
556 rte_rwlock_read_unlock(h->readwrite_lock);
560 rte_hash_reset(struct rte_hash *h)
563 uint32_t tot_ring_cnt, i;
568 __hash_rw_writer_lock(h);
569 memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket));
570 memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
571 *h->tbl_chng_cnt = 0;
573 /* clear the free ring */
574 while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
577 /* clear free extendable bucket ring and memory */
578 if (h->ext_table_support) {
579 memset(h->buckets_ext, 0, h->num_buckets *
580 sizeof(struct rte_hash_bucket));
581 while (rte_ring_dequeue(h->free_ext_bkts, &ptr) == 0)
585 /* Repopulate the free slots ring. Entry zero is reserved for key misses */
586 if (h->use_local_cache)
587 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
588 (LCORE_CACHE_SIZE - 1);
590 tot_ring_cnt = h->entries;
592 for (i = 1; i < tot_ring_cnt + 1; i++)
593 rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));
595 /* Repopulate the free ext bkt ring. */
596 if (h->ext_table_support) {
597 for (i = 1; i <= h->num_buckets; i++)
598 rte_ring_sp_enqueue(h->free_ext_bkts,
599 (void *)((uintptr_t) i));
602 if (h->use_local_cache) {
603 /* Reset local caches per lcore */
604 for (i = 0; i < RTE_MAX_LCORE; i++)
605 h->local_free_slots[i].len = 0;
607 __hash_rw_writer_unlock(h);
611 * Function called to enqueue back an index in the cache/ring,
612 * as slot has not being used and it can be used in the
613 * next addition attempt.
616 enqueue_slot_back(const struct rte_hash *h,
617 struct lcore_cache *cached_free_slots,
620 if (h->use_local_cache) {
621 cached_free_slots->objs[cached_free_slots->len] = slot_id;
622 cached_free_slots->len++;
624 rte_ring_sp_enqueue(h->free_slots, slot_id);
627 /* Search a key from bucket and update its data.
628 * Writer holds the lock before calling this.
630 static inline int32_t
631 search_and_update(const struct rte_hash *h, void *data, const void *key,
632 struct rte_hash_bucket *bkt, uint16_t sig)
635 struct rte_hash_key *k, *keys = h->key_store;
637 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
638 if (bkt->sig_current[i] == sig) {
639 k = (struct rte_hash_key *) ((char *)keys +
640 bkt->key_idx[i] * h->key_entry_size);
641 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
642 /* 'pdata' acts as the synchronization point
643 * when an existing hash entry is updated.
644 * Key is not updated in this case.
646 __atomic_store_n(&k->pdata,
650 * Return index where key is stored,
651 * subtracting the first dummy index
653 return bkt->key_idx[i] - 1;
660 /* Only tries to insert at one bucket (@prim_bkt) without trying to push
662 * return 1 if matching existing key, return 0 if succeeds, return -1 for no
665 static inline int32_t
666 rte_hash_cuckoo_insert_mw(const struct rte_hash *h,
667 struct rte_hash_bucket *prim_bkt,
668 struct rte_hash_bucket *sec_bkt,
669 const struct rte_hash_key *key, void *data,
670 uint16_t sig, uint32_t new_idx,
674 struct rte_hash_bucket *cur_bkt;
677 __hash_rw_writer_lock(h);
678 /* Check if key was inserted after last check but before this
679 * protected region in case of inserting duplicated keys.
681 ret = search_and_update(h, data, key, prim_bkt, sig);
683 __hash_rw_writer_unlock(h);
688 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
689 ret = search_and_update(h, data, key, cur_bkt, sig);
691 __hash_rw_writer_unlock(h);
697 /* Insert new entry if there is room in the primary
700 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
701 /* Check if slot is available */
702 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
703 prim_bkt->sig_current[i] = sig;
704 /* Key can be of arbitrary length, so it is
705 * not possible to store it atomically.
706 * Hence the new key element's memory stores
707 * (key as well as data) should be complete
708 * before it is referenced.
710 __atomic_store_n(&prim_bkt->key_idx[i],
716 __hash_rw_writer_unlock(h);
718 if (i != RTE_HASH_BUCKET_ENTRIES)
725 /* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill
726 * the path head with new entry (sig, alt_hash, new_idx)
727 * return 1 if matched key found, return -1 if cuckoo path invalided and fail,
728 * return 0 if succeeds.
731 rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,
732 struct rte_hash_bucket *bkt,
733 struct rte_hash_bucket *alt_bkt,
734 const struct rte_hash_key *key, void *data,
735 struct queue_node *leaf, uint32_t leaf_slot,
736 uint16_t sig, uint32_t new_idx,
739 uint32_t prev_alt_bkt_idx;
740 struct rte_hash_bucket *cur_bkt;
741 struct queue_node *prev_node, *curr_node = leaf;
742 struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
743 uint32_t prev_slot, curr_slot = leaf_slot;
746 __hash_rw_writer_lock(h);
748 /* In case empty slot was gone before entering protected region */
749 if (curr_bkt->key_idx[curr_slot] != EMPTY_SLOT) {
750 __hash_rw_writer_unlock(h);
754 /* Check if key was inserted after last check but before this
757 ret = search_and_update(h, data, key, bkt, sig);
759 __hash_rw_writer_unlock(h);
764 FOR_EACH_BUCKET(cur_bkt, alt_bkt) {
765 ret = search_and_update(h, data, key, cur_bkt, sig);
767 __hash_rw_writer_unlock(h);
773 while (likely(curr_node->prev != NULL)) {
774 prev_node = curr_node->prev;
775 prev_bkt = prev_node->bkt;
776 prev_slot = curr_node->prev_slot;
778 prev_alt_bkt_idx = get_alt_bucket_index(h,
779 prev_node->cur_bkt_idx,
780 prev_bkt->sig_current[prev_slot]);
782 if (unlikely(&h->buckets[prev_alt_bkt_idx]
784 /* revert it to empty, otherwise duplicated keys */
785 __atomic_store_n(&curr_bkt->key_idx[curr_slot],
788 __hash_rw_writer_unlock(h);
792 if (h->readwrite_concur_lf_support) {
793 /* Inform the previous move. The current move need
794 * not be informed now as the current bucket entry
795 * is present in both primary and secondary.
796 * Since there is one writer, load acquires on
797 * tbl_chng_cnt are not required.
799 __atomic_store_n(h->tbl_chng_cnt,
800 *h->tbl_chng_cnt + 1,
802 /* The stores to sig_alt and sig_current should not
803 * move above the store to tbl_chng_cnt.
805 __atomic_thread_fence(__ATOMIC_RELEASE);
808 /* Need to swap current/alt sig to allow later
809 * Cuckoo insert to move elements back to its
810 * primary bucket if available
812 curr_bkt->sig_current[curr_slot] =
813 prev_bkt->sig_current[prev_slot];
814 /* Release the updated bucket entry */
815 __atomic_store_n(&curr_bkt->key_idx[curr_slot],
816 prev_bkt->key_idx[prev_slot],
819 curr_slot = prev_slot;
820 curr_node = prev_node;
821 curr_bkt = curr_node->bkt;
824 if (h->readwrite_concur_lf_support) {
825 /* Inform the previous move. The current move need
826 * not be informed now as the current bucket entry
827 * is present in both primary and secondary.
828 * Since there is one writer, load acquires on
829 * tbl_chng_cnt are not required.
831 __atomic_store_n(h->tbl_chng_cnt,
832 *h->tbl_chng_cnt + 1,
834 /* The stores to sig_alt and sig_current should not
835 * move above the store to tbl_chng_cnt.
837 __atomic_thread_fence(__ATOMIC_RELEASE);
840 curr_bkt->sig_current[curr_slot] = sig;
841 /* Release the new bucket entry */
842 __atomic_store_n(&curr_bkt->key_idx[curr_slot],
846 __hash_rw_writer_unlock(h);
853 * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
857 rte_hash_cuckoo_make_space_mw(const struct rte_hash *h,
858 struct rte_hash_bucket *bkt,
859 struct rte_hash_bucket *sec_bkt,
860 const struct rte_hash_key *key, void *data,
861 uint16_t sig, uint32_t bucket_idx,
862 uint32_t new_idx, int32_t *ret_val)
865 struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
866 struct queue_node *tail, *head;
867 struct rte_hash_bucket *curr_bkt, *alt_bkt;
868 uint32_t cur_idx, alt_idx;
874 tail->prev_slot = -1;
875 tail->cur_bkt_idx = bucket_idx;
877 /* Cuckoo bfs Search */
878 while (likely(tail != head && head <
879 queue + RTE_HASH_BFS_QUEUE_MAX_LEN -
880 RTE_HASH_BUCKET_ENTRIES)) {
881 curr_bkt = tail->bkt;
882 cur_idx = tail->cur_bkt_idx;
883 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
884 if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
885 int32_t ret = rte_hash_cuckoo_move_insert_mw(h,
886 bkt, sec_bkt, key, data,
889 if (likely(ret != -1))
893 /* Enqueue new node and keep prev node info */
894 alt_idx = get_alt_bucket_index(h, cur_idx,
895 curr_bkt->sig_current[i]);
896 alt_bkt = &(h->buckets[alt_idx]);
898 head->cur_bkt_idx = alt_idx;
909 static inline int32_t
910 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
911 hash_sig_t sig, void *data)
914 uint32_t prim_bucket_idx, sec_bucket_idx;
915 struct rte_hash_bucket *prim_bkt, *sec_bkt, *cur_bkt;
916 struct rte_hash_key *new_k, *keys = h->key_store;
917 void *slot_id = NULL;
918 void *ext_bkt_id = NULL;
919 uint32_t new_idx, bkt_id;
924 struct lcore_cache *cached_free_slots = NULL;
926 struct rte_hash_bucket *last;
928 short_sig = get_short_sig(sig);
929 prim_bucket_idx = get_prim_bucket_index(h, sig);
930 sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
931 prim_bkt = &h->buckets[prim_bucket_idx];
932 sec_bkt = &h->buckets[sec_bucket_idx];
933 rte_prefetch0(prim_bkt);
934 rte_prefetch0(sec_bkt);
936 /* Check if key is already inserted in primary location */
937 __hash_rw_writer_lock(h);
938 ret = search_and_update(h, data, key, prim_bkt, short_sig);
940 __hash_rw_writer_unlock(h);
944 /* Check if key is already inserted in secondary location */
945 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
946 ret = search_and_update(h, data, key, cur_bkt, short_sig);
948 __hash_rw_writer_unlock(h);
953 __hash_rw_writer_unlock(h);
955 /* Did not find a match, so get a new slot for storing the new key */
956 if (h->use_local_cache) {
957 lcore_id = rte_lcore_id();
958 cached_free_slots = &h->local_free_slots[lcore_id];
959 /* Try to get a free slot from the local cache */
960 if (cached_free_slots->len == 0) {
961 /* Need to get another burst of free slots from global ring */
962 n_slots = rte_ring_mc_dequeue_burst(h->free_slots,
963 cached_free_slots->objs,
964 LCORE_CACHE_SIZE, NULL);
969 cached_free_slots->len += n_slots;
972 /* Get a free slot from the local cache */
973 cached_free_slots->len--;
974 slot_id = cached_free_slots->objs[cached_free_slots->len];
976 if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) {
981 new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
982 new_idx = (uint32_t)((uintptr_t) slot_id);
984 memcpy(new_k->key, key, h->key_len);
985 /* Key can be of arbitrary length, so it is not possible to store
986 * it atomically. Hence the new key element's memory stores
987 * (key as well as data) should be complete before it is referenced.
988 * 'pdata' acts as the synchronization point when an existing hash
991 __atomic_store_n(&new_k->pdata,
995 /* Find an empty slot and insert */
996 ret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data,
997 short_sig, new_idx, &ret_val);
1000 else if (ret == 1) {
1001 enqueue_slot_back(h, cached_free_slots, slot_id);
1005 /* Primary bucket full, need to make space for new entry */
1006 ret = rte_hash_cuckoo_make_space_mw(h, prim_bkt, sec_bkt, key, data,
1007 short_sig, prim_bucket_idx, new_idx, &ret_val);
1010 else if (ret == 1) {
1011 enqueue_slot_back(h, cached_free_slots, slot_id);
1015 /* Also search secondary bucket to get better occupancy */
1016 ret = rte_hash_cuckoo_make_space_mw(h, sec_bkt, prim_bkt, key, data,
1017 short_sig, sec_bucket_idx, new_idx, &ret_val);
1021 else if (ret == 1) {
1022 enqueue_slot_back(h, cached_free_slots, slot_id);
1026 /* if ext table not enabled, we failed the insertion */
1027 if (!h->ext_table_support) {
1028 enqueue_slot_back(h, cached_free_slots, slot_id);
1032 /* Now we need to go through the extendable bucket. Protection is needed
1033 * to protect all extendable bucket processes.
1035 __hash_rw_writer_lock(h);
1036 /* We check for duplicates again since could be inserted before the lock */
1037 ret = search_and_update(h, data, key, prim_bkt, short_sig);
1039 enqueue_slot_back(h, cached_free_slots, slot_id);
1043 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1044 ret = search_and_update(h, data, key, cur_bkt, short_sig);
1046 enqueue_slot_back(h, cached_free_slots, slot_id);
1051 /* Search sec and ext buckets to find an empty entry to insert. */
1052 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1053 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1054 /* Check if slot is available */
1055 if (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {
1056 cur_bkt->sig_current[i] = short_sig;
1057 cur_bkt->key_idx[i] = new_idx;
1058 __hash_rw_writer_unlock(h);
1064 /* Failed to get an empty entry from extendable buckets. Link a new
1065 * extendable bucket. We first get a free bucket from ring.
1067 if (rte_ring_sc_dequeue(h->free_ext_bkts, &ext_bkt_id) != 0) {
1072 bkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1;
1073 /* Use the first location of the new bucket */
1074 (h->buckets_ext[bkt_id]).sig_current[0] = short_sig;
1075 (h->buckets_ext[bkt_id]).key_idx[0] = new_idx;
1076 /* Link the new bucket to sec bucket linked list */
1077 last = rte_hash_get_last_bkt(sec_bkt);
1078 last->next = &h->buckets_ext[bkt_id];
1079 __hash_rw_writer_unlock(h);
1083 __hash_rw_writer_unlock(h);
1089 rte_hash_add_key_with_hash(const struct rte_hash *h,
1090 const void *key, hash_sig_t sig)
1092 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1093 return __rte_hash_add_key_with_hash(h, key, sig, 0);
1097 rte_hash_add_key(const struct rte_hash *h, const void *key)
1099 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1100 return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
1104 rte_hash_add_key_with_hash_data(const struct rte_hash *h,
1105 const void *key, hash_sig_t sig, void *data)
1109 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1110 ret = __rte_hash_add_key_with_hash(h, key, sig, data);
1118 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)
1122 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1124 ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data);
1131 /* Search one bucket to find the match key - uses rw lock */
1132 static inline int32_t
1133 search_one_bucket_l(const struct rte_hash *h, const void *key,
1134 uint16_t sig, void **data,
1135 const struct rte_hash_bucket *bkt)
1138 struct rte_hash_key *k, *keys = h->key_store;
1140 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1141 if (bkt->sig_current[i] == sig &&
1142 bkt->key_idx[i] != EMPTY_SLOT) {
1143 k = (struct rte_hash_key *) ((char *)keys +
1144 bkt->key_idx[i] * h->key_entry_size);
1146 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1150 * Return index where key is stored,
1151 * subtracting the first dummy index
1153 return bkt->key_idx[i] - 1;
1160 /* Search one bucket to find the match key */
1161 static inline int32_t
1162 search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig,
1163 void **data, const struct rte_hash_bucket *bkt)
1168 struct rte_hash_key *k, *keys = h->key_store;
1170 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1171 key_idx = __atomic_load_n(&bkt->key_idx[i],
1173 if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {
1174 k = (struct rte_hash_key *) ((char *)keys +
1175 key_idx * h->key_entry_size);
1176 pdata = __atomic_load_n(&k->pdata,
1179 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1183 * Return index where key is stored,
1184 * subtracting the first dummy index
1193 static inline int32_t
1194 __rte_hash_lookup_with_hash_l(const struct rte_hash *h, const void *key,
1195 hash_sig_t sig, void **data)
1197 uint32_t prim_bucket_idx, sec_bucket_idx;
1198 struct rte_hash_bucket *bkt, *cur_bkt;
1202 short_sig = get_short_sig(sig);
1203 prim_bucket_idx = get_prim_bucket_index(h, sig);
1204 sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1206 bkt = &h->buckets[prim_bucket_idx];
1208 __hash_rw_reader_lock(h);
1210 /* Check if key is in primary location */
1211 ret = search_one_bucket_l(h, key, short_sig, data, bkt);
1213 __hash_rw_reader_unlock(h);
1216 /* Calculate secondary hash */
1217 bkt = &h->buckets[sec_bucket_idx];
1219 /* Check if key is in secondary location */
1220 FOR_EACH_BUCKET(cur_bkt, bkt) {
1221 ret = search_one_bucket_l(h, key, short_sig,
1224 __hash_rw_reader_unlock(h);
1229 __hash_rw_reader_unlock(h);
1234 static inline int32_t
1235 __rte_hash_lookup_with_hash_lf(const struct rte_hash *h, const void *key,
1236 hash_sig_t sig, void **data)
1238 uint32_t prim_bucket_idx, sec_bucket_idx;
1239 struct rte_hash_bucket *bkt, *cur_bkt;
1240 uint32_t cnt_b, cnt_a;
1244 short_sig = get_short_sig(sig);
1245 prim_bucket_idx = get_prim_bucket_index(h, sig);
1246 sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1249 /* Load the table change counter before the lookup
1250 * starts. Acquire semantics will make sure that
1251 * loads in search_one_bucket are not hoisted.
1253 cnt_b = __atomic_load_n(h->tbl_chng_cnt,
1256 /* Check if key is in primary location */
1257 bkt = &h->buckets[prim_bucket_idx];
1258 ret = search_one_bucket_lf(h, key, short_sig, data, bkt);
1260 __hash_rw_reader_unlock(h);
1263 /* Calculate secondary hash */
1264 bkt = &h->buckets[sec_bucket_idx];
1266 /* Check if key is in secondary location */
1267 FOR_EACH_BUCKET(cur_bkt, bkt) {
1268 ret = search_one_bucket_lf(h, key, short_sig,
1271 __hash_rw_reader_unlock(h);
1276 /* The loads of sig_current in search_one_bucket
1277 * should not move below the load from tbl_chng_cnt.
1279 __atomic_thread_fence(__ATOMIC_ACQUIRE);
1280 /* Re-read the table change counter to check if the
1281 * table has changed during search. If yes, re-do
1283 * This load should not get hoisted. The load
1284 * acquires on cnt_b, key index in primary bucket
1285 * and key index in secondary bucket will make sure
1286 * that it does not get hoisted.
1288 cnt_a = __atomic_load_n(h->tbl_chng_cnt,
1290 } while (cnt_b != cnt_a);
1295 static inline int32_t
1296 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
1297 hash_sig_t sig, void **data)
1299 if (h->readwrite_concur_lf_support)
1300 return __rte_hash_lookup_with_hash_lf(h, key, sig, data);
1302 return __rte_hash_lookup_with_hash_l(h, key, sig, data);
1306 rte_hash_lookup_with_hash(const struct rte_hash *h,
1307 const void *key, hash_sig_t sig)
1309 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1310 return __rte_hash_lookup_with_hash(h, key, sig, NULL);
1314 rte_hash_lookup(const struct rte_hash *h, const void *key)
1316 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1317 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
1321 rte_hash_lookup_with_hash_data(const struct rte_hash *h,
1322 const void *key, hash_sig_t sig, void **data)
1324 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1325 return __rte_hash_lookup_with_hash(h, key, sig, data);
1329 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)
1331 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1332 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
1336 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
1338 unsigned lcore_id, n_slots;
1339 struct lcore_cache *cached_free_slots;
1341 if (h->use_local_cache) {
1342 lcore_id = rte_lcore_id();
1343 cached_free_slots = &h->local_free_slots[lcore_id];
1344 /* Cache full, need to free it. */
1345 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
1346 /* Need to enqueue the free slots in global ring. */
1347 n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
1348 cached_free_slots->objs,
1349 LCORE_CACHE_SIZE, NULL);
1350 ERR_IF_TRUE((n_slots == 0),
1351 "%s: could not enqueue free slots in global ring\n",
1353 cached_free_slots->len -= n_slots;
1355 /* Put index of new free slot in cache. */
1356 cached_free_slots->objs[cached_free_slots->len] =
1357 (void *)((uintptr_t)bkt->key_idx[i]);
1358 cached_free_slots->len++;
1360 rte_ring_sp_enqueue(h->free_slots,
1361 (void *)((uintptr_t)bkt->key_idx[i]));
1365 /* Compact the linked list by moving key from last entry in linked list to the
1369 __rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) {
1371 struct rte_hash_bucket *last_bkt;
1376 last_bkt = rte_hash_get_last_bkt(cur_bkt);
1378 for (i = RTE_HASH_BUCKET_ENTRIES - 1; i >= 0; i--) {
1379 if (last_bkt->key_idx[i] != EMPTY_SLOT) {
1380 cur_bkt->key_idx[pos] = last_bkt->key_idx[i];
1381 cur_bkt->sig_current[pos] = last_bkt->sig_current[i];
1382 last_bkt->sig_current[i] = NULL_SIGNATURE;
1383 last_bkt->key_idx[i] = EMPTY_SLOT;
1389 /* Search one bucket and remove the matched key.
1390 * Writer is expected to hold the lock while calling this
1393 static inline int32_t
1394 search_and_remove(const struct rte_hash *h, const void *key,
1395 struct rte_hash_bucket *bkt, uint16_t sig, int *pos)
1397 struct rte_hash_key *k, *keys = h->key_store;
1401 /* Check if key is in bucket */
1402 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1403 key_idx = __atomic_load_n(&bkt->key_idx[i],
1405 if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {
1406 k = (struct rte_hash_key *) ((char *)keys +
1407 key_idx * h->key_entry_size);
1408 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1409 bkt->sig_current[i] = NULL_SIGNATURE;
1410 /* Free the key store index if
1411 * no_free_on_del is disabled.
1413 if (!h->no_free_on_del)
1414 remove_entry(h, bkt, i);
1416 __atomic_store_n(&bkt->key_idx[i],
1422 * Return index where key is stored,
1423 * subtracting the first dummy index
1432 static inline int32_t
1433 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
1436 uint32_t prim_bucket_idx, sec_bucket_idx;
1437 struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt;
1438 struct rte_hash_bucket *cur_bkt;
1443 short_sig = get_short_sig(sig);
1444 prim_bucket_idx = get_prim_bucket_index(h, sig);
1445 sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1446 prim_bkt = &h->buckets[prim_bucket_idx];
1448 __hash_rw_writer_lock(h);
1449 /* look for key in primary bucket */
1450 ret = search_and_remove(h, key, prim_bkt, short_sig, &pos);
1452 __rte_hash_compact_ll(prim_bkt, pos);
1453 last_bkt = prim_bkt->next;
1454 prev_bkt = prim_bkt;
1458 /* Calculate secondary hash */
1459 sec_bkt = &h->buckets[sec_bucket_idx];
1461 FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1462 ret = search_and_remove(h, key, cur_bkt, short_sig, &pos);
1464 __rte_hash_compact_ll(cur_bkt, pos);
1465 last_bkt = sec_bkt->next;
1471 __hash_rw_writer_unlock(h);
1474 /* Search last bucket to see if empty to be recycled */
1477 __hash_rw_writer_unlock(h);
1480 while (last_bkt->next) {
1481 prev_bkt = last_bkt;
1482 last_bkt = last_bkt->next;
1485 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1486 if (last_bkt->key_idx[i] != EMPTY_SLOT)
1489 /* found empty bucket and recycle */
1490 if (i == RTE_HASH_BUCKET_ENTRIES) {
1491 prev_bkt->next = last_bkt->next = NULL;
1492 uint32_t index = last_bkt - h->buckets_ext + 1;
1493 rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);
1496 __hash_rw_writer_unlock(h);
1501 rte_hash_del_key_with_hash(const struct rte_hash *h,
1502 const void *key, hash_sig_t sig)
1504 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1505 return __rte_hash_del_key_with_hash(h, key, sig);
1509 rte_hash_del_key(const struct rte_hash *h, const void *key)
1511 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1512 return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
1516 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
1519 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1521 struct rte_hash_key *k, *keys = h->key_store;
1522 k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
1527 __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
1535 int __rte_experimental
1536 rte_hash_free_key_with_position(const struct rte_hash *h,
1537 const int32_t position)
1539 /* Key index where key is stored, adding the first dummy index */
1540 uint32_t key_idx = position + 1;
1542 RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
1544 unsigned int lcore_id, n_slots;
1545 struct lcore_cache *cached_free_slots;
1546 const uint32_t total_entries = h->use_local_cache ?
1547 h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1
1551 if (key_idx >= total_entries)
1554 if (h->use_local_cache) {
1555 lcore_id = rte_lcore_id();
1556 cached_free_slots = &h->local_free_slots[lcore_id];
1557 /* Cache full, need to free it. */
1558 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
1559 /* Need to enqueue the free slots in global ring. */
1560 n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
1561 cached_free_slots->objs,
1562 LCORE_CACHE_SIZE, NULL);
1563 RETURN_IF_TRUE((n_slots == 0), -EFAULT);
1564 cached_free_slots->len -= n_slots;
1566 /* Put index of new free slot in cache. */
1567 cached_free_slots->objs[cached_free_slots->len] =
1568 (void *)((uintptr_t)key_idx);
1569 cached_free_slots->len++;
1571 rte_ring_sp_enqueue(h->free_slots,
1572 (void *)((uintptr_t)key_idx));
1579 compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
1580 const struct rte_hash_bucket *prim_bkt,
1581 const struct rte_hash_bucket *sec_bkt,
1583 enum rte_hash_sig_compare_function sig_cmp_fn)
1587 /* For match mask the first bit of every two bits indicates the match */
1588 switch (sig_cmp_fn) {
1589 #ifdef RTE_MACHINE_CPUFLAG_SSE2
1590 case RTE_HASH_COMPARE_SSE:
1591 /* Compare all signatures in the bucket */
1592 *prim_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1594 (__m128i const *)prim_bkt->sig_current),
1595 _mm_set1_epi16(sig)));
1596 /* Compare all signatures in the bucket */
1597 *sec_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1599 (__m128i const *)sec_bkt->sig_current),
1600 _mm_set1_epi16(sig)));
1604 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1605 *prim_hash_matches |=
1606 ((sig == prim_bkt->sig_current[i]) << (i << 1));
1607 *sec_hash_matches |=
1608 ((sig == sec_bkt->sig_current[i]) << (i << 1));
1613 #define PREFETCH_OFFSET 4
1615 __rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys,
1616 int32_t num_keys, int32_t *positions,
1617 uint64_t *hit_mask, void *data[])
1622 uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
1623 uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
1624 uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
1625 uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
1626 const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1627 const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1628 uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1629 uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1630 struct rte_hash_bucket *cur_bkt, *next_bkt;
1632 /* Prefetch first keys */
1633 for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
1634 rte_prefetch0(keys[i]);
1637 * Prefetch rest of the keys, calculate primary and
1638 * secondary bucket and prefetch them
1640 for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
1641 rte_prefetch0(keys[i + PREFETCH_OFFSET]);
1643 prim_hash[i] = rte_hash_hash(h, keys[i]);
1645 sig[i] = get_short_sig(prim_hash[i]);
1646 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1647 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1649 primary_bkt[i] = &h->buckets[prim_index[i]];
1650 secondary_bkt[i] = &h->buckets[sec_index[i]];
1652 rte_prefetch0(primary_bkt[i]);
1653 rte_prefetch0(secondary_bkt[i]);
1656 /* Calculate and prefetch rest of the buckets */
1657 for (; i < num_keys; i++) {
1658 prim_hash[i] = rte_hash_hash(h, keys[i]);
1660 sig[i] = get_short_sig(prim_hash[i]);
1661 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1662 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1664 primary_bkt[i] = &h->buckets[prim_index[i]];
1665 secondary_bkt[i] = &h->buckets[sec_index[i]];
1667 rte_prefetch0(primary_bkt[i]);
1668 rte_prefetch0(secondary_bkt[i]);
1671 __hash_rw_reader_lock(h);
1673 /* Compare signatures and prefetch key slot of first hit */
1674 for (i = 0; i < num_keys; i++) {
1675 compare_signatures(&prim_hitmask[i], &sec_hitmask[i],
1676 primary_bkt[i], secondary_bkt[i],
1677 sig[i], h->sig_cmp_fn);
1679 if (prim_hitmask[i]) {
1680 uint32_t first_hit =
1681 __builtin_ctzl(prim_hitmask[i])
1684 primary_bkt[i]->key_idx[first_hit];
1685 const struct rte_hash_key *key_slot =
1686 (const struct rte_hash_key *)(
1687 (const char *)h->key_store +
1688 key_idx * h->key_entry_size);
1689 rte_prefetch0(key_slot);
1693 if (sec_hitmask[i]) {
1694 uint32_t first_hit =
1695 __builtin_ctzl(sec_hitmask[i])
1698 secondary_bkt[i]->key_idx[first_hit];
1699 const struct rte_hash_key *key_slot =
1700 (const struct rte_hash_key *)(
1701 (const char *)h->key_store +
1702 key_idx * h->key_entry_size);
1703 rte_prefetch0(key_slot);
1707 /* Compare keys, first hits in primary first */
1708 for (i = 0; i < num_keys; i++) {
1709 positions[i] = -ENOENT;
1710 while (prim_hitmask[i]) {
1711 uint32_t hit_index =
1712 __builtin_ctzl(prim_hitmask[i])
1715 primary_bkt[i]->key_idx[hit_index];
1716 const struct rte_hash_key *key_slot =
1717 (const struct rte_hash_key *)(
1718 (const char *)h->key_store +
1719 key_idx * h->key_entry_size);
1722 * If key index is 0, do not compare key,
1723 * as it is checking the dummy slot
1727 key_slot->key, keys[i], h)) {
1729 data[i] = key_slot->pdata;
1732 positions[i] = key_idx - 1;
1735 prim_hitmask[i] &= ~(3ULL << (hit_index << 1));
1738 while (sec_hitmask[i]) {
1739 uint32_t hit_index =
1740 __builtin_ctzl(sec_hitmask[i])
1743 secondary_bkt[i]->key_idx[hit_index];
1744 const struct rte_hash_key *key_slot =
1745 (const struct rte_hash_key *)(
1746 (const char *)h->key_store +
1747 key_idx * h->key_entry_size);
1750 * If key index is 0, do not compare key,
1751 * as it is checking the dummy slot
1756 key_slot->key, keys[i], h)) {
1758 data[i] = key_slot->pdata;
1761 positions[i] = key_idx - 1;
1764 sec_hitmask[i] &= ~(3ULL << (hit_index << 1));
1770 /* all found, do not need to go through ext bkt */
1771 if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {
1772 if (hit_mask != NULL)
1774 __hash_rw_reader_unlock(h);
1778 /* need to check ext buckets for match */
1779 for (i = 0; i < num_keys; i++) {
1780 if ((hits & (1ULL << i)) != 0)
1782 next_bkt = secondary_bkt[i]->next;
1783 FOR_EACH_BUCKET(cur_bkt, next_bkt) {
1785 ret = search_one_bucket_l(h, keys[i],
1786 sig[i], &data[i], cur_bkt);
1788 ret = search_one_bucket_l(h, keys[i],
1789 sig[i], NULL, cur_bkt);
1798 __hash_rw_reader_unlock(h);
1800 if (hit_mask != NULL)
1805 __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
1806 int32_t num_keys, int32_t *positions,
1807 uint64_t *hit_mask, void *data[])
1812 uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
1813 uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
1814 uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
1815 uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
1816 const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1817 const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1818 uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1819 uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1820 struct rte_hash_bucket *cur_bkt, *next_bkt;
1821 void *pdata[RTE_HASH_LOOKUP_BULK_MAX];
1822 uint32_t cnt_b, cnt_a;
1824 /* Prefetch first keys */
1825 for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
1826 rte_prefetch0(keys[i]);
1829 * Prefetch rest of the keys, calculate primary and
1830 * secondary bucket and prefetch them
1832 for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
1833 rte_prefetch0(keys[i + PREFETCH_OFFSET]);
1835 prim_hash[i] = rte_hash_hash(h, keys[i]);
1837 sig[i] = get_short_sig(prim_hash[i]);
1838 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1839 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1841 primary_bkt[i] = &h->buckets[prim_index[i]];
1842 secondary_bkt[i] = &h->buckets[sec_index[i]];
1844 rte_prefetch0(primary_bkt[i]);
1845 rte_prefetch0(secondary_bkt[i]);
1848 /* Calculate and prefetch rest of the buckets */
1849 for (; i < num_keys; i++) {
1850 prim_hash[i] = rte_hash_hash(h, keys[i]);
1852 sig[i] = get_short_sig(prim_hash[i]);
1853 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1854 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1856 primary_bkt[i] = &h->buckets[prim_index[i]];
1857 secondary_bkt[i] = &h->buckets[sec_index[i]];
1859 rte_prefetch0(primary_bkt[i]);
1860 rte_prefetch0(secondary_bkt[i]);
1864 /* Load the table change counter before the lookup
1865 * starts. Acquire semantics will make sure that
1866 * loads in compare_signatures are not hoisted.
1868 cnt_b = __atomic_load_n(h->tbl_chng_cnt,
1871 /* Compare signatures and prefetch key slot of first hit */
1872 for (i = 0; i < num_keys; i++) {
1873 compare_signatures(&prim_hitmask[i], &sec_hitmask[i],
1874 primary_bkt[i], secondary_bkt[i],
1875 sig[i], h->sig_cmp_fn);
1877 if (prim_hitmask[i]) {
1878 uint32_t first_hit =
1879 __builtin_ctzl(prim_hitmask[i])
1882 primary_bkt[i]->key_idx[first_hit];
1883 const struct rte_hash_key *key_slot =
1884 (const struct rte_hash_key *)(
1885 (const char *)h->key_store +
1886 key_idx * h->key_entry_size);
1887 rte_prefetch0(key_slot);
1891 if (sec_hitmask[i]) {
1892 uint32_t first_hit =
1893 __builtin_ctzl(sec_hitmask[i])
1896 secondary_bkt[i]->key_idx[first_hit];
1897 const struct rte_hash_key *key_slot =
1898 (const struct rte_hash_key *)(
1899 (const char *)h->key_store +
1900 key_idx * h->key_entry_size);
1901 rte_prefetch0(key_slot);
1905 /* Compare keys, first hits in primary first */
1906 for (i = 0; i < num_keys; i++) {
1907 positions[i] = -ENOENT;
1908 while (prim_hitmask[i]) {
1909 uint32_t hit_index =
1910 __builtin_ctzl(prim_hitmask[i])
1914 &primary_bkt[i]->key_idx[hit_index],
1916 const struct rte_hash_key *key_slot =
1917 (const struct rte_hash_key *)(
1918 (const char *)h->key_store +
1919 key_idx * h->key_entry_size);
1921 if (key_idx != EMPTY_SLOT)
1922 pdata[i] = __atomic_load_n(
1926 * If key index is 0, do not compare key,
1927 * as it is checking the dummy slot
1931 key_slot->key, keys[i], h)) {
1936 positions[i] = key_idx - 1;
1939 prim_hitmask[i] &= ~(3ULL << (hit_index << 1));
1942 while (sec_hitmask[i]) {
1943 uint32_t hit_index =
1944 __builtin_ctzl(sec_hitmask[i])
1948 &secondary_bkt[i]->key_idx[hit_index],
1950 const struct rte_hash_key *key_slot =
1951 (const struct rte_hash_key *)(
1952 (const char *)h->key_store +
1953 key_idx * h->key_entry_size);
1955 if (key_idx != EMPTY_SLOT)
1956 pdata[i] = __atomic_load_n(
1960 * If key index is 0, do not compare key,
1961 * as it is checking the dummy slot
1966 key_slot->key, keys[i], h)) {
1971 positions[i] = key_idx - 1;
1974 sec_hitmask[i] &= ~(3ULL << (hit_index << 1));
1980 /* The loads of sig_current in compare_signatures
1981 * should not move below the load from tbl_chng_cnt.
1983 __atomic_thread_fence(__ATOMIC_ACQUIRE);
1984 /* Re-read the table change counter to check if the
1985 * table has changed during search. If yes, re-do
1987 * This load should not get hoisted. The load
1988 * acquires on cnt_b, primary key index and secondary
1989 * key index will make sure that it does not get
1992 cnt_a = __atomic_load_n(h->tbl_chng_cnt,
1994 } while (cnt_b != cnt_a);
1996 /* all found, do not need to go through ext bkt */
1997 if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {
1998 if (hit_mask != NULL)
2000 __hash_rw_reader_unlock(h);
2004 /* need to check ext buckets for match */
2005 for (i = 0; i < num_keys; i++) {
2006 if ((hits & (1ULL << i)) != 0)
2008 next_bkt = secondary_bkt[i]->next;
2009 FOR_EACH_BUCKET(cur_bkt, next_bkt) {
2011 ret = search_one_bucket_lf(h, keys[i],
2012 sig[i], &data[i], cur_bkt);
2014 ret = search_one_bucket_lf(h, keys[i],
2015 sig[i], NULL, cur_bkt);
2024 if (hit_mask != NULL)
2029 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
2030 int32_t num_keys, int32_t *positions,
2031 uint64_t *hit_mask, void *data[])
2033 if (h->readwrite_concur_lf_support)
2034 __rte_hash_lookup_bulk_lf(h, keys, num_keys, positions,
2037 __rte_hash_lookup_bulk_l(h, keys, num_keys, positions,
2042 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
2043 uint32_t num_keys, int32_t *positions)
2045 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
2046 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
2047 (positions == NULL)), -EINVAL);
2049 __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL);
2054 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
2055 uint32_t num_keys, uint64_t *hit_mask, void *data[])
2057 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
2058 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
2059 (hit_mask == NULL)), -EINVAL);
2061 int32_t positions[num_keys];
2063 __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data);
2065 /* Return number of hits */
2066 return __builtin_popcountl(*hit_mask);
2070 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
2072 uint32_t bucket_idx, idx, position;
2073 struct rte_hash_key *next_key;
2075 RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
2077 const uint32_t total_entries_main = h->num_buckets *
2078 RTE_HASH_BUCKET_ENTRIES;
2079 const uint32_t total_entries = total_entries_main << 1;
2081 /* Out of bounds of all buckets (both main table and ext table) */
2082 if (*next >= total_entries_main)
2085 /* Calculate bucket and index of current iterator */
2086 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
2087 idx = *next % RTE_HASH_BUCKET_ENTRIES;
2089 /* If current position is empty, go to the next one */
2090 while ((position = __atomic_load_n(&h->buckets[bucket_idx].key_idx[idx],
2091 __ATOMIC_ACQUIRE)) == EMPTY_SLOT) {
2094 if (*next == total_entries_main)
2096 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
2097 idx = *next % RTE_HASH_BUCKET_ENTRIES;
2100 __hash_rw_reader_lock(h);
2101 next_key = (struct rte_hash_key *) ((char *)h->key_store +
2102 position * h->key_entry_size);
2103 /* Return key and data */
2104 *key = next_key->key;
2105 *data = next_key->pdata;
2107 __hash_rw_reader_unlock(h);
2109 /* Increment iterator */
2112 return position - 1;
2114 /* Begin to iterate extendable buckets */
2116 /* Out of total bound or if ext bucket feature is not enabled */
2117 if (*next >= total_entries || !h->ext_table_support)
2120 bucket_idx = (*next - total_entries_main) / RTE_HASH_BUCKET_ENTRIES;
2121 idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
2123 while ((position = h->buckets_ext[bucket_idx].key_idx[idx]) == EMPTY_SLOT) {
2125 if (*next == total_entries)
2127 bucket_idx = (*next - total_entries_main) /
2128 RTE_HASH_BUCKET_ENTRIES;
2129 idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
2131 __hash_rw_reader_lock(h);
2132 next_key = (struct rte_hash_key *) ((char *)h->key_store +
2133 position * h->key_entry_size);
2134 /* Return key and data */
2135 *key = next_key->key;
2136 *data = next_key->pdata;
2138 __hash_rw_reader_unlock(h);
2140 /* Increment iterator */
2142 return position - 1;