lib/hash/rte_cuckoo_hash.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2016 Intel Corporation
   3  * Copyright(c) 2018 Arm Limited
   4  */
   5
   6 #include <string.h>
   7 #include <stdint.h>
   8 #include <errno.h>
   9 #include <stdio.h>
  10 #include <sys/queue.h>
  11
  12 #include <rte_common.h>
  13 #include <rte_log.h>
  14 #include <rte_prefetch.h>
  15 #include <rte_branch_prediction.h>
  16 #include <rte_malloc.h>
  17 #include <rte_eal_memconfig.h>
  18 #include <rte_errno.h>
  19 #include <rte_string_fns.h>
  20 #include <rte_cpuflags.h>
  21 #include <rte_rwlock.h>
  22 #include <rte_ring_elem.h>
  23 #include <rte_vect.h>
  24 #include <rte_tailq.h>
  25
  26 #include "rte_hash.h"
  27 #include "rte_cuckoo_hash.h"
  28
  29 /* Mask of all flags supported by this version */
  30 #define RTE_HASH_EXTRA_FLAGS_MASK (RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT | \
  31                                    RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD | \
  32                                    RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY | \
  33                                    RTE_HASH_EXTRA_FLAGS_EXT_TABLE |     \
  34                                    RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL | \
  35                                    RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF)
  36
  37 #define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET)                            \
  38         for (CURRENT_BKT = START_BUCKET;                                      \
  39                 CURRENT_BKT != NULL;                                          \
  40                 CURRENT_BKT = CURRENT_BKT->next)
  41
  42 TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
  43
  44 static struct rte_tailq_elem rte_hash_tailq = {
  45         .name = "RTE_HASH",
  46 };
  47 EAL_REGISTER_TAILQ(rte_hash_tailq)
  48
  49 struct __rte_hash_rcu_dq_entry {
  50         uint32_t key_idx;
  51         uint32_t ext_bkt_idx;
  52 };
  53
  54 struct rte_hash *
  55 rte_hash_find_existing(const char *name)
  56 {
  57         struct rte_hash *h = NULL;
  58         struct rte_tailq_entry *te;
  59         struct rte_hash_list *hash_list;
  60
  61         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
  62
  63         rte_mcfg_tailq_read_lock();
  64         TAILQ_FOREACH(te, hash_list, next) {
  65                 h = (struct rte_hash *) te->data;
  66                 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
  67                         break;
  68         }
  69         rte_mcfg_tailq_read_unlock();
  70
  71         if (te == NULL) {
  72                 rte_errno = ENOENT;
  73                 return NULL;
  74         }
  75         return h;
  76 }
  77
  78 static inline struct rte_hash_bucket *
  79 rte_hash_get_last_bkt(struct rte_hash_bucket *lst_bkt)
  80 {
  81         while (lst_bkt->next != NULL)
  82                 lst_bkt = lst_bkt->next;
  83         return lst_bkt;
  84 }
  85
  86 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
  87 {
  88         h->cmp_jump_table_idx = KEY_CUSTOM;
  89         h->rte_hash_custom_cmp_eq = func;
  90 }
  91
  92 static inline int
  93 rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)
  94 {
  95         if (h->cmp_jump_table_idx == KEY_CUSTOM)
  96                 return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len);
  97         else
  98                 return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);
  99 }
 100
 101 /*
 102  * We use higher 16 bits of hash as the signature value stored in table.
 103  * We use the lower bits for the primary bucket
 104  * location. Then we XOR primary bucket location and the signature
 105  * to get the secondary bucket location. This is same as
 106  * proposed in Bin Fan, et al's paper
 107  * "MemC3: Compact and Concurrent MemCache with Dumber Caching and
 108  * Smarter Hashing". The benefit to use
 109  * XOR is that one could derive the alternative bucket location
 110  * by only using the current bucket location and the signature.
 111  */
 112 static inline uint16_t
 113 get_short_sig(const hash_sig_t hash)
 114 {
 115         return hash >> 16;
 116 }
 117
 118 static inline uint32_t
 119 get_prim_bucket_index(const struct rte_hash *h, const hash_sig_t hash)
 120 {
 121         return hash & h->bucket_bitmask;
 122 }
 123
 124 static inline uint32_t
 125 get_alt_bucket_index(const struct rte_hash *h,
 126                         uint32_t cur_bkt_idx, uint16_t sig)
 127 {
 128         return (cur_bkt_idx ^ sig) & h->bucket_bitmask;
 129 }
 130
 131 struct rte_hash *
 132 rte_hash_create(const struct rte_hash_parameters *params)
 133 {
 134         struct rte_hash *h = NULL;
 135         struct rte_tailq_entry *te = NULL;
 136         struct rte_hash_list *hash_list;
 137         struct rte_ring *r = NULL;
 138         struct rte_ring *r_ext = NULL;
 139         char hash_name[RTE_HASH_NAMESIZE];
 140         void *k = NULL;
 141         void *buckets = NULL;
 142         void *buckets_ext = NULL;
 143         char ring_name[RTE_RING_NAMESIZE];
 144         char ext_ring_name[RTE_RING_NAMESIZE];
 145         unsigned num_key_slots;
 146         unsigned int hw_trans_mem_support = 0, use_local_cache = 0;
 147         unsigned int ext_table_support = 0;
 148         unsigned int readwrite_concur_support = 0;
 149         unsigned int writer_takes_lock = 0;
 150         unsigned int no_free_on_del = 0;
 151         uint32_t *ext_bkt_to_free = NULL;
 152         uint32_t *tbl_chng_cnt = NULL;
 153         struct lcore_cache *local_free_slots = NULL;
 154         unsigned int readwrite_concur_lf_support = 0;
 155         uint32_t i;
 156
 157         rte_hash_function default_hash_func = (rte_hash_function)rte_jhash;
 158
 159         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 160
 161         if (params == NULL) {
 162                 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
 163                 return NULL;
 164         }
 165
 166         /* Check for valid parameters */
 167         if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
 168                         (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
 169                         (params->key_len == 0)) {
 170                 rte_errno = EINVAL;
 171                 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
 172                 return NULL;
 173         }
 174
 175         if (params->extra_flag & ~RTE_HASH_EXTRA_FLAGS_MASK) {
 176                 rte_errno = EINVAL;
 177                 RTE_LOG(ERR, HASH, "rte_hash_create: unsupported extra flags\n");
 178                 return NULL;
 179         }
 180
 181         /* Validate correct usage of extra options */
 182         if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) &&
 183             (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF)) {
 184                 rte_errno = EINVAL;
 185                 RTE_LOG(ERR, HASH, "rte_hash_create: choose rw concurrency or "
 186                         "rw concurrency lock free\n");
 187                 return NULL;
 188         }
 189
 190         /* Check extra flags field to check extra options. */
 191         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
 192                 hw_trans_mem_support = 1;
 193
 194         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) {
 195                 use_local_cache = 1;
 196                 writer_takes_lock = 1;
 197         }
 198
 199         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) {
 200                 readwrite_concur_support = 1;
 201                 writer_takes_lock = 1;
 202         }
 203
 204         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)
 205                 ext_table_support = 1;
 206
 207         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL)
 208                 no_free_on_del = 1;
 209
 210         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) {
 211                 readwrite_concur_lf_support = 1;
 212                 /* Enable not freeing internal memory/index on delete.
 213                  * If internal RCU is enabled, freeing of internal memory/index
 214                  * is done on delete
 215                  */
 216                 no_free_on_del = 1;
 217         }
 218
 219         /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
 220         if (use_local_cache)
 221                 /*
 222                  * Increase number of slots by total number of indices
 223                  * that can be stored in the lcore caches
 224                  * except for the first cache
 225                  */
 226                 num_key_slots = params->entries + (RTE_MAX_LCORE - 1) *
 227                                         (LCORE_CACHE_SIZE - 1) + 1;
 228         else
 229                 num_key_slots = params->entries + 1;
 230
 231         snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
 232         /* Create ring (Dummy slot index is not enqueued) */
 233         r = rte_ring_create_elem(ring_name, sizeof(uint32_t),
 234                         rte_align32pow2(num_key_slots), params->socket_id, 0);
 235         if (r == NULL) {
 236                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 237                 goto err;
 238         }
 239
 240         const uint32_t num_buckets = rte_align32pow2(params->entries) /
 241                                                 RTE_HASH_BUCKET_ENTRIES;
 242
 243         /* Create ring for extendable buckets. */
 244         if (ext_table_support) {
 245                 snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s",
 246                                                                 params->name);
 247                 r_ext = rte_ring_create_elem(ext_ring_name, sizeof(uint32_t),
 248                                 rte_align32pow2(num_buckets + 1),
 249                                 params->socket_id, 0);
 250
 251                 if (r_ext == NULL) {
 252                         RTE_LOG(ERR, HASH, "ext buckets memory allocation "
 253                                                                 "failed\n");
 254                         goto err;
 255                 }
 256         }
 257
 258         snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
 259
 260         rte_mcfg_tailq_write_lock();
 261
 262         /* guarantee there's no existing: this is normally already checked
 263          * by ring creation above */
 264         TAILQ_FOREACH(te, hash_list, next) {
 265                 h = (struct rte_hash *) te->data;
 266                 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
 267                         break;
 268         }
 269         h = NULL;
 270         if (te != NULL) {
 271                 rte_errno = EEXIST;
 272                 te = NULL;
 273                 goto err_unlock;
 274         }
 275
 276         te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
 277         if (te == NULL) {
 278                 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
 279                 goto err_unlock;
 280         }
 281
 282         h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
 283                                         RTE_CACHE_LINE_SIZE, params->socket_id);
 284
 285         if (h == NULL) {
 286                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 287                 goto err_unlock;
 288         }
 289
 290         buckets = rte_zmalloc_socket(NULL,
 291                                 num_buckets * sizeof(struct rte_hash_bucket),
 292                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 293
 294         if (buckets == NULL) {
 295                 RTE_LOG(ERR, HASH, "buckets memory allocation failed\n");
 296                 goto err_unlock;
 297         }
 298
 299         /* Allocate same number of extendable buckets */
 300         if (ext_table_support) {
 301                 buckets_ext = rte_zmalloc_socket(NULL,
 302                                 num_buckets * sizeof(struct rte_hash_bucket),
 303                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 304                 if (buckets_ext == NULL) {
 305                         RTE_LOG(ERR, HASH, "ext buckets memory allocation "
 306                                                         "failed\n");
 307                         goto err_unlock;
 308                 }
 309                 /* Populate ext bkt ring. We reserve 0 similar to the
 310                  * key-data slot, just in case in future we want to
 311                  * use bucket index for the linked list and 0 means NULL
 312                  * for next bucket
 313                  */
 314                 for (i = 1; i <= num_buckets; i++)
 315                         rte_ring_sp_enqueue_elem(r_ext, &i, sizeof(uint32_t));
 316
 317                 if (readwrite_concur_lf_support) {
 318                         ext_bkt_to_free = rte_zmalloc(NULL, sizeof(uint32_t) *
 319                                                                 num_key_slots, 0);
 320                         if (ext_bkt_to_free == NULL) {
 321                                 RTE_LOG(ERR, HASH, "ext bkt to free memory allocation "
 322                                                                 "failed\n");
 323                                 goto err_unlock;
 324                         }
 325                 }
 326         }
 327
 328         const uint32_t key_entry_size =
 329                 RTE_ALIGN(sizeof(struct rte_hash_key) + params->key_len,
 330                           KEY_ALIGNMENT);
 331         const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
 332
 333         k = rte_zmalloc_socket(NULL, key_tbl_size,
 334                         RTE_CACHE_LINE_SIZE, params->socket_id);
 335
 336         if (k == NULL) {
 337                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 338                 goto err_unlock;
 339         }
 340
 341         tbl_chng_cnt = rte_zmalloc_socket(NULL, sizeof(uint32_t),
 342                         RTE_CACHE_LINE_SIZE, params->socket_id);
 343
 344         if (tbl_chng_cnt == NULL) {
 345                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 346                 goto err_unlock;
 347         }
 348
 349 /*
 350  * If x86 architecture is used, select appropriate compare function,
 351  * which may use x86 intrinsics, otherwise use memcmp
 352  */
 353 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
 354         /* Select function to compare keys */
 355         switch (params->key_len) {
 356         case 16:
 357                 h->cmp_jump_table_idx = KEY_16_BYTES;
 358                 break;
 359         case 32:
 360                 h->cmp_jump_table_idx = KEY_32_BYTES;
 361                 break;
 362         case 48:
 363                 h->cmp_jump_table_idx = KEY_48_BYTES;
 364                 break;
 365         case 64:
 366                 h->cmp_jump_table_idx = KEY_64_BYTES;
 367                 break;
 368         case 80:
 369                 h->cmp_jump_table_idx = KEY_80_BYTES;
 370                 break;
 371         case 96:
 372                 h->cmp_jump_table_idx = KEY_96_BYTES;
 373                 break;
 374         case 112:
 375                 h->cmp_jump_table_idx = KEY_112_BYTES;
 376                 break;
 377         case 128:
 378                 h->cmp_jump_table_idx = KEY_128_BYTES;
 379                 break;
 380         default:
 381                 /* If key is not multiple of 16, use generic memcmp */
 382                 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
 383         }
 384 #else
 385         h->cmp_jump_table_idx = KEY_OTHER_BYTES;
 386 #endif
 387
 388         if (use_local_cache) {
 389                 local_free_slots = rte_zmalloc_socket(NULL,
 390                                 sizeof(struct lcore_cache) * RTE_MAX_LCORE,
 391                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 392                 if (local_free_slots == NULL) {
 393                         RTE_LOG(ERR, HASH, "local free slots memory allocation failed\n");
 394                         goto err_unlock;
 395                 }
 396         }
 397
 398         /* Default hash function */
 399 #if defined(RTE_ARCH_X86)
 400         default_hash_func = (rte_hash_function)rte_hash_crc;
 401 #elif defined(RTE_ARCH_ARM64)
 402         if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32))
 403                 default_hash_func = (rte_hash_function)rte_hash_crc;
 404 #endif
 405         /* Setup hash context */
 406         strlcpy(h->name, params->name, sizeof(h->name));
 407         h->entries = params->entries;
 408         h->key_len = params->key_len;
 409         h->key_entry_size = key_entry_size;
 410         h->hash_func_init_val = params->hash_func_init_val;
 411
 412         h->num_buckets = num_buckets;
 413         h->bucket_bitmask = h->num_buckets - 1;
 414         h->buckets = buckets;
 415         h->buckets_ext = buckets_ext;
 416         h->free_ext_bkts = r_ext;
 417         h->hash_func = (params->hash_func == NULL) ?
 418                 default_hash_func : params->hash_func;
 419         h->key_store = k;
 420         h->free_slots = r;
 421         h->ext_bkt_to_free = ext_bkt_to_free;
 422         h->tbl_chng_cnt = tbl_chng_cnt;
 423         *h->tbl_chng_cnt = 0;
 424         h->hw_trans_mem_support = hw_trans_mem_support;
 425         h->use_local_cache = use_local_cache;
 426         h->local_free_slots = local_free_slots;
 427         h->readwrite_concur_support = readwrite_concur_support;
 428         h->ext_table_support = ext_table_support;
 429         h->writer_takes_lock = writer_takes_lock;
 430         h->no_free_on_del = no_free_on_del;
 431         h->readwrite_concur_lf_support = readwrite_concur_lf_support;
 432
 433 #if defined(RTE_ARCH_X86)
 434         if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))
 435                 h->sig_cmp_fn = RTE_HASH_COMPARE_SSE;
 436         else
 437 #elif defined(RTE_ARCH_ARM64)
 438         if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON))
 439                 h->sig_cmp_fn = RTE_HASH_COMPARE_NEON;
 440         else
 441 #endif
 442                 h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR;
 443
 444         /* Writer threads need to take the lock when:
 445          * 1) RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY is enabled OR
 446          * 2) RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD is enabled
 447          */
 448         if (h->writer_takes_lock) {
 449                 h->readwrite_lock = rte_malloc(NULL, sizeof(rte_rwlock_t),
 450                                                 RTE_CACHE_LINE_SIZE);
 451                 if (h->readwrite_lock == NULL)
 452                         goto err_unlock;
 453
 454                 rte_rwlock_init(h->readwrite_lock);
 455         }
 456
 457         /* Populate free slots ring. Entry zero is reserved for key misses. */
 458         for (i = 1; i < num_key_slots; i++)
 459                 rte_ring_sp_enqueue_elem(r, &i, sizeof(uint32_t));
 460
 461         te->data = (void *) h;
 462         TAILQ_INSERT_TAIL(hash_list, te, next);
 463         rte_mcfg_tailq_write_unlock();
 464
 465         return h;
 466 err_unlock:
 467         rte_mcfg_tailq_write_unlock();
 468 err:
 469         rte_ring_free(r);
 470         rte_ring_free(r_ext);
 471         rte_free(te);
 472         rte_free(local_free_slots);
 473         rte_free(h);
 474         rte_free(buckets);
 475         rte_free(buckets_ext);
 476         rte_free(k);
 477         rte_free(tbl_chng_cnt);
 478         rte_free(ext_bkt_to_free);
 479         return NULL;
 480 }
 481
 482 void
 483 rte_hash_free(struct rte_hash *h)
 484 {
 485         struct rte_tailq_entry *te;
 486         struct rte_hash_list *hash_list;
 487
 488         if (h == NULL)
 489                 return;
 490
 491         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 492
 493         rte_mcfg_tailq_write_lock();
 494
 495         /* find out tailq entry */
 496         TAILQ_FOREACH(te, hash_list, next) {
 497                 if (te->data == (void *) h)
 498                         break;
 499         }
 500
 501         if (te == NULL) {
 502                 rte_mcfg_tailq_write_unlock();
 503                 return;
 504         }
 505
 506         TAILQ_REMOVE(hash_list, te, next);
 507
 508         rte_mcfg_tailq_write_unlock();
 509
 510         if (h->dq)
 511                 rte_rcu_qsbr_dq_delete(h->dq);
 512
 513         if (h->use_local_cache)
 514                 rte_free(h->local_free_slots);
 515         if (h->writer_takes_lock)
 516                 rte_free(h->readwrite_lock);
 517         rte_ring_free(h->free_slots);
 518         rte_ring_free(h->free_ext_bkts);
 519         rte_free(h->key_store);
 520         rte_free(h->buckets);
 521         rte_free(h->buckets_ext);
 522         rte_free(h->tbl_chng_cnt);
 523         rte_free(h->ext_bkt_to_free);
 524         rte_free(h);
 525         rte_free(te);
 526 }
 527
 528 hash_sig_t
 529 rte_hash_hash(const struct rte_hash *h, const void *key)
 530 {
 531         /* calc hash result by key */
 532         return h->hash_func(key, h->key_len, h->hash_func_init_val);
 533 }
 534
 535 int32_t
 536 rte_hash_max_key_id(const struct rte_hash *h)
 537 {
 538         RETURN_IF_TRUE((h == NULL), -EINVAL);
 539         if (h->use_local_cache)
 540                 /*
 541                  * Increase number of slots by total number of indices
 542                  * that can be stored in the lcore caches
 543                  */
 544                 return (h->entries + ((RTE_MAX_LCORE - 1) *
 545                                         (LCORE_CACHE_SIZE - 1)));
 546         else
 547                 return h->entries;
 548 }
 549
 550 int32_t
 551 rte_hash_count(const struct rte_hash *h)
 552 {
 553         uint32_t tot_ring_cnt, cached_cnt = 0;
 554         uint32_t i, ret;
 555
 556         if (h == NULL)
 557                 return -EINVAL;
 558
 559         if (h->use_local_cache) {
 560                 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
 561                                         (LCORE_CACHE_SIZE - 1);
 562                 for (i = 0; i < RTE_MAX_LCORE; i++)
 563                         cached_cnt += h->local_free_slots[i].len;
 564
 565                 ret = tot_ring_cnt - rte_ring_count(h->free_slots) -
 566                                                                 cached_cnt;
 567         } else {
 568                 tot_ring_cnt = h->entries;
 569                 ret = tot_ring_cnt - rte_ring_count(h->free_slots);
 570         }
 571         return ret;
 572 }
 573
 574 /* Read write locks implemented using rte_rwlock */
 575 static inline void
 576 __hash_rw_writer_lock(const struct rte_hash *h)
 577 {
 578         if (h->writer_takes_lock && h->hw_trans_mem_support)
 579                 rte_rwlock_write_lock_tm(h->readwrite_lock);
 580         else if (h->writer_takes_lock)
 581                 rte_rwlock_write_lock(h->readwrite_lock);
 582 }
 583
 584 static inline void
 585 __hash_rw_reader_lock(const struct rte_hash *h)
 586 {
 587         if (h->readwrite_concur_support && h->hw_trans_mem_support)
 588                 rte_rwlock_read_lock_tm(h->readwrite_lock);
 589         else if (h->readwrite_concur_support)
 590                 rte_rwlock_read_lock(h->readwrite_lock);
 591 }
 592
 593 static inline void
 594 __hash_rw_writer_unlock(const struct rte_hash *h)
 595 {
 596         if (h->writer_takes_lock && h->hw_trans_mem_support)
 597                 rte_rwlock_write_unlock_tm(h->readwrite_lock);
 598         else if (h->writer_takes_lock)
 599                 rte_rwlock_write_unlock(h->readwrite_lock);
 600 }
 601
 602 static inline void
 603 __hash_rw_reader_unlock(const struct rte_hash *h)
 604 {
 605         if (h->readwrite_concur_support && h->hw_trans_mem_support)
 606                 rte_rwlock_read_unlock_tm(h->readwrite_lock);
 607         else if (h->readwrite_concur_support)
 608                 rte_rwlock_read_unlock(h->readwrite_lock);
 609 }
 610
 611 void
 612 rte_hash_reset(struct rte_hash *h)
 613 {
 614         uint32_t tot_ring_cnt, i;
 615         unsigned int pending;
 616
 617         if (h == NULL)
 618                 return;
 619
 620         __hash_rw_writer_lock(h);
 621
 622         if (h->dq) {
 623                 /* Reclaim all the resources */
 624                 rte_rcu_qsbr_dq_reclaim(h->dq, ~0, NULL, &pending, NULL);
 625                 if (pending != 0)
 626                         RTE_LOG(ERR, HASH, "RCU reclaim all resources failed\n");
 627         }
 628
 629         memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket));
 630         memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
 631         *h->tbl_chng_cnt = 0;
 632
 633         /* reset the free ring */
 634         rte_ring_reset(h->free_slots);
 635
 636         /* flush free extendable bucket ring and memory */
 637         if (h->ext_table_support) {
 638                 memset(h->buckets_ext, 0, h->num_buckets *
 639                                                 sizeof(struct rte_hash_bucket));
 640                 rte_ring_reset(h->free_ext_bkts);
 641         }
 642
 643         /* Repopulate the free slots ring. Entry zero is reserved for key misses */
 644         if (h->use_local_cache)
 645                 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
 646                                         (LCORE_CACHE_SIZE - 1);
 647         else
 648                 tot_ring_cnt = h->entries;
 649
 650         for (i = 1; i < tot_ring_cnt + 1; i++)
 651                 rte_ring_sp_enqueue_elem(h->free_slots, &i, sizeof(uint32_t));
 652
 653         /* Repopulate the free ext bkt ring. */
 654         if (h->ext_table_support) {
 655                 for (i = 1; i <= h->num_buckets; i++)
 656                         rte_ring_sp_enqueue_elem(h->free_ext_bkts, &i,
 657                                                         sizeof(uint32_t));
 658         }
 659
 660         if (h->use_local_cache) {
 661                 /* Reset local caches per lcore */
 662                 for (i = 0; i < RTE_MAX_LCORE; i++)
 663                         h->local_free_slots[i].len = 0;
 664         }
 665         __hash_rw_writer_unlock(h);
 666 }
 667
 668 /*
 669  * Function called to enqueue back an index in the cache/ring,
 670  * as slot has not being used and it can be used in the
 671  * next addition attempt.
 672  */
 673 static inline void
 674 enqueue_slot_back(const struct rte_hash *h,
 675                 struct lcore_cache *cached_free_slots,
 676                 uint32_t slot_id)
 677 {
 678         if (h->use_local_cache) {
 679                 cached_free_slots->objs[cached_free_slots->len] = slot_id;
 680                 cached_free_slots->len++;
 681         } else
 682                 rte_ring_sp_enqueue_elem(h->free_slots, &slot_id,
 683                                                 sizeof(uint32_t));
 684 }
 685
 686 /* Search a key from bucket and update its data.
 687  * Writer holds the lock before calling this.
 688  */
 689 static inline int32_t
 690 search_and_update(const struct rte_hash *h, void *data, const void *key,
 691         struct rte_hash_bucket *bkt, uint16_t sig)
 692 {
 693         int i;
 694         struct rte_hash_key *k, *keys = h->key_store;
 695
 696         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 697                 if (bkt->sig_current[i] == sig) {
 698                         k = (struct rte_hash_key *) ((char *)keys +
 699                                         bkt->key_idx[i] * h->key_entry_size);
 700                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 701                                 /* The store to application data at *data
 702                                  * should not leak after the store to pdata
 703                                  * in the key store. i.e. pdata is the guard
 704                                  * variable. Release the application data
 705                                  * to the readers.
 706                                  */
 707                                 __atomic_store_n(&k->pdata,
 708                                         data,
 709                                         __ATOMIC_RELEASE);
 710                                 /*
 711                                  * Return index where key is stored,
 712                                  * subtracting the first dummy index
 713                                  */
 714                                 return bkt->key_idx[i] - 1;
 715                         }
 716                 }
 717         }
 718         return -1;
 719 }
 720
 721 /* Only tries to insert at one bucket (@prim_bkt) without trying to push
 722  * buckets around.
 723  * return 1 if matching existing key, return 0 if succeeds, return -1 for no
 724  * empty entry.
 725  */
 726 static inline int32_t
 727 rte_hash_cuckoo_insert_mw(const struct rte_hash *h,
 728                 struct rte_hash_bucket *prim_bkt,
 729                 struct rte_hash_bucket *sec_bkt,
 730                 const struct rte_hash_key *key, void *data,
 731                 uint16_t sig, uint32_t new_idx,
 732                 int32_t *ret_val)
 733 {
 734         unsigned int i;
 735         struct rte_hash_bucket *cur_bkt;
 736         int32_t ret;
 737
 738         __hash_rw_writer_lock(h);
 739         /* Check if key was inserted after last check but before this
 740          * protected region in case of inserting duplicated keys.
 741          */
 742         ret = search_and_update(h, data, key, prim_bkt, sig);
 743         if (ret != -1) {
 744                 __hash_rw_writer_unlock(h);
 745                 *ret_val = ret;
 746                 return 1;
 747         }
 748
 749         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
 750                 ret = search_and_update(h, data, key, cur_bkt, sig);
 751                 if (ret != -1) {
 752                         __hash_rw_writer_unlock(h);
 753                         *ret_val = ret;
 754                         return 1;
 755                 }
 756         }
 757
 758         /* Insert new entry if there is room in the primary
 759          * bucket.
 760          */
 761         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 762                 /* Check if slot is available */
 763                 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
 764                         prim_bkt->sig_current[i] = sig;
 765                         /* Store to signature and key should not
 766                          * leak after the store to key_idx. i.e.
 767                          * key_idx is the guard variable for signature
 768                          * and key.
 769                          */
 770                         __atomic_store_n(&prim_bkt->key_idx[i],
 771                                          new_idx,
 772                                          __ATOMIC_RELEASE);
 773                         break;
 774                 }
 775         }
 776         __hash_rw_writer_unlock(h);
 777
 778         if (i != RTE_HASH_BUCKET_ENTRIES)
 779                 return 0;
 780
 781         /* no empty entry */
 782         return -1;
 783 }
 784
 785 /* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill
 786  * the path head with new entry (sig, alt_hash, new_idx)
 787  * return 1 if matched key found, return -1 if cuckoo path invalided and fail,
 788  * return 0 if succeeds.
 789  */
 790 static inline int
 791 rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,
 792                         struct rte_hash_bucket *bkt,
 793                         struct rte_hash_bucket *alt_bkt,
 794                         const struct rte_hash_key *key, void *data,
 795                         struct queue_node *leaf, uint32_t leaf_slot,
 796                         uint16_t sig, uint32_t new_idx,
 797                         int32_t *ret_val)
 798 {
 799         uint32_t prev_alt_bkt_idx;
 800         struct rte_hash_bucket *cur_bkt;
 801         struct queue_node *prev_node, *curr_node = leaf;
 802         struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
 803         uint32_t prev_slot, curr_slot = leaf_slot;
 804         int32_t ret;
 805
 806         __hash_rw_writer_lock(h);
 807
 808         /* In case empty slot was gone before entering protected region */
 809         if (curr_bkt->key_idx[curr_slot] != EMPTY_SLOT) {
 810                 __hash_rw_writer_unlock(h);
 811                 return -1;
 812         }
 813
 814         /* Check if key was inserted after last check but before this
 815          * protected region.
 816          */
 817         ret = search_and_update(h, data, key, bkt, sig);
 818         if (ret != -1) {
 819                 __hash_rw_writer_unlock(h);
 820                 *ret_val = ret;
 821                 return 1;
 822         }
 823
 824         FOR_EACH_BUCKET(cur_bkt, alt_bkt) {
 825                 ret = search_and_update(h, data, key, cur_bkt, sig);
 826                 if (ret != -1) {
 827                         __hash_rw_writer_unlock(h);
 828                         *ret_val = ret;
 829                         return 1;
 830                 }
 831         }
 832
 833         while (likely(curr_node->prev != NULL)) {
 834                 prev_node = curr_node->prev;
 835                 prev_bkt = prev_node->bkt;
 836                 prev_slot = curr_node->prev_slot;
 837
 838                 prev_alt_bkt_idx = get_alt_bucket_index(h,
 839                                         prev_node->cur_bkt_idx,
 840                                         prev_bkt->sig_current[prev_slot]);
 841
 842                 if (unlikely(&h->buckets[prev_alt_bkt_idx]
 843                                 != curr_bkt)) {
 844                         /* revert it to empty, otherwise duplicated keys */
 845                         __atomic_store_n(&curr_bkt->key_idx[curr_slot],
 846                                 EMPTY_SLOT,
 847                                 __ATOMIC_RELEASE);
 848                         __hash_rw_writer_unlock(h);
 849                         return -1;
 850                 }
 851
 852                 if (h->readwrite_concur_lf_support) {
 853                         /* Inform the previous move. The current move need
 854                          * not be informed now as the current bucket entry
 855                          * is present in both primary and secondary.
 856                          * Since there is one writer, load acquires on
 857                          * tbl_chng_cnt are not required.
 858                          */
 859                         __atomic_store_n(h->tbl_chng_cnt,
 860                                          *h->tbl_chng_cnt + 1,
 861                                          __ATOMIC_RELEASE);
 862                         /* The store to sig_current should not
 863                          * move above the store to tbl_chng_cnt.
 864                          */
 865                         __atomic_thread_fence(__ATOMIC_RELEASE);
 866                 }
 867
 868                 /* Need to swap current/alt sig to allow later
 869                  * Cuckoo insert to move elements back to its
 870                  * primary bucket if available
 871                  */
 872                 curr_bkt->sig_current[curr_slot] =
 873                         prev_bkt->sig_current[prev_slot];
 874                 /* Release the updated bucket entry */
 875                 __atomic_store_n(&curr_bkt->key_idx[curr_slot],
 876                         prev_bkt->key_idx[prev_slot],
 877                         __ATOMIC_RELEASE);
 878
 879                 curr_slot = prev_slot;
 880                 curr_node = prev_node;
 881                 curr_bkt = curr_node->bkt;
 882         }
 883
 884         if (h->readwrite_concur_lf_support) {
 885                 /* Inform the previous move. The current move need
 886                  * not be informed now as the current bucket entry
 887                  * is present in both primary and secondary.
 888                  * Since there is one writer, load acquires on
 889                  * tbl_chng_cnt are not required.
 890                  */
 891                 __atomic_store_n(h->tbl_chng_cnt,
 892                                  *h->tbl_chng_cnt + 1,
 893                                  __ATOMIC_RELEASE);
 894                 /* The store to sig_current should not
 895                  * move above the store to tbl_chng_cnt.
 896                  */
 897                 __atomic_thread_fence(__ATOMIC_RELEASE);
 898         }
 899
 900         curr_bkt->sig_current[curr_slot] = sig;
 901         /* Release the new bucket entry */
 902         __atomic_store_n(&curr_bkt->key_idx[curr_slot],
 903                          new_idx,
 904                          __ATOMIC_RELEASE);
 905
 906         __hash_rw_writer_unlock(h);
 907
 908         return 0;
 909
 910 }
 911
 912 /*
 913  * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
 914  * Cuckoo
 915  */
 916 static inline int
 917 rte_hash_cuckoo_make_space_mw(const struct rte_hash *h,
 918                         struct rte_hash_bucket *bkt,
 919                         struct rte_hash_bucket *sec_bkt,
 920                         const struct rte_hash_key *key, void *data,
 921                         uint16_t sig, uint32_t bucket_idx,
 922                         uint32_t new_idx, int32_t *ret_val)
 923 {
 924         unsigned int i;
 925         struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
 926         struct queue_node *tail, *head;
 927         struct rte_hash_bucket *curr_bkt, *alt_bkt;
 928         uint32_t cur_idx, alt_idx;
 929
 930         tail = queue;
 931         head = queue + 1;
 932         tail->bkt = bkt;
 933         tail->prev = NULL;
 934         tail->prev_slot = -1;
 935         tail->cur_bkt_idx = bucket_idx;
 936
 937         /* Cuckoo bfs Search */
 938         while (likely(tail != head && head <
 939                                         queue + RTE_HASH_BFS_QUEUE_MAX_LEN -
 940                                         RTE_HASH_BUCKET_ENTRIES)) {
 941                 curr_bkt = tail->bkt;
 942                 cur_idx = tail->cur_bkt_idx;
 943                 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 944                         if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
 945                                 int32_t ret = rte_hash_cuckoo_move_insert_mw(h,
 946                                                 bkt, sec_bkt, key, data,
 947                                                 tail, i, sig,
 948                                                 new_idx, ret_val);
 949                                 if (likely(ret != -1))
 950                                         return ret;
 951                         }
 952
 953                         /* Enqueue new node and keep prev node info */
 954                         alt_idx = get_alt_bucket_index(h, cur_idx,
 955                                                 curr_bkt->sig_current[i]);
 956                         alt_bkt = &(h->buckets[alt_idx]);
 957                         head->bkt = alt_bkt;
 958                         head->cur_bkt_idx = alt_idx;
 959                         head->prev = tail;
 960                         head->prev_slot = i;
 961                         head++;
 962                 }
 963                 tail++;
 964         }
 965
 966         return -ENOSPC;
 967 }
 968
 969 static inline uint32_t
 970 alloc_slot(const struct rte_hash *h, struct lcore_cache *cached_free_slots)
 971 {
 972         unsigned int n_slots;
 973         uint32_t slot_id;
 974
 975         if (h->use_local_cache) {
 976                 /* Try to get a free slot from the local cache */
 977                 if (cached_free_slots->len == 0) {
 978                         /* Need to get another burst of free slots from global ring */
 979                         n_slots = rte_ring_mc_dequeue_burst_elem(h->free_slots,
 980                                         cached_free_slots->objs,
 981                                         sizeof(uint32_t),
 982                                         LCORE_CACHE_SIZE, NULL);
 983                         if (n_slots == 0)
 984                                 return EMPTY_SLOT;
 985
 986                         cached_free_slots->len += n_slots;
 987                 }
 988
 989                 /* Get a free slot from the local cache */
 990                 cached_free_slots->len--;
 991                 slot_id = cached_free_slots->objs[cached_free_slots->len];
 992         } else {
 993                 if (rte_ring_sc_dequeue_elem(h->free_slots, &slot_id,
 994                                                 sizeof(uint32_t)) != 0)
 995                         return EMPTY_SLOT;
 996         }
 997
 998         return slot_id;
 999 }
