4 * Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 #include <sys/queue.h>
41 #include <rte_common.h>
42 #include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */
44 #include <rte_memcpy.h>
45 #include <rte_prefetch.h>
46 #include <rte_branch_prediction.h>
47 #include <rte_memzone.h>
48 #include <rte_malloc.h>
50 #include <rte_eal_memconfig.h>
51 #include <rte_per_lcore.h>
52 #include <rte_errno.h>
53 #include <rte_string_fns.h>
54 #include <rte_cpuflags.h>
56 #include <rte_rwlock.h>
57 #include <rte_spinlock.h>
59 #include <rte_compat.h>
63 TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
65 static struct rte_tailq_elem rte_hash_tailq = {
68 EAL_REGISTER_TAILQ(rte_hash_tailq)
70 /* Macro to enable/disable run-time checking of function parameters */
71 #if defined(RTE_LIBRTE_HASH_DEBUG)
72 #define RETURN_IF_TRUE(cond, retval) do { \
77 #define RETURN_IF_TRUE(cond, retval)
80 /* Hash function used if none is specified */
81 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
82 #include <rte_hash_crc.h>
83 #define DEFAULT_HASH_FUNC rte_hash_crc
85 #include <rte_jhash.h>
86 #define DEFAULT_HASH_FUNC rte_jhash
89 /** Number of items per bucket. */
90 #define RTE_HASH_BUCKET_ENTRIES 4
92 #define NULL_SIGNATURE 0
94 #define KEY_ALIGNMENT 16
96 typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len);
97 static int rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len);
98 static int rte_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len);
99 static int rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len);
100 static int rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len);
101 static int rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len);
102 static int rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len);
103 static int rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len);
104 static int rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len);
106 /** A hash table structure. */
108 char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */
109 uint32_t entries; /**< Total table entries. */
110 uint32_t num_buckets; /**< Number of buckets in table. */
111 uint32_t key_len; /**< Length of hash key. */
112 rte_hash_function hash_func; /**< Function used to calculate hash. */
113 rte_hash_cmp_eq_t rte_hash_cmp_eq; /**< Function used to compare keys. */
114 uint32_t hash_func_init_val; /**< Init value used by hash_func. */
115 uint32_t bucket_bitmask; /**< Bitmask for getting bucket index
116 from hash signature. */
117 uint32_t key_entry_size; /**< Size of each key entry. */
119 struct rte_ring *free_slots; /**< Ring that stores all indexes
120 of the free slots in the key table */
121 void *key_store; /**< Table storing all keys and data */
122 struct rte_hash_bucket *buckets; /**< Table with buckets storing all the
123 hash values and key indexes
125 } __rte_cache_aligned;
127 /* Structure storing both primary and secondary hashes */
128 struct rte_hash_signatures {
138 /* Structure that stores key-value pair */
139 struct rte_hash_key {
144 /* Variable key size */
146 } __attribute__((aligned(KEY_ALIGNMENT)));
148 /** Bucket structure */
149 struct rte_hash_bucket {
150 struct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES];
151 /* Includes dummy key index that always contains index 0 */
152 uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1];
153 uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
154 } __rte_cache_aligned;
157 rte_hash_find_existing(const char *name)
159 struct rte_hash *h = NULL;
160 struct rte_tailq_entry *te;
161 struct rte_hash_list *hash_list;
163 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
165 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
166 TAILQ_FOREACH(te, hash_list, next) {
167 h = (struct rte_hash *) te->data;
168 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
171 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
181 rte_hash_create(const struct rte_hash_parameters *params)
183 struct rte_hash *h = NULL;
184 struct rte_tailq_entry *te = NULL;
185 struct rte_hash_list *hash_list;
186 struct rte_ring *r = NULL;
187 char hash_name[RTE_HASH_NAMESIZE];
188 void *ptr, *k = NULL;
189 void *buckets = NULL;
190 char ring_name[RTE_RING_NAMESIZE];
193 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
195 if (params == NULL) {
196 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
200 /* Check for valid parameters */
201 if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
202 (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
203 !rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) ||
204 (params->key_len == 0)) {
206 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
210 snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
212 /* Guarantee there's no existing */
213 h = rte_hash_find_existing(params->name);
217 te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
219 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
223 h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
224 RTE_CACHE_LINE_SIZE, params->socket_id);
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 buckets = rte_zmalloc_socket(NULL,
235 num_buckets * sizeof(struct rte_hash_bucket),
236 RTE_CACHE_LINE_SIZE, params->socket_id);
238 if (buckets == NULL) {
239 RTE_LOG(ERR, HASH, "memory allocation failed\n");
243 const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;
245 /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
246 const uint64_t key_tbl_size = key_entry_size * (params->entries + 1);
248 k = rte_zmalloc_socket(NULL, key_tbl_size,
249 RTE_CACHE_LINE_SIZE, params->socket_id);
252 RTE_LOG(ERR, HASH, "memory allocation failed\n");
256 /* Select function to compare keys */
257 switch (params->key_len) {
259 h->rte_hash_cmp_eq = rte_hash_k16_cmp_eq;
262 h->rte_hash_cmp_eq = rte_hash_k32_cmp_eq;
265 h->rte_hash_cmp_eq = rte_hash_k48_cmp_eq;
268 h->rte_hash_cmp_eq = rte_hash_k64_cmp_eq;
271 h->rte_hash_cmp_eq = rte_hash_k80_cmp_eq;
274 h->rte_hash_cmp_eq = rte_hash_k96_cmp_eq;
277 h->rte_hash_cmp_eq = rte_hash_k112_cmp_eq;
280 h->rte_hash_cmp_eq = rte_hash_k128_cmp_eq;
283 /* If key is not multiple of 16, use generic memcmp */
284 h->rte_hash_cmp_eq = memcmp;
287 snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
288 r = rte_ring_lookup(ring_name);
290 /* clear the free ring */
291 while (rte_ring_dequeue(r, &ptr) == 0)
294 r = rte_ring_create(ring_name, rte_align32pow2(params->entries + 1),
295 params->socket_id, 0);
297 RTE_LOG(ERR, HASH, "memory allocation failed\n");
301 /* Setup hash context */
302 snprintf(h->name, sizeof(h->name), "%s", params->name);
303 h->entries = params->entries;
304 h->key_len = params->key_len;
305 h->key_entry_size = key_entry_size;
306 h->hash_func_init_val = params->hash_func_init_val;
308 h->num_buckets = num_buckets;
309 h->bucket_bitmask = h->num_buckets - 1;
310 h->buckets = buckets;
311 h->hash_func = (params->hash_func == NULL) ?
312 DEFAULT_HASH_FUNC : params->hash_func;
317 /* populate the free slots ring. Entry zero is reserved for key misses */
318 for (i = 1; i < params->entries + 1; i++)
319 rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
321 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
322 te->data = (void *) h;
323 TAILQ_INSERT_TAIL(hash_list, te, next);
324 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
336 rte_hash_free(struct rte_hash *h)
338 struct rte_tailq_entry *te;
339 struct rte_hash_list *hash_list;
344 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
346 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
348 /* find out tailq entry */
349 TAILQ_FOREACH(te, hash_list, next) {
350 if (te->data == (void *) h)
355 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
359 TAILQ_REMOVE(hash_list, te, next);
361 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
363 rte_free(h->key_store);
364 rte_free(h->buckets);
370 rte_hash_hash(const struct rte_hash *h, const void *key)
372 /* calc hash result by key */
373 return h->hash_func(key, h->key_len, h->hash_func_init_val);
376 /* Calc the secondary hash value from the primary hash value of a given key */
377 static inline hash_sig_t
378 rte_hash_secondary_hash(const hash_sig_t primary_hash)
380 static const unsigned all_bits_shift = 12;
381 static const unsigned alt_bits_xor = 0x5bd1e995;
383 uint32_t tag = primary_hash >> all_bits_shift;
385 return (primary_hash ^ ((tag + 1) * alt_bits_xor));
389 rte_hash_reset(struct rte_hash *h)
397 memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket));
398 memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
400 /* clear the free ring */
401 while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
404 /* Repopulate the free slots ring. Entry zero is reserved for key misses */
405 for (i = 1; i < h->entries + 1; i++)
406 rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));
409 /* Search for an entry that can be pushed to its alternative location */
411 make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
415 uint32_t next_bucket_idx;
416 struct rte_hash_bucket *next_bkt[RTE_HASH_BUCKET_ENTRIES];
419 * Push existing item (search for bucket with space in
420 * alternative locations) to its alternative location
422 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
423 /* Search for space in alternative locations */
424 next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask;
425 next_bkt[i] = &h->buckets[next_bucket_idx];
426 for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
427 if (next_bkt[i]->signatures[j].sig == NULL_SIGNATURE)
431 if (j != RTE_HASH_BUCKET_ENTRIES)
435 /* Alternative location has spare room (end of recursive function) */
436 if (i != RTE_HASH_BUCKET_ENTRIES) {
437 next_bkt[i]->signatures[j].alt = bkt->signatures[i].current;
438 next_bkt[i]->signatures[j].current = bkt->signatures[i].alt;
439 next_bkt[i]->key_idx[j] = bkt->key_idx[i];
443 /* Pick entry that has not been pushed yet */
444 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++)
445 if (bkt->flag[i] == 0)
448 /* All entries have been pushed, so entry cannot be added */
449 if (i == RTE_HASH_BUCKET_ENTRIES)
452 /* Set flag to indicate that this entry is going to be pushed */
454 /* Need room in alternative bucket to insert the pushed entry */
455 ret = make_space_bucket(h, next_bkt[i]);
457 * After recursive function.
458 * Clear flags and insert the pushed entry
459 * in its alternative location if successful,
464 next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current;
465 next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt;
466 next_bkt[i]->key_idx[ret] = bkt->key_idx[i];
473 static inline int32_t
474 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
475 hash_sig_t sig, void *data)
478 uint32_t prim_bucket_idx, sec_bucket_idx;
480 struct rte_hash_bucket *prim_bkt, *sec_bkt;
481 struct rte_hash_key *new_k, *k, *keys = h->key_store;
486 prim_bucket_idx = sig & h->bucket_bitmask;
487 prim_bkt = &h->buckets[prim_bucket_idx];
488 rte_prefetch0(prim_bkt);
490 alt_hash = rte_hash_secondary_hash(sig);
491 sec_bucket_idx = alt_hash & h->bucket_bitmask;
492 sec_bkt = &h->buckets[sec_bucket_idx];
493 rte_prefetch0(sec_bkt);
495 /* Get a new slot for storing the new key */
496 if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)
498 new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
499 rte_prefetch0(new_k);
500 new_idx = (uint32_t)((uintptr_t) slot_id);
502 /* Check if key is already inserted in primary location */
503 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
504 if (prim_bkt->signatures[i].current == sig &&
505 prim_bkt->signatures[i].alt == alt_hash) {
506 k = (struct rte_hash_key *) ((char *)keys +
507 prim_bkt->key_idx[i] * h->key_entry_size);
508 if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
509 rte_ring_sp_enqueue(h->free_slots, &slot_id);
513 * Return index where key is stored,
514 * substracting the first dummy index
516 return (prim_bkt->key_idx[i] - 1);
521 /* Check if key is already inserted in secondary location */
522 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
523 if (sec_bkt->signatures[i].alt == sig &&
524 sec_bkt->signatures[i].current == alt_hash) {
525 k = (struct rte_hash_key *) ((char *)keys +
526 sec_bkt->key_idx[i] * h->key_entry_size);
527 if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
528 rte_ring_sp_enqueue(h->free_slots, &slot_id);
532 * Return index where key is stored,
533 * substracting the first dummy index
535 return (sec_bkt->key_idx[i] - 1);
541 rte_memcpy(new_k->key, key, h->key_len);
544 /* Insert new entry is there is room in the primary bucket */
545 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
546 /* Check if slot is available */
547 if (likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) {
548 prim_bkt->signatures[i].current = sig;
549 prim_bkt->signatures[i].alt = alt_hash;
550 prim_bkt->key_idx[i] = new_idx;
555 /* Primary bucket is full, so we need to make space for new entry */
556 ret = make_space_bucket(h, prim_bkt);
558 * After recursive function.
559 * Insert the new entry in the position of the pushed entry
560 * if successful or return error and
561 * store the new slot back in the ring
564 prim_bkt->signatures[ret].current = sig;
565 prim_bkt->signatures[ret].alt = alt_hash;
566 prim_bkt->key_idx[ret] = new_idx;
567 return (new_idx - 1);
570 /* Error in addition, store new slot back in the ring and return error */
571 rte_ring_sp_enqueue(h->free_slots,
572 (void *)((uintptr_t) new_idx));
578 rte_hash_add_key_with_hash(const struct rte_hash *h,
579 const void *key, hash_sig_t sig)
581 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
582 return __rte_hash_add_key_with_hash(h, key, sig, 0);
586 rte_hash_add_key(const struct rte_hash *h, const void *key)
588 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
589 return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
593 rte_hash_add_key_with_hash_data(const struct rte_hash *h,
594 const void *key, hash_sig_t sig, void *data)
598 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
599 ret = __rte_hash_add_key_with_hash(h, key, sig, data);
607 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)
611 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
613 ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data);
619 static inline int32_t
620 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
621 hash_sig_t sig, void **data)
626 struct rte_hash_bucket *bkt;
627 struct rte_hash_key *k, *keys = h->key_store;
629 bucket_idx = sig & h->bucket_bitmask;
630 bkt = &h->buckets[bucket_idx];
632 /* Check if key is in primary location */
633 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
634 if (bkt->signatures[i].current == sig &&
635 bkt->signatures[i].sig != NULL_SIGNATURE) {
636 k = (struct rte_hash_key *) ((char *)keys +
637 bkt->key_idx[i] * h->key_entry_size);
638 if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
642 * Return index where key is stored,
643 * substracting the first dummy index
645 return (bkt->key_idx[i] - 1);
650 /* Calculate secondary hash */
651 alt_hash = rte_hash_secondary_hash(sig);
652 bucket_idx = alt_hash & h->bucket_bitmask;
653 bkt = &h->buckets[bucket_idx];
655 /* Check if key is in secondary location */
656 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
657 if (bkt->signatures[i].current == alt_hash &&
658 bkt->signatures[i].alt == sig) {
659 k = (struct rte_hash_key *) ((char *)keys +
660 bkt->key_idx[i] * h->key_entry_size);
661 if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
665 * Return index where key is stored,
666 * substracting the first dummy index
668 return (bkt->key_idx[i] - 1);
677 rte_hash_lookup_with_hash(const struct rte_hash *h,
678 const void *key, hash_sig_t sig)
680 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
681 return __rte_hash_lookup_with_hash(h, key, sig, NULL);
685 rte_hash_lookup(const struct rte_hash *h, const void *key)
687 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
688 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
692 rte_hash_lookup_with_hash_data(const struct rte_hash *h,
693 const void *key, hash_sig_t sig, void **data)
695 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
696 return __rte_hash_lookup_with_hash(h, key, sig, data);
700 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)
702 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
703 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
706 static inline int32_t
707 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
713 struct rte_hash_bucket *bkt;
714 struct rte_hash_key *k, *keys = h->key_store;
716 bucket_idx = sig & h->bucket_bitmask;
717 bkt = &h->buckets[bucket_idx];
719 /* Check if key is in primary location */
720 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
721 if (bkt->signatures[i].current == sig &&
722 bkt->signatures[i].sig != NULL_SIGNATURE) {
723 k = (struct rte_hash_key *) ((char *)keys +
724 bkt->key_idx[i] * h->key_entry_size);
725 if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
726 bkt->signatures[i].sig = NULL_SIGNATURE;
727 rte_ring_sp_enqueue(h->free_slots,
728 (void *)((uintptr_t)bkt->key_idx[i]));
730 * Return index where key is stored,
731 * substracting the first dummy index
733 return (bkt->key_idx[i] - 1);
738 /* Calculate secondary hash */
739 alt_hash = rte_hash_secondary_hash(sig);
740 bucket_idx = alt_hash & h->bucket_bitmask;
741 bkt = &h->buckets[bucket_idx];
743 /* Check if key is in secondary location */
744 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
745 if (bkt->signatures[i].current == alt_hash &&
746 bkt->signatures[i].sig != NULL_SIGNATURE) {
747 k = (struct rte_hash_key *) ((char *)keys +
748 bkt->key_idx[i] * h->key_entry_size);
749 if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
750 bkt->signatures[i].sig = NULL_SIGNATURE;
751 rte_ring_sp_enqueue(h->free_slots,
752 (void *)((uintptr_t)bkt->key_idx[i]));
754 * Return index where key is stored,
755 * substracting the first dummy index
757 return (bkt->key_idx[i] - 1);
766 rte_hash_del_key_with_hash(const struct rte_hash *h,
767 const void *key, hash_sig_t sig)
769 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
770 return __rte_hash_del_key_with_hash(h, key, sig);
774 rte_hash_del_key(const struct rte_hash *h, const void *key)
776 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
777 return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
780 /* Lookup bulk stage 0: Prefetch input key */
782 lookup_stage0(unsigned *idx, uint64_t *lookup_mask,
783 const void * const *keys)
785 *idx = __builtin_ctzl(*lookup_mask);
786 if (*lookup_mask == 0)
789 rte_prefetch0(keys[*idx]);
790 *lookup_mask &= ~(1llu << *idx);
794 * Lookup bulk stage 1: Calculate primary/secondary hashes
795 * and prefetch primary/secondary buckets
798 lookup_stage1(unsigned idx, hash_sig_t *prim_hash, hash_sig_t *sec_hash,
799 const struct rte_hash_bucket **primary_bkt,
800 const struct rte_hash_bucket **secondary_bkt,
801 hash_sig_t *hash_vals, const void * const *keys,
802 const struct rte_hash *h)
804 *prim_hash = rte_hash_hash(h, keys[idx]);
805 hash_vals[idx] = *prim_hash;
806 *sec_hash = rte_hash_secondary_hash(*prim_hash);
808 *primary_bkt = &h->buckets[*prim_hash & h->bucket_bitmask];
809 *secondary_bkt = &h->buckets[*sec_hash & h->bucket_bitmask];
811 rte_prefetch0(*primary_bkt);
812 rte_prefetch0(*secondary_bkt);
816 * Lookup bulk stage 2: Search for match hashes in primary/secondary locations
817 * and prefetch first key slot
820 lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,
821 const struct rte_hash_bucket *prim_bkt,
822 const struct rte_hash_bucket *sec_bkt,
823 const struct rte_hash_key **key_slot, int32_t *positions,
824 uint64_t *extra_hits_mask, const void *keys,
825 const struct rte_hash *h)
827 unsigned prim_hash_matches, sec_hash_matches, key_idx, i;
828 unsigned total_hash_matches;
830 prim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
831 sec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
832 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
833 prim_hash_matches |= ((prim_hash == prim_bkt->signatures[i].current) << i);
834 sec_hash_matches |= ((sec_hash == sec_bkt->signatures[i].current) << i);
837 key_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)];
839 key_idx = sec_bkt->key_idx[__builtin_ctzl(sec_hash_matches)];
841 total_hash_matches = (prim_hash_matches |
842 (sec_hash_matches << (RTE_HASH_BUCKET_ENTRIES + 1)));
843 *key_slot = (const struct rte_hash_key *) ((const char *)keys +
844 key_idx * h->key_entry_size);
846 rte_prefetch0(*key_slot);
848 * Return index where key is stored,
849 * substracting the first dummy index
851 positions[idx] = (key_idx - 1);
853 *extra_hits_mask |= (uint64_t)(__builtin_popcount(total_hash_matches) > 3) << idx;
858 /* Lookup bulk stage 3: Check if key matches, update hit mask and return data */
860 lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * const *keys,
861 void *data[], uint64_t *hits, const struct rte_hash *h)
865 hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len);
867 data[idx] = key_slot->pdata;
869 *hits |= (uint64_t)(hit) << idx;
873 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
874 uint32_t num_keys, int32_t *positions,
875 uint64_t *hit_mask, void *data[])
878 uint64_t extra_hits_mask = 0;
879 uint64_t lookup_mask, miss_mask;
881 const void *key_store = h->key_store;
883 hash_sig_t hash_vals[RTE_HASH_LOOKUP_BULK_MAX];
885 unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
886 const struct rte_hash_bucket *primary_bkt10, *primary_bkt11;
887 const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11;
888 const struct rte_hash_bucket *primary_bkt20, *primary_bkt21;
889 const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21;
890 const struct rte_hash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;
891 hash_sig_t primary_hash10, primary_hash11;
892 hash_sig_t secondary_hash10, secondary_hash11;
893 hash_sig_t primary_hash20, primary_hash21;
894 hash_sig_t secondary_hash20, secondary_hash21;
896 lookup_mask = (uint64_t) -1 >> (64 - num_keys);
897 miss_mask = lookup_mask;
899 lookup_stage0(&idx00, &lookup_mask, keys);
900 lookup_stage0(&idx01, &lookup_mask, keys);
902 idx10 = idx00, idx11 = idx01;
904 lookup_stage0(&idx00, &lookup_mask, keys);
905 lookup_stage0(&idx01, &lookup_mask, keys);
906 lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
907 &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
908 lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
909 &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
911 primary_bkt20 = primary_bkt10;
912 primary_bkt21 = primary_bkt11;
913 secondary_bkt20 = secondary_bkt10;
914 secondary_bkt21 = secondary_bkt11;
915 primary_hash20 = primary_hash10;
916 primary_hash21 = primary_hash11;
917 secondary_hash20 = secondary_hash10;
918 secondary_hash21 = secondary_hash11;
919 idx20 = idx10, idx21 = idx11;
920 idx10 = idx00, idx11 = idx01;
922 lookup_stage0(&idx00, &lookup_mask, keys);
923 lookup_stage0(&idx01, &lookup_mask, keys);
924 lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
925 &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
926 lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
927 &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
928 lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
929 secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
931 lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
932 secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
935 while (lookup_mask) {
936 k_slot30 = k_slot20, k_slot31 = k_slot21;
937 idx30 = idx20, idx31 = idx21;
938 primary_bkt20 = primary_bkt10;
939 primary_bkt21 = primary_bkt11;
940 secondary_bkt20 = secondary_bkt10;
941 secondary_bkt21 = secondary_bkt11;
942 primary_hash20 = primary_hash10;
943 primary_hash21 = primary_hash11;
944 secondary_hash20 = secondary_hash10;
945 secondary_hash21 = secondary_hash11;
946 idx20 = idx10, idx21 = idx11;
947 idx10 = idx00, idx11 = idx01;
949 lookup_stage0(&idx00, &lookup_mask, keys);
950 lookup_stage0(&idx01, &lookup_mask, keys);
951 lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
952 &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
953 lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
954 &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
955 lookup_stage2(idx20, primary_hash20, secondary_hash20,
956 primary_bkt20, secondary_bkt20, &k_slot20, positions,
957 &extra_hits_mask, key_store, h);
958 lookup_stage2(idx21, primary_hash21, secondary_hash21,
959 primary_bkt21, secondary_bkt21, &k_slot21, positions,
960 &extra_hits_mask, key_store, h);
961 lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
962 lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
965 k_slot30 = k_slot20, k_slot31 = k_slot21;
966 idx30 = idx20, idx31 = idx21;
967 primary_bkt20 = primary_bkt10;
968 primary_bkt21 = primary_bkt11;
969 secondary_bkt20 = secondary_bkt10;
970 secondary_bkt21 = secondary_bkt11;
971 primary_hash20 = primary_hash10;
972 primary_hash21 = primary_hash11;
973 secondary_hash20 = secondary_hash10;
974 secondary_hash21 = secondary_hash11;
975 idx20 = idx10, idx21 = idx11;
976 idx10 = idx00, idx11 = idx01;
978 lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
979 &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
980 lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
981 &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
982 lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
983 secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
985 lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
986 secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
988 lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
989 lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
991 k_slot30 = k_slot20, k_slot31 = k_slot21;
992 idx30 = idx20, idx31 = idx21;
993 primary_bkt20 = primary_bkt10;
994 primary_bkt21 = primary_bkt11;
995 secondary_bkt20 = secondary_bkt10;
996 secondary_bkt21 = secondary_bkt11;
997 primary_hash20 = primary_hash10;
998 primary_hash21 = primary_hash11;
999 secondary_hash20 = secondary_hash10;
1000 secondary_hash21 = secondary_hash11;
1001 idx20 = idx10, idx21 = idx11;
1003 lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
1004 secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
1006 lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
1007 secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
1009 lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
1010 lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
1012 k_slot30 = k_slot20, k_slot31 = k_slot21;
1013 idx30 = idx20, idx31 = idx21;
1015 lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
1016 lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
1018 /* ignore any items we have already found */
1019 extra_hits_mask &= ~hits;
1021 if (unlikely(extra_hits_mask)) {
1022 /* run a single search for each remaining item */
1024 idx = __builtin_ctzl(extra_hits_mask);
1026 ret = rte_hash_lookup_with_hash_data(h,
1027 keys[idx], hash_vals[idx], &data[idx]);
1029 hits |= 1ULL << idx;
1031 positions[idx] = rte_hash_lookup_with_hash(h,
1032 keys[idx], hash_vals[idx]);
1033 if (positions[idx] >= 0)
1034 hits |= 1llu << idx;
1036 extra_hits_mask &= ~(1llu << idx);
1037 } while (extra_hits_mask);
1041 if (unlikely(miss_mask)) {
1043 idx = __builtin_ctzl(miss_mask);
1044 positions[idx] = -ENOENT;
1045 miss_mask &= ~(1llu << idx);
1046 } while (miss_mask);
1049 if (hit_mask != NULL)
1054 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1055 uint32_t num_keys, int32_t *positions)
1057 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1058 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1059 (positions == NULL)), -EINVAL);
1061 __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL);
1066 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
1067 uint32_t num_keys, uint64_t *hit_mask, void *data[])
1069 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1070 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1071 (hit_mask == NULL)), -EINVAL);
1073 int32_t positions[num_keys];
1075 __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data);
1077 /* Return number of hits */
1078 return __builtin_popcountl(*hit_mask);
1082 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
1084 uint32_t bucket_idx, idx, position;
1085 struct rte_hash_key *next_key;
1087 RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
1089 const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
1091 if (*next >= total_entries)
1094 /* Calculate bucket and index of current iterator */
1095 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1096 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1098 /* If current position is empty, go to the next one */
1099 while (h->buckets[bucket_idx].signatures[idx].sig == NULL_SIGNATURE) {
1102 if (*next == total_entries)
1104 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1105 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1108 /* Get position of entry in key table */
1109 position = h->buckets[bucket_idx].key_idx[idx];
1110 next_key = (struct rte_hash_key *) ((char *)h->key_store +
1111 position * h->key_entry_size);
1112 /* Return key and data */
1113 *key = next_key->key;
1114 *data = next_key->pdata;
1116 /* Increment iterator */
1119 return (position - 1);
1122 /* Functions to compare multiple of 16 byte keys (up to 128 bytes) */
1124 rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
1126 const __m128i k1 = _mm_loadu_si128((const __m128i *) key1);
1127 const __m128i k2 = _mm_loadu_si128((const __m128i *) key2);
1128 #ifdef RTE_MACHINE_CPUFLAG_SSE4_1
1129 const __m128i x = _mm_xor_si128(k1, k2);
1131 return !_mm_test_all_zeros(x, x);
1133 const __m128i x = _mm_cmpeq_epi32(k1, k2);
1135 return (_mm_movemask_epi8(x) != 0xffff);
1140 rte_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len)
1142 return rte_hash_k16_cmp_eq(key1, key2, key_len) ||
1143 rte_hash_k16_cmp_eq((const char *) key1 + 16,
1144 (const char *) key2 + 16, key_len);
1148 rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len)
1150 return rte_hash_k16_cmp_eq(key1, key2, key_len) ||
1151 rte_hash_k16_cmp_eq((const char *) key1 + 16,
1152 (const char *) key2 + 16, key_len) ||
1153 rte_hash_k16_cmp_eq((const char *) key1 + 32,
1154 (const char *) key2 + 32, key_len);
1158 rte_hash_k64_cmp_eq(const void *key1, const void *key2, size_t key_len)
1160 return rte_hash_k32_cmp_eq(key1, key2, key_len) ||
1161 rte_hash_k32_cmp_eq((const char *) key1 + 32,
1162 (const char *) key2 + 32, key_len);
1166 rte_hash_k80_cmp_eq(const void *key1, const void *key2, size_t key_len)
1168 return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
1169 rte_hash_k16_cmp_eq((const char *) key1 + 64,
1170 (const char *) key2 + 64, key_len);
1174 rte_hash_k96_cmp_eq(const void *key1, const void *key2, size_t key_len)
1176 return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
1177 rte_hash_k32_cmp_eq((const char *) key1 + 64,
1178 (const char *) key2 + 64, key_len);
1182 rte_hash_k112_cmp_eq(const void *key1, const void *key2, size_t key_len)
1184 return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
1185 rte_hash_k32_cmp_eq((const char *) key1 + 64,
1186 (const char *) key2 + 64, key_len) ||
1187 rte_hash_k16_cmp_eq((const char *) key1 + 96,
1188 (const char *) key2 + 96, key_len);
1192 rte_hash_k128_cmp_eq(const void *key1, const void *key2, size_t key_len)
1194 return rte_hash_k64_cmp_eq(key1, key2, key_len) ||
1195 rte_hash_k64_cmp_eq((const char *) key1 + 64,
1196 (const char *) key2 + 64, key_len);