lib/librte_hash/rte_cuckoo_hash.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  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
  16  *       distribution.
  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.
  20  *
  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.
  32  */
  33
  34 #include <string.h>
  35 #include <stdint.h>
  36 #include <errno.h>
  37 #include <stdio.h>
  38 #include <stdarg.h>
  39 #include <sys/queue.h>
  40
  41 #include <rte_common.h>
  42 #include <rte_memory.h>         /* for definition of RTE_CACHE_LINE_SIZE */
  43 #include <rte_log.h>
  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>
  49 #include <rte_eal.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>
  55 #include <rte_log.h>
  56 #include <rte_rwlock.h>
  57 #include <rte_spinlock.h>
  58 #include <rte_ring.h>
  59 #include <rte_compat.h>
  60
  61 #include "rte_hash.h"
  62 #include "rte_cuckoo_hash.h"
  63
  64 #if defined(RTE_ARCH_X86)
  65 #include "rte_cuckoo_hash_x86.h"
  66 #endif
  67
  68 TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
  69
  70 static struct rte_tailq_elem rte_hash_tailq = {
  71         .name = "RTE_HASH",
  72 };
  73 EAL_REGISTER_TAILQ(rte_hash_tailq)
  74
  75 struct rte_hash *
  76 rte_hash_find_existing(const char *name)
  77 {
  78         struct rte_hash *h = NULL;
  79         struct rte_tailq_entry *te;
  80         struct rte_hash_list *hash_list;
  81
  82         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
  83
  84         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
  85         TAILQ_FOREACH(te, hash_list, next) {
  86                 h = (struct rte_hash *) te->data;
  87                 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
  88                         break;
  89         }
  90         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
  91
  92         if (te == NULL) {
  93                 rte_errno = ENOENT;
  94                 return NULL;
  95         }
  96         return h;
  97 }
  98
  99 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
 100 {
 101         h->rte_hash_custom_cmp_eq = func;
 102 }
 103
 104 static inline int
 105 rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)
 106 {
 107         if (h->cmp_jump_table_idx == KEY_CUSTOM)
 108                 return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len);
 109         else
 110                 return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);
 111 }
 112
 113 struct rte_hash *
 114 rte_hash_create(const struct rte_hash_parameters *params)
 115 {
 116         struct rte_hash *h = NULL;
 117         struct rte_tailq_entry *te = NULL;
 118         struct rte_hash_list *hash_list;
 119         struct rte_ring *r = NULL;
 120         char hash_name[RTE_HASH_NAMESIZE];
 121         void *k = NULL;
 122         void *buckets = NULL;
 123         char ring_name[RTE_RING_NAMESIZE];
 124         unsigned num_key_slots;
 125         unsigned hw_trans_mem_support = 0;
 126         unsigned i;
 127
 128         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 129
 130         if (params == NULL) {
 131                 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
 132                 return NULL;
 133         }
 134
 135         /* Check for valid parameters */
 136         if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
 137                         (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
 138                         !rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) ||
 139                         (params->key_len == 0)) {
 140                 rte_errno = EINVAL;
 141                 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
 142                 return NULL;
 143         }
 144
 145         /* Check extra flags field to check extra options. */
 146         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
 147                 hw_trans_mem_support = 1;
 148
 149         /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
 150         if (hw_trans_mem_support)
 151                 /*
 152                  * Increase number of slots by total number of indices
 153                  * that can be stored in the lcore caches
 154                  * except for the first cache
 155                  */
 156                 num_key_slots = params->entries + (RTE_MAX_LCORE - 1) *
 157                                         LCORE_CACHE_SIZE + 1;
 158         else
 159                 num_key_slots = params->entries + 1;
 160
 161         snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
 162         /* Create ring (Dummy slot index is not enqueued) */
 163         r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots - 1),
 164                         params->socket_id, 0);
 165         if (r == NULL) {
 166                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 167                 goto err;
 168         }
 169
 170         snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
 171
 172         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 173
 174         /* guarantee there's no existing: this is normally already checked
 175          * by ring creation above */
 176         TAILQ_FOREACH(te, hash_list, next) {
 177                 h = (struct rte_hash *) te->data;
 178                 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
 179                         break;
 180         }
 181         h = NULL;
 182         if (te != NULL) {
 183                 rte_errno = EEXIST;
 184                 te = NULL;
 185                 goto err_unlock;
 186         }
 187
 188         te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
 189         if (te == NULL) {
 190                 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
 191                 goto err_unlock;
 192         }
 193
 194         h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
 195                                         RTE_CACHE_LINE_SIZE, params->socket_id);
 196
 197         if (h == NULL) {
 198                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 199                 goto err_unlock;
 200         }
 201
 202         const uint32_t num_buckets = rte_align32pow2(params->entries)
 203                                         / RTE_HASH_BUCKET_ENTRIES;
 204
 205         buckets = rte_zmalloc_socket(NULL,
 206                                 num_buckets * sizeof(struct rte_hash_bucket),
 207                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 208
 209         if (buckets == NULL) {
 210                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 211                 goto err_unlock;
 212         }
 213
 214         const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;
 215         const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
 216
 217         k = rte_zmalloc_socket(NULL, key_tbl_size,
 218                         RTE_CACHE_LINE_SIZE, params->socket_id);
 219
 220         if (k == NULL) {
 221                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 222                 goto err_unlock;
 223         }
 224
 225 /*
 226  * If x86 architecture is used, select appropriate compare function,
 227  * which may use x86 intrinsics, otherwise use memcmp
 228  */
 229 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
 230         /* Select function to compare keys */
 231         switch (params->key_len) {
 232         case 16:
 233                 h->cmp_jump_table_idx = KEY_16_BYTES;
 234                 break;
 235         case 32:
 236                 h->cmp_jump_table_idx = KEY_32_BYTES;
 237                 break;
 238         case 48:
 239                 h->cmp_jump_table_idx = KEY_48_BYTES;
 240                 break;
 241         case 64:
 242                 h->cmp_jump_table_idx = KEY_64_BYTES;
 243                 break;
 244         case 80:
 245                 h->cmp_jump_table_idx = KEY_80_BYTES;
 246                 break;
 247         case 96:
 248                 h->cmp_jump_table_idx = KEY_96_BYTES;
 249                 break;
 250         case 112:
 251                 h->cmp_jump_table_idx = KEY_112_BYTES;
 252                 break;
 253         case 128:
 254                 h->cmp_jump_table_idx = KEY_128_BYTES;
 255                 break;
 256         default:
 257                 /* If key is not multiple of 16, use generic memcmp */
 258                 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
 259         }
 260 #else
 261         h->cmp_jump_table_idx = KEY_OTHER_BYTES;
 262 #endif
 263
 264         if (hw_trans_mem_support) {
 265                 h->local_free_slots = rte_zmalloc_socket(NULL,
 266                                 sizeof(struct lcore_cache) * RTE_MAX_LCORE,
 267                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 268         }
 269
 270         /* Setup hash context */
 271         snprintf(h->name, sizeof(h->name), "%s", params->name);
 272         h->entries = params->entries;
 273         h->key_len = params->key_len;
 274         h->key_entry_size = key_entry_size;
 275         h->hash_func_init_val = params->hash_func_init_val;
 276
 277         h->num_buckets = num_buckets;
 278         h->bucket_bitmask = h->num_buckets - 1;
 279         h->buckets = buckets;
 280         h->hash_func = (params->hash_func == NULL) ?
 281                 DEFAULT_HASH_FUNC : params->hash_func;
 282         h->key_store = k;
 283         h->free_slots = r;
 284         h->hw_trans_mem_support = hw_trans_mem_support;
 285
 286         /* Turn on multi-writer only with explicit flat from user and TM
 287          * support.
 288          */
 289         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) {
 290                 if (h->hw_trans_mem_support) {
 291                         h->add_key = ADD_KEY_MULTIWRITER_TM;
 292                 } else {
 293                         h->add_key = ADD_KEY_MULTIWRITER;
 294                         h->multiwriter_lock = rte_malloc(NULL,
 295                                                         sizeof(rte_spinlock_t),
 296                                                         LCORE_CACHE_SIZE);
 297                         rte_spinlock_init(h->multiwriter_lock);
 298                 }
 299         } else
 300                 h->add_key = ADD_KEY_SINGLEWRITER;
 301
 302         /* Populate free slots ring. Entry zero is reserved for key misses. */
 303         for (i = 1; i < params->entries + 1; i++)
 304                 rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
 305
 306         te->data = (void *) h;
 307         TAILQ_INSERT_TAIL(hash_list, te, next);
 308         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 309
 310         return h;
 311 err_unlock:
 312         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 313 err:
 314         rte_ring_free(r);
 315         rte_free(te);
 316         rte_free(h);
 317         rte_free(buckets);
 318         rte_free(k);
 319         return NULL;
 320 }
 321
 322 void
 323 rte_hash_free(struct rte_hash *h)
 324 {
 325         struct rte_tailq_entry *te;
 326         struct rte_hash_list *hash_list;
 327
 328         if (h == NULL)
 329                 return;
 330
 331         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 332
 333         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 334
 335         /* find out tailq entry */
 336         TAILQ_FOREACH(te, hash_list, next) {
 337                 if (te->data == (void *) h)
 338                         break;
 339         }
 340
 341         if (te == NULL) {
 342                 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 343                 return;
 344         }
 345
 346         TAILQ_REMOVE(hash_list, te, next);
 347
 348         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 349
 350         if (h->hw_trans_mem_support)
 351                 rte_free(h->local_free_slots);
 352
 353         if (h->add_key == ADD_KEY_MULTIWRITER)
 354                 rte_free(h->multiwriter_lock);
 355         rte_ring_free(h->free_slots);
 356         rte_free(h->key_store);
 357         rte_free(h->buckets);
 358         rte_free(h);
 359         rte_free(te);
 360 }
 361
 362 hash_sig_t
 363 rte_hash_hash(const struct rte_hash *h, const void *key)
 364 {
 365         /* calc hash result by key */
 366         return h->hash_func(key, h->key_len, h->hash_func_init_val);
 367 }
 368
 369 /* Calc the secondary hash value from the primary hash value of a given key */
 370 static inline hash_sig_t
 371 rte_hash_secondary_hash(const hash_sig_t primary_hash)
 372 {
 373         static const unsigned all_bits_shift = 12;
 374         static const unsigned alt_bits_xor = 0x5bd1e995;
 375
 376         uint32_t tag = primary_hash >> all_bits_shift;
 377
 378         return primary_hash ^ ((tag + 1) * alt_bits_xor);
 379 }
 380
 381 void
 382 rte_hash_reset(struct rte_hash *h)
 383 {
 384         void *ptr;
 385         unsigned i;
 386
 387         if (h == NULL)
 388                 return;
 389
 390         memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket));
 391         memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
 392
 393         /* clear the free ring */
 394         while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
 395                 rte_pause();
 396
 397         /* Repopulate the free slots ring. Entry zero is reserved for key misses */
 398         for (i = 1; i < h->entries + 1; i++)
 399                 rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));
 400
 401         if (h->hw_trans_mem_support) {
 402                 /* Reset local caches per lcore */
 403                 for (i = 0; i < RTE_MAX_LCORE; i++)
 404                         h->local_free_slots[i].len = 0;
 405         }
 406 }
 407
 408 /* Search for an entry that can be pushed to its alternative location */
 409 static inline int
 410 make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
 411 {
 412         static unsigned int nr_pushes;
 413         unsigned i, j;
 414         int ret;
 415         uint32_t next_bucket_idx;
 416         struct rte_hash_bucket *next_bkt[RTE_HASH_BUCKET_ENTRIES];
 417
 418         /*
 419          * Push existing item (search for bucket with space in
 420          * alternative locations) to its alternative location
 421          */
 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)
 428                                 break;
 429                 }
 430
 431                 if (j != RTE_HASH_BUCKET_ENTRIES)
 432                         break;
 433         }
 434
 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];
 440                 return i;
 441         }
 442
 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)
 446                         break;
 447
 448         /* All entries have been pushed, so entry cannot be added */
 449         if (i == RTE_HASH_BUCKET_ENTRIES || nr_pushes > RTE_HASH_MAX_PUSHES)
 450                 return -ENOSPC;
 451
 452         /* Set flag to indicate that this entry is going to be pushed */
 453         bkt->flag[i] = 1;
 454
 455         nr_pushes++;
 456         /* Need room in alternative bucket to insert the pushed entry */
 457         ret = make_space_bucket(h, next_bkt[i]);
 458         /*
 459          * After recursive function.
 460          * Clear flags and insert the pushed entry
 461          * in its alternative location if successful,
 462          * or return error
 463          */
 464         bkt->flag[i] = 0;
 465         nr_pushes = 0;
 466         if (ret >= 0) {
 467                 next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current;
 468                 next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt;
 469                 next_bkt[i]->key_idx[ret] = bkt->key_idx[i];
 470                 return i;
 471         } else
 472                 return ret;
 473
 474 }
 475
 476 /*
 477  * Function called to enqueue back an index in the cache/ring,
 478  * as slot has not being used and it can be used in the
 479  * next addition attempt.
 480  */
 481 static inline void
 482 enqueue_slot_back(const struct rte_hash *h,
 483                 struct lcore_cache *cached_free_slots,
 484                 void *slot_id)
 485 {
 486         if (h->hw_trans_mem_support) {
 487                 cached_free_slots->objs[cached_free_slots->len] = slot_id;
 488                 cached_free_slots->len++;
 489         } else
 490                 rte_ring_sp_enqueue(h->free_slots, slot_id);
 491 }
 492
 493 static inline int32_t
 494 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
 495                                                 hash_sig_t sig, void *data)
 496 {
 497         hash_sig_t alt_hash;
 498         uint32_t prim_bucket_idx, sec_bucket_idx;
 499         unsigned i;
 500         struct rte_hash_bucket *prim_bkt, *sec_bkt;
 501         struct rte_hash_key *new_k, *k, *keys = h->key_store;
 502         void *slot_id = NULL;
 503         uint32_t new_idx;
 504         int ret;
 505         unsigned n_slots;
 506         unsigned lcore_id;
 507         struct lcore_cache *cached_free_slots = NULL;
 508
 509         if (h->add_key == ADD_KEY_MULTIWRITER)
 510                 rte_spinlock_lock(h->multiwriter_lock);
 511
 512         prim_bucket_idx = sig & h->bucket_bitmask;
 513         prim_bkt = &h->buckets[prim_bucket_idx];
 514         rte_prefetch0(prim_bkt);
 515
 516         alt_hash = rte_hash_secondary_hash(sig);
 517         sec_bucket_idx = alt_hash & h->bucket_bitmask;
 518         sec_bkt = &h->buckets[sec_bucket_idx];
 519         rte_prefetch0(sec_bkt);
 520
 521         /* Get a new slot for storing the new key */
 522         if (h->hw_trans_mem_support) {
 523                 lcore_id = rte_lcore_id();
 524                 cached_free_slots = &h->local_free_slots[lcore_id];
 525                 /* Try to get a free slot from the local cache */
 526                 if (cached_free_slots->len == 0) {
 527                         /* Need to get another burst of free slots from global ring */
 528                         n_slots = rte_ring_mc_dequeue_burst(h->free_slots,
 529                                         cached_free_slots->objs, LCORE_CACHE_SIZE);
 530                         if (n_slots == 0)
 531                                 return -ENOSPC;
 532
 533                         cached_free_slots->len += n_slots;
 534                 }
 535
 536                 /* Get a free slot from the local cache */
 537                 cached_free_slots->len--;
 538                 slot_id = cached_free_slots->objs[cached_free_slots->len];
 539         } else {
 540                 if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)
 541                         return -ENOSPC;
 542         }
 543
 544         new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
 545         rte_prefetch0(new_k);
 546         new_idx = (uint32_t)((uintptr_t) slot_id);
 547
 548         /* Check if key is already inserted in primary location */
 549         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 550                 if (prim_bkt->signatures[i].current == sig &&
 551                                 prim_bkt->signatures[i].alt == alt_hash) {
 552                         k = (struct rte_hash_key *) ((char *)keys +
 553                                         prim_bkt->key_idx[i] * h->key_entry_size);
 554                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 555                                 /* Enqueue index of free slot back in the ring. */
 556                                 enqueue_slot_back(h, cached_free_slots, slot_id);
 557                                 /* Update data */
 558                                 k->pdata = data;
 559                                 /*
 560                                  * Return index where key is stored,
 561                                  * substracting the first dummy index
 562                                  */
 563                                 return prim_bkt->key_idx[i] - 1;
 564                         }
 565                 }
 566         }
 567
 568         /* Check if key is already inserted in secondary location */
 569         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 570                 if (sec_bkt->signatures[i].alt == sig &&
 571                                 sec_bkt->signatures[i].current == alt_hash) {
 572                         k = (struct rte_hash_key *) ((char *)keys +
 573                                         sec_bkt->key_idx[i] * h->key_entry_size);
 574                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 575                                 /* Enqueue index of free slot back in the ring. */
 576                                 enqueue_slot_back(h, cached_free_slots, slot_id);
 577                                 /* Update data */
 578                                 k->pdata = data;
 579                                 /*
 580                                  * Return index where key is stored,
 581                                  * substracting the first dummy index
 582                                  */
 583                                 return sec_bkt->key_idx[i] - 1;
 584                         }
 585                 }
 586         }
 587
 588         /* Copy key */
 589         rte_memcpy(new_k->key, key, h->key_len);
 590         new_k->pdata = data;
 591
 592 #if defined(RTE_ARCH_X86) /* currently only x86 support HTM */
 593         if (h->add_key == ADD_KEY_MULTIWRITER_TM) {
 594                 ret = rte_hash_cuckoo_insert_mw_tm(prim_bkt,
 595                                 sig, alt_hash, new_idx);
 596                 if (ret >= 0)
 597                         return new_idx - 1;
 598
 599                 /* Primary bucket full, need to make space for new entry */
 600                 ret = rte_hash_cuckoo_make_space_mw_tm(h, prim_bkt, sig,
 601                                                         alt_hash, new_idx);
 602
 603                 if (ret >= 0)
 604                         return new_idx - 1;
 605
 606                 /* Also search secondary bucket to get better occupancy */
 607                 ret = rte_hash_cuckoo_make_space_mw_tm(h, sec_bkt, sig,
 608                                                         alt_hash, new_idx);
 609
 610                 if (ret >= 0)
 611                         return new_idx - 1;
 612         } else {
 613 #endif
 614                 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 615                         /* Check if slot is available */
 616                         if (likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) {
 617                                 prim_bkt->signatures[i].current = sig;
 618                                 prim_bkt->signatures[i].alt = alt_hash;
 619                                 prim_bkt->key_idx[i] = new_idx;
 620                                 break;
 621                         }
 622                 }
 623
 624                 if (i != RTE_HASH_BUCKET_ENTRIES) {
 625                         if (h->add_key == ADD_KEY_MULTIWRITER)
 626                                 rte_spinlock_unlock(h->multiwriter_lock);
 627                         return new_idx - 1;
 628                 }
 629
 630                 /* Primary bucket full, need to make space for new entry
 631                  * After recursive function.
 632                  * Insert the new entry in the position of the pushed entry
 633                  * if successful or return error and
 634                  * store the new slot back in the ring
 635                  */
 636                 ret = make_space_bucket(h, prim_bkt);
 637                 if (ret >= 0) {
 638                         prim_bkt->signatures[ret].current = sig;
 639                         prim_bkt->signatures[ret].alt = alt_hash;
 640                         prim_bkt->key_idx[ret] = new_idx;
 641                         if (h->add_key == ADD_KEY_MULTIWRITER)
 642                                 rte_spinlock_unlock(h->multiwriter_lock);
 643                         return new_idx - 1;
 644                 }
 645 #if defined(RTE_ARCH_X86)
 646         }
 647 #endif
 648         /* Error in addition, store new slot back in the ring and return error */
 649         enqueue_slot_back(h, cached_free_slots, (void *)((uintptr_t) new_idx));
 650
 651         if (h->add_key == ADD_KEY_MULTIWRITER)
 652                 rte_spinlock_unlock(h->multiwriter_lock);
 653         return ret;
 654 }
 655
 656 int32_t
 657 rte_hash_add_key_with_hash(const struct rte_hash *h,
 658                         const void *key, hash_sig_t sig)
 659 {
 660         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 661         return __rte_hash_add_key_with_hash(h, key, sig, 0);
 662 }
 663
 664 int32_t
 665 rte_hash_add_key(const struct rte_hash *h, const void *key)
 666 {
 667         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 668         return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
 669 }
 670
 671 int
 672 rte_hash_add_key_with_hash_data(const struct rte_hash *h,
 673                         const void *key, hash_sig_t sig, void *data)
 674 {
 675         int ret;
 676
 677         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 678         ret = __rte_hash_add_key_with_hash(h, key, sig, data);
 679         if (ret >= 0)
 680                 return 0;
 681         else
 682                 return ret;
 683 }
 684
 685 int
 686 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)
 687 {
 688         int ret;
 689
 690         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 691
 692         ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data);
 693         if (ret >= 0)
 694                 return 0;
 695         else
 696                 return ret;
 697 }
 698 static inline int32_t
 699 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
 700                                         hash_sig_t sig, void **data)
 701 {
 702         uint32_t bucket_idx;
 703         hash_sig_t alt_hash;
 704         unsigned i;
 705         struct rte_hash_bucket *bkt;
 706         struct rte_hash_key *k, *keys = h->key_store;
 707
 708         bucket_idx = sig & h->bucket_bitmask;
 709         bkt = &h->buckets[bucket_idx];
 710
 711         /* Check if key is in primary location */
 712         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 713                 if (bkt->signatures[i].current == sig &&
 714                                 bkt->signatures[i].sig != NULL_SIGNATURE) {
 715                         k = (struct rte_hash_key *) ((char *)keys +
 716                                         bkt->key_idx[i] * h->key_entry_size);
 717                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 718                                 if (data != NULL)
 719                                         *data = k->pdata;
 720                                 /*
 721                                  * Return index where key is stored,
 722                                  * substracting the first dummy index
 723                                  */
 724                                 return bkt->key_idx[i] - 1;
 725                         }
 726                 }
 727         }
 728
 729         /* Calculate secondary hash */
 730         alt_hash = rte_hash_secondary_hash(sig);
 731         bucket_idx = alt_hash & h->bucket_bitmask;
 732         bkt = &h->buckets[bucket_idx];
 733
 734         /* Check if key is in secondary location */
 735         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 736                 if (bkt->signatures[i].current == alt_hash &&
 737                                 bkt->signatures[i].alt == sig) {
 738                         k = (struct rte_hash_key *) ((char *)keys +
 739                                         bkt->key_idx[i] * h->key_entry_size);
 740                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 741                                 if (data != NULL)
 742                                         *data = k->pdata;
 743                                 /*
 744                                  * Return index where key is stored,
 745                                  * substracting the first dummy index
 746                                  */
 747                                 return bkt->key_idx[i] - 1;
 748                         }
 749                 }
 750         }
 751
 752         return -ENOENT;
 753 }
 754
 755 int32_t
 756 rte_hash_lookup_with_hash(const struct rte_hash *h,
 757                         const void *key, hash_sig_t sig)
 758 {
 759         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 760         return __rte_hash_lookup_with_hash(h, key, sig, NULL);
 761 }
 762
 763 int32_t
 764 rte_hash_lookup(const struct rte_hash *h, const void *key)
 765 {
 766         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 767         return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
 768 }
 769
 770 int
 771 rte_hash_lookup_with_hash_data(const struct rte_hash *h,
 772                         const void *key, hash_sig_t sig, void **data)
 773 {
 774         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 775         return __rte_hash_lookup_with_hash(h, key, sig, data);
 776 }
 777
 778 int
 779 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)
 780 {
 781         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 782         return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
 783 }
 784
 785 static inline void
 786 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
 787 {
 788         unsigned lcore_id, n_slots;
 789         struct lcore_cache *cached_free_slots;
 790
 791         bkt->signatures[i].sig = NULL_SIGNATURE;
 792         if (h->hw_trans_mem_support) {
 793                 lcore_id = rte_lcore_id();
 794                 cached_free_slots = &h->local_free_slots[lcore_id];
 795                 /* Cache full, need to free it. */
 796                 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
 797                         /* Need to enqueue the free slots in global ring. */
 798                         n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
 799                                                 cached_free_slots->objs,
 800                                                 LCORE_CACHE_SIZE);
 801                         cached_free_slots->len -= n_slots;
 802                 }
 803                 /* Put index of new free slot in cache. */
 804                 cached_free_slots->objs[cached_free_slots->len] =
 805                                 (void *)((uintptr_t)bkt->key_idx[i]);
 806                 cached_free_slots->len++;
 807         } else {
 808                 rte_ring_sp_enqueue(h->free_slots,
 809                                 (void *)((uintptr_t)bkt->key_idx[i]));
 810         }
 811 }
 812
 813 static inline int32_t
 814 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 815                                                 hash_sig_t sig)
 816 {
 817         uint32_t bucket_idx;
 818         hash_sig_t alt_hash;
 819         unsigned i;
 820         struct rte_hash_bucket *bkt;
 821         struct rte_hash_key *k, *keys = h->key_store;
 822         int32_t ret;
 823
 824         bucket_idx = sig & h->bucket_bitmask;
 825         bkt = &h->buckets[bucket_idx];
 826
 827         /* Check if key is in primary location */
 828         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 829                 if (bkt->signatures[i].current == sig &&
 830                                 bkt->signatures[i].sig != NULL_SIGNATURE) {
 831                         k = (struct rte_hash_key *) ((char *)keys +
 832                                         bkt->key_idx[i] * h->key_entry_size);
 833                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 834                                 remove_entry(h, bkt, i);
 835
 836                                 /*
 837                                  * Return index where key is stored,
 838                                  * substracting the first dummy index
 839                                  */
 840                                 ret = bkt->key_idx[i] - 1;
 841                                 bkt->key_idx[i] = 0;
 842                                 return ret;
 843                         }
 844                 }
 845         }
 846
 847         /* Calculate secondary hash */
 848         alt_hash = rte_hash_secondary_hash(sig);
 849         bucket_idx = alt_hash & h->bucket_bitmask;
 850         bkt = &h->buckets[bucket_idx];
 851
 852         /* Check if key is in secondary location */
 853         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 854                 if (bkt->signatures[i].current == alt_hash &&
 855                                 bkt->signatures[i].sig != NULL_SIGNATURE) {
 856                         k = (struct rte_hash_key *) ((char *)keys +
 857                                         bkt->key_idx[i] * h->key_entry_size);
 858                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 859                                 remove_entry(h, bkt, i);
 860
 861                                 /*
 862                                  * Return index where key is stored,
 863                                  * substracting the first dummy index
 864                                  */
 865                                 ret = bkt->key_idx[i] - 1;
 866                                 bkt->key_idx[i] = 0;
 867                                 return ret;
 868                         }
 869                 }
 870         }
 871
 872         return -ENOENT;
 873 }
 874
 875 int32_t
 876 rte_hash_del_key_with_hash(const struct rte_hash *h,
 877                         const void *key, hash_sig_t sig)
 878 {
 879         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 880         return __rte_hash_del_key_with_hash(h, key, sig);
 881 }
 882
 883 int32_t
 884 rte_hash_del_key(const struct rte_hash *h, const void *key)
 885 {
 886         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 887         return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
 888 }
 889
 890 int
 891 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
 892                                void **key)
 893 {
 894         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 895
 896         struct rte_hash_key *k, *keys = h->key_store;
 897         k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
 898                                      h->key_entry_size);
 899         *key = k->key;
 900
 901         if (position !=
 902             __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
 903                                         NULL)) {
 904                 return -ENOENT;
 905         }
 906
 907         return 0;
 908 }
 909
 910 /* Lookup bulk stage 0: Prefetch input key */
 911 static inline void
 912 lookup_stage0(unsigned *idx, uint64_t *lookup_mask,
 913                 const void * const *keys)
 914 {
 915         *idx = __builtin_ctzl(*lookup_mask);
 916         if (*lookup_mask == 0)
 917                 *idx = 0;
 918
 919         rte_prefetch0(keys[*idx]);
 920         *lookup_mask &= ~(1llu << *idx);
 921 }
 922
 923 /*
 924  * Lookup bulk stage 1: Calculate primary/secondary hashes
 925  * and prefetch primary/secondary buckets
 926  */
 927 static inline void
 928 lookup_stage1(unsigned idx, hash_sig_t *prim_hash, hash_sig_t *sec_hash,
 929                 const struct rte_hash_bucket **primary_bkt,
 930                 const struct rte_hash_bucket **secondary_bkt,
 931                 hash_sig_t *hash_vals, const void * const *keys,
 932                 const struct rte_hash *h)
 933 {
 934         *prim_hash = rte_hash_hash(h, keys[idx]);
 935         hash_vals[idx] = *prim_hash;
 936         *sec_hash = rte_hash_secondary_hash(*prim_hash);
 937
 938         *primary_bkt = &h->buckets[*prim_hash & h->bucket_bitmask];
 939         *secondary_bkt = &h->buckets[*sec_hash & h->bucket_bitmask];
 940
 941         rte_prefetch0(*primary_bkt);
 942         rte_prefetch0(*secondary_bkt);
 943 }
 944
 945 /*
 946  * Lookup bulk stage 2:  Search for match hashes in primary/secondary locations
 947  * and prefetch first key slot
 948  */
 949 static inline void
 950 lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,
 951                 const struct rte_hash_bucket *prim_bkt,
 952                 const struct rte_hash_bucket *sec_bkt,
 953                 const struct rte_hash_key **key_slot, int32_t *positions,
 954                 uint64_t *extra_hits_mask, const void *keys,
 955                 const struct rte_hash *h)
 956 {
 957         unsigned prim_hash_matches, sec_hash_matches, key_idx, i;
 958         unsigned total_hash_matches;
 959
 960         prim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
 961         sec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
 962         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 963                 prim_hash_matches |= ((prim_hash == prim_bkt->signatures[i].current) << i);
 964                 sec_hash_matches |= ((sec_hash == sec_bkt->signatures[i].current) << i);
 965         }
 966
 967         key_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)];
 968         if (key_idx == 0)
 969                 key_idx = sec_bkt->key_idx[__builtin_ctzl(sec_hash_matches)];
 970
 971         total_hash_matches = (prim_hash_matches |
 972                                 (sec_hash_matches << (RTE_HASH_BUCKET_ENTRIES + 1)));
 973         *key_slot = (const struct rte_hash_key *) ((const char *)keys +
 974                                         key_idx * h->key_entry_size);
 975
 976         rte_prefetch0(*key_slot);
 977         /*
 978          * Return index where key is stored,
 979          * substracting the first dummy index
 980          */
 981         positions[idx] = (key_idx - 1);
 982
 983         *extra_hits_mask |= (uint64_t)(__builtin_popcount(total_hash_matches) > 3) << idx;
 984
 985 }
 986
 987
 988 /* Lookup bulk stage 3: Check if key matches, update hit mask and return data */
 989 static inline void
 990 lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * const *keys,
 991                 const int32_t *positions, void *data[], uint64_t *hits,
 992                 const struct rte_hash *h)
 993 {
 994         unsigned hit;
 995         unsigned key_idx;
 996
 997         hit = !rte_hash_cmp_eq(key_slot->key, keys[idx], h);
 998         if (data != NULL)
 999                 data[idx] = key_slot->pdata;
1000
1001         key_idx = positions[idx] + 1;
1002         /*
1003          * If key index is 0, force hit to be 0, in case key to be looked up
1004          * is all zero (as in the dummy slot), which would result in a wrong hit
1005          */
1006         *hits |= (uint64_t)(hit && !!key_idx)  << idx;
1007 }
1008
1009 static inline void
1010 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1011                         uint32_t num_keys, int32_t *positions,
1012                         uint64_t *hit_mask, void *data[])
1013 {
1014         uint64_t hits = 0;
1015         uint64_t extra_hits_mask = 0;
1016         uint64_t lookup_mask, miss_mask;
1017         unsigned idx;
1018         const void *key_store = h->key_store;
1019         int ret;
1020         hash_sig_t hash_vals[RTE_HASH_LOOKUP_BULK_MAX];
1021
1022         unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
1023         const struct rte_hash_bucket *primary_bkt10, *primary_bkt11;
1024         const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11;
1025         const struct rte_hash_bucket *primary_bkt20, *primary_bkt21;
1026         const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21;
1027         const struct rte_hash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;
1028         hash_sig_t primary_hash10, primary_hash11;
1029         hash_sig_t secondary_hash10, secondary_hash11;
1030         hash_sig_t primary_hash20, primary_hash21;
1031         hash_sig_t secondary_hash20, secondary_hash21;
1032
1033         lookup_mask = (uint64_t) -1 >> (64 - num_keys);
1034         miss_mask = lookup_mask;
1035
1036         lookup_stage0(&idx00, &lookup_mask, keys);
1037         lookup_stage0(&idx01, &lookup_mask, keys);
1038
1039         idx10 = idx00, idx11 = idx01;
1040
1041         lookup_stage0(&idx00, &lookup_mask, keys);
1042         lookup_stage0(&idx01, &lookup_mask, keys);
1043         lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
1044                         &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
1045         lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
1046                         &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
1047
1048         primary_bkt20 = primary_bkt10;
1049         primary_bkt21 = primary_bkt11;
1050         secondary_bkt20 = secondary_bkt10;
1051         secondary_bkt21 = secondary_bkt11;
1052         primary_hash20 = primary_hash10;
1053         primary_hash21 = primary_hash11;
1054         secondary_hash20 = secondary_hash10;
1055         secondary_hash21 = secondary_hash11;
1056         idx20 = idx10, idx21 = idx11;
1057         idx10 = idx00, idx11 = idx01;
1058
1059         lookup_stage0(&idx00, &lookup_mask, keys);
1060         lookup_stage0(&idx01, &lookup_mask, keys);
1061         lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
1062                         &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
1063         lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
1064                         &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
1065         lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
1066                         secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
1067                         key_store, h);
1068         lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
1069                         secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
1070                         key_store, h);
1071
1072         while (lookup_mask) {
1073                 k_slot30 = k_slot20, k_slot31 = k_slot21;
1074                 idx30 = idx20, idx31 = idx21;
1075                 primary_bkt20 = primary_bkt10;
1076                 primary_bkt21 = primary_bkt11;
1077                 secondary_bkt20 = secondary_bkt10;
1078                 secondary_bkt21 = secondary_bkt11;
1079                 primary_hash20 = primary_hash10;
1080                 primary_hash21 = primary_hash11;
1081                 secondary_hash20 = secondary_hash10;
1082                 secondary_hash21 = secondary_hash11;
1083                 idx20 = idx10, idx21 = idx11;
1084                 idx10 = idx00, idx11 = idx01;
1085
1086                 lookup_stage0(&idx00, &lookup_mask, keys);
1087                 lookup_stage0(&idx01, &lookup_mask, keys);
1088                 lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
1089                         &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
1090                 lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
1091                         &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
1092                 lookup_stage2(idx20, primary_hash20, secondary_hash20,
1093                         primary_bkt20, secondary_bkt20, &k_slot20, positions,
1094                         &extra_hits_mask, key_store, h);
1095                 lookup_stage2(idx21, primary_hash21, secondary_hash21,
1096                         primary_bkt21, secondary_bkt21, &k_slot21, positions,
1097                         &extra_hits_mask, key_store, h);
1098                 lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
1099                 lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
1100         }
1101
1102         k_slot30 = k_slot20, k_slot31 = k_slot21;
1103         idx30 = idx20, idx31 = idx21;
1104         primary_bkt20 = primary_bkt10;
1105         primary_bkt21 = primary_bkt11;
1106         secondary_bkt20 = secondary_bkt10;
1107         secondary_bkt21 = secondary_bkt11;
1108         primary_hash20 = primary_hash10;
1109         primary_hash21 = primary_hash11;
1110         secondary_hash20 = secondary_hash10;
1111         secondary_hash21 = secondary_hash11;
1112         idx20 = idx10, idx21 = idx11;
1113         idx10 = idx00, idx11 = idx01;
1114
1115         lookup_stage1(idx10, &primary_hash10, &secondary_hash10,
1116                 &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
1117         lookup_stage1(idx11, &primary_hash11, &secondary_hash11,
1118                 &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
1119         lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
1120                 secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
1121                 key_store, h);
1122         lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
1123                 secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
1124                 key_store, h);
1125         lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
1126         lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
1127
1128         k_slot30 = k_slot20, k_slot31 = k_slot21;
1129         idx30 = idx20, idx31 = idx21;
1130         primary_bkt20 = primary_bkt10;
1131         primary_bkt21 = primary_bkt11;
1132         secondary_bkt20 = secondary_bkt10;
1133         secondary_bkt21 = secondary_bkt11;
1134         primary_hash20 = primary_hash10;
1135         primary_hash21 = primary_hash11;
1136         secondary_hash20 = secondary_hash10;
1137         secondary_hash21 = secondary_hash11;
1138         idx20 = idx10, idx21 = idx11;
1139
1140         lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20,
1141                 secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
1142                 key_store, h);
1143         lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21,
1144                 secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
1145                 key_store, h);
1146         lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
1147         lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
1148
1149         k_slot30 = k_slot20, k_slot31 = k_slot21;
1150         idx30 = idx20, idx31 = idx21;
1151
1152         lookup_stage3(idx30, k_slot30, keys, positions, data, &hits, h);
1153         lookup_stage3(idx31, k_slot31, keys, positions, data, &hits, h);
1154
1155         /* ignore any items we have already found */
1156         extra_hits_mask &= ~hits;
1157
1158         if (unlikely(extra_hits_mask)) {
1159                 /* run a single search for each remaining item */
1160                 do {
1161                         idx = __builtin_ctzl(extra_hits_mask);
1162                         if (data != NULL) {
1163                                 ret = rte_hash_lookup_with_hash_data(h,
1164                                                 keys[idx], hash_vals[idx], &data[idx]);
1165                                 if (ret >= 0)
1166                                         hits |= 1ULL << idx;
1167                         } else {
1168                                 positions[idx] = rte_hash_lookup_with_hash(h,
1169                                                         keys[idx], hash_vals[idx]);
1170                                 if (positions[idx] >= 0)
1171                                         hits |= 1llu << idx;
1172                         }
1173                         extra_hits_mask &= ~(1llu << idx);
1174                 } while (extra_hits_mask);
1175         }
1176
1177         miss_mask &= ~hits;
1178         if (unlikely(miss_mask)) {
1179                 do {
1180                         idx = __builtin_ctzl(miss_mask);
1181                         positions[idx] = -ENOENT;
1182                         miss_mask &= ~(1llu << idx);
1183                 } while (miss_mask);
1184         }
1185
1186         if (hit_mask != NULL)
1187                 *hit_mask = hits;
1188 }
1189
1190 int
1191 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1192                       uint32_t num_keys, int32_t *positions)
1193 {
1194         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1195                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1196                         (positions == NULL)), -EINVAL);
1197
1198         __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL);
1199         return 0;
1200 }
1201
1202 int
1203 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
1204                       uint32_t num_keys, uint64_t *hit_mask, void *data[])
1205 {
1206         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1207                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1208                         (hit_mask == NULL)), -EINVAL);
1209
1210         int32_t positions[num_keys];
1211
1212         __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data);
1213
1214         /* Return number of hits */
1215         return __builtin_popcountl(*hit_mask);
1216 }
1217
1218 int32_t
1219 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
1220 {
1221         uint32_t bucket_idx, idx, position;
1222         struct rte_hash_key *next_key;
1223
1224         RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
1225
1226         const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
1227         /* Out of bounds */
1228         if (*next >= total_entries)
1229                 return -ENOENT;
1230
1231         /* Calculate bucket and index of current iterator */
1232         bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1233         idx = *next % RTE_HASH_BUCKET_ENTRIES;
1234
1235         /* If current position is empty, go to the next one */
1236         while (h->buckets[bucket_idx].signatures[idx].sig == NULL_SIGNATURE) {
1237                 (*next)++;
1238                 /* End of table */
1239                 if (*next == total_entries)
1240                         return -ENOENT;
1241                 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1242                 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1243         }
1244
1245         /* Get position of entry in key table */
1246         position = h->buckets[bucket_idx].key_idx[idx];
1247         next_key = (struct rte_hash_key *) ((char *)h->key_store +
1248                                 position * h->key_entry_size);
1249         /* Return key and data */
1250         *key = next_key->key;
1251         *data = next_key->pdata;
1252
1253         /* Increment iterator */
1254         (*next)++;
1255
1256         return position - 1;
1257 }