1000
1001 static inline int32_t
1002 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
1003                                                 hash_sig_t sig, void *data)
1004 {
1005         uint16_t short_sig;
1006         uint32_t prim_bucket_idx, sec_bucket_idx;
1007         struct rte_hash_bucket *prim_bkt, *sec_bkt, *cur_bkt;
1008         struct rte_hash_key *new_k, *keys = h->key_store;
1009         uint32_t ext_bkt_id = 0;
1010         uint32_t slot_id;
1011         int ret;
1012         unsigned lcore_id;
1013         unsigned int i;
1014         struct lcore_cache *cached_free_slots = NULL;
1015         int32_t ret_val;
1016         struct rte_hash_bucket *last;
1017
1018         short_sig = get_short_sig(sig);
1019         prim_bucket_idx = get_prim_bucket_index(h, sig);
1020         sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1021         prim_bkt = &h->buckets[prim_bucket_idx];
1022         sec_bkt = &h->buckets[sec_bucket_idx];
1023         rte_prefetch0(prim_bkt);
1024         rte_prefetch0(sec_bkt);
1025
1026         /* Check if key is already inserted in primary location */
1027         __hash_rw_writer_lock(h);
1028         ret = search_and_update(h, data, key, prim_bkt, short_sig);
1029         if (ret != -1) {
1030                 __hash_rw_writer_unlock(h);
1031                 return ret;
1032         }
1033
1034         /* Check if key is already inserted in secondary location */
1035         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1036                 ret = search_and_update(h, data, key, cur_bkt, short_sig);
1037                 if (ret != -1) {
1038                         __hash_rw_writer_unlock(h);
1039                         return ret;
1040                 }
1041         }
1042
1043         __hash_rw_writer_unlock(h);
1044
1045         /* Did not find a match, so get a new slot for storing the new key */
1046         if (h->use_local_cache) {
1047                 lcore_id = rte_lcore_id();
1048                 cached_free_slots = &h->local_free_slots[lcore_id];
1049         }
1050         slot_id = alloc_slot(h, cached_free_slots);
1051         if (slot_id == EMPTY_SLOT) {
1052                 if (h->dq) {
1053                         __hash_rw_writer_lock(h);
1054                         ret = rte_rcu_qsbr_dq_reclaim(h->dq,
1055                                         h->hash_rcu_cfg->max_reclaim_size,
1056                                         NULL, NULL, NULL);
1057                         __hash_rw_writer_unlock(h);
1058                         if (ret == 0)
1059                                 slot_id = alloc_slot(h, cached_free_slots);
1060                 }
1061                 if (slot_id == EMPTY_SLOT)
1062                         return -ENOSPC;
1063         }
1064
1065         new_k = RTE_PTR_ADD(keys, slot_id * h->key_entry_size);
1066         /* The store to application data (by the application) at *data should
1067          * not leak after the store of pdata in the key store. i.e. pdata is
1068          * the guard variable. Release the application data to the readers.
1069          */
1070         __atomic_store_n(&new_k->pdata,
1071                 data,
1072                 __ATOMIC_RELEASE);
1073         /* Copy key */
1074         memcpy(new_k->key, key, h->key_len);
1075
1076         /* Find an empty slot and insert */
1077         ret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data,
1078                                         short_sig, slot_id, &ret_val);
1079         if (ret == 0)
1080                 return slot_id - 1;
1081         else if (ret == 1) {
1082                 enqueue_slot_back(h, cached_free_slots, slot_id);
1083                 return ret_val;
1084         }
1085
1086         /* Primary bucket full, need to make space for new entry */
1087         ret = rte_hash_cuckoo_make_space_mw(h, prim_bkt, sec_bkt, key, data,
1088                                 short_sig, prim_bucket_idx, slot_id, &ret_val);
1089         if (ret == 0)
1090                 return slot_id - 1;
1091         else if (ret == 1) {
1092                 enqueue_slot_back(h, cached_free_slots, slot_id);
1093                 return ret_val;
1094         }
1095
1096         /* Also search secondary bucket to get better occupancy */
1097         ret = rte_hash_cuckoo_make_space_mw(h, sec_bkt, prim_bkt, key, data,
1098                                 short_sig, sec_bucket_idx, slot_id, &ret_val);
1099
1100         if (ret == 0)
1101                 return slot_id - 1;
1102         else if (ret == 1) {
1103                 enqueue_slot_back(h, cached_free_slots, slot_id);
1104                 return ret_val;
1105         }
1106
1107         /* if ext table not enabled, we failed the insertion */
1108         if (!h->ext_table_support) {
1109                 enqueue_slot_back(h, cached_free_slots, slot_id);
1110                 return ret;
1111         }
1112
1113         /* Now we need to go through the extendable bucket. Protection is needed
1114          * to protect all extendable bucket processes.
1115          */
1116         __hash_rw_writer_lock(h);
1117         /* We check for duplicates again since could be inserted before the lock */
1118         ret = search_and_update(h, data, key, prim_bkt, short_sig);
1119         if (ret != -1) {
1120                 enqueue_slot_back(h, cached_free_slots, slot_id);
1121                 goto failure;
1122         }
1123
1124         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1125                 ret = search_and_update(h, data, key, cur_bkt, short_sig);
1126                 if (ret != -1) {
1127                         enqueue_slot_back(h, cached_free_slots, slot_id);
1128                         goto failure;
1129                 }
1130         }
1131
1132         /* Search sec and ext buckets to find an empty entry to insert. */
1133         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1134                 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1135                         /* Check if slot is available */
1136                         if (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {
1137                                 cur_bkt->sig_current[i] = short_sig;
1138                                 /* Store to signature and key should not
1139                                  * leak after the store to key_idx. i.e.
1140                                  * key_idx is the guard variable for signature
1141                                  * and key.
1142                                  */
1143                                 __atomic_store_n(&cur_bkt->key_idx[i],
1144                                                  slot_id,
1145                                                  __ATOMIC_RELEASE);
1146                                 __hash_rw_writer_unlock(h);
1147                                 return slot_id - 1;
1148                         }
1149                 }
1150         }
1151
1152         /* Failed to get an empty entry from extendable buckets. Link a new
1153          * extendable bucket. We first get a free bucket from ring.
1154          */
1155         if (rte_ring_sc_dequeue_elem(h->free_ext_bkts, &ext_bkt_id,
1156                                                 sizeof(uint32_t)) != 0 ||
1157                                         ext_bkt_id == 0) {
1158                 if (h->dq) {
1159                         if (rte_rcu_qsbr_dq_reclaim(h->dq,
1160                                         h->hash_rcu_cfg->max_reclaim_size,
1161                                         NULL, NULL, NULL) == 0) {
1162                                 rte_ring_sc_dequeue_elem(h->free_ext_bkts,
1163                                                          &ext_bkt_id,
1164                                                          sizeof(uint32_t));
1165                         }
1166                 }
1167                 if (ext_bkt_id == 0) {
1168                         ret = -ENOSPC;
1169                         goto failure;
1170                 }
1171         }
1172
1173         /* Use the first location of the new bucket */
1174         (h->buckets_ext[ext_bkt_id - 1]).sig_current[0] = short_sig;
1175         /* Store to signature and key should not leak after
1176          * the store to key_idx. i.e. key_idx is the guard variable
1177          * for signature and key.
1178          */
1179         __atomic_store_n(&(h->buckets_ext[ext_bkt_id - 1]).key_idx[0],
1180                          slot_id,
1181                          __ATOMIC_RELEASE);
1182         /* Link the new bucket to sec bucket linked list */
1183         last = rte_hash_get_last_bkt(sec_bkt);
1184         last->next = &h->buckets_ext[ext_bkt_id - 1];
1185         __hash_rw_writer_unlock(h);
1186         return slot_id - 1;
1187
1188 failure:
1189         __hash_rw_writer_unlock(h);
1190         return ret;
1191
1192 }
1193
1194 int32_t
1195 rte_hash_add_key_with_hash(const struct rte_hash *h,
1196                         const void *key, hash_sig_t sig)
1197 {
1198         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1199         return __rte_hash_add_key_with_hash(h, key, sig, 0);
1200 }
1201
1202 int32_t
1203 rte_hash_add_key(const struct rte_hash *h, const void *key)
1204 {
1205         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1206         return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
1207 }
1208
1209 int
1210 rte_hash_add_key_with_hash_data(const struct rte_hash *h,
1211                         const void *key, hash_sig_t sig, void *data)
1212 {
1213         int ret;
1214
1215         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1216         ret = __rte_hash_add_key_with_hash(h, key, sig, data);
1217         if (ret >= 0)
1218                 return 0;
1219         else
1220                 return ret;
1221 }
1222
1223 int
1224 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)
1225 {
1226         int ret;
1227
1228         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1229
1230         ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data);
1231         if (ret >= 0)
1232                 return 0;
1233         else
1234                 return ret;
1235 }
1236
1237 /* Search one bucket to find the match key - uses rw lock */
1238 static inline int32_t
1239 search_one_bucket_l(const struct rte_hash *h, const void *key,
1240                 uint16_t sig, void **data,
1241                 const struct rte_hash_bucket *bkt)
1242 {
1243         int i;
1244         struct rte_hash_key *k, *keys = h->key_store;
1245
1246         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1247                 if (bkt->sig_current[i] == sig &&
1248                                 bkt->key_idx[i] != EMPTY_SLOT) {
1249                         k = (struct rte_hash_key *) ((char *)keys +
1250                                         bkt->key_idx[i] * h->key_entry_size);
1251
1252                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1253                                 if (data != NULL)
1254                                         *data = k->pdata;
1255                                 /*
1256                                  * Return index where key is stored,
1257                                  * subtracting the first dummy index
1258                                  */
1259                                 return bkt->key_idx[i] - 1;
1260                         }
1261                 }
1262         }
1263         return -1;
1264 }
1265
1266 /* Search one bucket to find the match key */
1267 static inline int32_t
1268 search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig,
1269                         void **data, const struct rte_hash_bucket *bkt)
1270 {
1271         int i;
1272         uint32_t key_idx;
1273         struct rte_hash_key *k, *keys = h->key_store;
1274
1275         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1276                 /* Signature comparison is done before the acquire-load
1277                  * of the key index to achieve better performance.
1278                  * This can result in the reader loading old signature
1279                  * (which matches), while the key_idx is updated to a
1280                  * value that belongs to a new key. However, the full
1281                  * key comparison will ensure that the lookup fails.
1282                  */
1283                 if (bkt->sig_current[i] == sig) {
1284                         key_idx = __atomic_load_n(&bkt->key_idx[i],
1285                                           __ATOMIC_ACQUIRE);
1286                         if (key_idx != EMPTY_SLOT) {
1287                                 k = (struct rte_hash_key *) ((char *)keys +
1288                                                 key_idx * h->key_entry_size);
1289
1290                                 if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1291                                         if (data != NULL) {
1292                                                 *data = __atomic_load_n(
1293                                                         &k->pdata,
1294                                                         __ATOMIC_ACQUIRE);
1295                                         }
1296                                         /*
1297                                          * Return index where key is stored,
1298                                          * subtracting the first dummy index
1299                                          */
1300                                         return key_idx - 1;
1301                                 }
1302                         }
1303                 }
1304         }
1305         return -1;
1306 }
1307
1308 static inline int32_t
1309 __rte_hash_lookup_with_hash_l(const struct rte_hash *h, const void *key,
1310                                 hash_sig_t sig, void **data)
1311 {
1312         uint32_t prim_bucket_idx, sec_bucket_idx;
1313         struct rte_hash_bucket *bkt, *cur_bkt;
1314         int ret;
1315         uint16_t short_sig;
1316
1317         short_sig = get_short_sig(sig);
1318         prim_bucket_idx = get_prim_bucket_index(h, sig);
1319         sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1320
1321         bkt = &h->buckets[prim_bucket_idx];
1322
1323         __hash_rw_reader_lock(h);
1324
1325         /* Check if key is in primary location */
1326         ret = search_one_bucket_l(h, key, short_sig, data, bkt);
1327         if (ret != -1) {
1328                 __hash_rw_reader_unlock(h);
1329                 return ret;
1330         }
1331         /* Calculate secondary hash */
1332         bkt = &h->buckets[sec_bucket_idx];
1333
1334         /* Check if key is in secondary location */
1335         FOR_EACH_BUCKET(cur_bkt, bkt) {
1336                 ret = search_one_bucket_l(h, key, short_sig,
1337                                         data, cur_bkt);
1338                 if (ret != -1) {
1339                         __hash_rw_reader_unlock(h);
1340                         return ret;
1341                 }
1342         }
1343
1344         __hash_rw_reader_unlock(h);
1345
1346         return -ENOENT;
1347 }
1348
1349 static inline int32_t
1350 __rte_hash_lookup_with_hash_lf(const struct rte_hash *h, const void *key,
1351                                         hash_sig_t sig, void **data)
1352 {
1353         uint32_t prim_bucket_idx, sec_bucket_idx;
1354         struct rte_hash_bucket *bkt, *cur_bkt;
1355         uint32_t cnt_b, cnt_a;
1356         int ret;
1357         uint16_t short_sig;
1358
1359         short_sig = get_short_sig(sig);
1360         prim_bucket_idx = get_prim_bucket_index(h, sig);
1361         sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1362
1363         do {
1364                 /* Load the table change counter before the lookup
1365                  * starts. Acquire semantics will make sure that
1366                  * loads in search_one_bucket are not hoisted.
1367                  */
1368                 cnt_b = __atomic_load_n(h->tbl_chng_cnt,
1369                                 __ATOMIC_ACQUIRE);
1370
1371                 /* Check if key is in primary location */
1372                 bkt = &h->buckets[prim_bucket_idx];
1373                 ret = search_one_bucket_lf(h, key, short_sig, data, bkt);
1374                 if (ret != -1)
1375                         return ret;
1376                 /* Calculate secondary hash */
1377                 bkt = &h->buckets[sec_bucket_idx];
1378
1379                 /* Check if key is in secondary location */
1380                 FOR_EACH_BUCKET(cur_bkt, bkt) {
1381                         ret = search_one_bucket_lf(h, key, short_sig,
1382                                                 data, cur_bkt);
1383                         if (ret != -1)
1384                                 return ret;
1385                 }
1386
1387                 /* The loads of sig_current in search_one_bucket
1388                  * should not move below the load from tbl_chng_cnt.
1389                  */
1390                 __atomic_thread_fence(__ATOMIC_ACQUIRE);
1391                 /* Re-read the table change counter to check if the
1392                  * table has changed during search. If yes, re-do
1393                  * the search.
1394                  * This load should not get hoisted. The load
1395                  * acquires on cnt_b, key index in primary bucket
1396                  * and key index in secondary bucket will make sure
1397                  * that it does not get hoisted.
1398                  */
1399                 cnt_a = __atomic_load_n(h->tbl_chng_cnt,
1400                                         __ATOMIC_ACQUIRE);
1401         } while (cnt_b != cnt_a);
1402
1403         return -ENOENT;
1404 }
1405
1406 static inline int32_t
1407 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
1408                                         hash_sig_t sig, void **data)
1409 {
1410         if (h->readwrite_concur_lf_support)
1411                 return __rte_hash_lookup_with_hash_lf(h, key, sig, data);
1412         else
1413                 return __rte_hash_lookup_with_hash_l(h, key, sig, data);
1414 }
1415
1416 int32_t
1417 rte_hash_lookup_with_hash(const struct rte_hash *h,
1418                         const void *key, hash_sig_t sig)
1419 {
1420         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1421         return __rte_hash_lookup_with_hash(h, key, sig, NULL);
1422 }
1423
1424 int32_t
1425 rte_hash_lookup(const struct rte_hash *h, const void *key)
1426 {
1427         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1428         return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
1429 }
1430
1431 int
1432 rte_hash_lookup_with_hash_data(const struct rte_hash *h,
1433                         const void *key, hash_sig_t sig, void **data)
1434 {
1435         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1436         return __rte_hash_lookup_with_hash(h, key, sig, data);
1437 }
1438
1439 int
1440 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)
1441 {
1442         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1443         return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
1444 }
1445
1446 static int
1447 free_slot(const struct rte_hash *h, uint32_t slot_id)
1448 {
1449         unsigned lcore_id, n_slots;
1450         struct lcore_cache *cached_free_slots = NULL;
1451
1452         /* Return key indexes to free slot ring */
1453         if (h->use_local_cache) {
1454                 lcore_id = rte_lcore_id();
1455                 cached_free_slots = &h->local_free_slots[lcore_id];
1456                 /* Cache full, need to free it. */
1457                 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
1458                         /* Need to enqueue the free slots in global ring. */
1459                         n_slots = rte_ring_mp_enqueue_burst_elem(h->free_slots,
1460                                                 cached_free_slots->objs,
1461                                                 sizeof(uint32_t),
1462                                                 LCORE_CACHE_SIZE, NULL);
1463                         RETURN_IF_TRUE((n_slots == 0), -EFAULT);
1464                         cached_free_slots->len -= n_slots;
1465                 }
1466         }
1467
1468         enqueue_slot_back(h, cached_free_slots, slot_id);
1469         return 0;
1470 }
1471
1472 static void
1473 __hash_rcu_qsbr_free_resource(void *p, void *e, unsigned int n)
1474 {
1475         void *key_data = NULL;
1476         int ret;
1477         struct rte_hash_key *keys, *k;
1478         struct rte_hash *h = (struct rte_hash *)p;
1479         struct __rte_hash_rcu_dq_entry rcu_dq_entry =
1480                         *((struct __rte_hash_rcu_dq_entry *)e);
1481
1482         RTE_SET_USED(n);
1483         keys = h->key_store;
1484
1485         k = (struct rte_hash_key *) ((char *)keys +
1486                                 rcu_dq_entry.key_idx * h->key_entry_size);
1487         key_data = k->pdata;
1488         if (h->hash_rcu_cfg->free_key_data_func)
1489                 h->hash_rcu_cfg->free_key_data_func(h->hash_rcu_cfg->key_data_ptr,
1490                                                     key_data);
1491
1492         if (h->ext_table_support && rcu_dq_entry.ext_bkt_idx != EMPTY_SLOT)
1493                 /* Recycle empty ext bkt to free list. */
1494                 rte_ring_sp_enqueue_elem(h->free_ext_bkts,
1495                         &rcu_dq_entry.ext_bkt_idx, sizeof(uint32_t));
1496
1497         /* Return key indexes to free slot ring */
1498         ret = free_slot(h, rcu_dq_entry.key_idx);
1499         if (ret < 0) {
1500                 RTE_LOG(ERR, HASH,
1501                         "%s: could not enqueue free slots in global ring\n",
1502                                 __func__);
1503         }
1504 }
1505
1506 int
1507 rte_hash_rcu_qsbr_add(struct rte_hash *h, struct rte_hash_rcu_config *cfg)
1508 {
1509         struct rte_rcu_qsbr_dq_parameters params = {0};
1510         char rcu_dq_name[RTE_RCU_QSBR_DQ_NAMESIZE];
1511         struct rte_hash_rcu_config *hash_rcu_cfg = NULL;
1512
1513         if (h == NULL || cfg == NULL || cfg->v == NULL) {
1514                 rte_errno = EINVAL;
1515                 return 1;
1516         }
1517
1518         const uint32_t total_entries = h->use_local_cache ?
1519                 h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1
1520                                                         : h->entries + 1;
1521
1522         if (h->hash_rcu_cfg) {
1523                 rte_errno = EEXIST;
1524                 return 1;
1525         }
1526
1527         hash_rcu_cfg = rte_zmalloc(NULL, sizeof(struct rte_hash_rcu_config), 0);
1528         if (hash_rcu_cfg == NULL) {
1529                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
1530                 return 1;
1531         }
1532
1533         if (cfg->mode == RTE_HASH_QSBR_MODE_SYNC) {
1534                 /* No other things to do. */
1535         } else if (cfg->mode == RTE_HASH_QSBR_MODE_DQ) {
1536                 /* Init QSBR defer queue. */
1537                 snprintf(rcu_dq_name, sizeof(rcu_dq_name),
1538                                         "HASH_RCU_%s", h->name);
1539                 params.name = rcu_dq_name;
1540                 params.size = cfg->dq_size;
1541                 if (params.size == 0)
1542                         params.size = total_entries;
1543                 params.trigger_reclaim_limit = cfg->trigger_reclaim_limit;
1544                 if (params.max_reclaim_size == 0)
1545                         params.max_reclaim_size = RTE_HASH_RCU_DQ_RECLAIM_MAX;
1546                 params.esize = sizeof(struct __rte_hash_rcu_dq_entry);
1547                 params.free_fn = __hash_rcu_qsbr_free_resource;
1548                 params.p = h;
1549                 params.v = cfg->v;
1550                 h->dq = rte_rcu_qsbr_dq_create(&params);
1551                 if (h->dq == NULL) {
1552                         rte_free(hash_rcu_cfg);
1553                         RTE_LOG(ERR, HASH, "HASH defer queue creation failed\n");
1554                         return 1;
1555                 }
1556         } else {
1557                 rte_free(hash_rcu_cfg);
1558                 rte_errno = EINVAL;
1559                 return 1;
1560         }
1561
1562         hash_rcu_cfg->v = cfg->v;
1563         hash_rcu_cfg->mode = cfg->mode;
1564         hash_rcu_cfg->dq_size = params.size;
1565         hash_rcu_cfg->trigger_reclaim_limit = params.trigger_reclaim_limit;
1566         hash_rcu_cfg->max_reclaim_size = params.max_reclaim_size;
1567         hash_rcu_cfg->free_key_data_func = cfg->free_key_data_func;
1568         hash_rcu_cfg->key_data_ptr = cfg->key_data_ptr;
1569
1570         h->hash_rcu_cfg = hash_rcu_cfg;
1571
1572         return 0;
1573 }
1574
1575 static inline void
1576 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt,
1577                 unsigned int i)
1578 {
1579         int ret = free_slot(h, bkt->key_idx[i]);
1580
1581         if (ret < 0) {
1582                 RTE_LOG(ERR, HASH,
1583                         "%s: could not enqueue free slots in global ring\n",
1584                                 __func__);
1585         }
1586 }
1587
1588 /* Compact the linked list by moving key from last entry in linked list to the
1589  * empty slot.
1590  */
1591 static inline void
1592 __rte_hash_compact_ll(const struct rte_hash *h,
1593                         struct rte_hash_bucket *cur_bkt, int pos) {
1594         int i;
1595         struct rte_hash_bucket *last_bkt;
1596
1597         if (!cur_bkt->next)
1598                 return;
1599
1600         last_bkt = rte_hash_get_last_bkt(cur_bkt);
1601
1602         for (i = RTE_HASH_BUCKET_ENTRIES - 1; i >= 0; i--) {
1603                 if (last_bkt->key_idx[i] != EMPTY_SLOT) {
1604                         cur_bkt->sig_current[pos] = last_bkt->sig_current[i];
1605                         __atomic_store_n(&cur_bkt->key_idx[pos],
1606                                          last_bkt->key_idx[i],
1607                                          __ATOMIC_RELEASE);
1608                         if (h->readwrite_concur_lf_support) {
1609                                 /* Inform the readers that the table has changed
1610                                  * Since there is one writer, load acquire on
1611                                  * tbl_chng_cnt is not required.
1612                                  */
1613                                 __atomic_store_n(h->tbl_chng_cnt,
1614                                          *h->tbl_chng_cnt + 1,
1615                                          __ATOMIC_RELEASE);
1616                                 /* The store to sig_current should
1617                                  * not move above the store to tbl_chng_cnt.
1618                                  */
1619                                 __atomic_thread_fence(__ATOMIC_RELEASE);
1620                         }
1621                         last_bkt->sig_current[i] = NULL_SIGNATURE;
1622                         __atomic_store_n(&last_bkt->key_idx[i],
1623                                          EMPTY_SLOT,
1624                                          __ATOMIC_RELEASE);
1625                         return;
1626                 }
1627         }
1628 }
1629
1630 /* Search one bucket and remove the matched key.
1631  * Writer is expected to hold the lock while calling this
1632  * function.
1633  */
1634 static inline int32_t
1635 search_and_remove(const struct rte_hash *h, const void *key,
1636                         struct rte_hash_bucket *bkt, uint16_t sig, int *pos)
1637 {
1638         struct rte_hash_key *k, *keys = h->key_store;
1639         unsigned int i;
1640         uint32_t key_idx;
1641
1642         /* Check if key is in bucket */
1643         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1644                 key_idx = __atomic_load_n(&bkt->key_idx[i],
1645                                           __ATOMIC_ACQUIRE);
1646                 if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {
1647                         k = (struct rte_hash_key *) ((char *)keys +
1648                                         key_idx * h->key_entry_size);
1649                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1650                                 bkt->sig_current[i] = NULL_SIGNATURE;
1651                                 /* Free the key store index if
1652                                  * no_free_on_del is disabled.
1653                                  */
1654                                 if (!h->no_free_on_del)
1655                                         remove_entry(h, bkt, i);
1656
1657                                 __atomic_store_n(&bkt->key_idx[i],
1658                                                  EMPTY_SLOT,
1659                                                  __ATOMIC_RELEASE);
1660
1661                                 *pos = i;
1662                                 /*
1663                                  * Return index where key is stored,
1664                                  * subtracting the first dummy index
1665                                  */
1666                                 return key_idx - 1;
1667                         }
1668                 }
1669         }
1670         return -1;
1671 }
1672
1673 static inline int32_t
1674 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
1675                                                 hash_sig_t sig)
1676 {
1677         uint32_t prim_bucket_idx, sec_bucket_idx;
1678         struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt;
1679         struct rte_hash_bucket *cur_bkt;
1680         int pos;
1681         int32_t ret, i;
1682         uint16_t short_sig;
1683         uint32_t index = EMPTY_SLOT;
1684         struct __rte_hash_rcu_dq_entry rcu_dq_entry;
1685
1686         short_sig = get_short_sig(sig);
1687         prim_bucket_idx = get_prim_bucket_index(h, sig);
1688         sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1689         prim_bkt = &h->buckets[prim_bucket_idx];
1690
1691         __hash_rw_writer_lock(h);
1692         /* look for key in primary bucket */
1693         ret = search_and_remove(h, key, prim_bkt, short_sig, &pos);
1694         if (ret != -1) {
1695                 __rte_hash_compact_ll(h, prim_bkt, pos);
1696                 last_bkt = prim_bkt->next;
1697                 prev_bkt = prim_bkt;
1698                 goto return_bkt;
1699         }
1700
1701         /* Calculate secondary hash */
1702         sec_bkt = &h->buckets[sec_bucket_idx];
1703
1704         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1705                 ret = search_and_remove(h, key, cur_bkt, short_sig, &pos);
1706                 if (ret != -1) {
1707                         __rte_hash_compact_ll(h, cur_bkt, pos);
1708                         last_bkt = sec_bkt->next;
1709                         prev_bkt = sec_bkt;
1710                         goto return_bkt;
1711                 }
1712         }
1713
1714         __hash_rw_writer_unlock(h);
1715         return -ENOENT;
1716
1717 /* Search last bucket to see if empty to be recycled */
1718 return_bkt:
1719         if (!last_bkt)
1720                 goto return_key;
1721
1722         while (last_bkt->next) {
1723                 prev_bkt = last_bkt;
1724                 last_bkt = last_bkt->next;
1725         }
1726
1727         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1728                 if (last_bkt->key_idx[i] != EMPTY_SLOT)
1729                         break;
1730         }
1731         /* found empty bucket and recycle */
1732         if (i == RTE_HASH_BUCKET_ENTRIES) {
1733                 prev_bkt->next = NULL;
1734                 index = last_bkt - h->buckets_ext + 1;
1735                 /* Recycle the empty bkt if
1736                  * no_free_on_del is disabled.
1737                  */
1738                 if (h->no_free_on_del) {
1739                         /* Store index of an empty ext bkt to be recycled
1740                          * on calling rte_hash_del_xxx APIs.
1741                          * When lock free read-write concurrency is enabled,
1742                          * an empty ext bkt cannot be put into free list
1743                          * immediately (as readers might be using it still).
1744                          * Hence freeing of the ext bkt is piggy-backed to
1745                          * freeing of the key index.
1746                          * If using external RCU, store this index in an array.
1747                          */
1748                         if (h->hash_rcu_cfg == NULL)
1749                                 h->ext_bkt_to_free[ret] = index;
1750                 } else
1751                         rte_ring_sp_enqueue_elem(h->free_ext_bkts, &index,
1752                                                         sizeof(uint32_t));
1753         }
1754
1755 return_key:
1756         /* Using internal RCU QSBR */
1757         if (h->hash_rcu_cfg) {
1758                 /* Key index where key is stored, adding the first dummy index */
1759                 rcu_dq_entry.key_idx = ret + 1;
1760                 rcu_dq_entry.ext_bkt_idx = index;
1761                 if (h->dq == NULL) {
1762                         /* Wait for quiescent state change if using
1763                          * RTE_HASH_QSBR_MODE_SYNC
1764                          */
1765                         rte_rcu_qsbr_synchronize(h->hash_rcu_cfg->v,
1766                                                  RTE_QSBR_THRID_INVALID);
1767                         __hash_rcu_qsbr_free_resource((void *)((uintptr_t)h),
1768                                                       &rcu_dq_entry, 1);
1769                 } else if (h->dq)
1770                         /* Push into QSBR FIFO if using RTE_HASH_QSBR_MODE_DQ */
1771                         if (rte_rcu_qsbr_dq_enqueue(h->dq, &rcu_dq_entry) != 0)
1772                                 RTE_LOG(ERR, HASH, "Failed to push QSBR FIFO\n");
1773         }
1774         __hash_rw_writer_unlock(h);
1775         return ret;
1776 }
1777
1778 int32_t
1779 rte_hash_del_key_with_hash(const struct rte_hash *h,
1780                         const void *key, hash_sig_t sig)
1781 {
1782         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1783         return __rte_hash_del_key_with_hash(h, key, sig);
1784 }
1785
1786 int32_t
1787 rte_hash_del_key(const struct rte_hash *h, const void *key)
1788 {
1789         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1790         return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
1791 }
1792
1793 int
1794 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
1795                                void **key)
1796 {
1797         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1798
1799         struct rte_hash_key *k, *keys = h->key_store;
1800         k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
1801                                      h->key_entry_size);
1802         *key = k->key;
1803
1804         if (position !=
1805             __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
1806                                         NULL)) {
1807                 return -ENOENT;
1808         }
1809
1810         return 0;
1811 }
1812
1813 int
1814 rte_hash_free_key_with_position(const struct rte_hash *h,
1815                                 const int32_t position)
1816 {
1817         /* Key index where key is stored, adding the first dummy index */
1818         uint32_t key_idx = position + 1;
1819
1820         RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
1821
1822         const uint32_t total_entries = h->use_local_cache ?
1823                 h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1
1824                                                         : h->entries + 1;
1825
1826         /* Out of bounds */
1827         if (key_idx >= total_entries)
1828                 return -EINVAL;
1829         if (h->ext_table_support && h->readwrite_concur_lf_support) {
1830                 uint32_t index = h->ext_bkt_to_free[position];
1831                 if (index) {
1832                         /* Recycle empty ext bkt to free list. */
1833                         rte_ring_sp_enqueue_elem(h->free_ext_bkts, &index,
1834                                                         sizeof(uint32_t));
1835                         h->ext_bkt_to_free[position] = 0;
1836                 }
1837         }
1838
1839         /* Enqueue slot to cache/ring of free slots. */
1840         return free_slot(h, key_idx);
1841
1842 }
1843
1844 static inline void
1845 compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
1846                         const struct rte_hash_bucket *prim_bkt,
1847                         const struct rte_hash_bucket *sec_bkt,
1848                         uint16_t sig,
1849                         enum rte_hash_sig_compare_function sig_cmp_fn)
1850 {
1851         unsigned int i;
1852
1853         /* For match mask the first bit of every two bits indicates the match */
1854         switch (sig_cmp_fn) {
1855 #if defined(__SSE2__)
1856         case RTE_HASH_COMPARE_SSE:
1857                 /* Compare all signatures in the bucket */
1858                 *prim_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1859                                 _mm_load_si128(
1860                                         (__m128i const *)prim_bkt->sig_current),
1861                                 _mm_set1_epi16(sig)));
1862                 /* Compare all signatures in the bucket */
1863                 *sec_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1864                                 _mm_load_si128(
1865                                         (__m128i const *)sec_bkt->sig_current),
1866                                 _mm_set1_epi16(sig)));
1867                 break;
1868 #elif defined(__ARM_NEON)
1869         case RTE_HASH_COMPARE_NEON: {
1870                 uint16x8_t vmat, vsig, x;
1871                 int16x8_t shift = {-15, -13, -11, -9, -7, -5, -3, -1};
1872
1873                 vsig = vld1q_dup_u16((uint16_t const *)&sig);
1874                 /* Compare all signatures in the primary bucket */
1875                 vmat = vceqq_u16(vsig,
1876                         vld1q_u16((uint16_t const *)prim_bkt->sig_current));
1877                 x = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x8000)), shift);
1878                 *prim_hash_matches = (uint32_t)(vaddvq_u16(x));
1879                 /* Compare all signatures in the secondary bucket */
1880                 vmat = vceqq_u16(vsig,
1881                         vld1q_u16((uint16_t const *)sec_bkt->sig_current));
1882                 x = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x8000)), shift);
1883                 *sec_hash_matches = (uint32_t)(vaddvq_u16(x));
1884                 }
1885                 break;
1886 #endif
1887         default:
1888                 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1889                         *prim_hash_matches |=
1890                                 ((sig == prim_bkt->sig_current[i]) << (i << 1));
1891                         *sec_hash_matches |=
1892                                 ((sig == sec_bkt->sig_current[i]) << (i << 1));
1893                 }
1894         }
1895 }
1896
1897 static inline void
1898 __bulk_lookup_l(const struct rte_hash *h, const void **keys,
1899                 const struct rte_hash_bucket **primary_bkt,
1900                 const struct rte_hash_bucket **secondary_bkt,
1901                 uint16_t *sig, int32_t num_keys, int32_t *positions,
1902                 uint64_t *hit_mask, void *data[])
1903 {
1904         uint64_t hits = 0;
1905         int32_t i;
1906         int32_t ret;
1907         uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1908         uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1909         struct rte_hash_bucket *cur_bkt, *next_bkt;
1910
1911         __hash_rw_reader_lock(h);
1912
1913         /* Compare signatures and prefetch key slot of first hit */
1914         for (i = 0; i < num_keys; i++) {
1915                 compare_signatures(&prim_hitmask[i], &sec_hitmask[i],
1916                         primary_bkt[i], secondary_bkt[i],
1917                         sig[i], h->sig_cmp_fn);
1918
1919                 if (prim_hitmask[i]) {
1920                         uint32_t first_hit =
1921                                         __builtin_ctzl(prim_hitmask[i])
1922                                         >> 1;
1923                         uint32_t key_idx =
1924                                 primary_bkt[i]->key_idx[first_hit];
1925                         const struct rte_hash_key *key_slot =
1926                                 (const struct rte_hash_key *)(
1927                                 (const char *)h->key_store +
1928                                 key_idx * h->key_entry_size);
1929                         rte_prefetch0(key_slot);
1930                         continue;
1931                 }
1932
1933                 if (sec_hitmask[i]) {
1934                         uint32_t first_hit =
1935                                         __builtin_ctzl(sec_hitmask[i])
1936                                         >> 1;
1937                         uint32_t key_idx =
1938                                 secondary_bkt[i]->key_idx[first_hit];
1939                         const struct rte_hash_key *key_slot =
1940                                 (const struct rte_hash_key *)(
1941                                 (const char *)h->key_store +
1942                                 key_idx * h->key_entry_size);
1943                         rte_prefetch0(key_slot);
1944                 }
1945         }
1946
1947         /* Compare keys, first hits in primary first */
1948         for (i = 0; i < num_keys; i++) {
1949                 positions[i] = -ENOENT;
1950                 while (prim_hitmask[i]) {
1951                         uint32_t hit_index =
1952                                         __builtin_ctzl(prim_hitmask[i])
1953                                         >> 1;
1954                         uint32_t key_idx =
1955                                 primary_bkt[i]->key_idx[hit_index];
1956                         const struct rte_hash_key *key_slot =
1957                                 (const struct rte_hash_key *)(
1958                                 (const char *)h->key_store +
1959                                 key_idx * h->key_entry_size);
1960
1961                         /*
1962                          * If key index is 0, do not compare key,
1963                          * as it is checking the dummy slot
1964                          */
1965                         if (!!key_idx &
1966                                 !rte_hash_cmp_eq(
1967                                         key_slot->key, keys[i], h)) {
1968                                 if (data != NULL)
1969                                         data[i] = key_slot->pdata;
1970
1971                                 hits |= 1ULL << i;
1972                                 positions[i] = key_idx - 1;
1973                                 goto next_key;
1974                         }
1975                         prim_hitmask[i] &= ~(3ULL << (hit_index << 1));
1976                 }
1977
1978                 while (sec_hitmask[i]) {
1979                         uint32_t hit_index =
1980                                         __builtin_ctzl(sec_hitmask[i])
1981                                         >> 1;
1982                         uint32_t key_idx =
1983                                 secondary_bkt[i]->key_idx[hit_index];
1984                         const struct rte_hash_key *key_slot =
1985                                 (const struct rte_hash_key *)(
1986                                 (const char *)h->key_store +
1987                                 key_idx * h->key_entry_size);
1988
1989                         /*
1990                          * If key index is 0, do not compare key,
1991                          * as it is checking the dummy slot
1992                          */
1993
1994                         if (!!key_idx &
1995                                 !rte_hash_cmp_eq(
1996                                         key_slot->key, keys[i], h)) {
1997                                 if (data != NULL)
1998                                         data[i] = key_slot->pdata;
1999
2000                                 hits |= 1ULL << i;
2001                                 positions[i] = key_idx - 1;
2002                                 goto next_key;
2003                         }
2004                         sec_hitmask[i] &= ~(3ULL << (hit_index << 1));
2005                 }
2006 next_key:
2007                 continue;
2008         }
2009
2010         /* all found, do not need to go through ext bkt */
2011         if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {
2012                 if (hit_mask != NULL)
2013                         *hit_mask = hits;
2014                 __hash_rw_reader_unlock(h);
2015                 return;
2016         }
2017
2018         /* need to check ext buckets for match */
2019         for (i = 0; i < num_keys; i++) {
2020                 if ((hits & (1ULL << i)) != 0)
2021                         continue;
2022                 next_bkt = secondary_bkt[i]->next;
2023                 FOR_EACH_BUCKET(cur_bkt, next_bkt) {
2024                         if (data != NULL)
2025                                 ret = search_one_bucket_l(h, keys[i],
2026                                                 sig[i], &data[i], cur_bkt);
2027                         else
2028                                 ret = search_one_bucket_l(h, keys[i],
2029                                                 sig[i], NULL, cur_bkt);
2030                         if (ret != -1) {
2031                                 positions[i] = ret;
2032                                 hits |= 1ULL << i;
2033                                 break;
2034                         }
2035                 }
2036         }
2037
2038         __hash_rw_reader_unlock(h);
2039
2040         if (hit_mask != NULL)
2041                 *hit_mask = hits;
2042 }
2043
2044 static inline void
2045 __bulk_lookup_lf(const struct rte_hash *h, const void **keys,
2046                 const struct rte_hash_bucket **primary_bkt,
2047                 const struct rte_hash_bucket **secondary_bkt,
2048                 uint16_t *sig, int32_t num_keys, int32_t *positions,
2049                 uint64_t *hit_mask, void *data[])
2050 {
2051         uint64_t hits = 0;
2052         int32_t i;
2053         int32_t ret;
2054         uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
2055         uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
2056         struct rte_hash_bucket *cur_bkt, *next_bkt;
2057         uint32_t cnt_b, cnt_a;
2058
2059         for (i = 0; i < num_keys; i++)
2060                 positions[i] = -ENOENT;
2061
2062         do {
2063                 /* Load the table change counter before the lookup
2064                  * starts. Acquire semantics will make sure that
2065                  * loads in compare_signatures are not hoisted.
2066                  */
2067                 cnt_b = __atomic_load_n(h->tbl_chng_cnt,
2068                                         __ATOMIC_ACQUIRE);
2069
2070                 /* Compare signatures and prefetch key slot of first hit */
2071                 for (i = 0; i < num_keys; i++) {
2072                         compare_signatures(&prim_hitmask[i], &sec_hitmask[i],
2073                                 primary_bkt[i], secondary_bkt[i],
2074                                 sig[i], h->sig_cmp_fn);
2075
2076                         if (prim_hitmask[i]) {
2077                                 uint32_t first_hit =
2078                                                 __builtin_ctzl(prim_hitmask[i])
2079                                                 >> 1;
2080                                 uint32_t key_idx =
2081                                         primary_bkt[i]->key_idx[first_hit];
2082                                 const struct rte_hash_key *key_slot =
2083                                         (const struct rte_hash_key *)(
2084                                         (const char *)h->key_store +
2085                                         key_idx * h->key_entry_size);
2086                                 rte_prefetch0(key_slot);
2087                                 continue;
2088                         }
2089
2090                         if (sec_hitmask[i]) {
2091                                 uint32_t first_hit =
2092                                                 __builtin_ctzl(sec_hitmask[i])
2093                                                 >> 1;
2094                                 uint32_t key_idx =
2095                                         secondary_bkt[i]->key_idx[first_hit];
2096                                 const struct rte_hash_key *key_slot =
2097                                         (const struct rte_hash_key *)(
2098                                         (const char *)h->key_store +
2099                                         key_idx * h->key_entry_size);
2100                                 rte_prefetch0(key_slot);
2101                         }
2102                 }
2103
2104                 /* Compare keys, first hits in primary first */
2105                 for (i = 0; i < num_keys; i++) {
2106                         while (prim_hitmask[i]) {
2107                                 uint32_t hit_index =
2108                                                 __builtin_ctzl(prim_hitmask[i])
2109                                                 >> 1;
2110                                 uint32_t key_idx =
2111                                 __atomic_load_n(
2112                                         &primary_bkt[i]->key_idx[hit_index],
2113                                         __ATOMIC_ACQUIRE);
2114                                 const struct rte_hash_key *key_slot =
2115                                         (const struct rte_hash_key *)(
2116                                         (const char *)h->key_store +
2117                                         key_idx * h->key_entry_size);
2118
2119                                 /*
2120                                  * If key index is 0, do not compare key,
2121                                  * as it is checking the dummy slot
2122                                  */
2123                                 if (!!key_idx &
2124                                         !rte_hash_cmp_eq(
2125                                                 key_slot->key, keys[i], h)) {
2126                                         if (data != NULL)
2127                                                 data[i] = __atomic_load_n(
2128                                                         &key_slot->pdata,
2129                                                         __ATOMIC_ACQUIRE);
2130
2131                                         hits |= 1ULL << i;
2132                                         positions[i] = key_idx - 1;
2133                                         goto next_key;
2134                                 }
2135                                 prim_hitmask[i] &= ~(3ULL << (hit_index << 1));
2136                         }
2137
2138                         while (sec_hitmask[i]) {
2139                                 uint32_t hit_index =
2140                                                 __builtin_ctzl(sec_hitmask[i])
2141                                                 >> 1;
2142                                 uint32_t key_idx =
2143                                 __atomic_load_n(
2144                                         &secondary_bkt[i]->key_idx[hit_index],
2145                                         __ATOMIC_ACQUIRE);
2146                                 const struct rte_hash_key *key_slot =
2147                                         (const struct rte_hash_key *)(
2148                                         (const char *)h->key_store +
2149                                         key_idx * h->key_entry_size);
2150
2151                                 /*
2152                                  * If key index is 0, do not compare key,
2153                                  * as it is checking the dummy slot
2154                                  */
2155
2156                                 if (!!key_idx &
2157                                         !rte_hash_cmp_eq(
2158                                                 key_slot->key, keys[i], h)) {
2159                                         if (data != NULL)
2160                                                 data[i] = __atomic_load_n(
2161                                                         &key_slot->pdata,
2162                                                         __ATOMIC_ACQUIRE);
2163
2164                                         hits |= 1ULL << i;
2165                                         positions[i] = key_idx - 1;
2166                                         goto next_key;
2167                                 }
2168                                 sec_hitmask[i] &= ~(3ULL << (hit_index << 1));
2169                         }
2170 next_key:
2171                         continue;
2172                 }
2173
2174                 /* all found, do not need to go through ext bkt */
2175                 if (hits == ((1ULL << num_keys) - 1)) {
2176                         if (hit_mask != NULL)
2177                                 *hit_mask = hits;
2178                         return;
2179                 }
2180                 /* need to check ext buckets for match */
2181                 if (h->ext_table_support) {
2182                         for (i = 0; i < num_keys; i++) {
2183                                 if ((hits & (1ULL << i)) != 0)
2184                                         continue;
2185                                 next_bkt = secondary_bkt[i]->next;
2186                                 FOR_EACH_BUCKET(cur_bkt, next_bkt) {
2187                                         if (data != NULL)
2188                                                 ret = search_one_bucket_lf(h,
2189                                                         keys[i], sig[i],
2190                                                         &data[i], cur_bkt);
2191                                         else
2192                                                 ret = search_one_bucket_lf(h,
2193                                                                 keys[i], sig[i],
2194                                                                 NULL, cur_bkt);
2195                                         if (ret != -1) {
2196                                                 positions[i] = ret;
2197                                                 hits |= 1ULL << i;
2198                                                 break;
2199                                         }
2200                                 }
2201                         }
2202                 }
2203                 /* The loads of sig_current in compare_signatures
2204                  * should not move below the load from tbl_chng_cnt.
2205                  */
2206                 __atomic_thread_fence(__ATOMIC_ACQUIRE);
2207                 /* Re-read the table change counter to check if the
2208                  * table has changed during search. If yes, re-do
2209                  * the search.
2210                  * This load should not get hoisted. The load
2211                  * acquires on cnt_b, primary key index and secondary
2212                  * key index will make sure that it does not get
2213                  * hoisted.
2214                  */
2215                 cnt_a = __atomic_load_n(h->tbl_chng_cnt,
2216                                         __ATOMIC_ACQUIRE);
2217         } while (cnt_b != cnt_a);
2218
2219         if (hit_mask != NULL)
2220                 *hit_mask = hits;
2221 }
2222
2223 #define PREFETCH_OFFSET 4
2224 static inline void
2225 __bulk_lookup_prefetching_loop(const struct rte_hash *h,
2226         const void **keys, int32_t num_keys,
2227         uint16_t *sig,
2228         const struct rte_hash_bucket **primary_bkt,
2229         const struct rte_hash_bucket **secondary_bkt)
2230 {
2231         int32_t i;
2232         uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
2233         uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
2234         uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
2235
2236         /* Prefetch first keys */
2237         for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
2238                 rte_prefetch0(keys[i]);
2239
2240         /*
2241          * Prefetch rest of the keys, calculate primary and
2242          * secondary bucket and prefetch them
2243          */
2244         for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
2245                 rte_prefetch0(keys[i + PREFETCH_OFFSET]);
2246
2247                 prim_hash[i] = rte_hash_hash(h, keys[i]);
2248
2249                 sig[i] = get_short_sig(prim_hash[i]);
2250                 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
2251                 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
2252
2253                 primary_bkt[i] = &h->buckets[prim_index[i]];
2254                 secondary_bkt[i] = &h->buckets[sec_index[i]];
2255
2256                 rte_prefetch0(primary_bkt[i]);
2257                 rte_prefetch0(secondary_bkt[i]);
2258         }
2259
2260         /* Calculate and prefetch rest of the buckets */
2261         for (; i < num_keys; i++) {
2262                 prim_hash[i] = rte_hash_hash(h, keys[i]);
2263
2264                 sig[i] = get_short_sig(prim_hash[i]);
2265                 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
2266                 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
2267
2268                 primary_bkt[i] = &h->buckets[prim_index[i]];
2269                 secondary_bkt[i] = &h->buckets[sec_index[i]];
2270
2271                 rte_prefetch0(primary_bkt[i]);
2272                 rte_prefetch0(secondary_bkt[i]);
2273         }
2274 }
2275
2276
2277 static inline void
2278 __rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys,
2279                         int32_t num_keys, int32_t *positions,
2280                         uint64_t *hit_mask, void *data[])
2281 {
2282         uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
2283         const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2284         const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2285
2286         __bulk_lookup_prefetching_loop(h, keys, num_keys, sig,
2287                 primary_bkt, secondary_bkt);
2288
2289         __bulk_lookup_l(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
2290                 positions, hit_mask, data);
2291 }
2292
2293 static inline void
2294 __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
2295                         int32_t num_keys, int32_t *positions,
2296                         uint64_t *hit_mask, void *data[])
2297 {
2298         uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
2299         const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2300         const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2301
2302         __bulk_lookup_prefetching_loop(h, keys, num_keys, sig,
2303                 primary_bkt, secondary_bkt);
2304
2305         __bulk_lookup_lf(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
2306                 positions, hit_mask, data);
2307 }
2308
2309 static inline void
2310 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
2311                         int32_t num_keys, int32_t *positions,
2312                         uint64_t *hit_mask, void *data[])
2313 {
2314         if (h->readwrite_concur_lf_support)
2315                 __rte_hash_lookup_bulk_lf(h, keys, num_keys, positions,
2316                                           hit_mask, data);
2317         else
2318                 __rte_hash_lookup_bulk_l(h, keys, num_keys, positions,
2319                                          hit_mask, data);
2320 }
2321
2322 int
2323 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
2324                       uint32_t num_keys, int32_t *positions)
2325 {
2326         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
2327                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
2328                         (positions == NULL)), -EINVAL);
2329
2330         __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL);
2331         return 0;
2332 }
2333
2334 int
2335 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
2336                       uint32_t num_keys, uint64_t *hit_mask, void *data[])
2337 {
2338         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
2339                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
2340                         (hit_mask == NULL)), -EINVAL);
2341
2342         int32_t positions[num_keys];
2343
2344         __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data);
2345
2346         /* Return number of hits */
2347         return __builtin_popcountl(*hit_mask);
2348 }
2349
2350
2351 static inline void
2352 __rte_hash_lookup_with_hash_bulk_l(const struct rte_hash *h,
2353                         const void **keys, hash_sig_t *prim_hash,
2354                         int32_t num_keys, int32_t *positions,
2355                         uint64_t *hit_mask, void *data[])
2356 {
2357         int32_t i;
2358         uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
2359         uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
2360         uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
2361         const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2362         const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2363
2364         /*
2365          * Prefetch keys, calculate primary and
2366          * secondary bucket and prefetch them
2367          */
2368         for (i = 0; i < num_keys; i++) {
2369                 rte_prefetch0(keys[i]);
2370
2371                 sig[i] = get_short_sig(prim_hash[i]);
2372                 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
2373                 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
2374
2375                 primary_bkt[i] = &h->buckets[prim_index[i]];
2376                 secondary_bkt[i] = &h->buckets[sec_index[i]];
2377
2378                 rte_prefetch0(primary_bkt[i]);
2379                 rte_prefetch0(secondary_bkt[i]);
2380         }
2381
2382         __bulk_lookup_l(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
2383                 positions, hit_mask, data);
2384 }
2385
2386 static inline void
2387 __rte_hash_lookup_with_hash_bulk_lf(const struct rte_hash *h,
2388                         const void **keys, hash_sig_t *prim_hash,
2389                         int32_t num_keys, int32_t *positions,
2390                         uint64_t *hit_mask, void *data[])
2391 {
2392         int32_t i;
2393         uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
2394         uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
2395         uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
2396         const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2397         const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
2398
2399         /*
2400          * Prefetch keys, calculate primary and
2401          * secondary bucket and prefetch them
2402          */
2403         for (i = 0; i < num_keys; i++) {
2404                 rte_prefetch0(keys[i]);
2405
2406                 sig[i] = get_short_sig(prim_hash[i]);
2407                 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
2408                 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
2409
2410                 primary_bkt[i] = &h->buckets[prim_index[i]];
2411                 secondary_bkt[i] = &h->buckets[sec_index[i]];
2412
2413                 rte_prefetch0(primary_bkt[i]);
2414                 rte_prefetch0(secondary_bkt[i]);
2415         }
2416
2417         __bulk_lookup_lf(h, keys, primary_bkt, secondary_bkt, sig, num_keys,
2418                 positions, hit_mask, data);
2419 }
2420
2421 static inline void
2422 __rte_hash_lookup_with_hash_bulk(const struct rte_hash *h, const void **keys,
2423                         hash_sig_t *prim_hash, int32_t num_keys,
2424                         int32_t *positions, uint64_t *hit_mask, void *data[])
2425 {
2426         if (h->readwrite_concur_lf_support)
2427                 __rte_hash_lookup_with_hash_bulk_lf(h, keys, prim_hash,
2428                                 num_keys, positions, hit_mask, data);
2429         else
2430                 __rte_hash_lookup_with_hash_bulk_l(h, keys, prim_hash,
2431                                 num_keys, positions, hit_mask, data);
2432 }
2433
2434 int
2435 rte_hash_lookup_with_hash_bulk(const struct rte_hash *h, const void **keys,
2436                 hash_sig_t *sig, uint32_t num_keys, int32_t *positions)
2437 {
2438         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) ||
2439                         (sig == NULL) || (num_keys == 0) ||
2440                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
2441                         (positions == NULL)), -EINVAL);
2442
2443         __rte_hash_lookup_with_hash_bulk(h, keys, sig, num_keys,
2444                 positions, NULL, NULL);
2445         return 0;
2446 }
2447
2448 int
2449 rte_hash_lookup_with_hash_bulk_data(const struct rte_hash *h,
2450                 const void **keys, hash_sig_t *sig,
2451                 uint32_t num_keys, uint64_t *hit_mask, void *data[])
2452 {
2453         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) ||
2454                         (sig == NULL) || (num_keys == 0) ||
2455                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
2456                         (hit_mask == NULL)), -EINVAL);
2457
2458         int32_t positions[num_keys];
2459
2460         __rte_hash_lookup_with_hash_bulk(h, keys, sig, num_keys,
2461                         positions, hit_mask, data);
2462
2463         /* Return number of hits */
2464         return __builtin_popcountl(*hit_mask);
2465 }
2466
2467 int32_t
2468 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
2469 {
2470         uint32_t bucket_idx, idx, position;
2471         struct rte_hash_key *next_key;
2472
2473         RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
2474
2475         const uint32_t total_entries_main = h->num_buckets *
2476                                                         RTE_HASH_BUCKET_ENTRIES;
2477         const uint32_t total_entries = total_entries_main << 1;
2478
2479         /* Out of bounds of all buckets (both main table and ext table) */
2480         if (*next >= total_entries_main)
2481                 goto extend_table;
2482
2483         /* Calculate bucket and index of current iterator */
2484         bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
2485         idx = *next % RTE_HASH_BUCKET_ENTRIES;
2486
2487         /* If current position is empty, go to the next one */
2488         while ((position = __atomic_load_n(&h->buckets[bucket_idx].key_idx[idx],
2489                                         __ATOMIC_ACQUIRE)) == EMPTY_SLOT) {
2490                 (*next)++;
2491                 /* End of table */
2492                 if (*next == total_entries_main)
2493                         goto extend_table;
2494                 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
2495                 idx = *next % RTE_HASH_BUCKET_ENTRIES;
2496         }
2497
2498         __hash_rw_reader_lock(h);
2499         next_key = (struct rte_hash_key *) ((char *)h->key_store +
2500                                 position * h->key_entry_size);
2501         /* Return key and data */
2502         *key = next_key->key;
2503         *data = next_key->pdata;
2504
2505         __hash_rw_reader_unlock(h);
2506
2507         /* Increment iterator */
2508         (*next)++;
2509
2510         return position - 1;
2511
2512 /* Begin to iterate extendable buckets */
2513 extend_table:
2514         /* Out of total bound or if ext bucket feature is not enabled */
2515         if (*next >= total_entries || !h->ext_table_support)
2516                 return -ENOENT;
2517
2518         bucket_idx = (*next - total_entries_main) / RTE_HASH_BUCKET_ENTRIES;
2519         idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
2520
2521         while ((position = h->buckets_ext[bucket_idx].key_idx[idx]) == EMPTY_SLOT) {
2522                 (*next)++;
2523                 if (*next == total_entries)
2524                         return -ENOENT;
2525                 bucket_idx = (*next - total_entries_main) /
2526                                                 RTE_HASH_BUCKET_ENTRIES;
2527                 idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
2528         }
2529         __hash_rw_reader_lock(h);
2530         next_key = (struct rte_hash_key *) ((char *)h->key_store +
2531                                 position * h->key_entry_size);
2532         /* Return key and data */
2533         *key = next_key->key;
2534         *data = next_key->pdata;
2535
2536         __hash_rw_reader_unlock(h);
2537
2538         /* Increment iterator */
2539         (*next)++;
2540         return position - 1;
2541 }