lib/librte_hash/rte_cuckoo_hash.c

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