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